#### corCTF 2021 - Crypto Challenge Writeups

• Author: qopruzjf, quintec, willwam845
• Date:

# fibinary

### Author: Quintec

fibinary was a simple encoding challenge where each character was encoded in “base Fibonacci” - a binary number where each successive place value represented the next Fibonacci number. For example, 110100 would represent 8 + 5 + 0 + 3 + 0 + 0 = 16. To decode, we simply do the reverse of encoding, and add together the Fibonacci numbers indicated by the 1s in the binary representation. Here was my solve script:

 1fib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89][::-1]
2
3with open('flag.enc', 'r') as f:
5
6for tok in toks:
7	n = 0
8	for i in range(len(tok)):
9		if tok[i] == '1':
10			n += fib[i]
11	print(chr(n), end='')
12print()


# 4096

## Challenge

I heard 4096 bit RSA is secure, so I encrypted the flag with it.

## Solution

Let’s take a look at source.py.

 1from Crypto.Util.number import getPrime, bytes_to_long
2from private import flag
3
4def prod(lst):
5	ret = 1
6	for num in lst:
7		ret *= num
8	return ret
9
10m = bytes_to_long(flag)
11primes = [getPrime(32) for _ in range(128)]
12n = prod(primes)
13e = 65537
14print(n)
15print(pow(m, e, n))


So, 128 32-bit primes were generated and multiplied together to produce the modulus for RSA encryption. Since 32-bits is small, we can just factor n using sage, and the likelihood that all the primes are unique is high(there are many 32-bit primes), so we can just calculate phi(n) as the product of p_i - 1 for the primes p_i. Alternatively, just use sage’s totient function. Then, decryption is the usual. I suggest people who aren’t familiar with RSA that uses an arbitrary number of primes look into the actual math behind why it still works.

Here’s the solve script:

 1from Crypto.Util.number import long_to_bytes
2n = 459885975247015080805640556741011516977197329640766993963868420109797926433366540892987268841395390677003815083264385212101691633439322325099797177448692622480464621078335184219389796838162276766514601933466475468401515898684493274917613994100522239975168457673847893881262044268360912988376575672476171112591298760495756557513258957047691316107068789781127778556052622156938314563686550649890013123308529462323524956343976590389389598189062535997792610595692423958859734240408888038654268044525127233802930885203114382004407420679618854820752321423652210263026002674421004459358125628893165197704730466465357733250277754582116729335454780585183881507464319371872816864390937163980938342321213464267167886221361565606170274949413010811340309217975928566961337873662243232735415505259424592138609448552846032645740285154650705912665026491380837092800272560626482253083963281523307784385386183075753783677135489658756755609520313684847611300385005067351044518651327694437586779518531321476281945821098370942775037752436793514318106103039341369024642099069559532445745414503597893184762282819390252433279093193434255143378230817111136472977731464704181932470261447745719555587426871560009788187914276773536835263029421459
3c = 28755115299447380219865175141510816277127168995053017865115990550984575125799683185050702823351567348600828299072471787373507105523347305190934990188579267752586087083593225747175981684997138309755745359524509032537903919777044868871605615082163195170687980598583706842782998787213163456976487674758299135192443422599601908006134268958490155310804660685217691260626978944786030603741681463537491343107154880830022752091923044127859420510244685212654149762222514692807085300768408438515214359180426754805425610056804647793212776220975050809958444765557485627572244455567542349113285436767315494336729564478949697782757093180889501388671840393906428863764844923821078129810082488811253658252080197407107745563251321553018503591423447398679152763318675601718545686288006911301792697520238398588188160613822537782998910198317606647548568160063550153871090661536552353526398962780934555640261433391205589034576219843858289208904106775652085670099705038854877624295738691647401202134659947562445654410163435449737035924690998038213621986164097914575256877909759645573588363096065366890651919757816350994847106221042650232103061907896322357719105163758442738521889967022959871387866183293407447159616199193109243274307191759
4
5def prod(lst):
6	ret = 1
7	for num in lst:
8		ret *= num
9	return ret
10
11fs = ecm.factor(n)
12fs = [p - 1 for p in fs]
13phi = prod(fs)
14e = 65537
15d = pow(e, -1, phi)
16print(long_to_bytes(pow(c, d, n)))


corctf{to0_m4ny_pr1m3s55_63aeea37a6b3b22f}

By the way, the modulus was not actually 4096 bits, but 4042 bits.

# dividing_secrets

## Challenge

I won’t give you the secret. But, I’ll let you divide it.

nc crypto.be.ax 6000

## Solution

Let’s take a look at the provided server.py.

 1from Crypto.Util.number import bytes_to_long, getStrongPrime
