НИСТ просит помощи в создании надежных постквантовых методов шифрования данных



    Национальный институт стандартов и технологий (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 году.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 16

      –1
      Ну как минимум протоколы квантовых криптоалгоритмов уже есть, правда пока не испробованные, но тем не менее. Как минимум два из них я попытался осветить в своей статье, уже как месяц назад.
        +1
        1 То, что вы имеете в виду более правильно называть квантовым распределением ключа. Это не шифрование, а именно более безопасный способ распределения ключа.
        2 На практике оно малоприменимо. Не будут же от каждого сайта до каждого потребителя оптоволокно тащить.

        И НИСТу я бы не стал доверять: их уже однажды уличили.
          0
          И НИСТу я бы не стал доверять: их уже однажды уличили.
          с этим не поспоришь.

          Но все же квантовое распределение ключа все же в идеале безопасней того, что сейчас используется. Да и передаваться может не только ключ по квантовому каналу, но и любая другая информации, и защитой тут уже будет не математика, как в случае с классической криптографией, а физика. А с физикой бороться сложнее, чем с математическими вычислениями.
          Ведь по сути вся криптография держится на том, что подбор ключей в лоб занимает, как говориться, «неприемлемое» время, т.е. информация устареет раньше, чем будет подобран ключ. А как раз основная опасность для классической криптографии, это то, что все шифрование как с симметричное, так и асимметричное будет на квантовых вычислителях будет просто просчитано в лоб, ибо скорость вычисления у них будет не в разы, а в 10^6 раз быстрее, ну или около того.
            0

            Многие проблемы, на базе которых строят асимметричные криптоалгоритмы, ускоряются экспоненциально. Но для симметричных и для хеш-сумм достаточно просто удвоить длину ключа, т.к. Алгоритм Гровера требует O(sqrt(N)) операций для полного перебора N значений: вместо перебора 2^128 ключей потребуется (в теории) всего 2^64 квантовых операций (на практике есть проблемы с столь длительной обработкой квантового состояния).


            http://csrc.nist.gov/groups/ST/post-quantum-crypto/documents/pqcrypto-2016-presentation.pdf#page=3


             When will a quantum computer be built?
            ◦ 15 years, $1 billion USD, nuclear power plant (PQCrypto 2014, Matteo Mariantoni)
             Impact:
            ◦ Public key crypto:
            RSA
            Elliptic Curve Cryptography (ECDSA)
            Finite Field Cryptography (DSA)
            Diffie-Hellman key exchange
            ◦ Symmetric key crypto:
             AES — Need larger keys
             Triple DES — Need larger keys
            ◦ Hash functions:
             SHA-1, SHA-2 and SHA-3 — Use longer output

            Недавно запретили AES-128 и требуют удлинять ключи в асимметричных: http://csrc.nist.gov/groups/SMA/ispab/documents/minutes/2015-10/oct21_stanger_final_approved_nsa.pdf


            Cryptography Today Suite “Use What You Have”
            Public Key P-384
            RSA/DH 3072+
            Symmetric AES 256
            Hash SHA-384

            http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf


            We don’t know that Grover’s algorithm will ever be practically relevant, but if it is, doubling the key size will be sufficient to preserve security. Furthermore, it has been shown that an exponential speed up for search algorithms is impossible, suggesting that symmetric algorithms and hash functions should be usable in a quantum era [2].
              0
              Ну во-первых это использование алгоритма на одном квантовом вычислителе позволяет понизить в заявленное количество раз, а как насчет распараллелить просчет, на нескольких устройствах? Во-вторых, рассматривается случай черного ящика. Во-вторых, а как же Алгоритм Шора при использование его и возможностей квантовых компьютеров, алгоритм способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера поставила бы крест на большей части современной криптографической защиты. (Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом).
                0

                Для большинства ныне используемых асимметричных алгоритмов (с публичным ключом) успешно работает Шор, именно их надо заменять (все 4 варианта Public key crypto в той презентации были зачеркнуты).


                Алгоритм Шора не работает для распространенных симметричных алгоритмов, только Гровер.


                Распараллеливать можно классические переборщики, и до определенных пределов это полезно:


                Классический параллелизм 56, 64, 128, 256

                Для полного перебора ключа в 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"


                С одной стороны Гровер позволяет значительно (квадратично) снизить количество операций (2^32 для ключа 64, 2^64 для ключа в 128, 2^128 для 256 бит). С другой стороны реализации криптоалгоритмов в квантовом компьютере (в составе блока Uω алгоритма) не конвейеризуются так же легко, как в классических чипах. Т.е. на одну операцию будет уходить не один такт, а десятки (= полное последовательное выполнение всего криптоалгоритма).
                Частоты "переключения" (обработки кубитов) квантовых вентилей (это еще не тактовая частота для алгоритма, в такт в классических чипах переключаются цепочки длиной в десятки вентилей) вероятно будут несколько ниже. В популярной для реализации кв. компьютеров для частных случаев алгоритма шора типа 15 и 21 технологии LOQC частота переключения вентиля (~f_max) ограничена геометрией, в которой летают фотоны, т.е. тысячи-сотни нс на столе и до сотен нс в интегрированном чипе; для сверхпроводящих кубитов в чипах (охлаждаемых растворением гелия-3 в гелии-4) в целом такое же геометрическое ограничение в десятки нс.


                Алгоритм Гровера является последовательным — для срабатывания алгоритма (усиления одного из состояний) требуется одно и только одно единичное значение функции в данном интервале поиска (wiki "f be the function that maps database entries to 0 or 1, where f(x) = 1 if and only if x satisfies the search criterion (x = ω)."; crypto.so 25168 "Grovers algorithm only outputs a correct answer if it is feed with a input set such that the target function evaluates as 1 for a single input and as 0 otherwise."). Амплитуда искомого значения немного усиливается (inversion about mean) на каждой операции, после порядка C*sqrt(n) операций она станет заметной: https://youtu.be/JbAwuRA__Ec?t=329
                Необходимо выполнить полное количество операций последовательно в рамках одного кванового компьютера (без потери когерентности в процессе).


                arXiv quant-ph/9711070 "Grover’s quantum searching algorithm is optimal"


                I also show that unfortunately quantum searching cannot be parallelized better than by assigning different parts of the search space to independent quantum computers.
                … Bennett et al. [3] have shown that asymptotically no quantum algorithm can solve the problem in less
                than a number of steps proportional to √N. Boyer et al. [4] have improved this result to show that e.g. for a 50% success probability no quantum algorithm can do better than only a few percent faster than Grover’s algorithm.

                https://arxiv.org/pdf/1603.09383.pdf — "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" — B Parallel quantum search


                Classical search is easily parallelized by distributing the 2^k bitstrings among 2^t processors. Each processor fixes the first t bits of its input to a unique string and sequentially evaluates every setting of the remaining k − t bits…
                Quantum computation has a different time/area trade-off curve. In particular, parallel quantum strategies have strictly greater cost than sequential quantum search.… Parallelizing this algorithm across 2^t quantum processors reduces the temporal cost per processor by a factor of 2^t/2 and increases the area by a factor of 2^t. Fixing t bits of the input does not change the overhead of the Grover iteration

                (Некто Lov K. Grover из Bell Labs, Lucent по заказу "NSA and ARO" выяснил в 2004 году — quant-ph/0407217, что параллелизм в алгоритме L.K. Grover от 1996 года есть только для случая, когда в базе данных есть несколько значений k для которых f(k)=1)


                Есть оценки сложности реализации Гровера для AES: https://arxiv.org/pdf/1512.04965v1.pdf Applying Grover’s algorithm to AES: quantum resource estimates — 2015-12-15; выбран вариант одного искомого значения k — "serial nature of Grover’s algorithm...for the case of AES, such that there is (plausibly) precisely one solution to the problem of finding the correct key K that was used to encrypt a small set of given plaintext-ciphertext pairs, i.e., we can (plausibly) enforce the situation M = 1 by defining a suitable function f". Для AES-128 — миллион вентилей с глубиной схемы в 50-110 тысяч вентилей (это на одну итерацию AES из ~2^64 необходимых), ширина — порядка тысячи кубитов. Допустим, у нас есть быстрый кв.вентиль, работающий за 10 нс — тогда одна операция AES128 займет ~1 мс. 2^64 операций займут порядка 2^54 сек = 2^29 лет (всего лишь полмиллиарда лет, на протяжении которых нельзя нарушать квантовое состояние вычислителя). У AES256 — глубина схемы 60-130 тыс.

            +1
            А что с НИСТ были за проблемы? Я что-то ни найти, ни припомнить никак не могу. Мне они казались как раз из тех немногих кто в этой области ещё как-то прилично себя вели.
              0

              Наиболее известный случай — 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


              The Guardian and the New York Times reported that NIST allowed the National Security Agency (NSA) to insert a cryptographically secure pseudorandom number generator called Dual EC DRBG into NIST standard SP 800-90 that had a backdoor that the NSA can use to covertly decrypt material that was encrypted using this pseudorandom number generator.[18] Both papers report[19][20] that the NSA worked covertly to get its own version of SP 800-90 approved for worldwide use in 2006. The leaked document states that "eventually, NSA became the sole editor". The reports confirm suspicions and technical grounds publicly raised by cryptographers in 2007 that the EC-DRBG could contain an kleptographic backdoor (perhaps placed in the standard by NSA).[21]

              Еще есть теории заговора по выбору ECC-кривых NIST (Эллиптическая_криптография#Эллиптические кривые, рекомендованные NIST)


              NIST рекомендует 15 эллиптических кривых, многие из которых были получены Jerry Solinas (NSA) на базе наработок Neal Koblitz (англ.)русск.[9]. В частности, FIPS 186-3[10] рекомендует 10 конечных полей.… Эти конечные поля и эллиптические кривые выбраны, как часто ошибочно считается, из-за высокого уровня безопасности. По заявлениям NIST, их выбор был обоснован эффективностью программной реализации.12 Имеются сомнения в безопасности по крайней мере нескольких из них.13 14 15

              И также заговор по константам в популярных параметрах для классического 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"


              Our chosen prime p looks random, and p−1 has a 160-bit prime factor, in line with recommended parameters for the Digital Signature Algorithm. However, our p has been trapdoored in such a way that the special number field sieve can be used to compute discrete logarithms in F∗_p, yet detecting that p has this trapdoor seems out of reach… Our computations show that trapdoored primes are entirely feasible with current computing technology. We also describe special number field sieve discrete log computations carried out for multiple weak primes found in use in the wild.… In this paper, we demonstrate that constructing and exploiting trapdoored primes for Diffie-Hellman and DSA is feasible for 1024-bit keys with modern academic computing resources.… both France and China standardized elliptic curves for public use without providing any sort of justification for the chosen parameters… RFC 5114… parameters were drawn from NIST test data, but neither the NIST test data [39] nor RFC 5114 itself contain the seeds used to generate the finite field parameters.
                +1
                Спасибо. У меня эти истории ассоциировались скорее с АНБ. В данном случае подача тоже скорее от АНБ https://geektimes.ru/post/260684/
          0
          1. Криптография, которая основана на хэ-функциях.
          Прочитал сначала, как «хз-функции».
            –1

            История развивается по спирали, в 40ые годы 20го века первые ЭВМ появились именно для расшифровки кодов, что в свою очередь вызвало в последствии бум криптографии. Сейчас, похоже, намечается примерно тоже самое.

              0
              «брейнсторминг» — это не «мозговой штурм» по-русски?
                +1
                Так как тема относительно знакомая, если не возражаете, дополню парой моментов

                1. Про hash-based системы, к сожалению не помню деталей. Так что пропущу )
                2. Системы на базе кодов — развиваются последние тридцать-сорок, кажется лет. С переменным успехом. Криптосистема МакЭллиса — одна из старейших, остается одной из самых стабильных. Все попытки собрать на этой базе что-то более вменяемое рано или поздно взламываются. Минус — ооооооочень большой ключ на вменяемых размерностях. Зато быстрая, особенно асимптотически.
                3. Криптосистемы на решетках. Имеют под собой две задачи на одной специфичной структуре. Одна из задач почти не используется, а вторая полностью совпадает с задачей для code-based криптосистем, что лично у меня вызывает недоумение. Самая известная криптосистема в этом классе насколько знаю NTRU с двумя большими минусами — закрыта патентами и имеет рекомендованные параметры (что традиционно вызывает недоверие). Соответственно интерес к ней мягко говоря не очень большой.
                4. Многомерные квадратичные системы(MQ-problem). Хорошая мат.задача в основе, но реализации стабильно ломаются. Идея постоянно развивается, но хорошей реализации как понимаю, на данный момент нет. Кстати, почти везде фамилию Patarin перевирают :) Он скорее Жак Патара. Насколько знаю, в этом направлении копает он со своими последователями и еще одна группа в Японии.
                5. Как альтернативу, рассматривать симметричные криптосистемы можно, но ставить в один ряд с асимметричными несколько странно.

                В начале 2000-х Еврокомиссия проводила конкурс NESSIE на крипто-системы, где среди участников было несколько схем на базе MQ-проблемы, одна из которых даже вышла в финал(SFLASH), однако через несколько лет была отозвана из-за найденной уязвимости.

                Существует конференция PQCrypto, проходящая довольно регулярно, посвященная как раз вопросам постквантовой криптографии.

                Есть еще несколько некоммутативных задач, на базе которых можно строить криптосистемы (вроде что-то из теории кос предлагалось), но как-то до готовой системы толи не доходит, толи не вызывает должного интереса, т.к. даже в рамках той же конференции PQCrypto секции бьются по задачам упомянутым выше — hash,code,lattice, MQ

                И в целом очень огорчает тот факт, что на русском языке материалов по теме постквантовой криптографии чуть больше нуля :(
                  0
                  Где-то месяц назад был ещё один занимательный эпизод на эту тему: Петер Шор (тот самый) с коллегой заслали в arXiv статью о квантовой атаке на одну из систем криптографии на решётках. Правда потом почти сразу её изъяли, но так как там были праздники и выходные, она ещё некоторое время пролежала, так что дискуссий было достаточно, напимер вот тут более подробно .
                    0
                    Я правильно понял, что изъяли из-за найденной ошибки?
                      0
                      Пишут что ошибка. Вопрос можно ли её исправить или это фатально.

                Only users with full accounts can post comments. Log in, please.