ECIES

ECIES (eng. Elliptic Curve Integrated Encryption Scheme) — это схема шифрования на открытых ключах, основанная на эллиптических кривых. Эта схема была предложена Виктором Шоупом в 2001 году. ECIES используется в различных стандартах, например, ANSI X9.63, IEEE 1363a, ISO 18033-2 и SECG SEC 1.

Историческая справка

В 1997 году учёными Михиром Белларе и Филлипом Рогавэем была изобретена схема DLAES (Discrete Logarithm Augmented Encryption Scheme), которая впоследствии была переименована в DHAES (Diffie-Hellman Augmented Encryption Scheme) в 1998 году, а позже, во избежание путаницы с аббревиатурой AES, переименована в DHIES(Diffie-Hellman Integrated Encryption Scheme). DHIES представляет собой усовершенствованную схему Эль-Гамаля, в которой используются эллиптические кривые, различные алгоритмы имитовставки и хеш-функции.

DHIES была оценена ANSI и с некоторыми модификациями схема была включена в стандарт ANSI X9.63 в 2001 году. Так же, независимо, с некоторыми поправками схема была включена в стандарт IEEE 1363 в 2000 году. В 2004 году, когда стандарт ANSI X9.63 стал общедоступным, IEEE пересмотрела схему с учётом достоинств двух предыдущих из стандартов ANSI X9.63 и IEEE 1363 и включила новую схему в стандарт IEEE 1363a в 2004 году.

Все вышеперечисленные схемы получили общее название ECIES (Elliptic Curve Integrated Encryption Scheme).

В 2009 году одна из версий ECIES вошла в стандарт ISO/IEC 18033-2, а в 2009 в стандарт SECG SEC 1.

Описание алгоритма

ECIES (Elliptic Curve Integrated Encryption Scheme) включает в себя несколько функций:

1. Key Agreement (KA)- функция для генерации общего секрета. Например, протокол Диффи — Хеллмана либо его модификации.
2. Key Derivation Function (KDF) — функция для генерации общих ключей из некоторого набора данных и параметров.
3. Encryption (ENC) — алгоритм шифрования, использующийся обеим сторонами.
4. Method Authentication Code (MAC) — функция для генерации аутентификационных данных (имитовставка).
5. Hash (HASH) — функция хеширования (используется в MAC и KDF).

Входные параметры алгоритма

Первая сторона — Алиса:

• [math]\displaystyle{ P_B }[/math] — открытый ключ Боба
• [math]\displaystyle{ p_a }[/math] — закрытый собственный ключ
• Ε — группа точек над эллиптической кривой
• G — циклическая подгруппа точек группы E эллиптической кривой
• g — генератор подгруппы G

Вторая сторона — Боб:

• [math]\displaystyle{ P_A }[/math] — открытый ключ Алисы
• [math]\displaystyle{ p_b }[/math] — закрытый собственный ключ
• Ε — группа точек над эллиптической кривой
• G — подгруппа точек группы E эллиптической кривой
• g — генератор подгруппы G

Шифрование

Предположим, Алиса хочет послать сообщение Бобу. У Алисы есть открытый ключ Боба [math]\displaystyle{ P_B }[/math], у Боба — соответствующий закрытый ключ [math]\displaystyle{ p_b }[/math], также Алиса генерирует временную пару своих открытого [math]\displaystyle{ P_A }[/math] и закрытого [math]\displaystyle{ p_a }[/math] ключей. Закрытые ключи — элементы конечного поля (поля, на котором задана эллиптическая кривая), а открытые ключи — точки, принадлежащие эллиптической кривой и вычисленные как произведение закрытого ключа и генератора g эллиптической кривой.

Для отправки сообщения Алиса выполняет следующие действия:

• С помощью метода генерации общего секрета KA Алиса вычисляет общий секрет [math]\displaystyle{ s }[/math] = [math]\displaystyle{ p_a }[/math] × [math]\displaystyle{ P_B }[/math] (по протоколу Диффи — Хеллмана).

• Используя полученный общий секрет [math]\displaystyle{ s }[/math] и метод получения ключей из ключевой и дополнительной информации KDF, Алиса получает ключ шифрования [math]\displaystyle{ k_{ENC} }[/math], а также ключ для вычисления имитовставки [math]\displaystyle{ k_{MAC} }[/math].

• С помощью симметричного алгоритма шифрования Алиса шифрует открытое сообщение [math]\displaystyle{ m }[/math] ключом [math]\displaystyle{ k_{ENC} }[/math] и получает шифротекст [math]\displaystyle{ c }[/math].

• Взяв ключ [math]\displaystyle{ k_{MAC} }[/math], зашифрованное сообщение [math]\displaystyle{ c }[/math] и другие заранее обговорённые сторонами параметры, Алиса вычисляет тэг сообщения с помощью функции MAC.

• Алиса отсылает Бобу {[math]\displaystyle{ P_A }[/math], [math]\displaystyle{ tag }[/math], [math]\displaystyle{ c }[/math]}.

Расшифрование

Относительно процесса расшифрования шаги, которые должен выполнить Боб, являются следующими:

