Total Commander Forum Index Total Commander
Форум поддержки пользователей Total Commander
Сайты: Все о Total Commander | Totalcmd.net | Ghisler.com | RU.TCKB
 
 RulesRules   SearchSearch   FAQFAQ   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Уникальность crc32 для файлов
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Total Commander Forum Index -> Программное обеспечение printer-friendly view
View previous topic :: View next topic  
Author Message
Batya



Joined: 15 Dec 2004
Posts: 2218
Location: Москва, Россия

Post (Separately) Posted: Thu Jun 11, 2009 15:17    Post subject: Уникальность crc32 для файлов Reply with quote

Подскажите, знающие люди, насколько crc32 для каждого файла уникальна?
Насколько можно по совпадению crc32 судить о совпадении содержимого у 2-х разных файлов?
_________________
Нет, я не сплю. Я просто медленно моргаю.
Back to top
View user's profile Send private message
CaptainFlint



Joined: 14 Dec 2004
Posts: 6151
Location: Москва

Post (Separately) Posted: Thu Jun 11, 2009 15:21    Post subject: Reply with quote

Как и для любого хэша: гарантий никаких быть не может (по принципу Дирихле).
Кроме этого, CRC32 ещё и не является криптостойким, т.е. если захотеть, можно поправить содержимое файла для получения любого заранее выбранного значения хэша.
_________________
Почему же, ё-моё, ты нигде не пишешь "ё"?
Back to top
View user's profile Send private message
Worros



Joined: 19 Jan 2007
Posts: 1123

Post (Separately) Posted: Thu Jun 11, 2009 19:52    Post subject: Reply with quote

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

Из моего собственного опыта: то, о чем говорит CaptainFlint, подгонка crc32, делается в частности для образов майкрософтовских дисков, т.о. отличить например установочные диски разных билдов одной операционки по crc32 заведомо невозможно(речь идет об оригинальных MSDNовских, всякие зверьсиди и прочие поделки в рассмотрение не берутся).
_________________
педофилия, каннибализм, бетономешалка !!!
Back to top
View user's profile Send private message
CaptainFlint



Joined: 14 Dec 2004
Posts: 6151
Location: Москва

Post (Separately) Posted: Thu Jun 11, 2009 19:57    Post subject: Reply with quote

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

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

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

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

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

Федора уже SHA256 вовсю пользуется. Вчера только рыл инет в поисках утилиты для проверки. Smile
_________________
Почему же, ё-моё, ты нигде не пишешь "ё"?
Back to top
View user's profile Send private message
Batya



Joined: 15 Dec 2004
Posts: 2218
Location: Москва, Россия

Post (Separately) Posted: Thu Jun 11, 2009 23:22    Post subject: Reply with quote

ОК.
Тогда можно ли однозначно утверждать об идентичности содержимого файлов при сопадении md5?
_________________
Нет, я не сплю. Я просто медленно моргаю.
Back to top
View user's profile Send private message
Worros



Joined: 19 Jan 2007
Posts: 1123

Post (Separately) Posted: Thu Jun 11, 2009 23:28    Post subject: Reply with quote

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

_________________
педофилия, каннибализм, бетономешалка !!!
Back to top
View user's profile Send private message
Tol!k



Joined: 01 Apr 2008
Posts: 1727
Location: Арзамас

Post (Separately) Posted: Fri Jun 12, 2009 00:49    Post subject: Re: Уникальность crc32 для файлов Reply with quote

Batya wrote:
Подскажите, знающие люди, насколько crc32 для каждого файла уникальна?
Насколько можно по совпадению crc32 судить о совпадении содержимого у 2-х разных файлов?
Для бытовых применений CRC32 вполне достаточно. Ну кому нужно подделывать контрольную сумму одной фотки на вашем компе, чтобы она совпала с контрольной суммой другой фотки? Вероятность пропустить изменение данных — 1 на 2^32 (~4,3 млн.)
CRC32 используется, например, в WinRARe.
Back to top
View user's profile Send private message
Batya



