Постквантова криптографія – новий алгоритм «зник за 60 хвилин»

Ми писали про PQC, скорочення від постквантова криптографія, кілька разів раніше.

Якщо ви пропустили ажіотаж у ЗМІ про так звані квантові обчислення за останні кілька років…

…це (якщо ви вибачте, що деякі експерти, ймовірно, вважатимуть необдуманим спрощенням) спосіб створення обчислювальних пристроїв, які можуть відстежувати кілька можливих результатів розрахунку одночасно.

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

Два цікаві криптоаналітичні прискорення можливі за допомогою квантового обчислювального пристрою, припускаючи, що достатньо потужний і надійний пристрій може бути створений:

• Алгоритм квантового пошуку Гровера. Зазвичай, якщо ви хочете шукати довільно впорядкований набір відповідей, щоб побачити, чи є ваш у списку, ви очікуєте, що в гіршому випадку переглянете весь список, перш ніж отримати остаточну відповідь. Наприклад, якщо ви хочете знайти 128-бітний ключ дешифрування AES, щоб розшифрувати документ, вам потрібно буде виконати пошук у списку всіх можливих ключів, починаючи з 000..001, ..2, ..3, і так далі, аж до FFF..FFF (16 байт FF), щоб бути впевненим у виконанні проблеми. Іншими словами, ви повинні мати бюджет, щоб спробувати всі 2¹²⁸ можливі ключі, перш ніж знайти потрібний ключ або визначити, що його немає. Алгоритм Гровера, однак, враховуючи великий і досить потужний квантовий комп’ютер, стверджує, що він здатний виконати той самий подвиг із квадратний корінь звичайних зусиль, таким чином зламавши код, теоретично, лише за 2⁶⁴ намагається замість цього.
• Алгоритм квантової факторизації Шора. Кілька сучасних алгоритмів шифрування покладаються на той факт, що множення двох великих простих чисел можна зробити швидко, тоді як поділити їхній добуток на два числа, з яких ви почали, настільки ж неможливо. Щоб відчути це, спробуйте помножити 59×87 за допомогою ручки та паперу. Щоб отримати його, може знадобитися хвилина або близько того (відповідь 5133), але це не так складно. Тепер спробуйте іншим шляхом. Розділіть, скажімо, 4171 на два множники. Набагато складніше! (Це 43×97.) А тепер уявіть, що ви робите це з числом із 600 цифр. Грубо кажучи, ви застрягли, намагаючись поділити 600-значне число на кожне можливе 300-значне просте число, поки не виграєте джекпот або не виявите, що відповіді немає. Алгоритм Шора, однак, обіцяє вирішити цю проблему за допомогою логарифм звичайного зусилля. Таким чином, розкладання числа з 2048 двійкових цифр має займати лише вдвічі більше часу, ніж розкладання 1024-бітного числа, а не вдвічі більше, ніж розкладання 2047-бітного числа, що означає величезне прискорення.

Протидія загрозі

Загрозу від алгоритму Гровера можна протистояти, просто збільшивши розмір чисел, які ви використовуєте, звівши їх у квадрат, що означає подвоєння кількості бітів у вашому криптографічному хеші або ключі симетричного шифрування. (Іншими словами, якщо ви вважаєте, що SHA-256 зараз підходить, використання замість нього SHA-512 забезпечить стійку до PQC альтернативу.)

Але протистояти алгоритму Шора не так просто.

Розмір відкритого ключа в 2048 біт потребує експоненціального збільшення, а не просто зведенням у квадрат, тож замість ключа 2×2048=4096 біт вам знадобиться новий ключ із неможливим розміром 2²⁰⁴⁸ шматочки…

…або вам доведеться прийняти абсолютно новий тип постквантової системи шифрування, до якої не застосовувався алгоритм Шора.

Що ж, орган зі стандартизації США NIST керує a PQC «конкурс» з кінця 2017 року.

Процес був відкритий для всіх, усі учасники віталися, усі алгоритми відкрито публікувалися, а громадський контроль не просто можливий, але активно заохочується:

