Цепочки – метод поиска коллизии. [Архив]

Просмотр полной версии : Цепочки – метод поиска коллизии.

Red_Red1

20.01.2009, 01:33

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

(Функция взята искуственно для удобства пояснения)
Задача:
Найти пароль от ЛЮБОГО известного хеша этой функции Ф().
Решение (алгоритм)
Сгенерируем цепочку хешей где сами хеши будут паролями т.е.:
(Цепочка 1)

Ф(00)=01
Ф(01)=02
Ф(02)=03
Ф(03)=04
Ф(04)=05
...
Ф(98)=99
Ф(99)=00

Круг замкнулся. Мы перебрали все возможные хеши. Хеш от 00 даст 01 (начало цепочки).
В цепочке имеем что каждый элемент (хеш) это пароль от следующего за ним хеша.
Т.е. пароль от хеша „03” это строка „02”, от „56” – строка „55”.
Если мы найдем хеш от пароля „пассворд” то получим (например) значение 32
Ф(пассворд)=32
Но в то же время мы знаем что пароль от хеша 32 это строка „31” (смотрим цепочку)
Значит:

Ф(пассворд)=32
Ф(31)=32

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

Ф(00)=01
Ф(01)=02
Ф(02)=03
Ф(03)=04
Ф(04)=05
...
Ф(98)=99
Ф(99)=00

Но сохраняем каждый десятый хеш, в результате получим такую цепочку
00 – первый хеш.
09 – хеш от 08
19 – хеш от 18
...
99 – хеш от 98

Запишу полностью для удобства понимания дальнейшего :)
(Цепочка 2)

00
09
19
29
39
49
59
69
79
89
99

Итого 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
В конце видим

«MySql хеши
...
Скорость перебора одного хеша 8 000 000 000 000 п/c. на GF8600GT»
И второе условие необходимое для работы этой темы, нужно что бы
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.
Хотелось бы обсудить идею вообще ну и алгоритмы реализации. Т.е. слушаю ваши мнения на этот весь тред :)

Qwazar

20.01.2009, 01:46

Эмм.. А почему ты думаешь что при A<B, F(A)<F(B) ?? Или я чтото не понял? Да и распределение может быть неравномерным, т.е. при A<C<B может быть и F(C)<F(A)<F(B). Тогда и диапазона никакого не будет.

Red_Red1

20.01.2009, 02:01

A<B, F(A)<F(B)
Ты не понял. Мы вычисляем хеш от хеша, на примере реальной функции олдмускул
берем строку 606717496665bcba вычисляем от нее хеш
oldpassword(606717496665bcba)=6a0d3dfd1c4308f4
дальше от результата
oldpassword(6a0d3dfd1c4308f4)=774cb1d32ece3273 и т.д
oldpassword(774cb1d32ece3273)=278117eb39e5d68c
oldpassword(278117eb39e5d68c)=7c52766a01a03c28
oldpassword(7c52766a01a03c28)=34de6b1d0a7eab07
Выход подаем на вход. И делаем так пока не переберем ВСЕ. Сохраняя при этом каждый ну допустим каждый тысячный хеш (это в реале мало, шаг нужне больше... ну я описывал)
____________________
Гм, я кажется понял что смутило. То что я хеши брал 01 02 03 ...
Вообщем это для удобства пояснения... сама нумерация не важна... это просто строки и все. Ну или считайте как индексы хешей... Т.е. Первый хеш, второй хеш, третий хеш... и т.д.

NFM

20.01.2009, 02:15

то есть для того чтобы найти значение от мд5 хеша, мы тупо сначала хешируем все значения от 00000000000000000000000000000000 до 99999999999999999999999999999999 и состаляем цепочки.
Причем проанализиовав я думаю мы мы можем некоторые значения не брать (кстати например хеш какого то значения может быть равен допустим 555555.....555? то есть если проанализировать мы часть значение можем не принимать и тогда наша база сузиться.)
я думаю на малых длинах хешей это прокатит.

Red_Red1

20.01.2009, 02:18

