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

Volniy · Сообщение **Volniy** » Сб июн 13, 2009 07:06

Хорошее решение - доверить все это дело Тотал Командеру. Вроде неплохо это у него получается

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

Tol!k · Сообщение **Tol!k** » Вс июн 14, 2009 21:57

Batya писал(а):Есть идеи алгоритма?

Если файлы разного размера — они не равны.
Если 2 файла одного размера — сравниваем по содержимому.
Если 3 и более файлов одного размера — вычисляем простой и быстрый хеш (например CRC16) и сравниваем хеши. Если хеши не равны, то не равны и файлы. Если хеши равны — сравниваем файлы по содержимому.

Volniy писал(а):Кстати, только что подсмотрел, как это реализовано у Гислера.

Где (или как)? Тоже любопытно.

Tol!k писал(а):Если 3 и более файлов одного размера — вычисляем простой и быстрый хеш (например CRC16) и сравниваем хеши. Если хеши не равны, то не равны и файлы. Если хеши равны — сравниваем файлы по содержимому.

Любой хэш, какой бы быстрый он ни был, требует полного считывания всего содержимого файла. И плюс сравнение по содержимому выполнит полное считывание. Да ещё, не исключено, что не единожды (если файлов несколько). Мне кажется, надо использовать что-то более хитрое. Например, так:
1. Получили полный список файлов.
2. Разбили на группы с одинаковым размером.
3. Внутри каждой группы считываем по блоку длиной N из каждого файла, сравниваем эти блоки попарно.
4. По результатам сравнения разбиваем файлы из текущей группы на подгруппы, внутри которых содержимое всех считанных к данному моменту блоков у всех файлов идентичное.
5. Повторяем шаги 3-4, пока файлы не будут считаны и сравнены полностью.
6. Полученный набор подгрупп и представляет собой разбиение всех файлов на одинаковые по содержимому, причём каждый из файлов в процессе работы был полностью прочитан ровно один раз.

Volniy · Сообщение **Volniy** » Пн июн 15, 2009 01:16

Tol!k, никакого реверсинга, упаси бог! Просто подсунул Тоталу определенный набор файлов и проследил его файловые операции при поиске дубликатов Filemon-ом. Интересовал единственный вопрос: бывают ли повторные чтения содержимого одного и того-же файла. Сие в эскпериментах замечено не было.

Lazy Crazy

Изначально Batya упоминал, что всё это нужно для топика "автоматическое удаление файлов по датам создания", который начинал Neo233 с проблемой идентификации ‘картинок с Web-камеры’ в ‘кэше Internet Explorer`a’. А значит размер файлов относительно небольшой и даже полное сравнение не должно быть проблемой…

Batya · Сообщение **Batya** » Пн июн 15, 2009 16:05

CaptainFlint
Отличная мысль. Надо подумать, можно ли это сделать через vbs.

Lazy Crazy писал(а):А значит размер файлов относительно небольшой и даже полное сравнение не должно быть проблемой…

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

Моторокер

Batya писал(а):при таком подходе надо будет значительное число раз читать одни и те же файлы. (Предположим, что размеры файлов совпадают.)

Если уж файл читаем, почему бы не считать параллельно его сумму? Операции с файлами намного медленней операций в оперативке.

Можно хранить кол-во считанного и нерассчитанную до конца сумму.

alexanderwdark

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

Длина самой хэш суммы здесь только косвенно влияет на надежность и стойкость. Есть определенный минимум, конечно. Скажем, 80-128 бит. Короче - сликом мало вариантов.

Но, сам алгоритм подсчета может быть уязвим для совпадений / коллизий. Сейчас на конкурсе SHA3 уже тьма новых, хороших на первый взгляд, хэшей были отсеяны - хотя и давали на выходе 512 и выше бит (64 байта). Приничой были именно коллизии, а у кого и возможность частично предсказать исходную информацию на основе хэша.

MD5 уже давно сломали, SHA1 так же не надежен. От SHA2 уже отказываются. Скоро уже будет известен SHA3, финалистов уже совсем не много осталось.

Уже можно выделить отличные алгоритмы: Keccak и Skein. Что особенно у них интересно - они гибкие, длина хэша может быть любой, не фиксирована до типовых 128, 256, 384, 512 бит.

Последний заточен под 64-битные системы, поэтому на 32-разрядных ОС довольно медлителен. Keccak в этом плане интереснее, если победит, у нас будет отличный алгоритм для самых различных целей.

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

Хотя и сейчас есть способ: считайте сразу две хэш-суммы. Вероятность подмены / совпадения сразу двух хэшей практически нереальна.

Mite · Сообщение **Mite** » Ср окт 28, 2009 01:58

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

alexanderwdark

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

Вполне, поскольку сумма - циклическая. Ее есть смысл проверять, если размер файла идентичен.

Mite · Сообщение **Mite** » Ср окт 28, 2009 08:54

Batya писал(а):Насколько можно по совпадению crc32 судить о совпадении содержимого у 2-х разных файлов?

Если судить только по совпадению crc32, не сравнивая никакие другие параметры файлов, то этого недостаточно! Необходим хотя бы еще один параметр: или размер, или

alexanderwdark писал(а):считайте сразу две хэш-суммы. Вероятность подмены / совпадения сразу двух хэшей практически нереальна.

basileus

Вставлю лыко в строку.
Любой ХЭШ есть сжатие с потерями.
Представляется наиболее разумным следуюющий подход:
Выбираем некую константу, для размера блока, меньшую сегмента памяти.
Скажем, 4 килобайта.
Все файлы, требующие сравнения, длина которых меньше этого блока,
просто сравниваются друг с другом. (строим дерево, для ускорения сравнения, представляя данные как очень длинное число)
Файлы большей длины обсчитываем быстрой CRC(иной хэш), разбивая на блоки такой длины, чтобы в общая длина всех CRC блоков + CRC всего файла занимали этот блок.
Далее - аналогично маленьким файлам.
Но, еще с одной итерацией.
Если, по Дирихле, в узел дерева (ящик Дирихле), попадёт более одного элемента - проводим полное сравнение файлов.
Чем больше длина блока -тем лучше работает метод.
Расход памяти на посроение деревьев и выделение блоков может быть значительным.
Возможно, имеет делать предварительное построение еще одного дерева по длинам файлов и запускать этот алогритм для каждого узла отдельно.