Asymmetric algorithms for secret key distribution

Key distribution problem

Given $n=1000$ people, we would need 499,500 symmetric keys opposed to 2000 asymmetric keys in order to communicate between each person. This is the key distribution problem.

Link to original

We can use public-key encryption algorithms to support faster symmetric cryptography.

Distribution with RSA

Key distribution with RSA

Alice encrypts $M$ by using Bob’s public key $(e,n)$.

• Alice randomly chooses a secret key $K$ to be shared with Bob.
• Alice sends $C=(K^e\text{ mod }n,E_K(M))$ to Bob.

Bob decrypts $C$ with his private key $(d,n)$.

• Bob splits $C$ into $(C_1,C_2)$.
• Bob computes $K=C_1^d\text{ mod }n$ and $M=D_K(C_2)$.

Link to original

SSL Protocol

Alice chooses a secret, encrypts it with Bob’s public key and rest of the session is protected based on that secret.

If the private key $(d,n)$ is compromised, then $K$ can be recovered from previously observed traffic.

Diffie-Hellman key exchange

Diffie-Hellman key exchange

Diffie-Hellman is a simple public-key algorithm that enables two users to establish a secret key using a public-key scheme based on discrete logarithms.

1. Principals share a prime number $q$ and an integer $\alpha$ that is a primitive root of $q$. Both $q$ and $\alpha$ may be public, or $A$ could send them in the first message.
2. $A$ and $B$ generate random numbers $X_A$ and $X_B$ both less than $q$. (these are private keys)
3. $A$ computes $Y_A={\alpha }^{X_A}\text{ mod }q$, $B$ computes $Y_B={\alpha }^{X_B}\text{ mod }q$. (these are public keys, also known as “Diffie-Hellman half keys”)
4. $A$ and $B$ exchange $Y_A$ and $Y_B$.
5. $A$ computes $K_A=Y_B^{X_A}\text{ mod }q$, $B$ computes $K_B=Y_A^{X_B}\text{ mod }q$. (the keys are equal, i.e. $K_A=K_B$)

Link to original

Proof

$$\begin{array}{rl}{K}_A& =Y_B^{X_A}\text{ mod }q\\ & =({\alpha }^{X_B}\text{ mod }q{)}^{X_A}\text{ mod }q\\ & =({\alpha }^{X_B}{)}^{X_A}\text{ mod }q\\ & ={\alpha }^{X_A{X}_B}\text{ mod }q\\ & =({\alpha }^{X_A}{)}^{X_B}\text{ mod }q\\ & =({\alpha }^{X_A}\text{ mod }{)}^{X_B}\text{ mod }q\\ & =Y_A^{X_B}\text{ mod }q\\ & =K_B\end{array}$$

Protocol is only secure if the authenticity of the two participants can be established.

The shared secret key is never transmitted (not even in encrypted form).

• $Y_A={\alpha }^{X_A}\text{ mod }q$ and $Y_B={\alpha }^{X_B}\text{ mod }q$ are the public keys.
• $X_A$ and $X_B$ are the private keys which are never shared, so the attacker $C$ can only use $q$, $\alpha$, $Y_A$, and $Y_B$.
• $C$ must take a discrete logarithm to determine the key. To compute the private key of user $B$, $C$ must compute $X_B={\text{dlog}}_{\alpha ,q}(Y_B)$.

Keys are unauthenticated and D-H is vulnerable to a MITM attack.

1. Attacker $C$ prepares by generating two random private keys and computing the corresponding public keys.
2. $C$ can intercept any communication, i.e. swap the public keys shared by $A$ and $C$ for his own.
3. As such, $C$ negotiates D-H key exchange with both participants individually and then acts as a tunnel between them. Encrypted messages are sent to $C$ which are decrypted then re-encrypted for the other peer.

$C$ may also modify any message they want. We can overcome this vulnerability with the use of digital signatures and public-key certificates to achieve mutual authentication between $A$ and $B$.

Primitive Roots

Primitive root

A primitive root $s$ of a prime number $p$ is a number whose powers generate $1,\dots ,p-1$.

So $s^1\text{ mod }p,s^2\text{ mod }p,\dots ,s^{p-1}\text{ mod }p$ are distinct, i.e. a permutation of $1$ through $p-1$.

