SKEME

SKEME — криптографический протокол распространения ключей, созданный в 1996 году Хьюго Кравчиком(англ. Hugo Krawczyk). Он позволяет двум сторонам получить общий секретный ключ, используя незащищённый канал связи.

Протокол SKEME послужил основой для протокола IKE ^[1], определённого в RFC 2409.

Основные свойства протоколаПравить

аутентификация собеседников — уверенность в том, кто является собеседником ^[2];
perfect forward secrecy (PFS) — потеря секретных ключей не ведёт к компрометации прошлой переписки ^[3];
возможность отречения — третье лицо не сможет доказать, что сообщения написаны кем-либо другому адресату ^[4];
strong secrecy — злоумышленник не может детектировать изменение секретного ключа ^[5];
гибкость — четыре возможных режима работы позволяют достичь компромисса между производительностью и безопасностью ^[6].

Режимы и этапыПравить

ОбозначенияПравить

Для описания протокола используются следующие обозначения:

$\text{[math]}$ $\text{[math]}$ $PKE_{A}(arg)$ — шифрование сообщения $\text{[math]}$ $\text{[math]}$ $a r g$ с открытым ключом, принадлежащим стороне A;
$\text{[math]}$ $\text{[math]}$ $H(arg)$ — вычисление криптографической хеш-функции с аргументом $\text{[math]}$ $\text{[math]}$ $a r g$ ;
$\text{[math]}$ $\text{[math]}$ $F_{K}$ — псевдослучайная функция с ключом $\text{[math]}$ $\text{[math]}$ $K$ , результат вычисления которой нельзя предсказать без знания ключа;
$\text{[math]}$ $\text{[math]}$ $id_{A},id_{B}$ — идентификаторы сторон A и B соответственно;
$\text{[math]}$ $\text{[math]}$ $g, p$ — генератор и модуль соответственно, используемые в протоколе Диффи — Хеллмана.

Базовый режимПравить

Первый этапПравить

Во время первого этапа стороны A и B получают эфемерный ключ $\text{[math]}$ $\text{[math]}$ $K_{0}$ , зная открытые ключи друг друга ^[7]. Для этого они обмениваются «половинками ключа», зашифрованными открытыми ключами друг друга, а затем комбинируют «половинки» при помощи хеш-функции.

\text{[math]}

A\longrightarrow B\colon PKE_{B}(K_{A})

\text{[math]}

B\longrightarrow A\colon PKE_{A}(K_{B})

\text{[math]}

K_{0}=H(K_{A},K_{B})

Значения $\text{[math]}$ $\text{[math]}$ $K_{A}$ и $\text{[math]}$ $\text{[math]}$ $K_{B}$ должны быть выбраны случайным образом^[8]. Если сторона A следует протоколу, то она может быть уверена в том, что эфемерный ключ $\text{[math]}$ $\text{[math]}$ $K_{0}$ неизвестен никому, кроме B. Аналогично, сторона B может быть уверена в том, что эфемерный ключ не знает никто, кроме A^[9].

Второй этапПравить

На втором этапе стороны используют протокол Диффи — Хеллмана^[10]. Сторона А выбирает случайное число $\text{[math]}$ $\text{[math]}$ $x$ и вычисляет значение $\text{[math]}$ $\text{[math]}$ $g^{x}{\bmod {p}}$ . Сторона B выбирает случайное число $\text{[math]}$ $\text{[math]}$ $y$ и вычисляет значение $\text{[math]}$ $\text{[math]}$ $g^{y}{\bmod {p}}$ . После этого, стороны обмениваются вычисленными значениями.

\text{[math]}

A\longrightarrow B\colon g^{x}{\pmod {p}}

\text{[math]}

B\longrightarrow A\colon g^{y}{\pmod {p}}

Третий этапПравить

На третьем этапе происходит аутентификация $\text{[math]}$ $\text{[math]}$ $g^{x}$ и $\text{[math]}$ $\text{[math]}$ $g^{y}$ , переданных во время второго этапа, с использованием эфемерного ключа $\text{[math]}$ $\text{[math]}$ $K_{0}$ , полученного на первом этапе.

\text{[math]}

A\longrightarrow B\colon F_{K_{0}}(g^{y},g^{x},id_{A},id_{B})

\text{[math]}

B\longrightarrow A\colon F_{K_{0}}(g^{x},g^{y},id_{B},id_{A})

Включение $\text{[math]}$ $\text{[math]}$ $g^{x}$ в первое сообщение позволяет стороне B убедиться в том, что значение $\text{[math]}$ $\text{[math]}$ $g^{x}$ на втором этапе было действительно передано стороной A^[11]. Значение $\text{[math]}$ $\text{[math]}$ $g^{y}$ в этом же сообщении позволяет B защититься от атаки повторного воспроизведения^[12].

