Реальный случай взлома RSA

[vitus_wagner]

http://www.theregister.co.uk/2009/09/23/texas_instruments_calculator_hacking/
Любители, желающие установить альтернативную ОС на калькуляторы Texas Instruments оказались
способными взломать методом грубой силы секретные ключи RSA, которыми подписаны родные прошивки.
Правда, там ключи были всего лишь 512 битные. Но взлом 512-битный RSA уже по силам просто группе волонтеров, не то что какой-нибудь спецслужбе. Честно сказать, не помню какая сейчас оценка скорости факторизации в зависимости от размера числа, но похоже 1024-битные ключи уже по зубам тем, кто не слишком стеснен в средствах.

RSA RIP.

Comments

[andrzejn]

А какие алгоритмы шифрования с открытым ключом сейчас считаются ещё достаточно надёжными?

[vitus_wagner]

Никакие. Алгоритм шифрования с открытым ключом существует ровно один - RSA.

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

[amarao-san.livejournal.com]

Т.е. прощай PKI, прощай вся современная криптография от кербероса до SSL?

[avysk]

А как же Эль-Гамаль? :-)))

[silly_sad.livejournal.com]

лукавите.
нет ГОСТОВ это не значит что нет алгоритмов.
если можно сделать подпись то можно сделать и шифрование.

[phd_ru]

Эль-Гамаль? Эллиптические кривые? В английской википедии ещё несколько менее известных перечислено.

[edo-rus.livejournal.com]

это либо алгоритмы электронной подписи, не позволяющие при проверке подписи восстановить (расшифровать) исходный хэш

можно расшифровать?

[lightjedi.livejournal.com]

Ну, не ровно один. МакЭлис есть еще, к примеру. Ключ только большой очень.

[temporalescha.livejournal.com]

А Эль-Гамаль что, не шифрование??? Эльгамаль предложил И шифрование, И подпись. Есть еще Рабина, например, доказанно сводимое к факторизации (в отличие от RSA). Странное какое-то безапелляционное и неверное утверждение.

[dil.livejournal.com]

ну вот, дожили, уже на калькуляторы стали ставить альтернативные ОС..

[alll]

Дожили уже давно, ещё когда из начинки для калькуляторов стали делать универсальные компьютеры. Первые микропрцессоры Интел сварганила как раз для калькуляторов, емнип.

The project that produced the 4004 originated in 1969, when Busicom, a Japanese calculator manufacturer, asked Intel to build a chipset for high-performance desktop calculators. Busicom's original design called for a dozen different logic and memory chips. Ted Hoff, the Intel engineer assigned to the project, believed the design was not cost effective. His solution was to simplify the design and produce a programmable processor capable of creating a set of complex special-purpose calculator chips. Together with Masatoshi Shima and Federico Faggin, later the founder of Zilog, Hoff came up with a four-chip design; a ROM for custom application programs, a RAM for processing data, an I/O device, and an unnamed 4-bit central processing unit which would become known as a "microprocessor."
http://en.wikipedia.org/wiki/Microprocessor#History

[dil.livejournal.com]

ну тут всё-таки ROM..

[alll]

Да, закон Мура сильно подкузьмил. Оно конешно, трудоёмкость вскрытия зависит экспоненциально от длинны ключа, ну так и возможности вычислителей последние несколько десятков лет растут более-менее экспоненциально.

[vitus_wagner]

Насколько я помню, там достигнуты хорошие результаты по части сокращения перебора. Даже для дискретного логарифмирвоания уже вместо корня квадратного оценка приближается к кубическому корню из величины основания,
а для факторизации - ещё лучшие результаты достигнуты.

[avryabov.livejournal.com]

вроде как экспонента от корня кубического от длинны ключа, если я правильно понял.
http://ru.wikipedia.org/wiki/RSA

[avryabov.livejournal.com]

Почему именно RIP?
Мало 1024? удвоим, и еще раз удвоим.
Он конечно не по степени двойки растет, но тоже не плохо.

[vitus_wagner]

Потому что закопать давно пора. Есть нормальные алгоритмы.

[ilya-portnov.livejournal.com]

Да, кстати, как я понимаю, DES/3DES RIP давно и надёжно?

[temporalescha.livejournal.com]

3DES к обсуждаемой проблеме не имеет никакого отношения, это симметричный алгоритм. DES, конечно, RIP, а тройной пока еще поживет.

[exception13.livejournal.com]

на ЛОРе уже пофлеймили и постановили что был не брутфорс а т.н. "просев"

[temporalescha.livejournal.com]

"Просев" - это один из алгоритмов решета (лучший на сегодняшний день для чисел длиннее примерно тех же 512 бит - алгоритм обобщенного решета числового поля). Брутфорс понимался именно так, шифр взломан путем решения задачи факторизации.

[karpion.livejournal.com]

Интересно, где там зашита проверка электронной подписи? В ПЗУ, которое можно заменить? Или прямо в процессоре/чипсете?

[beldmit.livejournal.com]

Убей там спаммера...

[http://users.livejournal.com/__sergio__/]

1) В английской википедии про dh, написано, что shared secret делается из своего прайвета и чужого паблика. http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange#Description
То есть на сколько я понял, в качестве a, b, p, и q используются открытые и закрытые ключи.
Но если это так, то надёжность hd не выше надёжности rsa. Очевидно википедия нагло врёт ( или я чего-то не понимаю ), и в нормальном случае используются a и b не связанные с p и q.
Но, может всё-таки кто-то для dh использует rsa ключи, если да, то кто?

2) Ещё про hd написано, что канал связи должен быть защищён от подмены. При этом было бы логично не надется на это, а подписывать всё что нужно. В реальном мире так и происходит?

3) На сколько мне известно, Эль-Гамаль использует только gpg, а все остальные rsa.

4) Заодно будет очень интересно узнать, почему только openvpn хочет отдельного файла с DH parameters?

5)
>А схема шифрования Эль-Гамаля - дырявая обертка вокруг схемы Диффи-Хеллмана, и про неё лучше >забыть, а для шифрования случайного сессионного ключа на общем ключе Диффи-Хеллмана использовать >нормальный симметричный алгоритм.
>Как, кстати, и делают все кроме GPG.

А как делает GPG?

[dottedmag.livejournal.com]

JFYI: http://brainhub.googlepages.com/draft-jivsov-openpgp-ecc-03.html

Медленно, правда, но обсуждение в ietf-openpgp идёт.