Quote from: ZeroTheGreat on January 30, 2014, 01:19:35 AM

Но ведь мало найти коллизию, надо ещё определить какого она рода и насколько опасна?

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

Quote from: ZeroTheGreat on January 30, 2014, 01:19:35 AM

А если сообщения с одинаковым хэшем вообще никак аналитически не стыкуются, то это будет значить, что коллизия безопасна, так?

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

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

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

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

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

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

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