Генерация сессионного ключаПравить

Результатом выполнения протокола является сессионный ключ, вычисляемый как $\text{[math]}$ $\text{[math]}$ $SK=H(g^{xy}{\bmod {p}})$ ^[13].

SKEME без PFSПравить

Режим SKEME без PFS предоставляет возможность обмена ключами без вычислительных затрат, необходимых для обеспечения PFS ^[14]. Для этого на втором этапе вместо значений $\text{[math]}$ $\text{[math]}$ $g^{x}$ и $\text{[math]}$ $\text{[math]}$ $g^{y}$ , стороны посылают друг другу случайные числа $\text{[math]}$ $\text{[math]}$ $nonce_{A}$ и $\text{[math]}$ $\text{[math]}$ $nonce_{B}$ .

\text{[math]}

A\longrightarrow B\colon nonce_{A}

\text{[math]}

B\longrightarrow A\colon nonce_{B}

Третий этап тоже модифицируется. Аргументы функции $\text{[math]}$ $\text{[math]}$ $F_{K_{0}}$ меняются с $\text{[math]}$ $\text{[math]}$ $g^{x}$ и $\text{[math]}$ $\text{[math]}$ $g^{y}$ на $\text{[math]}$ $\text{[math]}$ $nonce_{A}$ и $\text{[math]}$ $\text{[math]}$ $nonce_{B}$ соответственно.

\text{[math]}

A\longrightarrow B\colon F_{K_{0}}(nonce_{B},nonce_{A},id_{A},id_{B})

\text{[math]}

B\longrightarrow A\colon F_{K_{0}}(nonce_{A},nonce_{B},id_{B},id_{A})

Данная модификация второго и третьего этапа позволяет сторонам убедиться в том, что ключ $\text{[math]}$ $\text{[math]}$ $K_{0}$ , полученный на первом этапе, известен обеим сторонам. ^[15].

Результатом выполнения протокола в данном режиме является сессионный ключ, вычисляемый как $\text{[math]}$ $\text{[math]}$ $SK=F_{K_{0}}(arg)$ , где $\text{[math]}$ $\text{[math]}$ $arg=F_{K_{0}}(nonce_{B},nonce_{A},id_{A},id_{B})$ ^[16].

Pre-shared key и PFSПравить

В данном режиме предполагается, что сторонам уже известен секретный ключ (например, ключ задан вручную), и они используют этот ключ для того, чтобы получить новый сессионный ключ ^[17]. В этом режиме первый этап можно пропустить и использовать секретный ключ вместо $\text{[math]}$ $\text{[math]}$ $K_{0}$ . В этом режиме обеспечивается perfect forward secrecy ^[18].

Сессионный ключ в данном режиме вычисляется так же, как в базовом ^[19].

Fast Re-KeyПравить

Fast Re-Key — самый быстрый режим протокола SKEME ^[20]. Этот режим позволяет часто обновлять ключ без вычислительных затрат на асимметричное шифрование и на использование протокола Диффи — Хеллмана ^[21].

В этом режиме предполагается, что ключ $\text{[math]}$ $\text{[math]}$ $K_{0}$ известен сторонам с предыдущего раунда протокола. Первый этап пропускается, а второй и третий этап, а также вычисление сессионного ключа выполняются так же, как в режиме SKEME без PFS ^[22].

ПримечанияПравить