Причем проанализиовав я думаю мы мы можем некоторые значения не брать (кстати например хеш какого то значения может быть равен допустим 555555.....555? то есть если проанализировать мы часть значение можем не принимать и тогда наша база сузиться.)
Тоже думал про это... но ответа незнаю... нужно анализировать хеш функцию на областьь значений.
Про МД5 говорить пока рано так как 2^128 это все же ОЧЕНЬ много даже для КУДА.
Но это ПОКА рано ;) Да и кстати может кто то внесет что то свое и тогда МД5 тоже будет взят...

все значения от 00000000000000000000000000000000 до 99999999999999999999999999999999 и состаляем цепочки.
Тут не совсем верно сказано. Цепочка одна, просто храним не все значения а только каждый N-ный.
И не от 000000... до 9999999....
а допустим от 000000..... ДО некого хеша - ХЕШ от которого даст 000000... и круг замкнется. Тут кстати опять вылазит вопрос будет ли этот хеш, т.е. в области значений функции МД5 есть хеш 000000...
Может действительно "красивые хеши НЕ могут существовать" и ВСЕХ реальных хешей не от 000000... до 9999999.... (2^128) а ГОРАЗДО меньше?
Думаем.... :)

NFM

20.01.2009, 02:30

Почитал на вики про алгоритм мд5
Шаг 3. Инициализация буфера Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения шестнадцатеричными числами: А = 01 23 45 67; В = 89 AB CD EF; С = FE DC BA 98; D = 76 54 32 10.
то есть если я правильно дальше понял, хеш обьязательно у нас получается составленным из букв и цифр вместе. То есть нету такого входного значения, хеш которого будет составлен или только из цифр или только из букв, что сужает намного нашу область

или я неправильно понял?
--
а вот еще дальше прочитал

оллизии MD5 Коллизия хеш-функции — это получение одинакового значения функции для разных сообщений и идентичного начального буфера. В отличие от коллизий, псевдоколлизии определяются как равные значения хеша для разного значения начального буфера, причем сами сообщения могут совпадать или отличаться. В 1996 году Ганс Доббертин, нашел псевдоколлизии в MD5, используя определенные инициализирующие векторы, отличные от стандартных. Оказалось, что можно для известного сообщения построить второе, такое что оно будет иметь такой же хеш как и исходное. C точки зрения математики это означает MD5(IV,L1) = MD5(IV,L2), где IV начальное значение буфера, а L1 и L2 различные сообщения. Ханс Доббертин нашел такие значения. Например если взять начальное значение буфера: A = 0x12AC2375 В = 0x3B341042 C = 0x5F62B97C D = 0x4BA763ED и задать входное сообщениеAA1DDABE D97ABFF5 BBF0E1C1 32774244 1006363E 7218209D E01C136D 9DA64D0E 98A1FB19 1FAE44B0 236BB992 6B7A779B 1326ED65 D93E0972 D458C868 6B72746A то, добавляя число 29 к определенному 32-разрядному слову в блочном буфере, можно получить второе сообщение с таким же хешем. Ханс Доббертин представил такую формулу: Тогда MD5(IV, L1) = MD5(IV, L2) = BF90E670752AF92B9CE4E3E1B12CF8DE. В 2004 году китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии.[5][6] В 2005 году Ван Сяоюнь и Юй Хунбо из университета Шаньдун в Китае опубликовали алгоритм, который может найти две различные последовательности 128 байт, которые дают одинаковый MD5 хеш. Одна из таких пар:d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70 иd131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70 Каждый их этих блоков дает MD5 хеш равный 79054025255fb1a26e4bc422aef54eb4.
ну итам дальше описано
ps: криво вошло =( короч http://ru.wikipedia.org/wiki/MD5

preda1or

20.01.2009, 02:41

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

или я неправильно понял?

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

NFM

20.01.2009, 02:49

Если не сложно, можно пример тогда?

Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения шестнадцатеричными числами:
А = 01 23 45 67;
В = 89 AB CD EF;
С = FE DC BA 98;
D = 76 54 32 10.

В этих переменных будут храниться результаты промежуточных вычислений. Начальное состояние ABCD называется инициализирующим вектором.
----
судя по лекциям предатора ) я думаю у него адекватный преподаватель
чистый md5 имеет область значений хэшей от 00000000000000000000000000000000 до FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF (хотя это только область значений, нету точного задавания значений)
а вот в md5(md5()) - область значений может выраждаеться. То есть мд5(мд5) с большой вероятностью может быть составленным только из цифр и букв одновременно. Но я думаю это надо уточнять у тех кот увлекается криптографией, у меня спецкурс по криптографий уже закончился и я успешно спал на нем, и препода увижу только в след семестре чтобы посоветоваться )

