You wrote on Wed, Feb 16, 2005 at 08:03:11AM +0000: Не совсем "взломали". Скорее, "нашли два ключа с равными значениями функции".
Показали, что можно найти ключ со значением, равным данному, за 2^69 операций, что уже в пределах commercially feasible (хоть и не мгновенно), если нужно подделать подпись под важным документом итп.
как я понимаю, это они weak collision (2nd preimage) нашли, а не strong collision: дан x - plaintext и H(x), за 2**69 они могут найти y plaintext такой, что H(y) = H(x)
strong collision - найти любые x и y такие, что H(x) = H(y)
Это-то понятно. Честная функция и т.п. Вопрос не в том, какая математика лежит в основе криптографии. Вопрос - почему тот факт, что кто-то может подобрать ключи, важен для Sladshot'а? Ведь это - типовая ситуация как я понимаю? Т.е. в каждый момент времени какая-то защита взламывается, какая-то взламывается успешно, для какой-то фомки ставится усовершенствованная защита и т.п. Т.е. это уже целая отрасль такая. И вот я и прошу, как человек извне, объяснить мне отраслевую значимость данного конкретного случая.
Ну нахождение абы каких коллизий может само по себе и не так важно, но от него и до подделки подписи может быть недалеко.
Например, пакеты в лунуксах подписываются MD5. А злоумышленник, скажем, может трояна запустить под видом хорошего пакета с нужной подписью.
Или в банках, где используются цифровые подписи (а значит и необратимые хэш-функции), можно будет некую инстанцию попросить подписать один документ, а потом подменить его на другой с тем же значением хэша. И подпись будет валидной. О последствиях подобной возможности можно долго фантазировать ;-)
Это _первый_ случай взлома данного конкретного замка, простоявшего довольно долго. Есть некоторый класс замков, не очень широкий, в пределах двух десятков типов (наверное?), которые считаются невзламываемыми на протяжении уже лет 10, и на них много чего основано.
Ситуация как раз совсем не типовая. Есть две распространенные хэш-функции: SHA и MD5. MD5 недавно сломали (во всяком случае показали, что при определенных условиях она имеет слабость). Теперь и SHA.
Хэш-функции - это одни из самых базисных криптографических алгоритмов, на основе которых строятся уже собственно схемы защиты. И они используются практически везде (правда эта новая проблема с SHA затрагивает не все области криптографии, а "только" то, что связано с сертификатами и эл.подписями).
Одним словом, когда пишут, что что-то взломали, то обычно имеется ввиду нечто более высокого уровня. Или какой-нибудь алгоритм кодирования с определенной длинной ключа.
В любом случае, это не конец света, но новость достаточно неприятная.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2005-02-16 08:03 am (UTC)no subject
Date: 2005-02-16 08:06 am (UTC)Показали, что можно найти ключ со значением, равным данному, за 2^69 операций, что уже в пределах commercially feasible (хоть и не мгновенно), если нужно подделать подпись под важным документом итп.
no subject
Date: 2005-02-16 08:10 am (UTC)collisions - это два ключа с равными значениями.
no subject
Date: 2005-02-16 08:11 am (UTC)no subject
Date: 2005-02-16 08:14 am (UTC)no subject
Date: 2005-02-16 12:09 pm (UTC)дан x - plaintext и H(x), за 2**69 они могут найти y plaintext такой, что H(y) = H(x)
strong collision - найти любые x и y такие, что H(x) = H(y)
http://www.cacr.math.uwaterloo.ca/hac/ (chapter 9)
так что страшно, но пока еще не очень. интересно, какие альтернативы следует использовать из свободно циркулирующих
no subject
Date: 2005-02-18 01:37 am (UTC)no subject
Date: 2005-02-16 08:14 am (UTC)MD4 rullz
Date: 2005-02-16 08:20 am (UTC)Re: MD4 rullz
Date: 2005-02-16 08:43 am (UTC)С добрым утром.
no subject
Date: 2005-02-16 08:29 am (UTC)no subject
Date: 2005-02-16 09:23 am (UTC)no subject
Date: 2005-02-16 09:30 am (UTC)Вопрос не в том, какая математика лежит в основе криптографии.
Вопрос - почему тот факт, что кто-то может подобрать ключи, важен для Sladshot'а? Ведь это - типовая ситуация как я понимаю? Т.е. в каждый момент времени какая-то защита взламывается, какая-то взламывается успешно, для какой-то фомки ставится усовершенствованная защита и т.п. Т.е. это уже целая отрасль такая. И вот я и прошу, как человек извне, объяснить мне отраслевую значимость данного конкретного случая.
no subject
Date: 2005-02-16 09:38 am (UTC)Например, пакеты в лунуксах подписываются MD5. А злоумышленник, скажем, может трояна запустить под видом хорошего пакета с нужной подписью.
Или в банках, где используются цифровые подписи (а значит и необратимые хэш-функции), можно будет некую инстанцию попросить подписать один документ, а потом подменить его на другой с тем же значением хэша. И подпись будет валидной. О последствиях подобной возможности можно долго фантазировать ;-)
no subject
Date: 2005-02-16 07:39 pm (UTC)no subject
Date: 2005-02-17 08:18 am (UTC)no subject
Date: 2005-02-16 07:51 pm (UTC)Хэш-функции - это одни из самых базисных криптографических алгоритмов, на основе которых строятся уже собственно схемы защиты. И они используются практически везде (правда эта новая проблема с SHA затрагивает не все области криптографии, а "только" то, что связано с сертификатами и эл.подписями).
Одним словом, когда пишут, что что-то взломали, то обычно имеется ввиду нечто более высокого уровня. Или какой-нибудь алгоритм кодирования с определенной длинной ключа.
В любом случае, это не конец света, но новость достаточно неприятная.
no subject
Date: 2005-02-17 08:19 am (UTC)no subject
Date: 2005-02-16 09:03 am (UTC)no subject
Date: 2005-02-16 09:05 am (UTC)спасибо