Apr 18, 16

Crypto Classics: Wiener's RSA Attack

When simple math pwns fancy crypto

While reading on RSA I stumbled upon Dan Boneh’s Twenty Years of Attacks on the RSA Cryptosystem 1999 paper. In there, I found a trove of applied attacks against RSA; one of which, Wiener’s, employs continued fractions approximation to break RSA efficiently (under certain conditions).

The attack was interesting enough to make me want to learn about it and spread the word.

So, today we’re going to use simple math and Python to distill Wiener’s Attack :).

Preliminaries

Listed below are some basic math and crypto concepts. Academic fellows might want Wiener’s original paper [¹].

Continued Fractions

A simple continued fraction is an expression of the following form $x=a_0$ :

x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \ldots}}}

Where $a_i$ s are called quotients.

A continued fraction is abbreviated by its continued fraction expansion:

x = [a_0, a_1, a_2, a_3, \ldots, a_n]

Rational numbers (Irrational numbers) have finite (infinite) continued fraction expansions.

Simple examples:

\frac{73}{95} = 0 + \frac{1}{1 + \frac{1}{3 + \frac{1}{3 + \frac{1}{7}}}} = [0, 1, 3, 3, 7]

\pi = [3, 7, 15, 1, 292, 1, 1, 1, 2, \ldots]

The following algorithm calculates the continued fraction expansion of a rational number with nominator $n$ and denominator $d$ .

# Continued Fraction Expansion of Rationals

def cf_expansion(n, d):
    e = []

    q = n // d
    r = n % d
    e.append(q)

    while r != 0:
        n, d = d, r
        q = n // d
        r = n % d
        e.append(q)

    return e

Rational Approximations

We know that $\pi$ is an irrational number. The cool thing is that we can form succinct rational approximations of $\pi$ using its continued fraction expansion.

c_0 = \frac{3}{1} = 3.0

c_1 = 3 + \frac{1}{7} = \frac{22}{7} = 3.142857

c_2 = 3 + \frac{1}{7 + \frac{1}{15}} = \frac{333}{106} = 3.141509

c_3 = 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{1}}} = \frac{355}{113} = 3.141593

\ldots

These rational numbers ( $c_i$ ) are called the convergents of a continued fraction. As $i$ grows $c_i$ approaches $\pi$ (3.141592…).

The following algorithm (taken from [¹]) calculates the convergents of a continued fraction expansion $e = [a_0, a_1,\ldots , a_n]$ :

def convergents(e):
    n = [] # Nominators
    d = [] # Denominators

    for i in range(len(e)):
        if i == 0:
            ni = e[i]
            di = 1
        elif i == 1:
            ni = e[i]*e[i-1] + 1
            di = e[i]
        else: # i > 1
            ni = e[i]*n[i-1] + n[i-2]
            di = e[i]*d[i-1] + d[i-2]

        n.append(ni)
        d.append(di)
        yield (ni, di)

RSA Review

An RSA public key consists of two integers: an exponent $e$ and a modulus $N$ . $N$ is the product of two randomly chosen prime numbers $p$ and $q$ . The private key, $d$ , is the decryption exponent:

d = e^{-1}\ \text{mod}\ (p-1)(q-1) = e^{-1}\ \text{mod}\ \varphi(N)

Where $\varphi(N)$ is Euler’s totient function.

That is, there exists an integer $k$ such that $ed-k\varphi(N)=1$ , therefore:

\varphi(N) = \frac{ed - 1}{k}

Lets assume that the attacker has an educated guess of what $k$ and $d$ are. Using the formula above he can simply compute $\varphi(N)$ , but what can he do with $\varphi(N)$ ? and how can he be certain that these are the correct $k$ and $d$ ?

Factoring N with $\varphi(N)$

Recall that $N=pq$ and $\varphi(N) = (p-1)(q-1)$ :