NFM

20.01.2009, 03:27

предатор подумал и короче мы тут тупим, при одном проходе мд5 у нас просто строка из 32 символа, так что никакого вырождения нету )

preda1or

20.01.2009, 03:34

[preda1or] (02:31:04 20/01/2009)
хех

[preda1or] (02:31:06 20/01/2009)
реально тупим

[preda1or] (02:31:10 20/01/2009)
вырождение есть

[preda1or] (02:31:14 20/01/2009)

[preda1or] (02:31:17 20/01/2009)
вынос мозга

[NFM] [md5] (02:31:20 20/01/2009)
где?

[preda1or] (02:32:33 20/01/2009)
$string=md5();
md5($string)
$string - это 32байта строка от 0......0000 до F.....FFFF, а значит входной параметр уменьшился до 32^16

[preda1or] (02:32:42 20/01/2009)
то есть до 16^32

[preda1or] (02:32:52 20/01/2009)
вот тебе и вырождение

[preda1or] (02:33:23 20/01/2009)
а просто md5($string) - $string любой длинны и символов

[preda1or] (02:33:27 20/01/2009)
уловил мысль?)

впадлу переписывать

NFM

20.01.2009, 03:39

короче мы сузили кол-во хешей всего лишь до 1208925819614629174706176 примерно ) и еще пришла мысль что при бесконечном хеширование функция наши хеши будут циклически повторяться ))).
-----
Получается таким методом мы сможем найти только первый хеш от мд5.
То есть например
$l=md5(pass);
$k=md5($l);

пробрутив и занеся в базу 16^32 значений хешей от 0000...000 до FFF...FFF и сравнивая с $k мы сможем найти $l а потом уже брутить ее по словарю или обычными методами. Както все так получается )

NFM

20.01.2009, 03:58

кстати, кому интересно, попробуйте такое.
возьмите например слово pass
его хеш будет 1a1dc91c907325c69271ddf0c944bc72
Пишем простенький скрипт. Делаем цикл хеширования слова pass. То есть

$l=pass;
while i<бесконечность do
$l=md5($l);
if $l=1a1dc91c907325c69271ddf0c944bc72 на каком то шаге, то мы нашли порядок l . то есть число которое обозначает через сколько проходов хегирования наше слово будет иметь одинаквый хеш. правда я не думаю что компьютер сделает это ближайший год, надо узнать скорость за которую скрипт этот будет срабатывать. Порядок по идее должен быть меньше 16^32
---
вот такой вот ночной бред ))

preda1or

20.01.2009, 04:20

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

лебедя бы сюда....

NFM

20.01.2009, 04:32

протсенкий скрипт

<?
$mtime = microtime();
$mtime = explode(" ",$mtime);
$mtime = $mtime[1] + $mtime[0];
$tstart = $mtime;
$l="pass";
while($a <1000000) {
$a++;
$l=md5($l);
}
$mtime = microtime();
$mtime = explode(" ",$mtime);
$mtime = $mtime[1] + $mtime[0];
$tend = $mtime;
$totaltime = ($tend - $tstart);
printf ("Страница сгенерирована за %f секунд !", $totaltime);
?>

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

preda1or

20.01.2009, 04:37

Страница сгенерирована за 21.915162 секунд - для 1000000
Всего-то 7.14592971 × 10^33 секунд...

Neoveneficus

20.01.2009, 04:37

Сгенерируем цепочку хешей где сами хеши будут паролями т.е.:
(Цепочка 1)

Ф(00)=01
Ф(01)=02
Ф(02)=03
Ф(03)=04
Ф(04)=05
...
Ф(98)=99
Ф(99)=00