↑ mao2002plausible, 2002, 5 Achieving Complete Deniability, p. 5: «SKEME is a basis for the “Pre-shared-key Mode” in IKE [11].».
↑ krawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «Notice that the key $\text{[math]}$ $\text{[math]}$ $K_{0}$ shared in the SHARE phase can be known only to A and B (assuming their private keys are not compromised) and then only these parties could have generated the above authenticated messages.».
↑ krawczyk96, 1996, 4 Summary of the Main Features, p. 124: «Perfect forward secrecy via Diffie-Hellman exchange provided as part of the basic protocol.».
↑ di2006deniable, 2006, 1 Introduction, p. 403: «For SKEME we show the strong form of deniability guaranteed by our definition».
↑ blanchet2004automatic, 2004, 7 Experimental Results, p. 99: «We have also proved strong secrecy results for the protocols of Otway-Rees [38], Yahalom [21], and Skeme [32].».
↑ krawczyk96, 1996, 4 Summary of the Main Features, p. 124: «SKEME is designed to achieve the requirements listed and discussed in Section 2. In particular, to provide support for the different security scenarios and to allow flexible tradeoffs between security and performance…».
↑ bauer2000security, 2000, 5.1 Four examples, p. 49: «SHARE enables two principals A and B to obtain a shared key, assuming that initially each knows the public key of the other…».
↑ krawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «We stress that the values of $\text{[math]}$ $\text{[math]}$ $K_{A}$ and $\text{[math]}$ $\text{[math]}$ $K_{B}$ need to be chosen as (pseudo-) random values, and fresh for each run of the protocol.».
↑ krawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «If A follows the protocol then she is assured that the shared key $\text{[math]}$ $\text{[math]}$ $K_{0}$ is not known to anybody except B».
↑ krawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «The next phase, EXCH, is used to exchange Diffie-Hellman exponents.».
↑ krawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «The inclusion of $\text{[math]}$ $\text{[math]}$ $g^{x}$ in the first message serves to authenticate (to B) that $\text{[math]}$ $\text{[math]}$ $g^{x}$ came from A».
↑ krawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «the value $\text{[math]}$ $\text{[math]}$ $g^{y}$ in the same message is used to prove to B the freshness of this message (assuming $\text{[math]}$ $\text{[math]}$ $g^{y}$ was freshly chosen by B)».
↑ krawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «The session key SK, which is the key shared between A and B as the result of this protocol, is computed by the parties as $\text{[math]}$ $\text{[math]}$ $SK=H(g^{xy}{\bmod {p}})$ .».
↑ krawczyk96, 1996, 3.3.1 SKEME Without PFS, p. 122: «The mode of SKEME presented in this section is intended to provide the key exchange functionality based on public keys of the parties, but without paying the high performance cost required to achieve PFS.».
↑ krawczyk96, 1996, 3.3.1 SKEME Without PFS, p. 122: «In this way the combination of EXCH and AUTH provides the parties with the assurance that the key $\text{[math]}$ $\text{[math]}$ $K_{0}$ they shared through the SHARE phase is known to both of them…».
↑ krawczyk96, 1996, 3.3.1 SKEME Without PFS, p. 122: «…we define $\text{[math]}$ $\text{[math]}$ $S K$ to be $\text{[math]}$ $\text{[math]}$ $F_{K_{0}}(arg)$ , where $\text{[math]}$ $\text{[math]}$ $a r g$ is the value sent in the message from A to B in phase AUTH…».
↑ krawczyk96, 1996, 3.3.2 Pre-shared key and PFS, p. 123: «In this mode, the protocol assumes that the parties already share a secret key, and that they use this key in order to derive a new and fresh key.».
↑ krawczyk96, 1996, 3.3.2 This mode provides also with perfect forward secrecy (PFS), p. 123.
↑ krawczyk96, 1996, 3.3.2 Pre-shared key and PFS, p. 123: «The computation is identical to that of the basic protocol…».
↑ krawczyk96, 1996, 3.3.3 Fast Re-key, p. 123: «This is the fastest mode of SKEME».
↑ krawczyk96, 1996, 3.3.3 Fast Re-key, p. 123: «It is intended to provide for very frequent key refreshment without going through expensive operations like public key or Diffie-Hellman computations.».
↑ krawczyk96, 1996, 3.3.3 Fast Re-key, p. 123: «Computation of $\text{[math]}$ $\text{[math]}$ $S K$ is identical to that of Section 3.3.1…».

ЛитератураПравить

Krawczyk H. SKEME: A versatile secure key exchange mechanism for internet (англ.) // Network and Distributed System Security, 1996., Proceedings of the Symposium on IEEE. — 1996. — P. 114—127. — ISBN 0-8186-7222-6. — doi:10.1109/NDSS.1996.492418. (недоступная ссылка)

Di Raimondo M., Gennaro R., Krawczyk H. Deniable authentication and key exchange (англ.) // Proceedings of the 13th ACM conference on Computer and communications security. — 2006. — P. 400—409. — ISBN 1-59593-518-5. — doi:10.1145/1180405.1180454.

Boyd C., Mathuria A. Protocols for authentication and key establishment. — Springer, 2003. — 321 с. — ISBN 3-540-43107-1.

Bauer FL., Steinbruggen R. Security Protocols and their Properties (англ.) // Foundations of Secure Computation. — IOS Press, 2000. — Vol. 175. — P. 39-60. — ISBN 1-58603-015-9.

Mao W., Paterson K.G. On the plausible deniability feature of Internet protocols (англ.). — Citeeer, 2002.

Blanchet, B. Automatic proof of strong secrecy for security protocols (англ.) // Proceedings of the 2004 IEEE Symposium on Security and Privacy. — 2004. — P. 86-100. — ISBN 0-7695-2136-3. — doi:10.1109/SECPRI.2004.1301317. Архивировано 3 декабря 2013 года.

СсылкиПравить

[_3f2fa60b74c21ab7-1] 2002plausible, 2002, 5 Achieving Complete Deniability, p. 5: «SKEME is a basis for the “Pre-shared-key Mode” in IKE [11].».

[_b832f9ec447b3d15-2] rawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «Notice that the key $\text{[math]}$ $\text{[math]}$ $K_{0}$ shared in the SHARE phase can be known only to A and B (assuming their private keys are not compromised) and then only these parties could have generated the above authenticated messages.».

