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

through

[^/[Print]\]
Goto page 1, 2 Next :| |:
Total Commander -> Программное обеспечение

#1: Уникальность crc32 для файлов Author: Batya, Location: Москва, Россия

Posted: Thu Jun 11, 2009 15:17
—
Подскажите, знающие люди, насколько crc32 для каждого файла уникальна?
Насколько можно по совпадению crc32 судить о совпадении содержимого у 2-х разных файлов?

#2: Author: CaptainFlint, Location: Москва

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

#3: Author: Worros,

Posted: Thu Jun 11, 2009 19:52
—
Неспроста весь *nix-мир пользуется для этих целей исключительно md5 , хотя через некоторое время нам улыбается переход уже на sha1.

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

#4: Author: CaptainFlint, Location: Москва

Posted: Thu Jun 11, 2009 19:57
—

Worros wrote:

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

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

Worros wrote:

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

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

Worros wrote:

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

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

#5: Author: Batya, Location: Москва, Россия

Posted: Thu Jun 11, 2009 23:22
—
ОК.
Тогда можно ли однозначно утверждать об идентичности содержимого файлов при сопадении md5?

#6: Author: Worros,

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

CaptainFlint wrote:

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

#7: Re: Уникальность crc32 для файлов Author: Tol!k, Location: Арзамас

Posted: Fri Jun 12, 2009 00:49
—

Batya wrote:

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

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

#8: Author: Batya, Location: Москва, Россия

Posted: Fri Jun 12, 2009 01:10
—
CaptainFlint, Worros, Tol!k
Спасибо за информацию!

#9: Author: Worros,

Posted: Fri Jun 12, 2009 01:16
—
Tol!k

Tol!k wrote:

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

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

#10: Author: Kent,

Posted: Fri Jun 12, 2009 02:25
—

Worros wrote:

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

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

#11: Author: Tol!k, Location: Арзамас

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

#12: Author: Batya, Location: Москва, Россия

Posted: Fri Jun 12, 2009 12:53
—

Tol!k wrote:

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

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

#13: Author: Volniy, Location: Местный

Posted: Fri Jun 12, 2009 23:57
—

Batya wrote:

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

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

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

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

#14: Author: DrShark, Location: Kyiv, Ukraine

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

#15: Author: Batya, Location: Москва, Россия

Posted: Sat Jun 13, 2009 02:03
—

Volniy wrote:

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

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

Total Commander -> Программное обеспечение

output generated using printer-friendly topic mod. All times are GMT + 4 Hours

Goto page 1, 2 Next :| |: Page 1 of 2