Круг замкнулся. Мы перебрали все возможные хеши. Хеш от 00 даст 01 (начало цепочки).

А теперь представь, что коллизия произошла на N'том (< 100) шаге... Что ты будешь делать?

NFM

20.01.2009, 04:45

вот еще мысль. по самому верхнему посту если я правильно все сказал, мы можем с очень большим трудом хрен знает как найти первый хеш от мд5(мд5).
А так как уже ясно что если допустим у нас md5(pass)=1a1dc91c907325c69271ddf0c944bc72 , то найдется еще одна строка, хеш который тоже будет равным 1a1dc91c907325c69271ddf0c944bc72.
то есть тогда мы можем допустим занести в базу 16^32 степени хешей и проверять взламываемый хеш с этой базе. Тогда при совпадений мы сможем найти значение. которое также подойдет под пароль.
Для примера можно хешировать числа от 1 до 16^32 проверяя, чтобы хеши не совпадали. И тогда например хеш строки "pass" может совпадать например с числом "33173" что и должно подойти при авторизаций на сайте, если там идет проверка по хешу.
это все теория конечно, хрен создашь такую базу с таким кол-вом значений. Но думаю данный метод подойдет под хеши малых размеров

preda1or

20.01.2009, 04:47

тут был тупой ночной пост :)

preda1or

20.01.2009, 04:49

не стоит этого делать
можно хешировать числа от 1 до 16^32 = ~10^31 Гб

NFM

20.01.2009, 04:53

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

Суперкомпьютер "СКИФ МГУ" построен на базе 625 серверов производства "Т-Платформы" с 1250-ю четырехъядерными процессорами Intel Xeon E5472. Пиковая производительность самого мощного в России, СНГ и Восточной Европе компьютера составляет 60 триллионов операций в секунду (TFlops). Реальная производительность системы на тесте Linpack - 47,04TFlops составила 78,4% от пиковой, что явилось лучшим показателем эффективности среди всех систем первой сотни списка Тор500 самых мощных компьютеров мира на базе четырехъядерных процессоров Intel Xeon. В настоящее время это абсолютный рекорд для России.

так что думаю в будущем все будет легко ломаться )

Fepsis

20.01.2009, 05:45

preda1or

20.01.2009, 09:30

2 Fepsis

http://www.mscs.dal.ca/~selinger/md5collision/

Red_Red1

20.01.2009, 09:52

Интересная тема... Тоже об этом думал.. Но думаю не всё так просто. Допустим такая ситуация:
создаём список паролей:
ф(0)=5
ф(5)=10
ф(10)=0
опаньки, вот и замыкание.. Радостные, что всего за месяц получили чудный список всевозможных (как нам кажется) паролей, идём брутить по этому списку... Брутим по нашему списку (0,5,10).. Результата нет..(((( Хны-Хны.. А всё почему..?!? Потомучто пароль, который мы пытались сбррутить "1", который в свою очередь так же имеет замыкание, только другое:
ф(1)=6
ф(6)=11
ф(11)=1
вполне может быть такое..)))
кстати, дайте пару разных строк, у которых одинаковый мд5 хеш... не сомневаюсь что есть.. любопытно... дайте глянуть..)
Приходило в голову это. Не описал специально что бы не путать.
Я ведь и хотел обсудить идею.
Вопрос КАК выловить что кольцо замкнулось. Ну и как выловить ВСЕ кольца. Если это сделать то мы опять получим всю цепочку-кольцо точнее несколько колец.
Т.е. хотелось бы все это дело испытать на практике. С олдмускул это реально.

-=lebed=-

20.01.2009, 10:37

