Довжина ключа і його повний перебір

Зміст 1. Введення 1.1. Що таке біт? 1.2. Що таке криптографічний ключ? 1.3. Що таке повний перебір? 1.4. Чи є повний перебір єдино можливим методом криптоаналізу? 1.5. 128-бітний ключ в два рази стійкішими до злому, ніж 64-бітний? 1.6. PGP має бути дуже стійкий, тому що використовує ключі 1024 біта. 2. Поточний стан справ 2.1. Яка максимальна довжина ключа для симетричних криптосистем, яка піддається програмного злому методом повного перебору? 2.2. Те ж, з використанням спеціальної апаратури? 2.3. А для несиметричних криптосистем? 2.4. Що щодо "кавника" Шаміра?

· 3. Те, що буде можливим у майбутньому 3.1. Що таке закон Мура? 3.2. Яка передбачувана вартість повного перебору з використанням спеціалізованого устаткування? 3.3. А з використанням квантових комп'ютерів?

· 4. Різні чутки 4.1. NSA/DST/інші можуть ламати ключі до 128 біт. 4.2. NSA/DST/інші мають квантовими комп'ютерами. 4.3. NSA/DST/інші досягли методів криптоаналізу, недоступних іншим. 4.4. Я працюю на NSA/DST/інших і тому намагаюся переконати громадськість, що 128-бітне шифрування надійно. 1. Введення 1.1. Що таке біт?

Біт є фундаментальною одиницею інформації. Він може приймати значення 0 або 1. Протягом останніх сорока років комп'ютери працюють з бінарними даними, тобто з наборами бітів (а не з цифрами від 0 до 9, як це прийнято у людей; можна сказати, що комп'ютери мають тільки два пальці). Бити дозволяють кодувати цілі числа, символи, тощо. Вся інформація, що проходить через комп'ютер, перетворюється на біти.

8 біт утворюють байт; це дає 256 комбінацій і дозволяє кодувати числа від 0 до 255 або символи (включаючи різницю між великими і малими літерами, символи з наголосами або інші).

1024 байти утворюють один кілобайт (КБ). 1024 використовується замість 1000 оскільки 1024 є ступенем числа 2, то є "круглим" числом, якщо працювати за основою 2. 1024 кілобайт утворюють мегабайт (МБ), або 1048576 байт. 1024 мегабайта утворюють гігабайт (ГБ), або 1073741824 байти. 1024 ГБ утворюють терабайт (ТБ). Подальше множення маловживаних, тому що дорогі з усіх точок зору. Типова ємність жорстких дисків широко поширених в Нині комп'ютерів складає десять гігабайт. Розвинена мережа може пропускати десять мегабайт за секунду між двома машинами. 1.2. Що таке криптографічний ключ?

Криптографічні операції, такі як шифрування і підписання даних електронним цифровим підписом, можуть бути здійснені тільки певними особами, що володіють деякими секретами. У минулі століття цим секретом був сам спосіб перетворення даних. Однак більш раціонально і ефективніше концентрувати цей секрет у вигляді набору бітів, а сам алгоритм робити загальнодоступним.

Дійсно, зберігати в таємниці алгоритм проблематично, і, крім того, необхідна чисельна оцінка його безпеки. Сам факт публікації алгоритму дозволяє "безкоштовно" отримати визнання його надійності криптографічних спільнотою.

Ключ, таким чином, є концентрацією секрету, цей набір бітів є "есенцією" конфіденційності. 1.3. Що таке повний перебір?

Зламати криптосистем, значить зуміти здійснити деякі операції, що вимагають (в теорії) знання секрету (ключа), не маючи інформації про останнього. Найбільш повним зломом є злом, в результаті якого стає відомий ключ, що дає зломщикові ті ж повноваження, що й законному власнику ключа.

