The “H1” Challenge

We are given two files. A python3 script (chall.py):

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

#!/usr/bin/python3
import os
import hashlib
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

flag = open('flag.txt').read()
INF = (1, 1, 0)

mod = 8948962207650232551656602815159153422162609644098354511344597187200057010413552439917934304191956942765446530386427345937963894309923928536070534607816947
a = 6294860557973063227666421306476379324074715770622746227136910445450301914281276098027990968407983962691151853678563877834221834027439718238065725844264138
b = 3245789008328967059274849584342077916531909009637501918328323668736179176583263496463525128488282611559800773506973771797764811498834995234341530862286627
n = 8948962207650232551656602815159153422162609644098354511344597187200057010413418528378981730643524959857451398370029280583094215613882043973354392115544169
G = (5139617820728399941653175323358137352238277428061991823713659546881441331696699723004749024403291797641521696406798421624364096550661311227399430098134141,
     1798860115416690485862271986832828064808333512613833729548071279524320966991708554765227095605106785724406691559310536469721469398449016850588110200884962,
     5042518522433577951395875294780962682755843408950010956510838422057522452845550974098236475624683438351211176927595173916071040272153903968536756498306512)

def Double(p):
    x, y, z = p
    if z == 0 or y == 0:
        return INF
    ysqr = y * y % mod
    zsqr = z * z % mod
    s = 4 * x * ysqr % mod
    m = (3 * x * x + a * zsqr * zsqr) % mod
    x2 = (m * m - 2 * s) % mod
    y2 = (m * (s - x2) - 8 * ysqr * ysqr) % mod
    z2 = 2 * y * z % mod
    return x2, y2, z2

def Add(p, q):
    if p[2] == 0:
        return q
    if q[2] == 0:
        return p
    x1, y1, z1 = p
    x2, y2, z2 = q
    z1sqr = z1 * z1 % mod
    z2sqr = z2 * z2 % mod
    u1 = x1 * z2sqr % mod
    u2 = x2 * z1sqr % mod
    s1 = y1 * z2 * z2sqr % mod
    s2 = y2 * z1 * z1sqr % mod
    if u1 == u2:
        if s1 != s2:
            return INF
        else:
            return Double(p)
    h = u2 - u1 % mod
    hsqr = h * h % mod
    hcube = hsqr * h % mod
    r = s2 - s1 % mod
    t = u1 * hsqr % mod
    x3 = (r * r - hcube - 2 * t) % mod
    y3 = (r * (t - x3) - s1 * hcube) % mod
    z3 = h * z1 * z2 % mod
    return x3, y3, z3

def Multiply(p, x):
    if p == INF:
        return p
    res = INF
    while x:
        x, r = divmod(x, 2)
        if r:
            res = Add(res, p)
        p = Double(p)
    return res

def Transform(m, l):
    z = m
    shift = l - n.bit_length()
    if shift > 0:
        z >>= shift
    return z

def RNG(nbits, a, b):
    nbytes = nbits // 8
    B = os.urandom(nbytes)
    return a * sum([B[i] * b ** i for i in range(len(B))]) % 2**nbits

def Sign(msg, d):
    h = hashlib.sha512(msg)
    z = Transform(int.from_bytes(h.digest(), 'big'), h.digest_size*8)
    k = RNG(n.bit_length(), 16843009, 4294967296)
    x1, y1, z1 = Multiply(G, k)
    r = (x1 * pow(z1, -2, mod) % mod) % n
    s = pow(k, -1, n) * (z + r * d) % n
    assert int(s) == pow(k, -1, n) * (z + r * d) % n
    return r, s

def Verify(msg, Q, r, s):
    h = hashlib.sha512(msg)
    z = Transform(int.from_bytes(h.digest(), 'big'), h.digest_size*8)
    u1 = z*pow(s, -1, n) % n
    u2 = r*pow(s, -1, n) % n
    x1, y1, z1 = Add(Multiply(G, u1), Multiply(Q, u2))
    return r == (x1 * pow(z1, -2, mod) % mod) % n

