» Вероятность одинакового CRC32

Кто-нить может ответить на сей вопрос с точки зрения сего алгоритма?

Возможно ли совпадение CRC у 2-х разных фалов одинаковой длинны?

MeGaBrAiN
Всего 4 миллиарда возможных комбинаций. Конечно есть вероятность, но маленькая.
Хотя есть алгоритмы - как подогнать CRC

CRC - слабый алгоритм, не защищенный от совпадений (collision-proof) и не рекомендуемый в криптосистемах.

UncoNNecteD
у меня где-то валяютца 2 файла, на которых md5 дает одинаковый hash
так что с hashами все не так просто и вероятность вовсе не обратно пропорциональна размеру hashа. а учитывая что crc32 можно и подобрать влет...

redp
Где-то в интернете была назначена награда в 10 тыс. первому человеку или группе, которая взломает md5.
Пока вроде бы не получается.

dremon
Уже есть в инете публичный сервак который ломает md5 за пару суток.
Правда пока только латиницу+цифры.

dremon
в том то и прикол что специально те файлы не подбирались - коллизия хеша в чистом виде

более конкретно о задаче..

в моей подписи сайт который занимается коллекционирование видео-материала (конкретно Mpeg4, DVD). Встал вопрос идентификации видео-файлов.. Сами понимаете, что расчет CRC32 и(или) MD5 для 700М занятие утомительное, а уж про считывание непосредственно с ЦД вообще гимор ( у меня вот 3500 тыщи фильмов и прочитать полностью каждый диск я уже не в состоянии ).. Поэтому я беру из середины файла 50 метров и считаю по ним CRC и хэш.. чтобы потом другие люди могли проделать тоже самое и получить из общей базы идентификацию файла..

В связи с этим делом и встал вопрос о вероятности совпадения.. Может есть иные варианты?

Не совсем в тему, но...(может не отругают)

Цитата:

Поэтому я беру из середины файла 50 метров и считаю по ним CRC и хэш.. чтобы потом другие люди могли проделать тоже самое и получить из общей базы идентификацию файла..

По моему не очень хороший способ идентификации. А ну как видеоматериал один и тот же, но сжато разными кодеками и с разным разрешением. Битики то разные будут, а материал один и тот же.

SashKa


Цитата:

По моему не очень хороший способ идентификации. А ну как видеоматериал один и тот же, но сжато разными кодеками и с разным разрешением. Битики то разные будут, а материал один и тот же.

все правильно.. номинально каждый из таких видеофайлов относится к одному фильму.. а сами файлы разные.. например версия одного комрада или другого.. разные кодеки, разные параметры видео и тд и тп.. задача узнать не какой ФИЛЬМ, а что за НОСИТЕЛЬ, откуда взят и какое у него качество.. попутно решается проблема дублей и одинаковых фильмов среди коллекционеров

Вроде как есть 64-битная версия CRC.
Почеши инет на эту тему.

ИМХО вопрос поставлен в корне не правильно, если вспомнить о том, для чего применяется обычно CRC, а именно, для проверки (обычно архиваторами) не искаженности файла,
Цитата:

Возможно ли совпадение CRC у 2-х разных фалов одинаковой длинны?

так что ЦРЦ вполне может совпасть и я не вижу причины, почему он не может, а вот хэш это совсем другое дело, вот он по своей сути не должен совпадать, так как принцип формирования хэш (его алгоритм) и само определение хэш-функции исключают эту возможность. При этом 50 метров это ИМХО много.

Цитата:

у меня где-то валяютца 2 файла, на которых md5 дает одинаковый hash

не мог бы ты дать эти файлы и чем ты находил этот ХЭШ (или ЦРЦ) ты точно не ошибся насчет термина ведь это разные вещи по сути.

ShIvADeSt

Цитата:

Что такое хэш-функция (hash, hash-function)?

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

Хэш функция обладает помимо прочих следующими свойствами:

Цитата:

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

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

Цитата:

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

Цитата:

A hash function is a function that converts an input from a (typically) large domain into an output in a (typically) smaller range (the hash value, often a subset of the integers). Hash functions vary in the domain of their inputs and the range of their outputs and in how patterns and similarities of input data affect output data. Hash functions are used in hash tables, cryptography and data processing. A good hash function is one that experiences few hash collisions in the expected domain of strings it will have to deal with; i.e. it would be possible to uniquely identify most of these strings using this hash.

