A Primer to Diffie-Hellman Key Exchange

28 Feb 2023

There are two famously hard problems in public key cryptography: one is integer factorization (for RSA algorithm) and the other is discrete logarithm computation in a finite group (for Diffie-Hellman key exchange).

Diffie-Hellman algorithm is widely used in secure network communications. According to RFC2631:

Diffie-Hellman key agreement requires that both the sender and recipient of a message have key pairs. By combining one’s private key and the other party’s public key, both parties can compute the same shared secret number. This number can then be converted into cryptographic keying material. That keying material is typically used as a key-encryption key (KEK) to encrypt (wrap) a content-encryption key (CEK) which is in turn used to encrypt the message data.

Table of Contents

• Algebraic Structures Refresher
• The Discrete Logarithm Problem (DLP)
  • An Example: Okamoto–Uchiyama Cryptosystem
  • The Elliptic Curve Discrete Logarithm Problem
• Diffie-Hellman Algorithm
• Small Subgroup Attacks
• Footnotes

Algebraic Structures Refresher

Definition 1. A group is a 2-tuple \((G, \times)\), where \(G\) is a set and \(\times\) is a binary operation that defines an associative multiplication map \(G \times G \rightarrow G\)¹ such that there is an identity element \(e \in G\) (i.e., \(e \times g = g \times e = g\) for all \(g \in G\)) and, for every element \(g \in G\), in inverse element \(g^{-1}\) satisfying \(g \times g^{-1} = e = g^{-1} \times g\). A group is Abelian if the operation \(\times\) is commutative, that is, if \(g \times h = h \times g\) for all \(g, h \in G\). A group \(G\) is called finite if \(G\) is a finite set.

For example, the group \(\mathbb{Z}_{n}\) consists of the elements \(\{ 0, 1, 2, \dots , n - 1 \}\) with addition \(\bmod{n}\) as the operation. If \(G\) is a group, \(g^{n}\) is defined for every \(g \in G\) and every integer \(n\).

Definition 2. Let \(n > 1\) be a fixed positive integer. For each integer \(x\), the congruence classes modulo \(n\), denoted by \([x]_{n}\), is defined as:

There are altogether \(n\) such congruence classes. Together these \(n\) congruence classes constitute \(\mathbb{Z} / n \mathbb{Z}\):

This is the quotient set of \(\mathbb{Z}\) by the congruence relation modulo \(n\).

Definition 3. Let \(G\) be a group and let \(g \in G\). The order of \(G\) is its cardinality \(\lvert G \rvert\). The order of \(g\) in \(G\) is the smallest positive integer \(n\) such that \(g^{n} = e\) provided that such an integer exists. If no such positive integer \(n\) exists, then the order of \(g\) is infinite.

Definition 4. Let \(G\) be a group and let \(S \subseteq G\). The subgroup of \(G\) generated by \(S\), denoted by \(\langle S \rangle\), is the smallest subgroup of \(G\) which contains \(S\), that is, the intersection of all subgroups of \(G\) which contain \(S\). The elements of \(S\) are called generators of the group \(\langle S \rangle\). We say that \(G\) is cyclic when \(G = \langle g \rangle\) for some \(g \in G\).

Theorem 4.1 Let \(G\) be a group and let \(g \in G\). Then we have:

1. \(\langle g \rangle = \{ g^{k} \mid k \in \mathbb{Z} \}\);
2. If \(\lvert g \rvert = \infty\), then the elements \(g^{k}, k \in \mathbb{Z}\) are all distinct, \(\lvert \langle g \rangle \rvert = \infty\);
3. If \(\lvert g \rvert = n\), then for \(k, l \in \mathbb{Z}\), \(g^{k} = g^{l}\) is equivalent to \(k = l \bmod{n}\), and

with \(\lvert \langle g \rangle \rvert = n\). In particular, for \(k \in \mathbb{Z}\), \(g^{k} = e\) is equivalent to \(n \mid k\).

