corCTF 2021 - Crypto Challenge Writeups

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:
 4	toks = f.read().strip().split()
 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

Author: qopruzjf

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

Author: qopruzjf

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
 5flag = open('flag.txt').read()
 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
 5flag = bytes_to_long(open("flag.txt", "rb").read())
 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)))

babypad

Author: willwam845

padding makes everything secure right

server.py

 1from Crypto.Cipher import AES
 2from Crypto.Util import Counter
 3from Crypto.Util.Padding import pad, unpad
 4from Crypto.Util.number import bytes_to_long
 5import os
 6
 7flag = open("/challenge/flag.txt").read().encode()
 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)
23    unpad(pt, 16)
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 *
 2from Crypto.Util.Padding import unpad
 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  
55print(unpad(flag, 16).decode())
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
 4from Crypto.Util.Padding import pad
 5from hashlib import sha256
 6from os import urandom
 7
 8flag = open("flag.txt", "rb").read()
 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()}'")
27print(f"ct = '{cipher.encrypt(pad(flag, 16)).hex()}'")

output.txt

c1 = 5365904711205493895182988721055598679508066289977091231731349423996531384326997250984304389796311073201846992254794801346573036775490182780952712232258774
c2 = 2351499357088933835557969576916974229915931074692169825269157710226395480997304497294813272746195475744137017453323338362896396977337638862808560417575150
p = 12118911800929768381158064532151564397584328623097191996086479213117076586014730135201334840794700976422626122702191630484231703678287738839516304757792517
iv = 'eacdfb3c2cd33a8ce71dbd9a11be89ad'
ct = 'ed36d8614dd35af75251496eef0bb76582dfb83cde59715df41150054be51ac15aaee8eb540a7dbbe58a6fae8287bd9e69043a4800a1e36055d415fd3f41735d3673b3dd5fbdd21941c48ac24ef9b1e288a8848c94e85cd1bda569d2a87c8f33bc790d9aaf97eed583d35a84cc75655cba591d3da9fa3c6e681a2727f2786ffccab3866006cda27d355d8d0665a88a24815b0133a2ff2c8541bc636ac2cc97e03b6189227d3b5469f736ce7373789809de794f987cfe437be56dbb32444055e23023ccd900934ed853ceb3cbac58775a3b7b1c9f3c5a0a32f273ae30ab8a8a9bf24585c39041c262820343eef64735636450dd8628f8a830e109ae3b2b05bef150c98a417b6632ca00c96ee544853955dc948d28dfff28071c5182656fa2ae56614207b9cd96b40cbe28e20bac396577272d341b86ff242daa904e67f226180a02cd2197f8dafda1dd325437e36e457802cefb692bcf0fe9a38addf1d493bd2d40bb972ceff8337fa81a7b9a29ebc6959617a6370b97b90ef8df90e0ea780a0aaea3affa6d7be74118328ca8e3eb060a5afce6f07487ad841382ee82018ba3f452b7f1a0968606739380572364fdfb3a8dac1ca8f856b4aaafbe9c45ad1f81c30f41606e8228ca59482c191af4ecb4f426863dbdbaf76e97a7f5867647e77837dc1b3c843e1a182cf9463f2215afae0d84f975da68d508ca05117de5f5f21a3d818e45cb7612ab052a36edbd7a2386e26777f597c524be57aad5ad254f8b6caa1cc8182d84e8d5a36ea9c5528f4152edb7ce4b5e58529787862a1e9736b2ab135b914835a72fced8485f736a0d7f18bf3d923c66b4c0acede868a3b3970b322675c85dbaf92b985d47bee0ffc18a7a2827dcf449d304d11fb9265d6367e55891f006ab3313a3df6da8c46f6f736b91f31c9c90b782af9a3a527c25f608a0e2ed62d019839587b647b05697c83f3ffafc10d545c8dfc7516e284ab572cd8216b7dcda698eb979f1cd23ba757bc865b51adb337b61bbb682a52fad42741f559a77d863b2ef8af02a8f7776819b02c9b10123c999f626bb563372e9ff141dbc4ac619c52f5a0e245f873b6cadc324e2ed62c6f1858beb8988cfdeb1fa1b223cd1b2ae295c032aa58b46d12c6ace4515561bfb8276ea4b6536aec2b42cfbb64eb30f39d3e79d220da29cd46bd1c8cca85f6c11a8c1b2c265099d51d10651444eea0bbbb556a8de4bf0df8cf9904f4dc7f7840f82a7b4101b7ff499d6f619555c906ce7381c7fe4f165330d76cda4e36ff421a402b1b8bcfcbbc5c80c71ccc9814996723ba4f30f52537bf99547af16bf51bcc6795f7f2cbbf67b0cd0d8d432ff77d17758af8e6309915f152cab18c56495a0b82bdbeb96386a44bb761ee3da3c262d6eb69ee03cc5acbbac45dda3b75a863508bbab3aac1ec8371c1b62753d9a1931c2e8285295902edec528384264c4ccc2d0f9073eae44b81355b82df39f142d3fc5df63e668ea9c6375bea7ee9685830ae39a64ad30af300b4e56fe10b8cd0b0e03488828af68e6fa03f05bc8c38d12c9025e35767f22d67668d081e9827dbe2cfa6ad29d7d7e5bc88135fad55550406226c0c71f16dc901211475e35b8ad97827ee1d0dc3c015b326f884dd3dd8792864a093f73b68169f206606225c85c28af07cd27e35d6b738307629ef71160ac7717f42f0ad26a5f0ddb0aa8940fc72fd054efffe96bb2b5d3d2c68939b256650f9c3db146b69c0a5749b130424a069a2d75b0df890b86c00af1704dbb3f891dea94c152406c1fa636fce8e96db8e4db3f1f4ba2634fd9344664b788b4289acadb0bc543b65018572503d34227ab3ffbce86247cb740dca70c73c85ac29aa646b760314acd0838f0048728cedec961711c2c7f339ea816411cb87ffbc13a7a3e533505df4ac45357b7e002979496343647e33f6d5becfc3c02e357985708f817ea39b9db2cee18af34fe0f93662120e5c496bce6d39f9fc46ef6817f4183227391d73f815cfdbc3a1c58b554b4407a7dfada42945dff9d5f500b8ba588f20f6db575754bada30049a234ea503147cbaf4de8c72f451bd1c47a51d87f9bebf9e738a631863e01ffe7f32e2b620a17ec373acab84eaa0f02a7656a2d39a405c43e770b46c990230b921d9a1e6c38b45ed14011216a41880149eb2392ed7c8e88568f0bcf0e406f91b9ef98adb59bfc45504b6766074058005c059d1422cf7c343fdc88195977e106b42fcf41e95743ced2a670371013ac4cc86e412d7ee9692e0beb540198ab2661fbeebb38be431811f4ab129eb406fa4d6ab2904848941798ab042b0a05622099cf8244045dc4e0006ed30ada599e2f32cc2e474ed836176e7f5e26488295179b67aca112246d63c7a17a86a087087f39c0abce7fbeed200be9daa6cf638685c3feeb5ec265a3f8fd8ae5ad1f86fc08750b636860b1b8bdc309c31da8278f28e7e3326791998f2e74b88da31ad1090156b182b2d11a1fff2dc43a238b1b103519124ed8db6407525d9da8e3773e7652e4b11978ec0d7df57832d96970ec790a11883428a585d6650f13f37c90679aead37055351fd7852472a19bc5d9df2841fada9fbefd432ea15c548924e477642a04c93b681e1326469aa8919262517cee53657134d9effc3bf68752f7ebfb87862cf34e585b1baacbe73062764915d5d6db44a386473ea07cc13d42260aae8919720ccae0e80e09decec61c5c741fd255b5e789734d9a7b86a2500c9b50c009f6b4b96d832a9ddc1695efeb21a7de77b61eadaa4406e0ae58facd6d6b5f4b4b736a335046dadab07d23b4c171270f2e3f0c29154c2dcd10085999106301069f292402a0fc3d0ba19677b921bd70e7bbc501e7bec663dee6aaa2f6cf62cfa3ee268d57721dfb71ff95301514d404e38b67c2753aa4ab4e4be9949fa495c1fc61143b4c4563021bacbb051bdf9419cddaf0e0015655a46fb53a4c7452a0f15ae9fa45cd8bdfab768456912f6cba7ad066ca493714db1abd1625c3d6971264143fe4ef2513e4c4b6f229272271edb8998ad0a9c3e0ed41a792c22b75c6a4c87d37f7b0aa600fb903857453ee137d880e09882535e8e51d719f5ca83d0fa01d71b5115c9190ae95eaafed8a272f9abd5e040aad5042bfbf7399a6f7f2f6932e9ce8ddb856663c6177864cdae1a7d116bb258de586e621b399e870f3909acdbbcbe4fa6f9f2fcb605ed250e11f43fc3c8645ed980d94a5d3a14aab60ba5725a363f845566f170eede27a65a0a2a30865c22aa7d5cafe0ea3252645b8086f3a5443bb8c869990446ddb34e73b99d1d6cb8cdc9c69b94d20785ffde8ad38f92319d56e90a4569d235581656f6f2df761fb792833b4e72207e157841bcc99b3860abfb37f76dd77615420988e1702751e11aa5579e9f1987f3519bfb0fcf835d63b825f9128db50c8c1eccc88a64b4df432c72654371154884c54abc2c5b31693de5265c685dc7e0eeb10bcdca698bfb75016b1dfec2ece20ec4951fd338775d239db1663f63b328d6c6a0415f35f23cffae21a9db195118f22083c5fcbd7192cfa611748cb79486ab78b16b0f1b8d5e81410b0213ff6f603dec71909c6b07bf12618551e4f9c8eaf7346c890b4c10c02970011242a9c57933cdff2526985c0009341474f7d18d197558585feca1cb0030afc784906b45bef19d4cc32b0ae289a08a3eadad86e512100dde8a85d8ab9cc5740cd2e58848b56b7f07defeb43d28aaa6e5a7e46a221323a928088743845b6dc669868634117a50759e5f144f35297374f79e6059a159ca0596fb26273a219fcdc9e5c56a2b9efa0fe392cf54b0c'

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
52iv = 'eacdfb3c2cd33a8ce71dbd9a11be89ad'
53ct = 'ed36d8614dd35af75251496eef0bb76582dfb83cde59715df41150054be51ac15aaee8eb540a7dbbe58a6fae8287bd9e69043a4800a1e36055d415fd3f41735d3673b3dd5fbdd21941c48ac24ef9b1e288a8848c94e85cd1bda569d2a87c8f33bc790d9aaf97eed583d35a84cc75655cba591d3da9fa3c6e681a2727f2786ffccab3866006cda27d355d8d0665a88a24815b0133a2ff2c8541bc636ac2cc97e03b6189227d3b5469f736ce7373789809de794f987cfe437be56dbb32444055e23023ccd900934ed853ceb3cbac58775a3b7b1c9f3c5a0a32f273ae30ab8a8a9bf24585c39041c262820343eef64735636450dd8628f8a830e109ae3b2b05bef150c98a417b6632ca00c96ee544853955dc948d28dfff28071c5182656fa2ae56614207b9cd96b40cbe28e20bac396577272d341b86ff242daa904e67f226180a02cd2197f8dafda1dd325437e36e457802cefb692bcf0fe9a38addf1d493bd2d40bb972ceff8337fa81a7b9a29ebc6959617a6370b97b90ef8df90e0ea780a0aaea3affa6d7be74118328ca8e3eb060a5afce6f07487ad841382ee82018ba3f452b7f1a0968606739380572364fdfb3a8dac1ca8f856b4aaafbe9c45ad1f81c30f41606e8228ca59482c191af4ecb4f426863dbdbaf76e97a7f5867647e77837dc1b3c843e1a182cf9463f2215afae0d84f975da68d508ca05117de5f5f21a3d818e45cb7612ab052a36edbd7a2386e26777f597c524be57aad5ad254f8b6caa1cc8182d84e8d5a36ea9c5528f4152edb7ce4b5e58529787862a1e9736b2ab135b914835a72fced8485f736a0d7f18bf3d923c66b4c0acede868a3b3970b322675c85dbaf92b985d47bee0ffc18a7a2827dcf449d304d11fb9265d6367e55891f006ab3313a3df6da8c46f6f736b91f31c9c90b782af9a3a527c25f608a0e2ed62d019839587b647b05697c83f3ffafc10d545c8dfc7516e284ab572cd8216b7dcda698eb979f1cd23ba757bc865b51adb337b61bbb682a52fad42741f559a77d863b2ef8af02a8f7776819b02c9b10123c999f626bb563372e9ff141dbc4ac619c52f5a0e245f873b6cadc324e2ed62c6f1858beb8988cfdeb1fa1b223cd1b2ae295c032aa58b46d12c6ace4515561bfb8276ea4b6536aec2b42cfbb64eb30f39d3e79d220da29cd46bd1c8cca85f6c11a8c1b2c265099d51d10651444eea0bbbb556a8de4bf0df8cf9904f4dc7f7840f82a7b4101b7ff499d6f619555c906ce7381c7fe4f165330d76cda4e36ff421a402b1b8bcfcbbc5c80c71ccc9814996723ba4f30f52537bf99547af16bf51bcc6795f7f2cbbf67b0cd0d8d432ff77d17758af8e6309915f152cab18c56495a0b82bdbeb96386a44bb761ee3da3c262d6eb69ee03cc5acbbac45dda3b75a863508bbab3aac1ec8371c1b62753d9a1931c2e8285295902edec528384264c4ccc2d0f9073eae44b81355b82df39f142d3fc5df63e668ea9c6375bea7ee9685830ae39a64ad30af300b4e56fe10b8cd0b0e03488828af68e6fa03f05bc8c38d12c9025e35767f22d67668d081e9827dbe2cfa6ad29d7d7e5bc88135fad55550406226c0c71f16dc901211475e35b8ad97827ee1d0dc3c015b326f884dd3dd8792864a093f73b68169f206606225c85c28af07cd27e35d6b738307629ef71160ac7717f42f0ad26a5f0ddb0aa8940fc72fd054efffe96bb2b5d3d2c68939b256650f9c3db146b69c0a5749b130424a069a2d75b0df890b86c00af1704dbb3f891dea94c152406c1fa636fce8e96db8e4db3f1f4ba2634fd9344664b788b4289acadb0bc543b65018572503d34227ab3ffbce86247cb740dca70c73c85ac29aa646b760314acd0838f0048728cedec961711c2c7f339ea816411cb87ffbc13a7a3e533505df4ac45357b7e002979496343647e33f6d5becfc3c02e357985708f817ea39b9db2cee18af34fe0f93662120e5c496bce6d39f9fc46ef6817f4183227391d73f815cfdbc3a1c58b554b4407a7dfada42945dff9d5f500b8ba588f20f6db575754bada30049a234ea503147cbaf4de8c72f451bd1c47a51d87f9bebf9e738a631863e01ffe7f32e2b620a17ec373acab84eaa0f02a7656a2d39a405c43e770b46c990230b921d9a1e6c38b45ed14011216a41880149eb2392ed7c8e88568f0bcf0e406f91b9ef98adb59bfc45504b6766074058005c059d1422cf7c343fdc88195977e106b42fcf41e95743ced2a670371013ac4cc86e412d7ee9692e0beb540198ab2661fbeebb38be431811f4ab129eb406fa4d6ab2904848941798ab042b0a05622099cf8244045dc4e0006ed30ada599e2f32cc2e474ed836176e7f5e26488295179b67aca112246d63c7a17a86a087087f39c0abce7fbeed200be9daa6cf638685c3feeb5ec265a3f8fd8ae5ad1f86fc08750b636860b1b8bdc309c31da8278f28e7e3326791998f2e74b88da31ad1090156b182b2d11a1fff2dc43a238b1b103519124ed8db6407525d9da8e3773e7652e4b11978ec0d7df57832d96970ec790a11883428a585d6650f13f37c90679aead37055351fd7852472a19bc5d9df2841fada9fbefd432ea15c548924e477642a04c93b681e1326469aa8919262517cee53657134d9effc3bf68752f7ebfb87862cf34e585b1baacbe73062764915d5d6db44a386473ea07cc13d42260aae8919720ccae0e80e09decec61c5c741fd255b5e789734d9a7b86a2500c9b50c009f6b4b96d832a9ddc1695efeb21a7de77b61eadaa4406e0ae58facd6d6b5f4b4b736a335046dadab07d23b4c171270f2e3f0c29154c2dcd10085999106301069f292402a0fc3d0ba19677b921bd70e7bbc501e7bec663dee6aaa2f6cf62cfa3ee268d57721dfb71ff95301514d404e38b67c2753aa4ab4e4be9949fa495c1fc61143b4c4563021bacbb051bdf9419cddaf0e0015655a46fb53a4c7452a0f15ae9fa45cd8bdfab768456912f6cba7ad066ca493714db1abd1625c3d6971264143fe4ef2513e4c4b6f229272271edb8998ad0a9c3e0ed41a792c22b75c6a4c87d37f7b0aa600fb903857453ee137d880e09882535e8e51d719f5ca83d0fa01d71b5115c9190ae95eaafed8a272f9abd5e040aad5042bfbf7399a6f7f2f6932e9ce8ddb856663c6177864cdae1a7d116bb258de586e621b399e870f3909acdbbcbe4fa6f9f2fcb605ed250e11f43fc3c8645ed980d94a5d3a14aab60ba5725a363f845566f170eede27a65a0a2a30865c22aa7d5cafe0ea3252645b8086f3a5443bb8c869990446ddb34e73b99d1d6cb8cdc9c69b94d20785ffde8ad38f92319d56e90a4569d235581656f6f2df761fb792833b4e72207e157841bcc99b3860abfb37f76dd77615420988e1702751e11aa5579e9f1987f3519bfb0fcf835d63b825f9128db50c8c1eccc88a64b4df432c72654371154884c54abc2c5b31693de5265c685dc7e0eeb10bcdca698bfb75016b1dfec2ece20ec4951fd338775d239db1663f63b328d6c6a0415f35f23cffae21a9db195118f22083c5fcbd7192cfa611748cb79486ab78b16b0f1b8d5e81410b0213ff6f603dec71909c6b07bf12618551e4f9c8eaf7346c890b4c10c02970011242a9c57933cdff2526985c0009341474f7d18d197558585feca1cb0030afc784906b45bef19d4cc32b0ae289a08a3eadad86e512100dde8a85d8ab9cc5740cd2e58848b56b7f07defeb43d28aaa6e5a7e46a221323a928088743845b6dc669868634117a50759e5f144f35297374f79e6059a159ca0596fb26273a219fcdc9e5c56a2b9efa0fe392cf54b0c'
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

Author: qopruzjf

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')
48r.recvuntil(b'Enter your bill: ')
49r.sendline(mybill.encode())
50r.interactive()

mystery_stream

Author: qopruzjf

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:
26		txt = f.read()
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:
47		pt = f.read()
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:
35	ct = f.read()
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

Author: qopruzjf

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
 5from Crypto.Util.Padding import pad
 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)
53print('encrypted flag:', cipher.encrypt(pad(flag, 16)).hex())
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.