The Neverhood, хеш алгоритм Опции

[-=CHE@TER=-]

Пишу сейчас страничку для сайта (ctpax-cheater) для игры The Neverhood.

В игре во всю используется вот такая хеш-функция (я её немножно переписал под свои нужды):

CODE

// The Neverhood hash routine
Const chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

Function StrHash(S: String): Longword;
Var I, C, K: Longword;
Begin
  result:=0;
  C:=0;
  For I:=1 To Length(S) Do
  Begin
    S[I]:=UpCase(S[I]);
    K:=Pos(S[I], chars);
    If K <> 0 Then
    Begin
      If K <= 10 Then // Digits
        C:=C + (Ord(S[I]) + $16 - $40)
      Else
        C:=C + (Ord(S[I]) - $40);
      If C >= $20 Then C:=C - $20;
      result:=result xor (1 ShL C);
    End;
  End;
End;

Т.е. игнорируется всё, что не цифры и английские буквы, затем от получившегося считается хеш.
В demo-версии эта функция находится в sub_425C10.
Ею зашифрованы как коды, так и имена файлов в .BLB архивах.

В Интернете нагуглил только два кода (там ещё один есть, но он неработающий - что-то забыли):
fastforward - увеличивает скорость игры в два раза (хеш $843070C0)
happybirthdayklaymen - работает только на первом экране - перекидывает игрока на второй (*улыбается*) (хеш $188B2105)
После набора кода нужно нажать ENTER. Перед набором, кстати, тоже неплохо будет - вдруг уже что-то нажимали (ENTER отправляет код на обработку и чистит буфер ввода для кода).

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

Есть, например, хеш $10410127 - он сохраняет текущий кадр игры в c:\NevShot.bmp (даже во время проигрывания smack-видео!). Но вот какой код ему соответствует - хрен знает.

Есть два способа посмотреть все коды:
1) Заменить хеши на известные значения.
2) Brute-force (полный перебор).

1-ый способ очень неудобен, потому что:
а) Все хеши кодов внутри какого-то case/switch и они должны быть заменены на соответствующие (т.е. отсортированы по возрастанию, а не как попало).
б) Они разбросаны по разным функциям, так что бегать между ними очень неудобно.
в) Этот способ неудобен ещё и тем, что его нельзя предложить всем имеющим игру - им придётся её как минимум патчить.

Перебор же очень трудоёмкий, даже если выбросить оттуда UpCase (т.е. заведомо перебирать только заглавные буквы и цифры) и оптимизировать.
Я заметил, что в этом алгоритме на каждом шаге зажигается или гасится (если уже был зажжён) 1 бит в хеше. Т.е. для упомянутого хеша $10410127 слово-пароль должно состоять как минимум из 8 знаков (с учётом того, что ни один бит не выключался), так как в этом числе 8 не нулевых бит.

Собственно, вопрос: кто-нибудь может предложить простой и быстрый алгоритм для перебора?

Может быть я чего-то не вижу и здесь можно гораздо быстрее и проще хеш подобрать.
Мне не обязательно получить именно тот код, который задумывался создателями - какая-нибудь последовательность типа "bsb99dc" - тоже сойдёт.

[-=CHE@TER=-]

Ну, начну в хронологическом порядке про хеши - с замены абракадабры подобранной "в лоб" для The Neverhood на нормальные слова и словосочетания.
Хотя, конечно, началось с того, что в начале недели решил хеши подобрать к C&C:RA1 demo, но об этом я в другой теме напишу. Пока разбирался как бы забрутфорсить RA1, решил вернуться к The Neverhood и сделать атаку не просто по словарю (1 слову), а комбинацию из двух слов, ибо по одному слову подбирался только код "skipper" (ну и "please", но он и так известен был). Стандартно это выглядело бы так:

CODE

for (j = 0; j < max_words; j++) {
  for (i = 0; i < max_words; i++) {
    strcpy(str_buff, wordlist[i]);
    strcat(str_buff, wordlist[j]);
    hash = Nev_Hash(str_buff);
    if ((hash == ...) || (hash == ...) ...) {
      save_hash_to_file(...);
    }
  }
}

Два вложенных цикла (по i и j), где слова склеиваются каждое с каждым.
Понятно, что код выше не оптимизированный, его можно оптимизировать, посчитав, например, один раз длинну каждого слова и далее делать не strcpy() и strcat(), а один раз в верхнем цикле memcpy() и второй раз уже memcpy() с длины первого слова. Копирование памяти работает куда быстрее, чем strcpy() и strcat() которым приходится длинну строки считать. Ну и всякого по мелочи: перевести сразу все строки в верхний регистр, чтобы отключить это в функции хеша и т.д.
И я уже хотел было всё это начать делать, но тут спросил себя: все эти вещи, безусловно, дадут прирост, но не настолько большой как хотелось бы, так что можно ли как-то посчитать от каждого слова хеш и уже складывать хеши, что будет в разы быстрее?
Помните алгоритм хеширования? См. выше Axsis очень подробно его объяснил.
Каждая буква, по сути, это сдвиг, на сколько сдвинуть, затем xor'ить этот бит. При сдвиге за 31 снова попадаем на ноль и так по кругу.
Давайте посмотрим на примере. Пусть нам нужно посчитать хеш от строки из двух символов: "0A" (ноль и 'a').
Код нуля 48, код 'A' - 65.
Хеш функция считает так:
shift += isdigit(ch) ? (ch - 64 + 22) : (ch - 64);
Т.е. если это цифра, то:
48 - 64 + 22 = 6 (для нуля)
А если это буква, то просто:
65 - 64 = 1 (для буквы 'A')
Т.е. хеш для строки "0A" будет:

