2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Коллизии sha256 ?
Сообщение06.08.2020, 01:57 


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

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

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

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

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

 Профиль  
                  
 
 Re: Коллизии sha256 ?
Сообщение06.08.2020, 02:03 
Заслуженный участник
Аватара пользователя


16/07/14
8452
Цюрих
Seman в сообщении #1477528 писал(а):
Как вообще оценить вероятность коллизий при подобном переборе?
Считаем, что хеш в каждой точке - случайное число, выбранное равномерно из диапазона значений хеш-функции. Ну и поскольку размер нашего множества гораздо меньше корня из размера образа хеш-функции, то вероятность коллизий в нём мала.

 Профиль  
                  
 
 Re: Коллизии sha256 ?
Сообщение06.08.2020, 18:56 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Коллизии sha256 ?
Сообщение06.08.2020, 23:16 


27/06/20
337
EUgeneUS в сообщении #1477685 писал(а):
К вопросу о квалификации разработчиков.
Полностью согласен. А ещё об этике: им, может быть, просто плевать на безопасность пользователей.

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

 Профиль  
                  
 
 Re: Коллизии sha256 ?
Сообщение01.09.2020, 13:55 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Коллизии sha256 ?
Сообщение01.09.2020, 17:25 
Заслуженный участник


26/05/14
981
ipgmvq в сообщении #1477724 писал(а):
(функцию len(set(_)) не использовал, чтобы избежать коллизий в объекте set Питона)

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

 Профиль  
                  
 
 Re: Коллизии sha256 ?
Сообщение01.09.2020, 19:34 


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

 Профиль  
                  
 
 Re: Коллизии sha256 ?
Сообщение01.09.2020, 19:41 
Заслуженный участник
Аватара пользователя


16/07/14
8452
Цюрих
ipgmvq в сообщении #1481584 писал(а):
Лично у меня он оставляет лишь впечатление, что Вы не знаете, как устроен тип set в Python.
А у меня - ваш комментарий оставляет аналогичное впечатление. Коллизии влияют на эффективность, но не на корректность.
Собственно посмотрите по приведенной вами ссылке, как считается число элементов в set, как вставляются новые элементы, и что происходит при коллизиях.

 Профиль  
                  
 
 Re: Коллизии sha256 ?
Сообщение01.09.2020, 20:18 


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

 Профиль  
                  
 
 Re: Коллизии sha256 ?
Сообщение04.09.2020, 22:59 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group