Найди кота
Всем привет!
Сегодня будет довольно странный пост — мы будем искать слово 'cat'.
Устраивайтесь поудобнее и погнали!
Что за?
Недавно мне пришла очень странная идея — найти в последовательности псевдослучайных чисел некое заданное слово.
Сначала я думал найти что-то типа 'hello world', но сразу отказался от него, т.к. чем длиннее фраза, тем меньше вероятность найти её.
И решил остановится на более коротком — 'cat'.
Задачи
Давайте сформулируем задачу:
- найти такой
seed, который будет давать слово 'cat' после последовательного применения функцииrand, т.е.
N1 = rand(seed)
N2 = rand(N1)
N3 = rand(N2)
N1 % 255 = 'c'
N2 % 255 = 'a'
N3 % 255 = 't'
Чтобы не было скучно решать только одну задача мне ещё подкинули найти кота в sha256 (хотя можно взять и любую другую хеш функцию).
Сформулируем и для неё задачу:
- найти такую строку, после применения к которой операции хеширования можно найти в полученном хеше слово 'cat'
Кот в случайных числах
В данном примере будем использовать xor shift для генерации псевдослучайных чисел
// xorshift.hpp
uint32_t xorshift(uint32_t seed) {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
return seed;
}
В качестве основного триплета я взял самый часто используемый: [13, 17, 5].
С ним точно будем уверены что период генерации будет 2 ^ 32 - 1, т.е. самый худший случай для перебора составит 4_294_967_295 итераций.
Если хотите подробнее погрузиться в теорию, то читайте вики и статью Xorshift RNGs.
Утилита для проверки
Для начала нам нужна утилита, с помощью которой сможем проверить любой заданный начальный seed.
#include <iostream>
#include "xorshift.hpp"
int main(int argc, char **argv) {
if (argc < 3) {
std::cout << "usage: " << argv[0] << " seed count" << std::endl;
return 0;
}
// получаем seed из первого аргумента
uint32_t seed = atoi(argv[1]);
// и длину цепочки
uint32_t count = atoi(argv[2]);
// генерируем результат
std::cout << "result: ";
while (count--) {
seed = xorshift(seed);
std::cout << char(seed % 255);
}
std::cout << std::endl;
}
Наивный алгоритм
Суть наивного алгоритма — простой перебор.
То есть берём какое-то начальное число seed и начинаем искать последовательность чисел, которые по модулю 255 будут давать слово 'cat'.
В коде его можно представить как-то так:
#include <iostream>
#include <string>
#include "xorshift.hpp"
// условие на нахождение кота
bool is_cat(const std::string & word) {
if (word.size() == 3) {
return word[0] == 'c' and
word[1] == 'a' and
word[2] == 't';
}
return false;
}
int main() {
std::string word = "";
uint32_t seed = 42;
uint32_t last_seed = seed;
uint64_t steps = 0;
while (true) {
seed = xorshift(seed);
steps += 1;
uint8_t v = seed % 255;
if (isalpha(v)) {
// если это буква алфавита то добавляем в слово
word.push_back(char(v));
} else {
// нашли кота?
if (is_cat(word)) {
std::cout << "found [" << last_seed << "] with " << steps << " steps: " << word << std::endl;
return 0;
}
last_seed = seed;
word = "";
}
}
}
Код написан не идеально, но в данном случае этого достаточно чтобы довольно быстро найти значение 357063244 пройдя 69_990_600 итераций, что довольно неплохо!
С помощью ранее представленной программы можем проверить его:
$ ./prove_xorshift 357063244 3
result: cat
Но будет не интересно останавливаться на таком простом переборе и поэтому давайте улучшим наш алгоритм!
Улучшенный алгоритм
Суть в том чтобы вместо обычного перебора брать и находить такие числа N удовлетворяющие условию N % 255 = K, где K — первая буква слова 'cat'.
То есть нам нужно найти seed, N1, N2 и N3 по ранее поставленным условиям:
N1 = xorshift(seed)
N2 = xorshift(N1)
N3 = xorshift(N2)
N1 % 255 = 'c'
N2 % 255 = 'a'
N3 % 255 = 't'
Для нахождения N1 мы можем воспользоваться формулой из статьи на вики.
Подставляя все значения в формулу и заменяя a на N1 и q на i получим:
N1 = 255 * i + int('c')
На данном этапе мы может определить N1, N2 и N3 просто перебирая все возможные N1 и проверяя на наше условие, но остаётся ещё число seed.
Пришлось покапаться в интернете для поиска того, что может помощь найти значение seed из N1. Я наткнулся на интересную статью в которой хоть и описывается обращение алгоритма XorShift128+, но самой идеи будет достаточно чтобы реализовать аналогичное решения для нашего 32-битного варианта.
Всё что нужно нам сделать — обратить все операции алгоритма и для этого разобьём задачу на три маленьких подзадачи, где мы будем обращать одну операцию за раз, а потом объединим результаты каждого из шагов, но только в обратном порядке.
Для обращения seed ^= seed << 13 можно сразу восстановить большую часть изначального значения, а затем сделать сдвиг и восстановить всё значение
tmp = (seed ^ (seed << 13)) & 0x00FFFFFF
result = seed ^ ((tmp << 13) & 0xFFFFFFFF)
Для seed ^= seed >> 17 решение вообще элементарное
result = (seed ^ (seed >> 17)) & 0xFFFFFFFF
А вот для seed ^= seed << 5 нужно немного потрудиться, т.к. от оригинального значения осталось совсем мало
# получаем два изначальных байта
f1 = (seed ^ (seed << 5)) & 0xFF
# а теперь у нас их три
f2 = (seed ^ ( f1 << 5)) & 0xFFF
f3 = (seed ^ ( f2 << 5)) & 0xFFFF
f4 = (seed ^ ( f3 << 5)) & 0xFFFFF
f5 = (seed ^ ( f4 << 5)) & 0xFFFFFF
f6 = (seed ^ ( f5 << 5)) & 0xFFFFFFF
# и постепенно приходим к результату
result = (seed ^ ( f6 << 5)) & 0xFFFFFFFF
Если не понятно как это всё работает, то стоит почитать про операции исключающее или и логический сдвиг.
Ну, а теперь остаётся только всё это закодить
#include <iostream>
#include <limits>
#include <string>
#include "xorshift.hpp"
const uint32_t ascii_max = 255;
const char c_symb = 'c';
bool is_cat(uint32_t c, uint32_t a, uint32_t t) {
return char(c % ascii_max) == c_symb and
char(a % ascii_max) == 'a' and
char(t % ascii_max) == 't';
}
uint32_t n_vals(uint32_t i) {
return ascii_max * i + uint8_t(c_symb);
}
uint32_t xorshift_backward(uint32_t seed) {
uint32_t f0 = (seed ^ (seed << 5)) & 0xFF;
uint32_t f1 = (seed ^ (f0 << 5)) & 0xFFF;
f0 = (seed ^ (f1 << 5)) & 0xFFFF;
f1 = (seed ^ (f0 << 5)) & 0xFFFFF;
f0 = (seed ^ (f1 << 5)) & 0xFFFFFF;
f1 = (seed ^ (f0 << 5)) & 0xFFFFFFF;
seed ^= f1 << 5;
seed ^= seed >> 17;
return seed ^ (((seed ^ (seed << 13)) & 0x00FFFFFF) << 13);
}
int main() {
for (uint32_t i = 0; i < std::numeric_limits<uint32_t>::max(); i++) {
uint32_t c = n_vals(i);
uint32_t a = xorshift(c);
uint32_t t = xorshift(a);
if (is_cat(c, a, t)) {
uint32_t seed = xorshift_backward(c);
std::cout << "found " << seed << " at step " << i << std::endl;
return 0;
}
}
}
В результате программа быстро (за 1315 шагов) находит первый seed, который ведёт к 'cat': 4140321215.
$ ./prove_xorshift 4140321215 3
result: cat
Кот в хешах
С xor shift закончим. Теперь перейдём на поиск кота в хеше.
Сразу встаёт вопрос: как будем представлять значение хеша в виде текста?
Мне сразу напросилось простое решение:
- интерпретируем каждые 2 символа как шестнадцатеричное значение
- будем выводить только символы из диапазона [a-zA-Z], а остальные заменять на '-'
То есть хеш
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
преобразуется в
--M-------------------B-s--b----
где '-' — символы вне диапазона.
Наивный алгоритм
В качестве наивного алгоритма сделаем следующее: сгенерируем некоторые случайное число с помощью random, потом преобразуем его в строку и посчитаем хеш.
Остаётся только преобразовать полученный хеш в читаемую строку и проверить если ли подстрока 'cat' в данной строке.
Замечу два момента:
- в качестве входной строки для хеш алгоритма был взят первый придуманный мной вариант, но вы можете взять что вашей душе угодно
- в данной реализации не будем считать количество проделанных итераций, т.к. мы используем функцию
random
К коллайдеру! То есть к коду!
# можно заменить на любую другую хеш функцию
from hashlib import sha256 as hasher
from random import random
# наш алфавит
alphabet = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
def as_text(value):
result = ''
# будем идти по два символа
for index in range(0, len(value), 2):
# преобразуем в число
block = int(value[index:index + 2], 16)
# а потом в символ
symbol = chr(block)
# и если он есть в алфавите, то добавляем в результирующую строку
result += symbol if symbol in alphabet else '-'
return result
if __name__ == '__main__':
result = ''
# перебираем пока не найдём кота
while 'cat' not in result:
# генерируем
text = str(random())
# хешируем
hashv = hasher(text.encode()).hexdigest()
# и в строку
result = as_text(hashv)
print(f"'{text}' -> {hashv} -> {result}")
Не забываем про утилиту для проверки хешей в ручном режиме:
alphabet = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
def as_text(value):
result = ''
for index in range(0, len(value), 2):
block = int(value[index:index + 2], 16)
symbol = chr(block)
result += symbol if symbol in alphabet else '-'
return result
print(as_text(input('Input hash: ')))
С помощью данного наивного подхода был найден вот такой вариант
c3377fd3636174cd06a81f38550d7057e2c676a7d20dbc38f8dfb957e25574c0
на основе вот этой строки
'0.44509213875838727'
сами можете убедиться с помощью sha256sum
$ echo -en "0.44509213875838727" | sha256sum -t
c3377fd3636174cd06a81f38550d7057e2c676a7d20dbc38f8dfb957e25574c0 -
а вот так выглядит преобразованный хеш в виде строки
----cat-----U-pW--v--------W-Ut-
Заключение
Я бы сказал "Не будем останавливаться на достигнутом — реализуем более быстрый алгоритм", но у меня пока нет идей для него! Как только я его придумаю, то напишу отдельный пост.
Весь написанный мной код можно взять по ссылке.
Всем пока!