Можно ли избежать проблемы создания двух сообщений с одинаковой хеш-суммой если к хеш сумме md5 добавить размер хешируемой строки/файла?

Question

[PO6OT]

Можно ли избежать проблемы создания двух сообщений с одинаковой хеш-суммой если к хеш сумме md5 добавить размер хешируемой строки/файла?

Например, могут ли существовать два разных файла/строки, у которых хеш-сумма MD5 и размер одинаковы?

Comments

[Владимир Мартьянов]

В процессе подсчета MD5-суммы в данные подмешивается и длина данных тоже. Скорее всего в SHA1 так же, так что не вижу смысла, все уже подмешано.

Answer 1

[mramor]

Например, могут ли существовать два разных файла/строки, у которых хеш-сумма MD5 и размер одинаковы?

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

Comments

[PO6OT]

ну просто думаю что лучше - перейти на sha256 или просто добавлять к хеш сумме размер файла?

[mramor]

Вадим Егоров: а что понимается под сообщением?

[PO6OT]

mramor: то, из чего получают хеш

[PO6OT]

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

[mramor]

файл - имя файл?
строка - номер строки?
сообщение - содержание строки вплоть до 0xa?

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

[PO6OT]

Задача:

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

Решение: к хеш-сумме добавлять размер файла в байтах в шестнадцатеричном исчислении.

Решение верно?

[PO6OT]

размер файла в байтах в шестнадцатеричном исчислении - шестнадцатеричное число, равное количеству байтов в файле

[mramor]

Вадим Егоров: Решение не верно.

[PO6OT]

mramor: а что тогда делать? допустим из 20 млн. файлов общим весом 2 млн. Gb есть вероятность совпадения?

[mramor]

Вариант, делать загрузку в каталоги типа год/месяц/день/час/минуты/милисекунда/ и там уже дежать его хешем. можно и имя файла держать как (d_m_Y_H_i_s).enc(bin).ascii и уже прилеплять имя файла, т.е. впереди имени будет двоичная маска даты, типа дата_имя(хеш?).ext
Вариантов тонна, чем держать все в одном каталоге с ориентиром на хеш и размер

[mramor]

Вадим Егоров: Вы файлообменник проектируете?

[PO6OT]

mramor: Не только.

[mramor]

Вадим Егоров: Я верно понял, что когда вы имели ввиду "тонны файлов" это было несуществующей проблемой, но с перспективой? :)

[PO6OT]

mramor: Я сделал что-то вроде CMS (на самом деле я не знаю как это называется) и теперь пишу расширения (это я тоже не знаю как правильно называть).
Можете почитать как с ней работать: woonem.tk/readme.txt

Я написал пока что 5 расширений:
system.zip
adwert.zip
holiday.zip
feedback.zip
projects.zip

Разрабатываю:
account.zip
auth.zip
settings.zip
и еще несколько.

Дочерним расширением для расширения Account является Storage. Вопрос относится к нему.

[PO6OT]

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

[mramor]

Вадим Егоров: Тогда могу пожелать только удачной разработки.

Еще идея, подмотренная в одном проекте: перед помещением файла в каталог загрузки проверяется есть ли такой файл, и если есть, то проверяется есть ли файл имя-номер.расширение. и так меняется номер в цикле, пока не дойдет до отсутствия файла, и после помещают под нужным файл-номер

[PO6OT]

mramor: но ведь одинаковые файлы могут иметь разное название

[mramor]

Вадим Егоров: Не понял .

[PO6OT]

mramor: перед помещением файла в каталог загрузки проверяется есть ли такой файл, и если есть, то проверяется есть ли файл имя-номер.расширение - вы имели в виду "перед отправлением файла на сервер, он сопоставляется с каждым или проверяется, есть ли файл с таким-же именем и расширением"? Честно говоря вы не очень понятно обьяснили

[mramor]

Вадим Егоров: допустим , есть файл в каталоге: dump.sql , вы грузите на ресурс файл с точно таким же названием, перед тем как поместить файл в каталог загрузки - он находится как временный где-нибудь в /tmp (это стандартный механизм, путь разве что может быть инным, не суть), вот перед копированием в каталог загрузки вы делаете:
if( file_exists($filename))

Если там уже есть dump.sql , то врубаем цикл есть ли там dump-1.sql, dump-2.sql и тд. если нет dump-N.sql, то сохраняем под именем dump-N.sql

Это не идеальный вариант, но тоже вариант.

[PO6OT]

mramor: это не то, что мне нужно. мне нужно чтоб не повторялись содержания файлов а не их имена.

[PO6OT]

mramor: я бы это и так использовал, если бы понадобилось

[PO6OT]

Оказывается, то что я вам описал называется: lurkmore.to/_/1806#mws_upT1Sjm
(Допустим, я бы не стал вместо цикла писать кучу строк повторяющегося кода в надежде на то, что количество обрабатываемой информации в этом псевдо-цикле не превысит кол-во повторений этого кода. Думаю, вы поняли о чем я.)

Answer 2

[Оптимус Пьян]

Если сообщения одинаковые, то длинна строки и размер файла тоже одинаковые будут? А значит и хеш совпадёт?

Comments

[PO6OT]

у разных сообщений может быть одинаковая хэш-сумма. Разве не знали никогда?

[PO6OT]

а может так случиться, что у этих разных сообщений будет одинаковое количество байтов?