Здравствуйте, vit0s, Вы писали:

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

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

Здравствуйте, uzhas, Вы писали:

U>важно понимать, что любая чексумма всегда ограничена по кол-ву значений (4 байта или 64 байта), а этой значит, что найдутся два набора байтов (возможно, очень длинных), отличающиеся одним битом, для которых чексумма совпадает.

U>ссылки по теме:
U>http://ru.wikipedia.org/wiki/SHA-1
U>http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Техническая поправочка — если полином CRC имеет одним из множителей (x+1), то НИКАКИЕ две последовательности, отичающиеся на один бит (ну или даже на нечетное колчество бит) не будут иметь одинаковой CRC. Об этом даже написано в вики, правда не в первых абзацах и несколько другими словами

Всем привет,

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

Заранее спасибо

Здравствуйте, vit0s, Вы писали:

V>может быть ненадежным
а что понимается под надежностью (со стороны вашей команды)? и зачем вам "надежность" в вашей задаче?
если вас интересует скорость то я бы предложил простой вариант с суммой всех байтов по модулю 256, этой чексуммой пользуются в FIX протоколе, например (CRC8)
если для вас это "ненадежно", то можно предложить crc16, crc32, md5, sha1

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

ссылки по теме:
http://ru.wikipedia.org/wiki/SHA-1
http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Здравствуйте, vit0s, Вы писали:

V>Всем привет,

V>Задача такова: нужно сеарилозвать массив экземпляров класса в файл и при чтении быть уверенным, что каждый объект записался успешно. Для этого с каждым объектом планируется писать в файл его чексумму чтобы потом при чтении объекта из файла понять корректно ли он был записан туда. Сначала в файл пишется чексумма, потом объект и так для каждого объекта.
V>Планировалось сначала использовать CRC32 алгоритм для вычисления чек-суммы, но мнения разделились ибо он может быть ненадежным для больших объектов. Я в этом всем шифровании не ас, поэтому решил спросить у общественности тут какой алгоритм для вычисления чексуммы (и вообще для этой задачи) подходит лучше с точки зрения производительности.

V>Заранее спасибо

http://www.cryptopp.com/

хеш функции:
SHA-1, SHA-2 (SHA-224, SHA-256, SHA-384, and SHA-512), SHA-3, Tiger, WHIRLPOOL, RIPEMD-128, RIPEMD-256, RIPEMD-160, RIPEMD-320

небезопасные или устаревшие алгоритмы для обратной совместимости и исторического значения:
MD2, MD4, MD5, Panama Hash, DES, ARC4, SEAL 3.0, WAKE-OFB, DESX (DES-XEX3), RC2, SAFER, 3-WAY, GOST, SHARK, CAST-128, Square

характеристики:
1. безопасность
2. скорость
3. применимость

К примеру, tiger tree hashing в некоторых p2p сетях (DC++) для идентификации именно одного файла. В торрентах используют SHA-1, хотя он теоретически небезопасен. Чем выше буква у SHA (1,2,3), тем алгоритм считается безопасней.

Вот здесь можете посмотреть скорость алгоритмов:
http://www.cryptopp.com/benchmarks.html

Что касается CRC32, то он гарантированно ненадёжен. Речь уже даже не о взломе, а о простом использовании в качестве уникального идентификатора.

Процессор Intel Core 2 1.83 GHz под Windows Vista в 32-битном режиме:

По ссылке жёлтым выделены нужные вам алгоритмы:

Algorithm    MiB/Second    Cycles Per Byte
CRC32           253             6.9
Adler32         920             1.9
MD5             255             6.8
SHA-1           153             11.4
SHA-256         111             15.8
SHA-512         99              17.7
Tiger           214             8.1
Whirlpool       57              30.5
RIPEMD-160      106             16.5
RIPEMD-320      110             15.9
RIPEMD-128      153             11.4
RIPEMD-256      158             11.1

Так же обращаю внимание на фразу:
Поддержка OpenMP была отключена, так что только одно ядро CPU было использовано для этого теста производительности.

Иными словами для увеличения производительности, если это допустимо, можно использовать:
1. параллельные вычисления в файле
2. вычисление за раз несколько файлов (для примера, пул потоков)

А теперь моё субъективное мнение, которое не основано на огромном опыте и многолетней работе в этой области, но говорит о том, как бы поступил именно я:

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

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

