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

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 #!/usr/bin/python3import qrcode  # https://github.com/lincolnloop/python-qrcodeimport randomimport osfrom PIL import Imagefrom 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() Colored by Color Scripter cs

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.

 123456789101112131415161718192021222324252627282930313233343536373839 from mt import untemperimport randomfrom PIL import Image img = Image.open('share2.png')value = 0for 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 = valuevalues = []for i in range(444 * 444 // 32):    values.append(tmp & 0xffffffff)    tmp >>= 32 mt_state = tuple(list(map(untemper, values[:624])) + )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 = 0for i in range(444 * 444 // 32):    real_value ^= random.getrandbits(32) << (32 * i) value ^= real_valuearr = [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")Colored by Color Scripter cs

FlagBot

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.

 12345678910111213141516171819202122232425262728293031 cur_mod = 1cur_val = 0 for i in range(0, 7):    a = S[i]    b = S[i]    p = S[i]    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]    b = S[i]    p = S[i]    E = EllipticCurve(GF(p), [a, b])    RR = E(R_pub[i])    RES = RR * cur_val    print(RES.xy())Colored by Color Scripter cs

curve

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778 #!/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()  Colored by Color Scripter cs

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() * (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...

 123456789101112131415161718192021222324252627282930313233 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 curvefor 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 nonzeroG = G * (Ord // pr)G1 = GG2 = G ## this ends parameter generationColored by Color Scripter cs

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566 ## by rbtree from pwn import *import stringimport 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))        breakprint("PoW Done") p = 11572562087281212077294341316763410822093276559896892655806738743748493229131824454041157658617469079306138012813995393545636120267619633658087398895787057 a = 0b = 587626359248673832094266933340735482471140319598254235432650868938827936103013631493279303809976008538035914917596142929543705518144408460458007005924570pr = 97order = 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))conn.sendlineafter(b'Y1: ', str(Gs))conn.sendlineafter(b'X2: ', str(Gs))conn.sendlineafter(b'Y2: ', str(Gs)) print("Parameter Sent") for _ in range(30):    points = get_points()     for i in range(96):        if points == Gs[i]:            a = i + 1            break     for i in range(96):        if points == Gs[i]:            b = i + 1            break     to_send = 0 if Gs[(a * b % 97) - 1] == points else 1    conn.sendlineafter(b'Choice: ', str(to_send)) conn.interactive()Colored by Color Scripter cs

BabyProof

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 from hashlib import sha256 from Crypto.Util.number import getRandomRangefrom 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()Colored by Color Scripter cs

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.

 123456789101112131415161718192021 d = 60 ## get 60 instancesM = Matrix(ZZ, d+1, d+1)for i in range(0, d):    M[0, i] = cs[i]M[0, d] = 1for i in range(0, d):    M[i+1, i] = qs[i] Target =  * (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()Target = vector(Target)TT = Babai_closest_vector(M, GG, Target) x = TT[d]print(x)print(bytes.fromhex(hex(x)[2:])) cs

easyRSA?

 12345678910111213141516171819202122232425262728293031323334353637 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 * qe = 127 flag = b"N1CTF{************************************}"secret = np.array(list(flag)) upper = 152989197224467A = 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) Colored by Color Scripter cs

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.

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 ## Step 1 : Factorization of Nrat = 2 ** 1000 ## scaling : super large to force zero in the first column for i in range(0, 9):    M[i, 0] = (3 ** (66 * i)) * ratM[9, 0] = n * ratfor i in range(0, 9):    M[i, i+1] = 1 Target =  * 10for i in range(1, 10):    Target[i] = (2 ** 64) M = M.LLL()GG = M.gram_schmidt()Target = vector(Target)TT = Babai_closest_vector(M, GG, Target) P. = PolynomialRing(ZZ)f = 0for 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 = 0cc += 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.npyp = 122286683590821384708927559261006610931573935494533014267913695701452160518376584698853935842772049170451497q = 268599801432887942388349567231788231269064717981088022136662922349190872076740737541006100017108181256486533e = 127n = p * qphi = (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 CVPmod = 152989197224467 sel = 15 ## sel can be large as 127, but that's too slowM = 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] = 1for i in range(43, 43+sel):    M[i, i-43] = modTarget =  * (sel + 43)for i in range(0, sel):    Target[i] = cv[i] - 8for i in range(sel, sel + 43):    Target[i] = 80 ## printable Target = vector(Target)M = M.LLL()GG = M.gram_schmidt()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) Colored by Color Scripter cs

'수학 > 암호론 및 CTF' 카테고리의 다른 글

 TetCTF 2021 Crypto Writeups  (1) 2021.01.03 2020.12.07 2020.10.18 2020.10.18 2020.10.11 2020.09.30