LINUX.ORG.RU

Уменьшение криптостойкости в алгоритме хэширования SHA-1

 ,


0

0

Исследователями из университета Макуори(Сидней) был найден новый способ взлома алгоритма хэширования SHA-1, который позволяет значительно сократить количество попыток при переборе -- с 2^63 до 2^52. Это означает, что взлом становится практически выгодным для финансово обеспеченных организаций.

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

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

Подробный анализ уязвимости(PDF): http://eprint.iacr.org/2009/259.pdf

>>> Подробности



Проверено: Shaman007 ()

Вот блин. Только недавно (в новости про уязвимость md5 ЕМНИП) говорили что sha1 охренительно надёжен, вот тут нашли уязвимость.

ptah_alexs ★★★★★
()
Ответ на: комментарий от ptah_alexs

> говорили что sha1 охренительно надёжен, вот тут нашли уязвимость.

Это НЕ уязвимость, просто SHA1 оказался не настолько стоек, как надеялись.

Надеюсь, модеры поправят заголовок.

tailgunner ★★★★★
()

>значительно сократить количество попыток при переборе -- с 2^63 до 2^52

количество возможных вариантов сократилось в 2048 раз и теперь составляет всего каких-то четыре с половиной тысячи триллионов - теперь взломать любой SHA-1 хэш - раз плюнуть! Отличная новость. ;)

jcd ★★★★★
()
Ответ на: комментарий от isden

Если судить по аватарам - то здесь сборище забубенных мутантов 8)))

V0ID ★★★
()

Кстати, SHA-1 с конца 2010 года более не будет стандартом США, госорганизациям предписано не считать подлинными электронные подписи, сделанные с использованием SHA-1.

Ну и Debian с аналогичными решениями уже подтянулся :) http://www.debian-administration.org/users/dkg/weblog/48

really_localhost
()

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

alt0v14 ★★★
()
Ответ на: комментарий от tailgunner

> Это НЕ уязвимость, просто SHA1 оказался не настолько стоек, как надеялись. Надеюсь, модеры поправят заголовок.

In academic cryptography, any attack that has less computational complexity than a brute force search is considered a break. This does not, however, necessarily mean that the attack can be practically exploited.

И кстати да, его именно продолжают ломать. Bruteforce=1/2^80, предыдущий рекорд 1/2^63, теперь уже 1/2^52. Когда уже доломают до 1/2^45 ?

www_linux_org_ru ★★★★★
()

> Это означает, что взлом становится практически выгодным для финансово обеспеченных организаций.

Все эти алгоритмы обычно очень просты в железной реализации, и полагаю недорогой FPGA какой-нить запросто может искать коллизии в 10^5 раз быстрее компа.

www_linux_org_ru ★★★★★
()
Ответ на: комментарий от Slackware_user

> Ждем массовый переход на Sha512

Никогда! Только tiger, только победа. Долой nsa-шное дерьмецо.

ubber
()
Ответ на: комментарий от www_linux_org_ru

>> Это НЕ уязвимость, просто SHA1 оказался не настолько стоек, как надеялись. Надеюсь, модеры поправят заголовок.

> In academic cryptography, any attack that has less computational complexity than a brute force search is considered a break.

И? Где здесь слово "vulnerability"?

tailgunner ★★★★★
()
Ответ на: комментарий от really_localhost

>Ну и Debian с аналогичными решениями уже подтянулся :)

Да... Debian... - это рекурсивное решето. Опять они чего-нибудь где-нибудь закомментировали в коде...

X-Pilot ★★★★★
()

чо за баяннновость?

давноже уже говорили про эти 2^52 в SHA-1...

... и даже говорили про то что в госудасрве-США приказали уже как два года назад -- поменять все SHA-1 на SHA-2 (SHA-256, SHA-512, ...)

новость БАЯН.. странно что ктото ещё не знает об этом......

mkfifo
()
Ответ на: комментарий от mkfifo

> новость БАЯН..

Ссылку?

> странно что ктото ещё не знает об этом......

Вроде статья о взломе еще не peer reviewed, а публикация была в среду.

tailgunner ★★★★★
()
Ответ на: комментарий от mkfifo

> http://it.slashdot.org/article.pl?sid=09/05/08/1429225&from=rss

Полтора месяца - это не баян еще, особенно, если не следить за специализированными криптоизданиями.

