Уникальность crc32 для файлов

[Batya]

Подскажите, знающие люди, насколько crc32 для каждого файла уникальна?
Насколько можно по совпадению crc32 судить о совпадении содержимого у 2-х разных файлов?

[CaptainFlint]

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

[Worros]

Неспроста весь *nix-мир пользуется для этих целей исключительно md5 , хотя через некоторое время нам улыбается переход уже на sha1.

Из моего собственного опыта: то, о чем говорит CaptainFlint, подгонка crc32, делается в частности для образов майкрософтовских дисков, т.о. отличить например установочные диски разных билдов одной операционки по crc32 заведомо невозможно(речь идет об оригинальных MSDNовских, всякие зверьсиди и прочие поделки в рассмотрение не берутся).

[CaptainFlint]

подгонка crc32, делается в частности для образов майкрософтовских дисков

Во-во, я как раз о них думал, когда писал о подгонке.

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

И даже разных операционок.

хотя через некоторое время нам улыбается переход уже на sha1.

Федора уже SHA256 вовсю пользуется. Вчера только рыл инет в поисках утилиты для проверки.

[Batya]

ОК.
Тогда можно ли однозначно утверждать об идентичности содержимого файлов при сопадении md5?

[Worros]

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

Как и для любого хэша: гарантий никаких быть не может (по принципу Дирихле).

[Tol!k]

Подскажите, знающие люди, насколько crc32 для каждого файла уникальна?
Насколько можно по совпадению crc32 судить о совпадении содержимого у 2-х разных файлов?

Для бытовых применений CRC32 вполне достаточно. Ну кому нужно подделывать контрольную сумму одной фотки на вашем компе, чтобы она совпала с контрольной суммой другой фотки? Вероятность пропустить изменение данных — 1 на 2^32 (~4,3 млн.)
CRC32 используется, например, в WinRARe.

[Batya]

CaptainFlint, Worros, Tol!k
Спасибо за информацию!

[Worros]

Tol!k

изменение данных — 1 на 2^32 (~4,3 млн.)

Изменение - да. Но мы говорим не об изменении. Речь идёт о применении crc32 не для верификации файлов, а для установления факта уникальности. И здесь далеко не так всё радужно. Пример с образами дисков выше уже приводился. Batya нигде не оговаривает, что собирается ограничиться "одной фоткой на компе".
Вероятность возникновения коллизии при взятии пары произвольных файлов и изменении одного - совершенно не одно и то же.

[Kent]

Неспроста весь *nix-мир пользуется для этих целей исключительно md5 , хотя через некоторое время нам улыбается переход уже на sha1.

Пользуется по инерции и не везде.
md5 давно уже под сомнением
http://www.opennet.ru/opennews/art.shtml?num=6449
И года полтора назад выкладывали примеры подделки хеша.
sha-1 тоже не внушает доверия
https://www.pgpru.com/novosti/2009/opub ... izijjvsha1
http://www.debian-administration.org/us ... /weblog/48

[Tol!k]

Worros, Kent
А и вправду, вопрос не о порче\подделке файла.
Но вообще не существует алгоритма вычисления хеша, однозначно идентифицирующего файл, если файл длиннее хеша. Ибо количество возможных комбинаций не может превысить 2^[длина хеша в битах]
Я ошипся, для CRC32 это ~4,3 млрд.
Batya, для однозначной идентификации файлов нужно сравнивать их по содержимому. А хеши — это или вынужденная мера (как в пиринговых сетях) или защита от кражи баз с паролями.

[Batya]

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

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

[Volniy]

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

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

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

Кстати, сравнение по содержимому нужно начинать со сравнения размеров файлов. Размеры не одинаковы - нефиг вообще сравнивать файлы, они безусловно неодинаковы.

[DrShark]

В связи с недавней найденной уязвимостью в sha1, я спрашивал Гислера о возможности внедрения создания контрольных сумм sha256 для файлов. Гислер ответил, что, по крайней мере, в финальную версию 7.50 добавлять не будет по причине недостаточного, по его мнению, быстродействия хэширования. Хотя в компоненте менеджера паролей Тотала SHA256 своё применение уже нашёл.

[Batya]

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

Да, но есть один нюанс - как определить группу дубликатов? Мне что-то в голову не лезет нормальных вариантов выделения дубликатов при сравнении по содержимому. Что-то мне подсказывает, что при таком подходе надо будет значительное число раз читать одни и те же файлы. (Предположим, что размеры файлов совпадают.)
Есть идеи алгоритма?