Skip to content

Hastad’s Broadcast Attack

Introduction

The Hastad’s Broadcast Attack works against small public exponent, especially if we cannot apply the n-th root on the ciphertext.

However, we need several ciphertexts from the same cleartext to use this attack.

Prerequisites :

$$ c_{1}, c_{2}, ..., c_{e} \text{: Encrypted messages from the same cleartext} $$

Maths

Imagine we have e = 3 and :

  • pubKey(n1, 3) and c1 the corresponding ciphertext to m.
  • pubKey(n2, 3) and c2 the corresponding ciphertext to m.
  • pubKey(n3, 3) and c3 the corresponding ciphertext to m.

This lead us to the following system of equations :

$$ m^3 \equiv c_{1} [n_{1}] $$ $$ m^3 \equiv c_{2} [n_{2}] $$ $$ m^3 \equiv c_{3} [n_{3}] $$

To find the original message, the easiest way is to calculate the cube root of one of the three encrypted messages. In some cases we cannot directly apply the cube root to any of the three encrypted messages (c1, c2 and c3). However, we can use the Chinese remainder theorem to find another equivalent solution that we can put to the cube root.

If the following condition (this is always the case in RSA) GCD(n1, n2) = GCD(n1, n3) = GCD(n2, n3) = 1 is true, we know, thanks to the Chinese Remainder Theorem, that there is a solution x which verifies :

$$ x \equiv m^3 [n_{1} \times n_{2} \times n_{3}] $$

The goal is to find x, then compute the third root of x to find m.

Example

Write-up for the challenge Broadcast from picoCTF 2017.

Source code (functions)

from gmpy2 import invert


def mul(lst):
    ret = 1
    for n in lst:
        ret *= n
    return ret

def crt(C, N):
    assert len(C) == len(N)

    total = 0
    modulo = mul(N)

    for n_i, c_i in zip(N, C):
        p = modulo // n_i
        total += c_i * invert(p, n_i) * p
    return total % modulo

Source code (solve)

Let's try to process the third root on the three ciphertexts, then on the solution of the Chinese Remainder Theorem.

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot


e = 3
c1 = 261345950255088824199206969589297492768083568554363001807292202086148198722402380676138078614774919011859552072663081496837339290624940098045941666974866866446747148793714978880579180140109296120579252064365079387725663301419872301919689576905808379498644521649965160582830113494402011911767969632749183893040
n1 = 1001191535967882284769094654562963158339094991366537360172618359025855097846977704928598237040115495676223744383629803332394884046043603063054821999994629411352862317941517957323746992871914047324555019615398720677218748535278252779545622933662625193622517947605928420931496443792865516592262228294965047903627
c2 = 147535246350781145803699087910221608128508531245679654307942476916759248493513464389047783263853539559909464172380863409036822999877585212049666595082028787841599217182491627615515631140110169864221202526469804843851098436855381511638675058329198719461892960196374373646640630449862633901416208177651026021529
n2 = 405864605704280029572517043538873770190562953923346989456102827133294619540434679181357855400199671537151039095796094162418263148474324455458511633891792967156338297585653540910958574924436510557629146762715107527852413979916669819333765187674010542434580990241759130158992365304284892615408513239024879592309
c3 = 633230627388596886579908367739501184580838393691617645602928172655297372327529230304236376306377467969593653208991026410622586986036527560756293113090229207730884534852421083696475045459334099812735568263375731682637178526500730184935921680548531576585762254329708094833083800017939729261922041250790796509661
n3 = 1204664380009414697639782865058772653140636684336678901863196025928054706723976869222235722439176825580211657044153004521482757717615318907205106770256270292154250168657084197056536811063984234635803887040926920542363612936352393496049379544437329226857538524494283148837536712608224655107228808472106636903723


def third_root(n):
    m, valid = iroot(n, e)
    if valid:
        print("Cleartext :", long_to_bytes(m))
    else:
        print("Unable to find the third root of :", n)

C = [c1, c2, c3]
N = [n1, n2, n3]

for c in C:
    third_root(c)

x = crt(C, N)
third_root(x)

Output

Unable to find the third root of : 261345950255088824199206969589297492768083568554363001807292202086148198722402380676138078614774919011859552072663081496837339290624940098045941666974866866446747148793714978880579180140109296120579252064365079387725663301419872301919689576905808379498644521649965160582830113494402011911767969632749183893040
Unable to find the third root of : 147535246350781145803699087910221608128508531245679654307942476916759248493513464389047783263853539559909464172380863409036822999877585212049666595082028787841599217182491627615515631140110169864221202526469804843851098436855381511638675058329198719461892960196374373646640630449862633901416208177651026021529
Unable to find the third root of : 633230627388596886579908367739501184580838393691617645602928172655297372327529230304236376306377467969593653208991026410622586986036527560756293113090229207730884534852421083696475045459334099812735568263375731682637178526500730184935921680548531576585762254329708094833083800017939729261922041250790796509661
Cleartext : b'broadcast_with_small_e_is_killer_86029531744'