Бихам, Эли

Эли Бихам
אלי ביהם
Дата рождения:
Страна:	Израиль
Научная сфера:	математика, вычислительные системы
Место работы:	Израильский Технический Институт
Научный руководитель:	Ади Шамир
Известен как:	один из разработчиков дифференциального криптоанализа, разработчик множественных методов атак.

Эли Бихам (Иврит: אלי ביהם) — израильский криптограф и криптоаналитик. Являясь учеником известного израильского учёного Ади Шамира, вместе с ним разрабатывал диффиренциальный криптоанализ. Эта разработка позволила ему получить степень доктора. Но позднее было выяснено, что данный криптоанализ был уже известен и держался в секрете Агентством безопасности США и корпорацией IBM. С октября 2008 года является профессором Израильского Технического Института в области вычислительных систем. Помимо разработки различных методов криптоанализа Эли Бихам принимал участие в создании шифров (блоковый шифр Serpent, Py — один из семейства потоковых шифров) и хэш-функций (например Tiger).

Хэш-функция Tiger

Как известно, для защиты данных требуются надёжные хэш-функции (например цифровые подписи) и при этом они должны быстро обрабатываться. Так были созданы, как тогда показалось, мощные шифры из семейств MD4 и Snefru. Но, например для Snefru, в 1990 году были найдены коллизии, а затем они были обнаружены и для MD4, что ставило под сомнение всё семейство данных функций. Поэтому требовалось разработать новую, более криптоустойчивую хэш-функцию. К тому же все предыдущие хэш-функции были разработаны для 32-х битных процессоров, а уже началось появление нового поколения процессоров — 64-х битные. Поэтому в 1995 году Эли Бихам вместе с Россом Андерсоном разрабатывает новую мощную и быструю хэш-функцию под названием Tiger с размером значения хэша 192 бита, работавшую на 64-х битных машинах.

Блочный шифр Serpent

Для конкурса AES Эли Бихам вместе с Россом Андерсоном и Ларсом Кнудсеном создаёт симметричный блочный алгоритм шифрования Serpent («змея»), попавший в финал 2-го этапа конкурса. S-блоки были построены после тщательного изучения S-блоков в алгоритме DES, что позволило 16 раундовому новому алгоритму шифрования быть в 2 раза быстрее DES и при этом не менее надёжным. Затем была создана версия с 32-мя раундами, что ещё больше увеличило его криптостойкость. 32-битная версия не имеет уязвимостей.

Потоковый шифр Py

Проект eSTREAM был создан для выявления новых потоковых шифров, подходящий для широкого распространения, образованный европейской сетью ECRYPT. Он был создан после провала всех 6 потоковых шифров проекта NESSIE. Данный проект был разделён на отдельные этапы и его главной целью являлся поиск алгоритма подходящего для различных приложений. Эли Бихам вместе с Дженифер Себбери разрабатывает потоковый шифр Py, подчиняющийся именно этому проекту. Он является одним из самых быстрых шифров в eSTREAM, около 2.85 циклов на байт на Pentium III (более чем в 2,5 раза быстрее RC4). Он имеет структуру, похожую на RC4, но здесь добавлен массив из 260 32-битных слов, которые индексируются путём перестановок байт, и в каждом раунде получается 64 бита. Затем, в январе 2007 года Бихам и Себбери создали более мощные версии данного потокового шифра: TPy, TPy6, TPypy.

Дифференциальный криптоанализ

Работая с Ади Шамиром, Эли Бихам разрабатывает дифференциальный криптоанализ, за который он и получил степень доктора. В 1990 году публикуется работа Эли Бихама и Ади Шамира «Differential Cryptanalysis of DES-like Cryptosystems», в которой они показывают как при помощи дифференциального криатоанализа за несколько минут можно взломать 8 раундовый DES. Так например для 6-раундового DES использование дифференциального криптоанализа привело к тому, что на обыкновенном персональном компьютере он был взломан менее чем за 0,3 секунды, используя 240 шифротекстов. При 8-раундовом DES было использовано 1500 шифротекстов, при этом время, затраченное на взлом шифра составило около 2 минут. С 15-ти и 16-ти раундовыми DES оказалось сложнее, но тем не менее они могут быть взломаны за $2^{52}$ и $2^{58}$ шага соответственно. Ниже приведена таблица, в которой показано количество шагов, необходимых для взлома DES, в зависимости от количества раундов.

Количество раундов	4	6	8	9	10	11	12	13	14	15	16
Количество шагов	24	28	216	226	235	236	243	244	251	252	258

Атака на GSM

В 2000 году Эли Бихам и его коллега Ор Дункельман публикуют статью "Cryptanalysis of the A5/1 GSM Stream Cipher", где они показывают как можно взломать потоковый шифр A5/1, который используется для шифрования в системах GSM. Атака на этот шифр показывает, что зная $2^{20.8}$ бит открытых текстов, можно за $2^{39.91}$ тактов взломать A5/1. Алекс Бирюков и Ади Шамир уже показывали взлом данного шифра, однако данная атака требовала предварительных вычислений в размере $2^{48}$ тактов и памяти в размере двух 73Gb жёстких дисков или $2^{42}$ тактов и памяти в размере четырёх 73Gb жёстких дисков. Атака же, придуманная Эли Бихамом и Ором Дункельманом требует около 2.36 минут вычислений для взлома шифра, при этом, если мы имеем $2^{20.8}$ бит открытых текстов, то необходимо всего 32Gb памяти и $2^{39.91}$ тактов или 2Gb памяти и $2^{40.97}$ тактов.

Взлом ANSI X9.52 CBCM

В 1998 году Эли Бихам и Ларс Кнудсен публикуют статью "Cryptanalysis of the ANSI X9.52 CBCM Mode", где они показывают атаку на данный шифр. Это вид тройного DES шифра. В данном шифре промежуточные значения обратной связи они изменяют ключевым OFB потоком независимо от открытого и шифротекста. Но Эли Бихам и Ларс Кнудсен смогли даже это использовать для атаки на шифр. Для атаки необходим один шифротекст из $2^{65}$ блоков и сложность анализа составляет $2^{58}$.

Литература

• Eli Biham, Adi Shamir Differential Cryptanalysis of DES-like Cryptosystems // Springer-Verlag. — 1998.
• Ross Anderson and Eli Biham Tiger: A Fast New Hash Function.
• Ross Anderson Eli Biham Lars Knudsen Serpent: A Flexible Block Cipher With Maximum Assurance.
• Eli Biham and Orr Dunkelman Cryptanalysis of the A5/1 GSM Stream Cipher. — Computer Science department, Technion - Israel Institute of Technology, Haifa 32000, Israel.
• Eli Biham and Lars R. Knudsen Cryptanalysis of the ANSI X9.52 CBCM Mode. — Computer Science department, Technion - Israel Institute of Technology, Haifa 32000, Israel.

Ссылки

• The eSTREAM Portfolio  (англ.)
• Mycrosoft Academic Search, Eli Biham  (англ.)
• Eli Biham  (англ.)