Hence $\forall b\in \mathbb{Z}.\exists i\in \{1,\dots ,p-1\}.b=s^i\text{ mod }p$.

Link to original

Discrete logarithm

For any integer $b$ and a primitive root $s$ of prime number $p$, we can find a unique exponent $i$ such that $b=s^i\text{ mod }p$ where $1\le i\le (p-1)$.

$i$ is called the discrete logarithm of $b$ for base $s$, $\text{mod }p$.

Computing discrete logarithms appears infeasible today.

Link to original

The security of D-H key exchange lies in the fact it is relatively easy to calculate exponentials modulo a prime but very difficult to calculate discrete logarithms.

Example of calculating secret key

Attacking the key

Group Diffie-Hellman (for $3+$ principals)

Given a D-H group $(\alpha ,q)$, three principals can together generate a secret key $K={\alpha }^{X_A{X}_B{X}_C}\text{ mod }q$ by: This can be extended to $n$ principals by adding more rounds of computations to compute the key $K={\alpha }^{X_1,X_2,\dots X_n}\text{ mod }q$.

El Gamal variant of Diffie-Hellman key exchange

El Gamal variant of Diffie-Hellman key exchange

The El Gamal variant of Diffie-Hellman has the same setup with a public prime $q$ and generator $\alpha$.

Let $E$ be any symmetric encryption function. The schema is as follows:

1. $A$ chooses $X_A$ and computes $Y_A={\alpha }^{X_A}\text{ mod }q$. $A\to B:Y_A$
2. $B$ chooses integer $X_B$, computes $Y_B={\alpha }^{X_B}\text{ mod }q$ , and computes key $K=Y_A^{X_B}\text{ mod }q$. $B\to A:(E(M,K),Y_B)$
3. $A$ computes $K=Y_B^{X_A}\text{ mod }q$ $\text{and uses }K\text{ to decrypt }E(M,K)$.

Link to original

Masey-Omura scheme

Masey-Omura scheme

The Masey-Omura scheme is a scheme that enables encryption without shared keys (based on the discrete logarithm problem).

Principals share some (public) prime $p$. Principals $u\in \{A,B\}$ chooses (private) $e_u,d_i\in \mathbb{Z}$ such that $e_u{d}_u\text{ mod }(p-1)=1$ So $(p-1)|(e_u{d}_u-1)$. So there is a $k$ where $e_u{d}_u=k(p-1)+1$. Hence, by Euler’s theorem, for all $m\in \{1,\dots ,p-1\}$:

$$\begin{array}{rl}{m}^{e_u{d}_u}\text{ mod }p& =m^{k(p-1)}m\text{ mod }p\\ & =m\text{ mod }p\\ & =m\end{array}$$

Steps go as follows:

1. $A\to B:m^{e_A}\text{ mod }p$
2. $B\to A:m^{e_A{e}_B}\text{ mod }p$
3. $A\to B:m^{e_A{e}_B{d}_A}\text{ mod }p(=m^{e_B})$
4. $m^{e_A{e}_B{d}_A{d}_B}\text{ mod }p(=m)$

Link to original

Message integrity and cryptographic hashes

Message integrity

Message / data integrity is the property that data has not been altered in an unauthorized manner since the time it was created, transmitted, or stored by an authorized source.

Link to original

In operating systems, access control is used to ensure data integrity. Meanwhile open networks use cryptographic means.

Hash Function

A hash function $h(x)$ has the properties:

• Compression: $h$ maps an input of $x$ of arbitrary bit length to an output $h(x)$ of fixed bit length $n$ which may be smaller
• Polynomial time computable

Link to original

Cryptographic hash function

A cryptographic hash function has the additional properties:

• It is one-way (preimage resistant) Given $y$, it is hard to compute an $x$ where $h(x)=y$.

And is usually either:

• 2nd-preimage resistant

  2nd-preimage resistant: it is computationally infeasible to find a second input that has the same output as any specified input, i.e. given $x$ to find an $x^{\prime }\ne x$ such that $h(x)=h(x^{\prime })$

  Link to original

• Collision resistant

  Collision resistant: it is difficult to find two distinct inputs $x,x^{\prime }$ where $h(x)=h(x^{\prime })$

  Link to original