Theorem 4.2 If \(H\) is a subgroup of the finite group \(G\), then the order of \(H\) divides the order of \(G\). This is the so-called Lagrange theorem.

If \(g\) is a group element of order \(r\), then one needs at least \(\log_{2}(r)\) bits to represent an arbitrary element of \(\langle g \rangle\)².

Definition 5. A ring is a 3-tuple \((R, +, \times)\), where \(R\) is a set and \(+, \times\) are binary operations satisfying the following properties:

• \((R, +)\) is an Abelian group with identity element \(0\);
• (associativity) For all \(a, b, c \in R\), \((a \times b) \times c = a \times (b \times c)\);
• (distributivity) For all \(a, b, c \in R\), \(a \times (b + c) = a \times b + a \times c\) and \((b + c) \times a = b \times a + c \times a\).

Definition 6. A field is a ring such that \((R \setminus \{0\}, \times)\) is an Abelian group with identity element \(1\), and \(1 \not = 0\).

Definition 7. The multiplicaitve group or group of units of a ring \(R\), denoted by \(R^{\times}\), is the set of elements of \(R\) with multiplicative inverses, together with multiplication.

A field is therefore a ring for which the multiplicative group is as large as possible. \(\mathbb{Z} / n \mathbb{Z}\) is a commutative ring with units, \([1]_{n}\) being the multiplicative identity. The multiplicative group of the ring \(\mathbb{Z} / n \mathbb{Z}\) (or the multiplicative group of integers modulo \(n\)) is often written succinctly as \((\mathbb{Z} / n \mathbb{Z})^{\times}\), which contains precisely the numbers between \(1\) and \(n\) that are coprime to \(n\). The notation used here follows that of the Wikipedia article. The Okamoto–Uchiyama cryptosystem as mentioned in the next section works in \((\mathbb{Z} / n \mathbb{Z})^{\times}\), where \(n\) is of the form \(p \cdot p \cdot q\) and \(p, q\) are both large primes.

The Discrete Logarithm Problem (DLP)

Definition 8. In its most standard form, the discrete logarithm problem in a finite group \(G\) can be stated as follows: Given \(g \in G\) and \(h \in \langle g \rangle\), find the least positive integer \(x\) such that \(g^{x} = h\). In additive notation, this means \(xg = h\)³. In either case, we call \(x\) the discrete logarithm of \(h\) with respect to the base \(g\) and denote it \(\log_{g}h\)⁴.

Definition 9. The generalized discrete logarithm problem is the following: given a finite cyclic group \(G\) of order \(n\), a generator \(g\) of \(G\), and an element \(h \in G\), find the integer \(x\), \(0 \leq x \leq n - 1\), such that \(g^{x} = h\).

Let \(g_{1}\) and \(g_{2}\) be two generators of a cyclic group \(G\) of order \(n\), and let \(h \in G\). Let \(x = \log_{g_{1}}h\), \(y = \log_{g_{2}}h\), and \(z = \log_{g_{1}}g_{2}\). Then \(g_{1}^{x} = h = g_{2}^{y} = \left( g_{1}^{z} \right)^{y}\). Consequently, \(x = zy \bmod{n}\), and

This means that any algorithm which computes logarithms to the base \(g_{1}\) can be used to compute logarithms to any other base \(g_{2}\) that is also a generator of \(G\).

A solution to the DLP exists if and only if \(h \in \langle g \rangle\), i.e., \(h\) lies in the subgroup generated by \(g\). While the DLP is generally considered a “hard problem,” there are entire families of cyclic groups for which the DLP is easy. Take, for example, the additive group \(G = \mathbb{Z} / n \mathbb{Z}\). If we use the generator \(g = 1\), the problem of computing discrete logarithms is absolutely trivial. In fact, if \(g\) is a generator, then it is coprime to \(n\). Finding the multiplicative inverse of \(g \bmod{n}\), via Euclid’s algorithm, suffices for finding the discrete logarithm of \(1\), and so we quickly get everything else.