def Encrypt(plaintext, x):
    key = hashlib.sha256(str(x).encode()).digest()
    aes = algorithms.AES(key)
    encryptor = Cipher(aes, modes.ECB(), default_backend()).encryptor()
    padder = padding.PKCS7(aes.block_size).padder()
    padded_data = padder.update(plaintext) + padder.finalize()
    ciphertext = encryptor.update(padded_data) + encryptor.finalize()
    return ciphertext

def Decrypt(ciphertext, x):
    key = hashlib.sha256(str(x).encode()).digest()
    aes = algorithms.AES(key)
    decryptor = Cipher(aes, modes.ECB(), default_backend()).decryptor()
    unpadder = padding.PKCS7(aes.block_size).unpadder()
    decrypted_data = decryptor.update(ciphertext) + decryptor.finalize()
    plaintext = unpadder.update(decrypted_data) + unpadder.finalize()
    return plaintext

# Alice and Bob have their keys:
da = RNG(n.bit_length(), 1, 256)
Qa = Multiply(G, da)
db = RNG(n.bit_length(), 1, 256)
Qb = Multiply(G, db)
x1a, y1a, z1a = Multiply(Qb, da)
ka = x1a * pow(z1a, -2, mod) % mod
x1b, y1b, z1b = Multiply(Qa, db)
kb = x1b * pow(z1b, -2, mod) % mod

# Alice sends message to Bob:
msga = b'Hello Bob.'
ra, sa = Sign(msga, da)
ca = Encrypt(msga, ka)
print('Alice -> Bob:', (ra, sa, int.from_bytes(ca, 'big')))

# Bob receives and verifies message:
recv_msg = Decrypt(ca, kb)
assert Verify(recv_msg, Qa, ra, sa)

# Bob sends message to Alice:
msgb = b'Hello Alice.'
rb, sb = Sign(msgb, db)
cb = Encrypt(msgb, kb)
print('Bob -> Alice:', (rb, sb, int.from_bytes(cb, 'big')))

# Alice receives and verifies message:
recv_msg = Decrypt(cb, ka)
assert Verify(recv_msg, Qb, rb, sb)

# Alice sends message to Bob:
msga = (f'Dinner tonight? What about Tapioca? Btw, here is the flag: {flag}').encode()
ra, sa = Sign(msga, da)
ca = Encrypt(msga, ka)
print('Alice -> Bob:', (ra, sa, int.from_bytes(ca, 'big')))

# Bob receives and verifies message:
recv_msg = Decrypt(ca, kb)
assert Verify(recv_msg, Qa, ra, sa)

# Bob sends message to Alice:
msgb = b'Dinner sounds good. Thanks for the flag.'
rb, sb = Sign(msgb, db)
cb = Encrypt(msgb, kb)
print('Bob -> Alice:', (rb, sb, int.from_bytes(cb, 'big')))

# Alice receives and verifies message:
recv_msg = Decrypt(cb, ka)
assert Verify(recv_msg, Qb, rb, sb)

And the following output (stdout from the python script):

Alice -> Bob: (8618416354247009865173783322782283385800726568519779763790691157278063798628048418532907783021806238103423515210146966468025964847364086792099622893845216, 2932674107137731789093617068375500084388905453653468925392946088867116597531950960271857205235755778202380084260003117176704579423285955014316540314931750, 27865871384804321325511205140263204607)
Bob -> Alice: (6706720197123832142768727143395528571627385686729472279085077699672602636953568596628477227511870037092766007177588966333093607595831000050978265637877796, 1073779379108240410856990657565545229209771903946426639922087094813786902448520023335130808991515066506036954730763452318418336144389425011731474342543709, 111403492170712993917428321974111102656)
Alice -> Bob: (8832295267397231051293216564016639537146222596144354850230682204978731311879255662259663270183445827348338041752369314181111940713714991119349376636404112, 8683784208731634307361157916911868656279723101808163939313971801256736484458199874570532609285522391139002296248059424750941962344918156540408403221858292, 105398535464409171419472607677747462033030589690350997911381059472020486557672504778060748058626707326992258591478040500759349352824508941100030623708235493999018571171774658661651532338275358740821547158517615704187173346885098836066743736788259192831313414309775979590033581301910426314601982482556670097620)
Bob -> Alice: (7616464676048536081690041693308621105395807976530049374449777558721544903144139995398352331701243976154631946836252022822278420653297509476320989403738186, 7381293847317597354132365685036776332763847784351725370466906894121224725876600151244989563125805807680044723478850091886778158534219876869209592138625256, 7994736246642278834331127451449673561762900804586058657648578638831731501930073150317394505661139656896430884711113)

