ECIES

ECIES (англ. Elliptic Curve Integrated Encryption Scheme) — це схема шифрування на відкритих ключах, що ґрунтується на еліптичних кривих. Цю схему запропонував 2001. ECIES використовується в різних стандартах, наприклад ANSI X9.63, IEEE 1363a, ISO 18033-2 і 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. Encriptyon (ENC) — алгоритм шифрування, що використовується обома сторонами.
4. Method Authentication Code (MAC) — функція для генерації автентифікаційних даних (імітовставка).
5. Hash (HASH) — функція хешування (використовується в MAC і KDF).

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

Перша сторона — Аліса:

• ${\displaystyle P_{B}}$ — відкритий ключ Боба
• ${\displaystyle p_{a}}$ — власний закритий ключ
• Ε — група точок еліптичної кривої над
• G — циклічна підгрупа групи точок E еліптичної кривої
• g — генератор підгрупи G

Друга сторона — Боб:

• ${\displaystyle P_{A}}$ — відкритий ключ
• ${\displaystyle p_{b}}$ — власний закритий ключ
• Ε — група точок еліптичної кривої над
• G — підгрупа групи точок E еліптичної кривої
• g — генератор підгрупи G

Шифрування

Припустимо, Аліса хоче послати повідомлення Бобу. Аліси має відкритий ключ Боба ${\displaystyle P_{B}}$ у Боба — відповідний закритий ключ ${\displaystyle p_{b}}$, також Аліса генерує тимчасову пару своїх відкритого ${\displaystyle P_{A}}$ і закритого ${\displaystyle p_{a}}$ ключів. Закриті ключі — елементи кінцевого поля (поля, на якому задана еліптична крива), а відкриті ключі — точки, що належать еліптичній кривій і обчислені як добуток закритого ключа і генератора g еліптичної кривої.

Для відправки повідомлення Аліса виконує наступні дії:

• За допомогою методу генерації загального секрету KA Аліса обчислює загальний секрет ${\displaystyle s}$ = ${\displaystyle p_{a}}$ × ${\displaystyle P_{B}}$ (за протоколом Діффі — Геллмана).

• Використовуючи отриманий загальний секрет ${\displaystyle s}$ і метод отримання ключів з ключовою і додатковою інформацією KDF, Аліса отримує ключ шифрування ${\displaystyle k_{ENC}}$, а також ключ для обчислення імітовставки ${\displaystyle k_{MAC}}$.

• За допомогою симетричного алгоритму шифрування Аліса шифрує відкрите повідомлення ${\displaystyle m}$ ключем ${\displaystyle k_{ENC}}$ і отримує шифротекст ${\displaystyle c}$.

• Взявши ключ ${\displaystyle k_{MAC}}$, зашифроване повідомлення ${\displaystyle c}$ та інші, заздалегідь обговорені сторонами параметри, Аліса обчислює тег повідомлення за допомогою функції MAC.

• Аліса відправляє Бобу {${\displaystyle P_{A}}$, ${\displaystyle tag}$, ${\displaystyle c}$}.

Розшифрування

Щодо процесу розшифрування кроки, які повинен виконати Боб, є наступними:

• З допомогою отриманого відкритого ключа Аліси й свого закритого ключа отримати загальний секрет ${\displaystyle s}$ = ${\displaystyle p_{b}}$ × ${\displaystyle P_{A}}$ ключі шифрування ${\displaystyle k_{ENC}}$ і імітовставки ${\displaystyle k_{MAC}}$.
• За допомогою ключів шифрування ${\displaystyle k_{ENC}}$ й імітовставки ${\displaystyle k_{MAC}}$ обчислити тег повідомлення і порівняти його з отриманим тегом. Якщо вони не збігаються, Боб повинен відхилити повідомлення через невдачу у процедурі перевірки MAC.
• Якщо теги виявляться однаковими, то Боб може продовжити процес, розшифровуючи зашифроване повідомлення ${\displaystyle c}$, використовуючи симетричний алгоритм Encryption і ${\displaystyle k_{ENC}}$.

Порівняння з іншими алгоритмами

Безпека 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

«М'яка вразливість»

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

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

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

Шоуп також довів, що схема ECIES може бути вразлива, коли функція XOR використовується при шифруванні повідомлень змінної довжини. Зокрема, це може привести до вразливості до атак на основі адаптивного шифротексту (англ. Adaptive Chosen Ciphertext Attacks (CCA2)). Можливі рішення:

• Зафіксувати довжину відкритого тексту.
• Інтерпретувати вихідні дані функції KDF як ${\displaystyle k_{MAC}}$||${\displaystyle k_{ENC}}$.
• Заборонити використання потокових фільтрів в 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: ${\displaystyle k_{MAC}}$||${\displaystyle k_{ENC}}$.
• Схема генерації еліптичної кривої: Brainpool (RFC 5639).

Примітки

1. V. Gayoso Martínez, F. Hernandez Alvarez, L. Hernandez Encinas, с. 1—2.
2. V. Gayoso Martínez, L. Hernández Encinas, C. Sánchez Ávila, с. 9.
3. V. Gayoso Martínez, L. Hernández Encinas, C. Sánchez Ávila, с. 9—10.
4. V. Gayoso Martínez, L. Hernández Encinas, C. Sánchez Ávila, с. 10.
5. N. Koblitz, с. 3—4.
6. V. Gayoso Martínez, L. Hernández Encinas, C. Sánchez Ávila, с. 2.
7. V. Shoup, с. 13.
8. V. Shoup, с. 38.
9. J. Stern, с. 20—21.
10. Quisquater, J., Koeune, F., с. 20.
11. V. Gayoso Martínez, L. Hernández Encinas, A. Queiruga Dios, с. 7—8.
12. V. Gayoso Martínez, L. Hernández Encinas, A. Queiruga Dios, с. 17—18.

Література

Статті

• 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.
• J. Quisquater, F. Koeune,. ECIES — Security evaluation of the encryption scheme and primitives.
• V. Gayoso Martínez, L. Hernández Encinas, A. Queiruga Dios. ECIES — Security evaluation of the encryption scheme and primitives.