[_2e74a94630c72258-3] rawczyk96, 1996, 4 Summary of the Main Features, p. 124: «Perfect forward secrecy via Diffie-Hellman exchange provided as part of the basic protocol.».

[_aa51c2a64e9b2f18-4] 2006deniable, 2006, 1 Introduction, p. 403: «For SKEME we show the strong form of deniability guaranteed by our definition».

[_52caa09db28c7908-5] t2004automatic, 2004, 7 Experimental Results, p. 99: «We have also proved strong secrecy results for the protocols of Otway-Rees [38], Yahalom [21], and Skeme [32].».

[_d74b8d841458a178-6] rawczyk96, 1996, 4 Summary of the Main Features, p. 124: «SKEME is designed to achieve the requirements listed and discussed in Section 2. In particular, to provide support for the different security scenarios and to allow flexible tradeoffs between security and performance…».

[_cd881c5db862cb8c-7] uer2000security, 2000, 5.1 Four examples, p. 49: «SHARE enables two principals A and B to obtain a shared key, assuming that initially each knows the public key of the other…».

[_58034b3828647f00-8] rawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «We stress that the values of $\text{[math]}$ $\text{[math]}$ $K_{A}$ and $\text{[math]}$ $\text{[math]}$ $K_{B}$ need to be chosen as (pseudo-) random values, and fresh for each run of the protocol.».

[_62d12dcc687938ed-9] rawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «If A follows the protocol then she is assured that the shared key $\text{[math]}$ $\text{[math]}$ $K_{0}$ is not known to anybody except B».

[_6aa017e7c714b963-10] rawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «The next phase, EXCH, is used to exchange Diffie-Hellman exponents.».

[_d41de64164819628-11] rawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «The inclusion of $\text{[math]}$ $\text{[math]}$ $g^{x}$ in the first message serves to authenticate (to B) that $\text{[math]}$ $\text{[math]}$ $g^{x}$ came from A».

[_031babd01992877c-12] rawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «the value $\text{[math]}$ $\text{[math]}$ $g^{y}$ in the same message is used to prove to B the freshness of this message (assuming $\text{[math]}$ $\text{[math]}$ $g^{y}$ was freshly chosen by B)».

[_3b16ef9801e0f60c-13] rawczyk96, 1996, 3.2 The Basic Protocol and Its Phases, p. 121: «The session key SK, which is the key shared between A and B as the result of this protocol, is computed by the parties as $\text{[math]}$ $\text{[math]}$ $SK=H(g^{xy}{\bmod {p}})$ .».

[_8d5c583616e86c34-14] rawczyk96, 1996, 3.3.1 SKEME Without PFS, p. 122: «The mode of SKEME presented in this section is intended to provide the key exchange functionality based on public keys of the parties, but without paying the high performance cost required to achieve PFS.».

[_f5eb443b6acdc068-15] rawczyk96, 1996, 3.3.1 SKEME Without PFS, p. 122: «In this way the combination of EXCH and AUTH provides the parties with the assurance that the key $\text{[math]}$ $\text{[math]}$ $K_{0}$ they shared through the SHARE phase is known to both of them…».

[_b6456bd53ae06bcf-16] rawczyk96, 1996, 3.3.1 SKEME Without PFS, p. 122: «…we define $\text{[math]}$ $\text{[math]}$ $S K$ to be $\text{[math]}$ $\text{[math]}$ $F_{K_{0}}(arg)$ , where $\text{[math]}$ $\text{[math]}$ $a r g$ is the value sent in the message from A to B in phase AUTH…».

[_6935304b7e70278c-17] rawczyk96, 1996, 3.3.2 Pre-shared key and PFS, p. 123: «In this mode, the protocol assumes that the parties already share a secret key, and that they use this key in order to derive a new and fresh key.».

[_ac11151974eee5bd-18] rawczyk96, 1996, 3.3.2 This mode provides also with perfect forward secrecy (PFS), p. 123.

[_f9b1953c89de2f82-19] rawczyk96, 1996, 3.3.2 Pre-shared key and PFS, p. 123: «The computation is identical to that of the basic protocol…».

[_8689317e9f48ea49-20] rawczyk96, 1996, 3.3.3 Fast Re-key, p. 123: «This is the fastest mode of SKEME».

[_de3474dab2d16fbf-21] rawczyk96, 1996, 3.3.3 Fast Re-key, p. 123: «It is intended to provide for very frequent key refreshment without going through expensive operations like public key or Diffie-Hellman computations.».

[_ff977615fe87e33f-22] rawczyk96, 1996, 3.3.3 Fast Re-key, p. 123: «Computation of $\text{[math]}$ $\text{[math]}$ $S K$ is identical to that of Section 3.3.1…».

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]