В случае, если бы нужна была некая гарантированная надёжность, то я бы остановился на:
SHA-256 — если бы нужен был небольшой хеш
и
SHA-512 — если бы хотел хеш чуть побольше (и ещё дайте мне таблетки от жадности)

Хотя если речь идёт о неком массиве, и никто никогда не смотрит на мои хеши, тогда MD5 в принципе нормальное решение. При прочих равных условиях CRC32 по сравнению с ним вообще не вариант.

Здравствуйте, vit0s, Вы писали:

V>Всем привет,

V>Задача такова: нужно сеарилозвать массив экземпляров класса в файл и при чтении быть уверенным, что каждый объект записался успешно. Для этого с каждым объектом планируется писать в файл его чексумму чтобы потом при чтении объекта из файла понять корректно ли он был записан туда. Сначала в файл пишется чексумма, потом объект и так для каждого объекта.
V>Планировалось сначала использовать CRC32 алгоритм для вычисления чек-суммы, но мнения разделились ибо он может быть ненадежным для больших объектов. Я в этом всем шифровании не ас, поэтому решил спросить у общественности тут какой алгоритм для вычисления чексуммы (и вообще для этой задачи) подходит лучше с точки зрения производительности.

V>Заранее спасибо

Git, например, использует в качестве хэшфункции SHA1 и ей хэшируется все — слепки данных, коммиты, и пр.

Здравствуйте, andyp, Вы писали:

A>Техническая поправочка — если полином CRC имеет одним из множителей (x+1), то НИКАКИЕ две последовательности, отичающиеся на один бит (ну или даже на нечетное колчество бит) не будут иметь одинаковой CRC. Об этом даже написано в вики, правда не в первых абзацах и несколько другими словами
не нашел цитату, но нашел ошибку в своих рассуждениях:
я же рассуждал так: пусть значения чексуммы принимает значения в диапазоне 0 <= checksum < M
рассмотрим все вектора v бит длиной M + 1, где ровно M нулей и одна единица.
набор чисел checksum(v) для всех таких векторов будет иметь дубликат, т.к. таких чисел ровно M + 1
возьмем те самые два вектора v1 и v2: checksum(v1) = checksum(v2)
они отличаются в двух позициях

верно ли тогда другое утверждение: любая checksum (с ограниченными значениями) не может застраховать от ошибки в данных в двух битах?

Здравствуйте, uzhas,

CRC — это хеш-функция. Для CRC32, например, имеем набор из 2^32 хеш-значений. Если рассматривать неограниченное количество M "входных" объектов, такое, что M сильно больше 2^32, то рано или поздно найдутся два различных объекта с одинаковой CRC.

Здравствуйте, Vlad_SP, Вы писали:

V_S>рано или поздно найдутся два различных объекта с одинаковой CRC.
согласен с этим высказыванием
я пытаюсь обосновать более сильное утверждение : найдутся достаточно похожие (расстояние Хэмминга = 2) объекты, для которых хеш будет одинаковый

Здравствуйте, uzhas, Вы писали:

U>Здравствуйте, andyp, Вы писали:

A>>Техническая поправочка — если полином CRC имеет одним из множителей (x+1), то НИКАКИЕ две последовательности, отичающиеся на один бит (ну или даже на нечетное колчество бит) не будут иметь одинаковой CRC. Об этом даже написано в вики, правда не в первых абзацах и несколько другими словами
U>не нашел цитату, но нашел ошибку в своих рассуждениях:
U>я же рассуждал так: пусть значения чексуммы принимает значения в диапазоне 0 <= checksum < M
U>рассмотрим все вектора v бит длиной M + 1, где ровно M нулей и одна единица.
U>набор чисел checksum(v) для всех таких векторов будет иметь дубликат, т.к. таких чисел ровно M + 1
U>возьмем те самые два вектора v1 и v2: checksum(v1) = checksum(v2)
U>они отличаются в двух позициях

U>верно ли тогда другое утверждение: любая checksum (с ограниченными значениями) не может застраховать от ошибки в данных в двух битах?

Верно для блоков начиная с определенной длины. Если блок короче определеннной величины, то все 2-х битовые паттерны вылавливаются. Я тут пишу о правильно выбранных полиномах.

PS там начинает играть роль, сколько 0 между единицами в паттерне ошибки. Как правило, CRC может исправить 2-битные ошибки, отстоящие друг от друга на 2^N — 1 бит (тут N — меньше чем число бит в CRC, зависит от выбранного полинома, максимально для так называемых примитивных полиномов)