Производит ли sha-1 коллизию для входных сообщений размером менее 160 бит?

Question

У меня есть 128-битный идентификатор, который я хочу выполнить односторонним хэшированием, но я не хочу получать такой же дайджест для входного сообщения.Кто-нибудь знает, гарантированно ли sha-1, или альтернатива, не вызовет коллизий для набора сообщений меньше, чем его размер выходного дайджеста?Это, по крайней мере, теоретически возможно ...

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

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

Answer 1

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

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

Answer 2

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

Answer 3

Ваш идентификатор уникален и имеет 128 бит.

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

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

У вас не может быть обоих миров - вы не можете иметь необратимое отображение 1: 1 .Это невозможно.

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

AES имеет хороший блок длиной 128 бит, который будет генерировать 128 бит на выходе из 128 бит ввода, быстрее, чем старые алгоритмы (!), и широко доступендля большинства платформ и языков.Я предлагаю вам использовать AES для ваших целей.

Answer 4

Кто-нибудь знает, гарантированно ли sha-1 или его альтернатива не создает коллизий

Хеш-функции были разработаны так, чтобы не создавать коллизий, но ничто не "гарантировано".Напротив, гарантируется, что будут БУДУТ коллизии, потому что пространство сообщений практически неопределенно, в то время как у вас ограниченное число возможных хэшей.

SHA-1, однако было доказано, что коллизия, и это лучшее, на что вы можете надеяться.

Answer 5

Для достаточно больших размеров бит, я думаю, дискретное возведение в степень является функцией 1: 1, но инверсия невозможна в вычислительном отношении.Я не уверен, насколько "большой" требуется, хотя.Код для необычайно медленной (но концептуально понятной) реализации:

unsigned long spin_once(unsigned long dat)
{
  if (dat & 1)
    return (dat >> 1);
  return (dat >> 1) ^ SomeMagicNumber;
}

unsigned long hash(unsigned long dat)
{
  unsigned long i,ret;

  if (dat == 0xFFFFFFFF)
    return 0;
  ret = 1;
  for (i=0; i < dat; i++)
    ret = spin_once(ret);
}

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

Answer 6

Я не знаю, какие хеш-функции позволяют избежать коллизий, но, если вы не можете найти ответ здесь, хорошей отправной точкой может быть Perfect Hash Function в Википедии. С этой страницы:

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

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

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

Answer 7

Хеширование "маловероятно" для создания каких-либо дубликатов, но нет никаких гарантий. На с другой стороны, любая симметричная схема шифрования будет выдавать 128 бит на 128 бит, и гарантируем отсутствие дубликатов.

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

Answer 8

Согласно этой статье http://www.debian -administration.org / users / dkg / weblog / 48 ,

Федеральным агентствам США было предписано прекратить всеопора на SHA-1 к концу 2010 года

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

Answer 9

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

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