\begin{aligned} \varphi(N) &= (p-1)(q-1) \\ &= N -p -q +1 \\ &= N -p -\frac{N}{p} + 1 \end{aligned}

Therefore:

p^2 +p(\varphi(N) -N -1) -N = 0

That is, given $\varphi(N)$ ( $N$ is public knowledge) we can efficiently compute the quadratic roots $p_1$ , $p_2$ and simply check if $p_1p_2 = N$ to ascertain correctness.

Guessing $k$ and $d$

Recall that $ed-k\varphi(N)=1$ , therefore:

\left| \frac{e}{\varphi(N)} - \frac{k}{d} \right| = \frac{1}{d\varphi(N)}

Hence, $\frac{k}{d}$ is a rational approximation of $\frac{e}{\varphi(N)}$ ( $\frac{1}{d\varphi(N)}$ is small). Assuming the attacker has $\frac{e}{\varphi(N)}$ , he may find $\frac{k}{d}$ among its convergents. But… the attacker doesn’t have $\varphi(N)$ , he only has the $e$ and $N$ .

Could it be that under certain conditions $\frac{k}{d}$ may be derived from $\frac{e}{N}$ ?

Wiener’s Theorem

Let $N=pq$ with $q<p<2q$ . Let $d<\frac{1}{3}N^{\frac{1}{4}}$ . Given $\langle e,N \rangle$ with $ed = 1\ \text{mod}\ \varphi(N)$ , $d$ can be efficiently recovered by searching the right $\frac{k}{d}$ among the convergents of $\frac{e}{N}$ .

Sanity Check

So the whole attack is as follows:

Generate a vulnerable RSA keypair (one with short private exponent ( $d<\frac{1}{3}N^{\frac{1}{4}}$ )).
Find the convergents of the continued fraction expansion of $\frac{e}{N}$ .
Iterate through the convergents $\frac{d_i}{k_i}$ :
- Compute $\varphi_i(N)$ using $k_i$ and $d_i$ .
- Ascertain correctness through factoring $N$ with $\varphi_i(N)$ . (Alternatively, we can do [²] instead).

Lets see if it actually works.

Vulnerable Key Generation

We simply adapt the normal RSA key generation to fit the constraints on $d$ , $q$ and $p$ .

# Low Private Exponent Generation

import gmpy2, random
from gmpy2 import isqrt, c_div
# Adapted from Hack.lu 2014 CTF

urandom = random.SystemRandom()

def get_prime(size):
    while True:
        r = urandom.getrandbits(size)
        if gmpy2.is_prime(r): # Miller-rabin
            return r

def test_key(N, e, d):
    msg = (N - 123) >> 7
    c = pow(msg, e, N)
    return pow(c, d, N) ==  msg

