Русский / Russian English / Английский

Сейчас на форуме: _MBK_, LoxmatbIj (+4 невидимых)
 · Начало · Статистика · Регистрация · Поиск · ПРАВИЛА ФОРУМА · Язык · RSS ·

 eXeL@B —› Основной форум —› Как обратить хэш функцию?
Посл.ответ Сообщение

Ранг: 2.1 (гость)
Статус: Участник

Создано: 24 октября 2011 12:46 New!
Цитата · Личное сообщение · #1

Code:
  1. unsigned long long HashFun(unsigned char *bp)
  2. {
  3.          unsigned long long h = 0x14E250A96F5C2B37;
  4.  
  5.          while (*bp) {
  6.                  h = h ^ *bp++;
  7.                  h = h + (<< 1) + (<< 4) + (<< 5) + (<< 7) + (<< 8) + (<< 40);
  8.          }
  9.          return h;
  10. }

Нужно найти набор данных, который бы давал заданный хэш.


Ранг: 793.4 (! !)
Статус: Участник
Шаман

Создано: 24 октября 2011 13:24 New!
Цитата · Личное сообщение · #2

а что по данным? Для не печатаемых символов можно искусственно коллизию сделать

Ранг: 2.1 (гость)
Статус: Участник

Создано: 24 октября 2011 13:57 New!
Цитата · Личное сообщение · #3

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

Ранг: 370.2 (мудрец)
Статус: Участник

Создано: 24 октября 2011 14:18 New!
Цитата · Личное сообщение · #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.
Дальше рассказывать или сам выкуришь матчасть?

| Сообщение посчитали полезным: zeppe1in, Veliant



Ранг: 793.4 (! !)
Статус: Участник
Шаман

Создано: 24 октября 2011 14:26 · Поправил: PE_Kill New!
Цитата · Личное сообщение · #5

Херню написал

Ранг: 2.1 (гость)
Статус: Участник

Создано: 24 октября 2011 14:27 New!
Цитата · Личное сообщение · #6

Рассказывайте дальше, я внимательно слушаю

Ранг: 370.2 (мудрец)
Статус: Участник

Создано: 24 октября 2011 14:59 New!
Цитата · Личное сообщение · #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).

| Сообщение посчитали полезным: PE_Kill, Isaev


Ранг: 370.2 (мудрец)
Статус: Участник

Создано: 24 октября 2011 15:07 New!
Цитата · Личное сообщение · #8

Дальше мы можем сделать атаку встречи посередине. Просчитываем половину хеша для первых 4х байт и сохраняем в памяти, просчитываем обратный хеш с конца для последних 4х байт и ищем совпадения. Понадобится 2 * 2^32 операций вычисления половинки хеша и 2^32 памяти для хранения отсортированных пар хеш-значение. Каждая такая пара весит 8+4=12 байт, значит нужно 48 гигабайт памяти.
Если нет 48 гигов, можно сделать встречу не совсем посередине. Например просчитываем таблицу для первых трех байт (8+3 * 2^24 = 176mb) и брутим обратный хеш для 5 последних байт (2^40 операций).

| Сообщение посчитали полезным: vasyaC


Ранг: 85.4 (постоянный)
Статус: Участник

Создано: 25 октября 2011 11:28 New!
Цитата · Личное сообщение · #9

тему нужно в FAQ, однозначно

Ранг: 370.2 (мудрец)
Статус: Участник

Создано: 25 октября 2011 11:38 New!
Цитата · Личное сообщение · #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 и напишу автору хеша.


Ранг: 793.4 (! !)
Статус: Участник
Шаман

Создано: 25 октября 2011 12:54 New!
Цитата · Личное сообщение · #11

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

Ранг: 370.2 (мудрец)
Статус: Участник

Создано: 25 октября 2011 13:19 New!
Цитата · Личное сообщение · #12

PE_Kill пишет:
А ты уверен, что можно подобрать 8 байтовые входные данные под любой хеш?

Скорее всего нельзя. Но я уже написал прогу которая найдет такие данные, если они вообще существуют. Если нельзя подобрать под 8 байт, можно попробовать под 9, есть соображения как улучшить атаку еще на 1 байт и перебирать 4+3 байт из 8ми или 4+4 (3+5) из 9ти.

Ранг: 370.2 (мудрец)
Статус: Участник

Создано: 25 октября 2011 16:12 New!
Цитата · Личное сообщение · #13

