Google CTF 2017 Quals - Bleichenbacher’s Lattice Task - Insanity Check

dsa_small_secrets.py

# writeup at http://mslc.ctf.su/wp/gctf2017quals-insanity-check/

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

Flag.java

/**
 * Print a Flag.
 * @author Daniel Bleichenbacher
 */
package blt;

import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.SecureRandom;
import java.security.GeneralSecurityException;

public class Flag {

  // 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;
      }
    }
  }

  private static BigInteger hashMessage(byte[] message) throws Exception {
    byte[] digest = MessageDigest.getInstance("SHA-256").digest(message);
    return new BigInteger(1, digest);
  }

  private static BigInteger[] sign(
      byte[] message,
      BigInteger p,
      BigInteger q,
      BigInteger g,
      BigInteger x) throws Exception {
    while (true) {
      BigInteger h = hashMessage(message);
      BigInteger k = generateSecret(q);
      BigInteger r = g.modPow(k, p).mod(q);
      BigInteger s = k.modInverse(q).multiply(h.add(x.multiply(r))).mod(q);
      if (r.equals(BigInteger.ZERO) || s.equals(BigInteger.ZERO)) continue;
      return new BigInteger[]{r,s};
    }
  }

 /**
  * This code generates a flag.
  */
  public static void main(String[] args) throws Exception {
    // p is a 2048 bit prime number.
    BigInteger p = new BigInteger(args[0]);
    // q is a 256-bit prime number that divides p-1.
    BigInteger q = new BigInteger(args[1]);
    // g is a generator of order q. (I.e. 1 = g**q mod p)
    BigInteger g = new BigInteger("2").modPow(p.divide(q), p);
    // generate the private key
    BigInteger x = generateSecret(q);
    BigInteger y = g.modPow(x, p);
    System.out.println("Y:" + y.toString());
    System.out.println("P:" + p.toString());
    System.out.println("Q:" + q.toString());
    byte[] message = ("CTF{" + x.toString() + "}").getBytes();
    System.err.println("Flag: " + new String(message));
    System.out.println("H:" + hashMessage(message).toString());
    BigInteger[] sig = sign(message, p, q, g, x);
    System.out.println("R:" + sig[0].toString());
    System.out.println("S:" + sig[1].toString());
  }
}

STDOUT

Y:4675975961034321318962575265110114310875697301524971406479091223605006115642041321079605682629390144148862285125353335575850114862081357772478008490889403608973023515499959473374820321940514939155187478991555363073408293339373770407404120884229693036839637631846964085605936966005664594330150750220123106270473482589454510979171010750141467635389981140248292523060541588378749922037870081811431605806877184957731660006793364727129226828277168254826229733536459158767652636094988369367622055662565355698632032334469812735980006733267919815359221578068741143213061033728991446898051375393719722707555958912382769606279
P:32163437489387646882545837937802838313337646833974044466731567532754579958012875893665844191303548189492604123505522382770478442837553069890471993483164949504735527438665048438808440494922021062011062567528480025060283867381823427214512155583444236623145440836252289902783715682554658231606320310129833109191138313801289027627739243726679212643242494506530838323607821437997048235272405577079630284307474612832155381483129670050964475785090109743586694668757059662450206919471125303517989042945192886030308203029077484932328302318567286732217365609075794327329327141979774234522455646843538377559711464098301949684161
Q:81090202316656819994650163122592145880088893063907447574390172288558447451623
H:88030618649759997479497646248126770071813905558516408828543254210959719582166
R:34644971883866574753209424578777685962679178432833890467656897732184789528635
S:19288448359668464692653054736434794709227686774726460500150496018082350808676