The DLP is known to be difficult in two types of groups:

1. The multiplicative group of integers modulo prime \(p\), \(\mathbb{Z}_{p}^{\times}\), and
2. The additive group of elliptic curves defined over finite fields.

If the DLP is difficult in a given group, we can use it to implement several public key cryptographic algorithms, for example, Diffie-Hellman key exchange protocol, ElGamal public key encryption protocol, and the Digital Signature Algorithm. For efficient public key cryptography based on discrete logarithms, one would like to:

• have groups for which computing \(g^{n}\) is as fast as possible;
• have groups for which the DLP is (at least conjecturally) as hard as possible;
• the representation of group elements is as small as possible.

The known algorithms for the DLP can be categorized as follows:

• algorithms which work in arbitrary groups, e.g., exhaustive search, the baby-step giant-step algorithm, Pollard’s rho algorithm;
• algorithms which work in arbitrary groups but are especially efficient if the order of the group has only small prime factors, e.g., Pohlig-Hellman algorithm; and
• the index-calculus algorithms, which are efficient only in certain groups⁵.

An Example: Okamoto–Uchiyama Cryptosystem

The “discrete log” challenge from PoseidonCTF 2020 is constructed based on a public key cryptosystem called the Okamoto–Uchiyama cryptosystem. Wikipedia provides a clear explanation of this cryptosystem.

Description: I heard some cryptosystem uses discrete logarithm. It is hard problem, isn’t it? I encrypted the flag with \(4095\)-bit modulus . . .

The problem.py program:

#!/usr/bin/env python3

from Crypto.Util.number import isPrime, getPrime, getRandomRange, bytes_to_long
from flag import flag

def keygen():
    p = getPrime(1024)
    q = p**2 + (1<<256)
    while not(isPrime(q)):
        q += 2
    n = p**2 * q
    while True:
        g = getRandomRange(2, n-1)
        if pow(g, p-1, p**2) != 1:
            break
    return (g, n), p

def encrypt(pubkey, msg):
    g, n = pubkey
    msgint = bytes_to_long(msg)
    encint = pow(g, msgint, n)
    return encint

wfile = open('output.txt', 'w')

pubkey, privkey = keygen()

print(privkey)
wfile.write('g = ' + str(pubkey[0]) + '\n')
wfile.write('n = ' + str(pubkey[1]) + '\n')

encint = encrypt(pubkey, flag)
wfile.write('enc = ' + str(encint) + '\n')

wfile.close()

The output.txt file:

