Протокол Діффі — Геллмана

Протокол Діффі — Геллмана

Схематична ілюстрація протоколу на прикладі змішування фарб
Клас	Протокол узгодження ключів
Структура даних	Швидкодія та криптографічна стійкість залежать від обраного простору (циклічної групи)

Протокол Діффі — Геллмана (англ. Diffie–Hellman key exchange (D–H)) — це метод обміну криптографічними ключами. Один з перших практичних прикладів узгодження ключа, що дозволяє двом учасникам, що не мають жодних попередніх даних один про одного, отримати спільний секретний ключ із використанням незахищеного каналу зв'язку. Цей ключ можна використати для шифрування наступних сеансів зв'язку, що використовують шифр з симетричним ключем.

Схему вперше оприлюднили Вітфілд Діффі і Мартін Геллман у 1976, хоча пізніше стверджувалось, що її кількома роками раніше винайшов Малколм Вільямсон у GCHQ, британській розвідувальній агенції. 2002 року Геллман запропонував називати алгоритм Обмін ключами Діффі — Геллмана — Меркле у визнання внеску Ральфа Меркле в винайденні криптосистем із відкритим ключем.

Хоча протокол Діффі — Геллмана є анонімним (без автентифікації) протоколом встановлення ключа, він забезпечує базу для різноманітних протоколів з автентифікацією, і використовується для забезпечення цілковитої прямої секретності в недовговічних режимах Transport Layer Security (відомих як EDH або DHE залежно від комплектації шифру).

U.S. Patent 4,200,770, термін дії якого наразі вибіг, описує алгоритм і заявляє Геллмана, Діффі і Меркле як винахідників.

Історія

Діффі й Геллман запропонували у 1976 році алгоритм для створення криптографічних систем з відкритим ключем, який так само, як і алгоритм Ель–Гамаля, базується на складності обчислення дискретного логарифма. Алгоритм Діффі — Геллмана може бути використаний для розподілу ключів (генерування секретного ключа), але його не можна використовувати для шифрування повідомлення.

Алгоритм узгодження ключа Діффі — Геллмана запатентовано у США та Канаді. Ліцензію на цей патент разом з іншими патентами в області криптографії з відкритим ключем отримала група Public Кеу Partners (PKP). Термін дії патенту США вибіг у 1997 році.

Алгоритм Діффі — Геллмана також працює в комутативних кільцях. Шмулі та Кевін МакКерлі запропонували варіант алгоритму, в якому модуль є складеним числом. Міллер і Ніл Кобліц розширили цей алгоритм для використання з еліптичними кривими. Ель–Гамаль використовував основоположну ідею алгоритму Діффі — Геллмана для створення алгоритму шифрування та цифрового підпису. Також є варіант алгоритму для роботи в полі Галуа. У низці реалізацій використаний цей підхід, оскільки обчислення виконуються набагато швидше, але важливо ретельно вибирати поле досить великим, аби забезпечити необхідну стійкість.

Криптографічна стійкість алгоритму Діффі — Геллмана заснована на передбачуваній складності задачі дискретного логарифмування (англ. discrete logarithm problem). Однак, хоча вміння розв'язувати задачу дискретного логарифмування дозволить зламати алгоритм Діффі — Геллмана, зворотне твердження ще не доведене.

Необхідно відзначити, що простий алгоритм Діффі — Геллмана працює тільки на лініях зв'язку, надійно захищених від модифікації. Тоді, коли в каналі можлива модифікація даних, з'являється можливість атаки «людина посередині».

Опис алгоритму

Алгоритм Діффі — Геллмана, де K — підсумковий спільний секрет (ключ)

Узгодження спільного таємного ключа відбувається таким чином.

Нехай G — скінченна циклічна група потужністю |G| породжена g.

Аліса і Боб таємно обирають два випадкових цілих числа s_A та s_B, в інтервалі [0, |G| − 1]. Потім вони таємно обчислють числа a_A = g^s_A та a_B = g^s_B відповідно, та обмінюються ними через незахищений канал передачі даних. Нарешті, Аліса та Боб обчислюють a_BA = a_B^s_A = g^s_Bs_A та a_AB = a_A^s_B = g^s_As_B відповідно. Слід зазначити, що a_AB = a_BA, і тому це число може служити спільним таємним ключем K Аліси та Боба.

Точніше, тепер Аліса та Боб можуть скористатись відображенням елементів множини G у простір іншої криптосистеми. Наприклад, вони можуть використати блок даних необхідного розміру (зокрема, молодші біти) значення a_AB як ключ звичайної блокової криптосистеми.

Запропоновано варіанти протоколу Діффі — Геллмана для різних множин. Зокрема: мультиплікативні групи над великими скінченними полями (поля простих чисел або розширення), мультиплікативна група залишків за модулем складеного числа, еліптичні криві над скінченними полями, якобіан гіпереліптичних кривих над скінченним полем, та факторгрупи уявних квадратичних полів.

