Вот и конец MD5

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

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

hmac-ripemd160 + blowfish спасут отца русской демократии.

> Кстати, создать валидный архив с тем же ключом будет посложнее, чем просто набор символов -- не любой мусор корректно распакуется.

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

> Но как можно md5 заменить на blowfish ?

Как в NetBSD

Миш, в 9.2 blowfish уже идет по умолчанию.

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

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

>Если я правильно понимаю, то теперь вместо "методом прямого перебора" можно "за 8 часов на 1.6GHz компьютере". А если это будет гораздо более мощный комп...

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

А как в слаке переползти на blowfish в shadow?

> Разницы между сверкой контрольных сумм и проверки ЭЦП вроде бы нету.

Есть. Помимо всего прочего, ЭЦП призвана удостоверять источник. Если A передал B свой публичный ключ по trusted каналу, то потом он может спокойно передавать данные и ЭЦП по untrusted каналу. Хэш же всего-лишь удостоверяет, что данные не побились при передаче. Не более того. Если злоумышленник ломанёт сайт, то наряду с данными он может фальсифицировать и хэш. И никаких коллизий искть не надо.

по ходу надо менять login, passwd... ?

> по ходу надо менять login, passwd... ?

Это ты про что?

это про переход на blowfish например... вообщем на другой алгоритм как перейти?

> Неверно. Если сумма длин хэшей меньше, длины исходного числа (файла), то коллизия будет обязательно.

Верно в том случае, если хеши "плохие": например, если первому соответствуют X1, X2 и X3, а второму - X1, X4, X5 и X6. Замечу, что в этом случае комбинация хеша обратима.

Пример "случайно обратимого" хеша - сумма цифр числа, такая, что при переполнении НЕ получается 0. Тогда хеш-сумма 0 будет получаться только для нуля.

http://www.antsight.com/zsl/rainbowcrack/

кстати говоря

> Верно в том случае, если хеши "плохие"

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

> При этом сам он уже давно не был криптостойким алгоритмом.

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

> Мляха, реально десктопу однопользовательскому угроза есть?

Врятли.

> Или все это касается серверов?

Смотря каких. Вон, на phpBB пароли в MD5 хранятся. Вспоминаем, что не давно была волна взломов с возможным вытягиванием баз. Кто там пароли не сменил? Ждите сообщений под своим именем... ;-)))

>Хм... А почему бы не использовать несколько признаков для контроля: размер, md5, crcXX, ну и скажем md5 от каждого второго символа? Это возведет сложность задачи в квадрат, грубо говоря.

>Т.е. строка s="эту строку нельзя подделать" сопровождается числами md5(s), 27, crc(s) и md5("эусрк еьяпдаь").

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

Конечно, на первых этапах это тормознёт народ. (В основном script kiddies), но потом... Простейший вариант: начинаем поиск коллизий по crc (что гораздо проще!) и уже их скармливаем md5...

>>Если я правильно понимаю, то теперь вместо "методом прямого перебора" можно "за 8 часов на 1.6GHz компьютере". А если это будет гораздо более мощный комп...

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

Не совсем понятно что значит "нет". За сравнительно короткое время, не брутефорсить, перебирая все возможные комбинации, можно подобрать некий пароль, хэш которого будет выглядеть точно так же, как и в shadow. Я не смогу зайти с этим паролем?

>> Мляха, реально десктопу однопользовательскому угроза есть?
>Врятли.
Есть, если для проверки файлов программ, входящих в дистрибутив, используется MD5.

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

Поясню ещё раз, я говорил о подписывании _уже известного_ открытого текста (скажем, архива), а не о паролях и т.п.

Т.е. злоумышленник может взять текст, проделать все что я тут понаписал, начать подбор с crc и...упростить себе работу?! Это как?!

Хуже такая схема точно не делает (т.к. никакой новой инфы нет), другое дело, что она дает повод для еще одной диссертации "поиск коллизий для двух хэшей одновременно", и соответствующей новости на ЛОР лет так через пять.

Если бы можно было "выписать все коллизии в crc и потом их скормить md5", то его бы так и подбирали с самого начала.

>> Разницы между сверкой контрольных сумм и проверки ЭЦП вроде бы нету.

