Что такое RKEM? Рассказывают коллеги из нашей лаборатории криптографии.

❗️Перед созданием защищённого соединения собеседники должны согласовать общий секретный ключ. В некоторых мессенджерах, браузерах и ряде других программ это автоматически выполняется с помощью механизма инкапсуляции ключа (KEM). Однако, как и другие зависящие от источника случайности криптографические механизмы, KEM уязвим для атак, использующих скомпрометированный генератор псевдослучайных чисел (PRNG).

При таких атаках жертву побуждают использовать ненадёжный PRNG со скрытой алгоритмической особенностью (бэкдором). Сгенерированные им числа проходят стандартные тесты на случайность, но предсказуемы для создателя этого PRNG.

🟦В классическом KEM отправитель генерирует шифртекст и общий секретный ключ, используя открытый ключ получателя и случайное число. Если это число может предсказать посторонний, KEM становится бесполезен.

Для защиты от бэкдоров в PRNG был разработан re-randomizable KEM (RKEM) — механизм инкапсуляции ключа с повторной рандомизацией, которая заменяет использованную при инкапсуляции случайность на новую, полученную из независимого источника.

🟦В RKEM вводится дополнительная функция, которая может выполняться третьей стороной, не владеющей секретным ключом (например, криптографическим обратным брандмауэром). Это перерандомизация шифртекста, которая использует гомоморфные свойства схемы шифрования.

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

📌Первые попытки создания RKEM строились на базе схемы Эль-Гамаля и протокола Диффи — Хеллмана. Сейчас этот же принцип используют для разработки постквантовых KEM, устойчивых к бэкдорам в PRNG и некоторым другим видам скрытого вмешательства (tampering). #криптословарь

Канал «Криптонита» в MAX