Являются ли первые 32 бита 160-битного хеша SHA1 приемлемой заменой хеша CRC32?

Question

Я работаю над проектом .NET 3.5, и мне нужно 32-битное хеш-значение. Похоже, что в классах .NET Cryptography отсутствуют какие-либо методы, которые возвращают 32-битный хеш (MD5 - 128 бит, SHA1 - 160 бит и т. Д.). Я реализовал класс CRC32, но обнаружил, что уже существующие функции хэширования SHA1 и MD5 работают намного быстрее.

Могут ли быть какие-либо проблемы (например, повышенная вероятность коллизий) со мной, использующим функцию хеширования SHA1 и просто разрывом первых 32 битов, которые будут сохранены в качестве моего хеш-значения?

Answer 1

Если вам не нужны дополнительные функции CRC32 (являющиеся линейным кодом), вам следует урезать вывод до 32 бит.

Является ли сокращение вывода некоторых криптографических хеш-функций вредом для его безопасности в отношении устойчивости к столкновениям - это проблема открытых исследований (существуют «неестественные» построенные примеры, если я правильно помню). Но NIST (вероятно, с одобрения АНБ) использовал технику резки, чтобы в любом случае получить SHA-224 от SHA-256 (см. статью о SHA в википедии ).

РЕДАКТИРОВАТЬ: CRC32 позволяет обнаруживать (и, возможно, исправлять) однобитовые ошибки, тогда как криптографическая хеш-функция должна иметь свойство, при котором вы не можете найти два входа с одинаковым хеш-значением.

Вам известен "парадокс дня рождения" (см. Снова википедию)? С 32-битной контрольной суммой вы ожидаете столкновения (то есть двух входов с одинаковым значением хеш-функции), когда у вас есть около 2 ^ 16 входов, и вы хотите хешировать еще много входов. (Перечитывая ваш комментарий, это может не быть проблемой для вас.)

Answer 2

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

Answer 3

Почему бы вам просто не использовать string.GetHashCode (). Он предназначен для вычисления 32-битного хеш-значения и создания нескольких коллизий с учетом реальных данных. Конечно, это небезопасно, но ваш вопрос не включает это как требование.

Answer 4

CRC32, вероятно, подходит для ваших нужд. Это обсуждалось в этом вопросе .

С точки зрения усечения примитива хеша, единственное широко используемое применение этого - псевдослучайная функция SSL / TLS (PRF) , которая используется для генерации ключей. Он использует HMAC, начальные числа и метки, чтобы генерировать столько байтов, сколько вам нужно, хешируя несколько раз, а затем обрезая до нужного количества байтов.

Что касается вашего конкретного вопроса, вы можете прочитать выходные данные хэша в Int32 и затем записать их вместе, если вы параноик:

static void Main()
{
    int xorCrc = GetHashedCrc(new SHA1Cng(), new byte[] {0xDE, 0xAD, 0xBE, 0xEF});
}

private static int GetHashedCrc(HashAlgorithm algorithm, byte[] bytesToHash)
{
    byte[] hash = algorithm.ComputeHash(bytesToHash);
    int totalInt32s = hash.Length/sizeof(int);
    int result = 0;
    for(int i = 0; i < totalInt32s; i++)
    {
        int currentInt = BitConverter.ToInt32(hash, sizeof(int)*i);
        result = result ^ currentInt;
    }

    return result;
}

Answer 5

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

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