Вообщем так...
Про md5 можно пока благополучно забыть, потому как 2^128 или что тоже колличество 16^32 ну это очень много и сгенерить их все, времени при современных технологиях не хватит.
Касательно хэшей mysql(64) - это в полне возможно попробовать реализовать.
Следует напомнить, что высокая скорость перебора хэшей mysql(64) в реализации от xSerg на CUDA получается за счёт использования уязвимости самого алгоритма хэширования mysql(64).
Далее, если брать в качестве входа функции именно предыдущую выходную строку, то область входных значений мы сужаем, потому как вход никак неограничен на самом деле. Если же строку подавать на вход функции в hex-виде, то можно предположить, что область входных значений будет равна области выходных. (на самом деле она будет меньше, потому как пробелы не учитываются на входе, т.е. это байты содержащие код 32 (dec) или 20 (hex)).
Но! это возможно только в случает полного отсутствия коллизий на участке входных значений длинной при кол. 2^64, т.е. соизмеримом с областью значений. Чего скорее всего не будет и мы получим ранее упомянутое замыкание круга и множество как входных, так и выходных значений остануться за пределами этого круга!
Отсюда следует вывод: что при замыкании в дальнейшей генерации цепочки нет смысла и для получения новой цепочки, содерж. другие значения входов и выходов, нам нужно взять другое начальное значение! Как оно должно быть связано с первой цепочкой? Каким образом вероятность возникновения замыкания (коллизии) зависит от шага? Вообщем в любом случае генерация цепочки в случае коллизии (замыкания) должна быть прервана (а это может случиться и раньше чем через 2^64 итераций)

preda1or

20.01.2009, 10:50

-=lebed=-
убил мой моск, буду думать, +

Fepsis

23.01.2009, 02:23

не стоит этого делать
= ~10^31 Гб
На счёт места на диске пришла идея, идея о способе хранения информации о паролях и хешах...
На примере MySQL хеша.. Представьте себе директорию, в которо находится 16 папок с именами 0,1,2,...,e,f. Заходим в любую из этих папок, в ней видим так же 16 папок 0,1,2,...,e,f. И так далее.. Глубина каждой папки - 16 вложений..
Теперь берём произвольную стоку (пароль) и находим его MySQL хеш:
123:773359240eb9a1d9
в папку ...7\7\3\3\5\9\2\4\0\e\b\9\a\1\d\9\
записывается файл НУЛЕВОЙ длины с именем "123"
и так для любого пароля...
Такой способ хранения не очень подойдёт для сервиса по восстановлению пароля из хеша, так как
http://crepers.jino-net.ru/oops.jpg
а пароли эти символы могут содержать, но если наша задача захешировать все числа от 0 до 2^64 или вариант когда выход пускается на вход (итерации) то вполне подойдёт..
берём начальную строку "0000000000000000"
файл "0000000000000000" -> в папку ...5\0\3\1\9\7\3\5\7\8\2\2\b\b\c\1\
"503197357822bbc1" -> ...4\2\f\c\0\a\f\2\0\0\0\0\0\0\0\0\ и т.д.
Мне кажется, написать прогу, которая данную стуктуру реализует, не очень сложная задача... И искать по такой базе очень удобно.. И если добъёмся того, что в каждой папке ...x\x\x\x\x\x\x\x\x\x\x\x\x\x\x\x\ будет лежать нулевой файл с именем "yyyyyyyyyyyyyyyy" то можео считать задачу относительно хеш функции MySQL решённой...
Не ругайтесь, если вышенаписанное бред или баян..
P.S. сейчас запустил на компе скрипт, создающий пустые файлы... Файлов было 100 000, винда показала, что папка с этими файлами весит 0 кб... Хотя я сомневаюсь что всё действительно по нулям.. Просветите меня..;)

preda1or

23.01.2009, 02:27

что папка с этими файлами весит 0 кб
Конечно не по нулям.Таблица разметки диска, интересно, сколько будет весить? Ты сэкономишь меньше процента,если вообще сумеешь.

Fepsis

23.01.2009, 02:36

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

diehard

28.06.2009, 02:39

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

По-моему вывод нелогичен. Получим НЕ ВСЕ хеши на выходе, будут повторы из-за коллизий типа:
hash(00000000000001) = 28282828282828
hash(34583475834758) = 28282828282828

Поэтому алгоритм обратится в вечный цикл и вот этого не произойдёт:

"Ф(45)=46 – ненайдено.
Ф(46)=47 – ненайдено.
Ф(47)=48 – ненайдено.
Ф(48)=49 – НАЙДЕНО!!!! "

