Lucifer (криптографія)

Lucifer — дослідний проєкт фірми IBM 1970-х років по створенню криптостійкого блокового шифру. Результати дослідження привели до створення двох методів побудови стійких до злому симетричних шифрів — мережі Фейстеля і підстановлювально-переустановленої мережі. «Люцифер» заклав основи сучасної симетричної криптографії. У проєкті брали участь Хорст Фейстель (англ. Horst Feistel) і Дон Копперсміт (англ. Don Coppersmith), які згодом стали відомими криптографами. Розвиток «Люцифера» призвів до створення алгоритму DES.

Lucifer

Розробники	Хорст Фейстель
Уперше оприлюднений	1971 - 1973 рік
Раундів	16
Тип	Мережа Фейстеля

Історія

Перша версія алгоритму від 1971 року використовувала блоки й ключі довжиною по 48 біт і ґрунтувалася на SP-мережах. Подальша модифікація алгоритму була запатентована в листопаді того ж року (U.S. Patent 3,796,830; Nov 1971) і використовувала мережу Фейстеля. У патенті міститься опис як власне самого алгоритму, так і мережі Фейстеля. У цьому шифрі використовувалися 64-розрядні ключі і 32-бітові блоки. І, нарешті, остання версія запропонована в 1973 році і оперувала з 128-бітними блоками і ключами. Шифр 1977-му році став національним стандартом Сполучених Штатів і широко відомий в світі під абревіатурою DES. За подібною схемою побудовані всі найсильніші з сучасних несекретних криптографічних алгоритмів, і ця архітектура блокових шифрів отримала назву «мережа Файстеля» в честь свого творця^[1].

Хорст Фейстель зазначав про роль шифрування:

Традиційно людьми, які найбільше потребують секретності, були військові та дипломати. В їх роботі часто необхідні елементи несподіванки, а несподіванка такого роду завжди передбачає таємність. Що стосується звичайних людей, то яку б потребу в секретності вони не відчували, це залишалося їх особистою проблемою і рідко виносилося на публічне обговорення; коханці і злодії завжди самі, як могли забезпечували свої потреби в секретній комунікації. Це положення справ мало змінилося до самої середини XIX століття — як раз приблизно в той час для вдосконалення техніки таємного листа були залучені наукові методи й способи мислення. Попри це, аж до нашого століття способи, використані для секретної комунікації, продовжували залишатися процедурами, які виконували за допомогою олівця і паперу.

— Хорст Фейстель^[1]

Перша версія

Структура алгоритму Люцифер зразка червня 1971 ріку являє собою SP-мережа (або підстановлювально-перестановлену мережу) — «сендвіч» з шарів двох типів, які використовуються по черзі. Перший тип шару — P-блок розрядності 128 біт, за ним йде другий шар, що має 32 модулі, кожен з яких складається з двох 4-бітних S-блоків, чиї відповідні входи закорочені й на них подається одне і те ж значення з виходу попереднього шару. Але самі блоки підставляння різні (відрізняються таблицями замін). На вихід модуля подаються значення тільки з одного з S-блоків, якого конкретно — визначається одним з бітів в ключі, номер якого відповідав номеру S-блоку в структурі. У схемі використовується 16 модулів вибору S-блоків (всього 32 S-блоку), таким чином така схема використовує 16-бітний ключ^[1].

Розглянемо тепер, як буде змінюватися шифротекст в наведеному вище алгоритмі при зміні всього одного біта. Для простоти візьмемо таблиці замін S-блоків такими, що якщо на вхід S-блоку подаються всі нулі, то і на виході будуть всі нулі. У реальних системах такі таблиці замін не використовуються, оскільки вони сильно спрощують роботу криптоаналітика, але в даному прикладі вони наочно ілюструють сильний міжсимвольний взаємозв'язок при зміні одного біта повідомлення, яке шифрується. Видно, що завдяки першому P-блоку єдина одиниця зсувається в центр блоку, потім наступний нелінійний S-блок «розмножує» її і вже дві одиниці користуючись з наступного P-блоку змінюють своє положення і т. д. В кінці пристрою шифрування, завдяки сильному міжсимвольному зв'язку, вихідні біти стали складною функцією від вхідних і від застосованого ключа. В середньому, на виході половина біт буде дорівнює «0» і половина — «1»^[1].

Друга й третя версії

У наступній версії алгоритму замість SP-мережі використовувалася мережа Фейстеля. За своєю суттю мережа Фейстеля є альтернативою SP-мереж і використовується набагато ширше. З теоретичної точки зору раундова функція шифрування може бути зведена до SP-мережі, однак мережа Фейстеля є більш практичною, через те, що шифрування і розшифрування може вестися одним і тим же пристроєм, але зі зворотним порядком застосованих ключів. Друга й третя версія алгоритму (використовують мережу Фейстеля) оперували над 32-бітними блоками з 64-бітовим ключем і 128-бітними блоками з 128-бітними ключами. В останній (третій) версії раундова функція шифрування була влаштована дуже просто — спочатку зашифрований підблок пропускався через шар 4-бітних S-блоків (аналогічно верствам в SP-мережах, тільки S-блок є сталим і не залежить від ключа), потім до нього по модулю 2 додавався раундовий ключ, після чого результат пропускався через P-блок^[2].

Криптоаналіз варіантів алгоритму

Будь-які криптоаналітичні роботи, присвячені варіантам № 1 і № 2 алгоритму Lucifer, не отримали широку популярність. Двом останнім варіантам «пощастило» більше; відомі такі результати їх криптоаналізу.

У 1991 році Елі Біхам і Аді Шамір досліджували варіант № 3 . Для визначеності вони використовували перестановку Р з алгоритму DES, а як таблиці S0 і Si були взяті рядки 3 і 4 таблиці замін S {алгоритму DES}. З 8-раундовим варіантом № 3 з 32-бітовим блоком, розкривається при наявності всього 24 обраних відкритих текстів і відповідних їм шифртекст шляхом виконання порядку 221 тестових операцій шифрування.

У тій же роботі Біхам і Шамір описали можливу атаку на аналогічний алгоритм з 128-бітовим блоком, для успішного здійснення якої потрібно 60-70 обраних відкритих текстів і порядку 253 операцій шифрування.

Крім того, Біхам і Шамір стверджували, що варіант № 4 є ще слабшим.

Останнє твердження було доведено в роботі, яку опублікували Ішаі Бен-Аройо і Елі Біхам в 1993 році. У ній змальована атака на варіант № 4 алгоритму Lucifer, в якому виявилося підмножина ключів, яка мала ризиковий результат: близько 55 % всіх можливих значень ключа, слабких до диференціального криптоаналізу. При використанні ключа шифрування з даної підмножини алгоритм розкривається при наявності 236 обраних відкритих текстів^[2].