Біхам, Елі

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


1. Хеш-функція Tiger

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


2. Блоковий шифр Serpent

Для конкурсу AES Елі Біхам разом з Россом Андерсоном і Ларсом Кнудсеном створює симетричний блочний алгоритм шифрування Serpent ("змія"), що потрапив у фінал 2-го етапу конкурсу. S-блоки були побудовані після ретельного вивчення S-блоків в алгоритмі DES, що дозволило 16 раундовому новому алгоритму шифрування бути в 2 рази швидше DES і при цьому не менш надійним. Потім була створена версія з 32-ма раундами, що ще більше збільшило його криптостійкість. 32-бітова версія не має вразливостей.


3. Потоковий шифр Py

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


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

Працюючи з Аді Шамір, Елі Біхам розробляє диференціальний криптоаналіз, за який він і отримав ступінь доктора. У 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
Кількість кроків 4 лютого 2 серпня 16 лютого 26 лютого 2 35 2 36 2 43 2 44 2 51 2 52 2 58

5. Атака на 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} тактів.


6. Злом 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.