![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
waqurСлабое место криптосистемы RSA — источник (псевдо)случайных чисел.
У него должна быть достаточно высокая энтропия.
Что значит "достаточно высокая"? Национальный институт стандартов и технологий (NIST) рекомендует использовать двойную битовую длину истинного случайного "засевочного" значения по сравнению с требуемым уровнем безопасности. Например, вы рассчитываете на криптоанализ сложности 2128, тогда вам нужны 256 истинно случайных бит на каждый RSA ключ.
Естественно, на практике так бывает не всегда, и некоторые реализации просто используют в качестве ГПСЧ rand(3), "засевая" её результатом работы функции time(3).
Надёжность RSA построена на сложности задачи факторизации (разложения на простые множители) большого целого числа, порядка 22048. Простые множители p и q являются основной частью приватного ключа, а их произведение pq является основной частью публичного ключа.
Когда у нас небольшая энтропия ГПСЧ, множители p и q, сгенерированные случайно для разных ключей, начинают повторяться. Причём благодаря парадоксу дней рождения, повторяться они начинают намного раньше, чем думает большинство людей.
Проблема в том, что RSA математически очень уязвима к таким повторам. Достаточно иметь два открытых ключа pq и ps, с совпадающим множителем p, и тогда путём нехитрых манипуляций (алгоритм Евклида) можно будет извлечь p, а вслед за ним q и s. Итог: оба публичных ключа факторизованы. Можно читать PGP-почту, прослушивать/подменять https-трафик и подделывать электронную цифровую подпись.
Сегодня был опубликован препринт статьи, авторы которой собрали коллекцию из 7 миллионов публичных RSA-ключей и путём вычисления общего сомножителя в каждой паре* публичных ключей смогли факторизовать 0.4% из них.
http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars
Дело в том, что заметная потеря энтропии происходит при переходе от псевдослучайных байт к псевдослучайным большим простым числам.
Предположим, мы используем генератор случайных чисел, имеющий 1024 миллиарда возможных состояний (40-битная энтропия). Предположим мы генерируем им выборку 512-битных целых чисел, которые мы затем тестируем на простоту (просеиваем). Вероятность этих целых чисел быть простыми составляет примерно 1/ln(2512), или около 1/354. Так что у нас будет примерно 3 миллиарда разных простых чисел на выходе из этого генератора.
Ключ состоит из двух простых чисел, так что два ключа имеют 4 возможных комбинации множителей, которые могут совпасть. Таким образом, вероятность, что два RSA-ключа "испортят друг друга" наличием общего множителя равна примерно 1 на 750 миллионов.
Если у нас в общем пуле есть 7 млн RSA-ключей, то это они образуют 7млн*7млн/2 пар, из которых каждая 750-миллионная пара окажется "дефективной". Всего таких пар найдётся около 32.7 тысяч, и они испортят 65.3 тыс ключей или 0.92% от общего количества.
На практике вышло чуть меньше, но того же порядка. Это значит только, что не у всех такие плохие генераторы ПСЧ с низкой энтропией.
Авторы нашумевшей статьи пишут:
Almost all of the vulnerable keys were generated by and are used to secure embedded hardware devices such as routers and firewalls, not to secure popular web sites such as your bank or email provider. Only one of the factorable SSL keys was signed by a trusted certificate authority and it has already expired.
https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs
Действительно, аппаратные роутеры и файерволлы — то такое, было бы куда печальнее, если бы один из факторизованных ключей оказался в SSL trusted root. 40-битный seed идёт вразрез с рекомендациями NIST, кто его всё равно использует на свой страх и риск — ССЗБ (Сам Себе Злобный Буратино).
В целом и в общем, теория идеально согласуется с практикой. Говённая реализация => Парадокс дней рождения и потеря энтропии на просеве простых чисел => Безопасность псу под хвост.
Подобная история со слабой энтропией ГПСЧ была в 2001 году, когда хакеры взломали систему защиты программ от реверс-инжинеринга, ASProtect, и выслали автору Алексею Солодовникову на e-mail генератор ключей к ASProtect. подробнее см. книгу "Защита информации" Д.Склярова, стр 83
* На самом деле, можно чуть быстрее, чем в каждой паре
См. также об источниках энтропии в ПК: http://waqur.livejournal.com/421109.html
У него должна быть достаточно высокая энтропия.
Что значит "достаточно высокая"? Национальный институт стандартов и технологий (NIST) рекомендует использовать двойную битовую длину истинного случайного "засевочного" значения по сравнению с требуемым уровнем безопасности. Например, вы рассчитываете на криптоанализ сложности 2128, тогда вам нужны 256 истинно случайных бит на каждый RSA ключ.
Естественно, на практике так бывает не всегда, и некоторые реализации просто используют в качестве ГПСЧ rand(3), "засевая" её результатом работы функции time(3).
Надёжность RSA построена на сложности задачи факторизации (разложения на простые множители) большого целого числа, порядка 22048. Простые множители p и q являются основной частью приватного ключа, а их произведение pq является основной частью публичного ключа.
Когда у нас небольшая энтропия ГПСЧ, множители p и q, сгенерированные случайно для разных ключей, начинают повторяться. Причём благодаря парадоксу дней рождения, повторяться они начинают намного раньше, чем думает большинство людей.
Проблема в том, что RSA математически очень уязвима к таким повторам. Достаточно иметь два открытых ключа pq и ps, с совпадающим множителем p, и тогда путём нехитрых манипуляций (алгоритм Евклида) можно будет извлечь p, а вслед за ним q и s. Итог: оба публичных ключа факторизованы. Можно читать PGP-почту, прослушивать/подменять https-трафик и подделывать электронную цифровую подпись.
Сегодня был опубликован препринт статьи, авторы которой собрали коллекцию из 7 миллионов публичных RSA-ключей и путём вычисления общего сомножителя в каждой паре* публичных ключей смогли факторизовать 0.4% из них.
http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars
Дело в том, что заметная потеря энтропии происходит при переходе от псевдослучайных байт к псевдослучайным большим простым числам.
Предположим, мы используем генератор случайных чисел, имеющий 1024 миллиарда возможных состояний (40-битная энтропия). Предположим мы генерируем им выборку 512-битных целых чисел, которые мы затем тестируем на простоту (просеиваем). Вероятность этих целых чисел быть простыми составляет примерно 1/ln(2512), или около 1/354. Так что у нас будет примерно 3 миллиарда разных простых чисел на выходе из этого генератора.
Ключ состоит из двух простых чисел, так что два ключа имеют 4 возможных комбинации множителей, которые могут совпасть. Таким образом, вероятность, что два RSA-ключа "испортят друг друга" наличием общего множителя равна примерно 1 на 750 миллионов.
Если у нас в общем пуле есть 7 млн RSA-ключей, то это они образуют 7млн*7млн/2 пар, из которых каждая 750-миллионная пара окажется "дефективной". Всего таких пар найдётся около 32.7 тысяч, и они испортят 65.3 тыс ключей или 0.92% от общего количества.
На практике вышло чуть меньше, но того же порядка. Это значит только, что не у всех такие плохие генераторы ПСЧ с низкой энтропией.
Авторы нашумевшей статьи пишут:
Almost all of the vulnerable keys were generated by and are used to secure embedded hardware devices such as routers and firewalls, not to secure popular web sites such as your bank or email provider. Only one of the factorable SSL keys was signed by a trusted certificate authority and it has already expired.
https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs
Действительно, аппаратные роутеры и файерволлы — то такое, было бы куда печальнее, если бы один из факторизованных ключей оказался в SSL trusted root. 40-битный seed идёт вразрез с рекомендациями NIST, кто его всё равно использует на свой страх и риск — ССЗБ (Сам Себе Злобный Буратино).
В целом и в общем, теория идеально согласуется с практикой. Говённая реализация => Парадокс дней рождения и потеря энтропии на просеве простых чисел => Безопасность псу под хвост.
Подобная история со слабой энтропией ГПСЧ была в 2001 году, когда хакеры взломали систему защиты программ от реверс-инжинеринга, ASProtect, и выслали автору Алексею Солодовникову на e-mail генератор ключей к ASProtect. подробнее см. книгу "Защита информации" Д.Склярова, стр 83
* На самом деле, можно чуть быстрее, чем в каждой паре
См. также об источниках энтропии в ПК: http://waqur.livejournal.com/421109.html
