N1CTF 2020 Crypto Write-Ups

I participated in N1CTF as a member of Super Guesser. 4th Place :)

We solved all crypto problems, and it was a great collaboration of me and rbtree. 

The explanation will be very brief, because I don't have a lot of free time on my hands :( :(

VSS

#!/usr/bin/python3
import qrcode  # https://github.com/lincolnloop/python-qrcode
import random
import os
from PIL import Image
from flag import FLAG
 
 
def vss22_gen(img):
    m, n = img.size
    share1, share2 = Image.new("L", (2*m, 2*n)), Image.new("L", (2*m, 2*n))
    image_data = img.getdata()
    flipped_coins = [int(bit) for bit in bin(random.getrandbits(m*n))[2:].zfill(m*n)]
    for idx, pixel in enumerate(image_data):
        i, j = idx//n, idx % n
        color0 = 0 if flipped_coins[idx] else 255
        color1 = 255 if flipped_coins[idx] else 0
        if pixel:
            share1.putpixel((2*j, 2*i), color0)
            share1.putpixel((2*j, 2*i+1), color0)
            share1.putpixel((2*j+1, 2*i), color1)
            share1.putpixel((2*j+1, 2*i+1), color1)
 
            share2.putpixel((2*j, 2*i), color0)
            share2.putpixel((2*j, 2*i+1), color0)
            share2.putpixel((2*j+1, 2*i), color1)
            share2.putpixel((2*j+1, 2*i+1), color1)
        else:
            share1.putpixel((2*j, 2*i), color0)
            share1.putpixel((2*j, 2*i+1), color0)
            share1.putpixel((2*j+1, 2*i), color1)
            share1.putpixel((2*j+1, 2*i+1), color1)
 
            share2.putpixel((2*j, 2*i), color1)
            share2.putpixel((2*j, 2*i+1), color1)
            share2.putpixel((2*j+1, 2*i), color0)
            share2.putpixel((2*j+1, 2*i+1), color0)
    share1.save('share1.png')
    share2.save('share2.png')
 
 
def vss22_superposition():
    share1 = Image.open('share1.png')
    share2 = Image.open('share2.png')
    res = Image.new("L", share1.size, 255)
    share1_data = share1.getdata()
    share2_data = share2.getdata()
    res.putdata([p1 & p2 for p1, p2 in zip(share1_data, share2_data)])
    res.save('result.png')
 
 
def main():
    qr = qrcode.QRCode(
        version=1,
        error_correction=qrcode.constants.ERROR_CORRECT_L,
        box_size=12,
        border=4,
    )
    qr.add_data(FLAG)
    qr.make(fit=True)
    img = qr.make_image(fill_color="black", back_color="white")
    vss22_gen(img._img)
    img.save('res.png')
    vss22_superposition()
 
 
if __name__ == '__main__':
    main()
 

The vulnerability lies in the use of "getrandbits" - it's implemented using MT19937. This PRNG is known to be predictable after 624 output values are known. Also, if you try to generate a QR code with a sample flag, we can see that the first few rows of the generated output are all white. With this fact, we can retrieve the first few thousand bits generated, and we can predict the following bits generated by MT19937. Therefore, we can recover the original QR code. This solution (and code itself) is due to rbtree. 

from mt import untemper
import random
from PIL import Image
 
img = Image.open('share2.png')
value = 0
for i in range(444):
    for j in range(444):
        value <<= 1
        value ^= 1 if 255 == img.getpixel((2 * j + 1, 2 * i)) else 0
 