> Есть. Помимо всего прочего, ЭЦП призвана удостоверять источник. Если A передал B свой публичный ключ по trusted каналу, то потом он может спокойно передавать данные и ЭЦП по untrusted каналу. Хэш же всего-лишь удостоверяет, что данные не побились при передаче. Не более того. Если злоумышленник ломанёт сайт, то наряду с данными он может фальсифицировать и хэш. И никаких коллизий искть не надо.

Для случая использования контрольной суммы мы проверяем равенство hash(x)==hash(x').

Для случая же использования ЭЦП (ЭЦП=priv_key(hash(x))) мы проверяем, что pub_key(ЭЦП)==hash(x'), а т.к. pub_key(priv_key(z))==z, то мы проверяем всё то же равенство hash(x)==hash(x').

Стойкость преобразований pub_key и priv_key - это отдельная история, о которой сейчас речь не идёт.

и какая это угроза?

> и какая это угроза?

Очевидно, это угроза получить поддельный файл с тем же MD5 и установить его себе на компьютер. Получить файл можно как от друга, так и с вскрытого основного сайта проекта или зеркала.

> мы проверяем всё то же равенство hash(x)==hash(x').

Мы ещё проверяем, что подписано было именно тем priv_key, которым нужно. Достоверность такой проверки зависит от криптостойкости алгоритма и секретности priv_key.

Скажем так, если у меня есть возможность злонамеренно заменить некоторое файло вместе с контрольной информацией, то если контрольная информация - просто хэш, то мне не нужно больше ничего для введения получателей информации в заблуждение. Если же информация _подписана_, то я не могу правильно подписать свою злонамеренную информацию, не узнав priv_key, а это уже совсем другая песня.

> Поясню ещё раз, я говорил о подписывании _уже известного_ открытого текста (скажем, архива), а не о паролях и т.п.

Тогда да, но это не фатально усложняет. В итоге вместо часов будут максимиу недели...

> Если бы можно было "выписать все коллизии в crc и потом их скормить md5", то его бы так и подбирали с самого начала.

Так crc не используется. Имеется ввиду ситуация, когда пароль или что-то хешируемое сохраняется как _два_ значения. Тогда ежу понятно, что сначала ищутся коллизии для лёгкой функции, а потом уже кормится тяжёлая... ;-)

> Мы ещё проверяем, что подписано было именно тем priv_key, которым нужно. Достоверность такой проверки зависит от криптостойкости алгоритма и секретности priv_key.

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

> AFAIK электронной подписью подписывается хэш.

На самом деле, если передаётся шифрованный контент от A к B, то вместо передачи pub_key_b(data) и подписи, можно передавать pub_key_b(priv_key_a(data)). Тогда подпись будет встроена в сам документ :)

> AFAIK электронной подписью подписывается хэш

Ага, понял... :) Мы говорим о разных вещах. Всё началось с того, что кто-то тут заявил, что хэш и ЭЦП - суть одно и то же, хотя это не так. Да, хэш-функции применяются в ЭЦП как составная часть, но это далеко не единственная, и даже наверно, не основная составляющая.

> Найтен способ нахождения коллизии...

Все так перепугались, что до сих пор не заметили эстонский акцент у сабжа :)

watashiwa_daredeska, ты не понимаешь.

Если мы сумеем найти поддельный файл x' такой, что hash(x)==hash(x'), то ЭЦП для файла x будет совпадать с ЭЦП для файла x'.

Т.е. можно подменить файл x на x' даже без знания priv_key.

> Всё началось с того, что кто-то тут заявил, что хэш и ЭЦП - суть одно и то же, хотя это не так. Да, хэш-функции применяются в ЭЦП как составная часть, но это далеко не единственная, и даже наверно, не основная составляющая.

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

>ну хватит народ пугать. из хеша ты никаким боком не сможешь восстановить оригинальные данные! в случае хеша мы имеем иньективное отображение.

Ну и? Я говорил, что если имеешь доступ к /etc/shadow, то скорее всего и на запись (потому что чтение для world запрещено так же как и запись), в таком случае стираем пароль рута (предварительно его записываем где-то), логинимся рутом, устанавливаем руткит (новый login мылит мне на бесплатный почтовик введённые пароли, если они совпадают с хешем) и возвращаем прежний пароль на рута. Аналогично делается и с зашифрованным файлом/разделом харда.

>зы. у вас дискретка когда?

По понедельникам и по средам с 10:30 до 12:10.

bunzip2: some.bz2: trailing garbage after EOF ignored

>Миш, в 9.2 blowfish уже идет по умолчанию.