Joined: 15 Dec 2004
Posts: 2218
Location: Москва, Россия

Post (Separately) Posted: Fri Jun 12, 2009 01:10    Post subject: Reply with quote

CaptainFlint, Worros, Tol!k
Спасибо за информацию!
_________________
Нет, я не сплю. Я просто медленно моргаю.
Back to top
View user's profile Send private message
Worros



Joined: 19 Jan 2007
Posts: 1123

Post (Separately) Posted: Fri Jun 12, 2009 01:16    Post subject: Reply with quote

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

Изменение - да. Но мы говорим не об изменении. Речь идёт о применении crc32 не для верификации файлов, а для установления факта уникальности. И здесь далеко не так всё радужно. Пример с образами дисков выше уже приводился. Batya нигде не оговаривает, что собирается ограничиться "одной фоткой на компе".
Вероятность возникновения коллизии при взятии пары произвольных файлов и изменении одного - совершенно не одно и то же.
_________________
педофилия, каннибализм, бетономешалка !!!
Back to top
View user's profile Send private message
Kent



Joined: 14 Dec 2004
Posts: 208

Post (Separately) Posted: Fri Jun 12, 2009 02:25    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
Tol!k



Joined: 01 Apr 2008
Posts: 1727
Location: Арзамас

Post (Separately) Posted: Fri Jun 12, 2009 07:52    Post subject: Reply with quote

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



Joined: 15 Dec 2004
Posts: 2218
Location: Москва, Россия

Post (Separately) Posted: Fri Jun 12, 2009 12:53    Post subject: Reply with quote

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

Это, разумеется, понятно. Просто в теме "автоматическое удаление файлов по датам создания" пишу скрипт, в котором надо отобрать дубликаты файлов. Думаю, что через сравнение содержимого файлов скрипт будет очень долго работать. Для текущей задачи считаю достаточным идентификацию по хэшу. Вопрос был относительно надёжности данного подхода. Наверное, всё-таки лучше передать скрипт под md5.
_________________
Нет, я не сплю. Я просто медленно моргаю.
Back to top
View user's profile Send private message
Volniy



Joined: 15 Dec 2004
Posts: 585
Location: Местный

Post (Separately) Posted: Fri Jun 12, 2009 23:57    Post subject: Reply with quote

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


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

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

Кстати, сравнение по содержимому нужно начинать со сравнения размеров файлов. Размеры не одинаковы - нефиг вообще сравнивать файлы, они безусловно неодинаковы.
Back to top
View user's profile Send private message
DrShark



Joined: 21 Oct 2006
Posts: 911
Location: Kyiv, Ukraine

Post (Separately) Posted: Sat Jun 13, 2009 01:00    Post subject: Reply with quote

В связи с недавней найденной уязвимостью в sha1, я спрашивал Гислера о возможности внедрения создания контрольных сумм sha256 для файлов. Гислер ответил, что, по крайней мере, в финальную версию 7.50 добавлять не будет по причине недостаточного, по его мнению, быстродействия хэширования. Хотя в компоненте менеджера паролей Тотала SHA256 своё применение уже нашёл.
Back to top
View user's profile Send private message
Batya



Joined: 15 Dec 2004
Posts: 2218
Location: Москва, Россия

Post (Separately) Posted: Sat Jun 13, 2009 02:03    Post subject: Reply with quote

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

Да, но есть один нюанс - как определить группу дубликатов? Мне что-то в голову не лезет нормальных вариантов выделения дубликатов при сравнении по содержимому. Что-то мне подсказывает, что при таком подходе надо будет значительное число раз читать одни и те же файлы. (Предположим, что размеры файлов совпадают.)
Есть идеи алгоритма?
_________________
Нет, я не сплю. Я просто медленно моргаю.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Total Commander Forum Index -> Программное обеспечение All times are GMT + 4 Hours
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group