The python script implements the operation (Add/Double/Exponentiation) of the curve $y^2 = x^3 + \text{a} x + \text{b}$ over the 512-bit prime field $\mathbb{Z}_\text{mod}$ with $\text{mod}, \text{a}, \text{b}$ as defined in the script. All operations are done using Jacobian coordinates. The order of this curve is $n$ and $G$ is a valid point on the curve (which has prime order).

The script mocks a key exchange between parties Alice and Bob:

1. First it picks random secret keys for Alice (da) / Bob (db) using RNG (more on that later) and computes their public key (Qa = G^da, Qb = G^db):

    da = RNG(n.bit_length(), 1, 256)
    Qa = Multiply(G, da)
    db = RNG(n.bit_length(), 1, 256)
    Qb = Multiply(G, db)
   

2. It then does a Diffie-Hellman key exchange:

    x1a, y1a, z1a = Multiply(Qb, da)
    ka = x1a * pow(z1a, -2, mod) % mod
    x1b, y1b, z1b = Multiply(Qa, db)
    kb = x1b * pow(z1b, -2, mod) % mod
   

   Remembering to convert the x-coordinate from Jacobian coordinates to affine (such that the representation is unique). ka and kb are the resulting shared secret (and ka = kb).

3. Alice then signs a message:

    # Alice sends message to Bob:
    msga = b'Hello Bob.'
    ra, sa = Sign(msga, da)
   

   Using ECDSA (much more on that later).

4. Alice then encrypts the message using the shared secret and sents the encrypted message to Bob:

    ca = Encrypt(msga, ka)
    print('Alice -> Bob:', (ra, sa, int.from_bytes(ca, 'big')))
   

5. Bob receives the message, decrypts it using the shared secret and verifies the ECDSA signature on the decrypted message.

    # Bob receives and verifies message:
    recv_msg = Decrypt(ca, kb)
    assert Verify(recv_msg, Qa, ra, sa)
   

Steps 2-5 is repeated for 4 different message:

1. One from Alice to Bob: “Hello Bob.”
2. One from Bob to Alice: “Hello Alice.”
3. One from Alice to Bob: “Dinner tonight? What about Tapioca? Btw, here is the flag: {flag}”
4. One from Bob to Alice: “Dinner sounds good. Thanks for the flag.”

Obviously our goal is to decrypt the third message…

About ECDSA and Its “Nonces”

Let us do a brief recap on ECDSA (a depressingly prolific signature scheme without a security proof):

Signing

Here is how to sign $m$ using the private key $d \in \mathbb{Z}_n$.

1. Hash the message: $h \gets \texttt{SHA512}(m) \in \mathbb{Z}_{n}$
2. Sample a random nonce: $k \sample \mathbb{Z}_{n}$
3. Exponentiate by the nonce: $(x_1, y_1) \gets k \times G \in \mathbb{E}[\mathbb{Z}_p]$
4. Reduce the x-coordinate mod the group order: $r \gets x_1 \mod n$
5. Complete the signature: $s \gets k^{-1} (h + r d) \mod n$
6. Signature is: $\sigma = (r, s)$

Verifying

Here is how to verify a signature $(r, s)$ against the message $m$ and public key $Q = d \times G$:

1. Hash the message: $h \gets \texttt{SHA512}(m) \in \mathbb{Z}_{n}$
2. Calculate $u_1 \gets h s^{-1} \mod n$, $u_2 \gets r s^{-1} \mod n$
3. Compute $(x_1, y_1) \gets u_1 \times G + u_2 \times Q$
4. Output $r \overset?= x_1 \mod n$

