md5 -- чо опять не так?

Любые обсуждения, не нарушающие правил форума.

Модератор: Модераторы

md5 -- чо опять не так?

Сообщение azsx » 06.03.2018 12:19:55

(md5 сумма) - не является уникальным id

Допустим надо сохранить 10 млн главных (чистый хтмл) в БД. Как известно, очень много полных совпадений, то есть сайты разные отдают одинаковый хтмл код. Будем считать: 1. Страница менее двух кбайт нам не интересна, также не нужны страницы более 100 мбайт; 2. Страница нужна только с инфорамционно значимым текстом (не белый шум). Просто первый контроль на полное совпадение.
Чем всё таки плох md5? Это хорошо отработанный алгоритм, достаточно экономный по ресурсам. Не согласны?
azsx
энтузиаст
 
Сообщения: 959
Зарегистрирован: 16.11.2015 06:38:32

Re: md5 -- чо опять не так?

Сообщение serbod » 06.03.2018 12:38:34

Он не гарантирует уникальность результата. Но можно сделать так - если md5 совпал, а исходные файлы различаются, то малость подкорректировать один из исходных файлов - добавить пробел или перевод строки, чтобы его md5 изменился.
Аватара пользователя
serbod
постоялец
 
Сообщения: 449
Зарегистрирован: 16.09.2016 11:03:02
Откуда: Минск

Re: md5 -- чо опять не так?

Сообщение azsx » 06.03.2018 12:43:02

Он не гарантирует уникальность результата.

Вот что это значит? Гарантирует только оригинал, ну сжатие без потерь. Все остальные алгоритмы вычисления хеша ничего не гарантируют. Что Вам гарантирует sha512?
azsx
энтузиаст
 
Сообщения: 959
Зарегистрирован: 16.11.2015 06:38:32

Re: md5 -- чо опять не так?

Сообщение runewalsh » 06.03.2018 12:58:48

Коллизии на обычных данных, т. е. не предложенных злоумышленником, можно считать невозможными (вероятность коллизии меньше вероятности, что бит в регистре сам флипнется и испортит результат сравнения хэшей, каким бы ни был исходный алгоритм), но MD5 взломан и для него существует алгоритм *построения* коллизий. Если тебя это не волнует, или от такой атаки твоя система не пострадает, используй на здоровье.
Последний раз редактировалось runewalsh 06.03.2018 13:09:36, всего редактировалось 1 раз.
Аватара пользователя
runewalsh
энтузиаст
 
Сообщения: 578
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение olegy123 » 06.03.2018 13:09:16

azsx писал(а):Чем всё таки плох md5? Это хорошо отработанный алгоритм, достаточно экономный по ресурсам. Не согласны?

Ничем, если нужны скорости - то md5 более оптимальный в решении.. Он компактен. 16 байт на ресурс.
olegy123
долгожитель
 
Сообщения: 1643
Зарегистрирован: 25.02.2016 12:10:20

Re: md5 -- чо опять не так?

Сообщение azsx » 06.03.2018 13:09:20

sha-1 также взломан. _ttps://habrahabr.ru/post/322478/
Как раз оперативная память бывает, что сбоит, я читал про такие случаи.
Вопрос в другом. Если Вам критично важно получить именно оригинал, то использовать никакие хеши нельзя в принципе. Если Вам это не важно и вы не считаете "радужные таблицы" на "биткоинах" то по сути md5 более чем надёжный алгоритм для любых задач. Он по сути уже избыточен.
Это не так?
olegy123 спасибо, но я именно разобраться хочу.
azsx
энтузиаст
 
Сообщения: 959
Зарегистрирован: 16.11.2015 06:38:32

Re: md5 -- чо опять не так?

Сообщение olegy123 » 06.03.2018 13:13:41

serbod писал(а):Он не гарантирует уникальность результата.

в некоторых решениях не нужна уникальность. Вполне MD5 достаточно.
MD% плох тем, что подбор комбинаций возможен(и он не уникальный) в рамках мощного компьютера. В задаче не ставится защищенность, нужен как контроль "четности".
Поэтому даже CRC32 будет достаточно.
olegy123
долгожитель
 
Сообщения: 1643
Зарегистрирован: 25.02.2016 12:10:20

Re: md5 -- чо опять не так?

Сообщение azsx » 06.03.2018 13:18:15

В задаче не ставится защищенность, нужен как контроль "четности"?

да, только контроль чётности.
Но допустим мне была бы необходима "защищённость". Есть какие то цифры какой тип sha будет более стойким, чем md5 и в каких вероятностях выражаются возможные коллизии при 2 кбайтов разумного текста, например? Или как это подсчитать?
Пишу наверное не понятно.
Вот почему на АЭС на критический участок алгоритм md5 нельзя, а sha-1 можно? По мне так если нельзя -- так только сравнение оригиналов.
Последний раз редактировалось azsx 06.03.2018 13:19:27, всего редактировалось 1 раз.
azsx
энтузиаст
 
Сообщения: 959
Зарегистрирован: 16.11.2015 06:38:32

Re: md5 -- чо опять не так?

Сообщение serbod » 06.03.2018 13:18:55

В данной задаче md5 используется как первичный ключ в таблице. И хотя вероятность коллизии стремится к нулю, дополнительная проверка бы не помешала, хотя бы по размеру исходных данных.
Аватара пользователя
serbod
постоялец
 
Сообщения: 449
Зарегистрирован: 16.09.2016 11:03:02
Откуда: Минск

Re: md5 -- чо опять не так?

Сообщение azsx » 06.03.2018 13:21:28