• С помощью полученного открытого ключа Алисы и своего закрытого ключа получить общий секрет [math]\displaystyle{ s }[/math] = [math]\displaystyle{ p_b }[/math] × [math]\displaystyle{ P_A }[/math], ключи шифрования [math]\displaystyle{ k_{ENC} }[/math] и имитовставки [math]\displaystyle{ k_{MAC} }[/math].
• При помощи ключей шифрования [math]\displaystyle{ k_{ENC} }[/math] и имитовставки [math]\displaystyle{ k_{MAC} }[/math] вычислить тэг сообщения и сравнить его с полученным тэгом. Если они не совпадают, Боб должен отклонить сообщение из-за неудачи в процедуре проверки MAC.
• Если тэги окажутся одинаковыми, то Боб может продолжить процесс, расшифровывая зашифрованное сообщение [math]\displaystyle{ c }[/math], используя симметричный алгоритм Encryption и [math]\displaystyle{ k_{ENC} }[/math].

Cравнение с другими алгоритмами

Безопасность ECIES основывается на вычислительной сложности задачи дискретного логарифмирования в группе точек эллиптической кривой (ECDLP). Криптографические алгоритмы также могут основываться на вычислительной сложности задач факторизации (пример алгоритма: RSA) и дискретного логарифмирования (схема Эль-Гамаля). Однако ECDLP считается сложнейшей из этих трёх задач, что приводит к важному преимуществу ECIES: размеру ключа.

Сравнение длин ключей ECIES и RSA

Уровень безопасности (бит)	Длина ключа RSA (бит)	Длина ключа ECIES (бит)
80	1024	160-223
112	2048	224-255
128	3072	256-283
192	7680	384-511
256	15360	512-571

Преимущество в размер ключа позволяет предъявлять меньшие требования к аппаратному обеспечению (например, к размерам буфера, оперативной и физической памяти; к пропускной способности канала в случае передачи ключей по сети).

Важным недостатком ECIES по сравнению с другими криптографическими алгоритмами является существование нескольких версий ECIES, описываемых различными стандартами (ANSI X9.63, IEEE 1363a, ISO/IEC 18033-2 и SECG SEC 1). Различия между данными стандартами — выбор конкретных функций и параметров для реализации составляющих ECIES (KA, KDF, ENC, MAC, HASH). Недостаток заключается в том, что невозможно реализовать версию ECIES, удовлетворяющую всем стандартам.

Известные атаки на ECIES

«Мягкая уязвимость»

Виктор Шоуп доказал, что если публичный ключ U не включён во входные данные функции KDF и, если в KDF используется только x-координата разделённого секрета, то ECIES подвержен атакам на основе адаптивного шифротекста (eng. Adaptive Chosen Ciphertext Attacks (CCA2)). Уязвимость названа «мягкой», так как никакая атака не смогла получить значимую информацию с использованием этой уязвимости.

Одно из возможных решений, предложенных Шоупом — добавить публичный ключ U во входные данные функции KDF.

Уязвимость при использовании функции XOR

Шоуп также доказал, что схема ECIES может быть уязвима, когда функция XOR используется при шифровании сообщений переменной длины. В частности, это может привести к уязвимости для атак на основе адаптивного шифротекста (англ. Adaptive Chosen Ciphertext Attacks (CCA2)). Возможные решения:

• Зафиксировать длину открытого текста.
• Интерпретировать выходные данные функции KDF как [math]\displaystyle{ k_{MAC} }[/math]||[math]\displaystyle{ k_{ENC} }[/math].
• Запретить использование потоковых фильтров в ECIES (разрешить только блочные шифры).

Атака малыми подгруппами (англ. ‘’Small subgroup attack’’)

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

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

Возможная конфигурации ECIES

Пример эффективной и безопасной реализации ECIES, совместимой со стандартами IEEE 1363a и ISO/IEC 18033-2:

• KA: Протокол Диффи — Хеллмана
• Hash: SHA-512 (SHA-256 для устройств с ограниченными ресурсами).
• KDF: KDF2.
• ENC: AES-128 в режиме сцепления блоков CBC mode.
• MAC: HMAC-SHA-512 (HMAC-SHA-256 для устройств с ограниченными ресурсами).
• Разделение секрета: Использовать только первую координату (без хеширования).
• Интерпретация выходных данных KDF: [math]\displaystyle{ k_{MAC} }[/math]||[math]\displaystyle{ k_{ENC} }[/math].
• Схема генерации эллиптической кривой: Brainpool (RFC 5639).

Литература

Статьи

• Víctor Gayoso Martínez, L. Hernández Encinas, Carmen Sánchez Ávila. A Survey of the Elliptic Curve Integrated Encryption Scheme (англ.).
• Victor Shoup. A Proposal for an ISO Standard for Public Key Encryption (version 2.1) (англ.).
• Neha Gupta, Harsh Kumar Singh, Anurag Jain. An Efficient Implementation For Key Management Technique Using Smart Card And ECIES Cryptography (англ.).
• V. Gayoso Mart´ınez, F. Hernandez Alvarez, L. Hernandez Encinas. Information Processing and Coding (англ.).
• N. Koblitz. Elliptic curve cryptosystems (англ.) // Mathematics of Computation.
• J. Stern. Evaluation report on the ECIES cryptosystem cryptosystems (англ.). Архивировано 1 февраля 2013 года.
• J. Quisquater, F. Koeune,. ECIES - Security evaluation of the encryption scheme and primitives (англ.). Архивировано 31 марта 2017 года.
• V. Gayoso Martínez, L. Hernández Encinas, A. Queiruga Dios. ECIES - Security evaluation of the encryption scheme and primitives (англ.).