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

Кроме длинного списка требований прилагался еще более фантастический список ожиданий: серьезные математические способности, опыт в криптографии, анализе и тому подобное. Но также предлагалось решить пазл тест: закодированное сообщение, которое требовалось расшифровать.

Хотя тема для меня абсолютно нова и близко не подхожу под требования, но решил, ради простого интереса, попытаться разгадать зашифрованное сообщение. Посмотреть, чем завлекают хакеров на работу.

Сообщение было закодировано в base64:
KDF function uses only this sentence as input for a generic hash algorithm which has a 32 bytes output.
Encryption algorithm is AES CBC with the concatenated key and init vector as KDF output.
Here is the encrypted question: далее шел текст закодированного сообщения как шестнадцатеричная строка.

KDF

Первое, что бросилось в глаза, это неизвестное мне KDF function.

Key Derivation Function — это такая функция, которая служит для получения секретных ключей из какого-то другого секретного значения для задач защиты информации.

Наиболее распространенная задача для KDF — это хеширование паролей. Где требуется усложнить взлом скомпрометированных хешей.
update (спасибо frol):
Задача KDF — сгенерировать вывод, который не только сложно обратить (задача хеш функций), но ещё и удовлетворяющий требованиям случайности последовательности (это требование исходит от алгоритмов шифрования, с которыми как раз и применяют KDF для параметров инициализации). Таким образом да, наиболее распространённая задача KDF — «хеширование» паролей, но не для сохранения в БД (хотя и так можно), а для дальнейшего использование этих «паролей» в качестве входных данных в шифровании.

А разве обычный sha-2 с солью не подходит для задах хеширования, сохранения и защиты паролей?

Вот KDF обеспечивают лучшую защиту секретных ключей (такие как пароли), чем обычные криптографические хеш-функции. Получается это за счет растяжения ключа (key stretching) и возможность использовать разные псевдослучайные хеш-функции (pseudo-random hash-function).

Если хеши паролей получались обычными криптографическими функциями, как md5, sha256 и другими, то атаки по словарю, или полный перебор будет происходит на порядки быстрее, чем если бы были использованы какие-то функции получения ключа (KDF) на основе этих же хеш-функций общего назначения.

Все дело в том, что применяя растяжение ключа, а именно многократное повторение хеширования, позволяет управлять сложностью подбора хеша, использованной памяти и процессорным временем. Что в итоге дает многократное усложнение взлома.

Когда легальным пользователям необходимо произвести вычисление только один раз (например, получение хеша пароля и сравнение с сохраненным значением), то злоумышленнику требуется произвести миллиарды таких вычислений, что при правильной настройки KDF не дает почти никаких шансов на успех.

Виды KDF

И вот разобрались с KDF, теперь вернемся к первой подсказке.
KDF function uses only this sentence as input for a generic hash algorithm which has a 32 bytes output.

Так как обычно KDF использует криптографические хеш-функции общего назначения как псевдослучайные, то понятно, что есть некая KDF, которая берет это предложение и использует некую общую функцию, которая возвращает 32 байта.

Какие же есть в природе разновидности KDF?
Вот примерный список:
KDF1, KDF2, KDF3, KDF4, MGF1, PBKDF-Schneier, PBKDF1, PBKDF2, bcrypt, scrypt, HKDF.

Многовато, надо бы исключить заведомо неверные.
Просмотрев описание каждой функции, удалил из списка те, которые либо устарели и тяжело найти реализацию, либо нет информации о псевдослучайных функциях.

Остались наиболее современные и актуальные: PBKDF2, bcrypt, scrypt, HKDF.

Казалось, наиболее перспективный претендент — это PBKDF2. Но на вход получает, кроме хеш-функции, еще и соль, количество итераций и количество выходных байт.

Далее выяснилось, что bcrypt обязательно на вход требует соль, да еще от реализации зависит количество итераций. Так как про соль из сообщения нам ничего не известно, bcrypt выбывает из претендентов.

Потом идет scrypt — наиболее криптостойкая современная KDF, которая использует HMAC_SHA256 как псевдослучайную функцию (что нам подходит, так как выход будет 32 байта), но также принимает на вход соль, количество итераций или вычислительную сложность, размер блока и коэффициент распараллеливания.

Остается так же и HMAC-based Extract-and-Expand Key Derivation Function или HKDF.

Поиск ключа

Второй этап расшифровки, это понять как расшифровывать.
В подсказке говорится: Encryption algorithm is AES CBC with the concatenated key and init vector as KDF output.

С алгоритмом шифрования все ясно — это AES в режиме шифрования CBC.

Для расшифровки требуется знать помимо ключа и вектор инициализации, так еще какой вариант AES используется, с размером блока 128, 192 или 256 бит.

Нам дали подсказку, что ключ и вектор инициализации (скорее всего) это выход KDF.
Вы уже почувствовали количество неизвестных параметров?

Тут начинаются танцы, потому что такие функции как PBKDF2 или scrypt могут возвращать считай почти любое количество байт, а HKDF возвращает в зависимости от псевдослучайной функции.

А еще неизвестны параметры сложности вычисления для PBKDF2 и scrypt, также неизвестна соль. И неясно какой размер ключа AES и какой размер вектора инициализации.

Благо выяснилось, что размер этого вектора должен совпадать с размером блока. Например, для rijndael-128 (rijndael — это другое название AES) — размер блока 128 бит или 16 байт. Поэтому в этом варианте размер вектора инициализации должен быть ровно 16 байт.

Также оказалось, что ключ не может быть больше, чем 32 байта.

Расшифровка

Теперь можно приступать к самой расшифровке.
И сейчас ясно, что надо взять результат работы KDF, из них от 0 до 32 байта — это ключ, а дальше, в зависимости от варианта AES, вектор инициализации: 16, 24 или 32 байта.

Получается, что размер результата работы KDF должен быть не больше 64 байта, чтобы вместить в себя 32 байта ключа и 32 байта вектора инициализации.

После проверки на базовых параметрах: пустая соль, простые коэффициенты (единички), не удалось получить результат.
Поэтому пришлось начать паниковать.

Паника

Для PBKDF2 перебирался только один параметр — итерации шифрования, но с пустой солью (так как не ясно было откуда брать эту соль).
Для scrypt перебирались сразу три параметра: размер блока, коэффициент распараллеливания и сложность.

Несмотря на то, что ключ и вектор инициализации также подбирались, никаких результатов не появилось.

Начал коситься на просто hash-based message authentication code (HMAC) варианты хешей, но везде говорилось, что это используется в качестве псевдослучайной функции, а не как KDF.
Но, перепробовав все варианты с HMAC, так и не получил результата.

Свет в конце

В одной из работ, посвященной scrypt, обнаружил, что как KDF могут быть использованы и просто хеш-функции общего назначения, которые не были специально спроектированы как функции получения ключа, что конечно плохая практика.

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

И оказалось, что при использовании rijndael-128 (16 байт размер вектора и блока), хеш-функции sha256, результат которой 32 байта делился на ключ 16 байт, и остальные 16 байт на вектор инициализации, получилось расшифровать исходное сообщение. В котором просто предлагалось послать письмо на определенный адрес.

Одной рукой печатаю, другой слезы вытираю. Все оказалось гораздо проще, чем виделось сначала.