Добавил при "2 кбайтов разумного текста, например?"
Нет, это не первичный ключ, это именно проверка на уникальность. Да включить второй и более алгоритма вычисления хеша (например, md5 и sha-1 считать) -- это круто. Но зачем?
azsx
энтузиаст
 
Сообщения: 959
Зарегистрирован: 16.11.2015 06:38:32

Re: md5 -- чо опять не так?

Сообщение olegy123 » 06.03.2018 13:21:49

azsx писал(а):Вот что это значит? Гарантирует только оригинал, ну сжатие без потерь. Все остальные алгоритмы вычисления хеша ничего не гарантируют. Что Вам гарантирует sha512?

не путайте хеширование с остальными вещами (шифрация,сжатием и т.п.)
shaХ, MD5, crc32 - все они вам дадут тест на уникальность данных.

В задачи нужно соблюсти баланс - между размером БД и данными на единицу ресурса. Предпочтительно sha256, но там 64байт, MD5 - 8байт.. crc32 - 4 байт..
4 байт легче в работе, в поиске. больше операций за 1 ресурс уйдет в shaХ.

Добавлено спустя 2 минуты 33 секунды:
azsx писал(а):Но допустим мне была бы необходима "защищённость".

защищенность в хешах не ищите.. они дают только тест на уникальность данных..
Да, можно пароли закрыть ими, но обратное открытие ими не предусмотрено.

Добавлено спустя 13 минут 3 секунды:
azsx писал(а):это именно проверка на уникальность. Да включить второй и более алгоритма вычисления хеша (например, md5 и sha-1 считать) -- это круто. Но зачем?

https://ru.wikipedia.org/wiki/%D0%A6%D0 ... 0%BE%D0%B4
Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.

т.е. правильнее называть хеш-функции "Помехоустойчивое кодирование". Контроль данных и т.п.

кстати, crc32 в некоторых процессорах исполняется аппаратно. Скорость вычисления будет максимальная.
olegy123
долгожитель
 
Сообщения: 1643
Зарегистрирован: 25.02.2016 12:10:20

Re: md5 -- чо опять не так?

Сообщение azsx » 06.03.2018 13:59:47

в задаче соблюдения баланса вы принципиально не можете гарантировать, что sha-512 никогда не будет иметь коллизий. Шанс мизерный, но есть.
azsx
энтузиаст
 
Сообщения: 959
Зарегистрирован: 16.11.2015 06:38:32

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 06.03.2018 14:16:59

azsx писал(а):Вот почему на АЭС на критический участок алгоритм md5 нельзя, а sha-1 можно?

sha - тоже нельзя пользовать в качестве уникального индекса.
azsx писал(а):в задаче соблюдения баланса вы принципиально не можете гарантировать, что sha-512 никогда не будет иметь коллизий. Шанс мизерный, но есть.

serbod - предложил, очень хороший вариант, использовать двойной индекс добавив длину в байтах.

Соответственно, наиболее идеальный вариант звучит так:
Делаете в базе три колонки:
    1) md5,
    2) sha
    3) указываете длину в байтах.
И только при совпадении всех трёх значений, считаете индекс уникальным. Соответственно, вероятность совпадения практически будет равна нолю, или совпадение сможет вычислить только очень великий математик с помощью очень большого PC. И в любом случае, совпадений будет БЕЗУСЛОВНО много, но их содержимое вряд-ли будет человеческим текстом (в смысле у 99,9(9)% из sha*md*size возможных вариантов - совпадение маловероятно). Как следствие, только спец. диверсия, позволит продублировать индекс.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение Mirage » 07.03.2018 03:09:02

Интересно, что тут может дать длина в байтах? Вероятности не умеем сравнивать вообще? Ну помножишь ты вероятность совпадения длины в байтах на 2 в минус 128-ой. Получишь значение малоотличимое от 2 в минус 128-ой.
А нулевую вероятность совпадения и побайтовое сравнение не даст. Задание - подумать почему.
Вообще абстрактно говорить бессмысленно. Надо от конкретной задачи отталкиваться. Для некоторых и бита четности хватит. :)
Mirage
энтузиаст
 
Сообщения: 881
Зарегистрирован: 06.05.2005 20:29:07
Откуда: Russia

Re: md5 -- чо опять не так?

Сообщение azsx » 07.03.2018 06:11:54

Mirage, спасибо, вы окончательно собрали мои мысли в кучку (прям как преподаватель). Вероятность коллизии на реальных данных от килобайтов и выше для md5 настолько мала, что её можно пренебречь (юзать md5 как id). В тех случаях, когда в результате коллизии погибнут люди и возможна ситуация, что целые исследовательские институты будут искать уязвимости в моей системе никакое применение хеша как уникального ключа не оправдано. Вот поиск ошибок в памяти или алгоритме сравнения, то есть сравнить два оригинала и ещё и сравнить хеш -- это оправдано.
Правда мои слова отвергает биткоин и торрент, но в теории я прав. Верно?
А нулевую вероятность совпадения и побайтовое сравнение не даст. Задание - подумать почему.

Вот тут я ничо не понял.
----
vitaly_l , способ сравнить двумя и выше алгоритмами на самом деле плох. Допустим, страница 50 мбайт. Вы 1) посчитать хеш для sha512; 2) а можете sha128 и md5. Совсем не факт, что второе событие менее вероятно, но зато оно значительно более ресурсоёмкое.
azsx
энтузиаст
 
Сообщения: 959
Зарегистрирован: 16.11.2015 06:38:32

След.

Вернуться в Потрепаться

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 14

Рейтинг@Mail.ru