в кратце написано то, что хорошая хэ-функция позволяет единтсвенным образом определить строку по ее хэшу. То есть (а именно об этом спрашивал автор тоника) опр. длине участка битов соответсвует единсвенно хэш-значени. А вот насчет ЦРЦ это не верно, так как я еще раз говорю, что ЦРЦ предназначен для проверки целостности данных, а хэш для подлинности. Ведь я думаю никто из вас не скажет, что при проверке пароля сверяется его ЦРЦ код

Добавлено
Хотя, щас прочитал еще в одном месте, да в самом деле если множество значений функции гораздо меньше множества определения, то есть возможность совпадения результатов, но

Цитата:

Поэтому я беру из середины файла 50 метров и считаю по ним CRC и хэш.. чтобы потом другие люди могли проделать тоже самое и получить из общей базы идентификацию файла..

тое сть согласовать длину участка файла и длину хэша, то можно добиться уникальных значений. То есть сделать длину хэша побольше

собстна я еще и MD5 использую.. если предположить что вероятность совпадения MD5 один на миллион, то уже можно использовать этот алгоритм для идентификации.. я прав?

Цитата:

обстна я еще и MD5 использую.. если предположить что вероятность совпадения MD5 один на миллион, то уже можно использовать этот алгоритм для идентификации.. я прав?

Да.

ShIvADeSt
На самом деле все просто, если длина данных 64 бита, а хэша 32, то значений данных в 2^32 больше. Соотвественно на каждое значение хэша приходится 2^32 значений исходных данных. И ничего с этим не поделаешь

Добавлено
Кстати 50Мб действительно дохрена... таким образом вероятность одинакового CRC только возрастает.

UncoNNecteD


Цитата:

Кстати 50Мб действительно дохрена... таким образом вероятность одинакового CRC только возрастает.

ну а сколько тогда?

MeGaBrAiN

Цитата:

Кстати 50Мб действительно дохрена... таким образом вероятность одинакового CRC только возрастает.

В такой логике при уменьшении размера этого куска вероятность бы падала и становилась бы минимальной для одного байта. Да нет, конечно, не изменяется вероятность. Она зависит только от числа дисков и от числа уникальных значений. Поэтому crc32 плюс md5 лучше чем просто crc32. Хочешь подстраховаться -- считай еще какую-нибудь хэш-функцию. Или бери два куска и считай для каждого из них crc32 и md5. Вот только 50Мб это действительно перебор, imho хватит и килобайта. Ведь данные на диске -- это результат работы кодека, поэтому они и так уже хорошо перемешаны и практически случайны (если, конечно, они взяты с середины диска). В принципе, можно было бы вообще взять четыре байта по фиксированному смещению и назвать их хэшем.

Shy

4 байта мало... можно на индекс авишника попасть.. я решил для постраховки 512 КБ брать из центра

Две хэш функции - дело хорошее.
Вероятность падает во много раз

Цитата:

В такой логике при уменьшении размера этого куска вероятность бы падала и становилась бы минимальной для одного байта.

Нет, до 32 бит - то есть до 4х байт. В принципе - так оно и есть, на 4х байтах данных вероятность совпадения CRC32 минимальна

У меня другой вопрос по CRC.

Например, есть некая фамилия, имя и дата рождения. Например, Pupkin Vasisualiy, 03/18/1979. Из этих данных и формируем строку 'PupkinVasisualiy03/18/1979'. Вычисляем
CRC16, получаем четыре цифры, храним их в базе. Теперь, собственно, вопрос. Какова вероятность, что попадется другая фамилия, имя и дата рождения (включая даже "невозможные" в жизни варианты даты рождения 99/99/9999 или такие фамилии/имена как PuPkiNvAsiSuALiY), что мы "нарвемся" на коллизию? Вариантов входных строк - 1 миллион. Есть какая-то формула, по которой можно было бы такую вероятность вычислить? Для строк одинаковой длины? Разной длины с максимальной длиной такой-то? Или, другими словами, нужно число коллизий на 1 миллион входных данных.

daru
элементарно - 2 в 16 степени
что гораздо меньше чем 1 миллион входных данных

