PKCS#1 OAEP

PKCS#1 OAEP (Optimal Asymmetric Encryption Padding) — это криптографический протокол, предназначенный для безопасного шифрования данных с использованием асимметричных алгоритмов, в первую очередь RSA. Он представляет собой схему дополнения (padding) открытого текста перед его зашифрованием, которая вводит элемент случайности и гарантирует, что даже при многократном шифровании одного и того же сообщения одним и тем же открытым ключом получаемые шифротексты будут различаться. Основное назначение OAEP — устранение уязвимостей, присущих детерминированным и нестойким схемам дополнения, таким как PKCS#1 v1.5, и обеспечение свойства семантической стойкости (security against chosen-plaintext attacks, CPA) и стойкости к атакам на основе подобранного шифротекста (chosen-ciphertext attack, CCA).

История

Разработка OAEP была инициирована в 1994 году криптографами Михаилом Белларе и Филипом Рогауэем. В 1995 году они представили схему на конференции Eurocrypt. Изначально OAEP был предложен как универсальная конструкция, которая могла бы быть использована с любой односторонней перестановкой с лазейкой (trapdoor permutation), включая RSA. Однако в 2001 году Виктор Шуп и другие исследователи обнаружили, что прямое применение OAEP к RSA не обеспечивает доказуемую стойкость к атакам на основе подобранного шифротекста (CCA) в стандартной модели. В ответ на это была разработана модификация, известная как OAEP+ (или OAEP+), которая исправляет этот недостаток.

В 2002 году схема OAEP была стандартизирована в рамках PKCS#1 v2.1 (Public-Key Cryptography Standards #1), разработанного компанией RSA Laboratories. Позже она была включена в более широкий стандарт PKCS#1 v2.2, а также в криптографические стандарты ANSI X9.44 и IEEE P1363. В настоящее время OAEP является рекомендуемой схемой дополнения для RSA во многих криптографических библиотеках и протоколах, включая TLS (Transport Layer Security) и OpenPGP.

Принцип работы