Link to original

Message digest

The resulting hash value can also be called the message digest or modification detection code

Link to original

Collision resistance and birthday paradox

Birthday Paradox We look at how many people must be in a room such that the probability $p$ that one has your birthday is $>.5$: the probability is $n/365$ so for $n=183,p>0.5$. We also consider how many people must be in a room such that the probability $p$ that any two share the same birthday is $>.5$: which is $23$.

Generalisation:

• Let $h$ have $2^m$ possible outputs
• $h$ must be applied to $2^{\frac{m}{2}}$ inputs so that the probability of a collision is greater than $0.5$

Birthday Attack One may assume a $64$ bit hash code is secure. Preimage resistance means, on average $2^{63}$ messages must be tried.

Birthday attack for finding collisions:

• Suppose $A$ is willing to sign a contract with $B$. Then $B$ prepares version $x$, which is good for $A$, and version $y$, which bankrupts them.
  • $B$ generates ‘good’ messages $x_1,\dots$
  • And similarly generates ‘bad’ $y_1,\dots$
  • Stops when $h(x_i)=h(y_j)$
• $A$ signs $h(x_i)$ and creates a signature which $B$ later uses for $y_j$.

On average, work requires is order of $2^{32}$. So double hash size if collision avoidance is important.

Constructing cryptographic hash function

• Simplest algorithms use block chaining techniques:
  • Divide message $M$ into fixed size blocks $b_1,\dots b_n$
  • Use symmetric encryption algorithm, e.g. DES (similar to Cipher Block Chaining w/ no secret key)
• Modern algorithms are more complex
  • MD5 (Message Digest by Rivest): 128-bit hashes, known weakness
  • SHA (Secure Hash Algorithm; U.S. std): 160-bit hashes SHA-1 widely used but deprecated. SHA-3 still apparently secure.

Message authentication

Message authentication

Message authentication (also called data-origin authentication) is a strategy to protect the integrity of a message, ensuring that each message is received and deemed acceptable.

Link to original

Message Authentication Codes (MACs)

MAC algorithm

A MAC (Message Authentication Code) algorithm is a family of hash functions $h_k$ parameterised by a secret key $K$. $h_k$ must be computation-resistant: given zero or more MAC pairs $(x_i,h_K(x_i))$, it is infeasible to compute $(x,h_K(x))$ for any new input $x\ne x_i$.

Link to original

Constructing MACs

Does not provide non-repudiation as a symmetric cipher is used.

Vulnerable to replay attacks.

Digital Signatures

Digital Signature

Digital Signatures are fundamental in authentication and non-repudiation.

• $\mathcal{M}$ is a set of messages that can be signed
• $\mathcal{S}$ is a set of elements called signatures, e.g. $n$-bit strings
• $S_A:\mathcal{M}\to \mathcal{S}$, is a signing transformation for entity $A$, and kept secret by $A$.
• $V_A:\mathcal{M}\times \mathcal{S}\to \{\text{true},\text{false}\}$ is a verification transformation for $A$‘s signature and is publicly known.

$S_A$ and $V_A$ provide a digital signature scheme for $A$.

Link to original

Example signature schema

Signing procedure (digital signatures)

Signing procedure: $A$ creates a signature for $m\in \mathcal{M}$ by computing $s=S_A(m)$ and transmits pair $(m,s)$.

Link to original

Verification procedure (digital signatures)

Verification procedure: $B$ verifies $A$‘s signature of $(m,s)$ by computing $u=V_A(m,s)$, and only accepting the signature if $u=\text{true}$.

Link to original

Secrecy (digital signatures)

Secrecy (digital signatures) requires it is hard for any entity other than $A$ to find, for any $m\in \mathcal{M}$, an $s\in \mathcal{S}$, where $V_A(m,s)=\text{true}$.

Link to original

Implementing digital signatures

Use of RSA for digital signatures

$D_d(E_e(m))=E_e(D_d(m))=m$

Forgery can be prevented by signing messages with a fixed structure:

• Message names its sender
• or (more typically) cryptographic hash signed, sent with the message.

Public-Key Infrastructure (PKI)

Not examined, slides lec 2. 26 - 72.