The Role of k

When you look at how $s$ is computed, it is pretty clear that $k$ ( $k^{-1}$ really) acts as a kind of “mask”: given $h$ and $r$ it is the only thing hiding $d$ (the private key). In ECDSA nomenclature $k$ is often called a “nonce”, however the word “nonce” in relation to ECDSA is a huge misnomer: if you reuse an ECDSA nonce, you are toast – as expected. However, even if:

1. The nonce is predictable – you are toast.
2. Nonces from different signatures share a linear relation – you are toast.
3. Some part of the nonces is predictable – you are toast.
4. The distribution of any bit in the nonce is not perfectly uniform – you are toast.

Therefore, when looking for vulnerabilities in an ECDSA implementation it is an obvious thing to check for. If you are in interested in more details (beyond this blog post) take a look at Recovering cryptographic keys from partial information, by example. How let us take a look at how the H1 challenge implements ECDSA:

def Sign(msg, d):
    h = hashlib.sha512(msg)
    z = Transform(int.from_bytes(h.digest(), 'big'), h.digest_size*8)
    k = RNG(n.bit_length(), 16843009, 4294967296)
    x1, y1, z1 = Multiply(G, k)
    r = (x1 * pow(z1, -2, mod) % mod) % n
    s = pow(k, -1, n) * (z + r * d) % n
    assert int(s) == pow(k, -1, n) * (z + r * d) % n
    return r, s

Vis-à-vis the previous section, the RNG call is going to be interesting…

RNG Shenanigans

The RNG function looks like this:

def RNG(nbits, a, b):
    nbytes = nbits // 8
    B = os.urandom(nbytes)
    return a * sum([B[i] * b ** i for i in range(len(B))]) % 2**nbits

In other words, the output $o$ is computed as:

Recall that in Sign, the ECDSA nonce is generated as k = RNG(n.bit_length(), 16843009, 4294967296). In other words: a = 16843009 = 0x1010101, b = 4294967296 = 0x100000000 = 2^32. Plugging this in to the equation for RNG, means that the nonce k is generated as:

Unpacking this expression a bit, we see that any term beyond $i = nbits / 32$ can be eliminated, as it is a multiple of $2^\text{nbits}$.

Also, by observing that the left side cannot be larger than $2^\text{nbits} - 1$, we get:

In the integers. Since $B_i < \texttt{0x100}$, the $B_i \cdot \texttt{0x1010101}$ operation, repeats the same byte 4 times to fill a 32-bit word. The $2^{32 * i}$ multiplication is a right shift by $i$ 32-bit words. In other words we expect $k$ to look something like this:

0x0x9f9f9f9fb6b6b6b667676767c5c5c5c5...omitted...eaeaeaea9a9a9a9a2929292915151515d0d0d0d0

Where $\text{nbits} / 32 = 512 / 32 = 16$ bytes are each repeated 4 times and concated to form $k$. In other words: $k$ can be written as a linear combination $k = \sum_{i} B_i V_i$ of integers $V_i = \texttt{0x01010101} \cdot 2^{32 \cdot i}$ where the $B_i's$ are short (they are bytes). This has all the markings of a lattice attack.

Back to ECDSA (and LLL)

We take the two signatures by Bob (for which we know the messages):

r1, s1, _ = (6706720197123832142768727143395528571627385686729472279085077699672602636953568596628477227511870037092766007177588966333093607595831000050978265637877796, 1073779379108240410856990657565545229209771903946426639922087094813786902448520023335130808991515066506036954730763452318418336144389425011731474342543709, 111403492170712993917428321974111102656)
r2, s2, _ = (7616464676048536081690041693308621105395807976530049374449777558721544903144139995398352331701243976154631946836252022822278420653297509476320989403738186, 7381293847317597354132365685036776332763847784351725370466906894121224725876600151244989563125805807680044723478850091886778158534219876869209592138625256, 7994736246642278834331127451449673561762900804586058657648578638831731501930073150317394505661139656896430884711113)

