Елі Біхам

Елі Біхам (івр. אלי ביהם‎) — ізраїльський криптограф і криптоаналітик. Будучи учнем відомого ізраїльського вченого Аді Шаміра, разом з ним розробляв диференційний криптоаналіз. Ця розробка дозволила йому отримати ступінь доктора. Але пізніше було з'ясовано, що даний криптоаналіз був уже відомий і тримався в секреті Агентством безпеки США і корпорацією IBM. З жовтня 2008 року є професором Ізраїльського Технічного Інституту в області обчислювальних систем. Крім розробки різних методів криптоаналізу, Елі Біхам брав участь в створенні шифрів (блоковий шифр Serpent, ^[en] — один з сімейства потокових шифрів) і хеш-функцій (наприклад Tiger).

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

Біографія

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

Елі отримав свою першу ступінь з математики та комп'ютерних наук з Тель-Авівському університеті, другий ступінь і докторат — в інституті Вайцмана. Докторат заахищений по темі криптоаналу під керівництвом Аді Шаміра. З 1991 року працює в Техніоні на відділенні комп'ютерних наук. З 2008 року — декан факультету комп'ютерних наук. З 2006 року він видає журнал з криптографічними дослідженнями й очолює міжнародну асоціацію криптографії.

Геш-функція Tiger

Докладніше: Tiger (хеш-функція)

Для захисту даних потрібні надійні хеш-функції (наприклад цифрові підписи) і при цьому вони повинні швидко оброблятися. Так були створені, як тоді здалося, потужні шифри з сімейств MD4 і . Але, наприклад для , в 1990 році були знайдені колізії, а потім вони були виявлені і для MD4, що ставило під сумнів все сімейство даних функцій. Тому потрібно розробити нову, більшу кріптостійкість хеш-функцію. До того ж всі попередні хеш-функції були розроблені для 32-бітних процесорів, а вже розпочалася поява нового покоління процесорів — 64-бітні. Тому в 1995 році Елі Біхам разом з Россом Андерсоном розробляє нову потужну та швидку хеш-функцію під назвою Tiger з розміром значення хеша 192 біта, яка працювала на 64-бітних машинах.

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

Докладніше: 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 року Біхам і Себбері створили більш потужні версії даного потокового шифру: , , .

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

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

Працюючи з Аді Шаміром, Елі Біхам розробляє диференційний криптоаналіз, за який він і отримав ступінь доктора. Зокрема, ними проведений криптоаналіз одного з раундів блочного шифру REDOC У 1990 році публікується робота Елі Біхам і Аді Шаміра англ. «Differential Cryptanalysis of DES-like Cryptosystems», в якій вони показують як за допомогою диференціального криптоаналізу за кілька хвилин можна зламати 8 раундовий DES. Так, наприклад, для 6-раундового DES використання диференціального криптоаналізу призвело до того, що на звичайному персональному комп'ютері він був зламаний менш ніж за 0,3 секунди, використовуючи 240 шифротексту. При 8-раундовому DES було використано 1500 шифротексту, при цьому час, витрачений на злом шифру склав близько 2 хвилин. З 15-ти і 16-ти раундовий DES виявилися складнішими, але тим не менше вони можуть бути зламані за ${\displaystyle 2^{52}}$ и ${\displaystyle 2^{58}}$ кроку відповідно. Нижче наведена таблиця, в якій показано кількість кроків, необхідних для злому [ [DES]], в залежності від кількості раундів.

Кількість раундів	4	6	8	9	10	11	12	13	14	15	16
Кількість кроків	2^4	2^8	2^16	2^26	2^35	2^36	2^43	2^44	2^51	2^52	2^58

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

У 2000 році Елі Біхам і його колега публікують статтю «англ. Cryptanalysis of the ANSI X9.52 CBCM Mode», де вони показують атаку на даний шифр. Це вид потрійного DES шифру. В даному шифрі проміжні значення зворотного зв'язку, вони змінюють ключовий потоком, незалежно від відкритого шифротексту. Але Елі Біхам і Ларс Кнудсен змогли навіть це використати для атаки на шифр. Для атаки необхідний один шифротекст з ${\displaystyle 2^{65}}$ блоків і складність аналізу становить ${\displaystyle 2^{58}}$.

Примітки

1. Математичний генеалогічний проєкт — 1997.
   d:Track:Q829984
2. . Архів оригіналу за 3 січня 2019. Процитовано 10 квітня 2018.
3. (PDF). Архів оригіналу (PDF) за 22 грудня 2018. Процитовано 13 квітня 2018.

Література

• 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.]