Как обратить хэш функцию?

Сейчас на форуме: rmn, exp50848 (+7 невидимых)

Посл.ответ	Сообщение
vasyaC Ранг: 2.1 (гость) Активность: 0.01↘0 Статус: Участник	Создано: 24 октября 2011 12:46 · Личное сообщение · #1 Code: unsigned long long HashFun(unsigned char bp) { unsigned long long h = 0x14E250A96F5C2B37; while* (bp) { h = h ^ bp++; h = h + (h << 1) + (h << 4) + (h << 5) + (h << 7) + (h << 8) + (h << 40); } return h; } Нужно найти набор данных, который бы давал заданный хэш.

PE_Kill Ранг: 793.4 (! !), 568thx Активность: 0.74↘0 Статус: Участник Шаман	Создано: 24 октября 2011 13:24 · Личное сообщение · #2 а что по данным? Для не печатаемых символов можно искусственно коллизию сделать ----- Yann Tiersen best and do not fuck
vasyaC Ранг: 2.1 (гость) Активность: 0.01↘0 Статус: Участник	Создано: 24 октября 2011 13:57 · Личное сообщение · #3 На вход можно подавать любые данные кроме нуля. На выходе должен быть строго определенный хэш. Решаема ли задача без полного перебора 8 байт?
ntldr Ранг: 369.8 (мудрец), 400thx Активность: 0.39↘0 Статус: Участник	Создано: 24 октября 2011 14:18 · Личное сообщение · #4 Если операция h = h + (h << 1) + (h << 4) + (h << 5) + (h << 7) + (h << 8) + (h << 40); обратима, то хэш можно вскрыть атакой --> встречи по середине <-- Проанализируем операцию на обратимость. Сначала заменяем сдвиги умножениями: h = h + (h * 2) + (h * 16) + (h * 32) + (h * 128) + (h * 256) + (h * 1099511627776). Упрощаем: h = h * 1099511628211 Так как умножение по модулю, математически это можно записать как 1099511628211x=b(mod 18446744073709551616). Это линейное сравнение, или сравнение первого порядка вида ax = b (mod m). Если a и m взаимно простые, т.е. их НОД равен 1, то линейное сравнение имеет одно решение, т.е. обратимо, иначе оно имеет НОД(a, m) решений. НОД(1099511628211, 18446744073709551616) = 1. Дальше рассказывать или сам выкуришь матчасть? ----- PGP key <0x1B6A24550F33E44A> \| Сообщение посчитали полезным: zeppe1in, Veliant
PE_Kill Ранг: 793.4 (! !), 568thx Активность: 0.74↘0 Статус: Участник Шаман	Создано: 24 октября 2011 14:26 · Поправил: PE_Kill · Личное сообщение · #5 Херню написал ----- Yann Tiersen best and do not fuck
vasyaC Ранг: 2.1 (гость) Активность: 0.01↘0 Статус: Участник	Создано: 24 октября 2011 14:27 · Личное сообщение · #6 Рассказывайте дальше, я внимательно слушаю
ntldr Ранг: 369.8 (мудрец), 400thx Активность: 0.39↘0 Статус: Участник	Создано: 24 октября 2011 14:59 · Личное сообщение · #7 vasyaC пишет: Рассказывайте дальше, я внимательно слушаю Ок, рассказываю дальше. Если ax=b(mod m) при gcd(a, m) = 1, то x = (by mod m), где ay = 1 (mod m). Подставляем числа в последнее уравнение: 1099511628211y = 1 (mod 18446744073709551616) и решаем его через --> http://www.wolframalpha.com/ <-- (любители математики могут решить расширенным алгоритмом Евклида). Получаем y = 14886173955864302971. Следовательно обращением умножения на 1099511628211 будет умножение на 14886173955864302971 (по модулю 2^64). ----- PGP key <0x1B6A24550F33E44A> \| Сообщение посчитали полезным: PE_Kill, Isaev
ntldr Ранг: 369.8 (мудрец), 400thx Активность: 0.39↘0 Статус: Участник	Создано: 24 октября 2011 15:07 · Личное сообщение · #8 Дальше мы можем сделать атаку встречи посередине. Просчитываем половину хеша для первых 4х байт и сохраняем в памяти, просчитываем обратный хеш с конца для последних 4х байт и ищем совпадения. Понадобится 2 * 2^32 операций вычисления половинки хеша и 2^32 памяти для хранения отсортированных пар хеш-значение. Каждая такая пара весит 8+4=12 байт, значит нужно 48 гигабайт памяти. Если нет 48 гигов, можно сделать встречу не совсем посередине. Например просчитываем таблицу для первых трех байт (8+3 * 2^24 = 176mb) и брутим обратный хеш для 5 последних байт (2^40 операций). ----- PGP key <0x1B6A24550F33E44A> \| Сообщение посчитали полезным: vasyaC
drone Ранг: 85.4 (постоянный), 51thx Активность: 0.09↘0 Статус: Участник	Создано: 25 октября 2011 11:28 · Личное сообщение · #9 тему нужно в FAQ, однозначно
ntldr Ранг: 369.8 (мудрец), 400thx Активность: 0.39↘0 Статус: Участник	Создано: 25 октября 2011 11:38 · Личное сообщение · #10 Опа-на, эта задачка не спроста! --> Link <-- Хеш из сабжа это модифицированный --> FNV_64_1a <--. На странице хэша есть Can you help solve some of the zero-hash challenges? We are interested in finding the shortest data sets, under certain constraints, that produce a FNV hash value of zero for the various sizes of the FNV-1 and FNV-1a hash function. Those who offer the best solution will receive fame and credit on the FNV web page. Интересно, посчитаю ка я решение для 64 битного FNV и напишу автору хеша. ----- PGP key <0x1B6A24550F33E44A>
PE_Kill Ранг: 793.4 (! !), 568thx Активность: 0.74↘0 Статус: Участник Шаман	Создано: 25 октября 2011 12:54 · Личное сообщение · #11 А ты уверен, что можно подобрать 8 байтовые входные данные под любой хеш? У него же по сути есть начальное значение и для данных свыше 8 байт оно будет уничтожено. ----- Yann Tiersen best and do not fuck
ntldr Ранг: 369.8 (мудрец), 400thx Активность: 0.39↘0 Статус: Участник	Создано: 25 октября 2011 13:19 · Личное сообщение · #12 PE_Kill пишет: А ты уверен, что можно подобрать 8 байтовые входные данные под любой хеш? Скорее всего нельзя. Но я уже написал прогу которая найдет такие данные, если они вообще существуют. Если нельзя подобрать под 8 байт, можно попробовать под 9, есть соображения как улучшить атаку еще на 1 байт и перебирать 4+3 байт из 8ми или 4+4 (3+5) из 9ти. ----- PGP key <0x1B6A24550F33E44A>
ntldr Ранг: 369.8 (мудрец), 400thx Активность: 0.39↘0 Статус: Участник	Создано: 25 октября 2011 16:12 · Личное сообщение · #13 Результаты для 8ми байт. Найдены улучшенной атакой со сложностью 2^32 + 2^24 операций и 2^24 памяти. FNV64_1a(d5 6b b9 53 42 87 08 36) == 0 FNV64_1(x) == 0 для 8ми байт решений не имеет ----- PGP key <0x1B6A24550F33E44A> \| Сообщение посчитали полезным: r_e
vasyaC Ранг: 2.1 (гость) Активность: 0.01↘0 Статус: Участник	Создано: 25 октября 2011 16:38 · Личное сообщение · #14 Можно мне в личку алгоритм улучшенной атаки? Цена вопроса 50WMZ.
ntldr Ранг: 369.8 (мудрец), 400thx Активность: 0.39↘0 Статус: Участник	Создано: 25 октября 2011 16:44 · Личное сообщение · #15 vasyaC пишет: Можно мне в личку алгоритм улучшенной атаки? Нельзя. Я это делаю не за бабло, а ради интереса. ----- PGP key <0x1B6A24550F33E44A> \| Сообщение посчитали полезным: yagello, SReg, _ruzmaz_
PE_Kill Ранг: 793.4 (! !), 568thx Активность: 0.74↘0 Статус: Участник Шаман	Создано: 25 октября 2011 16:50 · Личное сообщение · #16 16 гигов, вполне приемлемо. А сколько такой словарь будет генерироваться на x86 системе, если например нет возможности его скачать? ----- Yann Tiersen best and do not fuck
ntldr Ранг: 369.8 (мудрец), 400thx Активность: 0.39↘0 Статус: Участник	Создано: 25 октября 2011 17:05 · Личное сообщение · #17 для брута 8 байт встречей точно посередине потребуется 2^32 элементов памяти по 12 байт (8 байт на хеш + 4 байта на значение) и 2^32 + 2^32 операций. Это 48 гигов оперативки. Но 1 байт легко вычислить без перебора, поэтому сложность понижается до 2^24 элементов памяти по 11 байт и 2^24 + 2^32 операций. Я сейчас запустил брут по улучшенному алгоритму для 9 байт FNV64_1, такой брут имеет сложность 2^24 элементов памяти по 11 байт и 2^24 + 2^40 операций. Подробности в личку, чтобы шароварщик не ловил тут халяву. UPD найдено первое решение: FNV64_1(92 06 77 4c e0 2f 89 2a d2) == 0 ----- PGP key <0x1B6A24550F33E44A>
drone Ранг: 85.4 (постоянный), 51thx Активность: 0.09↘0 Статус: Участник	Создано: 26 октября 2011 13:35 · Личное сообщение · #18 теперь автор воткнет какой-нибудь другой алго
PE_Kill Ранг: 793.4 (! !), 568thx Активность: 0.74↘0 Статус: Участник Шаман	Создано: 26 октября 2011 14:57 · Личное сообщение · #19 drone всё уже давно придумано и реализовано, не знаю чего ТС ищет. ----- Yann Tiersen best and do not fuck
drone Ранг: 85.4 (постоянный), 51thx Активность: 0.09↘0 Статус: Участник	Создано: 27 октября 2011 12:56 · Личное сообщение · #20 видимо ищет велосипед с квадратными колесами, извиняюсь за оффтоп от себя и за PE_Kill
bowrouco Ранг: 47.7 (посетитель), 17thx Активность: 0.09↘0 Статус: Участник	Создано: 06 ноября 2011 18:25 · Поправил: bowrouco · Личное сообщение · #21 ntldr Подскажите на счёт циклического ксора, тоесть: Code: H4 H3 H2 H1 5 B1^B2 B1^B3 B2^B3^B4 B1^B2^B5 6 B2^B3 B1^B2^B4 B1^B3^B4^B5 B2^B3^B6 7 B1^B3^B4 B2^B3^B5 B1^B2^B4^B5^B6 B1^B3^B4^B7 8 B1^B2^B4^B5 B1^B3^B4^B6 B2^B3^B5^B6^B7 B1^B2^B4^B5^B8 9 B2^B3^B5^B6 B1^B2^B4^B5^B7 B1^B3^B4^B6^B7^B8 B2^B3^B5^B6^B9 10 B1^B3^B4^B6^B7 B2^B3^B5^B6^B8 B1^B2^B4^B5^B7^B8^B9 B1^B3^B4^B6^B7^B10 11 B1^B2^B4^B5^B7^B8 B1^B3^B4^B6^B7^B9 B2^B3^B5^B6^B8^B9^B10 B1^B2^B4^B5^B7^B8^B11 Это для кода B1B2B3... вычисляется хеш. Известен хеш(H4H3H2H1), размер(число итераций Iters), B1, возможно есчо B2 и B3. Максимальное число итераций - 32. Необходимо восстановить код по хешу с минимальным количеством итераций. Функция такая: Code: ; Esi: PCODE, Ecx: LENGTH xor eax,eax mov edx,eax or ecx,ecx je Exit push esi lea eax,dword ptr ds:[eax] @@: xor dh,dl xor dl,ah xor ah,al mov al,byte ptr ds:[esi] inc esi xor al,dh dec ecx jnz @b shl edx,16 lea eax,dword ptr ds:[eax + edx] pop esi Exit: ret У меня получилось Iters = 2^(8*(Len - 5)), для Iters > 5. Для 6 итераций можно разложить: B6 = H1^H4 B5 = H2^H3^H4 B4 = B1^B2^H3 ; B2 брутим. B3 = B2^H2^H3 = B1^B4^H3^H4 Для 7 так не удаётся разложить почемуто, Bn-1 != f(Bn). 8154_06.11.2011_EXELAB.rU.tgz - Hash.png
PE_Kill Ранг: 793.4 (! !), 568thx Активность: 0.74↘0 Статус: Участник Шаман	Создано: 06 ноября 2011 18:32 · Личное сообщение · #22 bowrouco это DrWeb32 GetSignHash, здесь вирмейкерам не рады, сомневаюсь, что ntldr будет это копать. ----- Yann Tiersen best and do not fuck
bowrouco Ранг: 47.7 (посетитель), 17thx Активность: 0.09↘0 Статус: Участник	Создано: 06 ноября 2011 18:36 · Личное сообщение · #23 PE_Kill Знаете вы много

Для печати