Хотя метод грубой силы , предложенный chux , работает нормально, как он есть, на самом деле мы можем ускорить его примерно в 256 раз (и, на самом деле, намного больше, если мыиспользуйте все оптимизации, описанные ниже).
Ключевым моментом здесь является то, что все операции, используемые для вычисления хэша, являются обратимыми.(Это сделано специально, так как это гарантирует, что, например, добавление одного и того же суффикса ко всем входным строкам не увеличит число коллизий хешей.) В частности:
Операция hash += hash << n, конечно, эквивалентно hash *= (1 << n) + 1.Мы работаем с 32-разрядными целыми числами без знака, поэтому все эти вычисления выполняются по модулю 2 32 .Чтобы отменить эту операцию, все, что нам нужно сделать, это найти модульную мультипликативную инверсию (1 << n) + 1 = 2 n + 1 по модулю 2 32 и умножить hash этим.
Мы можем сделать это довольно легко, например, с помощью этого скрипта Python , основанного на этом ответе здесь на SO .Оказывается, что мультипликативные инверсии 2 10 + 1, 2 3 + 1 и 2 15 + 1, в шестнадцатеричном виде, 0xC00FFC01, 0x38E38E39 и0x3FFF8001 соответственно.
Чтобы найти обратное значение hash ^= hash >> n для некоторой константы n, сначала обратите внимание, что эта операция оставляет старшие n биты hash полностью неизменными.Следующие младшие n биты просто XORed с самыми старшими n битами, поэтому для тех, кто просто повторяет операцию, она отменяется.Пока выглядит довольно просто, верно?
Чтобы восстановить исходные значения третьей старшей группы из n битов, нам нужно XOR их с исходными значениями второго наивысшего n бит, которые мы, конечно, можем вычислить, используя XOR для двух старших групп n бит, как описано выше.И так далее.
Все это сводится к тому, что обратная операция к hash ^= hash >> n:
hash ^= (hash >> n) ^ (hash >> 2*n) ^ (hash >> 3*n) ^ (hash >> 4*n) ^ ...
, где, конечно, мы можем отрезать серию после сдвигаколичество равно или больше количества битов в целых числах, с которыми мы работаем (т.е. 32, в данном случае).В качестве альтернативы, мы могли бы достичь одного и того же результата за несколько шагов, удваивая величину сдвига каждый раз, пока она не превысит длину в битах чисел, с которыми мы работаем, например:
hash ^= hash >> n;
hash ^= hash >> 2*n;
hash ^= hash >> 4*n;
hash ^= hash >> 8*n;
// etc.
(многошаговый метод масштабируетсялучше, когда n мало по сравнению с целочисленным размером, но для умеренно большого n одношаговый метод может страдать от меньшего количества конвейерных остановок на современных процессорах. Трудно сказать, какой из них на самом деле более эффективен в любой конкретной ситуации безсравнение их обоих, и результаты могут отличаться в зависимости от компиляторов и моделей процессоров. В любом случае о таких микрооптимизациях обычно не стоит беспокоиться.)
Наконец, конечно,обратное значение hash += key[i++] это просто hash -= key[--i].
Все это означает, что, если мы хотим, мы можем запустить хэш в обратном порядке, как это:
uint32_t reverse_one_at_a_time_hash(const uint8_t* key, size_t length, uint32_t hash) {
hash *= 0x3FFF8001; // inverse of hash += hash << 15;
hash ^= (hash >> 11) ^ (hash >> 22);
hash *= 0x38E38E39; // inverse of hash += hash << 3;
size_t i = length;
while (i > 0) {
hash ^= (hash >> 6) ^ (hash >> 12) ^ (hash >> 18) ^ (hash >> 24) ^ (hash >> 30);
hash *= 0xC00FFC01; // inverse of hash += hash << 10;
hash -= key[--i];
}
return hash; // this should return 0 if the original hash was correct
}
Затем вызов, скажем, reverse_one_at_a_time_hash("keynumber1", 10, 0xA7AF2FFE) должен вернуть ноль, , как на самом деле .
ОК, это круто.Но что хорошего в том, чтобы найти прообразы?
Ну, во-первых, если мы предположим всего, кроме первого байта ввода, то мы можем установить первый байт в ноль и запуститьхеш назад по этому входу.На этом этапе возможны два результата:
Если выполнение хэша в обратном направлении, как это, приводит к выводу, который является действительным входным байтом (т. Е. Не больше 255, и, возможно, с другимиограничения, если, например, вы хотите, чтобы все входные байты были печатаемыми ASCII), тогда мы можем установить первый байт входного значения на это значение, и все готово!
И наоборот, еслирезультат запуска хэша в обратном направлении не является допустимым входным байтом (например, если он больше 255), тогда мы знаем, что не существует первого байта, который мог бы сделать оставшуюся часть входного хэша для вывода, который мы хотим, и нам понадобитсявместо этого попробовать другое предположение.
Вот пример , который находит тот же ввод, что и код chux (но печатает его как строку в кавычках, а не как int с прямым порядком байтов):
#define TARGET_HASH 0xA7AF2FFE
#define INPUT_LEN 4
int main() {
uint8_t buf[INPUT_LEN+1]; // buffer for guessed input (and one more null byte at the end)
for (int i = 0; i <= INPUT_LEN; i++) buf[i] = 0;
do {
uint32_t ch = reverse_one_at_a_time_hash(buf, INPUT_LEN, TARGET_HASH);
if (ch <= 255) {
buf[0] = ch;
// print the input with unprintable chars nicely quoted
printf("hash(\"");
for (int i = 0; i < INPUT_LEN; i++) {
if (buf[i] < 32 || buf[i] > 126 || buf[i] == '"' || buf[i] == '\\') printf("\\x%02X", buf[i]);
else putchar(buf[i]);
}
printf("\") = 0x%08X\n", TARGET_HASH);
return 0;
}
// increment buffer, starting from second byte
for (int i = 1; ++buf[i] == 0; i++) /* nothing */;
} while (buf[INPUT_LEN] == 0);
printf("No matching input of %d bytes found for hash 0x%08X. :(", INPUT_LEN, TARGET_HASH);
return 1;
}
And вот версия, которая ограничивает ввод для печати ASCII (и выводит пятибайтовую строку ^U_N.):
#define TARGET_HASH 0xA7AF2FFE
#define MIN_INPUT_CHAR ' '
#define MAX_INPUT_CHAR '~'
#define INPUT_LEN 5
int main() {
uint8_t buf[INPUT_LEN+1]; // buffer for guessed input (and one more null byte at the end)
buf[0] = buf[INPUT_LEN] = 0;
for (int i = 1; i < INPUT_LEN; i++) buf[i] = MIN_INPUT_CHAR;
do {
uint32_t ch = reverse_one_at_a_time_hash(buf, INPUT_LEN, TARGET_HASH);
if (ch >= MIN_INPUT_CHAR && ch <= MAX_INPUT_CHAR) {
buf[0] = ch;
printf("hash(\"%s\") = 0x%08X\n", buf, TARGET_HASH);
return 0;
}
// increment buffer, starting from second byte, while keeping bytes within the valid range
int i = 1;
while (buf[i] >= MAX_INPUT_CHAR) buf[i++] = MIN_INPUT_CHAR;
buf[i]++;
} while (buf[INPUT_LEN] == 0);
printf("No matching input of %d bytes found for hash 0x%08X. :(", INPUT_LEN, TARGET_HASH);
return 1;
}
Конечно, этот код легко изменить, чтобы он был еще болееограничительный набор входных байтов.Например, с использованием следующих настроек :
#define TARGET_HASH 0xA7AF2FFE
#define MIN_INPUT_CHAR 'A'
#define MAX_INPUT_CHAR 'Z'
#define INPUT_LEN 7
создает (после нескольких секунд вычисления) прообраз KQEJZVS.
Ограничение входного диапазона делаеткод выполняется медленнее, поскольку вероятность того, что результат обратного вычисления хеша будет действительным входным байтом, конечно, пропорционален числу возможных действительных байтов.
Существуют различные способы, которымиэтот код можно было бы сделать еще быстрее.Например, мы можем объединить обратное хеширование с рекурсивным поиском , чтобы нам не приходилось многократно хэшировать всю входную строку, даже если изменяется только один байт:
#define TARGET_HASH 0xA7AF2FFE
#define MIN_INPUT_CHAR 'A'
#define MAX_INPUT_CHAR 'Z'
#define INPUT_LEN 7
static bool find_preimage(uint32_t hash, uint8_t *buf, int depth) {
// first invert the hash mixing step
hash ^= (hash >> 6) ^ (hash >> 12) ^ (hash >> 18) ^ (hash >> 24) ^ (hash >> 30);
hash *= 0xC00FFC01; // inverse of hash += hash << 10;
// then check if we're down to the first byte
if (depth == 0) {
bool found = (hash >= MIN_INPUT_CHAR && hash <= MAX_INPUT_CHAR);
if (found) buf[0] = hash;
return found;
}
// otherwise try all possible values for this byte
for (uint32_t ch = MIN_INPUT_CHAR; ch <= MAX_INPUT_CHAR; ch++) {
bool found = find_preimage(hash - ch, buf, depth - 1);
if (found) { buf[depth] = ch; return true; }
}
return false;
}
int main() {
uint8_t buf[INPUT_LEN+1]; // buffer for results
for (int i = 0; i <= INPUT_LEN; i++) buf[INPUT_LEN] = 0;
// first undo the finalization step
uint32_t hash = TARGET_HASH;
hash *= 0x3FFF8001; // inverse of hash += hash << 15;
hash ^= (hash >> 11) ^ (hash >> 22);
hash *= 0x38E38E39; // inverse of hash += hash << 3;
// then search recursively until we find a matching input
bool found = find_preimage(hash, buf, INPUT_LEN - 1);
if (found) {
printf("hash(\"%s\") = 0x%08X\n", buf, TARGET_HASH);
} else {
printf("No matching input of %d bytes found for hash 0x%08X. :(", INPUT_LEN, TARGET_HASH);
}
return !found;
}
Но подождите, мы еще не закончили!Глядя на исходный код хэш-функции «один за раз», мы можем видеть, что значение hash после первой итерации цикла будет ((c << 10) + c) ^ ((c << 4) + (c >> 6)), где c - первый байт ввода.Поскольку c является восьмибитным байтом, это означает, что только первые 18 байтов hash могут быть установлены после первой итерации.
Если факт, если мы вычисляем значение hash после первой итерации для каждого возможного значения первого байта c мы видим, что hash никогда не превышает 1042 * c.(На самом деле, максимум отношения hash / c составляет всего 1041.015625 = 1041 + 2 -6 .) Это означает, что, если M - максимально возможное значение действительного входного байта, значениеhash после первой итерации не может превышать 1042 * M.И добавление следующего входного байта только увеличивает hash максимум на M.
Таким образом, мы можем значительно ускорить код выше , добавив следующую проверку ярлыка в find_preimage():
// optimization: return early if no first two bytes can possibly match
if (depth == 1 && hash > MAX_INPUT_CHAR * 1043) return false;
Фактически, аналогичный аргумент может использоваться, чтобы показать, что после обработки первых двух байтов может быть установлено самое большее 28 младших байтов hash (и , точнее , что отношение hash к максимальному значению входного байта составляет не более 1084744.46667).Таким образом, мы можем расширить оптимизацию выше , чтобы охватить последние три этапа поиска, переписав find_preimage() следующим образом:
static bool find_preimage(uint32_t hash, uint8_t *buf, int depth) {
// first invert the hash mixing step
hash ^= (hash >> 6) ^ (hash >> 12) ^ (hash >> 18) ^ (hash >> 24) ^ (hash >> 30);
hash *= 0xC00FFC01; // inverse of hash += hash << 10;
// for the lowest three levels, abort early if no solution is possible
switch (depth) {
case 0:
if (hash < MIN_INPUT_CHAR || hash > MAX_INPUT_CHAR) return false;
buf[0] = hash;
return true;
case 1:
if (hash > MAX_INPUT_CHAR * 1043) return false;
else break;
case 2:
if (hash > MAX_INPUT_CHAR * 1084746) return false;
else break;
}
// otherwise try all possible values for this byte
for (uint32_t ch = MIN_INPUT_CHAR; ch <= MAX_INPUT_CHAR; ch++) {
bool found = find_preimage(hash - ch, buf, depth - 1);
if (found) { buf[depth] = ch; return true; }
}
return false;
}
Для примера поиска7-байтовый прообраз всего верхнего регистра 0xA7AF2FFE, эта дальнейшая оптимизация сокращает время работы до 0,075 секунды (в отличие от 0,148 секунд только для быстрого вызова depth == 1, 2,456 секунд для рекурсивного поиска без ярлыков и 15,489секунд для нерекурсивного поиска, рассчитанного по TIO).