Так как например "49" отсутствует в выдаче Ф(от конечного множества), зато 2 раза присутствует "48" и 5 раз присутствует "50" например.

Cthulchu

28.06.2009, 03:38

Cthulchu

28.06.2009, 04:17

да, что бы было понятнее - скажу, что это не кольца. это рендомно пересекающая саму себя функция, в местах пересечения оканчивая свой дальейший путь. движение функции задает, собственно, Ф() и аргумент конечно.
нам нужен алгоритм, который сможет подставлять в Ф() такие аргументы, что бы она заполнила все возможное пространство и разделить пространство на замыкающиеся кривые.
попробую по другому...
символьный ряд от нула до бесконечности, где каждый следующий аргумент (входное значение) функции (алгоритма хеширования) равен предыдущему (для первого насильно зададим предыдущий), если текуший аргумент уже где-то попадался - прерываем сохранение ряда, обьявляя его петлей. Хитростью (за хакерской догадкой надо к вебхаку обратиться) находим все петли, а мы уверены, что все диапазоны рано или поздно превратятся в петлю и это уже плюс. Главный же минус в том, что петли - тоже пересекаются. Им никто не запретил. Действительно, - коллизия коллизии.
Коллизия коллизии играет нам на руку, как мне кажется в стольк позднее время. Потому что это хороший шанс убрать лишние пароли из базы, а возможно, это является возможностью немножко регулировать размер колец для оптимизации брута конечного пароля (впадло считать какое отношение размера сегментов к их количеству будет оптимальным). Алгоритм писать под выяснение положений колец и их оптимизации - тоже впадло, так как асмового кодера под это благороднейшее дело - нету.

BrainDeaD

28.06.2009, 04:28

в принципе идея не нова. очень походит на ТМТО Хелльмана. буквально недавно наткнулся на статью в журнале C't за 11.2008
к сожалению журнал весит больше 100 мб, так что заливать не стану.
вот есть док klick (http://www3.iam.metu.edu.tr/iam/images/b/bf/Ardazuberterm.pdf)

diehard

28.06.2009, 04:35

дихард, это кольца. ред о них упоминал и тут и на сходке. давай лучше придумаем как красивее их обойти.
Единственное, что приходит в голову это тривиальный вариант с возможностью оптимизаций:
каждый полученый хеш прежде, чем хешировать снова - надо сопоставить с уже существующей базой нахешированых хешей... Да, это долго.
Что делать, если мы нашли кольцо? Останавливаем хеширование замыкающего кольцо хеша, удаляем его из базы, добавляем к нему единицу и продолжаем по заданому алгоритму.
Да, это будет долго.
ДА нет, это будет очень долго.
Оно того стоит.
Да, мой набросок допускает вероятность вычесления не всех хешей.
Ред, вместо того, что бы делить твою теоритическую базищу на сегменты по 250 миллионов хешей, оставляя лишь первый и последний - можно будет оставлять только кольца. Я, правда, не представляю сколько их там будет.
вот и все.

Нет, кольца тут не при чем, это еще хуже, попробую пояснить математическим языком -

А - конечное множество всех значений функции хеширования F()
Так как существуют такие a и b из множества A (a не равно b), для которых существует коллизия F(a)=F(b)=c, то с учётом того что А - конечно, то область значений F() на множестве аргументов A не равна А и является подмножеством A. Т.е. не для всякого x из А существует такое y из A, что F(y)=x

Cthulchu

28.06.2009, 04:43

ну да, я говорил о том, что возможно, останунтся хеши, которые сбрутить нельзя, но их мало будет... наверное мало...
Тобишь, ты обрисовал тот случай, когда среди всевозможных хешей, найдется такой, который не будет результатом хеширования какого-либо хеша. Согласен, но мы их упускаем. Почему-то я уверен в том (иначе сама идея не имеет смысла), что количество таких вот "иррациональных" хешей будет примерно 0.1% от всех возможных хешей.

diehard

28.06.2009, 04:50

Cthulchu

28.06.2009, 05:10

надо хорошо знать алгоритм хеширования и держать его в "оперативной памяти" мозга. Жаль, что Лебедя опять с нами нету. Птиц бы помог. Хватит, пора спать.