2from random import randrange
3from secret import flag
4
5LIMIT = 64
6
7def gen():
8	p = getStrongPrime(512)
9	g = randrange(1, p)
10	return g, p
11
12def main():
13	g, p = gen()
14	print("g:", str(g))
15	print("p:", str(p))
16	x = bytes_to_long(flag)
17	enc = pow(g, x, p)
18	print("encrypted flag:", str(enc))
19	ctr = 0
20	while ctr < LIMIT:
21		try:
22			div = int(input("give me a number> "))
23			print(pow(g, x // div, p))
24			ctr += 1
25		except:
26			print("whoops..")
27			return
28	print("no more tries left... bye")
29
30main()


We are given 64 queries where we can send to the server div, and the server will give us g^(flag // div) mod p. We want to somehow leak the flag. I started off by considering how we can leak the last bit of (flag // div), as if we can do that, we have a bit-by-bit leak to retrieve the flag by simply dividing by increasing powers of 2(same as pythons’ » operation).

My idea for the leak relies on finding the Legendre Symbol for a number, which you can read about here. I will use the notation (a | b) to refer to this. In particular, under certain conditions, we can find the legendre symbol ((g^(flag // div)) | p) and use it to deduce the last bit of (flag // div). First, let’s start with the assumption that g is not a quadratic residue, i.e. (g | p) = -1. Then, if we write k = (flag // div), consider the following cases:

• If k is odd, then the legendre symbol ((g^k) | p), calculated by Euler’s criterion, is (g^k)^((p-1)/2) = (g^((p-1)/2))^k = (-1)^k = -1 mod p. So, g^k will not be a quadratic residue either.

• If k is even, then we have (g^k)^((p-1)/2) = (g^((p-1)/2))^k = (-1)^k = 1 mod p. So, it will be a quadratic residue.

So, we can calculate the legendre symbol ((g^(flag // div)) | p) to leak the last bit of (flag // div). And as previously described, by sending div as increasing powers of 2, we can leak the bits of the flag until corctf appears in the bytes. Note that the 64 query limit is a bait and does not actually matter for this method(and likely some other ones), as the flag is invariable across the connections. We can just reconnect until we get g that is not a quadratic residue mod p, then leak 64 bits, and repeat.

Here is my implementation of the attack:

 1from pwn import *
2from Crypto.Util.number import long_to_bytes
3
4LIMIT = 64
5host, port = 'crypto.be.ax' , 6000
6
7def get_params(r):
8	r.recvuntil(b'g: ')
9	g = int(r.recvline())
10	r.recvuntil(b'p: ')
11	p = int(r.recvline())
12	return g, p
13
14div = 1
15flag_bits = ''
16while True:
17	r = remote(host, port)
18	g, p = get_params(r)
19	while pow(g, (p-1) // 2, p) == 1:
20		r.close()
21		r = remote(host, port)
22		g, p = get_params(r)
23	for _ in range(LIMIT):
24		r.recvuntil(b'give me a number> ')
25		r.sendline(str(div).encode())
26		res = int(r.recvline())
27		if pow(res, (p-1) // 2, p) == 1:
28			flag_bits = '0' + flag_bits
29		else:
30			flag_bits = '1' + flag_bits
31		div *= 2
32		cur = long_to_bytes(int(flag_bits, 2))
33		if b'corctf' in cur:
34			print(cur)
35			r.close()
36			exit()
37	r.close()


corctf{qu4drat1c_r3s1due_0r_n0t_1s_7h3_qu3st1on8852042051e57492}

# supercomputer

### Author: Quintec

supercomputer was a challenge about a seemingly impossible math computation involving taking powers of massive 2048 bit numbers, and then taking powers of those numbers. In the end, it reduced to finding the number of powers of p that divided into a massive final number t.

 1from Crypto.Util.number import getPrime, long_to_bytes
2from pwn import *
3import random, binascii
4
6
7def v(p, k):
8	ans = 0
9	while k % p == 0:
10		k /= p
11		ans += 1
12	return ans
13
14p, q, r = getPrime(2048), getPrime(2048), getPrime(2048)
15print(p, q, r)
16n = pow(p, q) * r
17
18a1 = random.randint(0, n)
19a2 = n - a1
20assert a1 % p != 0 and a2 % p != 0
21
22t = pow(a1, n) + pow(a2, n)
23print(binascii.hexlify(xor(flag, long_to_bytes(v(p, t)))))


There were many interesting ways to do this problem, but I’ll cover the most direct - the Lifting the Exponent (LTE) lemma. You can read a more detailed explanation on how it works and a proof of it (involving binomial expansions, another popular way to solve this challenge) in this PDF.

In summary, what this lemma says is, for our function $v_p$ (v with prime p),

$$v_p(x^n+y^n) = v_p(x + y) + v_p(n)$$​

Using this on t, we get

\begin{align*} v_p(t) = v_p(a_1^n + a_2^n) &= v_p(a_1 + a_2) + v_p(n) \\ &= v_p(n) + v_p(n) \\ &= q + q \\ &= 2q\end{align*}

Therefore, v(p, t) is $2q$ and we can plug that into the xor to recover our flag.

# babyrsa

### Author: willwam845

discord is the best place to store secrets

babyrsa.png

script.py

 1from Crypto.Util.number import bytes_to_long
2
3n = 73542616560647877565544036788738025202939381425158737721544398356851787401183516163221837013929559568993844046804187977705376289108065126883603562904941748653607836358267359664041064708762154474786168204628181667371305788303624396903323216279110685399145476916585122917284319282272004045859138239853037072761
4e = 0x10001
6
7print(f"n = {n}")
8print(f"e = {e}")
9print(f"ct = {pow(flag, e, n)}")
10print("""
11Transcription of image:
12735426165606478775655440367887380252029393814251587377215443983568517874011835161632
13289108065126883603562904941748653607836358267359664041064708762154474786168204628181
149145476916585122917284319282272004045859138239853037072761
15108294440701045353595867242719660522374526250640690193563048263854806748525172379331
16341078269246532299656864881223
17679098724593514422867704492870375465007225641192338424726642090768164214390632598250
1839563231146143146482074105407
19(n, p, q)
20""")


output.txt

﻿n = 73542616560647877565544036788738025202939381425158737721544398356851787401183516163221837013929559568993844046804187977705376289108065126883603562904941748653607836358267359664041064708762154474786168204628181667371305788303624396903323216279110685399145476916585122917284319282272004045859138239853037072761
e = 65537
ct = 2657054880167593054409755786316190176139048369036893368834913798649283717358246457720021168590230987384201961744917278479195838455294205306264398417522071058105245210332964380113841646083317786151272874874267948107036095666198197073147087762030842808562672646078089825632314457231611278451324232095496184838

Transcription of image:
735426165606478775655440367887380252029393814251587377215443983568517874011835161632
289108065126883603562904941748653607836358267359664041064708762154474786168204628181
9145476916585122917284319282272004045859138239853037072761
108294440701045353595867242719660522374526250640690193563048263854806748525172379331
341078269246532299656864881223
679098724593514422867704492870375465007225641192338424726642090768164214390632598250
39563231146143146482074105407

(n, p, q)


We get partial information on the decimal digits of the primes $p$ and $q$ which make up $n$. Doing a bit of testing by using the full value of $n$, along with the value in the image, we can deduce that there are 41 missing digits. Therefore, we can write $p$ as:

108294440701045353595867242719660522374526250640690193563048263854806748525172379331?????????????????????????????????????????341078269246532299656864881223

where ? are the unknown digits.

We can then form the polynomial $k_1 * 10^{71} + x * 10^{30}+ k_2$, with $k_1$ and $k_2$ being our leaked decimal digits. Then, notice that this polynomial has a small root mod $p$ and therefore will also have a small root $\mod n$, as $p$ is a factor of $n$. Therefore, using coppersmith to solve for $x$ should give us the value of $p$, and from there decrypting the flag is trivial.

However, one thing we need to be aware of is that the polynomial is not monic, and coppersmith requires our polynomial to be monic (i.e. the term of highest degree, in this case $x$, has the coefficent 1). With one $x$ term, this is quite simple; we can just multiply the entire polynomial by the inverse of $10^{30} \mod n$ or alternatively just use sage’s .monic() to do it for you.

Implementation below.

 1from Crypto.Util.number import long_to_bytes
2
3n = 73542616560647877565544036788738025202939381425158737721544398356851787401183516163221837013929559568993844046804187977705376289108065126883603562904941748653607836358267359664041064708762154474786168204628181667371305788303624396903323216279110685399145476916585122917284319282272004045859138239853037072761
4P.<x> = PolynomialRing(Zmod(n), implementation='NTL')
5poly = 108294440701045353595867242719660522374526250640690193563048263854806748525172379331 * 10^71 + x * 10^30 + 341078269246532299656864881223
6f = poly.monic()
7d_p = f.small_roots(X=10^41, beta=41/155)[0]
8p = int(poly(d_p))
9q = n // p
10assert p * q == n
11e = 65537
12ct = 2657054880167593054409755786316190176139048369036893368834913798649283717358246457720021168590230987384201961744917278479195838455294205306264398417522071058105245210332964380113841646083317786151272874874267948107036095666198197073147087762030842808562672646078089825632314457231611278451324232095496184838
13d = pow(e, -1, (p-1)*(q-1))
14print(long_to_bytes(pow(ct,d,n)))


### Author: willwam845

server.py

 1from Crypto.Cipher import AES
2from Crypto.Util import Counter
4from Crypto.Util.number import bytes_to_long
5import os
6
8key = os.urandom(16)
9
10def encrypt(pt):
11  iv = os.urandom(16)
12  ctr = Counter.new(128, initial_value=bytes_to_long(iv))
13  cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
14  return iv + cipher.encrypt(pad(pt, 16))
15
16def decrypt(ct):
17  try:
18    iv = ct[:16]
19    ct = ct[16:]
20    ctr = Counter.new(128, initial_value=bytes_to_long(iv))
21    cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
22    pt = cipher.decrypt(ct)
24    return 1
25  except Exception as e:
26    return 0
27
28def main():
29  print(encrypt(flag).hex())
30  while True:
31   try:
32    print(decrypt(bytes.fromhex(input("> "))))
33   except Exception as e:
34    pass
35
36main()


The server prints the encrypted flag using AES-CTR mode, and then we are allowed to decrypt any ciphertext of our choosing, if the decrypted ciphertext has valid padding, the server responds with $1$, otherwise it responds with $0$.

This is basically a basic padding oracle attack. What we can do is modify the last byte of the ciphertext until we get a $1$ response. This means that the decrypted ciphertext had the last byte as a \x01 (or sometimes in rare cases, a \x02). Since AES-CTR is just a stream cipher, we can recover the keystream byte at that location, and then xor it with the original flag ciphertext to get the flag byte. After this, we just need to make sure we modify the last bytes of the ciphertext so that when decrypted, only one byte gives valid padding. Rinse and repeat for each of the bytes until we get the full flag.

Implementation below.

 1from pwn import *
3import time
4
5s = remote(sys.argv[1],int(sys.argv[2])) #, level='debug')
6ct = bytes.fromhex(s.recvline().decode())
7t = time.time()
8
9def bxor(ba1,ba2):
10 return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])
11
12def query(msg):
13  s.sendlineafter(b">", msg.hex())
14  if int(s.recvline().decode()):
15    return 1
16  else:
17    return 0
18
19def brute(b, iv, p1, p2, block, ct):
20  if query(iv + p1[:-1] + bytes([b]) + p2) and ((block+16) < len(ct) or b != ct[-1]):
21    return True
22  return False
23
24assert query(ct)
25assert not query(b'\x00'*32)
26
27flag = b''
28
29for block in range(16, len(ct), 16):
30  iv = ct[:block]
31  p1 = ct[block:block+16]
32  p2 = b""
33  i = 1
34  for i in range (1, 16):
35    b1, b2 = 0, 128
36    if p1[-1] >= 128:
37      b1, b2 = 128, 256
38    for byte in range(b1, b2):
39      print(i, byte)
40      if brute(byte, iv, p1, p2, block, ct):
41        p2 = bytes([byte]) + p2
42        p2 = bxor(p2, bytes([i]) * i)
43        p2 = bxor(p2, bytes([i+1]) * i)
44        p1 = p1[:-1]
45        print(i, byte)
46        break
47
48  for byte in range(256):
49    if query(iv + bytes([byte]) + p2):
50      p2 = bytes([byte]) + p2
51      break
52  flag += (bxor(bxor(p2, b'\x10' * 16), ct[block:block+16]))
53  print(flag)
54
56print(f"Solved in {time.time() - t} seconds")


# babyrand

### Author: willwam845

you can’t break an lcg with only 2 outputs right

script.py

 1from random import randrange
2from Crypto.Util.number import getPrime, long_to_bytes
3from Crypto.Cipher import AES
5from hashlib import sha256
6from os import urandom
7
9
10def und():
11  p = getPrime(512)
12  x = randrange(p)
13  a = p ^ x ^ randrange(2**200)
14  b = p ^ x ^ randrange(2**200)
15  return p, a, b, x
16
17p,a,b,x = und()
18
19iv = urandom(16)
20key = sha256(long_to_bytes(a) + long_to_bytes(b)).digest()[:16]
21cipher = AES.new(key, AES.MODE_CBC, iv)
22
23print(f"c1 = {x}")
24print(f"c2 = {(x*a + b) % p}")
25print(f"p = {p}")
26print(f"iv = '{iv.hex()}'")


output.txt

c1 = 5365904711205493895182988721055598679508066289977091231731349423996531384326997250984304389796311073201846992254794801346573036775490182780952712232258774
c2 = 2351499357088933835557969576916974229915931074692169825269157710226395480997304497294813272746195475744137017453323338362896396977337638862808560417575150
p = 12118911800929768381158064532151564397584328623097191996086479213117076586014730135201334840794700976422626122702191630484231703678287738839516304757792517


The script provides us with 2 consecutive outputs of an LCG, and then tasks us to find the parameters of the LCG, with the modulus $p$ already given. It then uses the parameters to encrypt the flag.

Normally, there wouldn’t be any way to break this, however taking a look at the parameter generation, there seems to only be 200 bits of entropy, as the parameters are generated by xoring a known value with a random 200 bit value. This means that we can form a multivariate polynomial to solve for $a$ and $b$ which should have small roots. As usual, we can use defund’s implementation.

To form this polynomial, we start by replacing the xor with addition, as xor is rather annoying to work with algebraically. We know the value of $p \oplus x$ (I’ll call this $n$ from now on, and we know $ax + b = c_2$. If we write $a = n + k_1$ and then $b = n + k_2$, by substitution, we can write the polynomial: $$xn + xk_1 + n + k_2 - c_2$$

where $k_1$ and $k_2$ are the small roots. We then simply solve for these small roots, recover the value of $a$ and $b$, and then decrypt the flag.

Implementation below.

 1# from https://github.com/defund/coppersmith
2import itertools
3
4def small_roots(f, bounds, m=1, d=None):
5	if not d:
6		d = f.degree()
7
8	R = f.base_ring()
9	N = R.cardinality()
10
11	f /= f.coefficients().pop(0)
12	f = f.change_ring(ZZ)
13
14	G = Sequence([], f.parent())
15	for i in range(m+1):
16		base = N^(m-i) * f^i
17		for shifts in itertools.product(range(d), repeat=f.nvariables()):
18			g = base * prod(map(power, f.variables(), shifts))
19			G.append(g)
20
21	B, monomials = G.coefficient_matrix()
22	monomials = vector(monomials)
23
24	factors = [monomial(*bounds) for monomial in monomials]
25	for i, factor in enumerate(factors):
26		B.rescale_col(i, factor)
27
28	B = B.dense_matrix().LLL()
29
30	B = B.change_ring(QQ)
31	for i, factor in enumerate(factors):
32		B.rescale_col(i, 1/factor)
33
34	H = Sequence([], f.parent().change_ring(QQ))
35	for h in filter(None, B*monomials):
36		H.append(h)
37		I = H.ideal()
38		if I.dimension() == -1:
39			H.pop()
40		elif I.dimension() == 0:
41			roots = []
42			for root in I.variety(ring=ZZ):
43				root = tuple(R(root[var]) for var in f.variables())
44				roots.append(root)
45			return roots
46
47	return []
48
49c1 = 5365904711205493895182988721055598679508066289977091231731349423996531384326997250984304389796311073201846992254794801346573036775490182780952712232258774
50c2 = 2351499357088933835557969576916974229915931074692169825269157710226395480997304497294813272746195475744137017453323338362896396977337638862808560417575150
51p = 12118911800929768381158064532151564397584328623097191996086479213117076586014730135201334840794700976422626122702191630484231703678287738839516304757792517
54
55R.<a,b> = PolynomialRing(GF(p))
56
57poly = a * c1 + (p^^c1) * c1 +  b + (p^^c1)- c2
58_a, _b = small_roots(poly, (2^200, 2^200), m=3, d=2)[0]
59
60
61print("a =", _a + (p^^c1))
62print("b =", _b + (p^^c1))
63a, b = _a + (p^^c1), _b + (p^^c1)
64
65from Crypto.Cipher import AES
66from Crypto.Util.number import long_to_bytes
67from hashlib import sha256
68
69iv = bytes.fromhex(iv)
70ct = bytes.fromhex(ct)
71#print(iv)
72#print(ct)
73key = sha256(long_to_bytes(a) + long_to_bytes(b)).digest()[:16]
74cipher = AES.new(key, AES.MODE_CBC, iv)
75
76
77print(cipher.decrypt(ct))


and then decrypting the flag gives us some lovely ascii art of defund

***********************************************************,,...................
**************************************,,,,************************,,,,..........
*********************************               ,**************,,,.    .,**,..,,
,,,,******************,.      .                    ,********,,,,..,,,,,**,.,,,.,
,,,,,,,,,,********,        ..                   .....***,,..,,.,....,,***.,*.,,,
,,,,,,,,,,,,.    .                                     .      .,...,,****,*,.,,.
,,,,,,,,.. .     .                                               ...,**/,,*,.,,.
,,,,,,,.         .                                                .,**//,*/.,*.,
,,,,,.. .      ..                        .....                       ,/*,/*.,,,,
,,,,,..     ...                            ......                 ..   .,/,.*,,,
,,,,,,,......          .                          ....                  */.,*,,,
,,,. ....           ....                           ..           ....    ,*.*,,,,
,,*,.    ..  .,,,,,,,,,,.                                   ..         .   .,.,*
,,,,.  ..                ............,                     .            .    ,,*
,,,,. ..                     .,,,,,,,,,.                  .      ..    . .    ,*
,,,*, . . ..                           .,..               .     .      ....   ,,
,,, .,.. ,/(((/*.                         .,,,,,,,.       ..   ..      . ..  ...
,. ., . ,(((((((((/                              ...      ...  ..   ... ..  .,,.
,..,  . /((((((((/.                                 .,     .,...,,......,...*/**
,,..   .*(((((((*                                      .,,.  .,,,,,,*,.......***
,,*,     .*//*                  .  *(((/,               .       ....   ......**/
***..                          .  ,(((((((((((*.        .     ,,           ,*///
*,**.,.           .            .  /((((((((((((((((/*   .     ..        ..*/////
***/,..,,.        .             . *((((((((((((((((/    ...    .****,,,*,***/**,
****//*...*,.   .,..             .,(((((((((((((((*     .,     ...,,,,*/*,,,,,,,
*****//((///.,*,..,,                ./(((((((((/.     ...     .....*///*,,,,,,,,
********/(((/.....,*,,,.                            ....  ........,//*,,,,,,,,,,
***********//(//,.......,,,,,,...             .....,,...........,/*,,,,,,,,,,,,,
****************/////////////....,,,,*******,,,......./////////*,,,,,,,,,,,,,,,,
***********************///(((///,.......*,.........,///////*,,,,,,,,,,,,,,,,,,,,
************************,,,,,,**////////,,,,,/////////,,,,,,,,,,,,,,,,,,,,,,,,,,
********************,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,*

stan defund

flag: corctf{c0ngr4tul4t10ns_y0u_4r3_n0w_p4rt_0f_th3_d3fund_f4n_club!}


# LCG_k

## Challenge

Can you sign my message for me?

nc crypto.be.ax 6002

## Solution

Let’s look at the source provided in source.py.

 1from Crypto.Util.number import bytes_to_long, inverse
2from hashlib import sha256
3from secrets import randbelow
4from private import flag
5from fastecdsa.curve import P256
6
7G = P256.G
8N = P256.q
9
10class RNG:
11	def __init__(self, seed, A, b, p):
12		self.seed = seed
13		self.A = A
14		self.b = b
15		self.p = p
16
17	def gen(self):
18		out = self.seed
19		while True:
20			out = (self.A*out + self.b) % self.p
21			yield out
22
23def H(m):
24	h = sha256()
25	h.update(m)
26	return bytes_to_long(h.digest())
27
28def sign(m):
29	k = next(gen)
30	r = int((k*G).x) % N
31	s = ((H(m) + d*r)*inverse(k, N)) % N
32	return r, s
33
34def verify(r, s, m):
35	v1 = H(m)*inverse(s, N) % N
36	v2 = r*inverse(s, N) % N
37	V = v1*G + v2*pub
38	return int(V.x) % N == r
39
40seed, A, b = randbelow(N), randbelow(N), randbelow(N)
41lcg = RNG(seed, A, b, N)
42gen = lcg.gen()
43d = randbelow(N)
44pub = d*G
45mymsg = b'i wish to know the ways of the world'
46
47print('public key:', pub)
48signed_hashes = []
49
50for _ in range(4):
51	m = bytes.fromhex(input('give me something to sign, in hex>'))
52	h = H(m)
53	if m == mymsg or h in signed_hashes:
54		print("i won't sign that.")
55		exit()
56	signed_hashes.append(h)
57	r, s = sign(m)
58	print('r:', str(r))
59	print('s:', str(s))
60print('now, i want you to sign my message.')
61r = int(input('give me r>'))
62s = int(input('give me s>'))
63if verify(r, s, mymsg):
64	print("nice. i'll give you the flag.")
65	print(flag)
66else:
67	print("no, that's wrong.")


We are given the ability to sign four distinct messages(without hash collision) using ECDSA over the P256 curve, and then are asked to sign the message msg = 'i wish to know the ways of the world', without being able to sign it using one of the four chances given. The issue here is that the k nonces are generated using an linear congruence generator(LCG), so they are closely related to each other. Then, it seems like the method of attack is to exploit the nonces’ relationship to recover the private key, which we can then use to forge a signature for msg.

Let’s start out by writing the values of ri, si for each message mi that we send.

1ri = x(k_i*G) % N
2si = (H(mi) + d*ri)*k_i^-1 % N


with k_{i+1} = A*k_i + b mod p. The key here is that due to the nonce generation’s nature, we are not introducing any new unknowns into our equations beyond the first. Normally, when you sign messages using ECDSA, a new unknown k_i is added to your system of equations; in this case, however, no matter how many messages we sign, the unknowns remain as A, b, k1, d, where k1 is the k1 used in signing the first message. Technically the other unknown is seed instead, but to simplify things a little, we treat the first nonce directly as an unknown.

With four signatures, we get eight equations, although the ri equations are not very useful to us, since they take the the coordinate of an elliptic curve point. However, the four equations involving the sis are enough to solve. You can do this through the following method or through more thorough equation manipulation(basically, by hand). If you are interested in solutions where solvers did them by hand, I recommend checking out Utaha and y011d4’s writeups(you may need a translator for the second one), where they describe the methods to do so. The following method is less nice in my opinion, but demonstrates the usage of a powerful mathematical tool.

First, I eliminated the unknown private key d from my equations, by using the following relation:

1(si*k_i - H(mi))*ri^-1 - (s_{i+1}*k_{i+1} + H(m_{i+1}))*r_{i+1}^-1 = d - d = 0 mod N


with

k1 = k1
k2 = A*k1 + b
k3 = (A^2)*k1 + A*b + b
k4 = (A^3)*k1 + (A^2)*b + A*b + b


all mod N.

This produces 3 equations in 3 unknowns. (It turns out this step wasn’t needed, but I kept it in from when I was first trying things for a solve). For the appropriate values of the nonces, the expressions on the left hand sides evaluate to 0, as we see. Normally, this would be four unknowns in three equations; but in this case, all nonces can be expressed in terms of A, k1, b, so it’s only three unknowns. However, substituting those expressions in for the nonces and doing algebra manipulation may seem quite complicated. If possible, we’d like a simpler way to deal with them…

Notice that since each left hand side expression evaluated with the correct value of the nonces will evaluate to 0, this means that the same will be true for the correct values of A, k1, b. Let’s then treat each left hand expression as a multivariate polynomial P_i(A, k1, b) with roots at the the correct values for each variable.

Then, our three equations can be considered three polynomials that share the correct values of A, k1, b as roots. There is a powerful tool known as Groebner Basis reduction that takes a set of multivariate polynomials and outputs a set of “reduced” polynomials that share roots with the inputted ones, while often being simpler(i.e. having lower degree). Of course, there are lot more details, but this description should be sufficient to understand its usefulness(unfortunately, I’m not so familiar with the details of its workings). We will try to use it on our polynomials to produce a set of potentially simpler polynomials which we may be able to directly extract our desired roots.

Giving it a try yields polynomials of the following form:

b^2 + c1*b + c0
k1 + c3*b + c2
a + c5*b + c4


where the c terms are constants.

In particular, the first two are of use to us, as we can easily extract the roots of the first one to obtain candidates for b, and select one to solve for k1 with a 50% chance. Then, using the fact that

1s1 = (H(m1) + d*r1)*k1^-1 => (si*k1 - H(m1))*r1^-1 = d % N


we can recover d. Then, using an arbitrary k value, we can perform the same calculations done in sign to forge a valid signature for msg, and send the pair r, s to the server to get the flag.

Here is my script to do so:

 1import os
2os.environ['PWNLIB_NOTERM'] = '1'
3from pwn import *
4from hashlib import sha256
5from Crypto.Util.number import bytes_to_long
6from fastecdsa.curve import P256
7
8G = P256.G
9N = P256.q
10count = 4
11
12Fn = GF(N)
13
14def H(m):
15	h = sha256()
16	h.update(m)
17	return bytes_to_long(h.digest())
18
19host, port = 'crypto.be.ax', 6002
20r = remote(host, port)
21ms = [hex(i)[2:].zfill(2).encode() for i in range(count)]
22zs = [Fn(H(ms[i])) for i in range(count)]
23rs = []
24ss = []
25
26for i in range(count):
27	r.recvuntil(b'give me something to sign, in hex>')
28	r.sendline(ms[i].hex())
29	r.recvuntil(b'r:')
30	rs.append(Fn(int(r.recvline())))
31	r.recvuntil(b's:')
32	ss.append(Fn(int(r.recvline())))
33
34P.<k, a, b> = PolynomialRing(Fn)
35
36def lcg(x):
37	return a*x + b
38
39ks = [k]
40for _ in range(count-1):
41	ks.append(lcg(ks[-1]))
42
43polys = [ss[i]*ks[i]*rs[i]^-1 - zs[i]*rs[i]^-1 -ss[i+1]*ks[i+1]*rs[i+1]^-1 + zs[i+1]*rs[i+1]^-1 for i in range(count-1)]
44I = ideal(polys)
45B = I.groebner_basis()
46c0s = B[0].coefficients()
47c1s = B[1].coefficients()
48T.<x> = PolynomialRing(Fn, 'x')
49poly = c0s[0]*x^2 + c0s[1]*x + c0s[2]
50roots = poly.roots()
51# 50-50 here
52b = roots[0][0]
53print(roots)
54k1 = -(c1s[1]*b + c1s[2])*(c1s[0]^-1) % N
55d = ((ss[0]*k1 - zs[0])*(rs[0]^-1)) % N
56
57msg = b'i wish to know the ways of the world'
58fr = (int(2)*G).x % N
59fs = ((H(msg) + d*fr)*inverse_mod(2, N)) % N
60
61r.recvuntil(b'give me r>')
62r.sendline(str(fr))
63r.recvuntil(b'give me s>')
64r.sendline(str(fs))
65
66r.interactive()


corctf{r3l4ted_n0nce5_4re_d4n6er0us_fde6ebafa842716a}

# bank

### Author: Quintec

This was a challenge relating to a quantum money scheme, where you had to determine the value of 50 qubits that made up a dollar bill to get the flag. If you aren’t familiar with quantum computing or quantum money schemes and/or would like a quick overview, I recommend you check out my writeup here on a similar challenge I solved earlier this year and read the “The Basics” and “The Problem” sections.

## Analysis

Looking at this problem, unlike the one linked above, there is no “probe” qubit to use, so how can we determine the value of a qubit? Taking a closer look at the source code, we notice this section:

 1elif op == '8':
2    actual = bill[idx]
3    if actual in '01':
4        measured = qubits[idx].measure('01')
5    else:
6        measured = qubits[idx].measure('+-')
7    if actual == measured:
8        print('Qubit successfully verified.')
9    else:
10        print('Incorrect qubit!')


What notably doesn’t happen is the code exiting if the qubit is wrong. This means we can verify the qubit as many times as we want! Now this doesn’t solve the problem on its own, since we still don’t know what basis to pick, and picking the wrong one would destroy the information in the qubit. However, now we can use some properties of qubits to our advantage.

## Solution

Pick any basic single qubit gate, such as the X gate. Note that the X gate has eigenstates $|+\rangle$ and $|-\rangle$​​ , in other words, if you apply an X gate to a qubit currently in either of those 2 states, nothing happens. We can use this to our advantage since we know the qubits start in the correct, verified state.

For each qubit, we apply an X gate, and then try to verify it. If it still is successfully verified, we now know it is in the $+/-$ basis. Otherwise, the qubit did change (from $|0\rangle$ to $|1\rangle$ or vice versa), and we know it is in the $0/1$​ basis. Now that we know what basis it is in, we can simply measure it (keeping in mind we first applied an X gate). Do this for all 50 qubits and you’ll get the flag!

Here is a script my teammate qopruzjf wrote to testsolve my challenge: (I was too lazy to write my own)

 1from pwn import *
2r = remote('crypto.be.ax', 6005)
3
4mybill = list("?"*50)
5
6def test_X(i):
7	r.sendline(b'1')
8	r.recvuntil(b'9. Back')
9	r.sendline(b'8')
10	r.recvline()
11	re = r.recvline()[:-1]
12	print(re)
13	if re == b'> Incorrect qubit!': # qubit was not X-eigenvector, so in 0, 1
14		r.recvuntil(b'9. Back')
15		r.sendline(b'1')
16		r.recvuntil(b'9. Back')
17		r.sendline(b'6')
18		r.recvuntil(b'The qubit measured as ')
19		mybill[i] = r.recvline()[:-1].decode()
20		r.recvuntil(b'9. Back')
21		r.sendline(b'9')
22	else: # qubit is in +- basis
23		r.recvuntil(b'9. Back')
24		r.sendline(b'7')
25		r.recvuntil(b'The qubit measured as ')
26		mybill[i] = r.recvline()[:-1].decode()
27		r.recvuntil(b'9. Back')
28		r.sendline(b'9')
29
30def get_qubit(i):
31	r.recvuntil(b'3. Quit')
32	r.sendline(b'1')
33	r.recvuntil(b'index of the qubit you wish to work with: ')
34	r.sendline(str(i).encode())
35	r.recvuntil(b'9. Back')
36	test_X(i)
37
38r.recvuntil(b'Would you like an account? (y/n) ')
39r.sendline(b'y')
40
41for i in range(50):
42	get_qubit(i)
43
44mybill = ''.join(mybill)
45print(mybill)
46r.recvuntil(b'3. Quit')
47r.sendline(b'2')
49r.sendline(mybill.encode())
50r.interactive()


# mystery_stream

## Challenge

Mysterious stream cipher. Wonder what the seed was…

## Solution

We are provided two source files and a ciphertext file ct. Let’s take a look at source.py first:

 1from random import randrange
2from secrets import flag, key
3from Crypto.Util.number import long_to_bytes
4
5def bsum(state, taps, l):
6	ret = 0
7	for i in taps:
8		ret ^= (state >> (l - i))
9	return ret & 1
10
11class Gen:
12	def __init__(self, key, slength):
13		self.state = key
14		self.slength = slength
15		self.TAPS = [2, 4, 5, 7, 10, 12, 13, 17, 19, 24, 25, 27, 30, 32,
16		33, 34, 35, 45, 47, 49, 50, 52, 54, 56, 57, 58, 59, 60, 61, 64]
17
18	def clock(self):
19		out = bsum(self.state, self.TAPS, self.slength)
20		self.state = (out << (self.slength - 1)) + (self.state >> 1)
21		return out
22
23def insertflag(fn, flag):
24	txt = b''
25	with open(fn, 'rb') as f:
27	i = randrange(0, len(txt))
28	txt = txt[:i] + flag + txt[i:]
29	with open(fn, 'wb') as f:
30		f.write(txt)
31
32def gf256_multiply(a,b):
33  p = 0
34  for _ in range(8):
35    if b % 2:
36      p ^= a
37    check = a & 0x80
38    a <<= 1
39    if check == 0x80:
40      a ^= 0x1b
41    b >>= 1
42  return p % 256
43
44def encrypt(fn, outf, cipher):
45	pt = b''
46	with open(fn, 'rb') as f:
48	ct = b''
49	for byte in pt:
50		genbyte = 0
51		for i in range(8):
52			genbyte = genbyte << 1
53			genbyte += cipher.clock()
54		ct += long_to_bytes(gf256_multiply(genbyte, byte))
55	with open(outf, 'wb') as f:
56		f.write(ct)
57
58insertflag('pt', flag)
59cipher = Gen(key, 64)
60encrypt('pt', 'ct', cipher)


Looking at this, we can see that Gen is supposed to behave as a linear-feedback-stream-cipher, or LFSR for short. In encrypting the plaintext with the cipher, first, the flag is inserted into a random position, and then bytes are generates from the LFSR, which are multiplied byte-by-byte with the plaintext bytes via the gf256_multiply method.

To get a clearer view on the method of attack for this challenge, let’s also take a look at the pub.sage file:

 1R.<x> = PolynomialRing(GF(2), 'x')
2poly = [REDACTED]
3assert poly.degree() == 64
4M = [poly.list()[1:]]
5for i in range(63):
6	M.append([1 if j == i else 0 for j in range(64)])
7M = Matrix(GF(2), M)
8A = M^[REDACTED]
9E, S = A.eigenspaces_right(format='galois')[0]
10assert E == 1
11keyvec = S.random_element()
12key = int(''.join([str(d) for d in keyvec]), 2)
13print(key)


Analyzing the source from bottom up, it seems that the key used in source.py is periodic in some fashion, with period a = [REDACTED]. This comes from key being in the eigenspace of M^a for eigenvalue 1, meaning (M^a) * keyvec = keyvec. The question then is what M represents, and what the redacted a value is, and how they will help us solve the challenge.

Looking at the M matrix’s construction, we can see that it is comprised of the first row being the unknown poly’s coefficients, while the remaining rows seem to follow an identity matrix. The structure is something like this:

[[ ---- poly coefficients ---- ]
[1 0 0 0 0 0 0 0 0 0 0 0 .... 0]
[0 1 0 0 0 0 0 0 0 0 0 0 .... 0]
[0 0 1 0 0 0 0 0 0 0 0 0 .... 0]
.
.
.
[0 0 0 0 0 0 0 0 0 0 .... 0 1 0]]


If we replace the first row with all 0s, then you may recognize that this is a lower shift matrix, which, when multiplied by a vector, will move all the entries in that vector down one. To see why this matters, let’s take a look at Gen from source.py once again:

 1def bsum(state, taps, l):
2	ret = 0
3	for i in taps:
4		ret ^= (state >> (l - i))
5	return ret & 1
6
7class Gen:
8	def __init__(self, key, slength):
9		self.state = key
10		self.slength = slength
11		self.TAPS = [2, 4, 5, 7, 10, 12, 13, 17, 19, 24, 25, 27, 30, 32,
12		33, 34, 35, 45, 47, 49, 50, 52, 54, 56, 57, 58, 59, 60, 61, 64]
13
14	def clock(self):
15		out = bsum(self.state, self.TAPS, self.slength)
16		self.state = (out << (self.slength - 1)) + (self.state >> 1)
17		return out


Specifically, let’s take a look at the clock function. With each call to the clock function, the last bit of the state is removed by (self.state >> 1), and the out bit is put at the top by (out << (self.slength - 1)). The out bit is simply the bitwise sum(XOR) of the bits of self.state at the positions in self.TAPS. This may seem rather familiar, now that we’ve taken a look at M, calling clock seems to modify self.state very similarly to applying M to keyvec, where keyvec is simply the bitvector representation of key.

Here, we make one of the key observations of this challenge: it is likely that the first row of M, the coefficients of poly, are actually just the bit positions in taps. This inference is made both upon the previous observations, and upon the fact that LFSRs each have their own characteristic polynomial which define their taps(and vice versa), which you can read more about here. This means that we can reasonably conclude that the poly from pub.sage is the LFSR’s characteristic polynomial. (Though, it seems that this part turned out more guessy than intended. Apologies to anybody who may have been frustrated by this. I actually wanted this part to be clear to everyone, but people managed to solve without me just putting it into pub.sage. In the end, I just asked for anybody stuck to open a ticket. I’ll try to make things clearer next time.)

To recover the polynomial from the taps, you can use the following code, in sagemath:

1R.<x> = PolynomialRing(GF(2), 'x')
2taps = [2, 4, 5, 7, 10, 12, 13, 17, 19, 24, 25, 27, 30, 32, 33, 34, 35, 45, 47, 49, 50, 52, 54, 56, 57, 58, 59, 60, 61, 64]
3poly = 1
4for exp in taps:
5	poly += x^exp


to get x^64 + x^61 + x^60 + x^59 + x^58 + x^57 + x^56 + x^54 + x^52 + x^50 + x^49 + x^47 + x^45 + x^35 + x^34 + x^33 + x^32 + x^30 + x^27 + x^25 + x^24 + x^19 + x^17 + x^13 + x^12 + x^10 + x^7 + x^5 + x^4 + x^2 + 1 as the LFSR polynomial. Again, you can read the linked wikipedia page to see the relationship between the taps and the polynomial.

Based on this assumption, we can now recognize that the matrix M essentially models applying clock to change the internal state of the LFSR. With this information, from our observation that keyvec is periodic in being multiplied by M, it’s likely that the issue in the challenge is that key is periodic, with a period shorter than optimal(in this case, 2^64 - 1) to allow for some attack. The ciphertext ct being rather long also hints towards this.

Then, the next target is to find what the possible values of a are. This is where the main idea of the challenge lies - if we work under the assumption that the period of the LFSR is shorter than optimal, then its taps, and thus its polynomial, are likely not optimal. Since irreducibility of the characteristic polynomial is what gives an LFSR the optimal period length, it means that poly in this case is likely not irreducible. And in fact, factoring poly in sagemath gives us the following 4 factors:

1p8 = x^8 + x^6 + x^5 + x^4 + 1
2p14 = x^14 + x^13 + x^12 + x^2 + 1
3p19 = x^19 + x^18 + x^17 + x^14 + 1
4p23 = x^23 + x^18 + 1


With this, the insight on the possible values of a comes from this stackexchange post: here. Please do read more into it if interested.

To sum it up, for a LFSR with reducible characteristic polynomial poly, its possible periods(depending on the initial state) will be the least-common-multiples of the periods of the LFSRs with a characteristic polynomial that is an irreducible factor of poly. Specifically, in the case of this challenge, the periods of the 4 LFSRs based on the 4 factors of poly are 255, 16383, 524287, and 8388607 respectively. You can obtain these numbers from the aforementioned wikipedia page as well, but they come from the fact that each polynomial is the irreducible polynomial producing the optimal period for a LFSR with a state of d bits, where d is the degree of that polynomial. Optimal period simply refers to the LFSR going through all states except all 0s(an LFSR that reaches this state will always stay at this state), so that’s 2^d - 1 period length. Anyways, the possible periods of LFSR here are LCMs of combinations of those 4 numbers. With this, we can calculate all candidates for a.

In regards to finding a candidates, some people asked me during the CTF if I could provide a bound for a. The reason I said no is because the idea was to use this to find candidates for a, so hopefully that makes sense.

Now, knowing candidates for a, there are 2 main approaches: either bruteforce decrypt through all the keys with period length a, or use frequency analysis on the long ct to decrypt. Both of these options are really only viable if the period is short enough, so we can start off by testing a=255, as there are 255 keys with this period, and having a rather long period length means frequency analysis will likely fail, as ct is not long enough. My intended approach was to use the latter.

One thing to note in doing this: the bitstream is of length 255, but to do frequency analysis, under the assumption that the plaintext is in English(something I couldn’t mention directly in the challenge description, as that would give away quite a bit of the solution to experienced players), we want to look at the bytes instead, so that we can have a valid delimiter. We can get past this by simply treating the LFSR’s output as a 255 byte GF256 multiplication key, since 8*255 is divisible by 255.

Here is my script to do so:

 1from Crypto.Util.number import long_to_bytes, bytes_to_long
2delim = bytes_to_long(b' ')
3
4F = GF(2^8, 'x', modulus=x^8 + x^4 + x^3 + x + 1)
5
6def div(a, b):
7	elem = F.fetch_int(a) / F.fetch_int(b)
8	return elem.integer_representation()
9
10def g256_decrypt(m: bytes, key: list, outf):
11	ct = b''
12	for i in range(len(m)):
13		ct += long_to_bytes(div(m[i], key[i % len(key)]))
14	with open(outf, 'wb') as f:
15		f.write(ct)
16
17def g256_crack(ct: bytes, keylen: int, delim: int, outf):
18	key = ['']*keylen
19	for i in range(keylen):
20		index = i
21		samples = {}
22		while index < len(ct):
23			cur = ct[index]
24			if cur not in samples:
25				samples[cur] = 0
26			samples[cur] += 1
27			index += keylen
28		maxfreqbyte = max(samples, key=samples.get)
29		key[i] = div(maxfreqbyte, delim)
30	g256_decrypt(ct, key, outf)
31	print("done")
32
33ct = b''
34with open('ct', 'rb') as f:
36
37g256_crack(ct, 255, delim, 'finish')


You can view this in solve.sage as well. Then, simply searching for the prefix corctf{ will give us the flag: corctf{p3ri0dic4lly_l00ping_on_4nd_on...}

As another note, the reason I used gf256_multiply rather than something simpler like XOR was to avoid solves by simply applying xortool without much thought, so at the very least, teams would have to understand the approach they’re using.

# fried_rice

## Challenge

Kind of hungry… guess I’ll make some fried rice. NOTE: The server has a time limit of 5 minutes.

nc crypto.be.ax 6003

## Solution

Let’s examine the source given in source.sage first.

 1from random import shuffle, randrange, randint
2from os import urandom
3from Crypto.Util.number import getPrime, getStrongPrime, long_to_bytes
4from Crypto.Cipher import AES
6from private import flag
7import sys
8
9class RNG:
10	def __init__(self, seed, a, b):
11		self.state = seed
12		self.a = a
13		self.b = b
14		print('a:', a)
15		print('b:', b)
16
17	def nextbits(self, bitlen):
18		out = 0
19		for _ in range(bitlen):
20			out <<= 1
21			self.state = self.a * self.state + b
22			bit = int(sum(self.state[i] for i in range(7)))
23			out += bit
24		return out
25
26def get_params(rng, bitlen):
27	p = next_prime((1 << (bitlen - 1)) | rng.nextbits(bitlen))
28	q = next_prime((1 << (bitlen - 1)) | rng.nextbits(bitlen))
29	N = p * q
30	return N, p, q
31
32LIMIT = 26
33P.<x> = PolynomialRing(GF(2))
34F.<x> = P.quo(x^128 + x^7 + x^2 + x + 1)
35key, a, b = [F.random_element() for _ in range(3)]
36bytekey = long_to_bytes(int(''.join(list(map(str, key.list()))), 2))
37iv = os.urandom(16)
38cipher = AES.new(bytekey, AES.MODE_CBC, IV=iv)
39rng = RNG(key, a, b)
40N, p, q = get_params(rng, 512)
41if randint(0, 1):
42	p, q = q, p
43e = 65537
44d = inverse_mod(e, (p-1)*(q-1))
45dp = d % (p-1)
46r = getStrongPrime(1024)
47g = randrange(2, r)
48print('iv:', iv.hex())
49print('N:', N)
50print('e:', e)
51print('g:', g)
52print('r:', r)
54print()
55print("now, let's cook some fried rice!")
56for _ in range(LIMIT):
57	sys.stdout.flush()
58	m = int(input('add something in(in hex)> '), 16)
59	dp ^^= m
60	print('flip!', pow(g, dp, r))
61print("it's done. enjoy your fried rice!")


The server generates a polynomial over the given quotient ring F, takes the coefficients of said polynomial as an AES key, and encrypts the flag using it. Then, using the PRNG described with key as the initial state, it generates 512 bits, each for use in primes p and q. The server then gives us the parameters a and b used in the PRNG, the iv used in the AES encryption, the number N = p * q, the public exponent e used to calculate d, and the numbers g and r. It then takes 26 inputs from the user, and updates the value dp, initially equal to d % (p-1), by XORing it with the user’s input. (If you are not familiar with sagemath, ^ can be used for exponentiation, and ^^ is used for bitwise XOR.)

The end goal of the challenge is to recover bytekey. So, it seems that we need to somehow use the 26 queries to get information to factor N, and then with knowledge of p and q’s bits, reverse the PRNG to recover key, which will give us bytekey.

### Stage 1: Recovering bits of dp

First, let’s focus on the 26 queries with the server, and what we can do with them. Since the server will update dp XOR m for every m you send and the print g^dp mod r, it’s like that we are supposed to use these queries to recover some amount, if not all, of dp. Assuming we can’t just solve the discrete log problem(DLP), we will need to find some way to do this.

(As a side note, it is actually possible to solve the DLP, in some situations. This is because getStrongPrime returns a prime r such that r-1 and r+1 have at least one large prime factor. However, this is not nearly as secure as a safe prime, which is a prime of the form r = 2p + 1, where p is another prime. This was pointed out to me by a solver during the CTF. So, it is possible for r to be generated such that it is smooth enough to be attacked using the Pohlig-Hellman algorithm. You just need some luck. The attack taking advantage of this is in my opinion much cooler than my sloution, so I suggest you read joseph from skateboarding dog’s writeup about it.)

To illustrate my method of attack, let’s consider the numbers dp and dp1 = dp XOR 1. When let’s define v1 = g^dp mod r, and v2 = g^dp1 mod r. Now, consider the following two cases:

• dp is odd - then dp1 = dp - 1, as the last bit of dp is 1. Then, v2 = g^(dp - 1) = g^dp * g^-1 = v1 * g^-1 mod r.
• dp is even - then dp1 = dp + 1, as the last bit of dp is 0. Then, v2 = g^(dp + 1) = g^dp * g = v1 * g mod r.

Putting this into context of this challenge, suppose we first send 0 as m so that we retrieve v1 = g^dp mod r. Then, we can send 1 as m, so that we get v2 = g^(dp XOR 1) mod r. Then, simply checking if v2 = v1 * g^-1 mod r or v2 = v1 * g mod r will reveal the last bit of dp.

We can further extend this idea to reveal other bits. For a bit that is dis bits away from the last bit, we can check v1 = g^d1 mod r versus v2 = g^(d1 XOR (1 << dis)) mod r. d1 XOR (1 << dis) will either be 1 << dis = 2^dis added or subtracted from d1. So, we can similarly check whether v2 = v1 * g^(2^dis) mod r or v2 = v1 * g^-(2^dis) mod r. This gives us a method to leak any arbitrary bit of dp, simply by changing dis each time so that the original dp bit in that position is preserved before we attempt to leak it, even after dp is altered.

With this method, we can leak 25 bits of dp, in any positions. Note that the first query is used by sending 0 to get g^dp mod r. However, 25 bits of a ~512 bit number(since dp is the inverse of e, a relatively small number mod p, which is a 512 bit prime) is not very meaningful. We need some way to dramatically increase the number of bits we can leak.

We can do just this, simply by further expanding on the ideas we’ve developed so far. Let’s consider how we can check 2 bit chunks at a time instead of 1. Now, the possible 2 bit states our target chunk could have are 00, 01, 10, 11. If when XORed with 3, which is 11 in binary, the possible resultant states are 11, 10, 01, 00. These correspond to changes of 3, 1, -1, -3. Notice that the changes are all unique, so just like before, we can check each difference to see what the original bits of the chunk were.

Naturally, we can expand this further. Consider a chunk c of bit length l that we would like to check. We send m as the base 10 equivalent of a binary string consisting of l 1s. As long as the differences between all possible original states of c and c XOR m are unique, we can determine the original state of c, using a simple search through all the possible differences and the technique described above. Of course, when trying to find different chunks, we will need to account for bit positions they are in, just like before. And it’s easy to check that all differences are unique simply by calculating them.

The main issue with this method is, for every increase in bitlength of the chunk, we double the search space that we go through. With the given time limit, we are unable to leak large chunks at a time using this method without some substantial luck. On my laptop, with the 25 queries after sending m = 0, I was able to recover 14 bit chunks, for a total of 350 bits of dp. I chose to recover the most significant bits, since they will the simplest to use for the next part of the challenge.

As a side note, if you are more creative, you may find a method to more efficiently leak each chunk than this naive method. With 20 bits per chunk, it is enough to recover the entirety of dp and partially skip the next step.

Here’s the code to recover all but the bottom 168 bits of dp:

 1def search_chunk(nbits, stage, cur, m):
2	m = int(m << (stage * nbits))
3	r.recvuntil(b'add something in(in hex)> ')
4	r.sendline(hex(m)[2:].encode())
5	r.recvuntil(b'flip! ')
6	res = int(r.recvline())
7	cands = [i for i in range(2**nbits)]
8	ref = {}
9	# setup
10	for cand in cands:
11		c = int(cand << (stage * nbits))
12		diff = c - (c^^m)
13		ref[diff] = cand
14	# perform search
15	for k, v in ref.items():
16		if res * pow(g, k, rh) % rh == cur:
17			return res, v
18
19
20def recover_dp_MSBs(shift):
21	dpmsbs = 0
22	CHUNKSIZE = 14
23	r.recvuntil(b'add something in(in hex)> ')
24	r.sendline(b'00')
25	r.recvuntil(b'flip! ')
26	cur = int(r.recvline())
27	m = 2**CHUNKSIZE - 1
28	for i in range(LIMIT - 1):
29		cur, chunk = search_chunk(CHUNKSIZE, i + shift, cur, m)
30		dpmsbs += chunk << (CHUNKSIZE * i)
31		print(f'completed stage {i+1}')
32	return Integer(dpmsbs)
33
34d0 = recover_dp_MSBs(12)


### Stage 2: Factoring N using MSBs of dp (Skip to next section if already familiar)

There is a known attack to factor N when you know enough MSBs of dp = d mod (p-1). Relevant reading is here. The explanation there is already quite good, but I’ll try to explain the ideas used here in brief. Naturally, feel free to skip if you are familiar with this.

We start with the congruence e*dp = 1 mod (p-1). Lifting to the integers, we have e*dp = 1 + kp*(p-1). Because dp < p - 1, kp < e, or else kp * (p-1) > e*dp and the equality is not possible. So, we can bruteforce the value of kp, as e is small. Then, taking the equation mod p this time and moving all terms to the left side, we have e*dp + kp - 1 = 0 mod p.

Next, we include our known MSBs a into the expression. If the bottom l bits of dp, which we call r, are unknown, then we have dp = a*(2^l) + r, where a, l are known. Then, we have e*(a*(2^l) + r) + kp - 1 = 0 mod p. Note that R = 2^l is a upper bound for r, as r is l bits and 2^l is l+1 bits. Multiplying both sides by einv = e^-1 mod N, which is congruent to e^-1 mod p(I suggest trying to prove this yourself if this is not clear), we have r + a*(2^l) + einv(kp - 1) = 0 mod p. Let’s then define the value A = a*(2^l) + einv(kp - 1) and the polynomial P(x) = x + A in mod p, which has root r. Then, we need to find this root, which will allow us to calculate the quantity r + A, which, if it is a small multiple of p, will allow us to factor N via GCD.

The way we find this root will be to find it using another polynomial that also has it r as a root mod p. One way to construct such a polynomial is by constructing a polynomial that is a linear combination of other polynomials that have r as a root, because evaluating it at r will result in summing 0s. Consider the polynomials x*(x + A), x + A, and N. All of these share r as a root mod p(in the case of N, it is 0 mod p, and the 0 polynomial has any value as a root). We construct the following matrix as a lattice basis:

[[1, A, 0]
[0, 1, A]
[0, 0, N]]


where the columns correspond to the coefficient of x^2, x, and the constant from left to right, and each row corresponds to one of those polynomials. Then, any polynomial constructed by taking the coefficients from a vector in the lattice will also have root r in mod p.

Next, even though we do not know p, we want a polynomial where we can still extract r as a root. This means that we want our polynomial f(x) to have f(r) = 0 over the integers, since that will also be 0 mod p. Having a root mod N is not useful, as using GCD will simply return N.

To ensure that we can construct a polynomial with this property, we’ll make one more modification to the above matrix, which is multiplying the columns by R^2 and R for the first and second column, resulting in

[[R^2, R*A, 0]
[0, R, A]
[0, 0, N]]


as the matrix. My understanding for this is that since R > r, we sort of ’evaluate’ the polynomial at R in each row by doing this multiplication, and so the norm(refer to the paper for details, but it is untuitively connected to the length/magnitude) of that row acts as an upper bound on evaluating the polynomial at r instead. So, if we get the vector v = (a1*R^2, a2*R, a3), if the norm of v is less than p, then the polynomial f(x) = a1*x^2 + a2*x + a3 should have r as a root over the integers. To find v from the lattice, we can use LLL reduction, which will find it as long as R is not too big. This also fits the intuition that having too many unknown bits will result in failing to recover the appropriate root, and why we want to recover as many bits as possible from stage 1.

To recap, our approach for this part is as follows:

• For each possible value of kp < e, construct the aforementioned lattice
• LLL to recover the vector from which we construct the polynomial
• r is an integer, so get the integer roots from the polynomial
• for each root, calculate A + r and gcd with N. If greater than 1 and is less than N, then we have p, and we’re done.

Here’s the code for this stage:

 1def factor_n_with_dpmsbs(cs, shift):
2	l = cs * shift
3	ei = inverse_mod(e, N)
4	for kp in range(1, e):
5		R = 2**l
6		A = R * d0 + ei*(kp - 1)
7		B = Matrix([
8			[R**2, R*A, 0],
9			[0, R, A],
10			[0, 0, N]])
11		B = B.LLL()
12		vec = B[0]
13		poly = (vec[0]/(R^2))*y^2 + (vec[1]/R)*y + vec[2]
14		roots = poly.roots(multiplicities=False)
15		for root in roots:
16			ff = int(A + root)
17			fac = gcd(ff, N)
18			if fac > 1 and fac != N:
19				print('found!')
20				return fac, N / fac
21
22p, q = factor_n_with_dpmsbs(14, 12)


### Stage 3: Recovering the initial state of the PRNG

With a method to factor N to get p and q, we need to recover key so that we can get the AES key.

Note: The PRNG used here is a slightly modified version of the one in Phoenix from AeroCTF 2021. Additionally, the solve is based off what I learned from rkm0959’s writeup on that challenge. I highly recommend reading it, but I’ll explain the ideas here.

Since key is an element in the given quotient ring, we can express what we want to find as the vector of 128 coefficients [k127, k126, k125, ..., k0] where each ki is one of 0, 1 and key = k127*x^127 + k126*x^126 + ... + k1*x + k0. If we can get a system of 128 linear equations involving these 128 unknowns, we can get the key to decrypt the flag. Then, let’s consider how we can set up the system using the PRNG’s workings.

The state of the PRNG simply starts out as key, but updates as follows:

1self.state = self.a * self.state + self.b


where the result is kept in F. Then, after updating, the coefficients of x^6, x^5, …, x, and the constant are XORed together(addition in GF(2)), and the result is appended to the current output bits.

To consider how we can express each output bit in terms of our unknown coefficients, consider that: a*(k127*x^127 + k126*x^126 + ... + k1*x + k0) + b = k127*a*x^127 + k126*a*x^126 + .... + k1*a*x + k0*a + b. In other words, we can distribute a out to each of the individual monomials. Then, we’ll consider each monomial*a individually. Because adding polynomials will just be adding the coefficients in GF(2) for each x^i, if we define fi = ki*a*x^i, then, for state = a*(k127*x^127 + k126*x^126 + ... + k1*x + k0) + b, we have:

state[6] + state[5] + ... + state[0] = Sum(fi[6] + fi[5] + ... + fi[0]) + (b[6] + b[5] + ... + b[0]) = output[i], where the Sum is done over all 0 <= i < 128, and the addition is done in GF(2). Since fi = ki*a*x^i, fi[6] + fi[5] + ... + fi[0] = ki*((a*x^i)[6] + (a*x^i)[5] + ... + (a*x^i)[0]), meaning the previous equation gives us a linear equation in terms of ki, exactly what we wanted.

Naturally, we can extend this to subsequent states as well, since our states will look like:

1a*state + b
2(a^2)*state + a*b + b
3(a^3)*state + (a^2)*b + a*b + b
4.
5.
6.


so we can apply the same idea, treating a^i as our a from before, and b*(a^(i-1) + a^(i-2) + ... + 1) as our b from before. We can get our output 128 bits from one of p or q(skipping the first bit since it was ORed with 1), solve the system of 128 linear equations, recover key, and try using it to decrypt the flag. If it decrypts successfully, then we’re done.

Here’s this stage’s script:

 1def recover_key_from_prime(p):
2	stream = list(map(int, list(bin(p)[3:])))
3	v = [a*(x^i) for i in range(KEYLEN)] # skip the first bit
4	ext = b
5	M = []
6	vec = []
7	for j in range(KEYLEN):
8		v = [a*el for el in v]
9		ext = a*ext + b
10		M.append([int(sum(v[k][l] for l in range(7))) for k in range(KEYLEN)])
11		out = int(sum(ext[l] for l in range(7))) ^^ stream[j]
12		vec.append(out)
13	M, vec = Matrix(GF(2), M), vector(GF(2), vec)
14	key = M.solve_right(vec)
15	key = long_to_bytes(int(''.join(list(map(str, [bit for bit in key]))), 2))
16	print('got key!')
17	return key
18
19
20def recover_key_and_flag():
21	key1 = recover_key_from_prime(p)
22	key2 = recover_key_from_prime(q)
23	for key in (key1, key2):
24		try:
25			cipher = AES.new(key, AES.MODE_CBC, IV=iv)
27			print(flag)
28		except:
29			pass


and the final attack script:

  1import os
2os.environ['PWNLIB_NOTERM'] = '1'
3from pwn import *
4from Crypto.Util.number import long_to_bytes
5from Crypto.Cipher import AES
7from time import time
8
9host, port = '35.208.182.172', 6003
10r = remote(host, port)
11
12P.<x> = PolynomialRing(GF(2))
13F.<x> = P.quo(x^128 + x^7 + x^2 + x + 1)
14L.<y> = PolynomialRing(ZZ)
15
16LIMIT = 26
17e = 65537
18KEYLEN = 128
19a, b, iv, N, g, rh, enc = [None for _ in range(7)]
20
21def get_params():
22	global a, b, iv, N, g, rh, enc
23	r.recvuntil(b'a: ')
24	a = sage_eval(r.recvline().decode(), locals={'x':x})
25	r.recvuntil(b'b: ')
26	b = sage_eval(r.recvline().decode(), locals={'x':x})
27	assert a in F and b in F
28	r.recvuntil(b'iv: ')
29	iv = bytes.fromhex(r.recvline().decode())
30	r.recvuntil(b'N: ')
31	N = int(r.recvline())
32	r.recvuntil(b'e: ')
33	e = int(r.recvline())
34	r.recvuntil(b'g: ')
35	g = int(r.recvline())
36	r.recvuntil(b'r: ')
37	rh = int(r.recvline())
38	r.recvuntil(b'flag: ')
39	enc = bytes.fromhex(r.recvline().decode())
40
41
42def search_chunk(nbits, stage, cur, m):
43	m = int(m << (stage * nbits))
44	r.recvuntil(b'add something in(in hex)> ')
45	r.sendline(hex(m)[2:].encode())
46	r.recvuntil(b'flip! ')
47	res = int(r.recvline())
48	cands = [i for i in range(2**nbits)]
49	ref = {}
50	# setup
51	for cand in cands:
52		c = int(cand << (stage * nbits))
53		diff = c - (c^^m)
54		ref[diff] = cand
55	# perform search
56	for k, v in ref.items():
57		if res * pow(g, k, rh) % rh == cur:
58			return res, v
59
60
61def recover_dp_MSBs(shift):
62	dpmsbs = 0
63	CHUNKSIZE = 14
64	r.recvuntil(b'add something in(in hex)> ')
65	r.sendline(b'00')
66	r.recvuntil(b'flip! ')
67	cur = int(r.recvline())
68	m = 2**CHUNKSIZE - 1
69	for i in range(LIMIT - 1):
70		cur, chunk = search_chunk(CHUNKSIZE, i + shift, cur, m)
71		dpmsbs += chunk << (CHUNKSIZE * i)
72		print(f'completed stage {i+1}')
73	return Integer(dpmsbs)
74
75
76def factor_n_with_dpmsbs(cs, shift):
77	l = cs * shift
78	ei = inverse_mod(e, N)
79	for kp in range(1, e):
80		R = 2**l
81		A = R * d0 + ei*(kp - 1)
82		B = Matrix([
83			[R**2, R*A, 0],
84			[0, R, A],
85			[0, 0, N]])
86		B = B.LLL()
87		vec = B[0]
88		poly = (vec[0]/(R^2))*y^2 + (vec[1]/R)*y + vec[2]
89		roots = poly.roots(multiplicities=False)
90		for root in roots:
91			ff = int(A + root)
92			fac = gcd(ff, N)
93			if fac > 1 and fac != N:
94				print('found!')
95				return fac, N / fac
96
97
98def recover_key_from_prime(p):
99	stream = list(map(int, list(bin(p)[3:])))
100	v = [a*(x^i) for i in range(KEYLEN)] # skip the first bit
101	ext = b
102	M = []
103	vec = []
104	for j in range(KEYLEN):
105		v = [a*el for el in v]
106		ext = a*ext + b
107		M.append([int(sum(v[k][l] for l in range(7))) for k in range(KEYLEN)])
108		out = int(sum(ext[l] for l in range(7))) ^^ stream[j]
109		vec.append(out)
110	M, vec = Matrix(GF(2), M), vector(GF(2), vec)
111	key = M.solve_right(vec)
112	key = long_to_bytes(int(''.join(list(map(str, [bit for bit in key]))), 2))
113	print('got key!')
114	return key
115
116
117def recover_key_and_flag():
118	key1 = recover_key_from_prime(p)
119	key2 = recover_key_from_prime(q)
120	for key in (key1, key2):
121		try:
122			cipher = AES.new(key, AES.MODE_CBC, IV=iv)
124			print(flag)
125		except:
126			pass
127
128t = time()
129get_params()
130d0 = recover_dp_MSBs(12)
131print(f'Recovered in {time() - t} seconds')
132p, q = factor_n_with_dpmsbs(14, 12)
133recover_key_and_flag()


corctf{4nd_a_l1ttl3_bit_0f_gr3en_0ni0ns_on_t0p_dcca3160ef8135ea}

# leave_it_to_chance

## Challenge

Do you believe in the heart of the cards?

nc crypto.be.ax 6002

## Solution

We are provided the source file source.py, so let’s take a look at that first:

 1from Crypto.Util.number import getPrime
2from random import randrange, shuffle
3from private import flag
4
5class Game():
6	KEY_LEN = 32
7
8	def __init__(self):
9		self.p = getPrime(256)
10		while self.p % 4 == 3:
11			self.p = getPrime(256)
12		x = randrange(self.p)
13		while pow(x, (self.p-1)//2, self.p) == 1:
14			x = randrange(self.p)
15		self.a = pow(x, (self.p-1)//4, self.p)
16		self.privgen()
17		self.signed = []
18
19	def privgen(self):
20		self.priv = [randrange(self.p) for _ in range(self.KEY_LEN)]
21
22	def sign(self, m):
23		s = 0
24		for i in range(len(self.priv)):
25			s += (pow(m, i, self.p) * self.priv[i]) % self.p
26		return s
27
28	def verify(self, m, s):
29		c = self.sign(m)
30		return c**4 % self.p == s
31
32def getSig():
33	m = int(input("Enter the message you would like to sign, in hex> "), 16) % game.p
34	if m not in game.signed:
35		s = game.sign(m)
36		game.signed.append(m)
37		print(f"Signature: {hex(s**4 % game.p)[2:]}")
38		hints = [-s % game.p, s*game.a % game.p, -s*game.a % game.p]
39		shuffle(hints)
40		guess = int(input("Enter a guess for s, in hex> "), 16)
41		if guess in hints:
42			hints.remove(guess)
43		print(f"Hints: {hints[0]} {hints[1]}")
44	else:
46
47def verifyPair():
48	m = int(input("Enter m, in hex> "), 16)
49	s = int(input("Enter s, in hex> "), 16)
50	if game.verify(m, s):
51		print("Valid signature.")
52	else:
53		print("Invalid signature.")
54
55def guessPriv():
56	inp = input("Enter the private key as a list of space-separated numbers> ")
57	guess = [int(n) for n in inp.split(" ")]
58	if guess == game.priv:
59		print(f"Nice. Here's the flag: {flag}")
60	else:
61		print("No, that's wrong.")
62	exit()
63
66	print("[1] Get a signature")
67	print("[2] Verify a message")
68	print("[3] Guess the private key")
69	print("[4] Exit")
70	options = [getSig, verifyPair, guessPriv, exit]
71	choice = int(input("Choice> "))
72	if choice - 1 in range(len(options)):
73		options[choice - 1]()
74	else:
75		print("Please enter a valid choice.")
76
77game = Game()
78welcome = f"""Welcome.
79I will let you sign as many messages as you want.
80If you can guess the private key, the flag is yours.
81But you only have one chance. Make it count.
82p = {game.p}
83"""
84print(welcome)
85while True:


The private key that we want to guess is a series of 32 numbers, and we’re giving any number of chances to sign unique messages(as long as the connection does not break). Since the private key is used as the coefficients of a polynomial f(x) used in the signing of messages, we can put the end goal of the challenge as recovering f(x). Based on this, it seems like this challenge may be some variant of secret sharing.

However, we are not directly given the result of f(m) for each m that we sign; instead, we are given f(m)^4. So, it seems like we can’t directly apply lagrange interpolation on our (m, sig) pairs that we get from the server. Then, let’s turn our attention to recovering ss from the sigs that we get from the server.

### Hint system

Whenever we sign a message, we are given two hints. The hints array is initially contains the 3 numbers that are not s, but are valid values such that each raised to the 4th power also gives sig. To see this, consider:

1(-s)^4 = s^4 % p
2(s * x^((p-1)/4))^4 = s^4 * x^(p-1) = s^4 % p
3(s * (-x)^((p-1)/4))^4 = s^4 * x^(p-1) = s^4 % p


In short, they are the other roots of x^4 = sig % p. While we can calculate these 4 roots in sage easily, we don’t know which one is correct. Let’s look at the hints that we are given. If we send one of the roots guess to the server after signing, there are two scenarios:

1. guess = s. In this scenario, no hints are removed, and we receive 2 roots which are wrong as hints. We’re still left with 2 roots, unsure of which is correct.

2. guess != s. In this scenario, our guess is removed from hints, and like in scenario one, we receive 2 roots that are wrong, but we are still left with 2, unsure of which is correct.

It seems like in either scenario, we’re still left with 2 options to choose from. So it looks like we have a 50-50 scenario for getting each s value correct after receiving hints. Since we need our collection of 32 (m, s) pairs to be correct, even if we sign many messages and get 50% accurate, 50% inaccurate, to get the right f(x) recovered, it’s a (1/2)^32 chance… and since we only have 1 chance per connection, it doesn’t feel like this is a valid approach, even with spamming connections.

I mentioned that since 2 options are eliminated, it seems like we have a 50-50 to get each s value correct. However, there is something peculiar about the hint system. If we are given 2 options that are wrong, why not give them before sending a guess? In the first place, why take a guess from the user? To put what the hint system does into words, for the guess that you give, it reveals two roots that are wrong that are not guess, in either of the previously mentioned scenarios. To see why this matters, consider:

Before sending a guess, any of the 4 roots has a 1/4 chance of being s. So let’s select one as guess. Then, let’s split the 4 roots into 2 groups: 1 group that is just guess, and another group that consists of the remaining roots. Then, there is a 1/4 chance that s is in group 1, and a 3/4 chance that s is in group 2.

After we send guess, we receive two roots that are wrong as hints. Here is the important part - both of these roots will always be part of group 2, since the server never tells you if guess was wrong or right. However, the probability of s being in group 1 hasn’t changed, nor has it changed for being in group 2. In other words, the single root left over in group 2 now has a 3/4 chance of being correct. So, we can guess the actual value of s by selecting the root not in guess, hint1, hint2 with 3/4 chance. This is a very slight variation of what’s known as the Monty-Hall problem, with 4 doors(roots) instead of 3. You can read more about it here.

So, we now have a method to increase the probability that our s works. However, taking a sample of 32 and hoping that all (m, s) pairs are correct has probability (3/4)^32, which is still quite low… perhaps doable by spamming the server, but there is a more elegant way. (Also, I originally intend to add PoW to this challenge, but I forgot to tell our infra people before starting. This would discourage this solution method.) This involves using error correcting codes. The increase of probability from 50% to 75% will actually make a major difference in this, as we will see.

### Berlekamp-Welch Details

The error correcting code technique of interest is known as the Berlekamp-Welch algorithm for Reed Solomon codes. Relevant reading is here, but I will try to explain it more(?) clearly here, if the reader is interested.

Suppose that you have some polynomial f(x) of degree n-1 which you wish to find. Normally, n pairs of (m, s) is enough to recover f(x)(with unique m values, of course). However, suppose next that you know that up to k of your ss are inaccurate. If you know which (m, s) pairs are affected, then you only need to collect a total of n + k pairs, since you can then simply select the n non-affected pairs to reconstruct f(x). However, what if we don’t know which ones are affected, but still want to recover f(x) with certainty?

The Berlekamp-Welch algorithm allows you to do it as long as you receive n + 2k pairs, with up to k unknown errors. The idea is based on using an error locating polynomial, which we will call E(x). This is a polynomial of the form (x - e_1)(x - e_2)...(x - e_k), where e_i are the m values for which s is not correct. So, we can see that E(x) has degree k, and its leading coefficient is 1.

Then, the key observation is as follows: for all of the n + 2k pairs (m_i, s_i), the following equation holds:

f(m_i) * E(m_i) = s_i * E(m_i). Naturally, this is true mod p as well.

Let’s break down what this means.

• First, consider the case where (m_i, s_i) is a correct pair. Then f(m_i) = s_i, so we have s_i * E(m_i) = s_i * E(m_i). Simple enough.
• Next, consider the case where (m_i, s_i) is not a correct pair. Then m_i = e_j for some j; that is, E(m_i) = 0, since one of (x - e_1), (x - e_2), ..., (x - e_k) will evaluate to 0. Then, we have f(m_i) * 0 = s_i * 0, or 0 = 0. So, this equation is satisfied for all pairs.

Now, let’s consider the polynomial Q(x) = f(x) * E(x), from the left side of the above equation. We have already mentioned that f(x) is a degree n-1 polynomial, and E(x) is a degree k polynomial. Then, Q(x) has degree n - 1 + k. We note that Q(x) has n + k unknown coefficients a_j then, since with only our (m_i, s_i) pairs, we don’t know f(x) or E(x).

Then, consider the other side, s_i * E(x). E(x) is a polynomial of degree k, but only has k unknown coefficients b_j, as we know the leading coefficient is 1. Since all s_i are known, we are left with a total of n + 2k unknowns.

So, with n + 2k pairs, we can construct a system of n + 2k equations linear in the n + 2k unknowns, and solve for both the coefficients of Q(x) and E(x). Constructing the system of equations just has each equation look like:

a_{n+k-1} * (m_i)^(n+k-1) + a_{n+k-2} * (m_i)^(n+k-2) + .... + a_0 = s_i * ((m_i)^k + b_{k-1}^(k+1) + ... + b_0)

where your a and b values are the unknowns. Finding f(x) is then simply taking Q(x)/E(x).

Note that this method still works even if there are not exactly k errors; as long as the number of errors does not exceed k, this method will work. My intuition for this is that the previously mentioned equation at the center of this algorithm still holds even for less than k errors, and we can still treat E(x) as a k degree polynomial by treating some of the correct pairs as erroneous ones.

### Application to this Challenge

We now have a method to recover the original polynomial if we have up to certain number of errors. In our case, n = 32. However, k varies with the number of pairs we collect; if we don’t use the swapping method to get s right with 75% chance mentioned like before, then, if we call c our pair count, then k is about c/2. Then, we have the following equation:

32 + 2(c/2) = c

which has no solutions. What we are observing is that a 50% error rate is the limit for what Berlekamp-Welch cannot handle. Of course, since k is only approximately c/2, this is not guaranteed; but the closer k is to c/2, the more pairs you will need to collect; and the more pairs you collect, the closer k goes to c/2. So, unless you get quite lucky, you should not bet on the 50% chance working out. On the other hand, with a 75% success rate(and hence 25% error rate):

32 + 2(c/4) = c, which solves to c = 64, a very feasibly collectable amount of (m, s) pairs.

Here is my implementation of the attack. I used 80 pairs for a bit of leeway.

 1import os
2os.environ['PWNLIB_NOTERM'] = '1'
3from pwn import *
4
5host, port = 'crypto.be.ax', 6001
6r = remote(host, port)
7r.recvuntil(b"p = ")
8p = Integer(r.recvline())
9F = GF(p)
10R.<x> = PolynomialRing(F, 'x')
11
12def get_points(n):
13	points = []
14	for i in range(n):
15		r.recvuntil(b"Choice> ")
16		r.sendline(b"1")
17		r.recvuntil(b"sign, in hex> ")
18		r.sendline(hex(i)[2:].encode())
19		r.recvuntil(b"Signature: ")
20		sig = Integer(int(r.recvline(), 16))
21		poly = x^4 - sig
22		cands = [int(pair[0]) for pair in poly.roots()]
23		r.recvuntil(b"guess for s, in hex> ")
24		r.sendline(hex(cands[0])[2:].encode())
25		r.recvuntil(b"Hints: ")
26		line = r.recvline().decode().split(" ")
27		a, b = int(line[0]), int(line[1])
28		cands.pop(0)
29		cands.remove(a)
30		cands.remove(b)
31		points.append((i, Integer(cands[0])))
32	return points
33
34def get_matrix_and_b(n, k, points):
35	M, b = [], []
36	dQ = n + k - 1
37	for point in points:
38		r = []
39		for j in range(dQ + 1):
40			r.append(F(point[0])^j)
41		for j in range(k):
42			r.append(-F(point[1]) * F(point[0])^j)
43		M.append(r)
44		b.append(point[1] * F(point[0])^k)
45	M = Matrix(F, M)
46	b = vector(F, b)
47	return M, b
48
49def get_privkey(a, n, k):
50	Q = a[0]
51	for i in range(1, n + k):
52		Q += a[i]*x^i
53	E = a[n + k]
54	for i in range(1, k):
55		E += a[n + k + i]*x^i
56	E += x^k
57	P = Q / E
58	return P.numerator().list()
59
60def getflag(pay):
61	r.recvuntil(b"Choice> ")
62	r.sendline(b"3")
63	r.recvuntil(b"numbers> ")
64	r.sendline(pay.encode())
65	r.interactive()
66
67points = get_points(80)
68n, k = 32, len(points) // 4
69M, b = get_matrix_and_b(n, k, points)
70a = M.solve_right(b)
71priv = get_privkey(a, n, k)
72pay = ' '.join([str(v) for v in priv])
73getflag(pay)


corctf{wh0_n3eds_gue551ng_wh3n_y0u_have_l1ne4r_al6ebr4_526d95eadb9686bb}

Thanks to all the players who tried out crypto challenges. Hope you enjoyed!