И кстати... http://csrc.nist.gov/groups/ST/hash/statement.html:

> Federal agencies must stop relying on digital signatures that are generated using SHA-1 by the end of 2010.

что несколько противоречит:

> даже говорили про то что в госудасрве-США приказали уже как два года назад -- поменять все SHA-1 на SHA-2

tailgunner ★★★★★
()
Ответ на: комментарий от mkfifo

> .. и даже говорили про то что в госудасрве-США приказали уже как два года назад -- поменять все SHA-1 на SHA-2

"Приказали" - два года назад, а "поменять" - до конца 2010 года. Вполне прагматичный подход по выведению из продакшена потенциально ненадёжного алгоритма.

really_localhost
()
Ответ на: комментарий от X-Pilot

> Опять они чего-нибудь где-нибудь закомментировали в коде...

В GnuPG - вряд ли. Он в отличие от OpenSSL написан руками с активным применением головы.

really_localhost
()
Ответ на: комментарий от tailgunner

> "Взлом", естественно.

Тогда надо писать "взломан алгоритм", а по русски это не очень звучит.

www_linux_org_ru ★★★★★
()
Ответ на: комментарий от really_localhost

> В GnuPG - вряд ли. Он в отличие от OpenSSL написан руками с активным применением головы.

В GnuPG был *тоже* эпик фейл (и куча мелких).

Phong Nguyen identified a severe bug in the way GnuPG creates and uses ElGamal keys for signing. This is a significant security failure which can lead to a compromise of almost all ElGamal keys used for signing. This update disables the use of this type of key.

P.S. это было во всех дистрах, не только в дебиане.

www_linux_org_ru ★★★★★
()
Ответ на: комментарий от www_linux_org_ru

Если, конечно, мелкими можно назвать баги, когда сообщение вообще без подписи нормально верифицируется.

www_linux_org_ru ★★★★★
()

На серверах с установочными образами Fedora все контрольные суммы уже виде SHA256.

Jayrome ★★★★★
()
Ответ на: комментарий от tailgunner

>> как ты предлагаешь перевести break?

> "Взлом", естественно.

скорее `прорыв', в данном контексте

beastie ★★★★★
()
Ответ на: комментарий от www_linux_org_ru

> P.S. это было во всех дистрах, не только в дебиане.

Только вот никто этими ключами не пользовался - это была чисто gnupg-шная реализация фичи, ещё не вошедшей в формат. Кстати, так и не вошедшей потом.

really_localhost
()
Ответ на: комментарий от Sylvia

>всего лишь в сто миллиардов раз менее стоек )
откуда тровишки?

impfp
()
Ответ на: комментарий от piroflip

Есть Whirlpool, принят международным стандартом в ISO.

feanor ★★★
()

а еще монетка подброшенная в вверх может зависнуть в воздухе, вероятность этого тоже есть 2^N

fAngel
()
Ответ на: комментарий от alt0v14

>имеет ли смысл в таком случае подписывать данные двумя разными алгоритмами?

По идее можно и одним но со сдвигом. То есть в первом случае хешь считается с нуля до конца а во втором скажем с середины до середины

DNA_Seq ★★☆☆☆
()
Ответ на: комментарий от tailgunner

Да, не уязвимость, позволяющая поиметь пользователя алгоритма на раз-два. Но, заметь, это снижение стойкости сделало поиск коллизий вполне реальным, приносящим профит. То есть, оно может считаться критическим.

gotf
() автор топика
Ответ на: комментарий от alt0v14

>>имеет ли смысл в таком случае подписывать данные двумя разными алгоритмами?

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

gotf
() автор топика
Ответ на: комментарий от AnDoR

> А как поживают sha256 и иже с ними? Или там тот же самый алгоритм?

Базовая схема примерно такая же. Но аналогичных атак _пока_ не придумано. Остается только надеяться, что атаки в случае их появления не станут практически осуществимыми ввиду экстенсивных причин :)

really_localhost
()
Ответ на: комментарий от fAngel

> а еще монетка подброшенная в вверх может зависнуть в воздухе, вероятность этого тоже есть 2^N

На ЛОРе, похоже, уже появилось и свое собственное вероятностное пространство. Не иначе это последствия неверного применения машины времени.

really_localhost
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.