Комментарии 16
2 На практике оно малоприменимо. Не будут же от каждого сайта до каждого потребителя оптоволокно тащить.
И НИСТу я бы не стал доверять: их уже однажды уличили.
И НИСТу я бы не стал доверять: их уже однажды уличили.с этим не поспоришь.
Но все же квантовое распределение ключа все же в идеале безопасней того, что сейчас используется. Да и передаваться может не только ключ по квантовому каналу, но и любая другая информации, и защитой тут уже будет не математика, как в случае с классической криптографией, а физика. А с физикой бороться сложнее, чем с математическими вычислениями.
Ведь по сути вся криптография держится на том, что подбор ключей в лоб занимает, как говориться, «неприемлемое» время, т.е. информация устареет раньше, чем будет подобран ключ. А как раз основная опасность для классической криптографии, это то, что все шифрование как с симметричное, так и асимметричное будет на квантовых вычислителях будет просто просчитано в лоб, ибо скорость вычисления у них будет не в разы, а в 10^6 раз быстрее, ну или около того.
Многие проблемы, на базе которых строят асимметричные криптоалгоритмы, ускоряются экспоненциально. Но для симметричных и для хеш-сумм достаточно просто удвоить длину ключа, т.к. Алгоритм Гровера требует 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].
Для большинства ныне используемых асимметричных алгоритмов (с публичным ключом) успешно работает Шор, именно их надо заменять (все 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"
С одной стороны Гровер позволяет значительно (квадратично) снизить количество операций (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 тыс.
Наиболее известный случай — 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. Криптография, которая основана на хэ-функциях.Прочитал сначала, как «хз-функции».
История развивается по спирали, в 40ые годы 20го века первые ЭВМ появились именно для расшифровки кодов, что в свою очередь вызвало в последствии бум криптографии. Сейчас, похоже, намечается примерно тоже самое.
1. Про hash-based системы, к сожалению не помню деталей. Так что пропущу )
2. Системы на базе кодов — развиваются последние тридцать-сорок, кажется лет. С переменным успехом. Криптосистема МакЭллиса — одна из старейших, остается одной из самых стабильных. Все попытки собрать на этой базе что-то более вменяемое рано или поздно взламываются. Минус — ооооооочень большой ключ на вменяемых размерностях. Зато быстрая, особенно асимптотически.
3. Криптосистемы на решетках. Имеют под собой две задачи на одной специфичной структуре. Одна из задач почти не используется, а вторая полностью совпадает с задачей для code-based криптосистем, что лично у меня вызывает недоумение. Самая известная криптосистема в этом классе насколько знаю NTRU с двумя большими минусами — закрыта патентами и имеет рекомендованные параметры (что традиционно вызывает недоверие). Соответственно интерес к ней мягко говоря не очень большой.
4. Многомерные квадратичные системы(MQ-problem). Хорошая мат.задача в основе, но реализации стабильно ломаются. Идея постоянно развивается, но хорошей реализации как понимаю, на данный момент нет. Кстати, почти везде фамилию Patarin перевирают :) Он скорее Жак Патара. Насколько знаю, в этом направлении копает он со своими последователями и еще одна группа в Японии.
5. Как альтернативу, рассматривать симметричные криптосистемы можно, но ставить в один ряд с асимметричными несколько странно.
В начале 2000-х Еврокомиссия проводила конкурс NESSIE на крипто-системы, где среди участников было несколько схем на базе MQ-проблемы, одна из которых даже вышла в финал(SFLASH), однако через несколько лет была отозвана из-за найденной уязвимости.
Существует конференция PQCrypto, проходящая довольно регулярно, посвященная как раз вопросам постквантовой криптографии.
Есть еще несколько некоммутативных задач, на базе которых можно строить криптосистемы (вроде что-то из теории кос предлагалось), но как-то до готовой системы толи не доходит, толи не вызывает должного интереса, т.к. даже в рамках той же конференции PQCrypto секции бьются по задачам упомянутым выше — hash,code,lattice, MQ
И в целом очень огорчает тот факт, что на русском языке материалов по теме постквантовой криптографии чуть больше нуля :(
НИСТ просит помощи в создании надежных постквантовых методов шифрования данных