Якби сучасні протоколи криптографії вийшли з ладу, було б неможливо захистити онлайн-з’єднання — надсилати конфіденційні повідомлення, здійснювати безпечні фінансові транзакції чи перевіряти автентичність даних. Кожен міг отримати доступ до будь-чого; будь-хто міг прикинутися будь-ким. Цифрова економіка впаде.
Коли (або if) стане доступним повністю функціональний квантовий комп’ютер, ось що саме може статися. У результаті в 2017 році Національний інститут стандартів і технологій уряду США (NIST) запустив міжнародний конкурс на пошук найкращих способів досягнення «постквантової» криптографії.
Минулого місяця агентство обрало свою першу групу переможців: чотири протоколи, які після певного перегляду будуть розгорнуті як квантовий щит. Він також оголосив чотирьох додаткових кандидатів, які все ще розглядаються.
Тоді 30 липня пара дослідників показала, що вони були зламав одного з тих кандидатів за годину на ноутбуці. (З тих пір інші зробили атаку ще швидшою, зламавши протокол за лічені хвилини.) «Настільки драматична й потужна атака… стала справжнім шоком», — сказав Стівен Гелбрейт, математик і інформатик з Університету Окленда в Новій Зеландії. Не тільки математика, що лежить в основі атаки, була несподіваною, але й зменшила (надзвичайно необхідну) різноманітність постквантової криптографії — усунувши протокол шифрування, який працював зовсім не так, як більшість схем у конкурсі NIST.
"Це трохи неприємно", сказав Крістофер Пайкерт, криптограф Мічиганського університету.
Результати приголомшили та підбадьорили спільноту постквантової криптографії. Приголомшений, тому що ця атака (і ще одна з попереднього раунду змагань) раптом перетворила те, що було схоже на цифрові сталеві двері, на мокру газету. «Це сталося зненацька», — сказав Дастін Муді, один із математиків, який очолював зусилля зі стандартизації NIST. Але якщо криптографічну схему буде зламано, найкраще, якщо це станеться задовго до її використання в дикій природі. «Багато емоцій проходить через вас», – сказав Девід Джао, математик з Університету Ватерлоо в Канаді, який разом із дослідником IBM Лука Де Фео, запропонував протокол у 2011 році. Серед них, безперечно, подив і розчарування. «Але також, — додав Джао, — принаймні він зламався».
Secret Walks Among Curves
Джао та Де Фео побачили можливість для криптографічної системи, яка була б схожою на добре відомі протоколи та відповідним чином відрізнялася від них. Їхня схема, названа протоколом Діффі-Хеллмана суперсингулярної ізогенії (SIDH), стосувалася еліптичних кривих — тих самих математичних об’єктів, які використовуються в одному з найпоширеніших типів криптографії, які застосовуються сьогодні. Але воно використало їх зовсім по-іншому. Це також була найкомпактніша схема, яку розглядав NIST (з тим компромісом, що вона була повільнішою, ніж багато інших кандидатів).
І «з математичної точки зору це справді елегантно», — сказав Джао. «У той час це здавалося гарною ідеєю».
Скажімо, дві сторони, Аліса та Боб, хочуть таємно обмінятися повідомленням, навіть під пильним поглядом потенційного зловмисника. Вони починаються з набору точок, з’єднаних ребрами, які називаються графом. Кожна точка представляє окрему еліптичну криву. Якщо ви можете перетворити одну криву в іншу певним чином (через карту, що називається ізогенією), намалюйте ребро між парою точок. Отриманий графік величезний, і в ньому легко загубитися: якщо ви зробите відносно коротку прогулянку по його краях, ви потрапите десь, що виглядає абсолютно випадковим.
Графіки Аліси та Боба мають однакові точки, але ребра різні — вони визначені різними ізогеніями. Аліса та Боб починають з однієї точки, і кожен з них стрибає вздовж випадкових ребер на власному графіку, відстежуючи свій шлях від однієї точки до іншої. Кожен потім публікує своє кінцеве місце, але зберігає свій шлях у секреті.
Тепер вони міняються місцями: Аліса йде до кінцевої точки Боба, а Боб до Аліси. Кожен повторює свою таємну ходу. Вони роблять це таким чином, що обидва опинилися в одній точці.
Це місце було знайдено таємно, тому Аліса та Боб можуть використовувати його як секретний ключ — інформацію, яка дозволяє їм надійно шифрувати та розшифровувати повідомлення один одного. Навіть якщо зловмисник бачить проміжні точки, які Аліса та Боб надсилають одне одному, він не знає таємної прогулянки Аліси чи Боба, тому не може визначити цю кінцеву кінцеву точку.
Але щоб SIDH працював, Алісі та Бобу також потрібно обмінятися додатковою інформацією про свої прогулянки. Саме ця додаткова інформація призвела до краху SIDH.
Новий поворот у старій математиці
Томас Декрю не збирався зламати SIDH. Він намагався побудувати його — узагальнити метод для вдосконалення іншого типу криптографії. Це не спрацювало, але це породило ідею: його підхід може бути корисним для атаки на SIDH. І ось він підійшов Воутер Кастрік, його колега з Левенського католицького університету в Бельгії та один із його колишніх докторських радників, і вони занурилися у відповідну літературу.
Вони випадково натрапили на статтю, опубліковану математиком Ернст Кані У 1997 році це була теорема, яка «була майже відразу застосовна до SIDH», сказав Кастрик. «Я думаю, як тільки ми зрозуміли, що … напад стався досить швидко, за один-два дні».
Зрештою, щоб відновити секретну ходу Аліси (і, отже, спільний ключ), Кастрік і Декрю дослідили добуток двох еліптичних кривих — початкової кривої Аліси та кривої, яку вона публічно надіслала Бобу. Ця комбінація створює поверхню, яка називається абелевою. Потім вони використали ці абелеві поверхні, теорему Кані (яка пов’язує абелеві поверхні з еліптичними кривими) і додаткову інформацію, яку Аліса надала Бобу, щоб розкрити кожен крок, який робила Аліса.
«Це майже як сигнал самонаведення, який дозволяє зафіксувати [певні абелеві поверхні]», — сказав Джао. «І цей сигнал говорить вам, що це шлях, яким ви повинні піти, щоб зробити наступний крок, щоб знайти правильну [секретну прогулянку]». Що привело їх прямо до спільного ключа Аліси та Боба.
«Це дуже несподіваний підхід, коли ми звертаємося до більш складних об’єктів, щоб отримати результати щодо простішого об’єкта», – сказав Джао.
«Я був дуже схвильований, побачивши, як використовується ця техніка», — сказав Крістін Лаутер, математик і криптограф Meta AI Research, який не тільки допоміг розробити криптографію на основі ізогенії, але також працював над абелевими поверхнями. «Мені соромно за те, що я не думав про це як про спосіб зламати [це]».
Атака Castryck і Decru зламала версію протоколу SIDH із найнижчим рівнем безпеки за 62 хвилини та найвищий рівень безпеки лише за добу. Потім, незабаром після цього, інший експерт налаштував атаку так, що знадобилося лише 10 хвилин, щоб зламати версію з низьким рівнем безпеки, і кілька годин, щоб зламати версію з високим рівнем безпеки. Більш загальні напади опубліковано за останні кілька тижнів зробити малоймовірним, що SIDH можна врятувати.
«Це було особливе відчуття, — сказав Кастрик, хоча й гірко-солодкий. «Ми вбили одну з наших улюблених систем».
Момент водозбору
Неможливо гарантувати безумовну безпеку системи. Натомість криптографи покладаються на те, що минув достатньо часу та достатньо людей, які намагаються розібратися в проблемі, щоб почуватися впевнено. «Це не означає, що завтра ви не прокинетеся й не побачите, що хтось знайшов новий алгоритм для цього», — сказав Джеффрі Гоффштайн, математик з Університету Брауна.
Ось чому такі важливі змагання, як NIST. У попередньому раунді конкурсу NIST Уорд Бойленс, криптограф з IBM, розробив атаку, яка зламав схему під назвою Rainbow у вихідний день. Як Кастрік і Декрю, він зміг інсценувати свою атаку лише після того, як поглянув на основну математичну проблему під іншим кутом. І, як і атака на SIDH, ця атака зламала систему, яка покладалася на іншу математику, ніж більшість запропонованих постквантових протоколів.
«Нещодавні напади стали переломним моментом», — сказав він Томас Прест, криптограф стартапу PQShield. Вони підкреслюють, наскільки складною є постквантова криптографія та скільки аналізу може знадобитися для вивчення безпеки різних систем. «Математичний об’єкт може не мати очевидної структури в одній точці зору і мати структуру, яку можна використовувати в іншій», — сказав він. «Складна частина полягає в тому, щоб визначити правильну нову перспективу».
