В рамках проекта John the Ripper найдены упрощенные выражения для S-box'ов DES24.06.2011 20: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.