Rot256 : Cryptography & Other Random Bits.

# The “H1” Challenge

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

Python Script (click to expand)
  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 \overset\leftarrow \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:

 1 2 3 4 5 6 7 8 9  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:

 1 2 3 4  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: $o = a \cdot \sum_{i=0}^{\text{nbytes}-1} B_i \cdot b^i \mod 2^\text{nbits}, \ \ \ \forall i: B_i \in [0, 255]$

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:

$k = \texttt{0x1010101} \cdot \sum_{i=0}^{\text{nbytes}-1} B_i \cdot 2^{32 \cdot i} \mod 2^\text{nbits}$

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}$$.

$k = \left(\texttt{0x1010101} \cdot \sum_{i=0}^{(\text{nbits} / 32) - 1} B_i \cdot 2^{32 \cdot i}\right) + 2^\text{nbits} \left(\texttt{0x1010101} \cdot \sum_{i = \text{nbits} / 32}^{\text{bytes}} B_{i} \cdot 2^{32 \cdot i - \text{nbits}}\right) \mod 2^\text{nbits}$ Also, by observing that the left side cannot be larger than $$2^\text{nbits} - 1$$, we get: $k = \texttt{0x1010101} \cdot \sum_{i=0}^{(\text{nbits} / 32) - 1} B_i \cdot 2^{32 \cdot i} = \sum_{i=0}^{(\text{nbits} / 32) - 1} (B_i \cdot \texttt{0x1010101}) \cdot 2^{32 \cdot i}$ 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:

$h_1 = \texttt{SHA512}(\text{“Hello Alice”})$ $h_2 = \texttt{SHA512}(\text{“Dinner sounds good. Thanks for the flag."})$

Recall (from the description of ECDSA) that:

$s_1 = k_1^{-1} \cdot (h_1 + r_1 \cdot d)$ $s_2 = k_2^{-1} \cdot (h_2 + r_2 \cdot d)$

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

$s_2 \cdot k_2 - h_2 = r_2 \cdot d, s_1 \cdot k_1 - h_1 = r_1 \cdot d$ $(s_2 \cdot k_2 - h_2) / (s_1 \cdot k_1 - h_1) = r_2 / r_1$ $(s_2 \cdot k_2 - h_2) \cdot r_1 = (s_1 \cdot k_1 - h_1) \cdot r_2$ $(s_2 \cdot k_2 - h_2) \cdot r_1 / (s_1 \cdot r_2) = k_1 - h_1 / s_1$ $(s_2 \cdot k_2 - h_2) \cdot r_1 / (s_1 \cdot r_2) + h_1 / s_1 = k_1$ $(s_2 \cdot r_1 / (s_1 \cdot r_2)) \cdot k_2 + (- h_2 \cdot r_1 / (s_1 \cdot r_2) + h_1 / s_1) = k_1$ Note that the terms: $t = - s_2 \cdot r_1 / (s_1 \cdot r_2), u = h_2 \cdot r_1 / (s_1 \cdot r_2) - h_1 / s_1$ Can be computed directly from the signature, rewriting: $0 = k_1 + t k_2 + u \mod n$ Using our knowlege of how $$k_1$$ and $$k_2$$ are generated: $0 = \sum_{i = 0}^{15} V_i B_i + \sum_{i = 0}^{15} t V_i B_i' + u \mod n$

$-B_0 V_0 = -B_0 \cdot \texttt{0x01010101} = \sum_{i = 1}^{15} V_i B_i + \sum_{i = 0}^{15} t V_i B_i' + u \mod n$

$-B_0 = \sum_{i = 1}^{15} V_i B_i / \texttt{0x01010101} + \sum_{i = 0}^{15} t V_i B_i' / \texttt{0x01010101} + u / \texttt{0x01010101} \mod n$ $-B_0 = \sum_{i = 1}^{15} V_i B_i / \texttt{0x01010101} + \sum_{i = 0}^{15} t V_i B_i' / \texttt{0x01010101} + u / \texttt{0x01010101} + q n$ For some $$q$$, over the integers. Now consider the following matrix:

$\scriptstyle \begin{bmatrix} n & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{1} / \texttt{0x01010101} & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{2} / \texttt{0x01010101} & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{3} / \texttt{0x01010101} & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{4} / \texttt{0x01010101} & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{5} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{6} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{7} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{8} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{9} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{10} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{11} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{12} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{13} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{14} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ V_{15} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{0} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{1} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{2} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{3} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{4} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{5} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{6} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{7} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{8} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{9} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{10} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ t V_{11} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 & 0 \\ t V_{12} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 & 0 \\ t V_{13} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 & 0 \\ t V_{14} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 & 0 \\ t V_{15} / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 0 \\ u / \texttt{0x01010101} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2^8 \\ \end{bmatrix}$

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:

  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  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:

$\scriptstyle (-162, 239, 161, 163, 166, 102, 49, 47, 165, 156, 72, 217, 230, 37, 141, 125, 234, 51, 157, 242, 222, 239, 162, 66, 145, 133, 171, 141, 172, 29, 221, 51, 256)$

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:

$d = (k_1 \cdot s_1 - h_1) / r_1 \mod n$

# 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:

$u_1 = h s^{-1} \mod n, \ \ \ \ u_2 = r s^{-1} \mod n$

$(x_1, y_1) = R = u_1 \times G + u_2 \times Q_a = (h s^{-1}) \times G + (r s^{-1}) \times Q_a$

$\text{Check: } x_1 = r \mod n$

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:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  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:

  1 2 3 4 5 6 7 8 9 10 11  # 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) 

Lastly we decrypt the message from Alice which contains the flag:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14  _, _, ca = (8832295267397231051293216564016639537146222596144354850230682204978731311879255662259663270183445827348338041752369314181111940713714991119349376636404112, 8683784208731634307361157916911868656279723101808163939313971801256736484458199874570532609285522391139002296248059424750941962344918156540408403221858292, 105398535464409171419472607677747462033030589690350997911381059472020486557672504778060748058626707326992258591478040500759349352824508941100030623708235493999018571171774658661651532338275358740821547158517615704187173346885098836066743736788259192831313414309775979590033581301910426314601982482556670097620) ka = [ 0x8a6e81a10c229af504772b51c502638820811034faa62b8dafa019210347918419b71d0638c89b59026b7611edc6a14b2c1c1fb1092a352adfffb7e114f4f385, 0x3f837315a1fb46097f5eb680697901d75758b859846d37cad33d3f464efb84ace1e85fc60f4e445a031b5ca0e4965e0b081bd4a6e8efea1d3ba07aad51a70cd ] ca = ca.to_bytes(byteorder='big',length=(ca.bit_length() + 7) // 8) for k in ka: try: recv_msg = Decrypt(ca, k) print(recv_msg) except: pass 

And recover the flag:

CTF{But_in_real_life_devs_would_never_use_such_a_buggy_RNG_right?}


The code and challenge can be found on Github