Дано:

Некая хеш функция Ф()
Диапазон ее хешей от 00 до 99
Диапазон входных данных (паролей) - бесконечно (любая строка, файл)

(Функция взята искуственно для удобства пояснения)

Задача:

Найти пароль от ЛЮБОГО известного хеша этой функции Ф().

Решение (алгоритм)

Сгенерируем цепочку хешей где сами хеши будут паролями т.е.:
(Цепочка 1)
Круг замкнулся. Мы перебрали все возможные хеши. Хеш от 00 даст 01 (начало цепочки).
В цепочке имеем что каждый элемент (хеш) это пароль от следующего за ним хеша.
Т.е. пароль от хеша „03” это строка „02”, от „56” – строка „55”.
Если мы найдем хеш от пароля „пассворд” то получим (например) значение 32
Ф(пассворд)=32
Но в то же время мы знаем что пароль от хеша 32 это строка „31” (смотрим цепочку)
Значит:
Перед нами случай колизии когда два разных пароля дают один хеш.
Если бы эта функция применялась для хеширования паролей допустим форума и мы получили хеш 32 то авторизоваться можно как паролем „пассворд” так и паролем „31”
Получается имея полную цепочку хешей для функции Ф() мы можем найти пароль для ЛЮБОГО хеша. Для этого нужно найти наш хеш в цепочке и предыдущий хеш в ней будет паролем.
Для нашей функции диапазон хешей невелик и полная цепочка не займет много места, но если мы возьмем реально существующую функцию например oldmysql() то вся цепочка будет иметь 2^64 хешей (т.е. количество всех возможных хешей функции oldmysql())
Значит нельзя хранить всю цепочку.
Рассмотрим на примере нашей функции Ф() способ поиска пароля от нужного нам хеша при помощи цепочки которая хранит ПРОМЕЖУТОЧНЫЕ значения полной цепочки.

Идея

Итак полная цепочка для нашей фукнции будет занимать 100*2 = 200 знаков (100 – общее количество хешей, 2 – количество символов в хеше).
Генерировать будем так же как и описано выше:
(Цепочка 1)
Но сохраняем каждый десятый хеш, в результате получим такую цепочку
00 – первый хеш.
09 – хеш от 08
19 – хеш от 18
...
99 – хеш от 98

Запишу полностью для удобства понимания дальнейшего
(Цепочка 2)
Итого 11 записей. Что по объему равно 11*2=22 знака (Существенно меньше)
Остается вопрос КАК искать по этой цепочке пароль допустим от хеша 45. (пусть у пользователя форума был пароль „ВАСЯ” хеш от которого 45 )
Для того что бы найти пароль по нашей полученой цепочке с промежуточным сохранением (внимание сама суть!!!) берем наш хеш 45 и начинаем генерировать хеши от него по цепи и искать полученое значение в нашей неполной цепочке (Цепочка 2) Т.е.
Ф(45)=46 – ненайдено.
Ф(46)=47 – ненайдено.
Ф(47)=48 – ненайдено.
Ф(48)=49 – НАЙДЕНО!!!! В нашей неполной цепочке есть хеш 49.
Идем дальше. Смотрим предыдущий от найденого (49) хеш в нашей цепочке (Цепочка 2) там стоит значение хеш 39. Имеем НАЧАЛО диапазона где будет найден наш искомый хеш (45).
Начинаем снова генерить хеши от начала диапазона (39) и сравнивать его с нашим искомым хешем (45):
Ф(39)=40 - нет
Ф(40)=41 - нет
Ф(41)=42 - нет
Ф(42)=43 - нет
Ф(43)=44 - нет
Ф(44)=45 – НАШЛИ!!!!!!!! Значит паролем к нашему хешу будет строка „44”.
Все колизия найдена
Ф(ВАСЯ)=45
Ф(44)=45
(можем авторизоваться на форуме паролем 45 )
Теперь о том что это дает и как это все будет по времени.
Пусть полная цепочка генерится 100 часов. Т.е. один хеш в час. Это долго и неудобно НО сгенерить ее нужно лишь один (!) раз, сохранив при этом только каждый десятый хеш.
Дальше при самом неудачном варианте нам нужно будет генерить максимум 10 хешей, что займет всего 10 часов (пока без учета поиска)
Что касается места на полную цепочку (Цепочка 1) уходит 200 знаков, на неполную (Цепочка 2) – 22 знака.

Дальше о реальности

Все это дело было придумано основываясь на двух вещах:
1. Скорость генерирования хешей на CUDA сморим тут https://forum.antichat.ru/thread62728.html
В конце видим
И второе условие необходимое для работы этой темы, нужно что бы
2. Среди всего диапазона хешей если их взять как пароли небыло коллизий
Т.е.
ХЕШ1=OLDPASSWORD(хеш01)
ХЕШ2= OLDPASSWORD(хеш02)
ХЕШ1<>ХЕШ2 для ЛЮБЫХ пар хеш01-хеш02
Или другими словами OLDPASSWORD(хеш1)<>OLDPASSWORD(хеш2)
Нужно это для того что бы полная цепочка замкнулась в кольцо.


Теперь в цифрах. Для генерации полной цепочки (без сохранения) нужно
2^64/8 000 000 000 000 = 2305843 секунд = 640,5 часов = 26 дней. Что вообщем-то очень недолго.
Теперь определимся с шагом сохранения.
Тут важными будут два параметра:
1. Время восстановления одного участка цепочки.
2. Место которое мы готовы выделить на диске для хранения промежуточных результатов
Есть определенные ограничения и тонкости, но это уже можно узнать после ряда тестов.
Для примера если мы сделаем шаг размером 2^44 штук, то количество шагов(цепочек) и стало быть количество сохраненных промежуточных хешей будет 2^64 / 2^44 = 2^20 хешей. Это 1048576 хешей. По объему будет занимать 1048576*16 байт (длинна хеша)= 16777216 байт = 16 МБ. Всего 16 Мб на хранение цепочки промежуточных хешей.
Но при генерации цепочки из нашего искомого хеша мы вынуждены результат сравнивать со всеми 1 048 576 хранимых хешей, что сильно замедлит сокрост. Вот тут как раз нужно подобрать оптимальную длину шага что бы хранимых хешей было как можно меньше но один промежуток (шаг) перебирался за короткое время.
Можно например сделать так, не сравнивать каждый полученый хеш с хранимой цепочкой , а сгенерить весь промежуток длинной в шаг (2^44) и найти общий хеш среди нагенереного массива хешей и цепочкой промежутков. Вообщем придумать можно.

Вот такая вот идейка по поиску коллизий. Почему она вообще пришла мне в голову. Дело в том что у хеша диапазон входных значений бесконечность, но выходных конечное множество. А что если сами хеши использовать как пароли, на выходе тоже будут хеши. Значит если перебрать все хеши как входные данные, то мы получим ВСЕ хеши на выходе. Т.е. мы сузим диапазон входных значений с бесконечности до вполне конечного числа в случае с oldmysql хешами это будет 2^64, что не так уж и много во времена CUDA.
Хотелось бы обсудить идею вообще ну и алгоритмы реализации. Т.е. слушаю ваши мнения на этот весь тред