Interested Article - Бихам, Эли

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

Биография

Эли родился в Кфар Виткине. Его отец — выходец из Чехословакии, а мать родилась в Израиле, её родители были выходцами из России. Его деды — основатели Кфар Виткина. Дед по матери — Цви Берехьяху (Богуславский) умер в 1934. Его брат — коммунистический деятель Михаил Соломонович Богуславский .

Эли получил свою первую степень по математике и компьютерным наукам из Тель-Авивского университета, вторую степень и докторат из института Вайцмана. Докторат сделан по криптоанализу под руководством Ади Шамира. С 1991 работает в Технионе на отделении компьютерных наук. С 2008 декан факультета компьютерных наук там. С 2006 издает журнал по криптографическому исследованию и возглавляет международную ассоциацию криптографии.

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

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

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

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

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

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

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

Работая с Ади Шамиром , Эли Бихам разрабатывает дифференциальный криптоанализ , за который он и получил степень доктора . В 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
Количество шагов	2 ⁴	2 ⁸	2 ¹⁶	2 ²⁶	2 ³⁵	2 ³⁶	2 ⁴³	2 ⁴⁴	2 ⁵¹	2 ⁵²	2 ⁵⁸

Атака на 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}$ .

Примечания

. Дата обращения: 19 августа 2013. 3 января 2019 года.

Литература

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.