Skip to content

Instantly share code, notes, and snippets.

@hellman
Last active June 19, 2017 09:34
Show Gist options
  • Save hellman/2077e291902e544ce05e63dce27f0213 to your computer and use it in GitHub Desktop.
Save hellman/2077e291902e544ce05e63dce27f0213 to your computer and use it in GitHub Desktop.
Google CTF 2017 Quals - Bleichenbacher’s Lattice Task - Insanity Check
# 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
/**
* 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());
}
}
Y:4675975961034321318962575265110114310875697301524971406479091223605006115642041321079605682629390144148862285125353335575850114862081357772478008490889403608973023515499959473374820321940514939155187478991555363073408293339373770407404120884229693036839637631846964085605936966005664594330150750220123106270473482589454510979171010750141467635389981140248292523060541588378749922037870081811431605806877184957731660006793364727129226828277168254826229733536459158767652636094988369367622055662565355698632032334469812735980006733267919815359221578068741143213061033728991446898051375393719722707555958912382769606279
P:32163437489387646882545837937802838313337646833974044466731567532754579958012875893665844191303548189492604123505522382770478442837553069890471993483164949504735527438665048438808440494922021062011062567528480025060283867381823427214512155583444236623145440836252289902783715682554658231606320310129833109191138313801289027627739243726679212643242494506530838323607821437997048235272405577079630284307474612832155381483129670050964475785090109743586694668757059662450206919471125303517989042945192886030308203029077484932328302318567286732217365609075794327329327141979774234522455646843538377559711464098301949684161
Q:81090202316656819994650163122592145880088893063907447574390172288558447451623
H:88030618649759997479497646248126770071813905558516408828543254210959719582166
R:34644971883866574753209424578777685962679178432833890467656897732184789528635
S:19288448359668464692653054736434794709227686774726460500150496018082350808676
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment