📑 😱 🍝 3-pass protocols ▪️ 🧖🏽 👶

This text will be one of the rewritten chapters for the training manual on information protection of the Department of Radio Engineering and Control Systems, as well as, from this training code, the Department of Information Protection of the MIPT (GU). The full tutorial is available on github (see also draft releases ). On Habrir I plan to upload new "big" pieces, firstly, to collect useful comments and observations, and secondly, to give the community more overview material on useful and interesting topics.

Previous topics:

If there is a communication channel between Alice and Bob that is not accessible for modification by an attacker (that is, when only the passive cryptanalyst model is applicable), then even without a preliminary exchange of secret keys or other information, you can use the ideas used previously in public key cryptography. After describing the RSA in 1978, in 1980 Adi Shamir proposed using cryptosystems based on commutative operations to transmit information without first exchanging secret keys. If we assume that the transmitted information is a secret session key generated by one of the parties, then in general we get the following three-pass protocol.

Preliminary:

Alice and Bob are connected by an insecure communication channel, open for listening (but not for modification) by an attacker.
Each side has a pair of public and private keys $K_A$ , $k_A$ , $K_B$ , $k_B$ respectively.
The parties have chosen and used the commutative encryption function:

$\ begin {array} {lll} D_ {A} \ left (E_ {A} \ left (X \ right) \ right) = X & \ forall X, \ left \ {K_A, k_a \ right \}; \\ E_ {A} \ left (E_ {B} \ left (X \ right) \ right) = E_B \ left (E_A \ left (X \ right) \ right) & \ forall ~ K_A, K_B, X. \ end {array}$
$\ begin {array} {lll} D_ {A} \ left (E_ {A} \ left (X \ right) \ right) = X & \ forall X, \ left \ {K_A, k_a \ right \}; \\ E_ {A} \ left (E_ {B} \ left (X \ right) \ right) = E_B \ left (E_A \ left (X \ right) \ right) & \ forall ~ K_A, K_B, X. \ end {array}$

The protocol consists of three passes with the transmission of messages (hence the name) and one final one, on which Bob receives the key.

Alice picks a new session key $K$

$Alice \ to \ left \ {E_A \ left (K \ right) \ right \} \ to Bob$
$Bob \ to \ left \ {E_B \ left (E_A \ left (K \ right) \ right) \ right \} \ to Alice$
Alice, using the commutativity of the encryption function,

$D_{A} l e f t (E_{B} l e f t (E_{A} l e f t (K r i g h t) r i g h t) r i g h t) = D_{A} l e f t (E_{A} l e f t (E_{B} l e f t (K r i g h t) r i g h t) r i g h t) = E_{B} l e f t (K r i g h t) .$
$D_A \ left (E_B \ left (E_A \ left (K \ right) \ right) \ right) = D_A \ left (E_A \ left (E_B \ left (K \ right) \ right) \ right) = E_B \ left (K \ right).$

$Alice \ to \ left \ {E_B \ left (K \ right) \ right \} \ to Bob$
Bob decrypts $D_B \ left (E_B \ left (K \ right) \ right) = K$

As a result, the parties receive a shared secret key.

K

$K$ .

A common drawback of all such protocols is the lack of authentication of the parties. Of course, in the case of a passive cryptanalyst, this is not required, but in real life you still need to consider all possible models (including an active cryptanalyst) and use protocols that involve mutual authentication of the parties. Also, unlike the Diffie – Hellman scheme, the new key is selected by the session initiator, which allows the initiator, not with good intentions, to force the second participant to use the outdated session key.

Speaking in terms of security properties , all representatives of this class of protocols declare only key authentication (G7). Unlike the Diffie – Hellman scheme, three-pass protocols do not require the selection of new “master” keys for each protocol session, which is why neither perfect direct secrecy (G9) nor the formation of new keys (G10) can be guaranteed.

Trivial option

Let us give an example of a protocol based on the XOR function (bitwise addition modulo 2). Although this function can be used as a foundation for building systems of perfect cryptographic strength, for a three-pass protocol this is a bad choice.

