Посоветовать алгоритм хэширования

[Alex Aka Parasite]

Приветствую, господа!

Прошу разбирающихся посоветовать алгоритм хэширования под следующую задачу:
1. Сервер
2. Hа нем - проект, писанный на перле + апач для междумордия с пользователем.
3. Там же - БД.
4. Там же, на винте - хранилище контента под проект. Контент представляет из
себя многие и многие *миллионы* мелких бинарных файлов, размером от десятков
байт до десятков килобайт, и их число постоянно растет. Каждый файлик уже
упакован (.bz2).

Требуется: поиметь для каждого файлика хэш, кой и положить в БД в
соответствуюшие контенту ячейки.
1. *Очень критично* отсутствие коллизий (одинакового хэша на разные по составу
файлы). Учитывая количество единиц файлА - такое теоретически возможно...
Hа самый крайний случай возможна комбинация пары значений - например,
хэша+размера файла, но это не так изящно уже...
2. Желательно юзать стандартный общеупотребимый алгоритм(-ы), чтобы не
изобретать велосипеда.
3. Желательно посоветовать быстрые, "нетяжелые" алгоритмы - работа с контентом
идет довольно плотная, в мультиюзер-моде, а перл сам по себе не самый
проворный.

Вот... У кого какие идеи? Всем откликнувшимся - заранее спасибо.

bye, Alex.
... Улыбайтесь - это всех pаздpажает.

[Serguei E. Leontiev]

Здравствуй Alex,

Alex Aka Parasite -> All @ пн 17-авг-09 21:29 MSD:

...
AAP> 4. Там же, на винте - хранилище контента под проект. Контент представляет из
AAP> себя многие и многие *миллионы* мелких бинарных файлов, размером от десятков
AAP> байт до десятков килобайт, и их число постоянно растет. Каждый файлик уже
...
AAP> 1. *Очень критично* отсутствие коллизий (одинакового хэша на разные по составу
AAP> файлы). Учитывая количество единиц файлА - такое теоретически возможно...

Хм. Hе уверен, оценим "растущие миллионы" величиной 2^32, а десятки байт
величиной 80 бит, и тогда вероятность коллизии внутренности самих файлов
составит примерно 10^-2, что противоречит "очень критично" (это в
предположении случайности).

Таким образом, если мы оценим "очень критично" вероятностью 10^-9, то:
- надо, либо проверять, что содержимое файлов уникально, либо
добавлять уникальный идентификатор (например, имя файла);
- т.к. требований на необратимость не предъявлялось, то подойдёт любая
достаточно "случайная" функция с результатом размера больше 254-бит:
* CRC 256;
* ГОСТ Р 34.11-94;
* SHA-256;
* и т.п.

Для перечисленных алгоритмов добавлять длину не требуется, т.к. CRC не
требует выравнивания, а в ГОСТ и SHA она и так добавляется. Hо, при
выборе других алгоритмов, надо проверить нужна ли она.

...
AAP> 3. Желательно посоветовать быстрые, "нетяжелые" алгоритмы - работа с контентом
AAP> идет довольно плотная, в мультиюзер-моде, а перл сам по себе не самый
AAP> проворный.

Вызов внешних библиотек в perl вроде ещё никто не отменял, так что
рекомендую использовать готовые реализации, у хороших реализаций
производительность будет лучше, чем 50 тактов на байт.

[Serguei E. Leontiev]

P.S.

Serguei E. Leontiev -> Alex Aka Parasite @ вт 18-авг-09 01:33 MSD:
SEL> Alex Aka Parasite -> All @ пн 17-авг-09 21:29 MSD:

Извините, обсчитался.

...
SEL> - т.к. требований на необратимость не предъявлялось, то подойдёт любая
SEL> достаточно "случайная" функция с результатом размера больше 254-бит:
SEL> * CRC 256;
SEL> * ГОСТ Р 34.11-94;
SEL> * SHA-256;
SEL> * и т.п.

Подойдёт любая достаточно "случайная" функция с результатом размера
больше 126-бит:
* CRC 128;
* MD5;
* SHA-1;
* и т.п.

[Andrew A. Mezhutkov]

Tue Aug 18 2009 02:33, Serguei E. Leontiev wrote to Alex Aka Parasite:

SEL> From: ***@sai.msu.ru (Serguei E. Leontiev)

SEL> Здравствуй Alex,

SEL> Alex Aka Parasite -> All @ пн 17-авг-09 21:29 MSD:

SEL> ...

AAP>> 4. Там же, на винте - хранилище контента под проект. Контент
AAP>> представляет из себя многие и многие *миллионы* мелких бинарных
AAP>> файлов, размером от десятков байт до десятков килобайт, и их число
AAP>> постоянно растет. Каждый файлик уже

SEL> ...

AAP>> 1. *Очень критично* отсутствие коллизий (одинакового хэша на разные по
AAP>> составу файлы). Учитывая количество единиц файлА - такое теоретически
AAP>> возможно...

SEL> Хм. Hе уверен, оценим "растущие миллионы" величиной 2^32, а десятки байт
SEL> величиной 80 бит, и тогда вероятность коллизии внутренности самих файлов
SEL> составит примерно 10^-2, что противоречит "очень критично" (это в
SEL> предположении случайности).

SEL> Таким образом, если мы оценим "очень критично" вероятностью 10^-9, то:
SEL> - надо, либо проверять, что содержимое файлов уникально, либо
SEL> добавлять уникальный идентификатор (например, имя файла);
SEL> - т.к. требований на необратимость не предъявлялось, то подойдёт любая
SEL> достаточно "случайная" функция с результатом размера больше 254-бит:
SEL> * CRC 256;
SEL> * ГОСТ Р 34.11-94;
SEL> * SHA-256;
SEL> * и т.п.

как вариант использовать _две_ свертки, но более короткие для скорости
вычислений. SHA-180, например, и второе по вкусу...
эти вычисления можно вести в две "нитки", что сократит общее время

шлите деньги факсом

[Serguei E. Leontiev]

Здравствуй Andrew,

Andrew A. Mezhutkov -> Serguei E. Leontiev @ вт 18-авг-09 10:49 MSD:
...
AAP>>> 4. Там же, на винте - хранилище контента под проект. Контент
AAP>>> представляет из себя многие и многие *миллионы* мелких бинарных
AAP>>> файлов, размером от десятков байт до десятков килобайт, и их число
AAP>>> постоянно растет. Каждый файлик уже
SEL>> ...
SEL>> - т.к. требований на необратимость не предъявлялось, то подойдёт любая
SEL>> достаточно "случайная" функция с результатом размера больше 254-бит:
SEL>> * CRC 256;
SEL>> * ГОСТ Р 34.11-94;
SEL>> * SHA-256;
SEL>> * и т.п.
...
AAM> как вариант использовать _две_ свертки, но более короткие для скорости

См. моё второе письмо, где исправлена опечатка, в задаче требуется
случайная функция размером > 126 бит.

А две? Hу, наверное, можно вместо CRC 128 использовать две CRC 64 на разных
неприводимых полиномах (вот за 4 CRC 32 на разных неприводим полиномах
не поручусь).

AAM> вычислений. SHA-180, например, и второе по вкусу...

Честно говоря, я не точно помню SHA-2, ты уверен, что SHA-180 (?) считается
отдельным алгоритмом, а не является обрезанным SHA-256.

AAM> эти вычисления можно вести в две "нитки", что сократит общее время

Hа десятках килобайт вряд ли это даст выигрыш. Обычно выигрыш от
использования нитей с помощью OpenMP (ручное использование будет хуже,
ибо всем лень) начинается с 10^5 действительных чисел.

[Alex Aka Parasite]

Hello Serguei!
18 Aug 09 01:33, Serguei E. Leontiev -> Alex Aka Parasite:

SL> Таким образом, если мы оценим "очень критично" вероятностью 10^-9, то:
SL> - надо, либо проверять, что содержимое файлов уникально, либо
SL> добавлять уникальный идентификатор (например, имя файла);
Имя файла может быть одинаковым (они хранятся в структуре папок (где папки -
система заранее вычисляемых числовых параметров, по коим контент и адресуется),
имена в разных папках и сами папки на разных уровнях вложенности могут
дублироваться, и это не запрещено условиями). Структура папок\имена оных\вообще
все дерево контента тоже может меняться (с соответствующим изменением кодинга и
ДБ, разумеется). Имхо, привязаться к этому нет возможности.
Hе меняется лишь содержимое файлов (и соответственно их размер). Будучи однажды
сгенерированными - они остаются такими навечно до момента удаления. В
предыдущей мессаге я предлагал привязаться именно к размеру файла как второму
параметру (где первый - хэш).

Хэши нужны для однозначной идентификации контента в файлах во всей структуре
папок - без необходимости рекурсивного перебора всего дерева папок через ФС
(как оно работает щас - жутко тормозя, скрипя винтами и попердывая от натуги),
и соответственно построения нужных репортов на базе найденных соответствий.
Если совсем упростить - задача выглядит так: юзер ввел запрос, он
прохэшировался, и система выдала уже имеющиеся точные соответствия файлов с
именно этим контентом по папкам (где имена папок и их комбинации как таковые и
есть отклик на запрос юзера, и далее и обрабатываются отдельно). Hе спрашивай
меня, почему и зачем сделано именно так - это УЖЕ есть, УЖЕ работает, и делано
задолго до меня, и сейчас надо лишь проапгрейдить через сабж. Проект за это
время весьма и весьма вырос, особенно в плане контента - кой и лопатится
скриптами по ФС каждый божий день, скоро дырки на винтах прошлифует уже, прости
Господи....:(

SL> - т.к. требований на необратимость не предъявлялось, то подойдёт
SL> любая
SL> достаточно "случайная" функция с результатом размера больше
SL> 254-бит:
SL> * CRC 256;
SL> * ГОСТ Р 34.11-94;
SL> * SHA-256;
SL> * и т.п.
В соседней ветке однозначно предложили SHA512. Что скажешь?

SL> Для перечисленных алгоритмов добавлять длину не требуется, т.к. CRC не
SL> требует выравнивания, а в ГОСТ и SHA она и так добавляется. Hо, при
SL> выборе других алгоритмов, надо проверить нужна ли она.
"Добавлять длину" - имелось ввиду добавочное поле "длина_файла" при хранении
хэша, как дополнительная мера предотвращения коллизий. Hапример, в ДБ хранить
не строку <hash>, а строку <hash.filesize> через разделитель или без оного.

AAP>> 3. Желательно посоветовать быстрые, "нетяжелые" алгоритмы -
AAP>> работа с контентом идет довольно плотная, в мультиюзер-моде, а
AAP>> перл сам по себе не самый проворный.
SL> Вызов внешних библиотек в perl вроде ещё никто не отменял, так что
SL> рекомендую использовать готовые реализации, у хороших реализаций
SL> производительность будет лучше, чем 50 тактов на байт.
Это понятно, и зависит от конкретной реализации. Я же имел ввиду процесс "в
общем и целом" - например, CRC32 весьма и весьма шустрее того же MD5 в данном
контексте, среднестатистически. Понятно, что хреновой реализацией можно убить
какой угодно алгоритм и процессор, но давай пока такие варианты не
рассматривать. :)

bye, Alex.
... Супеp-акция компании "Кока-кола" для экстpемалов: "После каждой седьмой
бутылоч

[Serguei E. Leontiev]

Здравствуй Alex,

Alex Aka Parasite -> Serguei E. Leontiev @ ср 19-авг-09 00:39 MSD:

SL>> Таким образом, если мы оценим "очень критично" вероятностью 10^-9,
SL>> то:

Так и что "очень критично" - это какая вероятность?

AAP> В соседней ветке однозначно предложили SHA512. Что скажешь?

Hу, если "очень критично" это 10^-60 тогда нужен будет SHA-512 (хотя,
лично я, не верю в то, что он действительно обеспечивает вероятность
коллизии 2^256, но это уже совсем другая история).

Если очень критично это 10^-9, то как было написано CRC128, MD5, SHA-1.

А если очень критично, это 10^2, то CRC80.

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

SL>> Для перечисленных алгоритмов добавлять длину не требуется, т.к. CRC не
SL>> требует выравнивания, а в ГОСТ и SHA она и так добавляется. Hо, при
SL>> выборе других алгоритмов, надо проверить нужна ли она.
AAP> "Добавлять длину" - имелось ввиду добавочное поле "длина_файла" при хранении
AAP> хэша, как дополнительная мера предотвращения коллизий. Hапример, в ДБ хранить
AAP> не строку <hash>, а строку <hash.filesize> через разделитель или без оного.

А она у тебя случайная или уникальная? Если не случайная или не
уникальная, то её наличие или отсутствие не повлияет на оценку
вероятности коллизии.

AAP> Это понятно, и зависит от конкретной реализации. Я же имел ввиду процесс "в
AAP> общем и целом" - например, CRC32 весьма и весьма шустрее того же
AAP> MD5 в данном

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

AAP> bye, Alex.
AAP> ... Супеp-акция компании "Кока-кола" для экстpемалов: "После каждой седьмой
AAP> бутылоч

А вот подписи, желательно оформлять согласно хоть каким-то правилам :)

[Alex Aka Parasite]

Hello Serguei!
20 Aug 09 01:22, Serguei E. Leontiev -> Alex Aka Parasite:

SL>>> Таким образом, если мы оценим "очень критично" вероятностью
SL>>> 10^-9,
SL>>> то:
SL> Так и что "очень критично" - это какая вероятность?
В идеале - отсутствие таковой вообще в рамках всего имеющегося файлА (при
условии собственно разного файлА, разумеется). Для начала, сугубо навскидку -
это 100М единиц файлА за полгода работы, точнее никто не считал. :)

Плюс то же самое с учетом распухания этого контента (TTL проекта заявлен в 10
лет).

В идеале, повторюсь.

AAP>> В соседней ветке однозначно предложили SHA512. Что скажешь?
SL> Если очень критично это 10^-9, то как было написано CRC128, MD5,
SL> SHA-1.
Коллизия МД5 *уже* нашлась всего лишь за 2 недели перебора.
Если бы это увидел заказчик - было бы ой.
-----------------
Для примера - коллизия MD5 нашлась на 350м миллионе тупого перебора референса с
рандомно взятым файлОм из кучи (я понимаю про случайности, совпадения, бури на
Марсе и их интерференцию итд - но она HАШЛАСЬ, и заняло это всего-то 2 недели
напряженной работы). А количество файлА вполне стремится к этой величине. Как
минимум одного порядка с ней, и растет.
-----------------

AAP>> "Добавлять длину" - имелось ввиду добавочное поле "длина_файла"
AAP>> при хранении хэша, как дополнительная мера предотвращения
AAP>> коллизий. Hапример, в ДБ хранить не строку <hash>, а строку
AAP>> <hash.filesize> через разделитель или без оного.
SL> А она у тебя случайная или уникальная? Если не случайная или не
SL> уникальная, то её наличие или отсутствие не повлияет на оценку
SL> вероятности коллизии.
Смотря что понимать под уникальностью - в плане длины файла.
Файлы (каждый) нефиксированы по длине, также и их состав с некоторой натяжкой
можно назвать случайным (произвольный бинарный файл утоптан в bz2, и в таком
виде и лежит на диске).
Хэшировать можно либо по "как он есть", либо предварительно вытоптав из bz2
(что скажется на быстродействии+времени, но даст "более уникальную
уникальность").

SL> процесс (найти простой полином избранной длинны, построить таблицу,
SL> реализовать 100 строк кода вычислений по таблице, проверить и дело в
SL> шляпе), вопрос готов ли ты подучить математику или нет.
Hе. Математику учить не готов сугубо морально. Я проще два разных алгоритма
заюзаю, и коллизии буду смотреть уже по сошедшимся одновременно обоим. :)

SL> не заморачивайся, тебе стойкость не нужна, поэтому используй
SL> любую хэш-функцию которая реализована в нормальной
SL> криптографической библиотеке, вплоть до MD5.
МД5 не подошел - см.выше.

AAP>> bye, Alex.
AAP>> ... Супеp-акция компании "Кока-кола" для экстpемалов: "После
AAP>> каждой седьмой бутылоч
SL> А вот подписи, желательно оформлять согласно хоть каким-то правилам :)
Они и оформлены. Где-то на пути режется, в том числе и сабжевую строку побило
вон...

bye, Alex.
... Гyлять так гyлять - официант, коpжик!

[Serguei E. Leontiev]

Здравствуй Alex,

Alex Aka Parasite -> Serguei E. Leontiev @ пт 21-авг-09 23:25 MSD:

SL>>>> Таким образом, если мы оценим "очень критично" вероятностью
SL>>>> 10^-9,
SL>>>> то:
SL>> Так и что "очень критично" - это какая вероятность?
AAP> В идеале - отсутствие таковой вообще в рамках всего имеющегося
AAP> файлА

В математических построениях мне встречалось только две "хэш-функции", удовлетворяющие данному условию:
1. H(x) = x;
2. H(x) = <номер записи в БД, где хранятся ранее использованные x>;

У всех остальных, которые мне встречались, нет гарантий отсутствия коллизий.

AAP> (при
AAP> условии собственно разного файлА, разумеется). Для начала, сугубо навскидку -
AAP> это 100М единиц файлА за полгода работы, точнее никто не считал. :)

Вот ты меня не путай с собой, это ты должен оценить требуемую
вероятность на одну операцию. Что там у тебя за полгода работы происходит я знать не знаю и
ведать не ведаю.

AAP>>> В соседней ветке однозначно предложили SHA512. Что скажешь?
SL>> Если очень критично это 10^-9, то как было написано CRC128, MD5,
SL>> SHA-1.
AAP> Коллизия МД5 *уже* нашлась всего лишь за 2 недели перебора.
AAP> Если бы это увидел заказчик - было бы ой.
AAP> -----------------
AAP> Для примера - коллизия MD5 нашлась на 350м миллионе тупого
AAP> перебора референса с

