Коллизии sha256 ?

[Seman]

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

Как я понимаю "John The Ripper" работает тупо перебором, т.е. генерит по маске входные данные, вычисляет с них хеш, сравнивает с известным хешем и так пока не найдет такой хеш который совпадет с известным(из базы). (другого же просто не дано или нет?).

Дальше там в статье

Цитата:

Оказалось, что от 2347 до 4720 паспортов из файла db.sqlite считаются недействительными (разные цифры были получены в ходе сверки данных с разными версиями базы МВД — от 22 мая 2020 года и 3 июля 2020 года). Причем большая часть владельцев этих недействительных паспортов приняла участие в интернет-голосовании: 2060 из 2347 (22 мая) или 4233 из 4720 (3 июля).

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

[mihaild]

Seman в сообщении #1477528 писал(а):

Как вообще оценить вероятность коллизий при подобном переборе?

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

[EUgeneUS]

Seman
Это вполне понятная и известная атака.
1. Хотя количество значений хэша это $2^{256}$ - очень большое.
2. Но так как входные данные принимают очень малое количество значений (10 миллиардов всего)
3. То перебрать все входные данные потребует мало времени.

К вопросу о квалификации разработчиков.

[ipgmvq]

EUgeneUS в сообщении #1477685 писал(а):

К вопросу о квалификации разработчиков.

Полностью согласен. А ещё об этике: им, может быть, просто плевать на безопасность пользователей.

Seman в сообщении #1477528 писал(а):

долго наверное

По статье непонятно, конвертировались ли цифры номеров паспортов из ASCII в бинарный формат. Скорее всего нет. В ASCII они по 10 байтов, а в бинарном формате чуть более 4-х.
Считается относительно быстро даже на одном ядре, но нужно иметь очень много памяти 850 ГБ (или сохранять хэши на большое SSD), дальше сортировать и искать одинаковые. Прогнал на с 0 по 299 000 000 и коллизий не нашёл.
https://rextester.com/AIUR8703
(функцию len(set(_)) не использовал, чтобы избежать коллизий в объекте set Питона)

[Snegovik]

Данный материал вовсе не говорит против sha256, как собственно выше и сказали. Это вопрос "слабых паролей", на которые и нацелена работа программы John The Ripper, и небольшого исходного набора данных. Нужна была соль или еще какие-то меры, как правильно сказали вопрос к разработчикам алгоритма работы программы проверки данных. Что касается коллизий, то насколько я помню материал у хорошей хеш функции первая коллизия, с вероятностью 50%, должна встретится через $2^{N/2}$ операций перебора, где N размер выхода функции, т.е. для sha-256 через $2^{128}$ операций, а это число не просто огромно, оно трудно представимо (или даже вообще не представимо). Если же хешируются короткие данные, размером менее выхода самого хеша, то коллизий, насколько я понимаю, и вовсе быть не должно.

[slavav]

ipgmvq в сообщении #1477724 писал(а):

(функцию len(set(_)) не использовал, чтобы избежать коллизий в объекте set Питона)

Это замечание указывает на непонимание как работают множества в Питоне.

[ipgmvq]

slavav в сообщении #1481571 писал(а):

Это замечание указывает на непонимание как работают множества в Питоне.

У Вас не очень информативный комментарий, — доложу я Вам. Лично у меня он оставляет лишь впечатление, что Вы не знаете, как устроен тип set в Python.
Но я приглашаю Вас поделиться своим пониманием.
Для удобства привожу ниже исходный код для этого встроенного типа классической версии Питона CPython:
https://github.com/python/cpython/blob/ ... etobject.c
Предлагаю начать с поиска слова "collision" в комментариях исходного кода.

[mihaild]

ipgmvq в сообщении #1481584 писал(а):

Лично у меня он оставляет лишь впечатление, что Вы не знаете, как устроен тип set в Python.

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

[ipgmvq]

mihaild
Убедили. Как хорошо, что они об этом подумали.
Тогда код упрощаю:
https://rextester.com/ILXI31652

[ipgmvq]

Seman в сообщении #1477528 писал(а):

Можно конечно попробовать проверить, но это долго наверное.

Написал код. Требует POSIX-среды (Linux, macOS; может быть, кому удастся скомпилировать на Cygwin), OpenSSL и до 524 ГБ оперативной памяти. Прогнал ASCII-строки с 0000 000 000 по 9999 999 999 с лидирующими нулями в облаке на AWS — коллизий ни одной не нашёл.
Ссылка на код:
https://github.com/ipgmvq/sha256_collision_check