Before starting the protocol, both parties have their secret keys.

K_{A}

$K_A$ and

K_{B}

$K_B$ representing random binary sequences with a uniform distribution of characters. The encryption function is defined as

E_{i} (X) = X o p l u s K_{i}

$E_i (X) = X \ oplus K_i$ where

X

$X$ this message as well

K_{i}

$K_i$ - The secret key. It's obvious that:

f o r a l l i, j, X : E_{i} l e f t (E_{j} l e f t (X r i g h t) r i g h t) = X o p l u s K_{j} o p l u s K_{i} = X o p l u s K_{i} o p l u s K_{j} = E_{j} l e f t (E_{i} l e f t (X r i g h t) r i g h t)

$\ forall i, j, X: E_i \ left (E_j \ left (X \ right) \ right) = X \ oplus K_j \ oplus K_i = X \ oplus K_i \ oplus K_j = E_j \ left (E_i \ left (X \ right) \ right)$

Alice picks a new session key $K$

$Alice \ to \ left \ {E_A \ left (K \ right) = K \ oplus K_A \ right \} \ to Bob$
$Bob \ to \ left \ {E_B \ left (E_A \ left (K \ right) \ right) = K \ oplus K_A \ oplus K_B \ right \} \ to Alice$
Alice, using the commutativity of the encryption function,

$D_{A} l e f t (E_{B} l e f t (E_{A} l e f t (K r i g h t) r i g h t) r i g h t) = K o p l u s K_{A} o p l u s K_{B} o p l u s K_{A} = K o p l u s K_{B} = E_{B} l e f t (K r i g h t) .$
$D_A \ left (E_B \ left (E_A \ left (K \ right) \ right) \ right) = K \ oplus K_A \ oplus K_B \ oplus K_A = K \ oplus K_B = E_B \ left (K \ right).$

$Alice \ to \ left \ {E_B \ left (K \ right) = K \ oplus K_B \ right \} \ to Bob$
Bob decrypts $D_B \ left (E_B \ left (K \ right) \ right) = K \ oplus K_B \ oplus K_B = K$

At the end of the protocol session, Alice and Bob know the common session key

K

$K$ .

The proposed choice of the commutative encryption function of perfect secrecy is unsuccessful, as there are situations in which a cryptanalyst can determine the key

K

$K$ . Suppose a cryptanalyst intercepted all three messages:

K o p l u s K_{A}, K o p l u s K_{A} o p l u s K_{B}, K o p l u s K_{B} .

$K \ oplus K_A, ~~ K \ oplus K_A \ oplus K_B, ~~ K \ oplus K_B.$

Modulo 2 addition of all three messages gives the key

K

$K$ . Therefore, such an encryption system is not used.

Now we present the protocol for reliable transfer of the secret key, based on the exponential (commutative) encryption function. The stability of this protocol is associated with the difficulty of the task of computing the discrete logarithm: for known values

y, g, p

$y, g, p$ , to find

x

$x$ from the equation

y = g^{x} b m o d p

$y = g ^ x \ bmod p$ .

Shamir's Keyless Protocol

Parties tentatively agree on a large prime

p s i m 2^{1024}

$p \ sim 2 ^ {1024}$ . Each of the parties chooses a secret key.

a

$a$ and

b

$b$ . These keys are smaller and mutually simple.

p - 1

$p-1$ . Also, the parties prepared according to a special number