OAEP основан на конструкции «Feistel-like network» (сеть Фейстеля) и использует две криптографические хеш-функции: G и H. Функция G расширяет короткое случайное значение до длины, равной длине блока данных, а функция H сжимает блок данных до короткого значения. В стандартной реализации OAEP (например, в PKCS#1 v2.2) в качестве G и H обычно используется одна и та же хеш-функция (например, SHA-256), но с разными способами применения.

Процесс шифрования

Подготовка данных: Исходное сообщение M дополняется до длины n (размер модуля RSA в байтах минус 1) с помощью добавления нулевых байтов и метки (label), которая может быть пустой строкой. В результате получается блок данных DB (Data Block).
Генерация случайного числа: Генерируется случайное число r длиной, равной длине хеша (например, 32 байта для SHA-256).
Применение функции G: К случайному числу r применяется функция G, которая расширяет его до длины DB. Результат обозначается как G(r).
Вычисление маскированного блока: Выполняется операция XOR между DB и G(r): maskedDB = DB ⊕ G(r).
Применение функции H: К маскированному блоку maskedDB применяется функция H, которая сжимает его до длины хеша. Результат обозначается как H(maskedDB).
Вычисление маскированного случайного числа: Выполняется операция XOR между r и H(maskedDB): maskedSeed = r ⊕ H(maskedDB).
Формирование зашифрованного блока: Объединяются maskedSeed и maskedDB в единый блок, который затем интерпретируется как целое число, меньшее модуля RSA. Это число и шифруется с помощью RSA.
Шифрование RSA: Полученное целое число возводится в степень открытого ключа e по модулю n: c = m^e mod n, где m — это блок, полученный на шаге 7.

Процесс расшифрования

Расшифрование RSA: Шифротекст c возводится в степень секретного ключа d по модулю n: m = c^d mod n.
Разделение блока: Полученное целое число m преобразуется обратно в байтовый блок, который разделяется на maskedSeed (первые байты, равные длине хеша) и maskedDB (оставшиеся байты).
Восстановление случайного числа: К maskedDB применяется функция H, результат XOR-ится с maskedSeed для восстановления r: r = maskedSeed ⊕ H(maskedDB).
Восстановление блока данных: К восстановленному r применяется функция G, результат XOR-ится с maskedDB для восстановления DB: DB = maskedDB ⊕ G(r).
Проверка корректности: Из DB извлекается исходное сообщение M и проверяется, что дополнение (нулевые байты и метка) соответствует ожидаемому формату. Если проверка не проходит, расшифрование считается неудачным, и возвращается ошибка.

Классификация и варианты

OAEP и OAEP+

OAEP (стандартный): Описан в PKCS#1 v2.1 и v2.2. Обеспечивает стойкость к атакам на основе подобранного шифротекста (CCA) в модели случайного оракула (random oracle model). Однако, как показали Шуп и другие, в стандартной модели (без использования случайных оракулов) прямая конструкция с RSA не является доказуемо стойкой к CCA.
OAEP+: Модификация, предложенная в 2001 году. Вводит дополнительную хеш-функцию и изменяет структуру, чтобы обеспечить доказуемую стойкость к CCA в стандартной модели. OAEP+ используется реже, чем стандартный OAEP, из-за большей сложности и меньшей распространённости в стандартах.

Размеры блоков

Длина сообщения: Максимальная длина сообщения, которое может быть зашифровано с помощью OAEP, зависит от размера модуля RSA и длины используемой хеш-функции. Для модуля RSA длиной k байт и хеш-функции с длиной выхода h байт максимальная длина сообщения составляет k — 2h — 2 байта. Например, для RSA-2048 (k=256) и SHA-256 (h=32) максимальная длина сообщения составляет 256 — 64 — 2 = 190 байт.
Метка (label): OAEP позволяет использовать необязательную метку (label), которая ассоциируется с шифротекстом. Метка может быть пустой строкой или содержать, например, идентификатор отправителя или получателя. Она не шифруется, но участвует в процессе дополнения и проверяется при расшифровании.

Применение

OAEP широко используется в различных криптографических протоколах и системах:

TLS/SSL: В протоколах Transport Layer Security (TLS) и Secure Sockets Layer (SSL) OAEP используется для шифрования предварительного ключа (pre-master secret) при установлении соединения с использованием RSA. В современных версиях TLS (1.2 и 1.3) OAEP является предпочтительной схемой дополнения для RSA.
OpenPGP: В стандарте OpenPGP (RFC 4880) OAEP (под названием RSAES-OAEP) используется для шифрования сообщений с помощью RSA.
Криптографические библиотеки: OAEP реализован в большинстве популярных криптографических библиотек, таких как OpenSSL, Bouncy Castle, Crypto++ и других.
Стандарты PKI: В инфраструктуре открытых ключей (PKI) OAEP используется для шифрования ключей и сертификатов.

Критика и ограничения

Сложность реализации: OAEP является более сложной схемой по сравнению с простым дополнением, что может приводить к ошибкам в реализации. Неправильная реализация, например, неверная проверка формата при расшифровании, может сделать систему уязвимой к атакам, таким как атака по времени (timing attack) или атака на основе подобранного шифротекста.
Зависимость от хеш-функции: Безопасность OAEP напрямую зависит от криптографической стойкости используемой хеш-функции. Если хеш-функция окажется уязвимой (например, SHA-1, для которой найдены коллизии), то OAEP может быть скомпрометирован.
Ограничение на размер сообщения: OAEP накладывает ограничение на максимальный размер шифруемого сообщения, что делает его непригодным для прямого шифрования больших файлов. Для таких целей обычно используется гибридное шифрование, где OAEP применяется для шифрования симметричного ключа, а сам ключ используется для шифрования данных.
Проблемы с доказуемой стойкостью: Как упоминалось выше, стандартный OAEP не имеет доказуемой стойкости к CCA в стандартной модели, хотя на практике считается безопасным при использовании с достаточно большими модулями RSA (например, 2048 бит и более) и стойкими хеш-функциями.

Интересные факты

Название «Optimal Asymmetric Encryption Padding» (Оптимальное асимметричное дополнение шифрования) отражает цель схемы — достичь оптимального уровня безопасности для асимметричного шифрования.
OAEP является одним из немногих криптографических протоколов, который был разработан в рамках академической теории и затем успешно внедрён в промышленные стандарты, что подтверждает его практическую ценность.
В 2012 году исследователи из группы CRYPTREC (Япония) рекомендовали OAEP для использования в государственных криптографических стандартах Японии.

Источники

Bellare, M., Rogaway, P. (1995). Optimal Asymmetric Encryption — How to Encrypt with RSA. Advances in Cryptology — EUROCRYPT '94.
Shoup, V. (2001). OAEP Reconsidered. Journal of Cryptology, 14(2), 125-149.
RSA Laboratories. (2002). PKCS #1 v2.1: RSA Cryptography Standard.
RSA Laboratories. (2012). PKCS #1 v2.2: RSA Cryptography Standard.
RFC 4880: OpenPGP Message Format.
RFC 5246: The Transport Layer Security (TLS) Protocol Version 1.2.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →