A slow descent into the dark, into madness, futility, and despair.
Summary: DSA with short secrets, lattice + meet-in-the-middle attack.
In this challenge we are given a jar file, a java source code and an output file. Jar file contains several pictures, heavily hinting to lattices (and maybe to something else?). As we will see, Flag.java and STDOUT are enough to solve the challenge.
The java program performs a DSA signature with random private and ephemeral keys. The output is given and our goal is to recover the private key. The scheme indeed looks like proper DSA and is hard to break. However, if you run the program with random parameters, you can notice that the private keys generated are much smaller than they should be. At first I thought the Flag.class file was backdoored, but it turned out to be a quite funny bug in the java code. Consider the random generating function:
// Generate a random integer in the range 1 .. q-1. private static BigInteger generateSecret(BigInteger q) { // Get the number of bits of q. int qBits = q.bitCount(); SecureRandom rand = new SecureRandom(); while (true) { BigInteger x = new BigInteger(qBits, rand); if (x.compareTo(BigInteger.ZERO) == 1 && x.compareTo(q) == -1) { return x; } } } |
Seems legit? Until you read that the BigInteger.bitCount method actually returns the Hamming Weight, not the bit size of the number! The Hamming Weight of a random prime is twice as smaller: $q$ is 256 bits and the secret keys will be roughly of size 128. This would be relatively easy, so the author decided to use $q$ with Hamming Weight 150!
Here are details of the scheme:
- $p$ is 2048-bit prime, $g$ is an element of order $q$ mod $p$ ($q$ is 256-bit prime).
- $x$ is a 256-bit private key, $y=g^x \mod p$ is a 2048-bit public key.
- To sign a message $m$:
- generate an ephemeral 256-bit key $k$;
- compute $r = g^k \mod p \mod q$;
- compute $s = (h(m) + xr)/k \mod q$;
- $(r,s)$ is the signature.
The unknowns are $x$ and $k$. Due to the bug/backdoor, they are of size 150 bits instead of 256. In such cases the lattices come to mind, since they are often used to find small solutions to various equations.
One interesting equation we have is
$$sk \equiv h(m) + xr \pmod{q}.$$
The following I found in some paper about attacking DSA but currently I lost the paper. Let’s make the equation monic in one variable:
$$k – h(m)/s – xr/s \equiv 0 \pmod{q}.$$
$$k + B + Ax \equiv 0 \pmod{q}.$$
Assume that we know bounds on $x$ and $k$, $X$ and $K$ respectively. Then we can build the following lattice (the basis vectors are rows):
$$
\begin{pmatrix}
q & 0 & 0 \\
0 & qX & 0 \\
B & AX & K \\
\end{pmatrix}
$$
Basically we encode the equation and add two additional vectors to encode modular reductions. If $XK < q - \epsilon$ then the $LLL$-reduced basis of this lattice will contain two linear equations holding over integers with roots $x$ and $k$. Unfortunately, the secrets are 150 bits instead of 128 so the bound does not hold. We can try to guess some higher bits and run the LLL attack each time, but we need to guess roughly $300-256=44$ bits which is too much.
It is easy to get some solution within the bounds. There are roughly $2^{44}$ of them and we actually need to check all of them! One check can be to verify $x$ against the public key $y = g^x \mod p$. Another way is to use $h(x)$ given in STDOUT, which is probably faster, but still too slow.
Let’s think how to generate all solutions for the given bounds once we have some solution. If $k_0 + B + Ax_0 \equiv 0$, then we want to find small $\Delta_k, \Delta_x$ such that
$$(k_0 + \Delta_k) + B + A(x_0 + \Delta_x) \equiv 0 \pmod{q}.$$
$$\Rightarrow \Delta_k + A\Delta_x \equiv 0 \pmod{q}.$$
Consider the lattice:
$$
\begin{pmatrix}
1 & -A \\
0 & q \\
\end{pmatrix}
$$
The vectors in the lattices are all possible pairs $(\Delta_x,\Delta_k)$. Moreover, the LLL-reduced basis will contain small and somewhat orthogonal vectors $(\Delta_x^{(0)}, \Delta_k^{(0)})$ and $(\Delta_x^{(1)}, \Delta_k^{(1)})$. By adding small multiplies of these vectors to $(x_0,k_0)$ we can find almost all solutions up to the bound. Note that we are interested mostly only in the $x$ coordinate. The solutions have $x$ of the following form:
$$x = x_0 + i \Delta_x^{(0)} + j \Delta_x^{(1)}$$
where $i,j$ are relatively small integers (up to few millions in our case). It is too much to check… But can we use other equations? At a first glance, they are exponential and it is hard to use them here in a way other then simply verifying $x$ or $k$. However, it is actually easy: we can split search on $i$ and $j$ by using the equation $y = g^x \mod p$. This is similar to Meet-In-The-Middle / Baby-Step-Giant-Step attacks. First, we precompute a table for all $j$: $\{ yg^{-j \Delta_x^{(1)}} \mapsto j\}$ . Then we check for all $i$ if $g^{x_0 + i \Delta_x^{(0)}}$ is in the table. When we find it, we can easily compute $x$ from $i$ and $j$!
Here is full sage code, it finds the flag in a few minutes:
from sage.all import * Y = 4675975961034321318962575265110114310875697301524971406479091223605006115642041321079605682629390144148862285125353335575850114862081357772478008490889403608973023515499959473374820321940514939155187478991555363073408293339373770407404120884229693036839637631846964085605936966005664594330150750220123106270473482589454510979171010750141467635389981140248292523060541588378749922037870081811431605806877184957731660006793364727129226828277168254826229733536459158767652636094988369367622055662565355698632032334469812735980006733267919815359221578068741143213061033728991446898051375393719722707555958912382769606279 P = 32163437489387646882545837937802838313337646833974044466731567532754579958012875893665844191303548189492604123505522382770478442837553069890471993483164949504735527438665048438808440494922021062011062567528480025060283867381823427214512155583444236623145440836252289902783715682554658231606320310129833109191138313801289027627739243726679212643242494506530838323607821437997048235272405577079630284307474612832155381483129670050964475785090109743586694668757059662450206919471125303517989042945192886030308203029077484932328302318567286732217365609075794327329327141979774234522455646843538377559711464098301949684161 Q = 81090202316656819994650163122592145880088893063907447574390172288558447451623 H = 88030618649759997479497646248126770071813905558516408828543254210959719582166 R = 34644971883866574753209424578777685962679178432833890467656897732184789528635 S = 19288448359668464692653054736434794709227686774726460500150496018082350808676 G = pow(2, int(P//Q), P) A = (-R) * inverse_mod(S, Q) % Q B = (-H) * inverse_mod(S, Q) % Q while 1: XB = 125 KB = 125-16 X = 2**XB K = 2**KB khigh = randint(0, 2**16) Bnew = B + khigh * 2**KB m = matrix(ZZ, 3, 3, [ Q, 0, 0, 0, Q * X, 0, Bnew, A * X, K ]).LLL() mat = [] target = [] for row in m[:2]: const, cx, ck = row assert cx % X == 0 and ck % K == 0 mat.append([cx / X, ck / K]) target.append(-const) mat = matrix(ZZ, mat) try: x0, k0 = mat.solve_right(vector(ZZ, target)) if int(x0) != x0 or int(k0) != k0: continue except ValueError: continue x0, k0 = int(x0), int(k0) assert (A * x0 + k0 + Bnew) % Q == 0 k0 += khigh * 2**KB assert (A * x0 + k0 + B) % Q == 0 print "SOLUTION", x0, k0 print "SIZE %.02f %.02f" % (RR(log(abs(x0), 2)), RR(log(abs(k0), 2))) break BOUND1 = 10**7 BOUND2 = 10**7 MZ = matrix(ZZ, 2, 2, [ [1, -A], [0, Q], ]).LLL() DX1 = abs(MZ[0][0]) DX2 = abs(MZ[1][0]) print "STEP1" table = {} step = pow(G, DX2, P) curg = Y * inverse_mod( int(pow(step, BOUND1, P)), P ) % P cure = -BOUND1 for i in xrange(-BOUND1, BOUND1): if i % 100000 == 0: print i / 100000, "/", BOUND1 / 100000 assert curg not in table table[curg] = cure curg = (curg * step) % P cure += 1 print print "STEP2" step = pow(G, DX1, P) curg = pow(G, x0 - DX1 * BOUND2, P) cure = -BOUND2 for i in xrange(-BOUND2, BOUND2): if i % 100000 == 0: print i / 100000, "/", BOUND2 / 100000 if curg in table: print "Solved!", cure, table[curg] ans = x0 + cure * DX1 - table[curg] * DX2 print "Flag: CTF{%d}" % ans break curg = (curg * step) % P cure += 1 |
The flag: CTF{848525996645405165419773118980458599114509814}
1 ping
[…] Google CTF 2017 Quals – BLT (Bleichenbacher’s Lattice Task – Insanity Check) » […]