Елі Біхам

Елі Біхам
אלי ביהם‏‎
Народився	1960 Ізраїль
Країна	Ізраїль
Діяльність	криптолог, математик, інформатик, інженер, викладач університету
Alma mater	Тель-Авівський університет Науково-дослідний інститут імені Вейцмана
Галузь	математика
Заклад	Техніон
Науковий керівник	Аді Шамір
Аспіранти, докторанти	Alex Biryukovd Elad Pinhas Barkand Orr Dunkelmand Tal Mord Rafael Chend
Нагороди	член Міжнародної асоціації криптологічних дослідженьd (2012)
Особ. сторінка	cs.technion.ac.il/~biham/
Елі Біхам у Вікісховищі

Елі Біхам (івр. אלי ביהם‎) — ізраїльський криптограф і криптоаналітик. Будучи учнем відомого ізраїльського вченого Аді Шаміра, разом з ним розробляв диференційний криптоаналіз. Ця розробка дозволила йому отримати ступінь доктора. Але пізніше було з'ясовано, що даний криптоаналіз був уже відомий і тримався в секреті Агентством безпеки США і корпорацією IBM. З жовтня 2008 року є професором Ізраїльського Технічного Інституту в області обчислювальних систем. Крім розробки різних методів криптоаналізу, Елі Біхам брав участь в створенні шифрів (блоковий шифр Serpent, Py — один з сімейства потокових шифрів) і хеш-функцій (наприклад 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 для виявлення нових потокових шифрів, що підходить для широкого поширення, утворений європейською мережею ECRYPT. Він був створений після провалу всіх 6 потокових шифрів проекту NESSIE. Даний проект був розділений на окремі етапи і його головною метою був пошук алгоритму відповідного для різних додатків. Елі Біхам разом з Дженіфер Себбері розробляє потоковий шифр Py, який підпорядковується саме цьому проекту. Він є одним з найшвидших шифрів в eSTREAM, близько 2.85 циклів на байт на Pentium III (більш ніж в 2,5 рази швидше RC4). Він має структуру, схожу на RC4, але тут доданий масив з 260 32-бітних слів, які індексуються шляхом перестановок байт, і в кожному раунді виходить 64 біта. Потім, в січні 2007 року Біхам і Себбері створили більш потужні версії даного потокового шифру: TPy, TPy6, TPypy.

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

Працюючи з Аді Шаміром, Елі Біхам розробляє диференційний криптоаналіз, за який він і отримав ступінь доктора. Зокрема, ними проведений криптоаналіз одного з раундів блочного шифру REDOC У 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

У 2000 році Елі Біхам і його колега Ор Дункельман публікують статтю «Cryptanalysis of the A5/1 GSM Stream Cipher», де вони показують як можна зламати потоковий шифр A5/1, який використовується для шифрування в системах GSM. Атака на цей шифр показує, що знаючи $2^{20.8}$ біт відкритих текстів, можна за $2^{48}$ тактів зламати A5/1. Алекс Бірюков і Шамір Аді вже показували злом даного шифру, проте дана атака вимагала попередніх обчислень в розмірі$2^{48}$ тактів і пам'яті в розмірі двох 73Gb жорстких дисків або $2^{42}$ тактів і пам'яті в розмірі чотирьох 73Gb жорстких дисків. Атака ж, придумана Елі Біхамом і Ором Дункельманом вимагає близько 2.36 хвилин обчислень для злому шифру, при цьому, якщо ми маємо $2^{20.8}$ біт відкритих текстів, то необхідно всього 32Gb пам'яті і $2^{39.91}$ тактів або 2Gb пам'яті і $2^{40.97}$ тактів.

У 2000 році Елі Біхам і його колега Ор Дункельман публікують статтю «англ. 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.

Посилання

• Differential Cryptanalysis of the Data Encryption Standard [Архівовано 22 грудня 2018 у Wayback Machine.]
• Mathematics Genealogy Project Eli Biham [Архівовано 9 серпня 2018 у Wayback Machine.]
• Eli Biham's homepage at Technion [Архівовано 21 квітня 2018 у Wayback Machine.]