CODE

// начало
shift = 0;
hash = 0;
// для нуля
shift += 48 - 64 + 22; // 6
shift &= 0x1F; // не более 31
hash ^= (1 << shift); // hash == 0 ^ (1 << 6) == 64 (0100 0000)
// для букв 'A'
shift += 65 - 64; // 7 (6 + 1)
shift &= 0x1F; // не более 31
hash ^= (1 << shift); // hash == 64 ^ (1 << 7) == 64 ^ 128 ==>
192 == 0100 0000 ^ 1000 0000 == 1100 0000

Таким образом, хеш для строки из двух символов "0A" будет равен 192 или 1100 0000 в двоичном представлении.
А теперь предположим, что у нас есть изначально хеши отдельно от нуля и отдельно от 'A'. Можно ли их сложить? Конечно!
'A': hash = 64 (0100 0000); shift = 6
'0': hash = 2 (0000 0010); shift = 1
Чтобы получить хеш от суммы слов, нам нужно взять второй хеш, затем циклически (т.е. когда сдвинутые биты появляются справа, а не исчезают) сдвинуть его влево на значение shift, которое осталось после подсчёта первого хеша, после чего будет достаточно сделать xor на хеш первого слова!

CODE

#pragma pack(push, 1)
typedef struct {
  char *value; // ссылка на слово из словаря для вывода в файл
  uint32_t hash; // хеш этого слова
  uint8_t shift; // сдвиг после подсчёта хеша
} bin_list;
#pragma pack(pop)

uint32_t __inline__ merge_hash(bin_list *a, bin_list *b) {
  return(a->hash ^ ((b->hash << a->shift) | (b->hash >> (32 - a->shift))));
}

Таким образом, всё что нам будет нужно - это один раз посчитать подсчитать хеши от всех слов и сохранить их вместе со значением сдвига, а дальше работать с ними как с простыми числами!
Скорость работы получилась просто взрывная - я все пары слов на 1 ядре перебрал за 35 минут!
Сейчас только понял, что можно было ещё дальше оптимизировать - заранее посчитать все 32 формы сдвига для каждого хеша и тупо брать по такому массиву, через a->shift как индекс и затем делать xor - будет ещё быстрее, но сожрёт дополнительно 4*32 = 128 байт на каждое слово.
370100 слов * 128 = 47 372 800 (~45 Mb)
В принципе, по памяти терпимо - это даже не 100 Мб.

Совпадений, кстати, сказать, было достаточно много, так что пришлось их вручную просматривать. Мне кажется, я угадал только с тремя кодами:
itsshowtime
hellobemocked
workedupdrying
Возможно ещё эти:
mydeeds
craneprotectsfrolicks
С кодом для получения всех видеокассет мне крупно повезло - программа выдала мне такое совпадение первым же вариантом:
CHOWTIME ITS
Откуда я уже сразу догадался какой код там был - It's showtime (потому что слова showtime в словаре, через который я делал атаку, почему-то не было). Причём для сайта мне пришлось выбирать наиболее подходящие, да и просто культурные варианты. Под катом примеры того, что можно было получить.

WARNING EXPLICIT LANGUAGE

8580A64D = CLINTON SUCKS (игра вышла в 1996, а президентом (если это тот Clinton) он был с 1993 по 2001, так что кто знает?..)
A50535B1 = DISPOSES MATRIARCHY
56530108 = PIROZHOK RIME
8141A000 = DEFILED COW
4339581D = SOVKHOZ SINISTRUOUS
C8C004D4 = GOLD PEDERAST

Брутфорсить с тремя словами я начал, но быстро эту идею забросил (от этого остались только пара кодов начинающихся с "a..."), ибо:
370100 слов * 35 минут (перебор двух слов) = 12953500 минут = ((12953500 / 60) / 24) / 365 ~ 24.6
В общем 25 лет. Даже если я разобью на 4 ядра и заоптимизирую - это будет около 6 лет.
Но проблема тут даже не в этом, а в том, что пары слов дали мне 12 с лишним тысяч строк совпадений.
Сколько мне вариантов дадут три слова мне даже думать не хочется, ведь это же потом ещё и отсматривать придётся.
По хорошему из словаря бы выкинуть все странные и редкоиспользующиеся слова, добавить современные, тогда и перебирать было бы быстрее и результат был бы осмысленнее.
Но на это тоже нужно много времени, поэтому пусть уж будет как есть.