Однак, базовий варіант протоколу узгодження ключа анонімний, тут відсутня можливість автентифікації абонентів. Таким чином, протокол вразливий для атаки «людина посередині». Припустімо, що зловмисник C здатен здійснювати підміну повідомлень, якими обмінюються Аліса та Боб. Тоді він може згенерувати числа s^*_A та s^*_B, і відповідно, отримати два узгоджених ключа: g^s_As*_B та g^s*_As_B. В результаті зловмисник отримує можливість повністю контролювати обмін повідомленнями між Алісою та Бобом. При цьому вони не здатні виявити підміну та вважатимуть, що зв'язуються один з одним.

Для розв'язання цієї проблеми були запропоновані підсилені варіанти протоколу. Зокрема:

• Попереднє поширення сертифікатів (англ. static DH),
• Протоколи MTI (за прізвищами авторів англ. Matsumoto, Takashima, Imai),
• Відкритий розподіл ключів із використанням автопідписаних ключів,
• Протокол KEA (англ. Key Exchange Algorithm),
• Протокол «уніфікована модель» (англ. unified model),
• Протокол MQV (автори: англ. Law, Menezes, Qu, Solinas, Vanstone).

З автентифікацією абонентів:

• Протокол STS (англ. station-to-station),
• Протокол DHKE.

Приклад

Єва — криптоаналітик, прослуховувач. Вона читає листування Боба і Аліси, але не може змінити вмісту повідомлень.

• s = секретний ключ. s = 2
• g = відкрите просте число. g = 5
• p = відкрите просте число. p = 23
• a = секретний ключ Аліси. a = 6
• A = відкритий ключ Аліси. A = g^a mod p = 8
• b = секретний ключ Боба. b = 15
• B = відкритий ключ Боба. B = g^b mod p = 19

Аліса знає не знає p = 23 b = ? g = 5 a = 6 A = 56 mod 23 = 8 B = 5b mod 23 = 19 s = 196 mod 23 = 2 s = 8b mod 23 = 2 s = 196 mod 23 = 8b mod 23 s = 2

Боб знає не знає p = 23 a = ? g = 5 b = 15 B = 515 mod 23 = 19 A = 5a mod 23 = 8 s = 815 mod 23 = 2 s = 19a mod 23 = 2 s = 815 mod 23 = 19a mod 23 s = 2

Єва знає не знає p = 23 a = ? g = 5 b = ? s = ? A = 5a mod 23 = 8 B = 5b mod 23 = 19 s = 19a mod 23 s = 8b mod 23 s = 19a mod 23 = 8b mod 23

Складність зламу

Постає питання: «Наскільки складно обчислити DH-функцію за умови великого $p$?» Припустимо, що $p$ має $n$ біт завдовжки, тоді найліпший з відомих на сьогодні алгоритмів GNFS має час виконання $exp({\tilde {O}}({\sqrt[{3}]{n}}))$, підекспоненційний час виконання.

Приблизна порівняльна таблиця між складністю злому шифру з різними довжинами ключів і обчисленням функції Діффі — Геллмана в первинному варіанті і в варіанті, коли замість обчислень за модулем використовується інший алгебраїчний об'єкт:

Розмір ключа шифру	розмір модуля	розмір еліптичної кривої
80	1024	160
128	3072	256
256	15360	512

Обчислити функцію Діффі — Геллмана можна через обчислення $a$ з $A=g^{a}(\operatorname {mod} p)$ і $b$ з $B=g^{b}(\operatorname {mod} p)$. Це є проблема дискретного логарифма, яка обчислювальна нерозв'язна при достатньо великих $p$. Обчислення дискретного алгоритму за модулем $p$ потребує приблизно стільки ж часу як факторизація добутку двох простих чисел розміру як і $p$, саме на це покладається безпека криптосистем RSA. Отже протокол Діффі — Геллмана приблизно так само безпечний як безпечний RSA.

Більше двох учасників

Протокол Діффі — Геллмана не обмежується можливістю узгодження ключа між двома учасниками. Будь-яка кількість учасників може узяти участь в узгоджені ключа через ітеративне виконання протоколу узгодження і обмін проміжними даними (які не мають бути засекреченими). Наприклад, Аліса, Боб і Керол можуть узяти участь в узгоджені так (всі дії відбуваються за модулем $p$):

1. Учасники домовляються про параметри алгоритму $p$ і $g$.
2. Учасники генерують власні ключі, названі $a$, $b$ і $c$.
3. Аліса обчислює $g^{a}$ і відправляє Бобу.
4. Боб обчислює $(g^{a})^{b}=g^{ab}$ і відправляє Керол.
5. Керол обчислює $(g^{ab})^{c}=g^{abc}$ і використовує як свій секрет.
6. Боб обчислює $g^{b}$ і відправляє Керол.
7. Керол обчислює $(g^{b})^{c}=g^{bc}$ і відправляє Алісі.
8. Аліса обчислює $(g^{bc})^{a}=g^{bca}=g^{abc}$ і використовує як свій секрет.
9. Керол обчислює $g^{c}$ і відправляє Алісі.
10. Аліса обчислює $(g^{c})^{a}=g^{ca}$ і відправляє Боб.
11. Боб обчислює $(g^{ca})^{b}=g^{cab}=g^{abc}$ і використовує як свій секрет.

