Слабость механизма факторизации

А можете пояснить, в чем заключается слабость? Недостаточная длина, плохой генератор случайных чисел или что-то другое?
слабость механизма факторизации как раз и используется для защиты закрытого ключа. там какая-то неточность перевода.
Ни-че-го не понимаю… :-)

Факторизация — это операция, обратная перемножению простых чисел. Если понимать буквально, то чем слабже, т.е. хуже у вас работает факторизация, тем лучше защищена закрытая компонента ключа.
Слабая там не факторизация, а результат перемножения факторизуется быстрее, чем известными алгоритмами из-за особенностей выбора компонентов пары.

>используют для обеспечения безопасности уязвимые ключи длиной 2048 бит.

С длиной все в порядке, очевидно использовались слабые пары. Например такие что дают 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.

Уязвимость алгоритмическая
Да, чуть выше уже уточнил про wheel factorization.

С другой стороны, по-сути собранная случайность плохо использовалась.
Но на практике, как правило, нет хорошего доступного источника настоящей случайности.

Чушь, вы отстали примерно на пару десятилетий. Уже давно в процессорах аппаратные генераторы случайных чисел на тепловых шумах.
habrahabr.ru/post/128666
Чушь, вы отстали примерно на пару десятилетий. Уже давно в процессорах аппаратные генераторы случайных чисел на тепловых шумах.

На всякий — в эксплуатации находятся достаточно процессоров без RDRAND или аналогов этой инструкции. При этом собранную "случайность" всё равно нужно правильно использовать...

Этим занимаются части операционной системы, отвечающие за функцию CryptGenRandom в Windows и псевдоустройство /dev/random в Linux. Я возражал именно против «на практике, как правило, нет хорошего доступного источника настоящей случайности», потому как это дела минувших дней. По крайней мере даже в процессорах AMD двухлетней давности эту инструкцию реализовали, а в самых новых ещё более надёжная RDSEED есть. Так что, по сути, не имеют надёжного источника случайных чисел только либо морально старые процессоры, либо процессоры не для серверного/десктопного применения — всякие там энергоэффективные (и неспешные) miprs/arm/etc.
Этим занимаются части операционной системы, отвечающие за функцию CryptGenRandom в Windows и псевдоустройство /dev/random в Linux.

Ну всё правильно, только это не имеет непосредственного отношения к инфинеоновскому контроллеру, его прошивке и сопутствующих библиотекам. Более того, я соглашусь что моё многословие по теме в том комментарии было лишним. Особенно в ключе того, что дело там в «сите» (генераторе) простых чисел, а не где-то ещё.

Тем не менее, с генераторами «случайности» не всё очевидно и упомянутая позиция Линуса совершенно оправдана (т.е. мышиные телодвижения таки попадают в /dev/random даже при наличии RDRAND у CPU). Как говорится «Добрым словом и револьвером можно добиться большего, чем одним добрым словом» (Аль Капоне).
Есть интересные комментарии в википедии по поводу RDRAND:

...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 False

https://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). Результаты теста открытого ключа — безопасный.
Зачем выкладывают закрытые ключи в репозитории?
Выкладывают публичные, а уязвимости подвержены ключи, сгенерированные внутри смарт-карт.
немного не про то, но
интересно, а если пользователь будет всегда использовать персональный закрытый ключ, насколько это сможет повысить степень защиты.
скажем пользователю выдаются ( например по электронной почте ) набор случайных слов — ромб, вектор, плазмотрон, мятный, есть… и так ~64 буков. пользователь вводит их приложение, браузер. там оно склеивается и фиксится. теперь всё шифруется с помощью этого ключа.
такое в теории сломать проблематично, и если будет сломано, то только для 1го случая.
что тут принципиально не айс, ну кроме применения третьих почтовых программ?
Принципиально не айс тут схема распределения ключей, когда ключами надо обмениваться по защищённому каналу связи. Если абонентов много и отсутствует единый доверенный центр распределения ключей — это превращается в ад.
Плюс если кто-то утащит этот ваш ключ, то сможет расшифровать все предыдущие сообщения. Некоторые современные протоколы защищают от этого (TLS можно настроить, OpenVPN в режиме TLS всегда), см. Perfect Forward Secrecy и протокол Диффи-Хэллмана

К тому же, если набор слов (ключ) выдавать по электронной почте, то перехватив вашу почту (её же шифровать нечем — ключами ещё не обменялись), злоумышленник сможет читать и все следующие сообщения.
вот это интерересно, данкешн

ключами надо обмениваться по другому каналу (на сходке фидошников, например :D)

пользователю не разрешается самому создавать закрытый ключ. стоит задуматься, использовать или нет подобные решения, если вы не можете контролировать не только их работу, но даже не можете создать закрытый ключ более открытой библиотекой.

Я уж подумал очередная дыра в OpenSSL

а все так подумали, заголовок вон какой. В популярной где, сразу хочется спросить.

А найденные уязвимости и атаки на них были известны в момент, когда данные чипы и библиотеки создавались, или нет? </параноик_мод>
У кого-нибудь есть TPM-модуль от ASUS? Обновление от Dell ставится на него или там проверка модели?
Примерчик уязвимого ключа со смарт-карты (RSA-1024, hex)
92AAE726C9F3CEA8AACE8B74726387093137B33B1A2985FF2DA10EEB034AA4467029B7C90282D9B131B20E098C27224851082125501A48F14417AE1FE849F276103046F9A4D429B4B394FA89D56D7E30C696482D63637A195A0F7546E88A29ECAFABB53BF049E75CCC71FB43F896F7059FCCBF0EEA194EF3F7A1D40800E44CD1
Только полноправные пользователи могут оставлять комментарии.
Войдите, пожалуйста.