Конкурс пропозицій. [Закрито 2017-11-30]. […] Передбачається, що нові стандарти криптографії з відкритим ключем визначать один або більше додаткових несекретних, оприлюднених публічно цифрових підписів, шифрування з відкритим ключем і алгоритмів встановлення ключів, які доступні в усьому світі та здатні захищати конфіденційну державну інформацію в осяжному майбутньому, в тому числі після появи квантових комп’ютерів.

Після трьох раундів подання та обговорень, NIST оголосив2022-07-05, що вона вибрала чотири алгоритми, які вона вважала «стандартами» з негайним набуттям чинності, усі з чудовими назвами: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON та SPHINCS+.

Перший (CRYSTALS-KYBER) використовується як те, що називається a Ключовий механізм узгодження (KEM), де два кінці загальнодоступного каналу зв’язку безпечно створюють одноразовий приватний ключ шифрування для конфіденційного обміну даними сеансу. (Простіше кажучи: шпигуни просто отримують нашатковану капусту, тому вони не можуть підслухати розмову.)

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

Потрібно більше алгоритмів

Одночасно з оголошенням про нові стандарти NIST також оголосив a четвертий тур своєї конкуренції, висунувши ще чотири алгоритми як можливі альтернативні KEM. (Пам’ятайте, що на момент написання статті у нас уже є три схвалені алгоритми цифрового підпису на вибір, але лише один офіційний KEM.)

Це були: BIKE, Classic McEliece, HQC та SIKE.

Цікаво, що Алгоритм МакЕліса був винайдений ще в 1970-х роках американським криптографом Робертом Мак Елісом, який помер у 2019 році, задовго до того, як конкурс NIST уже розпочався.

Однак він так і не прижився, оскільки вимагав величезної кількості ключового матеріалу порівняно з популярною альтернативою того часу, алгоритмом Діффі-Хеллмана-Меркла (DHM, або іноді просто DH).

На жаль, один із трьох алгоритмів четвертого раунду, а саме SIKE, здається, було зламано.

У пугаючій статті під назвою ЕФЕКТИВНА АТАКА ВІДНОВЛЕННЯ КЛЮЧІВ НА SIDH (ПОПЕРЕДНЯ ВЕРСІЯ)бельгійські криптографи Воутер Кастрік і Томас Декру, здається, завдали смертельного удару алгоритму SIKE

Якщо вам цікаво, SIKE - це скорочення від Суперсингулярна інкапсуляція ключа ізогенії, а SIDH означає Суперсингулярна ізогенія Діффі-Хеллмана, специфічне використання Алгоритм SIKE за допомогою якого два кінці каналу зв’язку виконують «криптотанець», схожий на DHM, для обміну набором загальнодоступних даних, що дозволяє кожному кінці отримати приватне значення для використання як одноразового секретного ключа шифрування.

Ми не будемо намагатися пояснити напад тут; ми просто повторимо те, що стверджує документ, а саме, що:

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

Але отримані результати (інформація, яка називається ізогенія φ вище) має бути частиною процесу, яка ніколи не розкривалася – так званим закритим ключем.

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

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

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

Це суперечить алгоритму SIKE, якщо він налаштований на рівень 1, базовий рівень безпеки шифрування NIST.

Що ж робити?

Нічого!

(Це хороша новина.)

Як припускають автори статті, зазначивши, що їх результат все ще є попереднім, «З поточним станом справ SIDH, здається, повністю зламаний для будь-якої публічно створеної базової кривої».

(Це погана новина.)

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

Що б нарешті не сталося з SIKE, це чудове нагадування про те, чому спроби винайти власні алгоритми шифрування пов’язані з небезпекою.

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

Якби алгоритм PQC, такий як SIKE, витримав перевірку експертами з усього світу протягом більше п’яти років, незважаючи на те, що він був розкритий спеціально для того, щоб його можна було піддати громадському розгляду…

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

---