Национальный институт стандартов и технологий (National Institute of Standards and Technology, NIST) на днях обратился к общественности с просьбой помочь в решении проблемы, которую представители самого института называют «надвигающейся угрозой информационной безопасности». Речь идет о том, что квантовые компьютеры, прототипы которых уже работают, в будущем смогут легко взламывать любые коды шифрования, которые используются для защиты информации.
Представители НИСТ просят у специалистов по кибербезопасности, ученых и обычных пользователей устроить брейнсторминг по вопросу «постквантовой криптографии», алгоритмов, которые были бы недоступными и для квантовых компьютеров. Запрос организации официально зарегистрирован в Федеральном Реестре.
НИСТ занимается тем, что вместе с Американским национальным институтом стандартов (ANSI) участвует в разработке стандартов и спецификаций к программным решениям, используемым как в государственном секторе США, так и имеющим коммерческое применение. Основная миссия института -обеспечение инновационной и индустриальной конкурентоспособности США путём развития наук об измерениях, стандартизации и технологий с целью повышения экономической безопасности и улучшения качества жизни.
В целом, проблему, очерченную НИСТ, действительно можно назвать очень серьезной. Дело в том, что сейчас большинство традиционных криптосистем опираются на проблемы факторизации целых чисел или же задачи дискретного логарифмирования. Но такие задачи легко разрешить на мощных квантовых компьютерах, которые работают с алгоритмом Шора.
Стоит отметить, что термин «постквантовая криптография» вполне устоявшийся. Он обозначает часть криптографии, которая останется актуальной и при появлении квантовых компьютеров и квантовых же атак. В целом, постквантовая криптография основывается на пяти различных подходах, которые могут решить проблему квантовых атак. Вот эти подходы:
1. Криптография, которая основана на хэ-функциях. Здесь речь идет, например, о подписи Меркла с открытым ключом на основе хэш-дерева. Сам метод был предложен Ральфом Чарльзом Мерклом в 1979 году. Уже тогда он считал свою идею интересной альтернативой цифровым подписям RSA и DSA. Проблемой метода является то, что для любого открытого ключа на основе хэш-функции есть ограничение на количество подписей, которые можно получить из соответствующего набора закрытых ключей. Поэтому метод и не использовался. О нем вспомнили только тогда, когда речь зашла о системах, устойчивых к квантовым компьютерам;
2. Криптография, основанная на кодах исправления ошибок. Этот метод считается одним из наиболее перспективных. Классическим примером можно считать схемы шифрования McEliece и Niederreiter;
3. Криптография, основанная на решетках. Еще один перспективный метод. Здесь примером можно считать Ring-Learning with Errors, а также NTRU и GGH;
4. Криптография, основанная на многомерных квадратичных системах. Этот способ был предложен в 1996 году, он представляет собой подпись с открытым ключом Жака Патарина HFE;
5. Шифрование с секретным ключом. А здесь речь идет о шифре Rijndael, предложенном в 1998 году и впоследствии переименованном в AES (Advanced Encryption Standard).
Как уже говорилось выше, несмотря на то, что квантовые вычисления находятся в зачаточном состоянии, решить проблему надежности криптографических методов в этой сфере нужно уже сейчас. Перенимают квантовые идеи и классические компьютеры.
Дастин Муди (Dustin Moody), математик из НИСТ, подтверждает сказанное, говоря, что сейчас главная задача — разработка новых методов шифрования для хранимой и передаваемой информации. «Мы хотим заменить три существующих криптографических стандарта НИСТ, которые могут быть наиболее уязвимыми с точки зрения воздействия криптографических вычислений», — говорит Муди. Эти стандарты — FIPS 186-4, NIST SP 800-56A и NIST SP 800-56B.
У общественности есть почти год на подачу своих идей. Прием их заканчивается в ноябре следующего года. После этого НИСТ будет рассматривать поступившие заявки. Предложения, которые соответствуют стандартам постквантовой криптографии, заданным НИСТ, будут озвучены на открытом семинаре в 2018 году.
Поделиться с друзьями
den_golub
Ну как минимум протоколы квантовых криптоалгоритмов уже есть, правда пока не испробованные, но тем не менее. Как минимум два из них я попытался осветить в своей статье, уже как месяц назад.
KOLANICH
1 То, что вы имеете в виду более правильно называть квантовым распределением ключа. Это не шифрование, а именно более безопасный способ распределения ключа.
2 На практике оно малоприменимо. Не будут же от каждого сайта до каждого потребителя оптоволокно тащить.
И НИСТу я бы не стал доверять: их уже однажды уличили.
den_golub
Но все же квантовое распределение ключа все же в идеале безопасней того, что сейчас используется. Да и передаваться может не только ключ по квантовому каналу, но и любая другая информации, и защитой тут уже будет не математика, как в случае с классической криптографией, а физика. А с физикой бороться сложнее, чем с математическими вычислениями.
Ведь по сути вся криптография держится на том, что подбор ключей в лоб занимает, как говориться, «неприемлемое» время, т.е. информация устареет раньше, чем будет подобран ключ. А как раз основная опасность для классической криптографии, это то, что все шифрование как с симметричное, так и асимметричное будет на квантовых вычислителях будет просто просчитано в лоб, ибо скорость вычисления у них будет не в разы, а в 10^6 раз быстрее, ну или около того.
a5b
Многие проблемы, на базе которых строят асимметричные криптоалгоритмы, ускоряются экспоненциально. Но для симметричных и для хеш-сумм достаточно просто удвоить длину ключа, т.к. Алгоритм Гровера требует O(sqrt(N)) операций для полного перебора N значений: вместо перебора 2^128 ключей потребуется (в теории) всего 2^64 квантовых операций (на практике есть проблемы с столь длительной обработкой квантового состояния).
http://csrc.nist.gov/groups/ST/post-quantum-crypto/documents/pqcrypto-2016-presentation.pdf#page=3
Недавно запретили AES-128 и требуют удлинять ключи в асимметричных: http://csrc.nist.gov/groups/SMA/ispab/documents/minutes/2015-10/oct21_stanger_final_approved_nsa.pdf
http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf
den_golub
Ну во-первых это использование алгоритма на одном квантовом вычислителе позволяет понизить в заявленное количество раз, а как насчет распараллелить просчет, на нескольких устройствах? Во-вторых, рассматривается случай черного ящика. Во-вторых, а как же Алгоритм Шора при использование его и возможностей квантовых компьютеров, алгоритм способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера поставила бы крест на большей части современной криптографической защиты. (Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом).
a5b
Для большинства ныне используемых асимметричных алгоритмов (с публичным ключом) успешно работает Шор, именно их надо заменять (все 4 варианта Public key crypto в той презентации были зачеркнуты).
Алгоритм Шора не работает для распространенных симметричных алгоритмов, только Гровер.
Распараллеливать можно классические переборщики, и до определенных пределов это полезно:
Для полного перебора ключа в 56 бит в шкафу, набитом классическими ПЛИС (публично такой шкаф за $250 тыс представлен впервые в 1998 г), требуется перебор 2^56 вариантов ключа и выполнение 2^56 шифрований. В 2006 году сделали COPACOBANA (коробка с ПЛИС, дешевле 10 тыс.долларов) — https://www.iacr.org/archive/ches2006/09/09.pdf#page=8, частота FPGA — 100 МГц, каждый чип в такт завершал проверку 4 ключей (за счет конвейерной реализации). В коробке 120 чипов — суммарно 480 ключей в 10 нс = 48 млрд ключей (2^35) в сек, порядка 10 дней на перебор 2^55 ключей.
Для ключа в 64 бита — одна такая коробка потратила бы (при той же эффективности реализации) порядка 6 лет. Или ставить 256 коробок (2.3 млн евро за устройства, 40 стоек) для тех же 10 дней. В обоих вариантах потребуется примерно сравнимое количество энергии.
Для ключей в 128 бит прямой перебор можно хотя бы оценивать: https://micahflee.com/2013/01/no-really-the-nsa-cant-break-your-crypto/ — допустим, некое государственное агентство названное "без_имени" имеет бюджет в $100 трлн, покупает компьютеры (чипы) по 50$, каждый из которых выполняет проверку 100 тыс ключей в секунду (2 трлн компьютеров). На перебор потребуется всего лишь порядка 2^70 секунд ~= десятки триллионов лет. Это будет уже эпоха дегенерации звезд…
Ключи в 256 бит находятся за физическими пределами — https://geektimes.ru/post/264040/#comment_8838932 http://everything2.com/title/Thermodynamics+limits+on+cryptanalysis — по принципу Ландауэра (при необратимых вычислениях) чтобы проинкрементировать 256-битный счетчик от 0 до 2^256-1 потребуется затрата энергии эквивалентной энергии нескольких миллионов сверхновых звезд (по ~одной на каждый 219-битный интервал): "Even sucking all the energy from a supernova would be just enough to pass through all states of a 219-bit counter"
quverty
А что с НИСТ были за проблемы? Я что-то ни найти, ни припомнить никак не могу. Мне они казались как раз из тех немногих кто в этой области ещё как-то прилично себя вели.
a5b
Наиболее известный случай — Dual_EC_DRBG
https://en.wikipedia.org/wiki/Dual_EC_DRBG "Despite public criticism, it was for some time one of the four (now three) CSPRNGs standardized in NIST SP 800-90A as originally published circa June 2006."
Да, с 2014 они снова хорошие: "In April 21, 2014, NIST withdrew Dual_EC_DRBG from its draft guidance on random number generators recommending "current users of Dual_EC_DRBG transition to one of the three remaining approved algorithms as quickly as possible.""
https://en.wikipedia.org/wiki/National_Institute_of_Standards_and_Technology#Controversy
Еще есть теории заговора по выбору ECC-кривых NIST (Эллиптическая_криптография#Эллиптические кривые, рекомендованные NIST)
И также заговор по константам в популярных параметрах для классического DH / DSA (можно подготовить параметры полей, которые будут выглядеть случайными и качественными и при этом иметь у себя скрытые характеристики или заранее подсчитанные наборы для значительного ускорения взлома):
http://arstechnica.com/security/2016/10/how-the-nsa-could-put-undetectable-trapdoors-in-millions-of-crypto-keys/ "NSA could put undetectable “trapdoors” in millions of crypto keys" — "We show that we are never going to be able to detect primes that have been properly trapdoored. But we know exactly how the trapdoor works, and [we] can quantify the massive advantage it gives to the attacker."
https://eprint.iacr.org/2016/961.pdf "A kilobit hidden SNFS discrete logarithm computation"
quverty
Спасибо. У меня эти истории ассоциировались скорее с АНБ. В данном случае подача тоже скорее от АНБ https://geektimes.ru/post/260684/
LoadRunner
proton17
История развивается по спирали, в 40ые годы 20го века первые ЭВМ появились именно для расшифровки кодов, что в свою очередь вызвало в последствии бум криптографии. Сейчас, похоже, намечается примерно тоже самое.
Smitak
«брейнсторминг» — это не «мозговой штурм» по-русски?
molnij
Так как тема относительно знакомая, если не возражаете, дополню парой моментов
1. Про hash-based системы, к сожалению не помню деталей. Так что пропущу )
2. Системы на базе кодов — развиваются последние тридцать-сорок, кажется лет. С переменным успехом. Криптосистема МакЭллиса — одна из старейших, остается одной из самых стабильных. Все попытки собрать на этой базе что-то более вменяемое рано или поздно взламываются. Минус — ооооооочень большой ключ на вменяемых размерностях. Зато быстрая, особенно асимптотически.
3. Криптосистемы на решетках. Имеют под собой две задачи на одной специфичной структуре. Одна из задач почти не используется, а вторая полностью совпадает с задачей для code-based криптосистем, что лично у меня вызывает недоумение. Самая известная криптосистема в этом классе насколько знаю NTRU с двумя большими минусами — закрыта патентами и имеет рекомендованные параметры (что традиционно вызывает недоверие). Соответственно интерес к ней мягко говоря не очень большой.
4. Многомерные квадратичные системы(MQ-problem). Хорошая мат.задача в основе, но реализации стабильно ломаются. Идея постоянно развивается, но хорошей реализации как понимаю, на данный момент нет. Кстати, почти везде фамилию Patarin перевирают :) Он скорее Жак Патара. Насколько знаю, в этом направлении копает он со своими последователями и еще одна группа в Японии.
5. Как альтернативу, рассматривать симметричные криптосистемы можно, но ставить в один ряд с асимметричными несколько странно.
В начале 2000-х Еврокомиссия проводила конкурс NESSIE на крипто-системы, где среди участников было несколько схем на базе MQ-проблемы, одна из которых даже вышла в финал(SFLASH), однако через несколько лет была отозвана из-за найденной уязвимости.
Существует конференция PQCrypto, проходящая довольно регулярно, посвященная как раз вопросам постквантовой криптографии.
Есть еще несколько некоммутативных задач, на базе которых можно строить криптосистемы (вроде что-то из теории кос предлагалось), но как-то до готовой системы толи не доходит, толи не вызывает должного интереса, т.к. даже в рамках той же конференции PQCrypto секции бьются по задачам упомянутым выше — hash,code,lattice, MQ
И в целом очень огорчает тот факт, что на русском языке материалов по теме постквантовой криптографии чуть больше нуля :(
quverty
Где-то месяц назад был ещё один занимательный эпизод на эту тему: Петер Шор (тот самый) с коллегой заслали в arXiv статью о квантовой атаке на одну из систем криптографии на решётках. Правда потом почти сразу её изъяли, но так как там были праздники и выходные, она ещё некоторое время пролежала, так что дискуссий было достаточно, напимер вот тут более подробно .
molnij
Я правильно понял, что изъяли из-за найденной ошибки?
quverty
Пишут что ошибка. Вопрос можно ли её исправить или это фатально.