a^{'}

$a '$ and

b^{'}

$b '$ that allow them to decrypt a message encrypted with their key:

b e g i n a r r a y l a^{'} = a - 1 m o d (p - 1), a t i m e s a^{'} = 1 m o d (p - 1), f o r a l l X : (X^{a})^{a^{'}} = X . e n d a r r a y

$\ begin {array} {l} a '= a {-1} \ mod (p-1), \\ a \ times a' = 1 \ mod (p-1), \\ \ forall X: (X ^ a) ^ {a '} = X. \\ \ end {array}$

The last expression is true as a consequence of Fermat’s small theorem \ index {theorem! The farm is small}. Encryption and decryption operations are defined as follows:

\ begin {array} {lll} \ forall M <p: & C = E (M) = M ^ {a} & \ mod p, \\ & D (C) = C ^ {a '} & \ mod p, \\ & D_A (E_A (M)) = M ^ {aa '} = M & \ mod p. \\ \ end {array}

$\ begin {array} {lll} \ forall M <p: & C = E (M) = M ^ {a} & \ mod p, \\ & D (C) = C ^ {a '} & \ mod p, \\ & D_A (E_A (M)) = M ^ {aa '} = M & \ mod p. \\ \ end {array}$

Alice picks a new session key $K <p$

$Alice \ to \ left \ {E_A \ left (K \ right) = K ^ a \ bmod p \ right \} \ to Bob$
$Bob \ to \ left \ {E_B \ left (E_A \ left (K \ right) \ right) = K ^ {ab} \ bmod p \ right \} \ to Alice$
Alice, using the commutativity of the encryption function,

$D_{A} l e f t (E_{B} l e f t (E_{A} l e f t (K r i g h t) r i g h t) r i g h t) = K^{a b a^{'}} = K^{b} = E_{B} l e f t (K r i g h t) m o d p .$
$D_A \ left (E_B \ left (E_A \ left (K \ right) \ right) \ right) = K ^ {aba '} = K ^ b = E_B \ left (K \ right) \ mod p.$

$Alice \ to \ left \ {E_B \ left (K \ right) = K ^ b \ right \} \ to Bob$
Bob decrypts $D_B \ left (E_B \ left (K \ right) \ right) = K ^ {bb '} \ bmod p = K$

At the end of the protocol session, Alice and Bob know the common session key

K

$K$ .

Suppose a cryptanalyst intercepted three messages:

b e g i n a r r a y l y_{1} = K^{a} b m o d p, y_{2} = K^{a b} b m o d p, y_{3} = K^{b} b m o d p . e n d a r r a y

$\ begin {array} {l} y_1 = K ^ a \ bmod p, \\ y_2 = K ^ {ab} \ bmod p, \\ y_3 = K ^ b \ bmod p. \\ \ end {array}$

To find the key

K

$K$ , a cryptanalyst needs to solve a system of these three equations, which has a very large computational complexity, unacceptable from a practical point of view, if all three numbers

a, b, a b

$a, b, ab$ quite large. Let's pretend that

a

$a$ (or

b

$b$ ) few. Then, computing successive degrees

y_{3}

$y_3$ (or

y_{1}

$y_1$ ), can be found

a

$a$ (or

b

$b$ ), comparing the result with

y_{2}

$y_2$ . Knowing

a

$a$ , easy to find

a^{- 1} b m o d (p - 1)

$a ^ {- 1} \ bmod (p-1)$ and

K = (y_{1})^{a^{- 1}} b m o d p

$K = (y_1) ^ {a ^ {- 1}} \ bmod p$ .

Massey-Omura Cryptosystem

In 1982, James Massey and Jim Omura filed a patent (James Massey, Jim K. Omura), improving (in their opinion) the keyless protocol of Shamir. As an encryption operation instead of exponentiation in a multiplicative group

m a t h b b Z_{p}^{*}

$\ mathbb {Z} _p ^ *$ they suggested using exponentiation in the Galois field

m a t h b b G F 2^{n}

$\ mathbb {GF} {2 ^ n}$ . Secret key of each party (for Alice -

a

$a$ ) must satisfy the conditions:

b e g i n a r r a y l a i n m a t h b b G F 2^{n}, g f d l e f t (a, x^{n - 1} + x^{n - 2} + . . . + x + 1 r i g h t) = 1. e n d a r r a y

$\ begin {array} {l} a \ in \ mathbb {GF} {2 ^ n}, \\ gfd \ left (a, x ^ {n-1} + x ^ {n-2} + ... + x + 1 \ right) = 1. \\ \ end {array}$

Otherwise, the protocol looks similar.

Afterword

The author will be grateful for factual and other comments on the text.

3-pass protocols

Trivial option

Shamir's Keyless Protocol

Massey-Omura Cryptosystem

Afterword

More articles: