View previous topic :: View next topic |
Author |
Message |
Batya
Joined: 15 Dec 2004 Posts: 2220 Location: Москва, Россия
|
(Separately) Posted: Thu Jun 11, 2009 15:17 Post subject: Уникальность crc32 для файлов |
|
|
Подскажите, знающие люди, насколько crc32 для каждого файла уникальна?
Насколько можно по совпадению crc32 судить о совпадении содержимого у 2-х разных файлов? _________________ Нет, я не сплю. Я просто медленно моргаю. |
|
Back to top |
|
|
CaptainFlint
Joined: 14 Dec 2004 Posts: 6151 Location: Москва
|
(Separately) Posted: Thu Jun 11, 2009 15:21 Post subject: |
|
|
Как и для любого хэша: гарантий никаких быть не может (по принципу Дирихле).
Кроме этого, CRC32 ещё и не является криптостойким, т.е. если захотеть, можно поправить содержимое файла для получения любого заранее выбранного значения хэша. _________________ Почему же, ё-моё, ты нигде не пишешь "ё"? |
|
Back to top |
|
|
Worros
Joined: 19 Jan 2007 Posts: 1123
|
(Separately) Posted: Thu Jun 11, 2009 19:52 Post subject: |
|
|
Неспроста весь *nix-мир пользуется для этих целей исключительно md5 , хотя через некоторое время нам улыбается переход уже на sha1.
Из моего собственного опыта: то, о чем говорит CaptainFlint, подгонка crc32, делается в частности для образов майкрософтовских дисков, т.о. отличить например установочные диски разных билдов одной операционки по crc32 заведомо невозможно(речь идет об оригинальных MSDNовских, всякие зверьсиди и прочие поделки в рассмотрение не берутся). _________________ педофилия, каннибализм, бетономешалка !!! |
|
Back to top |
|
|
CaptainFlint
Joined: 14 Dec 2004 Posts: 6151 Location: Москва
|
(Separately) Posted: Thu Jun 11, 2009 19:57 Post subject: |
|
|
Worros wrote: | подгонка crc32, делается в частности для образов майкрософтовских дисков |
Во-во, я как раз о них думал, когда писал о подгонке.
Worros wrote: | отличить например установочные диски разных билдов одной операционки по crc32 заведомо невозможно |
И даже разных операционок.
Worros wrote: | хотя через некоторое время нам улыбается переход уже на sha1. |
Федора уже SHA256 вовсю пользуется. Вчера только рыл инет в поисках утилиты для проверки. _________________ Почему же, ё-моё, ты нигде не пишешь "ё"? |
|
Back to top |
|
|
Batya
Joined: 15 Dec 2004 Posts: 2220 Location: Москва, Россия
|
(Separately) Posted: Thu Jun 11, 2009 23:22 Post subject: |
|
|
ОК.
Тогда можно ли однозначно утверждать об идентичности содержимого файлов при сопадении md5? _________________ Нет, я не сплю. Я просто медленно моргаю. |
|
Back to top |
|
|
Worros
Joined: 19 Jan 2007 Posts: 1123
|
(Separately) Posted: Thu Jun 11, 2009 23:28 Post subject: |
|
|
С достаточной для нормального (и даже придирчивого) юзера вероятностью - да. Вероятность для sha1 - выше, для sha256 еще выше, но это всё идет в счет времени вычислений. Абсолютной однозначности не может гарантировать никто :
CaptainFlint wrote: | Как и для любого хэша: гарантий никаких быть не может (по принципу Дирихле). |
_________________ педофилия, каннибализм, бетономешалка !!! |
|
Back to top |
|
|
Tol!k
Joined: 01 Apr 2008 Posts: 1727 Location: Арзамас
|
(Separately) Posted: Fri Jun 12, 2009 00:49 Post subject: Re: Уникальность crc32 для файлов |
|
|
Batya wrote: | Подскажите, знающие люди, насколько crc32 для каждого файла уникальна?
Насколько можно по совпадению crc32 судить о совпадении содержимого у 2-х разных файлов? | Для бытовых применений CRC32 вполне достаточно. Ну кому нужно подделывать контрольную сумму одной фотки на вашем компе, чтобы она совпала с контрольной суммой другой фотки? Вероятность пропустить изменение данных — 1 на 2^32 (~4,3 млн.)
CRC32 используется, например, в WinRARe. |
|
Back to top |
|
|
Batya
Joined: 15 Dec 2004 Posts: 2220 Location: Москва, Россия
|
(Separately) Posted: Fri Jun 12, 2009 01:10 Post subject: |
|
|
CaptainFlint, Worros, Tol!k
Спасибо за информацию! _________________ Нет, я не сплю. Я просто медленно моргаю. |
|
Back to top |
|
|
Worros
Joined: 19 Jan 2007 Posts: 1123
|
(Separately) Posted: Fri Jun 12, 2009 01:16 Post subject: |
|
|
Tol!k
Tol!k wrote: | изменение данных — 1 на 2^32 (~4,3 млн.) |
Изменение - да. Но мы говорим не об изменении. Речь идёт о применении crc32 не для верификации файлов, а для установления факта уникальности. И здесь далеко не так всё радужно. Пример с образами дисков выше уже приводился. Batya нигде не оговаривает, что собирается ограничиться "одной фоткой на компе".
Вероятность возникновения коллизии при взятии пары произвольных файлов и изменении одного - совершенно не одно и то же. _________________ педофилия, каннибализм, бетономешалка !!! |
|
Back to top |
|
|
Kent
Joined: 14 Dec 2004 Posts: 208
|
|
Back to top |
|
|
Tol!k
Joined: 01 Apr 2008 Posts: 1727 Location: Арзамас
|
(Separately) Posted: Fri Jun 12, 2009 07:52 Post subject: |
|
|
Worros, Kent
А и вправду, вопрос не о порче\подделке файла.
Но вообще не существует алгоритма вычисления хеша, однозначно идентифицирующего файл, если файл длиннее хеша. Ибо количество возможных комбинаций не может превысить 2^[длина хеша в битах]
Я ошипся, для CRC32 это ~4,3 млрд.
Batya, для однозначной идентификации файлов нужно сравнивать их по содержимому. А хеши — это или вынужденная мера (как в пиринговых сетях) или защита от кражи баз с паролями. |
|
Back to top |
|
|
Batya
Joined: 15 Dec 2004 Posts: 2220 Location: Москва, Россия
|
(Separately) Posted: Fri Jun 12, 2009 12:53 Post subject: |
|
|
Tol!k wrote: | Batya, для однозначной идентификации файлов нужно сравнивать их по содержимому. |
Это, разумеется, понятно. Просто в теме "автоматическое удаление файлов по датам создания" пишу скрипт, в котором надо отобрать дубликаты файлов. Думаю, что через сравнение содержимого файлов скрипт будет очень долго работать. Для текущей задачи считаю достаточным идентификацию по хэшу. Вопрос был относительно надёжности данного подхода. Наверное, всё-таки лучше передать скрипт под md5. _________________ Нет, я не сплю. Я просто медленно моргаю. |
|
Back to top |
|
|
Volniy
Joined: 15 Dec 2004 Posts: 585 Location: Местный
|
(Separately) Posted: Fri Jun 12, 2009 23:57 Post subject: |
|
|
Batya wrote: | Думаю, что через сравнение содержимого файлов скрипт будет очень долго работать. |
Сравнение по содержимому файлов будет быстрее подсчета контрольных сумм этих файлов.
Для подсчета хешей нужно, как минимум прочесть файл полностью, кроме того еще и провести вычисления над считанным содержимым. Сравнение по содержимому требует полного считывания сравниваемых файлов только в случае если они идентичны, во всех других случаях сравнение будет закончено еще до считывания полного содержимого файлов (в принципе сравнение может завершиться уже на первом байте). Кроме того сравнение по содержимому это менее ресурсоемкая операция чем вычисление хэша.
Кстати, сравнение по содержимому нужно начинать со сравнения размеров файлов. Размеры не одинаковы - нефиг вообще сравнивать файлы, они безусловно неодинаковы. |
|
Back to top |
|
|
DrShark
Joined: 21 Oct 2006 Posts: 911 Location: Kyiv, Ukraine
|
(Separately) Posted: Sat Jun 13, 2009 01:00 Post subject: |
|
|
В связи с недавней найденной уязвимостью в sha1, я спрашивал Гислера о возможности внедрения создания контрольных сумм sha256 для файлов. Гислер ответил, что, по крайней мере, в финальную версию 7.50 добавлять не будет по причине недостаточного, по его мнению, быстродействия хэширования. Хотя в компоненте менеджера паролей Тотала SHA256 своё применение уже нашёл. |
|
Back to top |
|
|
Batya
Joined: 15 Dec 2004 Posts: 2220 Location: Москва, Россия
|
(Separately) Posted: Sat Jun 13, 2009 02:03 Post subject: |
|
|
Volniy wrote: | Сравнение по содержимому файлов будет быстрее подсчета контрольных сумм этих файлов. |
Да, но есть один нюанс - как определить группу дубликатов? Мне что-то в голову не лезет нормальных вариантов выделения дубликатов при сравнении по содержимому. Что-то мне подсказывает, что при таком подходе надо будет значительное число раз читать одни и те же файлы. (Предположим, что размеры файлов совпадают.)
Есть идеи алгоритма? _________________ Нет, я не сплю. Я просто медленно моргаю. |
|
Back to top |
|
|
|