Підслуховувач може бачити $g^{a}$, $g^{b}$, $g^{c}$, $g^{ab}$, $g^{ac}$ і $g^{bc}$, але не здатен використати яку-небудь з комбінацій для відтворення $g^{abc}$.

Для розширення механізму на більші групи, треба дотримуватись двох засад:

• Починаючи з простого ключа $g$, секрет утворюється піднесенням поточного значення до приватного показника один раз, в будь-якому порядку (перше таке піднесення до степеня дає нам відкритий ключ учасника).
• Будь-яке проміжне значення (яке має до $N-1$ виконаних піднесень до приватних показників, де $N$ є число учасників у групі) можна показувати, але кінцеве значення (із застосованими всіма $N$ показниками) містить спільний секрет і не може бути оприлюднене. Отже, кожен користувач повинен отримати свою копію спільного секрету застосуванням власного приватного ключа останнім.

Ці принципи залишають відкритими варіанти обрання порядку в якому учасники подають ключі. Найпростіший і найочевидніший розв'язок полягає у впорядкуванні $N$ учасників по колу і обійти коло для кожного з них, доки кожен з учасників не зробить внеску в кожен з $N$ ключів (з його останнім). Однак, це вимагає від кожного учасника виконати $N$ піднесень за модулем.

Через обрання оптимальнішого порядку, і покладання на те, що ключі можуть повторюватись, можливо зменшити кількість піднесень у степінь за модулем виконаних кожним учасником до $\log _{2}(N)+1$, через використання підходу розділяй і володарюй, наведеному тут для восьми учасників:

1. Кожен з учасників A, B, C і D виконують одне піднесення, породжуючи $g^{abcd}$; це значення посилається до E, F, G і H. В свою чергу. учасники A, B, C і D отримують $g^{efgh}$.
2. Учасники A і B виконують одне піднесення, породжуючи $g^{efghab}$, яке посилається до C і D, а C і D роблять це саме, породжуючи $g^{efghcd}$, яке вони посилають до A і B.,
3. Учасник A виконує піднесення, породжуючи $g^{efghcda}$, яке він посилає B; подібно, B посилає $g^{efghcdb}$ A. C і D чинять подібно.
4. Учасник A здійснює одне завершальне піднесення, і отримує секрет $g^{efghcdba}=g^{abcdefgh}$, тоді як B робить те саме для отримання $g^{efghcdab}=g^{abcdefgh}$; знову, C і D роблять подібним чином.
5. Учасник від E до H одночасно виконують ті самі операції, використовуючи $g^{abcd}$ як початкове значення.

По завершені алгоритму, всі учасники володітимуть секретом $g^{abcdefgh}$, але кожен з них виконає лише чотири модульні піднесення, а не вісім, як того потребує просте впорядкування по колу.

Неінтерактивність протоколу

Відкриті профілі користувачів у Фейсбуці, можуть стати в пригоді для автономного отримання секретного ключа. Андрію для отримання спільного ключа з Сергієм потрібно прочитати $g^{c}$ і піднести до степеня $a$, Сергію аналогічно

У випадку включення свого внеску до протоколу Діффі — Геллмана до свого відкритого фейсбук-профіля, користувачі не потребують спілкування для узгодження секретного ключа. Одразу по прочитанні відкритого профілю користувача, з ним можна починати безпечний зв'язок. Цю властивість іноді називають властивість неінтерактивності протоколу Діффі — Геллмана.

Чи можемо ми це зробити, також неінтерактивно, для більш ніж двох учасників? Тобто, чи може Андрій прочитати $g^{b},g^{c},g^{d}$ і одразу отримати спільний секретний ключ з Богданом, Сергієм і Дмитром — $K_{ABCD}$? На сьогодні відомо, що це можна зробити для трьох учасників, протокол називається Joux і використовує дуже складну математику. Для більш ніж трьох учасників ця проблема відкрита.

Припущення Діффі — Геллмана

$G$ — скінченна циклічна група порядку $n$. $g$ — випадковий породжувач групи. $a,b$ — довільні показники.

CDH

Обчислювальне припущення Діффі — Геллмана (англ. computational Diffie–Hellman assumption):

$Pr[A(g,g^{a},g^{b})\Rightarrow g^{ab}]$ — нехтовна мала.

HDH

Геш припущення Діффі — Геллмана (англ. hash Diffie–Hellman assumption), сильніше від CDH:

$(g,g^{a},g^{b},H(g^{b},g^{ab}))\approx _{p}(g,g^{a},g^{b},R),R{\overset {\underset {\mathrm {r} }{}}{\leftarrow }}K$

Посилання

• Пояснення протоколу Діффі — Геллмана за 5 хвилин на YouTube (англ.)
• RFC 2631 – Метод узгодження ключів Діффі–Геллмана E. Rescorla липень 1999. (англ.)
• Державна служба спеціального зв'язку та захисту інформації України, Наказ № 112: ТЕХНІЧНІ СПЕЦИФІКАЦІЇ форматів криптографічних повідомлень. Захищені дані [Архівовано 12 березня 2017 у Wayback Machine.]