Повний перебір є найбільш простим методом цієї точки зору: він полягає в тому, щоб пробувати всі ключі один за одним до тих пір, поки не знайдеться правильний. Цей метод є найбільш загальним, і може бути распараллелен (обчислення можуть бути розподілені на багато машин). Крім того, він найбільш реалістичний: якщо розглядати випадок симетричної системи шифрування (яка ставить у відповідність блоку, що складається з декількох байтів, другой блок тієї ж довжини, але перетворений до "нечитабельним" виду за допомогою ключа), досить перехопити пару відкритий текст/зашифрований текст, тобто блок з кілька байтів і відповідних їм зашифрованих. Наприклад, якщо передається картинка у форматі JPG, то початок повідомлення являє собою стандартний заголовок JPG, формат якого всім добре відомий.

З точки зору статистики, треба перебрати приблизно половину можливих ключів, перш ніж знайдеться правильний. Якщо довжина ключа становить 56 бітів, це означає, що в середньому необхідно провести 2 ^ 55 ітерацій, що складе 36028797018963968. 1.4. Чи є повний перебір єдино можливим методом криптоаналізу?

Ні. Але інші методи сильно залежать від конкретного алгоритму. Деякі, такі як лінійний або диференціальний криптоаналіз, вимагають величезного числа пар відкрита/зашифрований текст, уявляючи, таким чином, суто теоретичний інтерес.

Крім того, існують криптосистеми (зокрема, системи асиметричні, які називають ще "системами з відкритим ключем"), для яких все поєднання бітів не утворюють правильного ключа. Типовий приклад - RSA, де ключ представлений великим числом, отриманим з двох великих простих чисел. Сукупність наборів з 1024 біт, які є двійковій записом цих чисел, набагато менше 2 ^ 1024. Повний перебір абсурдний в цьому випадку. 1.5. 128-бітний ключ в два рази стійкішими до злому, ніж 64-бітний?

НІ! Це поширена помилка. Кожен додатковий біт подвоює кількість можливих ключів і витрати на повний перебір. Ключ довжиною 128 біт є в 18446744073709551616 разів більш складним для відбору, в порівнянні з ключем довжиною 64 біта (який вже не назвеш зовсім легким). 1.6. PGP має бути дуже стійкий, тому що використовує ключі 1024 біта.

Стоп! Давайте розберемося! "1024 біт" у PGP - це ключ RSA або DSS, то є ключ асиметричного алгоритму. Атака методом повного перебору не самий кращий варіант в цьому випадку.

Крім того, асиметричні алгоритми щодо повільні, і "всередині" PGP використовує симетричний алгоритм (історично IDEA, потім CAST) розмір ключа якого становить 128 біт. 2. Поточний стан справ 2.1. Яка максимальна довжина ключа для симетричних криптосистем, яка піддається програмного злому методом повного перебору?

Відомо, що два ключі по 56 біт були підібрані повним перебором на звичайних комп'ютерах типу PC. Спеціалізована машина (побудована EFF) допомогла для другого ключа, виконавши приблизно третина загального обсягу обчислень.

Ключі були для алгоритму DES. Якісний ПК або робоча станція можуть перебирати з максимальною швидкістю декількох мільйонів ключів в секунду. Якщо взяти середню швидкість один мільйон ключів в секунду на машину, то легко бачити, що для підбору ключа 10000 машин повинні в середньому витратити 42 дні.

Повний перебір ключа довжиною 64 біта для RC5 (для якого складність повного перебору трохи вище, ніж для DES) в даний час продовжується, і буде тривати, принаймні, ще кількох років. Нагадуємо, що підбір ключа розміром 64 бита, є в 256 разів більш трудомістким, ніж підбору ключа довжиною 56 біт. 2.2. Те ж, з використанням спеціальної апаратури?

Американська група EFF, інвестувала 250000 $ у створення спеціалізованої машини під назвою "Deep crack" ( "глибокий злом"), яка в змозі перебрати всі ключі алгоритму DES приблизно за три дні. У ній використані спеціалізовані процесори, які неможливо застосувати для цілей, відмінних від злому DES (зокрема, вони нічого "не знають" про RC5).