def create_keypair(size):
    while True:
        p = get_prime(size // 2)
        q = get_prime(size // 2)
        if q < p < 2*q:
            break

    N = p * q
    phi_N = (p - 1) * (q - 1)

    # Recall that: d < (N^(0.25))/3
    max_d = c_div(isqrt(isqrt(N)), 3)
    max_d_bits = max_d.bit_length() - 1

    while True:
        d = urandom.getrandbits(max_d_bits)
        try:
            e = int(gmpy2.invert(d, phi_N))
        except ZeroDivisionError:
            continue
        if (e * d) % phi_N == 1:
            break
    assert test_key(N, e, d)

    return  N, e, d, p, q

The Whole Attack Flow

#!/usr/bin/python3
import cf, sys, hashlib
import vulnerable_key as vk
from sympy import *

def sha1(n):
    h = hashlib.sha1()
    h.update(str(n).encode('utf-8'))
    return h.hexdigest()

if __name__ == '__main__':
    N, e, d, p, q = vk.create_keypair(1024)
    print('[+] Generated an RSA keypair with a short private exponent.')
    print('[+] For brevity, keypair components are crypto. hashed:')
    print('[+] ++ SHA1(e):    ', sha1(e))
    print('[+] -- SHA1(d):    ', sha1(d))
    print('[+] ++ SHA1(N):    ', sha1(N))
    print('[+] -- SHA1(p):    ', sha1(p))
    print('[+] -- SHA1(q):    ', sha1(q))
    print('[+] -- SHA1(phiN): ', sha1((p - 1)*(q - 1)))
    print('[+] ------------------')

    cf_expansion = cf.get_cf_expansion(e, N)
    convergents = cf.get_convergents(cf_expansion)
    print('[+] Found the continued fractions expansion convergents of e/N.')

    print('[+] Iterating over convergents; '
            'Testing correctness through factorization.')
    print('[+] ...')
    for pk, pd in convergents: # pk - possible k, pd - possible d
        if pk == 0:
            continue;

        possible_phi = (e*pd - 1)//pk

        p = Symbol('p', integer=True)
        roots = solve(p**2 + (possible_phi - N - 1)*p + N, p)

        if len(roots) == 2:
            pp, pq = roots # pp - possible p, pq - possible q
            if pp*pq == N:
                print('[+] Factored N! :) derived keypair components:')
                print('[+] ++ SHA1(e):    ', sha1(e))
                print('[+] ++ SHA1(d):    ', sha1(pd))
                print('[+] ++ SHA1(N):    ', sha1(N))
                print('[+] ++ SHA1(p):    ', sha1(pp))
                print('[+] ++ SHA1(q):    ', sha1(pq))
                print('[+] ++ SHA1(phiN): ', sha1(possible_phi))
                sys.exit(0)

    print('[-] Wiener\'s Attack failed; Could not factor N')
    sys.exit(1)

Executing it:

$ ./wiener.py
[+] Generated an RSA keypair with a short private exponent.
[+] For brevity, keypair components are crypto. hashed:
[+] ++ SHA1(e):     cf50c0f6e658fae6bd416f7cb5b99dd2764b44fa
[+] -- SHA1(d):     1772bee24f59ea13976f03510bbc32852f02c300
[+] ++ SHA1(N):     d2d6f603c4adf7cdc0d449ca288dd130a6741c91
[+] -- SHA1(p):     d34f85dbc869626f7cab9c367bcbfec8aad8a6d3
[+] -- SHA1(q):     1e93d20bf5a79200b98441ef8b82d9f76a06df8a
[+] -- SHA1(phiN):  a5835c28d591a66e57eacdeab88a0d1d0cb3d74a
[+] ------------------
[+] Found the continued fractions expansion convergents of e/N.
[+] Iterating over convergents; Testing correctness through factorization.
[+] ...
[+] Factored N! :) derived keypair components:
[+] ++ SHA1(e):     cf50c0f6e658fae6bd416f7cb5b99dd2764b44fa
[+] ++ SHA1(d):     1772bee24f59ea13976f03510bbc32852f02c300
[+] ++ SHA1(N):     d2d6f603c4adf7cdc0d449ca288dd130a6741c91
[+] ++ SHA1(p):     1e93d20bf5a79200b98441ef8b82d9f76a06df8a
[+] ++ SHA1(q):     d34f85dbc869626f7cab9c367bcbfec8aad8a6d3
[+] ++ SHA1(phiN):  a5835c28d591a66e57eacdeab88a0d1d0cb3d74a

All used code snippets are available on github.

That’s it ! :) I hope it brought some value to you.

Comments and thoughts are welcome on this tweet:

New (old-polished) blog post! Crypto-Classics: Wiener's RSA Attack: https://t.co/vjTYygdV2v
— Sagi Kedmi (@SagiKedmi) September 28, 2016

M.Wiener. Cryptanalysis of Short RSA Exponents.
↩
We could also validate correctness by encrypting using $\langle e,N \rangle$ and decrypting using $\langle d_i, N \rangle$ . That is, pick a random message $m$ and test if $m \equiv (m)^{ed_i} \text{mod}\ N$ .
↩