The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]

В рамках проекта John the Ripper найдены упрощенные выражения для S-box'ов DES

24.06.2011 21:58

Вышел релиз John the Ripper 1.7.8, включающий новые, упрощенные логические выражения, реализующие так называемые S-box'ы (S-блоки, блоки подстановок) в блочном шифре DES, на основе которого построены также некоторые методы хеширования паролей, включая традиционный crypt(3), используемый в Unix начиная с конца 1970-х годов.

Новые логические выражения на 17% проще известных ранее лучших результатов для тех же наборов логических операций. В частности, для набора {AND, OR, XOR, NOT, AND-NOT}, соответствующего типичным процессорам x86 (MMX, SSE2, AVX) и RISC, результат улучшен с 53.375 до 44.125 логических операций на S-box (в среднем для всех восьми S-box'ов). Для набора, содержащего операцию выбора битов, присутствующую на процессорах Cell, PowerPC с AltiVec, будущих x86 процессорах от AMD (начиная с Bulldozer) с расширениями XOP, а также новых видеокартах от ATI/AMD, результат улучшен с 39.875 до 32.875.

Это - результат многомесячной работы, проведенной Романом Русаковым (новый подход к проблеме оптимизации логических выражений для DES, реализация) и Александром Песляком (генерация программного кода с учетом особенностей процессорных архитектур, что повлияло на выбор конкретных логических выражений из тысяч с одинаковым количеством логических операций). Потребовались также месяцы процессорного времени и гигабайты оперативной памяти, что в конце 1990-х годов, когда были получены некоторые из лучших предыдущих результатов, было доступно не каждому исследователю.

Спонсором исследования выступила компания Rapid7. Несмотря на вложения в проект, результаты доступны свободно, и как Openwall, так и Rapid7 лишь рады использованию этих результатов в других разработках, в том числе "конкурирующих", как свободных, так и закрытых. Сами логические выражения, будучи математическими формулами, не являются объектом авторских прав. Соответствующий программный код, в том числе ассемблерный, сгенерированный специальным оптимизатором и доведенный вручную, доступен под сокращенной лицензией BSD (совсем не накладывающей ограничений). Компания ElcomSoft уже выразила намерение использовать полученные результаты в своих продуктах (закрытых).

В анонсе John the Ripper 1.7.8 приводятся новые результаты скорости подбора паролей для традиционного crypt(3), содержащего 25 итераций модифицированного DES, на процессоре Core i7-2600K 3.4 GHz с использованием AVX. На одном ядре такого процессора, при отсутствии совпадающих salt'ов, достигается скорость в 5.7 миллионов комбинаций {проверяемый пароль, подбираемый хеш} в секунду. Сборка с поддержкой OpenMP проверяет 20.6 миллионов комбинаций в секунду (задействуя все 4 ядра и 8 логических процессоров). Это соответствует более чем 500 миллионам 64-битных DES-шифрований в секунду, или скорости шифрования в 33 Gbps (теоретической, так как практическая реализация встретила бы ограничение пропускной способности шины и т.д.) Также, любопытно что одно DES-шифрование (все 16 раундов, где каждый раунд включает восемь подстановок) выполняется в среднем всего лишь за 7 тактов процессора. (Реально в этом тесте в каждый момент времени выполняется как минимум 1024 DES-шифрования, суммарно на разных логических процессорах и в разных битовых слоях AVX-регистров.)

Другие изменения в версии 1.7.8 включают исправление проблемы с расширением знака в реализации хешей bcrypt, при этом сохраняя и поддержку "неправильных" хешей используя новый префикс "$2x$" (отличие проявляется только на 8-битных символах), повышение производительности виртуальной машины для реализации внешних режимов подбора паролей (задаваемых на Си-подобном языке в конфигурационном файле), а также дополнительный пример внешнего режима (добавление контрольной цифры по алгоритму Луна).

Недавние изменения в ветке John the Ripper, развиваемой с более активным участием сообщества (версии с суффиксом -jumbo), включают поддержку большего количества типов не-хешей: секретные ключи SSH, файлы PDF, архивы RAR, ZIP (проект Dhiru Kholia в рамках GSoC 2011), а также поддержку UTF-8 с трансляцией в UCS-2 для типов хешей, использующих такое представление, интеграцию поддержки MPI (ранее отдельный патч) и многое другое (в основном работа magnum, JimF, bartavelle). Скорость подбора парольной фразы к шифрованному закрытому ключу от OpenSSH на одном компьютере составляет сотни тысяч вариантов в секунду (поддерживается OpenMP-параллелизация). Реализацией поддержки GPU, пока что для "медленных" типов хешей, занимается Lukas Odzioba в рамках GSoC 2011.

  1. Главная ссылка к новости (http://www.openwall.com/lists/...)
Автор новости: solardiz
Тип: К сведению
Ключевые слова: des, password, hash, crypt
При перепечатке указание ссылки на opennet.ru обязательно
Обсуждение (22) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.1, Sylvia (ok), 22:17, 24/06/2011 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    solardiz, неужели DES/3DES все еще актуальны для хешей паролей в 2011 году ?
     
     
  • 2.3, solardiz (ok), 22:33, 24/06/2011 [^] [^^] [^^^] [ответить]  
  • +4 +/
    > неужели DES/3DES все еще актуальны для хешей паролей в 2011 году ?

    3DES никогда не был (не для хешей).

    DES-based crypt(3) еще актуален - не столько для админов серверов (им надо исправлять настройки), сколько для тех кто занят compliance'ом (PCI DSS и т.п.) и pentesting'ом. Вон, недавно одна крупная международная компания, купившая JtR Pro, консультировалась со мной по настройке ежемесячного аудита DES-based crypt(3) хешей на паре сотен Solaris'овых серверов для соответствия PCI DSS. Для реальной безопасности - толку мало - во всяком случае, это не лучшая трата времени (лучше бы исправить настройки). Но спрос есть, в том числе коммерческий.

    Также, иногда утекают и публикуются базы паролей, хешированных DES-based crypt(3) - например, Gawker. Эти пароли - полезное дополнение для оптимизации алгоритмов перебора (.chr файлы, правила).

     
     
  • 3.4, Sylvia (ok), 22:50, 24/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    спасибо за уточнение )
    впрочем, "никогда" это все же не совсем верно, в RedHat 4.0 (1996 год) применялись 3DES хеши для пароля, причем всё было открыто в /etc/passwd и John the Ripper тогда уже существовал ;)
     
     
  • 4.9, solardiz (ok), 23:14, 24/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    > впрочем, "никогда" это все же не совсем верно, в RedHat 4.0 (1996 год) применялись 3DES хеши для пароля

    Ты плохо помнишь. Там был обычный DES-based crypt(3), как и на Slackware 3.x того же времени. И то и другое у меня еще сохранилось (правда, с моими же переделками за те годы, включая BSDI'ные хеши в клоне libc5). ;-)

    В Linux-PAM, который начали использовать в Red Hat Linux очень рано, была поддержка bigcrypt, но это никакой не 3DES.

     
     
  • 5.10, Sylvia (ok), 23:50, 24/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    времени прошло много, так что могу и уже не помнить DES там был или 3DES, а вот слака достаточно быстро перешла на использование shadow и MD5 passwords, blowfish тогда тоже уже был как альтернатива, но от Вас я брала только патчи на ядро, тогда еще 2.2 ;) менять crypt было уж слишком для меня )

     
     
  • 6.12, solardiz (ok), 00:41, 25/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    Надеюсь, не обидел обращением на ты - привык еще с фидо и т.п. Ко мне тоже можно на ты, хотя можно и по-всякому.

    По теме: во всех известных мне crypt()'ах на основе DES применяется почти одинаковая модификация DES - для реализации salt'ов. (Собственно DES получается лишь при нулевом salt'е. Для всех других значений salt'а - это не совсем DES.) Отличаются они размером salt'ов (12 или 24 бита), количеством итераций модифицированного-DES (25, либо 20+5 на две половинки в crypt16, либо переменное количество в BSDI), отсутствием или наличием поддержки паролей длиннее 8 символов и способом ее реализации (crypt16 vs. bigcrypt). 3DES там ни при чем.

    Но это действительно уже почти история.

     

  • 1.5, anonymous (??), 22:52, 24/06/2011 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    > Скорость подбора SSH-ключей на одном компьютере с поддержкой OpenMP составляет сотни тысяч вариантов парольной фразы в секунду

    Непонятно написано, подбирался закрытый ключ по заданному открытому, или по заданной паре открытый / шифрованный закрытый подбирался пароль к последнему?

     
     
  • 2.8, solardiz (ok), 23:02, 24/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    > подбирался закрытый ключ по заданному открытому, или по заданной паре открытый / шифрованный закрытый подбирался пароль к последнему?

    Подбирается парольная фраза к шифрованному закрытому ключу. Высокая скорость перебора означает, что такие фразы надо делать более сложными, чем типичные пароли: http://openwall.info/wiki/internal/ssh (А также то, что разработчикам OpenSSH есть что улучшить. Они в курсе.)

     

  • 1.6, ВКПб (?), 22:54, 24/06/2011 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    А какое шифрование не брутфорсится на видеокартах?
     
     
  • 2.7, solardiz (ok), 22:57, 24/06/2011 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Blowfish, и соответственно bcrypt, не реализуется на нынешних видеокартах эффективно: http://www.golubev.com/blog/?p=94
     
     
  • 3.11, pavlinux (ok), 00:32, 25/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    Вроде автор блоуфиша сам писал, что не надо его юзать. Туфиш юзайте.
     
     
  • 4.13, solardiz (ok), 00:53, 25/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    > Вроде автор блоуфиша сам писал, что не надо его юзать. Туфиш юзайте.

    Twofish - более новая разработка, финалист в конкурсе на AES. Как шифр, он может быть лучше. Но это не означает, что с Blowfish какие-то проблемы, а даже если бы и были, это почти наверняка не влияло бы на использование для хеширования паролей. Так что просто так переделывать bcrypt с Blowfish на Twofish нет никакого смысла. Если что-то в этой области делать, то совсем другое:
    http://www.openwall.com/lists/crypt-dev/2011/04/05/2
    http://www.openwall.com/lists/crypt-dev/2011/05/09/1

     
     
  • 5.14, pavlinux (ok), 00:56, 25/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    >> Вроде автор блоуфиша сам писал, что не надо его юзать. Туфиш юзайте.
    > Twofish - более новая разработка, финалист в конкурсе на AES.

    Сейчас у него на сайте роюсь,... где-то там читал...

    ---

    Ладно, вот скажи как криптоаналитик, криптоаналитику, =)
    когда правительства разрешать шифры с более чем 512-битным
    секретным ключом?

     
     
  • 6.15, solardiz (ok), 01:25, 25/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    > Сейчас у него на сайте роюсь,... где-то там читал...

    Так я не спорю. Да, авторы Twofish рекомендуют использовать Twofish, а не Blowfish, для новых разработок. Но не по причине "взлома" Blowfish, которого не было, и который, если бы и был, не относился бы к этой теме.

    > Ладно, вот скажи как криптоаналитик

    Я не считаю себя криптоаналитиком. Я разбираюсь в том, как (не) применять криптографические примитивы и т.п., но я не возьмусь, например, за криптоанализ какого-либо блочного шифра, или во всяком случае не как специалист.

    > когда правительства разрешать шифры с более чем 512-битным секретным ключом?

    Это тоже должно быть смешно? Давай просто закроем эту ветку.

     
  • 6.17, Аноним (-), 14:24, 25/06/2011 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > когда правительства разрешать шифры с более чем 512-битным

    секретным ключом?
    А они запрещены? Обычно очень длинный ключ не используют сугубо по практическим соображениям: шифрование это наука о том как заменить большой секрет маленьким. Тем более что если криптоалгоритм реализован качественно и упростить его не удалось, перебрать 2^512 значений попросту невозможно чисто физически: если на элементарную операцию расходуется хоть какая-то кроха энергии, при 2^512 тебе не хватит энергии во всей вселенной :). По грубым прикидкам, даже квантовых компьютеров можно не бояться уже с 256-битным ключом. А с 512-битным - солнце погаснет раньше чем его подберут.

     
  • 4.21, anonymous vulgaris (?), 01:40, 26/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    >Вроде автор блоуфиша сам писал, что не надо его юзать. Туфиш юзайте.

    Дык это вроде ему АНБ такую рекламу проплатило?

     
  • 2.20, solardiz (ok), 20:27, 25/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    В дополнение к моему предыдущему ответу, на видеокартах также не реализуются эффективно sequential memory-hard functions: http://www.tarsnap.com/scrypt.html

    Количество thread'ов и их быстродействие ограничиваются объемом памяти и пропускной способностью шины памяти видеокарты. Например, если на компьютере можно позволить себе потратить 512 MB памяти на одну операцию вычисления ключа (key derivation), и причем уже через несколько секунд эта память будет возвращена системе, то на видеокарте с 1 GB памяти поместится всего лишь 2 таких параллельных вычисления.

     

  • 1.16, Аноним (-), 14:15, 25/06/2011 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Было бы круто. Лет ...цать назад. А что, кто-то еще не выбросил DES на помойку? Он же уже давно тупым перебором на небольшом кластере за неделю крякается, улучшение на еще сколько-то процентов мало что в этом меняет.
     
     
  • 2.19, solardiz (ok), 18:32, 25/06/2011 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Чистый DES - да А те же crypt 3 хеши на основе DES - уже не тупым перебором и ... текст свёрнут, показать
     

  • 1.18, Аноним (-), 14:25, 25/06/2011 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    > А что, кто-то еще не выбросил DES на помойку?

    Solaris хотя бы. Возможно и еще какой некроЫнтерпрайз.

     
     
  • 2.22, Аноним (-), 19:24, 28/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    Ошибаешься, анон. В Солярисе это дефолтный алгоритм, но _не единственный_. Уже два года как поддерживается не только MD4 и BF, но и SHA256 и SHA512. Поскольку Солярис сертифицирован на FIPS-140-2.
     
     
  • 3.23, Аноним (-), 19:25, 28/06/2011 [^] [^^] [^^^] [ответить]  
  • +/
    > Ошибаешься, анон. В Солярисе это дефолтный алгоритм, но _не единственный_. Уже два
    > года как поддерживается не только MD4 и BF, но и SHA256
    > и SHA512. Поскольку Солярис сертифицирован на FIPS-140-2.

    Опечатался. MD5, конечно же.

     

     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Спонсоры:
    Слёрм
    Inferno Solutions
    Hosting by Ihor
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2019 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру