Comments 31
Слабость механизма факторизации
А можете пояснить, в чем заключается слабость? Недостаточная длина, плохой генератор случайных чисел или что-то другое?
Факторизация — это операция, обратная перемножению простых чисел. Если понимать буквально, то чем слабже, т.е. хуже у вас работает факторизация, тем лучше защищена закрытая компонента ключа.
Слабая там не факторизация, а результат перемножения факторизуется быстрее, чем известными алгоритмами из-за особенностей выбора компонентов пары.
С длиной все в порядке, очевидно использовались слабые пары. Например такие что дают N-1 состоящий из маленьких множителей. Или еще что похитрее.
...In the context of a responsible disclosure process, the team informed Infineon upfront that also “Fast Prime” could be exposed to an exploit using one of the newly developed analysis methods under a specific combination of preconditions: First, the application software must utilize the “Fast Prime” algorithm instead of the non-accelerated version, both of which are selectable. Second, the RSA key pairs have to be generated on a card or token which uses this algorithm. If these preconditions are met, then RSA key lengths of up to 2048 bits are considered to be significantly weakened in cryptographic strength...
www.infineon.com/cms/en/product/promopages/rsa-update/rsa-background
Технически проблема решается сбором «примерно случайной» информации: как вы нажимаете на клавиши или водите мышем, на деле все подходящие «внутрисистемные события» (точное время поступления аппаратных прерываний и т.д.). При этом крайне важно собрать/накопить достаточное количество «случайности» и затем правильно нафаршировать ею ключ. Типичная ошибка (утрированно) — начало ключа случайное, а потом не очень (пошли по кругу или ещё хуже).
Так вот, суть проблемы в том, что внутри библиотечки необходимая «случайность» либо плохо собиралась, либо плохо использовалась, либо и то и другое — собственно не важно. Главное, что в результате генерируемые ключи шифрования не всегда полностью случайны и проявляют существенные статистические искажения, в том числе корреляцию между отдельными битами и т.д.
Соответственно, зная причину и природу этих отклонений можно найти секретный ключ несравнимо быстрее, чем полным перебором.
Ну, корреляция между отдельными битами ключа — это алгоритмическая ошибка, которая ничего общего с энтропией не имеет. Хороший криптостойкий генератор (псевдо)случайных чисел должен давать на выходе последовательность без каких бы то ни было корреляций даже если его инициализировать нулями.
Недостаток энтропии обычно проявляется в другом — сгенерированные ключи оказываются одинаковыми у разных пользователей.
Насколько я сейчас понимаю проблема происходит от primesieve.org, точнее в последствиях en.wikipedia.org/wiki/Wheel_factorization
Так вот, суть проблемы в том, что внутри библиотечки необходимая «случайность» либо плохо собиралась, либо плохо использовалась, либо и то и другое — собственно не важно.
Нет.
The vulnerability does NOT depend on a weak or a faulty random number generator — all RSA keys generated by a vulnerable chip are impacted.
Уязвимость алгоритмическая
Но на практике, как правило, нет хорошего доступного источника настоящей случайности.
Чушь, вы отстали примерно на пару десятилетий. Уже давно в процессорах аппаратные генераторы случайных чисел на тепловых шумах.
habrahabr.ru/post/128666
Чушь, вы отстали примерно на пару десятилетий. Уже давно в процессорах аппаратные генераторы случайных чисел на тепловых шумах.
На всякий — в эксплуатации находятся достаточно процессоров без RDRAND или аналогов этой инструкции. При этом собранную "случайность" всё равно нужно правильно использовать...
Этим занимаются части операционной системы, отвечающие за функцию CryptGenRandom в Windows и псевдоустройство /dev/random в Linux.
Ну всё правильно, только это не имеет непосредственного отношения к инфинеоновскому контроллеру, его прошивке и сопутствующих библиотекам. Более того, я соглашусь что моё многословие по теме в том комментарии было лишним. Особенно в ключе того, что дело там в «сите» (генераторе) простых чисел, а не где-то ещё.
Тем не менее, с генераторами «случайности» не всё очевидно и упомянутая позиция Линуса совершенно оправдана (т.е. мышиные телодвижения таки попадают в /dev/random даже при наличии RDRAND у CPU). Как говорится «Добрым словом и револьвером можно добиться большего, чем одним добрым словом» (Аль Капоне).
...I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction. To quote from the article below: 'By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors....' Relying solely on the hardware random number generator which is using an implementation sealed inside a chip which is impossible to audit is a BAD idea…
Linus Torvalds dismissed concerns about the use of RdRand in the Linux kernel, and pointed out that it is not used as the only source of entropy for /dev/random, but rather used to improve the entropy by combining the values received from RdRand with other sources of randomness. However, Taylor Hornby of Defuse Security demonstrated that the Linux random number generator could become insecure if a backdoor is introduced into the RdRand instruction that specifically targets the code using it. Taylor's proof-of-concept implementation works on an unmodified Linux kernel prior to version 3.13...
en.wikipedia.org/wiki/RdRand
Пишут, что это вариация на тему https://en.wikipedia.org/wiki/Coppersmith%27s_attack — в большом наборе ключей обнаружили закономерность в структуре "генерируемых" чипом простых чисел при использовании ускоренного метода проверки на простоту “Fast Prime”. Полное описание атаки будет доступно 2 ноября.
https://keychest.net/roca "… The ROCA vulnerability has been discovered by researchers at Masaryk University (Brno, Czech Republic).… ROCA vulnerability, which is caused by an error in RSA key generation in Infineon security chips."
Technical details: The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli (ROCA) — ACM CCS conference on 2nd November 2017 — https://acmccs.github.io/session-H1/
https://crocs.fi.muni.cz/public/papers/rsa_ccs17 ROCA: Vulnerable RSA generation (CVE-2017-15361)
The vulnerability is present in NIST FIPS 140-2 and CC EAL 5+ certified devices since at least the year 2012.… The algorithmic vulnerability is characterized by a specific structure of the generated RSA primes, which makes factorization of commonly used key lengths including 1024 and 2048 bits practically possible.… The worst-case price of the factorization on an Amazon AWS c4 computation instance is $76 for the 1024-bit key and about $40,000 for the 2048-bit key.…
The vulnerability was found by a close inspection of a large number of RSA keys generated and exported from the manufacturer smartcards by researchers at CRoCS laboratory, Masaryk University, Enigma Bridge and Ca' Foscari University. The full results will be presented at an academic ACM Conference on Computer and Communications Security (ACM CCS '17) starting from October 30th.
Предложен оффлайн тест для обнаружения слабых ключей — https://github.com/crocs-muni/roca
Код проверяет, попадают ли остатки от деления N на ряд малых простых в определенные наборы https://github.com/crocs-muni/roca/blob/master/roca/detect.py#L597
self.primes = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167]
self.prints =....
for i in range(0, len(self.primes)):
if (1 << (modulus % self.primes[i])) & self.prints[i] == 0:
return Falsehttps://crypto.stackexchange.com/questions/52292/what-is-fast-prime "N mod 97 ∈ {1,35,36,61,62,96}"
Также исследователи связались с администрацией GitHub, сервис сейчас оповещает пользователей о необходимости замены ключей для подписи софта.В репозитории указан уязвимый ключ с длиной до 4096 бит, созданный GnuPG v2. Я создавал ключ по инструкции длиной 4096 бит (GnuPG v1.4.21). Результаты теста открытого ключа — безопасный.
Зачем выкладывают закрытые ключи в репозитории?
Некоторые детали — http://blog.cr.yp.to/20171105-infineon.html 2017.11.05: Reconstructing ROCA A case study of how quickly an attack can be developed from a limited disclosure. #infineon #roca #rsa
https://crypto.stackexchange.com/questions/53906/how-does-the-roca-attack-work Dec 13 '17
Полный тест https://github.com/crocs-muni/roca/blob/master/roca/detect.py#L496
https://acmccs.github.io/papers/p1631-nemecA.pdf "The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli" — CCS’17, October 30-November 3, 2017
RSA requires two large random primes p and q… However, there are at least three reasons to construct a candidate number from several smaller (randomly) generated components instead of generating it randomly:…
Yet, constructed primes may bring new problems as demonstrated in our work.… If at least one half of the bits of one of the primes is known, the remaining bits can be computationally recovered
attack utilizes the specific structure of the primes as generated by Manufacturer’s on-chip cryptographic library (further denoted as RSALib 1 — RSA v1.02.013 library)…
All RSA primes (as well as the moduli) generated by the RSALib have the following form: p = k ∗ M + (65537^a mod M).
The integer M is known and equal to some primorial M = Pn# (the product of the first n successive primes Pn# = \prod_{i=1}^{n} Pi = 2 ∗ 3 ∗ · · · ∗ Pn). The value n = 39 (i.e., M = 2 ∗ 3 ∗ · · · ∗ 167) is used to generate primes for an RSA key with a key size within the [512, 960] interval.
… Hence, the resulting RSA primes suffer from a significant loss of entropy (e.g., a prime used in 512-bit RSA has only 99 bits of entropy), and the pool from which primes are randomly generated is reduced (e.g., from 2^256 to 2^99 for 512-bit RSA).
The public RSA modulus N is a product of two primes p,q
N = p *q = (k ∗ M + 65537^a mod M) ∗ (l ∗ M + 65537^b mod M)
Использовали генератор по мотивам [JP2006]: Marc Joye and Pascal Paillier; Fast Generation of Prime Numbers on Portable Devices: An Update, in proceedings of CHES 2006 (slides). https://link.springer.com/content/pdf/10.1007/11894063_13.pdf https://doi.org/10.1007/11894063_13 https://www.iacr.org/workshops/ches/ches2006/presentations/Marc%20Joye.pdf
Изначально — быстрый и детерминированный алгоритм, позволяет хранить всего лишь 20 байт вместо 128байт=1024бит и перегенерировать ключ по запросу:
On-board key generation… • Re-generation on demand, dynamically-chosen sizes • Applications can manage keys on their own • Opens the way to key compression: e.g., 1024-bit RSA key 7→ 20 bytes
И неправильная его реализация — http://blog.cr.yp.to/20171105-infineon.html
Infineon was computing a power of a single number g modulo the product L = 2357… This would save Infineon the CRT effort, and would have the same basic effect of guaranteeing that the resulting integers are coprime to L, i.e., not divisible by any of the primes dividing L. This would also force all output keys to be 1 or 10 modulo 11 if g happened to be 10 modulo 11.…
The guess was that (company) was oversimplifying and generating merely a power of gg; this produces far fewer numbers modulo LL. The authors wrote back promptly, confirming that this guess was correct but not revealing more details.
интересно, а если пользователь будет всегда использовать персональный закрытый ключ, насколько это сможет повысить степень защиты.
скажем пользователю выдаются ( например по электронной почте ) набор случайных слов — ромб, вектор, плазмотрон, мятный, есть… и так ~64 буков. пользователь вводит их приложение, браузер. там оно склеивается и фиксится. теперь всё шифруется с помощью этого ключа.
такое в теории сломать проблематично, и если будет сломано, то только для 1го случая.
что тут принципиально не айс, ну кроме применения третьих почтовых программ?
Плюс если кто-то утащит этот ваш ключ, то сможет расшифровать все предыдущие сообщения. Некоторые современные протоколы защищают от этого (TLS можно настроить, OpenVPN в режиме TLS всегда), см. Perfect Forward Secrecy и протокол Диффи-Хэллмана
К тому же, если набор слов (ключ) выдавать по электронной почте, то перехватив вашу почту (её же шифровать нечем — ключами ещё не обменялись), злоумышленник сможет читать и все следующие сообщения.
пользователю не разрешается самому создавать закрытый ключ. стоит задуматься, использовать или нет подобные решения, если вы не можете контролировать не только их работу, но даже не можете создать закрытый ключ более открытой библиотекой.
Я уж подумал очередная дыра в OpenSSL
92AAE726C9F3CEA8AACE8B74726387093137B33B1A2985FF2DA10EEB034AA4467029B7C90282D9B131B20E098C27224851082125501A48F14417AE1FE849F276103046F9A4D429B4B394FA89D56D7E30C696482D63637A195A0F7546E88A29ECAFABB53BF049E75CCC71FB43F896F7059FCCBF0EEA194EF3F7A1D40800E44CD1
Серьезная уязвимость в популярной библиотеке шифрования подрывает безопасность миллионов крипто-ключей