Барон фон Юбельтатер хранит свой самый главный пароль в файле в хэшированном виде. Для защиты пароля он использует немного модифицированную функцию "Стрибог"(ГОСТ 34.11-2012) (Стандарт доступен, например, по адресу http://meganorm.ru/Data2/1/4293788/4293788459.pdf), которую он назвал "Юбельт-Стрибог". Граф фон Крипто утверждает, что эта функция ненадежна и готов доказать это, построив сообщение, хэш которого будет совпадать с выданным ему фон Юбельтатером значением. Помогите графу сделать это. Описание хэш-функции Юбельт-Стрибог, формат входных данных и тестовые значения описаны ниже.
Юбельт-Стрибог использует базовые преобразования L, P, S, используемые в хэш-функции Стрибог для построения функции сжатия следующим образом:
G(Hi−1,Mi) = E(L∘ P∘ S(Hi−1),Mi)⊕ Hi−1∣ {0,1}512 × {0,1}512 → {0,1}512 . |
Преобразования L, P, S описанны в [1] . Функция E задается следующим образом:
E(k,m) = X[K13]∘ |
|
L∘ P∘ S∘ X[Ki](m), |
где X[K](m) = m ⊕ K, а раундовые ключи вычисляются как:
Ki = L∘ P∘ S(Ci−1⊕ Ki−1), |
K0 = k, Ci — константы, описанные в [1].
Процедуру вычисления хэш-значения сообщения M хэш-функцией Юбельт-Стрибог можно описать следующим образом:
1. Дополнение сообщения: В конец сообщения M, представленного как битовая строка дописывается бит 1, а затем такое количество битов 0 так, чтобы длина получившегося сообщения M1 была кратна 512 битам.
2. Сообщение M1 разбивается на блоки по 512 бит и, начиная с первого блока, подается на вход функции сжатия G(H,M). В качестве H0 берется битовый вектор длины 512, состоящий только из 0.
3. Выход последнего преобразования функции сжатия и является необходимым хэш значением.
Процедуру вычисления хэш-функции можно также представить следующим псевдокодом:
|
Реализация, с помощью которой барон фон Юбельтатер будет проверять результаты работы графа принимает на вход сообщения, представленные в шестнадцатиричной записи длиной не более 1024.
Значение, переданное бароном:
317c577f2dd9021b8c921a639220e992519aa6a51d61dfb04b287638805dd6e8cc93ab8edf983010a59e548c6c839e6d16767233371246adb6001e1415d87b44
Тестовые примеры.
В приведенных ниже тестовых примерах || означает конкатенацию строк, а xn означает повторение символа x n раз подряд. Все примеры приведены в шестнадцатиричной системе счисления.
Сообщение M = 0128
Дополнение M1 = 0128||8||0127
хэш-значение = 08034d432d05d4c119931a139869aa0d1442f14c6007ac82402d1a8eb9d7cd504745a0d8fd3330bee1b409eff3afd4764bd3e2a83b1fb56c8400a48e2351b2b1
Сообщение M = 00
Дополнение M1 = 00||8||0125
хэш-значение = e8096004fbfedbaf9d2cdbb26089515cddc77abd36992ca16b78543a56fca0c337330a1facaa1f3fb02e3c48d6a61f6031eba0c0266faceed2b24bbb46363f20
Сообщение M = af
Дополнение M1 = af||8||0125
хэш-значение = 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) В приложении скрипт, выполняющий все эти действия.
E(k,m) = X[K13]∘ |
|
L∘ P∘ S∘ X[Ki](m), |