Результаты для 8ми байт. Найдены улучшенной атакой со сложностью 2^32 + 2^24 операций и 2^24 памяти.
FNV64_1a(d5 6b b9 53 42 87 08 36) == 0
FNV64_1(x) == 0 для 8ми байт решений не имеет

| Сообщение посчитали полезным: r_e


Ранг: 2.1 (гость)
Статус: Участник

Создано: 25 октября 2011 16:38 New!
Цитата · Личное сообщение · #14

Можно мне в личку алгоритм улучшенной атаки? Цена вопроса 50WMZ.

Ранг: 370.2 (мудрец)
Статус: Участник

Создано: 25 октября 2011 16:44 New!
Цитата · Личное сообщение · #15

vasyaC пишет:
Можно мне в личку алгоритм улучшенной атаки?

Нельзя. Я это делаю не за бабло, а ради интереса.

| Сообщение посчитали полезным: yagello, SReg, _ruzmaz_



Ранг: 793.4 (! !)
Статус: Участник
Шаман

Создано: 25 октября 2011 16:50 New!
Цитата · Личное сообщение · #16

16 гигов, вполне приемлемо. А сколько такой словарь будет генерироваться на x86 системе, если например нет возможности его скачать?

Ранг: 370.2 (мудрец)
Статус: Участник

Создано: 25 октября 2011 17:05 New!
Цитата · Личное сообщение · #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

Ранг: 85.4 (постоянный)
Статус: Участник

Создано: 26 октября 2011 13:35 New!
Цитата · Личное сообщение · #18

теперь автор воткнет какой-нибудь другой алго


Ранг: 793.4 (! !)
Статус: Участник
Шаман

Создано: 26 октября 2011 14:57 New!
Цитата · Личное сообщение · #19

drone всё уже давно придумано и реализовано, не знаю чего ТС ищет.

Ранг: 85.4 (постоянный)
Статус: Участник

Создано: 27 октября 2011 12:56 New!
Цитата · Личное сообщение · #20

видимо ищет велосипед с квадратными колесами, извиняюсь за оффтоп от себя и за PE_Kill

Ранг: 47.7 (посетитель)
Статус: Участник

Создано: 6 ноября 2011 18:25 · Поправил: bowrouco New!
Цитата · Личное сообщение · #21

ntldr

Подскажите на счёт циклического ксора, тоесть:
Code:
  1.          
  2.          H4                  H3                              H2                       H1     
  3. 5        B1^B2            B1^B3      B2^B3^B4                         B1^B2^B5
  4. 6        B2^B3            B1^B2^B4                        B1^B3^B4^B5         B2^B3^B6
  5. 7        B1^B3^B4                     B2^B3^B5               B1^B2^B4^B5^B6                  B1^B3^B4^B7
  6. 8        B1^B2^B4^B5         B1^B3^B4^B6          B2^B3^B5^B6^B7      B1^B2^B4^B5^B8
  7. 9        B2^B3^B5^B6         B1^B2^B4^B5^B7             B1^B3^B4^B6^B7^B8           B2^B3^B5^B6^B9
  8. 10       B1^B3^B4^B6^B7          B2^B3^B5^B6^B8     B1^B2^B4^B5^B7^B8^B9        B1^B3^B4^B6^B7^B10
  9. 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:
  1. ; Esi: PCODE, Ecx: LENGTH
  2.          xor eax,eax
  3.          mov edx,eax
  4.          or ecx,ecx
  5.          je Exit
  6.          push esi
  7.          lea eax,dword ptr ds:[eax]
  8. @@:
  9.          xor dh,dl
  10.          xor dl,ah
  11.          xor ah,al
  12.          mov al,byte ptr ds:[esi]
  13.          inc esi
  14.          xor al,dh
  15.          dec ecx
  16.          jnz @b
  17.          shl edx,16
  18.          lea eax,dword ptr ds:[eax + edx]
  19.          pop esi
  20. Exit:
  21.          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).

{ Атач доступен только для участников форума } - Hash.png


Ранг: 793.4 (! !)
Статус: Участник
Шаман

Создано: 6 ноября 2011 18:32 New!
Цитата · Личное сообщение · #22

bowrouco это DrWeb32 GetSignHash, здесь вирмейкерам не рады, сомневаюсь, что ntldr будет это копать.

Ранг: 47.7 (посетитель)
Статус: Участник

Создано: 6 ноября 2011 18:36 New!
Цитата · Личное сообщение · #23

PE_Kill
Знаете вы много
 eXeL@B —› Основной форум —› Как обратить хэш функцию?

Видеокурс ВЗЛОМ