g = 172749132303451034825184289722866887646478207718904031630914096520683022158034517117605936723970812800902379716660696042889559048647206589145869496198395421965440272135852383965230458163451729744948637995163776071512309614027603968693250321092562108610034043037860044795655266224453184735452048413623769098671844195106558284409006269382544367448145088128499405797694142037310933061698125568790497068516077791616445318819525778890129259953967830407023305805724947609041398183006524760589480514375528363943261764527906775893795625189651746165941438248136930298545695110631212696683271254403308539994170329875688236599305478130030194371971383054083049610267982461416568688720562725217837462387935392946474596966349477680685726377666929540130924122398746591270899232208239961618302848348129375606841006687727574503519146164506867574157671109933022528435615415554171024171300585408907077259610240139419075684581512703943171162496513070572546968852202777002845137863414028314025114932581655385254082418111977242759980115915504202336380850329162861826132885827910210346708045087589916666711356848614195462267049823085141386868421005551877773672329046391854000523197388175515628464457551891476514779819019668102328395639607489673081022505099
n = 204964538005458094391574690738766104196067587947267165575341074475716043971842449550067337731195102944823593489101699510575531541895593939634478254160200896755891641047742120885540191258962212405226135805491196590351987106011483652123110409148411537235255207358696047015199616340882291357173918540392964501976492251077110794432722042202109934588262870543755493029748475008610896164870659893013085704495216717998116109896882952474884270785733861739050889113464275228554841649603978281963688294995328883256317404081735364738985601286409677647577052211093127231530844271726386293348738817021732679704754961436390654856963930636538653822714234978179695778198536592408645222590877027896792957778186555118729335564281356291031440583078132397563914801937048297147819254611598144027963328749607393168101280779708669908245620694587176737529113823312930871616550632035759346759393976128246210013752530912953330415598837661326422094379798718827988692760848583517436061574821754507293943235476923624688378441177770313101393581916112910947153305055575974237171438666919114843946573283829704010962833299593770650238349021406868347635157566404829030358844616367849771415905381318344903398551946493709551783771889575282972265629264217620138873678733
enc = 58749077215207190492371298843854826665007067693641554277597021927783439106518176607848876784025881251057880587477892585242567469682290542409002363284991521084199535617805983767364935247518813883871587009725229910084882524866335007624383374126379502610933045897762967063766174922757656816300993939273687091280630401460905159739072179134897626330594985795970230333335492872721173603390854317323095769925904629970032658376378937924244589208035572848434030889091930182042226202356340798415809817722086119981262671540923062830870681500341640178082497128371291359953884993700348396920219975667972939044100089402796215197615549948516999318565775626034391795498234335228509335613253342179818268681240653806015040771731154600343889814141382273506238199460016081871283682838719833841393528105371834961952754168257271394981634141286257602629174903644009990944563870674888760807045240859970974837258567236802649772719645362361127488126570702845624169598462415354350277654287009645871674305081755840523910495569765451437265785385267255452210836618705384598344351666486694835670072372776263570462639412759703397195350879217144135006968472391258993407007505079063659488976186871280542665310586453539153772026697145449262179967269376262891840972187

Solution: The solution is given by Saurav Kumar Singh, which closely follows the decryption instructions from Wikipedia.

from Crypto.Util.number import isPrime, getPrime, getRandomRange, bytes_to_long, long_to_bytes
import os, sys, re, gmpy2

output_path = "output.txt"
if not os.path.exists(output_path):
    sys.exit("Error: File '%s' not found" % output_path)
lines = []
with open(output_path, 'r') as output:
    for i, line in enumerate(output):
        lines.append(re.findall(r'\b\d+\b', line.strip())[0])
        # print(lines[i])
        if i > 3:
            break
g = int(lines[0])
n = int(lines[1])
enc = int(lines[2])

# The integer 4th root of n:
root = gmpy2.iroot(n, 4)[0]
p = root
assert isPrime(p)
q = root * root + (1 << 256)
while not(isPrime(q)):
	q += 2
assert p * p * q == n

h = pow(g, n, n)
c = (enc * h) % n

b = pow(g, p - 1, p * p) - 1
assert b % p == 0
b = b // p

a = pow(c, p - 1, p * p) - 1
assert a % p == 0
a = a // p

# b_ * b == 1 modulo p
b_ = gmpy2.invert(b, p)
m = (a * b_) % p
print(f"Flag: {long_to_bytes(m).decode()}")

The Elliptic Curve Discrete Logarithm Problem

Theoretical details of elliptic curves can be found in Washington’s book⁶.

Definition 10. An elliptic curve \(E\) is the graph of an equation of the form

where \(A\) and \(B\) are constants. This is also referred to as the Weierstrass equation for an elliptic curve. If \(\mathbb{K}\) is a field with \(A, B \in \mathbb{K}\), then we way that \(E\) is defined over \(\mathbb{K}\). We assume that

to ensure distinct roots. Then, let \(P_{1} = (x_{1}, y_{1})\) and \(P_{2} = (x_{2}, y_{2})\) be points on \(E\) with \(P_{1}, P_{2} \not = \infty\)⁷. Define \(P_{1} + P_{2} = P_{3} = (x_{3}, y_{3})\) as follows:

