Может ли повториться хэш сумма?

Question

[za-open-source]

Может ли повториться хэш сумма ?

Answer 1

[Vindicar]

Да, это называется коллизия.
Идея хэш суммы в том, что она с пренебрежимо малой вероятностью повторится для похожих (sic!) входных строк.
Т.е. Если у тебя есть exe-шник и ты вычислил его хэш сумму - ты можешь подобрать другой файл с такой же хэш суммой. Но будет исчезающе малый шанс, что это тоже будет рабочий exe шник или вообще что-то распознаваемое, а не просто набор бинарного мусора.

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

Answer 2

[ky0]

Может. Называется - коллизия хэша.

Answer 3

[mayton2019]

Хеши бывают разной длины. От 8 бит до 512 бит. И в зависимости от сложности самой функции
и от разрядности возможны такие ситуации что для разных файлов вдруг хеш совпадает.

В криптографии отдельно изучают парадокс дней рождений (когда группа случайных людей порядка
20 человек вдруг имеет 50% вероятность нахождения пары людей с одинаковой датой рождения
вида MM/DD). Вобщем этот парадокс для криптунов - шибко важный и они носятся с ним везде
и любят обсуждать применительно к атакам на шифры и ЭЦП.

Кажется Брюс Шнайер предлагал свою метрику для ожидания коллизий в зависимости от длины
ключа.

В Java существовала атака на хеш-мап основанная на том что хеш-функция несовершеннаа
и может давать коллизии.

Для латиницы

public static int hashCode(byte[] value) {
        int h = 0;
        byte[] var2 = value;
        int var3 = value.length;
        for(int var4 = 0; var4 < var3; ++var4) {
            byte v = var2[var4];
            h = 31 * h + (v & 255);
        }
        return h;
    }

Насколько я понимаю ни к чему страшному атака не приводила. Просто хеш-мапа вырождалась
в список и некоторые тайм-критичные системы (Tomcat/Jetty) могли тормозить на отдаче хедеров.
Фиксилось это просто заменой бакетов хеш-табли на деревья при определенном условии. ТАм
было что-то вроде - если длина цепочки в бакете больше чем константа - то генерировать дерево.

Вобщем некоторые кибер-задроты не поленились и нашли такие строки которые дают одинаковые хеши.

Некоторые хеш-функции (CRC-32) обладают интересными свойствами. На диапазоне целых до 4 млрд
эта функция вообще дает 0 коллизий и точно отображает ключ в бакет. Кажется это свойства
тех полиномов на базе которых CRC вообще строятся. (Насчет CRC я точно не уверен. Мой приятель
этот факт проверял на С++).

Я честно говоря считал что в хешах уже все известно но периодически их придумывают новые с разными
свойствами. Вот для нужд биг-даты в 2008 был придуман Mur-mur https://en.wikipedia.org/wiki/MurmurHash

И еще примерно 9 лет назад один чел создал хеш-функцию xxhash которая якобы супер-быстрая
https://github.com/Cyan4973/xxHash но я не мерял. Такая себе функция-шустрик.

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