And we can compute:

Recall (from the description of ECDSA) that:

If we isolate $k_1$ the $d$ (secret key) terms cancel:

Note that the terms:

Can be computed directly from the signature, rewriting:

Using our knowlege of how $k_1$ and $k_2$ are generated:

For some $q$, over the integers. Now consider the following matrix:

We happen to know that there exists a vector $W$ in the row span of the matrix above with L-infinity norm at most $2^8$, i.e. where every entry $W_i$ has $| W_i | \leq 2^8$. Why? Because $( -B_0, B_1, B_2, \ldots, B_{15}, B_0, \ldots, B_{15}, 2^8)$ is one such vector, per the equality above! To solve this we feed the matrix to LLL. This looks something like this in SageMath:

def lll_solve(t, u):

    cols = (L // B) * 2 + 1

    K = 2^8

    M = []
    M.append([n] + (cols - 1) * [0])

    inv = F(0x01010101)^-1

    ci = [0x01010101 * 2^(B * i) for i in range(L / B)]
    ti = ci + [ci[i] * t for i in range(L / B)]
    ti = [int(v * inv) for v in ti]

    for i, v in enumerate(ti[1:]):
        M.append([v] + [0] * i + [1] + [0] * (cols - i - 2))

    M.append([int(u * inv)] + [0] * (cols - 2) + [K])

    for row in M:
        print(row)

    M = Matrix(M)

    for row in M.LLL():
        print(row)
        break

    # flip
    row[0] = -row[0]

    k1 = int(''.join([4 * ('%02x' % v) for v in row[:16]][::-1]), 16)
    k2 = int(''.join([4 * ('%02x' % v) for v in row[16:32]][::-1]), 16)

    return k1, k2

The solution we find is:

From this is it straightforward to recover $k_1$ and $k_2$ (as done in the script). Since $s_1 = k_1^{-1} (h_1 + r d)$ (from the ECDSA description) and having discovered $k_1$ it is easy to recover the Bob’s secret key from $s_1, h_1, r_1$ as:

Recovering Alice Public Key

We are almost done. However to complete the Diffie-Hellman exchange, we also need Alice’s public key (which we are not given explicitly). This is easy to extract from a signature as long as we know which message is signed. Luckly we have one such message (“Hello Bob.”).

Recall that during verification:

Where $Q_a$ is Alice’s public key. Now, the field in which $x_1$ resides happens to be larger than $n$, which means that $x_1 \in \{ r, r + n \}$. So we enumerate all possible points $R = (x_1, y_1) \in \mathbb{E}[D]$ and for each we compute $Q_a = r^{-1} \times (s \times R - h \times G)$. It looks something like this in SageMath:

def recover_key(r, s, h):

    # compute possible x-coordinates
    xs = [D(int(r))]
    if D.order() > F.order():
        xs.append(D(int(r) + n))

    pks = []
    for x in xs:

        # find curve point with the given x-coordinate
        try:
            R = E.lift_x(x)
        except ValueError:
            # not on the curve
            continue

        # it is either R or -R (for which the x-coordinate is the same)
        pks.append(int(r^-1) * (int(s) * R - int(h) * G))
        pks.append(int(r^-1) * (int(s) * (-R) - int(h) * G))

    return pks

Wrapping Up

Finally we recover the possible shared secrets (depending on whether we guessed $R$ correctly) as:

# Alice -> Bob: "Hello Bob."
r, s, _ = (8618416354247009865173783322782283385800726568519779763790691157278063798628048418532907783021806238103423515210146966468025964847364086792099622893845216, 2932674107137731789093617068375500084388905453653468925392946088867116597531950960271857205235755778202380084260003117176704579423285955014316540314931750, 27865871384804321325511205140263204607)

msga = b'Hello Bob.'

r = F(r)
s = F(s)

for pk in recover_key(r, s, h = msg_to_h(msga)):
    ss = int((int(d) * pk)[0])
    print('ss = 0x%x' % ss)