1. If \(x_{1} \not = x_{2}\), then \(x_{3} = m^{2} - x_{1} - x_{2}\), \(y_{3} = m(x_{1} - x_{3}) - y_{1}\), where \(m = \frac{y_{2} - y_{1}}{x_{2} - x_{1}}\).
2. If \(x_{1} = x_{2}\) but \(y_{1} \not = y_{2}\), then \(P_{3} = \infty\).
3. If \(P_{1} = P_{2}\) and \(y_{1} \not = 0\), then \(x_{3} = m^{2} - 2x_{1}\), \(y_{3} = m(x_{1} - x_{3}) - y_{1}\), where \(m = \frac{3x_{1}^{2} + A}{2y_{1}}\).
4. If \(P_{1} = P_{2}\) and \(y_{1} = 0\), then \(P_{3} = \infty\).

The addition of points on an elliptic curve \(E\) satisfies the following properties:

1. (commutativity) \(P_{1} + P_{2} = P_{2} + P_{1}\) for all \(P_{1}, P_{2}\) on \(E\).
2. (existence of identity) \(P + \infty = P\) for all points \(P\) on \(E\).
3. (existence of inverses) Given \(P\) on \(E\), there exists \(P^{\prime}\) on \(E\) with \(P + P^{\prime} = \infty\). \(P^{\prime}\) will usually be denoted \(-P\).
4. (associativity) \((P_{1} + P_{2}) + P_{3} = P_{1} + (P_{2} + P_{3})\) for all \(P_{1}, P_{2}, P_{3}\) on \(E\).

In other words, the points on \(E\) form an additive Abelian group with \(\infty\) as the identity element.

Diffie-Hellman Algorithm

Before the invention of the Diffie-Hellman algorithm, the problem of efficiently computing discrete logarithms actually attracted little attention. The goal of the Diffie-Hellman algorithm is usually to create an ephemeral key. An ephemeral key is used for some sequence of encryptions and decryptions and is discarded once it is no longer needed. Thus the Diffie-Hellman algorithm is effectively a way for two parties to agree on a random value in the face of an eavesdropper.

For two users, say Alice and Bob, to derive a common key in a finite cyclic group \(G\), \(\lvert G \rvert = n\), with generator \(g\), \(G = \langle g \rangle\), they, respectively, choose, at random, integers \(a, b \in_{\mathbb{R}}[1, n]\) and exchange \(g^{a}, g^{b}\). Each is able to compute \(g^{ab}\) from which a common key may be derived. It is assumed here that an adversary, knowing \(G\), \(g^{a}\), and \(g^{b}\), is unable to compute \(g^{ab}\)⁸.

Definition 11. The computation of \(g^{ab}\) from knowledge of \(g^{a}\) and \(g^{b}\) is referred to as the Diffie-Hellman problem (DHP). If one is able to find discrete logarithm in \(G\) then one can break the DH protocol and the DLP is at least as hard as the DHP⁹.

Protocol 1 (Ephemeral Diffie-Hellman) Assume that \(A\) and \(B\) are honest entities; \(p\) is a \(1024\)-bit prime¹⁰ and \(q\) is a \(160\)-bit prime divisor of \(p - 1\); \(g\) is an element of order \(q\) in \(\mathbb{Z}_{p}^{\times}\); the domain parameters \((p, q, g)\) are common to all entities. (Obviously, the choices for \(p\) and \(g\) must yield a large value for the order \(q\), the size of the generated cyclic subgroup of \(\mathbb{Z}_{p}^{\times}\).)

1. \(A\) selects \(x \in_{\mathbb{R}} [1, q - 1]\) and sends \(R_{A} = g^{x} \bmod{p}\) to \(B\).
2. \(B\) selects \(x \in_{\mathbb{R}} [1, q - 1]\) and sends \(R_{B} = g^{y} \bmod{p}\) to \(A\).
3. \(A\) computes \(K = (R_{B})^{x} = g^{xy}\).
4. \(B\) computes \(K = (R_{A})^{y} = g^{xy}\).

