· 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 - див. примітки) відносно рідко використовуються в даний час.
Рекорд факторизації датується двадцять другого серпня 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. Я обманщик, чи не так?
© Автор: Thomas Pornin (thomas.pornin @ ens.fr); оригінал: http://www.dmi.ens.fr/ ~ pornin / faq-cle.html
© Владислав Мяснянкін, переклад на російську мову.
Примітки перекладача. Будь ласка, не надсилайте мені зауваження / коментарі за змістом документа. Я тільки переклав його. Пишіть безпосередньо автору (французькою або англійською мовою) - адреса в заголовку. 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.