Барон фон Юбельтатер хранит свой самый главный пароль в файле в хэшированном виде. Для защиты пароля он использует немного модифицированную функцию "Стрибог"(ГОСТ 34.11-2012) (Стандарт доступен, например, по адресу http://meganorm.ru/Data2/1/4293788/4293788459.pdf), которую он назвал "Юбельт-Стрибог". Граф фон Крипто утверждает, что эта функция ненадежна и готов доказать это, построив сообщение, хэш которого будет совпадать с выданным ему фон Юбельтатером значением. Помогите графу сделать это. Описание хэш-функции Юбельт-Стрибог, формат входных данных и тестовые значения описаны ниже.

Юбельт-Стрибог использует базовые преобразования L, P, S, используемые в хэш-функции Стрибог для построения функции сжатия следующим образом:

Преобразования L, P, S описанны в  [1] . Функция E задается следующим образом:

где X[K](m) = m ⊕ K, а раундовые ключи вычисляются как:

K₀ = k, C_i — константы, описанные в  [1].

Процедуру вычисления хэш-значения сообщения M хэш-функцией Юбельт-Стрибог можно описать следующим образом:

1.     Дополнение сообщения: В конец сообщения M, представленного как битовая строка дописывается бит 1, а затем такое количество битов 0 так, чтобы длина получившегося сообщения M¹ была кратна 512 битам.

2.     Сообщение M¹ разбивается на блоки по 512 бит и, начиная с первого блока, подается на вход функции сжатия G(H,M). В качестве H₀ берется битовый вектор длины 512, состоящий только из 0.

3.     Выход последнего преобразования функции сжатия и является необходимым хэш значением.

Процедуру вычисления хэш-функции можно также представить следующим псевдокодом:

Реализация, с помощью которой барон фон Юбельтатер будет проверять результаты работы графа принимает на вход сообщения, представленные в шестнадцатиричной записи длиной не более 1024.

Значение, переданное бароном: 
317c577f2dd9021b8c921a639220e992519aa6a51d61dfb04b287638805dd6e8cc93ab8edf983010a59e548c6c839e6d16767233371246adb6001e1415d87b44

Тестовые примеры.

 
В приведенных ниже тестовых примерах || означает конкатенацию строк, а xⁿ означает повторение символа x n раз подряд. Все примеры приведены в шестнадцатиричной системе счисления.

 
Сообщение M = 0¹²⁸
Дополнение M¹ = 0¹²⁸||8||0¹²⁷
хэш-значение = 08034d432d05d4c119931a139869aa0d1442f14c6007ac82402d1a8eb9d7cd504745a0d8fd3330bee1b409eff3afd4764bd3e2a83b1fb56c8400a48e2351b2b1

 
Сообщение M = 00
Дополнение M¹ = 00||8||0¹²⁵
хэш-значение = e8096004fbfedbaf9d2cdbb26089515cddc77abd36992ca16b78543a56fca0c337330a1facaa1f3fb02e3c48d6a61f6031eba0c0266faceed2b24bbb46363f20

 
Сообщение M = af
Дополнение M¹ = af||8||0¹²⁵
хэш-значение = 08f79de0b7556269cd4ab1da981a7f5c7b07bafeb6c10697db2d75656a2176431054818f47bb0a9772de5676d87010b7fbd5579b0d24e9ae50bbf12e2694610c
 

Ссылки

[1]

ГОСТ Р 34.11-2012, Национальный стандарт Российской Федерации. Информационная технология. Криптографическая защита информации. Функция хэширования. Москва, 2012.

 
Комментарий к приложениям: Программа hashsnd.exe хэширует сообщение из файла mess.txt функцией Юбельт-Стрибог и выводит результат в файл hash.txt в шестнадцатиричном виде. Реализована на базе ГОСТ 34.11-2012. Правильным ответом является любая строка длиной менее 1024 символов в шестнадцатиричной записи, которая хэшируется в данное значение.

Разбор 3 задачи:

1) Заметим, что функции L, P и S обратимы (для L нужно обратить матрицу A, P обратна сама себе, а для S надо взять PIrev[ PI[i] ] = i, i = 0..255), а так как функция G является композицией обратимых функций (xor и LPS) от m, то и сама G обратима относительно m (обратную функцию будем называть Grev(k, h) = Erev(k, (h xor k)), где h - получаемый хеш).

2) Попробовав по нашему хешу получить m сталкиваемся с отсутствием padding'а, таким образом при хешировании m он будет добавлен и хеш будет другой, а значит сообщение должно состоять как минимум из двух блоков. Для первого блока H_0 - нулевой вектор, H_1 = G(LPS(H_0), m_0), а итоговым хешом будет G(LPS(H_1), m_1). Тогда можно попробовать найти H_1(перебором) такой, что m_1 = Grev(H_1, HASH) будет содержать байт в конце, который будет являться padding'ом, а затем его просто отрезать в итоговом сообщении. У меня ушло около 100 итераций, чтобы найти необходимый H_1.

3) Зная H_1 можно найти m_0 = Grev(H_0, H_1).

4) Соединяем 2 части сообщения и получаем ответ.

5) В приложении скрипт, выполняющий все эти действия.