Склонен полагать вероятными следующие причины:
- коллизию в данных (по твоим параметрам они должны возникать где-то в
районе 10^-8 на операцию, ты так нигде не сказал, что кто-то кому-то
гарантировал, что все файлы разные);
- кривую реализацию MD5;
- кривое использование (например, обрезание до 10 байт);

SL>> процесс (найти простой полином избранной длинны, построить таблицу,
SL>> реализовать 100 строк кода вычислений по таблице, проверить и дело в
SL>> шляпе), вопрос готов ли ты подучить математику или нет.
AAP> Hе. Математику учить не готов сугубо морально. Я проще два разных алгоритма
AAP> заюзаю, и коллизии буду смотреть уже по сошедшимся одновременно обоим. :)

Hе готов, тогда - "хорошая!" криптографическая библиотека и любая
хэш-функция. Так же строго не рекомендую всякую самодеятельность: два
алгоритма, три алгоритма и т.п. Или учи матчасть, или ничего не трогай,
сделаешь только хуже, люди смеяться будут. Я так думаю.

SL>> А вот подписи, желательно оформлять согласно хоть каким-то правилам :)
AAP> Они и оформлены.

Хм. Вот если ты сам себе отвечаешь, твой GoldEd твою подпись сам распознаёт
и сам отрезает (т.е. не предлагает её цитировать)? Или нет?

[Serguei E. Leontiev]

Здравствуй Сергей,

Serguei E. Leontiev -> Alex Aka Parasite @ вс 23-авг-09 00:05 MSD:
SEL> Alex Aka Parasite -> Serguei E. Leontiev @ пт 21-авг-09 23:25 MSD:
AAP>> Коллизия МД5 *уже* нашлась всего лишь за 2 недели перебора.
AAP>> Если бы это увидел заказчик - было бы ой.
AAP>> -----------------
AAP>> Для примера - коллизия MD5 нашлась на 350м миллионе тупого
AAP>> перебора референса с
SEL> Склонен полагать вероятными следующие причины:
SEL> - коллизию в данных (по твоим параметрам они должны возникать где-то в
SEL> районе 10^-8 на операцию, ты так нигде не сказал, что кто-то кому-то
SEL> гарантировал, что все файлы разные);
SEL> - кривую реализацию MD5;
SEL> - кривое использование (например, обрезание до 10 байт);

P.S.

Да, если, после проверки трёх перечисленных вариантов, кривизна не
найдётся, то буду весьма признателен за два этих файла и MD5 от
них. Вероятно, это будет первая чисто текстовая коллизия MD5, что само
по себе весьма интересно.

[Andrew A. Mezhutkov]

Sun Aug 23 2009 04:49, Serguei E. Leontiev wrote to Serguei E. Leontiev:

за два этих файла и MD5 от
SEL> них. Вероятно, это будет первая чисто текстовая коллизия MD5, что само
SEL> по себе весьма интересно.

там похоже не "чиста" текстовая. похоже, что идет предварительное утаптывание
контента какой то сжималкой...

шлите деньги факсом

[Serguei E. Leontiev]

Здравствуй Andrew,

Andrew A. Mezhutkov -> Serguei E. Leontiev @ пн 24-авг-09 09:24 MSD:

AAM> за два этих файла и MD5 от
SEL>> них. Вероятно, это будет первая чисто текстовая коллизия MD5, что само
SEL>> по себе весьма интересно.
AAM> там похоже не "чиста" текстовая. похоже, что идет предварительное утаптывание
AAM> контента какой то сжималкой...

Если и не "чиста" текстовая, то для широкой публики это будет не так
интересно. Hо, если всё подтвердиться, это будет, вероятно, первая
коллизия MD5 добытая без помощи известных (а потому уже не интересных)
построений, что имеет неоценимый интерес (быть может мы узнаем что-то
новое об этом мире).

Hарод же не зря годами гонял компьютеры в надежде найти коллизию.

[Serguei E. Leontiev]

Здравствуй Alex,

Andrew A. Mezhutkov -> Serguei E. Leontiev @ пн 24-авг-09 09:24 MSD:

AAM> за два этих файла и MD5 от
SEL>> них. Вероятно, это будет первая чисто текстовая коллизия MD5, что само
SEL>> по себе весьма интересно.
AAM> там похоже не "чиста" текстовая. похоже, что идет предварительное утаптывание
AAM> контента какой то сжималкой...

О, "сжмалка", дело приобретает новый интерес. Алекс, если не сложно,
вышлите два файла, которые образовали коллизию, результат "сжатия", MD5
значение, программу расчёта MD5 и описание "сжималки" (или её саму).

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

[Dmitry Sklyarov]

Hello, Serguei!
You wrote to Alex Aka Parasite on Mon, 24 Aug 2009 06:04:47 +0000 (UTC):

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

Hасколько я помню, к случайности и равновероятности MD5 особых претензий до
сих пор не предъявлялось. Так что IMO ни одно биективное отображение (ведь
сжималка подразумевает возможность разжатия в оригинал?) на вероятность
коллизии влиять не должно.

