CTF → SHA1 length extension

Многие популярные хеши, такие как MD5, SHA0, SHA1, SHA2 построены на общем принципе, односторонней функции сжатия Меркле-Дамгарда. Для того чтобы функция имела возможность принимать на вход данные любого размера, они выравниваются таким образом, чтобы их размер был сравним с 448 по модулю 512. Процесс выравнивания выглядит так - к входным данным дописывается единичный бит, оставшиеся биты устанавливаются в 0, а последние 64 устанавливаются в длину сообщения. Основываясь на этой особенности данного семейства хешей , атакующий может провести так называемую length extension attack. Атака заключается в том, что для заданной H(p||m) можно вычислить H(p||m||pad(p||m)||m') зная только m и длину p. Для этого мы инициализируем хеш функцию заданным значением, затем вычисляем и добавляем padding, после этого считаем хеш от m+padding+m', результат будет эквивалентен H(p||m||pad(p||m)||m').
Пример реализации данной атаки для SHA1 прилагается.