Вероятность совпадения - у 15% записей.
(1000000/(2^16)=15.258).

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

daru
CRC от этого не зависит.

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

ueban
CRC само по себе имеет разрядность. И соответственно количество значений в базисе.
Так что дели на любое число - вариантов больше не станет.

ShIvADeSt писал
>так что ЦРЦ вполне может совпасть и я не вижу причины, почему он не может, а вот хэш >?это совсем другое дело, вот он по своей сути не должен совпадать, так как принцип >формирования хэш (его алгоритм) и само определение хэш-функции исключают эту >возможность.
Почему это исключает? Просто вероятность совпадения соотносится как длины
2**(CRC/YourHash).

А вот идея насчет двух CRC (например 32 и 16 разрядной) -хороша.
Поскольку фактически мы делим число на два простых делителя (а полиномы
выбирают именно так) и вероятность совпадения двух остатков существенно ниже.
А если использовать табличные или иные бысрые методы обсчёта, то скорость
будет хорошей.
Могу показать хороший метод для CRC16 на полиноме 0XA001 (код для x86).
Реализация - моя.
function CRCb(CRC:word;sym:Byte): word;
asm {DL-sym,AL-loCRC,AH,hiCRC}
XOR DH,DH
XOR AL,DL //sym xor LoCRC
JP @ll1
MOV DH,$C0
XOR AH,$01
@ll1:
MOV DL,AH
MOV AH,AL
XOR AL,AL
RCR AX,1
XOR DX,AX
RCR AX,1
XOR AX,DX
end;

basilevs

Следует исходить из ЦЕЛИ создания/выбора алгоритма CRC: обнаружение ошибок/изменений СЛУЧАЙНОГО характера при передаче по каналам (извините за тавтологию) передачи данных. И такие случайные изменения этот алгоритм ловит замечательно. Правда остаётся (как в известной поговорке) тот самый дьявол, что кроется в подробностях. В данном случае - те самые коллизии (совпадающие CRC-суммы от разных проверяемых блоков данных). Для CRC16 - вероятность 2**16. В случае применения двух разных CRC16 вероятности снова "нарваться" на коллизию будет равна (2**16)*(2**16)=2**32. Чистая математика. Что эквивалентно использованию одной CRC32. Вплоть до времени расчета CRC-сумм, если у вас конечно программы подсчёта CRC правильные (без наворотов из-за горе-программиста).
Как говорил герой одной рекламы: "Отсюда вывод". Будете Вы брать 50 Mbyte, 50 Kbyte, 1 Kbyte, 0.5 Kbyte или 50 byte; из середины, из конца или начала файла (только не из самого начала или конца - чтобы не попасть на стандартный дескриптор полей/файла); будете брать байты подрят, через один или задом наперёд; CRC16 + CRC16 или CRC32; CRC16 + CRC32 или CRC48 - алгоритму ВСЁ РАВНО. Такими трюками вы можете "запутать" только программиста, но не программу(алгоритм). Ей это всё (простите за солдафонство) - монопенисуально.


Добавлено:
daru

Увы (или наоборот), но алгоритм CRC не является позиционным, то есть при обработке сообщения не учитывается положение содержащихся в нём байт. И также не учитывается положение бит в байте. Поэтому использование определённых правил написания имени и даты приводят лишь к тому, что некоторые биты в идентификаторе будут предопрелены и их значения зафискированы. Это плохо. Но оставшиеся "переменными" биты будут по прежнему влиять и менять итоговое значение CRC. Это хорошо. В итоге - если число "переменных" бит будет больше разрядности CRC, то это полностью компенсирует наличие предопределённых бит, сведёт их влияние практически к нулю. Рассмотрим дату dd/mm/yy. Для каждой цифры мы имеем три "переменных" бита, таких цифр шесть, итого 3*6=18 бит. Для адгоритма CRC16 - этого хватит с головой. Прикинем для CRC32: нужно ещё 14...16 "переменных" бит. Для каждой буквы имеем минимум 4 таких бита (ведь у нас больше 2**4=16 разных букв ?). Значит, если под имя отвести больше 16/4=4 символов, то влияние НЕСЛУЧАЙНОСТИ букв в имени и цифр в дате будет нивелировано. Видите, как просто. Согласитесь, это даже не математика. Это просто арифметика.