Всі інші машини того ж роду - з області чуток. DES використовується вже більше 20 років, і можна припустити, що, ймовірно, машині EFF передували інші прототипи, що розробляються секретними службами. У будь-якому випадку, скоро вже 15 років періодично згадуються принципи побудови такої машини. 2.3. А для несиметричних криптосистем?

В принципі, існують два математичні задачі, які використовуються в асиметричних шифри: факторизація і дискретного логарифмування. RSA використовує перше, DSS друге. Інші згадуються завдання (варіації двох попередніх, використання еліптичних кривих, завдання про укладання ранця, мінімізація мережі (задача комівояжера), зворотне розпізнавання (permuted perceptrons problem - див примітки) відносно рідко використовуються в даний час.

Рекорд факторизації датується 22-ым серпня 1999: число розміром 155 десяткових цифр (512 біт) було факторізовано за шість місяців обчислень на парку приблизно із 600 машин, деякі з яких можуть бути кваліфіковані як "бики" (зокрема Cray з 2 ГБ пам'яті). Застосовані алгоритми набагато складніші, ніж повний перебір, і вимагають великої кількості оперативної пам'яті з хорошою швидкістю доступу.

дискретного логарифмування менш досліджена, на його злом здійснено менше інвестицій, ніж на факторизації. Рекорд - близько 95 десяткових цифр. 2.4. Що щодо "кавника" Шаміра?

Представлений на Eurocrypt'99 в Празі (на початку травня 1999), цей апарат прискорює фізичними засобами дослідження гладких чисел (тобто отриманих твором тільки маленьких простих чисел), які отримують зазвичай методом решета. Ці числа є основою декількох алгоритмів факторизації і рішень задачі дискретного логарифмування.

Сам апарат ще не побудований, описані тільки його принципи. Існують технічні проблеми для реалізації прототипу (Arjen Lenstra висловив деякі заперечення, з якими Adi Shamir погодився).

На загальну думку, цей метод дозволив би факторізовать число приблизно в 600 біт, з коштами, які дозволили встановити рекорд в 465 біт (в лютому 1999), якщо всі проблеми з реалізацією будуть вирішені. Відзначено, що решето зайняло приблизно 60% часу для рекорду в 512 біт.

Все ж таки шоу було дуже захоплюючою. Phil Zimmerman, автор PGP, зауважив, що дуже задоволений тим, що дослідники цікавляться, як йдуть справи в цих проблеми, тому що це збільшує ступінь довіри до такого роду систем. 3. Те, що буде можливим у майбутньому 3.1. Що таке закон Мура?

Закон Мура (Moore) є оцінкою розвитку обчислювальної техніки в часі. У базовому варіанті він говорить, що для заданої вартості (у широкому сенсі, включаючи енергоспоживання, виробництво устаткування, знос, вартість зберігання, і т.д.) обчислювальна потужність збільшується в 8 разів кожні 3 роки. Говорячи більш точно, можна сказати, що через кожні три роки, технологічні досягнення дозволяють розмістити в 4 рази більше логічних елементів в мікросхемі заданої вартості, одночасно прискорюючи її швидкодію в 2 рази.

Цей закон чудово підтверджувався протягом останніх 15 років. Слід відзначити, що центральні мікропроцесори комп'ютерів загального призначення не повністю дотримуються цього закону, тому що вони не можуть так само швидко збільшити розмір шини даних (з міркувань забезпечення сумісності коду, а також тому, що обчислення, які ці процесори зазвичай виробляють, мають додаткові обмеження, що роблять непотрібним використання надто великих регістрів).

Це стосується, таким чином, систем, що описуються в термінах логічних елементів, спеціалізованих на конкретному алгоритмі. Таким чином, це по суті ASIC (Application Specific Integrated Circuit - спеціалізовані мікросхеми) і FPGA (Field Programmable Gate Arrays - програмовані логічні інтегральні схеми); тобто Перепрограмміруємая ланцюга, що виконують ті ж завдання, що й ASIC, але удвічі дорожчі при заданій потужності, однак є багатоцільовими). 3.2. Яка передбачувана вартість пального перебору з використанням спеціалізованого устаткування?

Якщо закон Мура буде продовжувати виконуватися (і немає вагомих підстав для зворотного, тому що він враховує якісні досягнення, а не тільки збільшення точності обробки кремнію), можна досягти машини EFF (чверть мільйона доларів, для 56 біт за 3 дні) і додавати 3 біта кожні 3 роки (3 біта = 2 ^ 3 = 8; що дає в 8 разів більше можливих варіантів ключів).

Зауважимо, що для збереження закон Мура, якісні досягнення повинні відбуватися досить швидко, тому що є межі у збільшенні щільності елементів на кристалі кремнію (уповільнення внаслідок тунельного ефекту). У ряді розроблюваних методів передбачається здійснити заміну кремнію на арсенід галію, що дозволить досягти більш високої щільності елементів, заміну алюмінію міддю, яка дозволяє працювати набагато швидше, побудова оптичної логіки (оптичний елемент перемикається приблизно в 100 разів швидше електронного, але його вартість вище більш ніж у 100 разів).

Таким чином, можна вважати, підібрати повним перебором 128-бітний ключ так само "легко", як зараз 56-бітний, стане можливим через 72 роки. Ця оцінка є "найкращою", у той час як багато дослідників цієї тематики вважають, що закон Мура буде виконуватися в кращому випадку ще декілька років (справді, всі якісні зміни, привнесені за останніх 15 років, були просто нереалізованими, відомими з 1975 року, і їх запас майже вичерпаний в даний час). 3.3. А з використанням квантових комп'ютерів?

Квантові комп'ютери, що реалізуються через суперпозицію станів однієї частинки, є більш потужної обчислювальної моделлю, ніж машина Тьюринга і дозволяють здійснити багато операцій (серед яких повний перебір ключів такого "безмежного" алгоритму, як DES) за субекспоненціальное час.

Квантові комп'ютери дуже спокусливі, але вони не існують. Був побудований двухбітовий квантовий регістр, але є досить потужні перешкоди для побудови машини, здатної зламати DES (головним чином, ініціалізація цього монстра, яка не може бути распараллелена, і займає, таким чином, 2 ^ n операцій для ключа n бітів).

Це не має великого значення для іншого типу квантової криптографії, що служить для "неперехвативаемой" передачі даних по оптоволокну (використовуючи принцип невизначеності). 4. Різні чутки 4.1. NSA/DST/інші можуть ламати ключі до 128 біт.

Є дуже сильні заперечення проти такого роду висловлювань. Серед класичних можна виділити одне, що припускає наявність процесора з енергоспоживанням в 10 разів менше, ніж у класичних (таким могли б мати у своєму розпорядженні секретні служби, які мають перевагу). Енергетичні витрати на повний перебір 128-бітного ключа, якщо їх перевести в теплову форму, змусили б зникнути під водою Нідерланди в результаті танення полярних льодів.

Що стосується 256-бітових ключів, то якщо припустити, що витрати на аналіз одного ключа рівні енергії переходу електрона з однієї орбіти атома на іншу, то кількості великодушно надається Сонцем енергії недостатньо для здійснення такого перебору за розумний час.

Деякі легко маніпулюють кількістю бітів, легко відносячи 20 біт на використання надпровідників або оптичних елементів, 20 інших на застосування супер-алгоритмів, і 30 останніх тому що "це вже трохи" (так, просто помножити на 1 мільярд, це дійсно "трохи").

Нагадаю, що число бітів експоненціально. Це означає, що витрати на перебір кожних n бітів пропорційні 2 ^ n. Щоб це було легше уявити, нагадаємо, що: 64 біта: 18446744073709551616 можливих ключів 128 біт: 340282366920938463463374607431768211456 можливих ключів 256 біт: 115792089237316195423570985008687907853269984665640564039457584007913129639936 можливих ключів 4.2. NSA/DST/інші мають квантовими комп'ютерами.

Дуже малоймовірно. Якщо це правда, то технологічні досягнення випереджають всіх як мінімум років на 10. Іншими словами, вони мали б тоді такий просунутою технологією, що сама ідея подальшої боротьби була б абсурдом.

Деякі згадують можливість отримання позаземної технології, або через Людей в Чорному, або безпосередньо через Phil Zimmerman, їх посла на цій планеті. Як вважають інші джерела, квантовим комп'ютером мала у своєму розпорядженні цивілізація атлантів (звичайно, Атлантида була затоплена саме в результаті перебору ключа "класичними" методами, див. вище).

Стикаючись з проявами абсурду і дилетантства в цій області, хочеться порадити триматися подалі від подібного роду спекуляцій, щоб не виглядати клоуном. Якщо хочеться оцінити що в змозі зробити NSA, треба дати йому 3 роки часу відповідно до закону Мура і хороший бюджет. Це дозволить зробити завдання з 64 бітами розв'язуваної. 80 біт залишаться недосяжними. 4.3. NSA/DST/інші досягли методів кріптоаналіза, недоступних іншим.

NSA (в особі Don Coppersmith) оголосив у 1987 році, що знали вже в 1977 про Диференціальний криптоаналіз, оприлюдненому Біхамом і Шамір (E. Biham, A. Shamir) саме в цьому 1987 році. Алгоритм DES, розроблений в 1977, спеціально приховується від такої атаки.

Тим не менше, уточнимо, що така атака вимагає величезної кількості пар відкрита/зашифрований текст, і, в будь-якому випадку, нереальна. Крім того, DES НЕ був захищений проти лінійного криптоаналізу, відкритого в 1993 Matsui, що обмежує наукове перевагу NSA 15 роками. Нарешті, цей останній спосіб криптоаналізу також нереальний, тому що вимагає 64 ТБ відомого відкритого тексту, що в кілька десятків мільйонів разів перевищує обсяг Біблії.

Подібні чутки ходили також про факторизації, дискретне логарифмуванню і кошти від прищів. Легко можна зустріти такі чутки в згадках про міжнародних змови злодіїв, які хочуть знати все про всі в цьому світі.

У будь-якому разі, з певного моменту, набагато дешевше встановити відеокамеру у вашому офісі, ніж змушувати "молотити" квантовий комп'ютер. Чи знаєте Ви, що відновлення зображення Вашого монітора можливо з дистанції 100 метрів? Те ж саме стосується і сигналів клавіатури, коли Ви друкуєте. Необхідно мати добре спроектовану сітку Фарадея, щоб захищатися від цього. Шифрування дозволяє встановити захищений канал між двома точками, але не захищає самі точки. 4.4. Я працюю на NSA/DST/інших і тому намагаюся переконати громадськість, що 128-бітне шифрування надійно.

Niark niark niark. Я обманщик, чи не так?

© Владислав Мяснянкина, переклад на російську мову. Примітки перекладача. Будь ласка, не надсилайте мені зауваження/коментарі за змістом документа. Я тільки переклав його. Пишіть безпосередньо автору (на французькою або англійською мовою) - адреса в заголовку. EFF - Electronic Frontier Foundation http://www.eff.org/ NSA - National Security Agency http://www.nsa.gov/ DST - Direction de la Sйcuritй du Territoire http://www.chez.com/icebreaker/dst/ Я не знайшов російського терміна для "Permuted Perceptrons Problem "і переклав як" завдання зворотного розпізнавання ". Якщо є більш правильний переклад - буду радий почути. Що це таке можна подивитися наприклад на http://cgi.dmi.ens.fr/cgi-bin/pointche/papers.html?Po95a (англійською). Якщо ви знайдете неточності у використанні термінів або запропонуйте більш "милозвучна" варіант їх перекладу, це буде сприйнято з вдячністю. Неконструктивна критика і флейм підуть на/dev/null.