While the ephemeral Diffie–Hellman protocol provides implicit key authentication¹¹ in the presence of passive adversaries, it does not on its own provide any useful services in the presence of active adversaries since neither entity is provided with any assurances regarding the identity of the entity it is communicating with.

Protocol 2 (Static Diffie-Hellman) Let \(a\) and \(b\) denote static private keys of \(A\) and \(B\) such that \(a, b \in_{\mathbb{R}} [1, q - 1]\). Let \(Y_{A}\) and \(Y_{B}\) denote static public keys of \(A\) and \(B\) such that \(Y_{A} = g^{a} \bmod{p}\), \(Y_{B} = g^{b} \bmod{p}\). Let \(Cert_{A}\) denote \(A\)’s public-key certificate, containing a string of information that uniquely identifies \(A\) (such as \(A\)’s name and address), her static public key \(Y_{A}\), and a certifying authority CA’s signature over this information. Any other entity \(B\) can use his authentic copy of the CA’s public key to verify \(A\)’s certificate, thereby obtaining an authentic copy of \(A\)’s static public key.

Assume that the CA has verified that \(A\) possess the private key \(a\) corresponding to her static public key \(Y_{A}\). This is done in order to prevent potential unknown key-share attacks¹² whereby an adversary \(E\) registers \(A\)’s public key \(Y_{A}\) as its own and subsequently deceives \(B\) into believing that \(A\)’s messages originated from \(E\).

Also assume that the CA has verified the validity of \(A\)’s static public key \(Y_{A}\), i.e., the CA has verified that \(1 < Y_{A} < p\) and that \((Y_{A})^{q} \equiv 1 \bmod{p}\).

1. \(A\) sends \(Cert_{A}\) to \(B\).
2. \(B\) sends \(Cert_{B}\) to \(A\).
3. \(A\) computes \(K = (Y_{B})^{a} = g^{ab}\).
4. \(B\) computes \(K = (Y_{A})^{b} = g^{ab}\).

Since each entity is assured that it possesses an authentic copy of the other entity’s public key, the static Diffie-Hellman protocol offers implicit key authentication. A major drawback, however, is that \(A\) and \(B\) compute the same shared secret \(K = g^{ab}\) for each run of the protocol¹³.

The OAKLEY protocol, which is based on the Diffie-Hellman algorithm, allows two users to establish a shared key with an assigned identifier and associated authenticated identities. The shared policy and key(s) used by the negotiating peers in the protocol to protect their communication is called a security association (SA). Implementation details of OAKLEY can be found in RFC2412. In the IPSec protocol suite, OAKLEY is used alongside ISAKMP (Internet Security Association and Key Management Protocol), and is now commonly known as IKE (Internet Key Exchange). The IKE protocol can provide perfect forward secrecy (PFS) of both keys and identities:

Definition 12. The notion of perfect forward secrecy (PFS) is that compromise of a single key will permit access to only data protected by a single key.

When PFS is turned on, for every negotiation of a new IKE phase 2 SA, the two gateways must generate a new set of phase 1 keys¹⁴. This is an extra layer of protection that PFS adds, which ensures if the phase 2 SA’s have expired, the keys used for new phase 2 SA’s have not been generated from the current phase 1 keying material.

Small Subgroup Attacks

RFC2785

Chae Hoon Lim and Pil Joong Lee, “A key recovery attack on discrete log-based schemes using a prime order subgroup,” CRYPTO ‘97, LNCS 1294, pp. 249-263, 1997.

Dan Brown and Alfred Menezes, “A Small Subgroup Attack on Arazi’s Key Agreement Protocol,” Bulletin of the ICA, No. 37, pp. 45-50, 2003.

Feng Hao, “On Small Subgroup Non-confinement Attack,” IEEE International Conference on Computer and Information Technology, pp. 1022-1025, 2010.

Footnotes

Last updated: 2023-03-29