tmp = value
values = []
for i in range(444 * 444 // 32):
    values.append(tmp & 0xffffffff)
    tmp >>= 32
 
mt_state = tuple(list(map(untemper, values[:624])) + [0])
random.setstate((3, mt_state, None))
 
# for i in range(444 * 444 // 32):
#     assert values[i] == random.getrandbits(32)
 
random.setstate((3, mt_state, None))
 
real_value = 0
for i in range(444 * 444 // 32):
    real_value ^= random.getrandbits(32) << (32 * i)
 
value ^= real_value
arr = [int(bit) for bit in bin(value)[2:].zfill(444 * 444)]
 
res = Image.new("L", (444, 444))
 
for i in range(444):
    for j in range(444):
        res.putpixel((j, i), 0 if arr[i * 444 + j] else 255)
    
res.save("res.png")

FlagBot

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
import base64
from secret import flag
 
RECEIVER_NUM = 7
 
def generate_safecurve():
    while True:
        p = random_prime(2 ^ 256-1, False, 2 ^ 255)
        a = randint(-p, p)
        b = randint(-p, p)
 
        if 4*a^3 + 27*b^2 == 0:
            continue
 
        E = EllipticCurve(GF(p), [a, b])
 
        fac = list(factor(E.order()))
 
        # Prevent rho method
        if fac[-1][0] < 1 << 80:
            continue
 
        # Prevent transfer
        for k in range(1, 20):
            if (p ^ k - 1) % fac[-1][0] == 0:
                break
        else:
            return E
 
class Sender:
    def __init__(self, curves, receivers):
        self.secret = randint(1 << 254, 1 << 255)
        self.curves = curves
        self.receivers = receivers
        self.shared_secrets = [None for _ in range(len(receivers))]
 
    def setup_connections(self):
        for idx, receiver in enumerate(self.receivers):
            curve = self.curves[idx]
            print(f"curves[{idx}] : {curve}")
            g = self.curves[idx].gens()[0]
            print(f"g[{idx}] = {g.xy()}")
            receiver.set_curve(curve, g)
            public = self.secret * g
            print(f"S_pub[{idx}] = {public.xy()}")
            yours = receiver.key_exchange(public)
            print(f"R_pub[{idx}] = {yours.xy()}")
            self.shared_secrets[idx] = yours * self.secret
 
    def send_secret(self):
        msg = b'Hi, here is your flag: ' + flag
        for idx, receiver in enumerate(self.receivers):
            px = self.shared_secrets[idx].xy()[0]
            _hash = sha256(long_to_bytes(px)).digest()
            key = _hash[:16]
            iv = _hash[16:]
            encrypted_msg = base64.b64encode(AES.new(key, AES.MODE_CBC, iv).encrypt(pad(msg, 16)))
            print(f"encrypted_msg[{idx}] = {encrypted_msg}")
            receiver.receive(encrypted_msg)
 
 
class Receiver:
    def __init__(self):
        self.secret = randint(1 << 254, 1 << 255)
        self.curve = None
        self.g = None
        self.shared_secret = None
 
    def set_curve(self, curve, g):
        self.curve = curve
        self.g = g
 
    def key_exchange(self, yours):
        self.shared_secret = yours * self.secret
        return self.g * self.secret
 
    def receive(self, encrypted_msg):
        px = self.shared_secret.xy()[0]
        _hash = sha256(long_to_bytes(px)).digest()
        key = _hash[:16]
        iv = _hash[16:]
        msg = AES.new(key, AES.MODE_CBC, iv).decrypt(base64.b64decode(encrypted_msg))
        msg = unpad(msg, 16)
        assert msg.startswith(b'Hi, here is your flag: ')
 
 
receivers = [Receiver() for _ in range(RECEIVER_NUM)]
curves = [generate_safecurve() for _ in range(RECEIVER_NUM)]
 
A = Sender(curves, receivers)
A.setup_connections()
A.send_secret()
 

This problem was solved by me, so I can give you a brief look inside my brain.

• You can't really do anything with AES-CBC in this challenge
• You can't really do anything with SHA256 anywhere
• That means that we have to break the DH style shared secret generation
• The secret key is reused every time, so that's the vulnerability
• The curve generation only checks the existence of large primes, so small primes can exist

At this point, the solution was straightforward. For each small prime $p$ that divides the order of the elliptic curve used, we can find the value of the secret key $\pmod{p}$ by using Pohlig-Hellman approach. Combining these with CRT, we can recover $d$ since it is at most $2^{255}$. 

Since we do need to deal with primes of size around $10^{12}$, Baby-Step-Giant-Step is required. Just use Sage.

The below code finds all the shared secrets. The remaining parts of the problem are straightforward.

cur_mod = 1
cur_val = 0
 
for i in range(0, 7):
    a = S[i][0]
    b = S[i][1]
    p = S[i][2]
    E = EllipticCurve(GF(p), [a, b])
    Ord = E.order()
    L = list(factor(Ord))
    GG = E(g[i])
    SS = E(S_pub[i])
    for pp, dd in L:
        if pp <= 10 ** 12 and dd == 1:
            Gp = (Ord // pp) * GG
            Sp = (Ord // pp) * SS
            tt = discrete_log(Sp, Gp, operation='+')
            cur_val = crt(cur_val, tt, cur_mod, pp)
            cur_mod = (cur_mod * pp) // gcd(pp, cur_mod)
    print("Done ", i)
    
print("[+] Secret: ", cur_val)
 
for i in range(0, 7):
    a = S[i][0]
    b = S[i][1]
    p = S[i][2]
    E = EllipticCurve(GF(p), [a, b])
    RR = E(R_pub[i])
    RES = RR * cur_val
    print(RES.xy()[0])

curve

#!/usr/bin/env sage
 
import signal, hashlib, string, random, os 
 
os.chdir(os.path.dirname(os.path.abspath(__file__)))
FLAG = open("./flag.txt", 'r').read()
ROUNDS = 30
 
def PoW():
  s = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
  h = hashlib.sha256(s.encode()).hexdigest()
  prefix = s[:16]
  print("sha256(%s+XXXX) == %s" % (prefix, h))
  c = input("Give me XXXX: ")
  if hashlib.sha256((prefix + c).encode()).hexdigest() == h:
    return True 
  return False
 
def chall():
  p = ZZ(input("P: "))  # of course we are using sage >= 9
  a = ZZ(input("A: "))
  b = ZZ(input("B: "))
 
  if not is_prime(p) or p.nbits() < 512:
    print("No bad parameters.")
    return
 
  E = EllipticCurve(GF(p), [a, b])
  if E.is_supersingular():
    print("No this is not good enough.")
    return
 
  q = E.order()
  x1 = ZZ(input("X1: "))
  y1 = ZZ(input("Y1: "))
  x2 = ZZ(input("X2: "))
  y2 = ZZ(input("Y2: "))
  G1 = E((x1, y1))
  G2 = E((x2, y2))
 
  for _ in range(ROUNDS):
    a0 = randint(1, q - 1)
    a1 = randint(1, q - 1)
 
    c = -1
    while c == -1 or c == a0 * a1:
      c = randint(1, q - 1)
 
    g0, g1 = G1 * a0, G2 * a1 
    c0, c1 = G1 * (a0 * a1), G1 * c
    b = randint(0, 1)
 
    if b == 0:
      print(g0, g1, c0)
    else:
      print(g0, g1, c1)
 
    choice = ZZ(input("Choice: "))
    if choice != b:
      print("Wrong choice.")
      return
 
  print(f"Thank you! Here's your reward: {FLAG}")
  return 
 
if __name__ == '__main__':
  if not PoW():
    print("Invalid PoW.")
    exit()
  signal.alarm(90)
 
  try:
    chall()
  except:
    print("oof...")
    exit()
 
 

We struggled greatly on this challenge, despite finding the solution quite immediately. Here's the process.

• $E$ is a large elliptic curve over a prime field, not supersingular
• We select two points $G_1, G_2$ on the curve, and play a sort of Decisional Diffie-Hellman game.
• Let's just fix $G = G_1 = G_2$ and see what we can do!
• If the order of $G$ is small, say $t$ - we can recover $a_0, a_1 \pmod{t}$ easily. 
• Therefore, we can directly calculate $a_0a_1G$ as well!
• Check if this is equal to the third point given. If so, check $b=0$ and otherwise check $b=1$.

Now we do some analysis. 

• If $b=0$ was chosen, this will give the correct answer with probability 1
• If $b=1$ was chosen, we fail if $c \equiv a_0 a_1 \pmod{t}$, so we succeed with probability $1-1/t$
• We do $30$ rounds, so $t$ shouldn't be too small (we want, say, $t> 50$)
• Obviously we do need to solve the discrete logarithm on a group of order $t$, so we want small $t$

This leads to the following goal.

• Find an elliptic curve that satisfies the server's desired conditions, with the order of the curve having a prime between $50$ and $400$

I think I took about 5 minutes until here, but the journey towards the flag for several reasons.

• First, my initial code used random $p, a, b$, generate the curve, find the order, then check for small primes.
• Seems good right? However, I tried to find $G$ using E.gens()[0] * (Order // small_prime)
• This obviously takes infinite time, and my computer was on the verge of dying because of it
• I realized the problem and replaced it by generating any point with Tonelli-Shanks and multiplying it by Order // small_prime

So I thought I was done here. After sending the parameters, I realized that I was not done here. Why?

• The server calculates the order of the elliptic curve as well
• While order calculation is done in polynomial time, it's still slow with 512 bit curve parameters
• Therefore, the server times out, and I can't solve the problem

So I thought I was done here, in a different meaning. After solving the remaining challs, I tried the following.

• Simply try the curves of the form $y^2 = x^3 + b$.

This worked, as the order calculation was done much faster. The challenge was solved.

The parameter finding and solution finding was done by me, and the programming was done by rbtree.

I learned a lot from solving this problem :) I'm still inexperienced, lots of studying to do... 

pr = []
for x in range(50, 200):
    if x in Primes():
        pr.append(x)
while True:
    p = random_prime(2 ** 512, False, 2 ** 511)
    if p % 3 == 2: ## in this case, y^2 = x^3 + b is guaranteed to be supersingular
        continue
    d = randint(1, p-1)
    E = EllipticCurve(GF(p), [0, d])
    if E.is_supersingular() == True:
        continue
    print(p)
    L = E.order()
    for cc in pr:
        if L % cc == 0:
            print(p, d, cc, L)
            break
 
## find any point on the elliptic curve
for u in range(1, 100):
    goal = (u ** 3 + a * u + b) % p
    if pow(goal, (p-1) // 2, p) == 1:
        v = tonelli(goal, p) ## sqrt, so you can directly use sage
        G = E(u, v)
        break
 
## hope that G is nonzero
G = G * (Ord // pr)
G1 = G
G2 = G
 
## this ends parameter generation

## by rbtree
 
from pwn import *
import string
import itertools
 
conn = remote('47.242.140.57', 9998)
conn.settimeout(None)
 
# PoW
 
challenge = conn.recvline().strip()
print(challenge)
prefix = challenge[7:7+16]
h = challenge.split()[-1]
charset = (string.ascii_letters + string.digits).encode()
for suffix in itertools.product(charset, repeat=4):
    if hashlib.sha256(prefix+bytes(suffix)).hexdigest() == h.decode():
        conn.sendlineafter(b'Give me XXXX: ', bytes(suffix))
        break
print("PoW Done")
 
p = 11572562087281212077294341316763410822093276559896892655806738743748493229131824454041157658617469079306138012813995393545636120267619633658087398895787057 
a = 0
b = 587626359248673832094266933340735482471140319598254235432650868938827936103013631493279303809976008538035914917596142929543705518144408460458007005924570
pr = 97
order = 11572562087281212077294341316763410822093276559896892655806738743748493229131918957581964494921602014693617723606720177358361724985583223555103419211299648
 
Gs = [] ## bunch of points (G, 2G, ... 97G)
print(len(Gs))
 
def get_points():
    points_s = conn.recvline().decode().strip()[1:-1].split(') (')
    points = []
    for point_s in points_s:
        point = tuple(int(v.strip()) for v in point_s.split(':')[:2])
        points.append(point)
    return points
 
conn.sendlineafter(b'P: ', str(p))
conn.sendlineafter(b'A: ', str(a))
conn.sendlineafter(b'B: ', str(b))
conn.sendlineafter(b'X1: ', str(Gs[0][0]))
conn.sendlineafter(b'Y1: ', str(Gs[0][1]))
conn.sendlineafter(b'X2: ', str(Gs[0][0]))
conn.sendlineafter(b'Y2: ', str(Gs[0][1]))
 
print("Parameter Sent")
 
for _ in range(30):
    points = get_points()
 
    for i in range(96):
        if points[0] == Gs[i]:
            a = i + 1
            break
 
    for i in range(96):
        if points[1] == Gs[i]:
            b = i + 1
            break
 
    to_send = 0 if Gs[(a * b % 97) - 1] == points[2] else 1
    conn.sendlineafter(b'Choice: ', str(to_send))
 
conn.interactive()

BabyProof

from hashlib import sha256
 
from Crypto.Util.number import getRandomRange
from Crypto.PublicKey import DSA
 
from secret import proof_of_work, flag
 
 
x = int.from_bytes(flag, 'big')
assert x.bit_length() == 247
 
 
def baby_proof():
    key = DSA.generate(3072)  # It takes time to generate, plz be patient...
    p, q, g = key.domain()
    y = pow(g, x, p)
 
    v = getRandomRange(1, x)
    t = pow(g, v, p)
 
    gyt = b"".join(
        map(
            lambda x: int.to_bytes(len(str(x)), 4, 'big') + str(x).encode(),
            (g, y, t)
        ))
    c = int.from_bytes(sha256(gyt).digest(), 'big')
    r = (v - c*x) % q
 
    print("I want to prove to you that I am in the knowledge of the discrete "
          "logarithm x that satisfies g^x = y modulo p, with the order of g "
          "modulo p being q.")
    print("However, I don't want to leak any information about x.")
    print("So, I use a non-interactive zero-knowledge proof for my purpose.")
    print("=================================================================")
    print("Here is my proof: ")
    print("Firstly, I choose a random (secret) v and compute t = g^v in Zq.")
    print("Secondly, I compute c = SHA256(g, y, t).")
    print("Then, I compute r = v - cx modulo q.")
    print("Finally, I will send you my proof (t, r).")
    print("You can check it by determining whether t == g^r * y^c or not.")
    print("Since there's negligible probability that I could forge the value "
          "r, you should believe that I really have knowledge of x.")
    print(g, y, p, q, t, r, sep="\n")
 
 
if __name__ == "__main__":
    if proof_of_work():
        baby_proof()

The key here is that $x$ is quite small compared to $2^{256}$, and $v$ is selected in $[1, x]$. 

Given the printed parameters, we can directly obtain the value of $c$ as well. We see that $$ cx \equiv v - r \pmod{q}, \quad 1 \le v \le x $$ Since $x$'s bit length is $247$, we get $1 \le v \le 2^{247}$ and can write something like $$ cx \pmod{q} \approx -r + 2^{246} \pmod{q} $$ This is an instance of Hidden Number Problem, so just gather a lot of these information and solve it.

d = 60 ## get 60 instances
M = Matrix(ZZ, d+1, d+1)
for i in range(0, d):
    M[0, i] = cs[i]
M[0, d] = 1
for i in range(0, d):
    M[i+1, i] = qs[i]
 
Target = [0] * (d+1)
for i in range(0, d):
    Target[i] = (2 ** 246) - rs[i]
Target[d] = (2 ** 246)
 
M = M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
 
x = TT[d]
print(x)
print(bytes.fromhex(hex(x)[2:]))

easyRSA?

from Crypto.Util.number import *
import numpy as np
 
mark = 3**66
 
def get_random_prime():
    total = 0
    for i in range(5):
        total += mark**i * getRandomNBitInteger(32)
    fac = str(factor(total)).split(" * ")
    return int(fac[-1])
 
def get_B(size):
    x = np.random.normal(0, 16, size)
    return np.rint(x)
 
p = get_random_prime()
q = get_random_prime()
N = p * q
e = 127
 
flag = b"N1CTF{************************************}"
secret = np.array(list(flag))
 
upper = 152989197224467
A = np.random.randint(281474976710655, size=(e, 43))
B = get_B(size=e).astype(np.int64)
linear = (A.dot(secret) + B) % upper
 
result = []
for l in linear:
    result.append(pow(l, e, N))
 
print(result)
print(N)
np.save("A.npy", A)
 

Looking at the problem, we see that we need to do the following

• Factorize $N$ using the vulnerable random prime generator, and recover the array "linear"
• Solve the instance of LWE by using the fact that secret vector (the flag) is small as well

We first focus on the first part. I actually thought about coppersmith method, but I couldn't get it to work.

I already have an experience in wasting time with coppersmith approach, (sharsable) so I stopped attempting.

rbtree noted that there is a polynomial $f$ with small coefficients, degree 8, and $f(3^{66}) \equiv 0 \pmod{N}$.

This is because for each $p, q$, there's a degree 4 polynomial with small coefficients that vanishes at $3^{66}$ modulo that prime.

If we multiply the two degree 4 polynomials, we arrive at the described polynomial of degree 8.

He then suggested using a lattice to find this polynomial. This was an excellent idea!

Since we want a small-coefficient-linear-combination of $3^{66 \cdot 0}, 3^{66 \cdot 1}, \cdots , 3^{66 \cdot 8}$ that vanishes to zero, we must use scaling, as I did in sharsable. Check the code for technical details. As I do usually, I used Babai's closest vector algorithm. We can expect $f$ to be factorized into two polynomials of degree 4. By calculating each polynomial at $3^{66}$ and taking GCDs, we can retrieve $p, q$. This completes Part 1. 

For Part 2, we need to solve the LWE problem. This is hard in general, but we know that the secret vector is small as well. 

Of course, LWE problem can be modeled as CVP problem, and we use the "secret vector is small" fact here as well.

## Step 1 : Factorization of N
rat = 2 ** 1000 
## scaling : super large to force zero in the first column
 
for i in range(0, 9):
    M[i, 0] = (3 ** (66 * i)) * rat
M[9, 0] = n * rat
for i in range(0, 9):
    M[i, i+1] = 1
 
Target = [0] * 10
for i in range(1, 10):
    Target[i] = (2 ** 64)
 
M = M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
 
P.<x> = PolynomialRing(ZZ)
f = 0
for i in range(1, 10):
    f = f + TT[i] * x^(i-1)
print(f.factor())
## (2187594805*x^4 + 2330453070*x^3 + 2454571743*x^2 + 2172951063*x + 3997404950) 
## (3053645990*x^4 + 3025986779*x^3 + 2956649421*x^2 + 3181401791*x + 4085160459)
 
cc = 0
cc += 2187594805 * (3 ** (66 * 4))
cc += 2330453070 * (3 ** (66 * 3))
cc += 2454571743 * (3 ** (66 * 2))
cc += 2172951063 * (3 ** (66 * 1))
cc += 3997404950 * (3 ** (66 * 0))
 
p = gcd(cc, n)
print(p)
print(n // p)
print(n % p)
 
## Step 2 : housekeeping stuff
## res in res.txt, A in A.npy
p = 122286683590821384708927559261006610931573935494533014267913695701452160518376584698853935842772049170451497
q = 268599801432887942388349567231788231269064717981088022136662922349190872076740737541006100017108181256486533
e = 127
n = p * q
phi = (p-1) * (q-1)
d = inverse(e, phi)
 
cv = []
for x in res:
    cv.append(pow(x, d, n))
 
print(cv)
 
np.set_printoptions(threshold=sys.maxsize)
A = np.load("A.npy")
A = np.ndarray.tolist(A)
print(A)
 
## Step 3 : LWE with CVP
mod = 152989197224467
 
sel = 15 ## sel can be large as 127, but that's too slow
M = Matrix(ZZ, sel + 43, sel + 43)
for i in range(0, 43):
    for j in range(0, sel):
        M[i, j] = A[j][i]
    M[i, sel + i] = 1
for i in range(43, 43+sel):
    M[i, i-43] = mod
Target = [0] * (sel + 43)
for i in range(0, sel):
    Target[i] = cv[i] - 8
for i in range(sel, sel + 43):
    Target[i] = 80 ## printable
 
Target = vector(Target)
M = M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
 
print(TT)
 
res = ""
for i in range(sel, sel+43):
    res += chr(TT[i])
 
print(res)