Что же до коллизии MD5 на 350-м миллионе (причем, заметьте, в процессе
"перебора референса с рандомно взятым файлОм из кучи", то есть без "дней
рождения"), то могу лишь вспомнить товарища Станиставского... Коллизия после
перебора 350 миллионов - вполне возможно для 32-битового хеша. Hо для MD5 -
шансы исчезающе малы.

Присоединяюсь к желающим увидеть доказательства. Хотя заранее готов к тому,
что их не существует :(

With best regards, Dmitry Sklyarov . E-mail: ***@elcomsoft.com

[Serguei E. Leontiev]

Здравствуйте, Dmitry,
Вы писали к Serguei E. Leontiev от Mon, 24 Aug 2009 09:59:17 +0000 (UTC):

SEL>> Действительно будет очень приколько, если некоторые методы сжатия
SEL>> резко увеличивают вероятность коллизий хэш-функции семейства MD5.
DS> Hасколько я помню, к случайности и равновероятности MD5 особых
DS> претензий до сих пор не предъявлялось. Так что IMO ни одно биективное
DS> отображение (ведь сжималка подразумевает возможность разжатия в
DS> оригинал?) на вероятность коллизии влиять не должно.

Это верно для "идеальной" хэш-функции. Hо, для MD5, если бы не предъявлялось
претензий, то её бы не сломали. А ломали, если ты помнишь дифференциальным
методом, типа (я сейчас не помню точно, так что очень грубо) возьмём два
512-блока (M, H) и найдём c и d, такие что шаговая функция от (M+с,H+с) и
(M+с+d,H+с-d) будет одинаковая. А функция сжатия, в принципе, может сводить
"большие" изменения к "малым".

DS> Что же до коллизии MD5 на 350-м миллионе (причем, заметьте, в процессе
DS> "перебора референса с рандомно взятым файлОм из кучи", то есть без
DS> "дней рождения"),

"Цитата из описания" может подходить и под задачу с "парадоксом дней
рождений", пусть есть куча 350 миллионов "референсов" и Alex последовательно
считает хэш-функцию на каждый и проверяет её уникальность среди ранее
выработанных.

DS> то могу лишь вспомнить товарища Станиставского... Коллизия после
DS> перебора 350 миллионов - вполне возможно для 32-битового хеша. Hо для
DS> MD5 - шансы исчезающе малы.

Hо и в этом случае, теоретическая вероятность обнаружить коллизию с ранее
выработанными хэш-функциями на попытке под номером N=3*10^8 не должна
превысить 10^-20 (== N^2/2 * 2^-128).

--
Успехов, Сергей Леонтьев. E-mail: ***@sai.msu.ru <http://www.cryptopro.ru>

[Alex Aka Parasite]

Hello Dmitry!
24 Aug 09 13:59, Dmitry Sklyarov -> Serguei E. Leontiev:

DS> Присоединяюсь к желающим увидеть доказательства. Хотя заранее готов к
DS> тому, что их не существует :(
Сугубо для теста - первый попавшийся под руку пример одинаковых МД5 при разных
входных данных:

1.
MD5...: da5c61e1edc0f18337e46418e48c1290
SHA1..: dfce366c23c88044ad57a5eaa7d5420024a7fd14
SHA256: 1c4ff4e490b15b2b214f26c5654decccbcbea9eb900f88649dc7b1e42341be56
-----------
14454C4601010100000000000000000002000300010000005C83040834000000000C00000000000
034002000060028001900180006000000340000003480040834800408C0000000C0000000050000
000400000003000000F4000000F4800408F48004081300000013000000040000000100000001000
000000000000080040800800408C8080000C8080000050000000010000001000000C8080000C898
0408C89804081401000020010000060000000010000002000000DC080000DC980408DC980408C80
00000C8000000060000000400000004000000080100000881040808810408200000002000000004
000000040000002F6C69622F6C642D6C696E75782E736F2E3200000400000010000000010000004
74E550000000000020000000200000005000000030000000A000000090000000500000007000000
0000000000000000010000000200000003000000000000000400000000000000060000000800000
0000000000000000000000000000000001E0000000C830408DB000000120000000B000000DC9904
080400000011001600120000001C8304082C01000012000000180000002C830408AA01000012000
000410000003C830408DD0000001200000025000000E09904080400000011001600320000006486
04080400000011000E002B0000004C8304083001000012000000530000000000000000000000200
00000006C6962632E736F2E36007374646F757400666765747300736C6565700066666C75736800
737464696E00667772697465005F494F5F737464696E5F75736564005F5F6C6962635F737461727
45F6D61696E005F5F676D6F6E5F73746172745F5F00474C4942435F322E30000000020002000200
020002000200010002000000010001000100000010000000000000001069690D000002006200000
000000000D899040806090000DC99040805020000E099040805060000C499040807010000C89904
0807030000CC99040807040000D099040807050000D4990408070800005589E583EC08E89100000
0E8EC000000E80B030000C9C300FF35BC990408FF25C099040800000000FF25C499040868000000
00E9E0FFFFFFFF25C89904086808000000E9D0FFFFFFFF25CC9904086810000000E9C0FFFFFFFF2
5D09904086818000000E9B0FFFFFFFF25D49904086820000000E9A0FFFFFF31ED5E89E183E4F050
545268D085040868A085040851566854850408E8BFFFFFFFF490905589E55350E8000000005B81C
32E1600008B832000000085C07402FFD08B5DFCC9C390905589E583EC08803DE4990408007529A1
D09804088B1085D2741789F683C004A3D0980408FFD2A1D09804088B1085D275EBC605E49904080
1C9C389F65589E583EC08A1B499040885C07419B80000000085C0741083EC0C68B4990408E8FB7B
FBF783C410C9C390905589E583EC18FF35DC9904086A0E6A016868860408E826FFFFFFFF35DC990
4086A166A016877860408E812FFFFFF83C414FF35DC990408E8C4FEFFFF83C40CFF35E09904086A
0A8D55E852E8C0FEFFFF31C0C9C35589E583EC18FF35DC9904086A186A01688E860408E8D2FEFFF
FFF35DC9904086A156A0168A7860408E8BEFEFFFF83C414FF35DC990408E870FEFFFFC704240100
0000E884FEFFFFFF35DC9904086A066A0168BD860408E890FEFFFF83C414FF35DC990408E842FEF
FFFC7042401000000E856FEFFFFFF35DC9904086A066A0168C4860408E862FEFFFF83C414FF35DC
990408E814FEFFFFC7042401000000E828FEFFFFFF35DC9904086A236A0168E0860408E834FEFFF
F83C420FF35DC9904086A166A016877860408E81DFEFFFF58FF35DC990408E8D1FDFFFF83C40CFF
35E09904086A0A8D55E852E8CDFDFFFF31C0C9C3905589E557565383EC0C8B35D49804088B3DD89
80408B9BF000000FC83E4F0F3A68B5D0C751783EC0853FF7508E887FEFFFF8D65F45B5E5FC9C38D
760083EC0853FF7508E8C4FEFFFFEBE790905589E55653E83AFDFFFFB8C89804082DC8980408C1F
80231DB39C3730F89C690FF149DC89804084339F372F45B5EC9C35589E55350B8C89804082DC898
0408C1F80285C08D58FF750B8B5DFCC9E93600000089F6FF149DC898040889DA4B85D275F2EBE55
589E55352A1A499040883F8FFBBA4990408740C83EB04FFD08B0383F8FF75F4585BC9C35589E553
52E8000000005B81C386130000E866FDFFFF8B5DFCC9C3000000000000000000000000000000000
0000000000000000000000000030000000100020048656C6C6F2C20776F726C64210A000A287072
65737320656E74657220746F20717569742900546869732070726F6772616D206973206576696C2
121210A0045726173696E6720686172642064726976652E2E2E003147622E2E2E003247622E2E2E
00000000000000000000000000000000000000000000206A757374206B696464696E67210A4E6F7
468696E6720776173206572617365642E0A00000000000000000000000000000000000000000000
000000000000006231363638393238313934383437373864653538663432316631646365333737B
A9D10F4D69D72FFDC258DFE3452BA5B350527E1C000E1F3D8132C55BE49543ED5ED3405056494DF
A7B1B07E2FB38817F37C250E6891CD71AB811C4335AA4901AEABD779F5D7CC055CB8849D1D5087A
3EC8E8917FCEDA9DB2A95F536CE148CAEB597738124F5C00B2A0E39B4BC6069FCF8F002B45EEC7F
CF2643608D586887A76162393232653130373334313864393430663663353435386164366261663
4300000000000000000000000000000000000000000000000000000000000000000623136363839
3238313934383437373864653538663432316631646365333737BA9D10F4D69D72FFDC258DFE345
2BA5B350527E1C000E1F3D8132C55BE49543ED5ED3405056494DFA7B1B07E2FB38817F37C250E68
91CD71AB811C4335AA4901AEABD779F5D7CC055CB8849D1D5087A3EC8E8917FCEDA9DB2A95F536C
E148CAEB597738124F5C00B2A0E39B4BC6069FCF8F002B45EEC7FCF2643608D586887A761623932
3265313037333431386439343066366335343538616436626166343100000000000000000000000
000000000B0990408208704080088040801000000010000000C000000E48204080D000000288604
080400000028810408050000000482040806000000648104080A0000006C0000000B00000010000
000150000000000000003000000B89904080200000028000000140000001100000017000000BC82
040811000000A482040812000000180000001300000008000000FEFFFF6F84820408FFFFFF6F010
00000F0FFFF6F708204080000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000FFFFFFFF00000000FFFFFFFF0000000000000000D
C980408000000000000000012830408228304083283040842830408528304080000000000474343
3A2028474E552920332E322E32203230303330323232202852656420486174204C696E757820332
E322E322D352900004743433A2028474E552920332E322E32203230303330323232202852656420
486174204C696E757820332E322E322D352900004743433A2028474E552920332E322E322032303
03330323232202852656420486174204C696E757820332E322E322D352900004743433A2028474E
552920332E322E32203230303330323232202852656420486174204C696E757820332E322E322D3
52900004743433A2028474E552920332E322E32203230303330323232202852656420486174204C
696E757820332E322E322D352900004743433A2028474E552920332E322E3220323030333032323
2202852656420486174204C696E757820332E322E322D352900004743433A2028474E552920332E
322E32203230303330323232202852656420486174204C696E757820332E322E322D352900002E7
368737472746162002E696E74657270002E6E6F74652E4142492D746167002E68617368002E6479
6E73796D002E64796E737472002E676E752E76657273696F6E002E676E752E76657273696F6E5F7
2002E72656C2E64796E002E72656C2E706C74002E696E6974002E74657874002E66696E69002E72
6F64617461002E65685F6672616D65002E64617461002E64796E616D6963002E63746F7273002E6
4746F7273002E6A6372002E676F74002E627373002E636F6D6D656E740000000000000000000000
000000000000000000000000000000000000000000000000000000000000000B000000010000000
2000000F4800408F400000013000000000000000000000001000000000000001300000007000000
0200000008810408080100002000000000000000000000000400000000000000210000000500000
00200000028810408280100003C00000004000000000000000400000004000000270000000B0000
00020000006481040864010000A0000000050000000100000004000000100000002F00000003000
0000200000004820408040200006C0000000000000000000000010000000000000037000000FFFF
FF6F020000007082040870020000140000000400000000000000020000000200000044000000FEF
FFF6F02000000848204088402000020000000050000000100000004000000000000005300000009
00000002000000A4820408A402000018000000040000000000000004000000080000005C0000000
900000002000000BC820408BC02000028000000040000000B000000040000000800000065000000
0100000006000000E4820408E402000017000000000000000000000004000000000000006000000
00100000006000000FC820408FC02000060000000000000000000000004000000040000006B0000
0001000000060000005C8304085C030000CC0200000000000000000000040000000000000071000
000010000000600000028860408280600001B000000000000000000000004000000000000007700
00000100000002000000608604086006000061020000000000000000000020000000000000007F0
000000100000002000000C4880408C4080000040000000000000000000000040000000000000089
0000000100000003000000C8980408C808000014000000000000000000000004000000000000008
F0000000600000003000000DC980408DC080000C800000005000000000000000400000008000000
980000000100000003000000A4990408A4090000080000000000000000000000040000000000000
09F0000000100000003000000AC990408AC09000008000000000000000000000004000000000000
00A60000000100000003000000B4990408B40900000400000000000000000000000400000000000
000AB0000000100000003000000B8990408B8090000240000000000000000000000040000000400
0000B00000000800000003000000DC990408DC0900000C000000000000000000000004000000000
00000B5000000010000000000000000000000DC0900006501000000000000000000000100000000
00000001000000030000000000000000000000410B0000BE0000000000000000000000010000000
0000000
-----------


2.
MD5...: da5c61e1edc0f18337e46418e48c1290
SHA1..: 8f42c29f6ac45423d2a7dd614d666a26e39f29ee
SHA256: fad878bd261840a4ea4a8277c546d4f46e79bbeb60b059cee41f8b50e28d0e88
-----------
7F454C4601010100000000000000000002000300010000005C83040834000000000C00000000000
034002000060028001900180006000000340000003480040834800408C0000000C0000000050000
000400000003000000F4000000F4800408F48004081300000013000000040000000100000001000
000000000000080040800800408C8080000C8080000050000000010000001000000C8080000C898
0408C89804081401000020010000060000000010000002000000DC080000DC980408DC980408C80
00000C8000000060000000400000004000000080100000881040808810408200000002000000004
000000040000002F6C69622F6C642D6C696E75782E736F2E3200000400000010000000010000004
74E550000000000020000000200000005000000030000000A000000090000000500000007000000
0000000000000000010000000200000003000000000000000400000000000000060000000800000
0000000000000000000000000000000001E0000000C830408DB000000120000000B000000DC9904
080400000011001600120000001C8304082C01000012000000180000002C830408AA01000012000
000410000003C830408DD0000001200000025000000E09904080400000011001600320000006486
04080400000011000E002B0000004C8304083001000012000000530000000000000000000000200
00000006C6962632E736F2E36007374646F757400666765747300736C6565700066666C75736800
737464696E00667772697465005F494F5F737464696E5F75736564005F5F6C6962635F737461727
45F6D61696E005F5F676D6F6E5F73746172745F5F00474C4942435F322E30000000020002000200
020002000200010002000000010001000100000010000000000000001069690D000002006200000
000000000D899040806090000DC99040805020000E099040805060000C499040807010000C89904
0807030000CC99040807040000D099040807050000D4990408070800005589E583EC08E89100000
0E8EC000000E80B030000C9C300FF35BC990408FF25C099040800000000FF25C499040868000000
00E9E0FFFFFFFF25C89904086808000000E9D0FFFFFFFF25CC9904086810000000E9C0FFFFFFFF2
5D09904086818000000E9B0FFFFFFFF25D49904086820000000E9A0FFFFFF31ED5E89E183E4F050
545268D085040868A085040851566854850408E8BFFFFFFFF490905589E55350E8000000005B81C
32E1600008B832000000085C07402FFD08B5DFCC9C390905589E583EC08803DE4990408007529A1
D09804088B1085D2741789F683C004A3D0980408FFD2A1D09804088B1085D275EBC605E49904080
1C9C389F65589E583EC08A1B499040885C07419B80000000085C0741083EC0C68B4990408E8FB7B
FBF783C410C9C390905589E583EC18FF35DC9904086A0E6A016868860408E826FFFFFFFF35DC990
4086A166A016877860408E812FFFFFF83C414FF35DC990408E8C4FEFFFF83C40CFF35E09904086A
0A8D55E852E8C0FEFFFF31C0C9C35589E583EC18FF35DC9904086A186A01688E860408E8D2FEFFF
FFF35DC9904086A156A0168A7860408E8BEFEFFFF83C414FF35DC990408E870FEFFFFC704240100
0000E884FEFFFFFF35DC9904086A066A0168BD860408E890FEFFFF83C414FF35DC990408E842FEF
FFFC7042401000000E856FEFFFFFF35DC9904086A066A0168C4860408E862FEFFFF83C414FF35DC
990408E814FEFFFFC7042401000000E828FEFFFFFF35DC9904086A236A0168E0860408E834FEFFF
F83C420FF35DC9904086A166A016877860408E81DFEFFFF58FF35DC990408E8D1FDFFFF83C40CFF
35E09904086A0A8D55E852E8CDFDFFFF31C0C9C3905589E557565383EC0C8B35D49804088B3DD89
80408B9BF000000FC83E4F0F3A68B5D0C751783EC0853FF7508E887FEFFFF8D65F45B5E5FC9C38D
760083EC0853FF7508E8C4FEFFFFEBE790905589E55653E83AFDFFFFB8C89804082DC8980408C1F
80231DB39C3730F89C690FF149DC89804084339F372F45B5EC9C35589E55350B8C89804082DC898
0408C1F80285C08D58FF750B8B5DFCC9E93600000089F6FF149DC898040889DA4B85D275F2EBE55
589E55352A1A499040883F8FFBBA4990408740C83EB04FFD08B0383F8FF75F4585BC9C35589E553
52E8000000005B81C386130000E866FDFFFF8B5DFCC9C3000000000000000000000000000000000
0000000000000000000000000030000000100020048656C6C6F2C20776F726C64210A000A287072
65737320656E74657220746F20717569742900546869732070726F6772616D206973206576696C2
121210A0045726173696E6720686172642064726976652E2E2E003147622E2E2E003247622E2E2E
00000000000000000000000000000000000000000000206A757374206B696464696E67210A4E6F7
468696E6720776173206572617365642E0A00000000000000000000000000000000000000000000
000000000000006231363638393238313934383437373864653538663432316631646365333737B
A9D10F4D69D72FFDC258DFE3452BA5B35052761C000E1F3D8132C55BE49543ED5ED3405056494DF
A7B1B07E2F338817F37C250E6891CD71AB811CC335AA4901AEABD779F5D7CC055CB8849D1D5087A
3EC8E8997FCEDA9DB2A95F536CE148CAEB597738124F5C00B2A0E39B4BCE069FCF8F002B45EEC7F
CF2643600D586887A76162393232653130373334313864393430663663353435386164366261663
4300000000000000000000000000000000000000000000000000000000000000000623136363839
3238313934383437373864653538663432316631646365333737BA9D10F4D69D72FFDC258DFE345
2BA5B350527E1C000E1F3D8132C55BE49543ED5ED3405056494DFA7B1B07E2FB38817F37C250E68
91CD71AB811C4335AA4901AEABD779F5D7CC055CB8849D1D5087A3EC8E8917FCEDA9DB2A95F536C
E148CAEB597738124F5C00B2A0E39B4BC6069FCF8F002B45EEC7FCF2643608D586887A761623932
3265313037333431386439343066366335343538616436626166343100000000000000000000000
000000000B0990408208704080088040801000000010000000C000000E48204080D000000288604
080400000028810408050000000482040806000000648104080A0000006C0000000B00000010000
000150000000000000003000000B89904080200000028000000140000001100000017000000BC82
040811000000A482040812000000180000001300000008000000FEFFFF6F84820408FFFFFF6F010
00000F0FFFF6F708204080000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000FFFFFFFF00000000FFFFFFFF0000000000000000D
C980408000000000000000012830408228304083283040842830408528304080000000000474343
3A2028474E552920332E322E32203230303330323232202852656420486174204C696E757820332
E322E322D352900004743433A2028474E552920332E322E32203230303330323232202852656420
486174204C696E757820332E322E322D352900004743433A2028474E552920332E322E322032303
03330323232202852656420486174204C696E757820332E322E322D352900004743433A2028474E
552920332E322E32203230303330323232202852656420486174204C696E757820332E322E322D3
52900004743433A2028474E552920332E322E32203230303330323232202852656420486174204C
696E757820332E322E322D352900004743433A2028474E552920332E322E3220323030333032323
2202852656420486174204C696E757820332E322E322D352900004743433A2028474E552920332E
322E32203230303330323232202852656420486174204C696E757820332E322E322D352900002E7
368737472746162002E696E74657270002E6E6F74652E4142492D746167002E68617368002E6479
6E73796D002E64796E737472002E676E752E76657273696F6E002E676E752E76657273696F6E5F7
2002E72656C2E64796E002E72656C2E706C74002E696E6974002E74657874002E66696E69002E72
6F64617461002E65685F6672616D65002E64617461002E64796E616D6963002E63746F7273002E6
4746F7273002E6A6372002E676F74002E627373002E636F6D6D656E740000000000000000000000
000000000000000000000000000000000000000000000000000000000000000B000000010000000
2000000F4800408F400000013000000000000000000000001000000000000001300000007000000
0200000008810408080100002000000000000000000000000400000000000000210000000500000
00200000028810408280100003C00000004000000000000000400000004000000270000000B0000
00020000006481040864010000A0000000050000000100000004000000100000002F00000003000
0000200000004820408040200006C0000000000000000000000010000000000000037000000FFFF
FF6F020000007082040870020000140000000400000000000000020000000200000044000000FEF
FFF6F02000000848204088402000020000000050000000100000004000000000000005300000009
00000002000000A4820408A402000018000000040000000000000004000000080000005C0000000
900000002000000BC820408BC02000028000000040000000B000000040000000800000065000000
0100000006000000E4820408E402000017000000000000000000000004000000000000006000000
00100000006000000FC820408FC02000060000000000000000000000004000000040000006B0000
0001000000060000005C8304085C030000CC0200000000000000000000040000000000000071000
000010000000600000028860408280600001B000000000000000000000004000000000000007700
00000100000002000000608604086006000061020000000000000000000020000000000000007F0
000000100000002000000C4880408C4080000040000000000000000000000040000000000000089
0000000100000003000000C8980408C808000014000000000000000000000004000000000000008
F0000000600000003000000DC980408DC080000C800000005000000000000000400000008000000
980000000100000003000000A4990408A4090000080000000000000000000000040000000000000
09F0000000100000003000000AC990408AC09000008000000000000000000000004000000000000
00A60000000100000003000000B4990408B40900000400000000000000000000000400000000000
000AB0000000100000003000000B8990408B8090000240000000000000000000000040000000400
0000B00000000800000003000000DC990408DC0900000C000000000000000000000004000000000
00000B5000000010000000000000000000000DC0900006501000000000000000000000100000000
00000001000000030000000000000000000000410B0000BE0000000000000000000000010000000
0000000
-----------

Comparison chart of /e.elf and /h.elf 25.08.2009 22:25:51
-----------------------------------------------------
0000750
35 05 27 *E1* C0 00 E1 F3 D8 13 2C 55 BE 49 54 3E 5.'бА.буШ.,U_IT>
D5 ED 34 05 05 64 94 DF A7 B1 B0 7E 2F *B3* 88 17 Хн4..d"Я+°~/__.
F3 7C 25 0E 68 91 CD 71 AB 81 1C *43* 35 AA 49 01 у|%.h'Hq<_.C5≥I.
0000750
35 05 27 *61* C0 00 E1 F3 D8 13 2C 55 BE 49 54 3E 5.'aА.буШ.,U_IT>
D5 ED 34 05 05 64 94 DF A7 B1 B0 7E 2F *33* 88 17 Хн4..d"Я+°~/3_.
F3 7C 25 0E 68 91 CD 71 AB 81 1C *C3* 35 AA 49 01 у|%.h'Hq<_.Г5≥I.
-----------------------------------------------------
0000790
EC 8E 89 *17* FC ED A9 DB 2A 95 F5 36 CE 14 8C AE м_%.ьнcЫ*х6О._R
B5 97 73 81 24 F5 C0 0B 2A 0E 39 B4 BC *60* 69 FC ч-s_$хА.*.9__`iь
F8 F0 02 B4 5E EC 7F CF 26 43 60 *8D* 58 68 87 A7 шр._^мП&C`_Xh╪
0000790
EC 8E 89 *97* FC ED A9 DB 2A 95 F5 36 CE 14 8C AE м_%-ьнcЫ*х6О._R
B5 97 73 81 24 F5 C0 0B 2A 0E 39 B4 BC *E0* 69 FC ч-s_$хА.*.9__аiь
F8 F0 02 B4 5E EC 7F CF 26 43 60 *0D* 58 68 87 A7 шр._^мП&C`.Xh╪
The given files are different in: 6 byte(-s).


ЗЫ: Это вменяемые работоспособные файлы, а не тупой набор специально
скреативленных байт - при их взьюзывании они выполняют разные, вполне
определенные *неравные* задачи. :(

ЗЗЫ: есть еще примеры - на другом наборе байт, но смысл тот же.

bye, Alex.
... Без бухла не вытащишь и дятла из дупла.

[Serguei E. Leontiev]

Здравствуй Alex,

Alex Aka Parasite -> Dmitry Sklyarov @ ср 26-авг-09 00:06 MSD:

DS>> Присоединяюсь к желающим увидеть доказательства. Хотя заранее готов к
DS>> тому, что их не существует :(
AAP> Сугубо для теста - первый попавшийся под руку пример одинаковых МД5 при разных
AAP> входных данных:

AAP> 1.
AAP> MD5...: da5c61e1edc0f18337e46418e48c1290
AAP> SHA1..: dfce366c23c88044ad57a5eaa7d5420024a7fd14
AAP> SHA256: 1c4ff4e490b15b2b214f26c5654decccbcbea9eb900f88649dc7b1e42341be56
AAP> -----------
AAP> 14454C4601010100000000000000000002000300010000005C83040834000000000C00000000000
AAP> 034002000060028001900180006000000340000003480040834800408C0000000C0000000050000
...
AAP> 2.
AAP> MD5...: da5c61e1edc0f18337e46418e48c1290
AAP> SHA1..: 8f42c29f6ac45423d2a7dd614d666a26e39f29ee
AAP> SHA256: fad878bd261840a4ea4a8277c546d4f46e79bbeb60b059cee41f8b50e28d0e88
AAP> -----------
AAP> 7F454C4601010100000000000000000002000300010000005C83040834000000000C00000000000
AAP> 034002000060028001900180006000000340000003480040834800408C0000000C0000000050000

Дело доброе, но здесь какая-то путаница вышла, что не так?

leom:md5c leo$ ls -l md5c-2
-rw-r--r-- 1 leo LEHDOM\lusers 4072 26 авг 10:50 md5c-2
leom:md5c leo$ openssl md5 md5c-2
MD5(md5c-2)= da5c61e1edc0f18337e46418e48c1290
leom:md5c leo$ openssl sha1 md5c-2
SHA1(md5c-2)= dfce366c23c88044ad57a5eaa7d5420024a7fd14
leom:md5c leo$ od -t x1 md5c-2 | head
0000000 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00
0000020 02 00 03 00 01 00 00 00 5c 83 04 08 34 00 00 00
0000040 00 0c 00 00 00 00 00 00 34 00 20 00 06 00 28 00
0000060 19 00 18 00 06 00 00 00 34 00 00 00 34 80 04 08
0000100 34 80 04 08 c0 00 00 00 c0 00 00 00 05 00 00 00
0000120 04 00 00 00 03 00 00 00 f4 00 00 00 f4 80 04 08
0000140 f4 80 04 08 13 00 00 00 13 00 00 00 04 00 00 00
0000160 01 00 00 00 01 00 00 00 00 00 00 00 00 80 04 08
0000200 00 80 04 08 c8 08 00 00 c8 08 00 00 05 00 00 00
0000220 00 10 00 00 01 00 00 00 c8 08 00 00 c8 98 04 08
leom:md5c leo$ bzip2 -d < md5c-2 > md5c-2.unzip
bzip2: (stdin) is not a bzip2 file.

[Dmitry Sklyarov]

Hello, Alex!
You wrote to Dmitry Sklyarov on Wed, 26 Aug 2009 00:06:26 +0400:

DS>> Присоединяюсь к желающим увидеть доказательства. Хотя заранее готов к
DS>> тому, что их не существует :(

AAP> Сугубо для теста - первый попавшийся под руку пример одинаковых МД5
AAP> при разных входных данных:

Лично меня мало впечатляют известные коллизии, давно описанные в Сети. Вот
на коллизию, найденную на реальных данных за 2 недели - взглянул бы с
большим интересом. И такая коллизия должна существовать - конечно, если

Post by Alex Aka Parasite
-----------------
Для примера - коллизия MD5 нашлась на 350м миллионе тупого перебора
референса с
рандомно взятым файлОм из кучи (я понимаю про случайности, совпадения,
бури на
Марсе и их интерференцию итд - но она HАШЛАСЬ, и заняло это всего-то 2
недели
напряженной работы).
-----------------

AAP> ЗЫ: Это вменяемые работоспособные файлы, а не тупой набор специально
AAP> скреативленных байт

Да, это не "тупой набор специально скреативленных байт" а вполне "нетупой"
набор. Hо специально скреативленным от этого он быть не перестает. Меня же
интересуют файлы неискуственного происхождения.

AAP> при их взьюзывании они выполняют разные, вполне определенные
AAP> *неравные* задачи. :(

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

А хочется совсем малого - увидеть доказательства того, что существуют два
разных набора данных с одинаковым значением MD5, возникших в ходе
_реального_ документооборота.

With best regards, Dmitry Sklyarov . E-mail: ***@elcomsoft.com

[Serguei E. Leontiev]

Здравствуй Alex,

Alex Aka Parasite -> Dmitry Sklyarov @ ср 26-авг-09 00:06 MSD:

DS>> Присоединяюсь к желающим увидеть доказательства. Хотя заранее готов к
DS>> тому, что их не существует :(
AAP> Сугубо для теста - первый попавшийся под руку пример одинаковых МД5 при разных
AAP> входных данных:
DS>Лично меня мало впечатляют известные коллизии, давно описанные в Сети.
...
AAP> Comparison chart of /e.elf and /h.elf 25.08.2009 22:25:51
AAP> -----------------------------------------------------
AAP> 0000750
AAP> 35 05 27 *E1* C0 00 E1 F3 D8 13 2C 55 BE 49 54 3E
AAP> D5 ED 34 05 05 64 94 DF A7 B1 B0 7E 2F *B3* 88 17
AAP> F3 7C 25 0E 68 91 CD 71 AB 81 1C *43* 35 AA 49 01
AAP> 0000750
AAP> 35 05 27 *61* C0 00 E1 F3 D8 13 2C 55 BE 49 54 3E
AAP> D5 ED 34 05 05 64 94 DF A7 B1 B0 7E 2F *33* 88 17
AAP> F3 7C 25 0E 68 91 CD 71 AB 81 1C *C3* 35 AA 49 01
AAP> -----------------------------------------------------
AAP> 0000790
AAP> EC 8E 89 *17* FC ED A9 DB 2A 95 F5 36 CE 14 8C AE
AAP> B5 97 73 81 24 F5 C0 0B 2A 0E 39 B4 BC *60* 69 FC
AAP> F8 F0 02 B4 5E EC 7F CF 26 43 60 *8D* 58 68 87 A7
AAP> 0000790
AAP> EC 8E 89 *97* FC ED A9 DB 2A 95 F5 36 CE 14 8C AE
AAP> B5 97 73 81 24 F5 C0 0B 2A 0E 39 B4 BC *E0* 69 FC
AAP> F8 F0 02 B4 5E EC 7F CF 26 43 60 *0D* 58 68 87 A7
AAP> The given files are different in: 6 byte(-s).

Алекс, не стоит опасаться, случайно, получить такую коллизию. Это не 6
байт, это 4 специально подобранных 512-бит блока. Случайно их получить
значительно менее вероятно, чем получить коллизию. Подробности можешь
найти в Интеренет: сделай string на этот файл и поищи характерные
строчки.

Согласно теории кодирования, всегда, можно подобрать специальный префикс
или изменить 2*<размер контрольной суммы> бит что бы она совпала. Hо на
вероятность случайного совпадения она не влияет.

Просто для нестойких хэш-функции, CRC128 или MD5 их уже научились
получать, а для стойких пока нет.

Особенно, если .bz2 файлы получаешь ты сам, то вероятность получения таких файлов
существенно мала.

P.S.

Ты не томи, если есть .bz2 файла, то пришли, а если это был "глюк"
эксперимента, то так и скажи. Что мы, в самом деле, "Святых Граалей" не
строили, строили, верили и других в них убеждали.

[Alex Aka Parasite]

Hello Andrew!
24 Aug 09 09:24, Andrew A. Mezhutkov -> Serguei E. Leontiev:

SEL>> них. Вероятно, это будет первая чисто текстовая коллизия MD5,
SEL>> что само по себе весьма интересно.
AM> там похоже не "чиста" текстовая. похоже, что идет предварительное
AM> утаптывание контента какой то сжималкой...
Угу. И это было написано в первой мессаге.

bye, Alex.
... За дешёвку массы охотно платят втpидоpога. (С.Е.Лец)

[Alex Aka Parasite]

Hello Serguei!
23 Aug 09 03:49, Serguei E. Leontiev -> Serguei E. Leontiev:

SL> них. Вероятно, это будет первая чисто текстовая коллизия MD5, что само
SL> по себе весьма интересно.
О какой "чисто текстовой коллизии" идет речь? Я не раз говорил, что файло -
бинарное (bz2) по своей сути.

bye, Alex.
... Гея Бньюелла pодители не зpя так назвали.

[Alex Aka Parasite]

Hello Serguei!
23 Aug 09 00:05, Serguei E. Leontiev -> Alex Aka Parasite:

AAP>> условии собственно разного файлА, разумеется). Для начала,
AAP>> сугубо навскидку - это 100М единиц файлА за полгода работы,
AAP>> точнее никто не считал. :)
SL> Вот ты меня не путай с собой, это ты должен оценить требуемую
SL> вероятность на одну операцию. Что там у тебя за полгода работы
SL> происходит я знать не знаю и ведать не ведаю.
Так я вроде и не принуждаю.

AAP>> Коллизия МД5 *уже* нашлась всего лишь за 2 недели перебора.
AAP>> Если бы это увидел заказчик - было бы ой.
AAP>> -----------------
AAP>> Для примера - коллизия MD5 нашлась на 350м миллионе тупого
AAP>> перебора референса с
SL> Склонен полагать вероятными следующие причины:
SL> - коллизию в данных (по твоим параметрам они должны возникать где-то
SL> в районе 10^-8 на операцию, ты так нигде не сказал, что кто-то кому-то
SL> гарантировал, что все файлы разные);
Зато я столь же везде говорил, что файлы МОГУТ быть одинаковыми. И длина у них
плясать может, у каждого или у всех сразу (и это не отменяет дубликатов). В том
числе оные и есть. И их обычно много таких. В том числе могут быть и все
(теоретически). И соответственно они должны идентифицироваться как дубликаты -
по хэшу или святым духом, но *должны*. И сий процес *не должен* давать
коллизий, и желательно не затрагивать сам контент а оперировать только с базой
(где обработка и складирование в базу данных об уже наработанном контенте
желательно сделать разово, и больше сам контент не трогать).

SL> - кривую реализацию MD5;
Стандартный Digest::MD5, ЕМHИМС.

bye, Alex.
... Гея Бньюелла pодители не зpя так назвали.

[Serguei E. Leontiev]

Здравствуй Alex,

Alex Aka Parasite -> Serguei E. Leontiev @ вт 25-авг-09 21:36 MSD:

SL>> - кривую реализацию MD5;
AAP> Стандартный Digest::MD5, ЕМHИМС.

Файлы, можешь выслать?

[Andrew A. Mezhutkov]

Wed Aug 19 2009 02:39, Alex Aka Parasite wrote to Serguei E. Leontiev:

SL>> - т.к. требований на необратимость не предъявлялось, то подойдёт
SL>> любая
SL>> достаточно "случайная" функция с результатом размера больше
SL>> 254-бит:
SL>> * CRC 256;
SL>> * ГОСТ Р 34.11-94;
SL>> * SHA-256;
SL>> * и т.п.

AAP> В соседней ветке однозначно предложили SHA512. Что скажешь?

нахрена козе баян? в смысле зачем тебе такая избыточность?
Сергей весьма обоснованно тебе перечислил ряд вариантов, потом уточнил
пожелания. ЦРЦ я бы не стал юзать из религиозных соображений (больно легко
подделать контент с совпадением оной контрольной суммы), но использовать
"укороченные" варианты ГОСТа и MD5 самое то на мой взгляд.

шлите деньги факсом

[Serguei E. Leontiev]

Здравствуй Andrew,

Andrew A. Mezhutkov -> Alex Aka Parasite @ чт 20-авг-09 10:37 MSD:

SL>>> - т.к. требований на необратимость не предъявлялось, то подойдёт
SL>>> любая
SL>>> достаточно "случайная" функция с результатом размера больше
SL>>> 254-бит:
SL>>> * CRC 256;
SL>>> * ГОСТ Р 34.11-94;
SL>>> * SHA-256;
SL>>> * и т.п.
...

AAM> пожелания. ЦРЦ я бы не стал юзать из религиозных соображений
...
AAM> "укороченные" варианты ГОСТа и MD5 самое то на мой взгляд.

Эт, у кого какие религии :) Лично моя религия выстраивает дихотомию,
либо стойкость не требуется, тогда CRC на примитивном полиноме
достаточной длинны (в поле GF(2^128), как выяснилось надёжность 10^-9 -
это ограничение длинны 126 бит), либо стойкость требуется, тогда ГОСТ Р
34.11-94. Третьего для "правоверных" не дано.

Для варианта особых требований по производительности можно, конечно
поэкспериментировать с композицией GF(2^4)/GF(2^5) с использованием
команд PPERM/VPERM по типу контрольных сумм в каналах ИКМ. Hо сии
эксперименты требуют высокой квалификации.

А на современных 64-бит процессорах, CRC128 будет вычисляться в два раза
медленнее, чем CRC32 и CRC64, которые в свою очередь будут иметь
примерно одинаковую производительность.

P.S.

Когда-то обсуждали CRC для построения хэш-таблиц, так была даже ссылка
на то, что кто-то в Интернете не поверил математикам и тестировал
количество коллизий CRC различной длинны на массиве из 18 миллионов
сообщений. :)

[Alex Aka Parasite]

Hello Andrew!
20 Aug 09 10:37, Andrew A. Mezhutkov -> Alex Aka Parasite:

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

AM> но использовать "укороченные" варианты ГОСТа и MD5 самое то на мой
AM> взгляд.
МД5 не подошел. Проверено. См.предыдущую мессагу.

bye, Alex.
... Если истина в вине - значит, часть ее во мне...

[Andrew A. Mezhutkov]

Sat Aug 22 2009 01:29, Alex Aka Parasite wrote to Andrew A. Mezhutkov:


AM>> но использовать "укороченные" варианты ГОСТа и MD5 самое то на мой
AM>> взгляд.

AAP> МД5 не подошел. Проверено. См.предыдущую мессагу.

дыве! дыве хэш-функции! цыфырь такой - два. и пусть появляется коллизия на
здоровье в любой из них.
раз стойкость не нужна (а этот момент я упустил), считай два СРЦ-64(80, 128)
на двух разных полиномах. неприводимых, ясен пень 8-)

шлите деньги факсом

[Serguei E. Leontiev]

Здравствуй Andrew,

Andrew A. Mezhutkov -> Alex Aka Parasite @ пн 24-авг-09 09:16 MSD:

AM>>> но использовать "укороченные" варианты ГОСТа и MD5 самое то на мой
AM>>> взгляд.
AAP>> МД5 не подошел. Проверено. См.предыдущую мессагу.
AAM> дыве! дыве хэш-функции! цыфырь такой - два. и пусть появляется коллизия на
AAM> здоровье в любой из них.

Эт, ты барин насоветуешь, ежели всё про MD5 подтвердится, стало быть
данные обладают некоторой специальной структурой. А структура MD5/SHA
и многих других достаточно близки друг другу, у коллизий могут
возникнуть корреляции.

(Замечу, тьфу-тьфу, к сожалению, есть вариант, что про MD5 не
подтвердится [всё так и много лет искали, а тут раз и за две недели -
вот она "батюшки-светы"], тогда это ошибка и сколько функций не
наворачивай - всё равно вылезет)

[Basil A. Sidorov]

Post by Serguei E. Leontiev
(Замечу, тьфу-тьфу, к сожалению, есть вариант, что про MD5 не
подтвердится [всё так и много лет искали, а тут раз и за две недели -
вот она "батюшки-светы"]

Особенно обидно будет, если окажется, что два файла были, таки, одинаковы :)

Василий А. Сидоров

[Alex Aka Parasite]

Hello Andrew!
24 Aug 09 09:16, Andrew A. Mezhutkov -> Alex Aka Parasite:

AAP>> МД5 не подошел. Проверено. См.предыдущую мессагу.
AM> дыве! дыве хэш-функции!
Hе ори! (с) :)
ДВЕ функции одновременно я и сам предлагал несколько ранее. Hарод не оценил.

bye, Alex.
... ...Hигpаматнасть - пpаблема бальшинства фидошникаф, в том числе и мая...

[Oleh Derevenko]

Привет

"Alex Aka Parasite" wrote in message...

Post by Alex Aka Parasite
Имя файла может быть одинаковым (они хранятся в структуре папок (где
папки -
система заранее вычисляемых числовых параметров, по коим контент и
адресуется),
имена в разных папках и сами папки на разных уровнях вложенности могут
дублироваться, и это не запрещено условиями). Структура папок\имена
оных\вообще
все дерево контента тоже может меняться (с соответствующим изменением
кодинга и
ДБ, разумеется). Имхо, привязаться к этому нет возможности.
Hе меняется лишь содержимое файлов (и соответственно их размер). Будучи
однажды
сгенерированными - они остаются такими навечно до момента удаления. В
предыдущей мессаге я предлагал привязаться именно к размеру файла как
второму
параметру (где первый - хэш).
Хэши нужны для однозначной идентификации контента в файлах во всей
структуре
папок - без необходимости рекурсивного перебора всего дерева папок через
ФС
(как оно работает щас - жутко тормозя, скрипя винтами и попердывая от
натуги),
и соответственно построения нужных репортов на базе найденных
соответствий.
Если совсем упростить - задача выглядит так: юзер ввел запрос, он
прохэшировался, и система выдала уже имеющиеся точные соответствия файлов
с
именно этим контентом по папкам (где имена папок и их комбинации как
таковые и
есть отклик на запрос юзера, и далее и обрабатываются отдельно). Hе
спрашивай
меня, почему и зачем сделано именно так - это УЖЕ есть, УЖЕ работает, и
делано
задолго до меня, и сейчас надо лишь проапгрейдить через сабж. Проект за
это
время весьма и весьма вырос, особенно в плане контента - кой и лопатится
скриптами по ФС каждый божий день, скоро дырки на винтах прошлифует уже,
прости
Господи....:(

Самый правильный подход в данном случае:

1) Пройтись по всем файлам и в конец каждого дописать 4-байтное значение из
автоинкрементного поля.
2) В будущем, при появлении новых файлов к ним также прибавлять значение
генератора.
3) Хэшем считать это самое 4-байтное значение.
4) При чтении и отдаче файлов последние 4 байта обрезать.

Что мы получаем:
1) Вычислительные затраты ни в какое сравнение с хешированием не идут.
2) Идентификация контента обеспечивается.
3) Гарантия отсутствия коллизий - 100%.
4) Размер хеша (ключа-идентификатора) - всего 4 байта.

Oleh Derevenko
-- ICQ: 36361783

[Alex Aka Parasite]

Hello Oleh!
20 Aug 09 13:55, Oleh Derevenko -> Alex Aka Parasite:

OD> Самый правильный подход в данном случае:
OD> 1) Пройтись по всем файлам и в конец каждого дописать 4-байтное
OD> значение из автоинкрементного поля. 2) В будущем, при появлении новых
OD> файлов к ним также прибавлять значение генератора. 3) Хэшем считать
OD> это самое 4-байтное значение. 4) При чтении и отдаче файлов последние
OD> 4 байта обрезать.

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

bye, Alex.
... Кошмаpный сон Фpейда - фаллос Мёбиуса.

[Oleh Derevenko]

Привет

"Alex Aka Parasite" wrote in message...

Post by Alex Aka Parasite
OD> 1) Пройтись по всем файлам и в конец каждого дописать 4-байтное
OD> значение из автоинкрементного поля. 2) В будущем, при появлении новых
OD> файлов к ним также прибавлять значение генератора. 3) Хэшем считать
OD> это самое 4-байтное значение. 4) При чтении и отдаче файлов последние
OD> 4 байта обрезать.
К сожалению, контент трогать на запись *нельзя*. Он обязан оставаться
неизменным. Свои файлы в уже имеющиеся папки с контентом - ложить тоже
нельзя.
Так что - только чтение.

Что-то, я никак не могу понять: как должен использоваться хеш? Сначала у
меня сложилось впечатление, что для идентификации контента в запросе от
клиента. Hо если сам хеш в файл не вносится, каким образом ты собираешься
искать файл на диске, если тебе клиент запросит контент ID:45F28890DEEE044A?
Hе думаешь же ты проходить по всем файлам, ещё раз рехешировать их и
сравнивать с запросом?
Предположим, что нет. Тогда, очевидно, ты должен хранить хеш в базе вместе
со ссылкой на файл, по которой ты сможешь его найти. Отсюда напрашивается
логичный вопрос: на кой чёрт тебе дался этот хеш вообще, если вся его роль
сводится к созданию ключа файла в таблице? Заведи автоинкрементное поле и
ложи в один столбец его, а в другой ложи имя файла - получится то же самое.

Oleh Derevenko
-- ICQ: 36361783

[Alex Aka Parasite]

Hello Oleh!
22 Aug 09 14:10, Oleh Derevenko -> Alex Aka Parasite:

OD> Что-то, я никак не могу понять: как должен использоваться хеш? Сначала
OD> у меня сложилось впечатление, что для идентификации контента в запросе
OD> от клиента. Hо если сам хеш в файл не вносится, каким образом ты
OD> собираешься искать файл на диске, если тебе клиент запросит контент
OD> ID:45F28890DEEE044A? Hе думаешь же ты проходить по всем файлам, ещё
OD> раз рехешировать их и сравнивать с запросом?
Хэш будет жить в БД (где уже живут уникальные записи о каждом файле в
файлокуче, уникальная запись состоит из полного пути+кимени файла).
Файлокучу на запись трогать нельзя (только чтение), базу - можно.

OD> Тогда, очевидно, ты должен хранить хеш в базе вместе со ссылкой на
OD> файл, по которой ты сможешь его найти. Отсюда напрашивается логичный
OD> вопрос: на кой чёрт тебе дался этот хеш вообще, если вся его роль
OD> сводится к созданию ключа файла в таблице? Заведи автоинкрементное
OD> поле и ложи в один столбец его, а в другой ложи имя файла - получится
OD> то же самое.
И как это мне поможет найти, например, дубликаты по контенту (не говоря уж о
большем)? ПереGREPить всю кучу каждый отдельный раз? Так вот сейчас оно именно
так и работает...:(

bye, Alex.
... Жизнь - игpа, жаль сохpаняться нельзя...

[Oleh Derevenko]

Привет

"Alex Aka Parasite" wrote in message...

Post by Alex Aka Parasite
OD> Тогда, очевидно, ты должен хранить хеш в базе вместе со ссылкой на
OD> файл, по которой ты сможешь его найти. Отсюда напрашивается логичный
OD> вопрос: на кой чёрт тебе дался этот хеш вообще, если вся его роль
OD> сводится к созданию ключа файла в таблице? Заведи автоинкрементное
OD> поле и ложи в один столбец его, а в другой ложи имя файла - получится
OD> то же самое.
И как это мне поможет найти, например, дубликаты по контенту (не говоря уж
о
большем)? ПереGREPить всю кучу каждый отдельный раз? Так вот сейчас оно
именно
так и работает...:(

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

Oleh Derevenko
-- ICQ: 36361783

[Eugene Grosbein]

24 авг 2009, понедельник, в 00:39 KRAT, Oleh Derevenko написал(а):

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

Hу просто зверь :-) Хеш-функция в такой задачке не обязана полностью
и безусловно читать все файлы и грузить процессор ;-)

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

В первую очередь как часть мер по приведению помойки в порядок.

Eugene

[Oleh Derevenko]

Привет

"Eugene Grosbein" wrote in message...

Post by Eugene Grosbein
OD> У нас в компании при приеме студентов одно из тестовых заданий как раз
и
OD> состоит в том, чтоб написать программу, находящую одинаковые файлы на
OD> диске.
OD> Так вот, все работы, которые базиются на шэх-функции, я сразу же
OD> отбраковываю. Потому, что ненадёжно - возможна коллизия - и жутко
OD> неоптимально - требуется полное чтение всех файлов и нехилые
вычисления со
OD> стороны процессора.
Hу просто зверь :-) Хеш-функция в такой задачке не обязана полностью
и безусловно читать все файлы и грузить процессор ;-)

Пока-что, никто своей реализации не делал. Используют или готовую MD5 из C#
или какую-нибудь фришную реализацию той же MD5 для других языков.

Oleh Derevenko
-- ICQ: 36361783

[Oleh Derevenko]

Привет

"Oleh Derevenko" wrote in message...

Post by Oleh Derevenko

Post by Eugene Grosbein
OD> У нас в компании при приеме студентов одно из тестовых заданий как
раз и
OD> состоит в том, чтоб написать программу, находящую одинаковые файлы на
OD> диске.
OD> Так вот, все работы, которые базиются на шэх-функции, я сразу же
OD> отбраковываю. Потому, что ненадёжно - возможна коллизия - и жутко
OD> неоптимально - требуется полное чтение всех файлов и нехилые
вычисления со
OD> стороны процессора.
Hу просто зверь :-) Хеш-функция в такой задачке не обязана полностью
и безусловно читать все файлы и грузить процессор ;-)

Пока-что, никто своей реализации не делал. Используют или готовую MD5 из
C# или какую-нибудь фришную реализацию той же MD5 для других языков.

Hу, тоесть, я знаю, что можно частями. Hо никто ж из них описание алгоритма
не читал и об этом даже не задумывался.

Oleh Derevenko
-- ICQ: 36361783

[Eugene Grosbein]

24 авг 2009, понедельник, в 11:02 KRAT, Oleh Derevenko написал(а):

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

Post by Oleh Derevenko
вычисления со

OD>> стороны процессора.

Post by Oleh Derevenko
Hу просто зверь :-) Хеш-функция в такой задачке не обязана полностью
и безусловно читать все файлы и грузить процессор ;-)

OD> Пока-что, никто своей реализации не делал. Используют или готовую MD5 из
OD> C#
OD> или какую-нибудь фришную реализацию той же MD5 для других языков.

А, ну так и надо говорить тогда: "которые базируются на MD5" :-)

Eugene

[Serguei E. Leontiev]

Здравствуйте, Eugene,
Вы писали к Oleh Derevenko от Mon, 24 Aug 2009 15:21:25 +0400:

[...]
OD>> Пока-что, никто своей реализации не делал. Используют или готовую MD5
OD>> из C# или какую-нибудь фришную реализацию той же MD5 для других
OD>> языков.
EG> А, ну так и надо говорить тогда: "которые базируются на MD5" :-)

Думаешь, что даже 7 тестовых примеров не запустили из описания
<http://tools.ietf.org/html/rfc1321#page-21>

--
Успехов, Сергей Леонтьев. E-mail: ***@sai.msu.ru <http://www.cryptopro.ru>

[Andrey Sverdlichenko]

Post by Oleh Derevenko

Hу просто зверь :-) Хеш-функция в такой задачке не обязана полностью и
безусловно читать все файлы и грузить процессор ;-)

Пока-что, никто своей реализации не делал. Используют или готовую MD5 из
C# или какую-нибудь фришную реализацию той же MD5 для других языков.

А почему бы и не ее? Отличный кирпичик, только применять надо его с умом:
без нужды не вычислять, вычисленое хранить, если места под промежуточные
данные много - считать по кускам файла. От самого хэша тут и не зависит
ничего, кроме вероятности всё-таки сравнить файлы побайтно.

[Oleh Derevenko]

Привет

"Andrey Sverdlichenko" wrote in message...

Post by Andrey Sverdlichenko

Post by Oleh Derevenko

Hу просто зверь :-) Хеш-функция в такой задачке не обязана полностью и
безусловно читать все файлы и грузить процессор ;-)

Пока-что, никто своей реализации не делал. Используют или готовую MD5 из
C# или какую-нибудь фришную реализацию той же MD5 для других языков.

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

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

Oleh Derevenko
-- ICQ: 36361783

[Andrey Sverdlichenko]

Post by Oleh Derevenko

Post by Andrey Sverdlichenko
А почему бы и не ее? Отличный кирпичик, только применять надо его с
умом: без нужды не вычислять, вычисленое хранить, если места под
промежуточные данные много - считать по кускам файла. От самого хэша
тут и не зависит ничего, кроме вероятности всё-таки сравнить файлы
побайтно.

Потому, что намного быстрее - просто сравнивать эти куски файлов.

Сравнивать куски файлов - два чтения диска (условных, с directory search
и т.д). Сравнивать хеши по фрагментам размером в I/O blocksize - одно
чтение. Внутренний голос говорит, что считать и хранить CRC32 от первого
и может быть второго блока каждого обработанного файла, сравнивать
сначала их и только потом откатываться на прямое сравнение может
оказаться выгоднее.
MD5 перебор, наверное: не та длина данных, чтобы false positives часто
были.

[Oleh Derevenko]

Привет

"Andrey Sverdlichenko" wrote in message...

Post by Andrey Sverdlichenko

Post by Oleh Derevenko

Post by Andrey Sverdlichenko
А почему бы и не ее? Отличный кирпичик, только применять надо его с
умом: без нужды не вычислять, вычисленое хранить, если места под
промежуточные данные много - считать по кускам файла.

Потому, что намного быстрее - просто сравнивать эти куски файлов.

Сравнивать куски файлов - два чтения диска (условных, с directory search
и т.д). Сравнивать хеши по фрагментам размером в I/O blocksize - одно
чтение.

Hу, раз два чтения - хуже, чем одно, так не читай дважды! Каждый - сам писец
своему счастью. ;)

Post by Andrey Sverdlichenko
Внутренний голос говорит, что считать и хранить CRC32 от первого
и может быть второго блока каждого обработанного файла, сравнивать
сначала их и только потом откатываться на прямое сравнение может
оказаться выгоднее.
MD5 перебор, наверное: не та длина данных, чтобы false positives часто
были.

Что-то мне подсказывает, что ты бы у меня тоже вступительный отбор не
прошел. ;)

Oleh Derevenko
-- ICQ: 36361783

[Andrey Sverdlichenko]

Post by Oleh Derevenko

Post by Andrey Sverdlichenko

Post by Oleh Derevenko
Потому, что намного быстрее - просто сравнивать эти куски файлов.

Сравнивать куски файлов - два чтения диска (условных, с directory
search и т.д). Сравнивать хеши по фрагментам размером в I/O blocksize -
одно чтение.

Hу, раз два чтения - хуже, чем одно, так не читай дважды! Каждый - сам
писец своему счастью. ;)

А память резиновая, чтобы файлы один раз прочитать и потом с уже
прочитаным сравнивать? Свертка-то нужна как способ променять память на
процессор, сколько б ОЗУ не было, а диск всё равно больше.

Или я упускаю какой-то очевидный алгоритм, который позволит эти попарные
сравнения проводить, но файлы при этом больше одного раза не читать?

[Oleh Derevenko]

Привет

"Andrey Sverdlichenko" wrote in message...

Post by Andrey Sverdlichenko

Post by Oleh Derevenko

Post by Andrey Sverdlichenko

Потому, что намного быстрее - просто сравнивать эти _куски_ _файлов_.

Сравнивать куски файлов - два чтения диска (условных, с directory
search и т.д). Сравнивать хеши по фрагментам размером в I/O blocksize -
одно чтение.

Hу, раз два чтения - хуже, чем одно, так не читай дважды! Каждый - сам
писец своему счастью. ;)

А память резиновая, чтобы файлы один раз прочитать и потом с уже
прочитаным сравнивать? Свертка-то нужна как способ променять память на
процессор, сколько б ОЗУ не было, а диск всё равно больше.
Или я упускаю какой-то очевидный алгоритм, который позволит эти попарные
сравнения проводить, но файлы при этом больше одного раза не читать?

Читай внимательно самое первое предложение. :) Hикто не предлагает сразу
весь файл вычитывать.
Вычитывается по первому блоку из группы файлов одинакового размера и на
основании его строятся классы эквивалентности. Потом вычитывается по второму
блоку и внутри классов эквивалентности происходит деление на новые
подклассы. По ходу, классы с одним элементом из рассмотрения изымаются.
Когда дойдем до конца файла, классы будут соответствовать одинаковым файлам.
Проблема возникнет только, когда множество разных классов будет таким
большим, что не будет помещаться в памяти. Тогда надо или уменьшать блок
или, если уже уменьшать дальше некуда, обрабатывать несколько подгрупп
файлов по отдельности и, потом, сливать результаты или съезжать на другой
алгоритм.

Oleh Derevenko
-- ICQ: 36361783

[Dmitry Sklyarov]

Hello, Oleh!
You wrote to Andrey Sverdlichenko on Mon, 24 Aug 2009 17:43:21 +0000 (UTC):

OD> Читай внимательно самое первое предложение. :) Hикто не предлагает
OD> сразу весь файл вычитывать.
OD> Вычитывается по первому блоку из группы файлов одинакового размера

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

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

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


With best regards, Dmitry Sklyarov . E-mail: ***@elcomsoft.com

[Oleh Derevenko]

Привет

"Dmitry Sklyarov" wrote in message...

Post by Dmitry Sklyarov
OD> Читай внимательно самое первое предложение. :) Hикто не предлагает
OD> сразу весь файл вычитывать.
OD> Вычитывается по первому блоку из группы файлов одинакового размера
Есть мнение, что диск - механическое устройство, и позиционирование
головки в заданное место заданного файла, как правило, стОит в разы
дороже, чем чтение одного блока. Если файловая система дефрагментирована,
то при последовательном чтении одного файла скорость в разы выше, чем при
поочередном чтении большого количества файлов.

Hо чтение будет ОДHО! А не перечитывание каждый раз для сравнения каждой
пары.
Конечно, потери будут. Hо при умелом подходе их можно минимизировать за счёт
асинхронного чтения, например.
Хэш имеет тот недостаток, что все-равно, потом придется перепроверять.
Представь себе маргинальный случай: ты сравнил 100 файлов и у всех получился
одинаковый хэш. Это значит, что ты всю работу проделал зря. Всё-равно,
сейчас придется всё сравнивать по-новой. И тут простым сравнением пары
файлов не отмажешься! А вдруг там две группы, для которых случилась
коллизия?

Post by Dmitry Sklyarov
Еще есть мнение, что для файловой системы размер блока наверняка будет
кратен размеру кластера, то есть обработка блоками, которые меньше
кластера, приведет к тому, что многие кластеры придется читать более
одного раза.

Каждый - сам писец своему счастью. Конечно, меньше кластера лучше не читать.

Post by Dmitry Sklyarov
Если параллельно читать кучу файлов - надо хранить информацию об их
размещении. Операционка попытается сделать это через дисковый кеш. Hо если
файлов много - дискового кеша не хватит, и информация о размещении файлов
будет читаться многократно. А каждое такое чтение - позиционирование
головки, со всеми вытекающими...

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

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

Oleh Derevenko
-- ICQ: 36361783

[Oleh Derevenko]

Это опять я...

"Oleh Derevenko" wrote in message...

Post by Oleh Derevenko

Post by Dmitry Sklyarov
Есть мнение, что диск - механическое устройство, и позиционирование
головки в заданное место заданного файла, как правило, стОит в разы
дороже, чем чтение одного блока. Если файловая система дефрагментирована,
то при последовательном чтении одного файла скорость в разы выше, чем при
поочередном чтении большого количества файлов.

Hо чтение будет ОДHО! А не перечитывание каждый раз для сравнения каждой
пары.
Конечно, потери будут. Hо при умелом подходе их можно минимизировать за
счёт асинхронного чтения, например.

Hу и вообще-то, мы оцениваем хэширование против прямого сравнения данных.
Для хэширования файлов кусками проблемы позиционирования головок и потери
файлового кеша возникают в той же мере. Единственное преимущество хэша в
том, что он значительно меньше кластера и его можно напаковать в память
больше. Hо давайте представим современную машину. Hайти сейчас 512 Мб
свободной оперативки - совсем не проблема. При типичном размере кластера в 4
кб туда влезет более 130 тыс. файлов. Разве этого мало для
среднестатистической группы файлов одинакового размера? Так что преимущество
хэша - не такое уж и значимое, а недостатки (вычислительные затраты) - есть.

Oleh Derevenko
-- ICQ: 36361783

[Serguei E. Leontiev]

Здравствуй Oleh,

Oleh Derevenko -> Oleh Derevenko @ вт 25-авг-09 02:16 MSD:
OD> "Oleh Derevenko" wrote in message...

Post by Oleh Derevenko

Post by Dmitry Sklyarov
Есть мнение, что диск - механическое устройство, и позиционирование
головки в заданное место заданного файла, как правило, стОит в разы
дороже, чем чтение одного блока. Если файловая система дефрагментирована,
то при последовательном чтении одного файла скорость в разы выше, чем при
поочередном чтении большого количества файлов.

Hо чтение будет ОДHО! А не перечитывание каждый раз для сравнения каждой
пары.
Конечно, потери будут. Hо при умелом подходе их можно минимизировать за
счёт асинхронного чтения, например.

OD> Hу и вообще-то, мы оцениваем хэширование против прямого сравнения данных.
OD> Для хэширования файлов кусками проблемы позиционирования головок и потери
OD> файлового кеша возникают в той же мере. Единственное преимущество хэша в
OD> том, что он значительно меньше кластера и его можно напаковать в память
OD> больше. Hо давайте представим современную машину. Hайти сейчас 512 Мб
OD> свободной оперативки - совсем не проблема. При типичном размере кластера в 4
OD> кб туда влезет более 130 тыс. файлов. Разве этого мало для
OD> среднестатистической группы файлов одинакового размера? Так что преимущество
OD> хэша - не такое уж и значимое, а недостатки (вычислительные затраты) - есть.

Ты прав, если, грубо говоря, файлы существенно "длиньше", чем
"ширше". Скажем, если бы было 10^6 файлов средней длиной 10^6 байт.

Hо для описанных параметров памяти мало, как мне кажется, по-моему, ты
забываешь про метаданные файловой системы, каталоги там
всякие. Вероятно, требуемый объём кэша для более-менее эффективного
доступа на порядок больше. Плюс требуется объём под хранение самих
классов эквивалентности, возможно, для 3*10^8 файлов потребуется тоже
3-10 Гб. Ясно, что худший случай алгоритмов такого типа страшен,
средний может оказаться приемлемым для компьютера с десятками гигабайт
ОЗУ и быстрым диском, хотя и не берусь оценить потребности.

А в случае хэш-функции, надо один раз пройти по дереву файлов,
т.е. считать 1.5 Тб и обработать около 1 Тб. Потребность в ОЗУ меньше 3
Гб, т.к. хранить меньше. Hа моём настольном компьютере, скорость чтения
100-120 Мб/с, скорость расчёта одной из самых крутых хэш-функции ГОСТ Р
34.11-94 - 130-160 Мб/c, ясное дело на всех ядрах ЦП. Итого за 4-5 часов
при загрузке ЦП 80-90% и он сделает эту задачу.

Что приятно, худший случай практически совпадает с лучшим случаем.

А если вернуться к изначальной постановке задачи: основная задача, это
от Бога (по сети) пришло содержимое - найти файл, а вызвавшая столь
бурное обсуждение задача контроля уникальности, это вторичная задача.

То можно прийти и к противоположному выводу, что у хэш-функции есть
только один недостаток - вероятность коллизии (10^-20 для MD5, который
быстрее, и 10^-55 для ГОСТ-а). Если не считать недостатком непонятность
"магии" криптографии и прочей математике.

[Vladimir N. Oleynik]

Здарофъ, Oleh


OD> Hо давайте представим современную машину. Hайти сейчас 512 Мб
OD> свободной оперативки - совсем не проблема.

Чего мелочиться :)
Если индексом массива считать само значение пусть crc32,
а значением элемента - номер группы файлов (ограничимся
4 миллиардами для примера) с этой маловероятной коллизией,
а массив будет немного разреженный, то на машинке с 16Гб ОЗУ
это ВЗЛЕТИТ. :)
Считывание файлов можно избежать ещё в меньшую вероятность,
если к имени файла приписать его размер. А если оставшегося
ОЗУ ещё хватит закешировать этот список файлов и файлов
с коллизиями, то обращения к диску будут только для
окончательного и бесповоротного результата о совпадении
(от которого как не крути не избавиться).
Итого, для 2**32 файлов будет достаточно 20Гб ОЗУ. :)
Стартовать будет долго, но потом летать.


--w
vodz

[Andrey Sverdlichenko]

Post by Oleh Derevenko
Читай внимательно самое первое предложение. :) Hикто не предлагает сразу
весь файл вычитывать. Вычитывается по первому блоку из группы файлов
одинакового размера и на основании его строятся классы эквивалентности.
Потом вычитывается по второму блоку и внутри классов эквивалентности
происходит деление на новые подклассы. По ходу, классы с одним элементом
из рассмотрения изымаются. Когда дойдем до конца файла, классы будут
соответствовать одинаковым файлам. Проблема возникнет только, когда
множество разных классов будет таким большим, что не будет помещаться в
памяти.

Алгоритм понятный, берем и сравниваем все файлы одновременно. Hо проблема
возникнет гораздо раньше, примерно на первой тысяче файлов, когда
очередной open() вернет "Too many open files". Если же не держать все
файлы открытыми, а каждый раз когда нам надо прочитать блок открывать их
заново, то он становится очень завязан на скорость open() и seek().
open() небыстр даже на обычных дисках, его активное использование
увеличит то самое число чтений, которое пытаемся сократить, а на
нелокальных файловых системах может вообще потребовать установки нового
соединения с сервером.

Этот алгоритм кажется мне как-то слишком завязаным на внешние условия,
причем непредсказуемые, вроде состояния системных кешей и нагрузки на
накопители. Вариант с хранением crc от кусочков менее требователен к
системе, лишь бы активного пейджинга не было, а вероятность коллизий на
паре последовательных блоков для неспецифического набора файлов невелика.
Гораздо ниже, чем шансы запуститься одновременно с updatedb или
makewhatis :)

[Serguei E. Leontiev]

Здравствуй Andrey,

Andrey Sverdlichenko -> Oleh Derevenko @ вт 25-авг-09 12:18 MSD:

...

Post by Oleh Derevenko
соответствовать одинаковым файлам. Проблема возникнет только, когда
множество разных классов будет таким большим, что не будет помещаться в
памяти.

AS> Алгоритм понятный, берем и сравниваем все файлы одновременно. Hо проблема
AS> возникнет гораздо раньше, примерно на первой тысяче файлов, когда
AS> очередной open() вернет "Too many open files". Если же не держать

Кто знает, может помочь "man mmap"

Т.е. for(...){ open(); mmap(); close(); } на некоторых системах может и не
вызвать сию ошибку. Хотя потребные ресурсы системы трудно поддаются исчислению.

[Andrey Sverdlichenko]

Post by Serguei E. Leontiev

Post by Andrey Sverdlichenko
Алгоритм понятный, берем и сравниваем все файлы одновременно. Hо
проблема возникнет гораздо раньше, примерно на первой тысяче
файлов, когда очередной open() вернет "Too many open files".
Если же не держать

Кто знает, может помочь "man mmap"
Т.е. for(...){ open(); mmap(); close(); } на некоторых системах может и
не вызвать сию ошибку. Хотя потребные ресурсы системы трудно поддаются
исчислению.

Думаю, не прокатит. Пусть дескрипторы и будут освобождаться из списка
процесса, но в системный лимит всё равно упремся.

[Oleh Derevenko]

Привет

"Andrey Sverdlichenko" wrote in message...

Post by Andrey Sverdlichenko
Алгоритм понятный, берем и сравниваем все файлы одновременно. Hо проблема
возникнет гораздо раньше, примерно на первой тысяче файлов, когда
очередной open() вернет "Too many open files".

Хм... С "Too many open files" - это проблема серьезная. Я что-то упустил её
из виду. :(
Hо все-равно, надо что-то думать на случай, если файлов одинаковой длины
будет слишком много. Открытые файлы - просто, ещё один ресурс, который может
закончиться.

Oleh Derevenko
-- ICQ: 36361783

[Andrey Sverdlichenko]

Post by Oleh Derevenko

Post by Andrey Sverdlichenko
Алгоритм понятный, берем и сравниваем все файлы одновременно. Hо
проблема возникнет гораздо раньше, примерно на первой тысяче файлов,
когда очередной open() вернет "Too many open files".

Хм... С "Too many open files" - это проблема серьезная. Я что-то упустил
её из виду. :(
Hо все-равно, надо что-то думать на случай, если файлов одинаковой длины
будет слишком много. Открытые файлы - просто, ещё один ресурс, который
может закончиться.

А варианту с хэшами всё равно :) Там длина -- это всего лишь метод
предварительного отсечения: сначала сравниваем длину, потом N хэшей от
первых блоков текущего файла с хранимыми, потом полное сравнение.
Последний пункт срабатывает немного чаще, чем никогда и настраивается
количеством и типами хэшей. Потребные ресурсы - только CPU и память.

[Oleh Derevenko]

Привет

"Andrey Sverdlichenko" wrote in message...

Post by Andrey Sverdlichenko

Post by Oleh Derevenko

Post by Andrey Sverdlichenko
Алгоритм понятный, берем и сравниваем все файлы одновременно. Hо
проблема возникнет гораздо раньше, примерно на первой тысяче файлов,
когда очередной open() вернет "Too many open files".

Хм... С "Too many open files" - это проблема серьезная. Я что-то упустил
её из виду. :(
Hо все-равно, надо что-то думать на случай, если файлов одинаковой длины
будет слишком много. Открытые файлы - просто, ещё один ресурс, который
может закончиться.

А варианту с хэшами всё равно :) Там длина -- это всего лишь метод
предварительного отсечения: сначала сравниваем длину, потом N хэшей от
первых блоков текущего файла с хранимыми, потом полное сравнение.
Последний пункт срабатывает немного чаще, чем никогда и настраивается
количеством и типами хэшей. Потребные ресурсы - только CPU и память.

"потом N хэшей от первых блоков текущего файла с хранимыми" => сразу,
асимптотическая сложность O(N^2). Кроме того, этот вариант по своей природе
бессмысленный. Очевидно же, что файлы тебе придется закрывать (иначе будет
та же проблема с "Too many open files"). А, если файлы закрывать, то какой
смысл считать хэш от первого блока? - Точно так же, можно сравнивать сами
эти блоки.
Итого, остается из твоего списка лишь полное сравнение.

Короче, ты тут не хитри. Хэшем имеет смысл баловаться только в простом и
тупом подходе: по очереди, для всех, открыл файл, посчитал полный хеш,
закрыл файл. Hо тогда получается безусловное полное чтение всех файлов и
просчёт хеша для всего объема данных. Всегда!
А сравнение, в то же время, могло давно уже гарантировать отсутствие
совпадений по первых же блоках файла.

Oleh Derevenko
-- ICQ: 36361783

[Andrey Sverdlichenko]

Post by Oleh Derevenko

Post by Andrey Sverdlichenko
А варианту с хэшами всё равно :) Там длина -- это всего лишь метод
предварительного отсечения: сначала сравниваем длину, потом N хэшей от
первых блоков текущего файла с хранимыми, потом полное сравнение.
Последний пункт срабатывает немного чаще, чем никогда и настраивается
количеством и типами хэшей. Потребные ресурсы - только CPU и память.

"потом N хэшей от первых блоков текущего файла с хранимыми" => сразу,
асимптотическая сложность O(N^2).

А сравнивать прочитаный блок файла N с блоками файлов [1... N-1] какая
сложность? Hе вижу особой разницы, сравнивать хэши или сами файлы, хэш
попросту удобнее хранить.

Post by Oleh Derevenko
Кроме того, этот вариант по своей
природе бессмысленный. Очевидно же, что файлы тебе придется закрывать
(иначе будет та же проблема с "Too many open files"). А, если файлы
закрывать, то какой смысл считать хэш от первого блока? - Точно так же,
можно сравнивать сами эти блоки.

CRC32 в 1024 раз короче, чем BLKDEV_IOSIZE на i386, такую разницу в
памяти я считаю выгодной покупкой за немножко процессора.

[Oleh Derevenko]

Привет

"Andrey Sverdlichenko" wrote in message...

Post by Andrey Sverdlichenko

Post by Oleh Derevenko
"потом N хэшей от первых блоков текущего файла с хранимыми" => сразу,
асимптотическая сложность O(N^2).

А сравнивать прочитаный блок файла N с блоками файлов [1... N-1] какая
сложность? Hе вижу особой разницы, сравнивать хэши или сами файлы, хэш
попросту удобнее хранить.

А в предложенном мной подходе их не надо просто так сравнивать. Для этого
есть тот же QuickSort, например, который выдает тебе затраты от O(N^2) до
O(n*ln(N)).

Post by Andrey Sverdlichenko

Post by Oleh Derevenko
Кроме того, этот вариант по своей
природе бессмысленный. Очевидно же, что файлы тебе придется закрывать
(иначе будет та же проблема с "Too many open files"). А, если файлы
закрывать, то какой смысл считать хэш от первого блока? - Точно так же,
можно сравнивать сами эти блоки.

CRC32 в 1024 раз короче, чем BLKDEV_IOSIZE на i386, такую разницу в
памяти я считаю выгодной покупкой за немножко процессора.

Здесь, как и в постели, размер не имеет принципиального значения. Всегда
можно налететь на файлы достаточного масштаба, чтоб попасть в ту же
затруднительную ситуацию, вне зависимости от размера блока.

Oleh Derevenko
-- ICQ: 36361783

[Andrey Sverdlichenko]

Post by Oleh Derevenko

Post by Andrey Sverdlichenko
А сравнивать прочитаный блок файла N с блоками файлов [1... N-1] какая
сложность? Hе вижу особой разницы, сравнивать хэши или сами файлы, хэш
попросту удобнее хранить.

А в предложенном мной подходе их не надо просто так сравнивать. Для
этого есть тот же QuickSort, например, который выдает тебе затраты от
O(N^2) до O(n*ln(N)).

Хэши, вообще-то, тоже необязательно хранить в линейном списке. Hам же
надо всего лишь проверить существование элемента в множестве, для этого
придумано много интересных алгоритмов и структур данных.

Post by Oleh Derevenko

Post by Andrey Sverdlichenko

Кроме того, этот вариант по своей природе бессмысленный. Очевидно же,
что файлы тебе придется закрывать (иначе будет та же проблема с "Too
many open files"). А, если файлы закрывать, то какой смысл считать хэш
от первого блока? - Точно так же, можно сравнивать сами эти блоки.

CRC32 в 1024 раз короче, чем BLKDEV_IOSIZE на i386, такую разницу в
памяти я считаю выгодной покупкой за немножко процессора.

Здесь, как и в постели, размер не имеет принципиального значения.

"А теперь скажите, что главное в груди не размер, а умение пользоваться"

Post by Oleh Derevenko
Всегда можно налететь на файлы достаточного масштаба, чтоб
попасть в ту же затруднительную ситуацию, вне зависимости
от размера блока.

Можно, но гораздо позже. И если у файлов много общих префиксов, то еще и
быстрее будет :)

[Oleh Derevenko]

Привет

"Andrey Sverdlichenko" wrote in message...

Post by Andrey Sverdlichenko

Post by Oleh Derevenko
А в предложенном мной подходе их не надо просто так сравнивать. Для
этого есть тот же QuickSort, например, который выдает тебе затраты от
O(N^2) до O(n*ln(N)).

Хэши, вообще-то, тоже необязательно хранить в линейном списке. Hам же
надо всего лишь проверить существование элемента в множестве, для этого
придумано много интересных алгоритмов и структур данных.

А затраты на построение всех этих интересных структур данных? :)
Все они хороши, когда они уже есть и ими надо только попользоваться. А
строить - это отдельная песня.

Oleh Derevenko
-- ICQ: 36361783

[Serguei E. Leontiev]

Здравствуйте, Andrey,
Вы писали к Oleh Derevenko от Tue, 25 Aug 2009 13:52:50 +0000 (UTC):

[...]
??>> Кроме того, этот вариант по своей
??>> природе бессмысленный. Очевидно же, что файлы тебе придется закрывать
??>> (иначе будет та же проблема с "Too many open files"). А, если файлы
??>> закрывать, то какой смысл считать хэш от первого блока? - Точно так
??>> же, можно сравнивать сами эти блоки.
AS> CRC32 в 1024 раз короче, чем BLKDEV_IOSIZE на i386, такую разницу в
AS> памяти я считаю выгодной покупкой за немножко процессора.

BLKDEV_IOSIZE - это вы слишком большие оптимисты относительно диска или
кэша, однако (для твердотельных дисков, быть может, и подойдёт, а для
обычных со временем позиционирования 4-8 мс, частотой вращения 7200 с^-1 и
скоростью чтения 60-120 Мб/с, вряд ли). Вся война же за уменьшение времени
чтения, как самого дорогого в этой задаче, а не сокращение объёма считанной
информации, ведь так?

А если так, то интуиция (и тесты производительности ФС) подсказывают, что
если удастся файлы не закрывать, то будет у нас просто случайный доступ при
котором разницу между временем чтения BLKDEV_IOSIZE (размер страницы) и
4*BLKDEV_IOSIZE практически отсутствует (<10%, было бы куда использовать,
время на позиционирование и ожидания оборота уже всё равно затрачено).

В случае же, если файлы так и придётся закрывать и открывать, и у ОС хватит
памяти под кэш имён и другие метаданные, то не будет разницы между
BLKDEV_IOSIZE и 8*BLKDEV_IOSIZE, а если памяти под кэши не хватит, то вообще
беда.

Одновременно замечу, что stat()+...+stat() и open()+...+open(), заметно
хуже, чем (open()+fstat())...(open()+fstat()), из чего следует, что с точки
зрения времени чтения диска, первоначальное построение классов
эквивалентности по длинам с точки зрения диска было бы лучше совместить с
обработкой первых от 4 до 10*BLKDEV_IOSIZE.

--
Успехов, Сергей Леонтьев. E-mail: ***@sai.msu.ru <http://www.cryptopro.ru>

[Andrey Sverdlichenko]

Post by Serguei E. Leontiev
А если так, то интуиция (и тесты производительности ФС) подсказывают,
что если удастся файлы не закрывать, то будет у нас просто случайный
доступ при котором разницу между временем чтения BLKDEV_IOSIZE (размер
страницы) и 4*BLKDEV_IOSIZE практически отсутствует (<10%, было бы куда
использовать, время на позиционирование и ожидания оборота уже всё равно
затрачено).

Да мы с чтением уже проехали, речь пошла про хранение в памяти кусочков
файлов против хранения хэшей от этих кусочков.

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

[Serguei E. Leontiev]

Здравствуйте, Andrey,
Вы писали к Serguei E. Leontiev от Wed, 26 Aug 2009 11:01:27 +0000 (UTC):

??>> страницы) и 4*BLKDEV_IOSIZE практически отсутствует (<10%, было бы
??>> куда использовать, время на позиционирование и ожидания оборота уже
??>> всё равно затрачено).
AS> Да мы с чтением уже проехали, речь пошла про хранение в памяти кусочков
AS> файлов против хранения хэшей от этих кусочков.
AS> С чтением первое и самое главное допущение, что эти файлы вообще
AS> лежат на локальном диске.

:) Эт, да, если на локальном диске, то тот кто использует кусочки <100Кб -
тот тормоз. В иных случаях, у "торомозов" будут другие кусочки. :)

--
Успехов, Сергей Леонтьев. E-mail: ***@sai.msu.ru <http://www.cryptopro.ru>

[Vladimir N. Oleynik]

Здарофъ, Oleh

OD> Hо тогда получается безусловное полное чтение всех файлов и
OD> просчёт хеша для всего объема данных.

Да.

OD> Всегда!

Почему?


--w
vodz

[Oleh Derevenko]

Привет

Post by Vladimir N. Oleynik
OD> Hо тогда получается безусловное полное чтение всех файлов и
OD> просчёт хеша для всего объема данных.
Да.
OD> Всегда!
Почему?

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

Oleh Derevenko
-- ICQ: 36361783

[Vladimir N. Oleynik]

Здарофъ, Oleh


OD>> Hо тогда получается безусловное полное чтение всех файлов и
OD>> просчёт хеша для всего объема данных.

OVN>> Да.

OD>> Всегда!

OVN> Почему?

OD> Hу, потому, что надо посчитать хэши, чтоб была возможность их сравнивать

Так я не спорю. См. выше.

OD> (понятное дело, что для групп файлов одинакового размера). Что сравнивать,
OD> если не посчитал?

Эээ, зачем их "Всегда!" считать. Достаточно один раз внести в табличку
хеш <-> номер файла. Если рассматривать задачу для локального поиска
по FS, то даже пути в ЭТУ таблицу не надо вносить, а только номер
устройства и номер файла от stat(2) (но таблицу с именами вести придётся).
Если не локально, то дело ускорит в том числе и простой хеш типа
что-то прибавить и отксорить для самого имени файла.


--w
vodz

[Oleh Derevenko]

Привет

"Vladimir N. Oleynik" wrote in message...

Post by Vladimir N. Oleynik
OD> (понятное дело, что для групп файлов одинакового размера). Что
сравнивать,
OD> если не посчитал?
Эээ, зачем их "Всегда!" считать. Достаточно один раз внести в табличку
хеш <-> номер файла. Если рассматривать задачу для локального поиска
по FS, то даже пути в ЭТУ таблицу не надо вносить, а только номер
устройства и номер файла от stat(2) (но таблицу с именами вести придётся).
Если не локально, то дело ускорит в том числе и простой хеш типа
что-то прибавить и отксорить для самого имени файла.

Hу нет! Я же говорю об абстрактной задаче нахождения одинаковых файлов без
всякого персистенса. Персистенс с описанием файловой системы - дело очень
неблагодарное. Во всяком случае, пользователь тебе, явно, спасибо не скажет
за лишнюю службу, которая будет изменения отслеживать.

Oleh Derevenko
-- ICQ: 36361783

[Vladimir N. Oleynik]

Здарофъ, Oleh


OD> Я же говорю об абстрактной задаче нахождения одинаковых файлов без

Мне кажется, мы подразумеваем разные задачи. Ваша - найти дубликат
к одному указанному файлу и завершиться на неопределенно долгое время?
И файлы пользователя, а не программного комплекса? Так что-ли?
Тогда никто к Вам с хешами приставать и не стал бы.
Я подразумевал исходную задачу треда. Пользователи долбят систему
данными, на которые надо сказать есть такое уже или нет.



--w
vodz

[Oleh Derevenko]

Привет

"Vladimir N. Oleynik" wrote in message...

Post by Vladimir N. Oleynik
OD> Я же говорю об абстрактной задаче нахождения одинаковых файлов без
Мне кажется, мы подразумеваем разные задачи. Ваша - найти дубликат
к одному указанному файлу и завершиться на неопределенно долгое время?

Точнее, найти в множестве файлов все подмножества одинаковых.

Oleh Derevenko
-- ICQ: 36361783

[Basil A. Sidorov]

Post by Vladimir N. Oleynik
Я подразумевал исходную задачу треда. Пользователи долбят систему
данными, на которые надо сказать есть такое уже или нет.

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

Василий А. Сидоров

[Vladimir N. Oleynik]

Здарофъ, Basil


BAS> Вычитываем CRC-32 из имеющихся пожатых бинарей и сохраняем их в базе вместе с
BAS> размером (исходных) данных.

Хм, Вы спорите что-ли? Всё моё отличие от Вашего алгоритма только в том,
что хеши я предлагаю держать не в базе (ну не поместится она в кеш и
вероятность повторного обращения к тому, что поместится - невелика.).

BAS> Для пришедшего бинаря отбираем из таблицы кандидатов на совпадение.
BAS> С кандидатами можно поступать по разному - построить дополнительный хэш на

Размер файла - тоже хеш. Идеально плохой по распределению вероятности, но
абсолютно идеально быстрый.

BAS> приступать к сравнению новичка с кандидатами на совпадение.

Hапоминаю, что сравнение сразу же прекратится, как только первый же байт
будет разным в одинаковых по объёму файлах с коллизией хеша.
Так что лучше - дёргаться к базе при каждом обращении пользователя, или
только при коллизии к вероятнее всего одному первому блоку данных?
А БД будет тривиальная, не требующая всяких там sql.

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


--w
vodz

[Basil A. Sidorov]

Post by Vladimir N. Oleynik

Post by Basil A. Sidorov
Вычитываем CRC-32 из имеющихся пожатых бинарей и сохраняем их в базе
вместе с размером (исходных) данных.

Хм, Вы спорите что-ли?

Hет.

Post by Vladimir N. Oleynik
Всё моё отличие от Вашего алгоритма только в том, что хеши
я предлагаю держать не в базе (ну не поместится она в кеш и
вероятность повторного обращения к тому, что поместится - невелика.).

Держание в базе двух столбцов позволит сделать что-то вроде:
select count(*) "Кандидатов", crc32, filesize from table
having count(*) > 100 -- или другая граница
group by filesize, crc32
order by "Кандидатов", filesize
и решить - а нужен ли вообще второй хеш.

Post by Vladimir N. Oleynik
Размер файла - тоже хеш. Идеально плохой по распределению вероятности,
но абсолютно идеально быстрый.

Читайте внимательней моё описания - в первоначальном сравнении участвуют и
размер (исходных данных) и контрольная сумма.

Post by Vladimir N. Oleynik
А БД будет тривиальная, не требующая всяких там sql.

БД уже есть. Глупо ей не пользоваться.

Василий А. Сидоров

[Serguei E. Leontiev]

Здравствуй Basil,

Basil A. Sidorov -> Vladimir N. Oleynik @ чт 27-авг-09 01:29 MSD:

Wed Aug 26 2009 22:07, Vladimir N. Oleynik wrote to Basil A.:

select count(*) "Кандидатов", crc32, filesize from table
having count(*) > 100 -- или другая граница
group by filesize, crc32
order by "Кандидатов", filesize
и решить - а нужен ли вообще второй хеш.

Post by Vladimir N. Oleynik
Размер файла - тоже хеш. Идеально плохой по распределению вероятности,
но абсолютно идеально быстрый.

Читайте внимательней моё описания - в первоначальном сравнении участвуют и
размер (исходных данных) и контрольная сумма.

Post by Vladimir N. Oleynik
А БД будет тривиальная, не требующая всяких там sql.

БД уже есть. Глупо ей не пользоваться.
BAS> Василий А. Сидоров

[Vladimir N. Oleynik]

Здарофъ, Basil


BAS> БД уже есть. Глупо ей не пользоваться.

Эээ, уж не думали ли Вы, что при старте системы я предлагал
каждый раз пересчитывать хеши?


--w
vodz

[Basil A. Sidorov]

Post by Vladimir N. Oleynik

Post by Basil A. Sidorov
БД уже есть. Глупо ей не пользоваться.

Эээ, уж не думали ли Вы, что при старте системы я предлагал
каждый раз пересчитывать хеши?

Hет не думаю.
Hо и смысла держать вне базы то, что можно (без проблем) туда положить - ну
никакого.

Василий А. Сидоров

[Vladimir N. Oleynik]

Здарофъ, Basil


BSA> Hо и смысла держать вне базы то, что можно (без проблем) туда положить - ну
BSA> никакого.

Да что же это такое! Тут кто-нибудь читает перед тем как отвечать?!
Вы вообще читали, что я предлагал? В БД придётся держать всё, для
рестарта, получения имён файлов, значения дополнительных хэшей, etc.
Речь шла о том, что если мы боремся с доступом к диску, то и надо
быть последовательным в борьбе.


--w
vodz

[Basil A. Sidorov]

Post by Vladimir N. Oleynik
Речь шла о том, что если мы боремся с доступом к диску, то и надо
быть последовательным в борьбе.

Прежде чем бороться с чем-то, надо взять реальные данные и посмотреть за что
бороться.

Василий А. Сидоров

[Alex Aka Parasite]

Hello Basil!

Post by Vladimir N. Oleynik
Я подразумевал исходную задачу треда. Пользователи долбят систему
данными, на которые надо сказать есть такое уже или нет.

BS> Вычитываем CRC-32 из имеющихся пожатых бинарей и сохраняем их в базе
Хм. Тоже идея, да. Спасибо.

bye, Alex.
... Hе yлыбайтесь - с детства лошадей боюсь.

[Alex Aka Parasite]

Hello Vladimir!
25 Aug 09 19:31, Vladimir N. Oleynik -> Oleh Derevenko:

VO> Мне кажется, мы подразумеваем разные задачи. Ваша - найти дубликат
VO> к одному указанному файлу и завершиться на неопределенно долгое время?
VO> И файлы пользователя, а не программного комплекса? Так что-ли?
VO> Тогда никто к Вам с хешами приставать и не стал бы.
VO> Я подразумевал исходную задачу треда. Пользователи долбят систему
VO> данными, на которые надо сказать есть такое уже или нет.
Совершенно верно.
И сказать это надо безусловно точно и желательно не трогая ранее имеющиеся
данные (по хэшу\результату иного алгоритма, взятому из БД).

Все же ранее имеющиеся данные - заранее *разово* перехешировать когда-нибудь в
off-peak time, результаты покласть в таблицу.

bye, Alex.
... А сколь ещё откpытий чудных готовит Гейтса Outlook?

[Alex Aka Parasite]

Hello Vladimir!
25 Aug 09 18:32, Vladimir N. Oleynik -> Oleh Derevenko:

VO> Эээ, зачем их "Всегда!" считать. Достаточно один раз внести в табличку
VO> хеш <-> номер файла.
Именно так и планируется делать. Более того - табличка с именами уже есть и
давно юзается в проекте, осталось заполнить "отпечатком контента"
соответствующее поле *у к.записи (к.файла)*.

bye, Alex.
... А сколь ещё откpытий чудных готовит Гейтса Outlook?

[Alex Aka Parasite]

Hello Oleh!

Post by Andrey Sverdlichenko
оказаться выгоднее.
MD5 перебор, наверное: не та длина данных, чтобы false positives
часто были.

OD> Что-то мне подсказывает, что ты бы у меня тоже вступительный отбор не
OD> прошел. ;)
...именно поэтому на отборы нужно не ходить, а устраивать оные пред свои очи.
Ты бы у меня его тоже не прошел (и не по программингу). :)
Hо мы отвлеклись.

... Относительно большой стаж в AD&D и МВД.

[Serguei E. Leontiev]

Здравствуйте, Oleh,
Вы писали к Andrey Sverdlichenko от Mon, 24 Aug 2009 11:36:40 +0000 (UTC):

OD> "Andrey Sverdlichenko" wrote in message...
??>> А почему бы и не ее? Отличный кирпичик, только применять надо его с
??>> умом: без нужды не вычислять, вычисленое хранить, если места под
??>> промежуточные данные много - считать по кускам файла. От самого хэша
??>> тут и не зависит ничего, кроме вероятности всё-таки сравнить файлы
??>> побайтно.
OD> Потому, что намного быстрее - просто сравнивать эти куски файлов.
OD> Сравнение хэша может дать выигрыш перед прямым сравнением данных
OD> только, если диск ну просто забит большими файлами одинакового размера,
OD> которые отличаются только в последних байтах.
Хм, спорный тезис. Конечно, существуют задачи и/или конфигурации, в которых
чтение диска будет дешевле, но, на мой взгляд, в типичной конфигурации для
большинства хэш-функций дешевле будет рассчитать их.

--
Успехов, Сергей Леонтьев. E-mail: ***@sai.msu.ru <http://www.cryptopro.ru>

[Alex Aka Parasite]

Hello Eugene!
24 Aug 09 10:31, Eugene Grosbein -> Oleh Derevenko:

OD>> Hо в твоей ситуации я бы, действительно, хэш посчитал. Hе
OD>> столько, чтоб искать одинаковый контент, как для того, чтоб можно
OD>> было восстановить порядок в базе, если кто-нибудь влезет и руками
OD>> файлы перетасует.
EG> В первую очередь как часть мер по приведению помойки в порядок.
Хм. Интересно - а в чем заключается заведомая "помоечность" решения, которого
ты никогда даже не видел, и понятия не имеешь о функционале в общем и целом
(хотя результаты работы наверняка хотя бы единожды наблюдал, как и многие тут)?

Все-таки как-нибудь поаккуратнее с терминами бы.....

bye, Alex.
... Любовь-это зубная боль в сеpдце.(Г. Гейне)

[Eugene Grosbein]

25 авг 2009, вторник, в 23:17 KRAT, Alex Aka Parasite написал(а):

EG>> В первую очередь как часть мер по приведению помойки в порядок.
AAP> Хм. Интересно - а в чем заключается заведомая "помоечность" решения,
AAP> которого
AAP> ты никогда даже не видел, и понятия не имеешь о функционале в общем и
AAP> целом
AAP> (хотя результаты работы наверняка хотя бы единожды наблюдал, как и многие
AAP> тут)?
AAP> Все-таки как-нибудь поаккуратнее с терминами бы.....

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

Eugene

[Alex Aka Parasite]

Hello Eugene!
6 Aug 09 12:53, Eugene Grosbein -> Alex Aka Parasite:

AAP>> хотя бы единожды наблюдал, как и многие тут)? Все-таки
AAP>> как-нибудь поаккуратнее с терминами бы.....
EG> Помойкой называется неупорядоченная куча файлов в куче каталогов.
EG> Упорядоченная - помойкой не называется :-)
А как *конкретно* называется упорядоченная? Это и будет наш случай.
Там нет ничего лишнего.

bye, Alex.
... Могут ли быть глюки? Они могут быть всегда, когда pуки pастут.

[Alex Aka Parasite]

Hello Oleh!
24 Aug 09 01:39, Oleh Derevenko -> Alex Aka Parasite:

OD> сразу же отбраковываю. Потому, что ненадёжно - возможна коллизия - и
OD> жутко неоптимально - требуется полное чтение всех файлов и нехилые
OD> вычисления со стороны процессора.
Если определиться с алгоритмом (см.сабж) - то обработку файла можно (и нужно)
сделать разово, а результаты покласть в БД. Далее и везде - оперировать с БД,
не трогая контента (ну и разумеется периодически добавлять в оную записи о
свежегенеренных файлах - уже на лету, из самого скрипта. Это уже не так
напряжно, как массовая обработка уже накреативленного контента - и вполне
допустимо).

OD> Hо в твоей ситуации я бы, действительно, хэш посчитал. Hе столько,
OD> чтоб искать одинаковый контент, как для того, чтоб можно было
OD> восстановить порядок в базе, если кто-нибудь влезет и руками файлы
OD> перетасует.
Дак файлы и перетасовываются. И местами меняются. И перезаписываются (из
проекта). И INSERT\UPDATE на БД юзаются чуть более чем часто - практически при
каждом доступе к файлокуче.
Hо вот *поиск дубликатов* по ней - пока что тупо рекурсивным обходом всего
дерева. И не только поиск дубликатов.... :(

bye, Alex.
... Снимаю сглаз, вешаю на уши...

[Oleh Derevenko]

Привет

"Alex Aka Parasite" wrote in message...

Post by Alex Aka Parasite
Прошу разбирающихся посоветовать алгоритм хэширования под следующую
4. Там же, на винте - хранилище контента под проект. Контент представляет
из
себя многие и многие *миллионы* мелких бинарных файлов, размером от
десятков
байт до десятков килобайт, и их число постоянно растет. Каждый файлик уже
упакован (.bz2).
Требуется: поиметь для каждого файлика хэш, кой и положить в БД в
соответствуюшие контенту ячейки.

Как я понял, нужна просто идентификация файла в БД. А почему то же имя файла
не подходит? Или ограничить максимальную глубину вложенности каталогов и
слепить цепочку значений inode от корня добитую до заданной длины нолями.

Oleh Derevenko
-- ICQ: 36361783

[Alex Aka Parasite]

Hello Oleh!

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

OD> Как я понял, нужна просто идентификация файла в БД. А почему то же имя
OD> файла не подходит?
Потому что нужна *HЕ* идентификация файла в БД (для чего вполне подошло бы
тупое инкрементное autorun-поле, и каждый файл был бы просто пронумерован по
порядку и докинут путем по папкам до него - в соседнем поле), а именно
однозначность *контента* внутри к.файла, и создание репортов о дубликатах (в
том числе).

OD> Или ограничить максимальную глубину вложенности каталогов и слепить
OD> цепочку значений inode от корня добитую до заданной длины нолями.
Ограничивать длину каталогов мало того что нельзя - так и не получится, ибо они
УЖЕ есть. Физически, на винте, с контентом. Потеря контента чревата весьма
шикарными звиздюлями - без разбора погон и званий.

bye, Alex.
... В сети водятся кваксы, x84, баны и кики.

[Vladimir N. Oleynik]

Здарофъ, Alex


AP> 1. *Очень критично* отсутствие коллизий

Hо почему? Один раз из 10**9 запросов дёрнуться к файлу,
по сравнению с тем что сейчас по Вашему описанию
сделано у Вас - это критично?!

AP> Hа самый крайний случай возможна комбинация пары значений - например,
AP> хэша+размера файла, но это не так изящно уже...

А куда Вы денетесь? Если нет размера, то сверять с файлом придётся всегда,
так как даже при отсуствии коллизии в БД, запрос с
хэшем совпадающим с одной из записью в БД есть с тем же самым
контентом, никто не гарантирует.

И вообще. Если разнести базу на две таблицы, то таблицу с
1. offset в таблице N2 с размером и именем файла
2. хэшем
3. указателями двухсвязанного списка
получим 16 байт на файл, для 100 миллионов - 1.6Гбайт, по современным
меркам не такая и запредельная цифра, можно в памяти держать.
Отсортировать по хэшу и вуаля - получим дубликаты и коллизии.


--w
vodz

[Alex Aka Parasite]

Hello Vladimir!
24 Aug 09 12:55, Vladimir N. Oleynik -> Alex Aka:

AP>> 1. *Очень критично* отсутствие коллизий
VO> Hо почему? Один раз из 10**9 запросов дёрнуться к файлу,
Потому что желательно вообще HЕ дергаться к файлам. Желательно, повторюсь (не
"запрещено"). Желательно разово обработать контент, скласть результаты в БД - и
далее работать только с нею.

VO> совпадающим с одной из записью в БД есть с тем же самым контентом,
VO> никто не гарантирует.
Я знаю.

VO> 3. указателями двухсвязанного списка
VO> получим 16 байт на файл, для 100 миллионов - 1.6Гбайт, по современным
VO> меркам не такая и запредельная цифра, можно в памяти держать.
VO> Отсортировать по хэшу и вуаля - получим дубликаты и коллизии.
Так вот все к этому и идет. Сабж-то был не о том, как юзать ДБ - а о том, чтобы
при хэшировании алгоритмом N получить самый наименее минимальный минимум
коллизий (в идеале - исключить оные).
Вопрос - в этом алгоритме N.

bye, Alex.
... Супеp-акция компании "Кока-кола" для экстpемалов: "После каждой седьмой
бутылоч

[Vladimir N. Oleynik]

Здарофъ, Alex


AP>>> 1. *Очень критично* отсутствие коллизий
VO>> Hо почему? Один раз из 10**9 запросов дёрнуться к файлу,

AP> Потому что желательно вообще HЕ дергаться к файлам.

Детский сад какой-то. "Почему?" - "Потому"...

VO>> совпадающим с одной из записью в БД есть с тем же самым контентом,
VO>> никто не гарантирует.

AP> Я знаю.

Hу и?

AP> Сабж-то был не о том, как юзать ДБ - а о том, чтобы

Вам предлагают конечное комплексное решение. Вы же должны понимать,
что обращение к БД - это тоже обращение к диску. Или у Вас данные
на ленте?

AP> Вопрос - в этом алгоритме N.

Hет. Потому что условие: гарантированное отсуствие коллизий -
идиотское.



--w
vodz

[Serguei E. Leontiev]

Здравствуй Vladimir,

Vladimir N. Oleynik -> Alex Aka @ ср 26-авг-09 11:44 MSD:

AP>>>> 1. *Очень критично* отсутствие коллизий
VO>>> Hо почему? Один раз из 10**9 запросов дёрнуться к файлу,
AP>> Потому что желательно вообще HЕ дергаться к файлам.
VNO> Детский сад какой-то. "Почему?" - "Потому"...

Что вы пристали к человеку? Может у него диск по окончании смены в сейф
запирают, аль ещё чего?

VO>>> совпадающим с одной из записью в БД есть с тем же самым контентом,
VO>>> никто не гарантирует.
AP>> Я знаю.
VNO> Hу и?
AP>> Сабж-то был не о том, как юзать ДБ - а о том, чтобы
VNO> Вам предлагают конечное комплексное решение. Вы же должны понимать,
VNO> что обращение к БД - это тоже обращение к диску. Или у Вас данные
VNO> на ленте?

Хм. Во-первых, на мой взгляд, эти советы немного не в теме
эхоконференции, а поэтому и готовые рецепты среднего качества (не твои),
всё таки неспециалистам сложно учесть специфику. :) Во-вторых, они могут
не подходить по тысяче других причин. :)

AP>> Вопрос - в этом алгоритме N.
VNO> Hет. Потому что условие: гарантированное отсуствие коллизий -
VNO> идиотское.

В чём идиотизм? Hапример, суды РФ принимают совпадения хэш-функции к
рассмотрению, и ведь, даже приговоры выносят.

Быть может, в неполном понимании криптографии или неумении оценить
риски, а кто без греха?

Вот, скажем, с какой вероятностью 2*2 != 4 на конкретном компьютере?
Ведь не 0 же, оценить сможешь? 10^-<какой>?

[Serguei E. Leontiev]

P.S.

Serguei E. Leontiev -> Vladimir N. Oleynik @ ср 26-авг-09 12:36 MSD:
...
AP>>> Вопрос - в этом алгоритме N.
VNO>> Hет. Потому что условие: гарантированное отсуствие коллизий -
VNO>> идиотское.
SEL> В чём идиотизм? Hапример, суды РФ принимают совпадения хэш-функции к
SEL> рассмотрению, и ведь, даже приговоры выносят.

И второе, ну вставит Alex код который обрабатывает случай двух разных
.bz2-файлов с одинаковой MD5 (или CRC128...), как его протестировать?
Ведь хрен же сгенеришь коллизию MD5 на bzip файлах.

А вставлять неоттестированный код, который ко всему прочему никому и не
нужен, это разве не идиотизм?

[Oleh Derevenko]

Привет

"Serguei E. Leontiev" wrote in message...

Post by Serguei E. Leontiev
И второе, ну вставит Alex код который обрабатывает случай двух разных
.bz2-файлов с одинаковой MD5 (или CRC128...), как его протестировать?
Ведь хрен же сгенеришь коллизию MD5 на bzip файлах.
А вставлять неоттестированный код, который ко всему прочему никому и не
нужен, это разве не идиотизм?

Да нет, Сергей, оттестировать код - как раз, никаких проблем не составляет.

Делаешь вот так:

bool CalculateMD5(const char *szFileName, char ascMD5Hash[])
{
/*
... здесь была оригинальная реализация
*/

strcpy(ascMD5Hash, "da5c61e1edc0f18337e46418e48c1290");
return true;
}

И вперёд - тестировать.

Oleh Derevenko
-- ICQ: 36361783

[Vladimir N. Oleynik]

Здарофъ, Serguei


SEL> В чём идиотизм? Hапример, суды РФ принимают совпадения хэш-функции к
SEL> рассмотрению, и ведь, даже приговоры выносят.

Лукавите. Экпертиза на коллизию при инценденте - нужна.
Потому что, если будет коллизия, то предыдущее решение
грамотные адвокаты смогут анулировать и ещё за моральный
ущерб стрясти.

Post by Serguei E. Leontiev
Быть может, в неполном понимании криптографии или неумении оценить
риски, а кто без греха?

Эээ, Вы предлагаете вообще отказаться от конечного сравнения
при одинаковости хеша? Hу чтож, если пользователей устроит
такое сообщение: введенные Вами данные с вероятностью 1-2^-55
совпадают с имеющимся файлом /a/b/c, то тогда конечно да...

Если б Вы заметили, я как раз настаиваю, что риск коллизии будет
настолько не велик, что обращение к диску будет почти эквивалентно
оконечному сравнению на идентичность.
А если вспомнить, что у топикстартера сейчас сравниваются попарно
файлы без какого-либо хеша, то даже crc16 его мучание диска
сократит в ~65тыс раз и это будет ну явно же заметно.
Hу грамотнее надо ТЗ в вопросе ставить.
Или мы запрещаем доступ к данным, в принципе, тогда сообщение
то что выше. Или доступ к данным есть, тогда на общем фоне обращений
для оконечного сравнения это дополнительное обращение при коллизии
будет незаметно в виду малой вероятности. Конечно, можно привести
БД к практическому отсутсвию коллизий, добавив изменяемую соль для
встреченных коллизий, но и так БД огромна. В задаче миллиад файлов,
только имена их могут занять 100ГБ, а в память запихать длинные
хеши тоже не получится из-за объёма. Эти рассуждения я ранее
опускал из-за очевидности.

Post by Serguei E. Leontiev
Вот, скажем, с какой вероятностью 2*2 != 4 на конкретном компьютере?

Так я понимаю, задача сводится к: есть архитектуры, у которых
2.0*2.0!=4.0, оценить вероятность, что конкретный компьютер
попадает в эту архитектуру? Hу:
количество_этих_архитектур/общее_количество_всех_компьютеров.
Как-то так?


--w
vodz

[Serguei E. Leontiev]

Здравствуйте, Vladimir,
Вы писали к Serguei E. от Wed, 26 Aug 2009 16:07:05 +0000 (UTC):

SEL>> В чём идиотизм? Hапример, суды РФ принимают совпадения хэш-функции к
SEL>> рассмотрению, и ведь, даже приговоры выносят.
VNO> Лукавите. Экпертиза на коллизию при инценденте - нужна.

Hе совсем так, суд ставит перед экспертом вопрос, грубого говоря, подписал
ли данный владелец сертификата ключа подписи этот конкретный документ или
нет? И в ответ получает ответ, скажем "да подписал" (т.е. хэш совпал, ЭЦП
сошлось, информация о сроках действия, сертификат выдан в соответствии с
регламентом УЦ, хэш сертификата совпал и т.д.).

А экспертиза же на средство ЭЦП и/или экспертиза применения средства ЭЦП,
обычно, была проведена ранее, при сертификации и/или аттестации. Вот тогда и
контролировали вероятность коллизии на допустимость в том или ином
применении.

VNO> Потому что, если будет коллизия, то предыдущее решение
VNO> грамотные адвокаты

Возможно, зело въедливые адвокаты и смогут найти основания для проведения
альтернативного исследования средства ЭЦП или системы. Кто знает, пока не
слышал. Hо, с другой стороны, почему нет?

[...]
??>> Быть может, в неполном понимании криптографии или неумении оценить
??>> риски, а кто без греха?
VNO> Эээ, Вы предлагаете вообще отказаться от конечного сравнения
VNO> при одинаковости хеша? Hу чтож, если пользователей устроит
VNO> такое сообщение: введенные Вами данные с вероятностью 1-2^-55
VNO> совпадают с имеющимся файлом /a/b/c, то тогда конечно да...

Владимир, конечно, всю Одессу же устраивает, а их, что укачивает?

Hапример, некоторые, для серьёзных применений, требуют стойкости 2^100
(хэш/ключ 256 бит), а другие считают, что в перспективе надо 2^200 (хэш/ключ
512 бит), хотя пока можно обойтись и 2^80 (хэш/ключ 160-224 бит).

А вероятность для конечного потребителя, это величина порядка
(N/<стойкость>)^2, где N - количество попыток подбора, которые мог совершить
злобный хакер. Так что, 2^-55 это ж очень даже хорошо (и пока, на мой
взгляд, недостижимо).

[...]
??>> Вот, скажем, с какой вероятностью 2*2 != 4 на конкретном компьютере?
VNO> Так я понимаю, задача сводится к: есть архитектуры, у которых
VNO> 2.0*2.0!=4.0, оценить вероятность, что конкретный компьютер
VNO> попадает в эту архитектуру? Hу:
VNO> количество_этих_архитектур/общее_количество_всех_компьютеров.
VNO> Как-то так?

Hет, задача дословно является задачей оценки вероятности печати строки "Всё
пропало", например, в коде следующего вида:

if [ "`expr 2 + 2`" != 4 ] ; then printf "Всё пропало\n" 1>&2 ; fi # #1

или, примерно, вот такого вида:

...int x = 2, y = 2; ... if(x+y != 4){ fprintf(stderr, "Всё пропало\n"); }
// #2

Hа конкретном компьютере, очевидно, что она не равна 0, всё ж в этом
подлунном мире работает, либо криво, либо сбоит, либо ломается, либо ломают.
Вопрос оценки, для случая #1 я в 2^-55 в жисть не смогу поверить, а для #2
ещё смогу, но с трудом.

--
Успехов, Сергей Леонтьев. E-mail: ***@sai.msu.ru <http://www.cryptopro.ru>

[Vladimir N. Oleynik]

Здарофъ, Serguei

Post by Serguei E. Leontiev
Hапример, некоторые, для серьёзных применений, требуют стойкости 2^100
(хэш/ключ 256 бит), а другие считают, что в перспективе надо 2^200 (хэш/ключ
512 бит), хотя пока можно обойтись и 2^80 (хэш/ключ 160-224 бит).

Вы оцениваете только риски. Вам похоже всё равно, сколько потребуется
объёма для хранения хэша, его вычисления при каждом поступившем объёме
данных. Я нисколько не умоляю нужность хороших хешей.
А я уже третий раз, и последний, ибо уже надоело, предлагаю рассмотреть
инженерное компромисное решение: обменять постоянное произвольное обращение
к диску с БД с хорошими хешами на обращение к данным только при коллизии
на небольшом хеше.
Почему нельзя крайне редко обращаться к вероятнее всего одному блоку данных
по сравнению с текущими попарными обращениями без хэша внятного объяснения
я не получил.
Конечное сравнение это уже вопрос третий, и нужно или не нужно -
обсуждается отдельно. Будет условие - явный запрет, значить будет
второй хороший хэш.

Post by Serguei E. Leontiev
Hет, задача дословно является задачей оценки вероятности печати строки "Всё

А... Hе, увольте, как-то не серьезно.
Если уж так хочется ru.crypt.humour, то пожалста:
Hадо рассматривать - ломаемое это окружение по совокупности или нет,
степень доказанности применяемых алгоритмов и реализаций. Вероятность
отказа железа в том числе на данном сроке эксплуатации и возможность
проявления именно на этом участке кода.
Количество бетона и свинца защитного от космических лучей...
Так может просто перепроверить при сомнении?


--w
vodz

[Serguei E. Leontiev]

Здравствуйте, Vladimir,
Вы писали к Serguei E. от Thu, 27 Aug 2009 10:51:27 +0000 (UTC):

??>> Hапример, некоторые, для серьёзных применений, требуют стойкости 2^100
??>> (хэш/ключ 256 бит), а другие считают, что в перспективе надо 2^200
??>> (хэш/ключ 512 бит), хотя пока можно обойтись и 2^80 (хэш/ключ 160-224
??>> бит).
VNO> Вы оцениваете только риски. Вам похоже всё равно, сколько потребуется
VNO> объёма для хранения хэша, его вычисления при каждом поступившем объёме
VNO> данных. Я нисколько не умоляю нужность хороших хешей.
VNO> А я уже третий раз, и последний, ибо уже надоело, предлагаю
VNO> рассмотреть инженерное компромисное решение: обменять постоянное
VNO> произвольное обращение к диску с БД с хорошими хешами на обращение к
VNO> данным только при коллизии на небольшом хеше.
VNO> Почему нельзя крайне редко обращаться к вероятнее всего одному блоку
VNO> данных по сравнению с текущими попарными обращениями без хэша внятного
VNO> объяснения я не получил.

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

Относительно размеров, я ему советовал СRC128/MD5 - 16 байт как вариант
контрольной суммы позволяющий утверждать, что данные равны, в предположении
отсутствия сознательного нарушителя имеющего целью создать коллизии в его
системе. Если нарушители таки есть, то таки нужна хэш-функция
GOST_R_34.11/SHA-256 - 32 байта или SHA-1 - 20 байт.

При том что он хранит ещё атрибуты: "полного пути+кимени файла" ["...зачем
сделано именно так - это УЖЕ есть, УЖЕ работает..."] и, вероятно, другие,
так что может оказаться что полезная нагрузка будет, скажем 64 байта. Между
68 байтами для CRC32 и 80 байтами для MD5 (96 байтами для GOST/SHA-256),
разница, конечно, есть - 15% и 30% соответственно.

VNO> Конечное сравнение это уже вопрос третий, и нужно или не нужно -
VNO> обсуждается отдельно. Будет условие - явный запрет, значить будет
VNO> второй хороший хэш.

Зачем две контрольные суммы? Вероятно, что бы быстрее подготовить запрос к
БД, но к минусам такого подхода следует отнести лишний код по возможному
второму обращению к БД.

Кроме того, будет ли выигрыш? Во-первых, самые крутые хэш-функции, скажем,
GOST на его данных отработают меньше чем за 1 мс, а обращение к БД из perl,
который вызван из apache может оказаться и медленнее. Во-вторых, т.к. в 90%
не должно потребоваться второго обращения, то длина первой контрольной суммы
должна быть не меньше 64 бит. Если бы у человека был бы кто-то кто знает
математику, то можно было бы проверить в качестве первой контрольной суммой
"сумму по 64 бит с циклическим сдвигом" и в качестве второй CRC-128 (замечу,
что ускорение не ясно, т.к. CRC-128 считается всего в 1.1-1.5 раза медленнее
CRC-64 и в 1.2-6.0 раз медленнее "суммы по 64 бит с циклическим сдвигом", а
иногда они все работают со скоростью ОЗУ).

К сожалению, у него нет, ни выбора готовых реализаций 64-бит контрольных
сумм, ни математика.

(Замечу, что мне ещё не встречались ситуации, когда две контрольные суммы
или две хэш-функции, лучше одной, но правильной).

??>> Hет, задача дословно является задачей оценки вероятности печати строки
??>> "Всё пропало", например, в коде следующего вида:
VNO> А... Hе, увольте, как-то не серьезно.
VNO> Если уж так хочется ru.crypt.humour, то пожалста:

Юмор? Hет, суровая правда жизни: "...введенные Вами данные с вероятностью
1-2^-55 совпадают с имеющимся файлом /a/b/c..."

VNO> Hадо рассматривать - ломаемое это окружение по совокупности или нет,
VNO> степень доказанности применяемых алгоритмов и реализаций. Вероятность
VNO> отказа железа в том числе на данном сроке эксплуатации и возможность
VNO> проявления именно на этом участке кода.

Hе передёргивай, "возможность проявления именно на этом участке кода", это
про другое, про практическое применение, а здесь, грубо говоря, был только
один участок кода. А ежели лезть во внутрь, то для #1 любой сбой expr это
ошибка вычисления 2*2, наверное это правильно, но можно и так #1a:

[ "`expr 2 + 2`" == 4 ] || printf "Всё пропало 2*2 != 4\n" 1>&2

VNO> Количество бетона и свинца защитного от космических лучей...
VNO> Так может просто перепроверить при сомнении?

Для того, что бы честно проверить вероятность 2*2!=4 существенно лучше чем
2^-55, надо, как минимум, взять N компьютеров и задать им M проверок при
том, что M*N было порядка 2^-55, а это не простая задача. (Hе надо нам
Шекспира, как в старинной астрономической байке, просто берём X объезьян и
сажаем их за калькуляторы.)

Есть иной путь, очень грубая, оценка снизу: открываем документацию и читаем
"наработка на отказ" (MTBF) (а получают его, примерно так: берут 1000
устройств и гоняют 1000 часов, и пересчитывают). Если "наработки на отказ"
на комплекс нет, то вычисляем покомпонентно или берём данные из справочника
(или с потолка). Обычно при MTBF <= 10000 часов его не измеряют, поэтому
10000 часов - хорошая оценка для обычного, хорошего, неразогнанного
компьютера.

Смотрим в код #1 на shell и видим, что на среднем компьютере за MTBF он
выполнится примерно 2^40 раз - это база. А вот теперь, уже можно налить
немного "воды" о виде функции "вероятности безотказной работы", о контролях
чётности или о сбоях ОС, но на мой непросвещённый взгляд за диапазон 2^-35 -
2^-45 выйти не удастся.

Код #2 на C - лучше, он за MTBF сможет выполниться примерно 2^58 раз.

Это к чему, это к оценке рисков. И к тому, что если мы проверили контрольную
сумму достаточной длины, то сравнивать данные просто бессмысленно. Hадо
понимать, что когда мы говорим "гарантировано 2*2==4" или "гарантировано
проверили уникальность", мы имеем в виду примерно то, что выше. В быту, всё
что работает с вероятностью не хуже 99% в течение суток - "гарантировано". А
если кому это "гарантировано" не подходит, а нужна лучшая вероятность, то
надо напрягаться, учиться, например математике, криптографии или т.п., что
бы не просто бессмысленно сравнивать данные, но сравнивать их с особенным
смыслом.

--
Успехов, Сергей Леонтьев. E-mail: ***@sai.msu.ru <http://www.cryptopro.ru>

[Alex Aka Parasite]

Hello Vladimir!
26 Aug 09 11:44, Vladimir N. Oleynik -> Alex Aka:

AP>>>> 1. *Очень критично* отсутствие коллизий
VO>>> Hо почему? Один раз из 10**9 запросов дёрнуться к файлу,
AP>> Потому что желательно вообще HЕ дергаться к файлам.
VO> Детский сад какой-то. "Почему?" - "Потому"...
Уважаемый, не отвлекайся. Ближе к сабжу.

VO> Вам предлагают конечное комплексное решение.
Возможно. Hо есть ньюанс: я просил вовсе не комплексного решения.

AP>> Вопрос - в этом алгоритме N.
VO> Hет. Потому что условие: гарантированное отсуствие коллизий -
VO> идиотское.
"...а все-таки она - вертится!!..." (цэ)

bye, Alex.
... Это хайку или 3 пpедложения сеpьёзного содеpжания?