Ты читать умеешь? Я это и написал.

Блин, что-то тут много криков насчёт возможности подбора пароля за 8 часов. Чё тупим, народ, в статье же ясно сказано, что можно подобрать текс, дающий такой же хэш, как ИЗВЕСТНЫЙ текст с известным хэшем. А в случае пароля мы знаем только ХЭШ, а самого пароля НЕ ЗНАЕМ. Так что насчёт паролей в shadow париться не стоит. Да и насчёт паролей, хранящихся в базах данных, тоже. Всё упирается лишь в подписывание файлов с известным содержимым на предмет установления подлинности этого содержимого.

Все равно пароль менять не буду [8P

> Чё тупим, народ, в статье же ясно сказано, что можно подобрать текс, дающий такой же хэш, как ИЗВЕСТНЫЙ текст с известным хэшем.

Ты не там ударение поставил. Должно быть так:

"Чё тупим, народ, в статье же ясно сказано, что можно подобрать текс, дающий ЗАДАННЫЙ ХЭШ".

> А в случае пароля мы знаем только ХЭШ, а самого пароля НЕ ЗНАЕМ. Так что насчёт паролей в shadow париться не стоит.

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

>Перед тем, как перестать беспокоиться насчет shadow, нужно определиться, что опасней: чтобы подобрали именно наш пароль, или любой с совпадающим хешем (с таким паролем в систему можно зайти на тех же правах). :)

У всех нормальных людей право на чтение /etc/shadow закрыто так же как и на запись.

>Очевидно, это угроза получить поддельный файл с тем же MD5 и установить его себе на компьютер. Получить файл можно как от друга, так и с вскрытого основного сайта проекта или зеркала.

то есть, достаточно не обмениватся критичными пакетами с "друзьями" (или лишние файлы проверять иным способом) и подключатся для скачивания исключительно к проверенному зеркалу? Ну вот в случае с джентой, получается чтобы не обломатся, достаточно устанавливать "--fetchonly" и выжидать пару дней, смотря новости по сайту насчет взломов. Или?

> Или?

Веревку мылить! Если серьезно, надо ждать пока всякие yum, apt и т.п. переползут на что-нить более стойкое и забрав эти пакеты из надежного источника обновить все остальное...

Появилось стойкое желание матюкнуцца. Ибо только сегодня утром мне принесли десктопину, на которую я думал поставить дистр через сеть. Терь чета даже страшновато, ХЗ с какого зеркала все повытягивает. Ладно, бум вручную зеркало выставлять. Или может отмиррорить у себя на хард файлы? Тока там жешь туева хуча гигабайт..

Прошу извинения, - действительно, насчет shadow (и вообще, паролей, хранящихся в виде хешей) можно не беспокоиться по причине, указанной YOjick.

>Появилось стойкое желание матюкнуцца. Ибо только сегодня утром мне принесли десктопину, на которую я думал поставить дистр через сеть. Терь чета даже страшновато, ХЗ с какого зеркала все повытягивает. Ладно, бум вручную зеркало выставлять. Или может отмиррорить у себя на хард файлы? Тока там жешь туева хуча гигабайт..

Не трахай лучше себе мозги - я так понимаю, что у тебя на том компе не находятся данные государственной важности. Не факт, что даже оригинальные программы (в том числе от M$) не содержат spyware - или ты думаешь, что можно просмотреть весь исходный код (тем более, если он не доступен/доступен не всем) на его отсутствие? Если бы что-то такое обнаружилось, тогда бы и стоило отказываться от использования. Вся индустрия действует на доверии авторам и посредникам.

>Прошу извинения, - действительно, насчет shadow (и вообще, паролей, хранящихся в виде хешей) можно не беспокоиться по причине, указанной YOjick.

Начнём с того, что при авторизации соответствие хеша оригинального пароля хешу введённого пароля проверяется _сервером_, соответственно клиент не знает хеша оригинального пароля. Естественно, при отсутствии других уязвимостей.

mikhail, разговор идет о ситуации, когда клиент знает хеш.

>mikhail, разговор идет о ситуации, когда клиент знает хеш.

Откуда? Это является уязвимостью. Клиенту хеш знать не нужно.

> Откуда?

Неважно.

> Это является уязвимостью. Клиенту хеш знать не нужно.

Однако, даже если он и знает хеш, получить пароль он не сможет. Вы согласны с тем, что это хорошо? Я - да.