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:
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89][::-1]
with open('flag.enc', 'r') as f:
toks = f.read().strip().split()
for tok in toks:
n = 0
for i in range(len(tok)):
if tok[i] == '1':
n += fib[i]
print(chr(n), end='')
print()
I heard 4096 bit RSA is secure, so I encrypted the flag with it.
Let's take a look at source.py
.
from Crypto.Util.number import getPrime, bytes_to_long
from private import flag
def prod(lst):
ret = 1
for num in lst:
ret *= num
return ret
m = bytes_to_long(flag)
primes = [getPrime(32) for _ in range(128)]
n = prod(primes)
e = 65537
print(n)
print(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:
from Crypto.Util.number import long_to_bytes
n = 459885975247015080805640556741011516977197329640766993963868420109797926433366540892987268841395390677003815083264385212101691633439322325099797177448692622480464621078335184219389796838162276766514601933466475468401515898684493274917613994100522239975168457673847893881262044268360912988376575672476171112591298760495756557513258957047691316107068789781127778556052622156938314563686550649890013123308529462323524956343976590389389598189062535997792610595692423958859734240408888038654268044525127233802930885203114382004407420679618854820752321423652210263026002674421004459358125628893165197704730466465357733250277754582116729335454780585183881507464319371872816864390937163980938342321213464267167886221361565606170274949413010811340309217975928566961337873662243232735415505259424592138609448552846032645740285154650705912665026491380837092800272560626482253083963281523307784385386183075753783677135489658756755609520313684847611300385005067351044518651327694437586779518531321476281945821098370942775037752436793514318106103039341369024642099069559532445745414503597893184762282819390252433279093193434255143378230817111136472977731464704181932470261447745719555587426871560009788187914276773536835263029421459
c = 28755115299447380219865175141510816277127168995053017865115990550984575125799683185050702823351567348600828299072471787373507105523347305190934990188579267752586087083593225747175981684997138309755745359524509032537903919777044868871605615082163195170687980598583706842782998787213163456976487674758299135192443422599601908006134268958490155310804660685217691260626978944786030603741681463537491343107154880830022752091923044127859420510244685212654149762222514692807085300768408438515214359180426754805425610056804647793212776220975050809958444765557485627572244455567542349113285436767315494336729564478949697782757093180889501388671840393906428863764844923821078129810082488811253658252080197407107745563251321553018503591423447398679152763318675601718545686288006911301792697520238398588188160613822537782998910198317606647548568160063550153871090661536552353526398962780934555640261433391205589034576219843858289208904106775652085670099705038854877624295738691647401202134659947562445654410163435449737035924690998038213621986164097914575256877909759645573588363096065366890651919757816350994847106221042650232103061907896322357719105163758442738521889967022959871387866183293407447159616199193109243274307191759
def prod(lst):
ret = 1
for num in lst:
ret *= num
return ret
fs = ecm.factor(n)
fs = [p - 1 for p in fs]
phi = prod(fs)
e = 65537
d = pow(e, -1, phi)
print(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.
I won't give you the secret. But, I'll let you divide it.
nc crypto.be.ax 6000
Let's take a look at the provided server.py
.
from Crypto.Util.number import bytes_to_long, getStrongPrime
from random import randrange
from secret import flag
LIMIT = 64
def gen():
p = getStrongPrime(512)
g = randrange(1, p)
return g, p
def main():
g, p = gen()
print("g:", str(g))
print("p:", str(p))
x = bytes_to_long(flag)
enc = pow(g, x, p)
print("encrypted flag:", str(enc))
ctr = 0
while ctr < LIMIT:
try:
div = int(input("give me a number> "))
print(pow(g, x // div, p))
ctr += 1
except:
print("whoops..")
return
print("no more tries left... bye")
main()
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:
from pwn import *
from Crypto.Util.number import long_to_bytes
LIMIT = 64
host, port = 'crypto.be.ax' , 6000
def get_params(r):
r.recvuntil(b'g: ')
g = int(r.recvline())
r.recvuntil(b'p: ')
p = int(r.recvline())
return g, p
div = 1
flag_bits = ''
while True:
r = remote(host, port)
g, p = get_params(r)
while pow(g, (p-1) // 2, p) == 1:
r.close()
r = remote(host, port)
g, p = get_params(r)
for _ in range(LIMIT):
r.recvuntil(b'give me a number> ')
r.sendline(str(div).encode())
res = int(r.recvline())
if pow(res, (p-1) // 2, p) == 1:
flag_bits = '0' + flag_bits
else:
flag_bits = '1' + flag_bits
div *= 2
cur = long_to_bytes(int(flag_bits, 2))
if b'corctf' in cur:
print(cur)
r.close()
exit()
r.close()
corctf{qu4drat1c_r3s1due_0r_n0t_1s_7h3_qu3st1on8852042051e57492}
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
.
from Crypto.Util.number import getPrime, long_to_bytes
from pwn import *
import random, binascii
flag = open('flag.txt').read()
def v(p, k):
ans = 0
while k % p == 0:
k /= p
ans += 1
return ans
p, q, r = getPrime(2048), getPrime(2048), getPrime(2048)
print(p, q, r)
n = pow(p, q) * r
a1 = random.randint(0, n)
a2 = n - a1
assert a1 % p != 0 and a2 % p != 0
t = pow(a1, n) + pow(a2, n)
print(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.
discord is the best place to store secrets
babyrsa.png
script.py
from Crypto.Util.number import bytes_to_long
n = 73542616560647877565544036788738025202939381425158737721544398356851787401183516163221837013929559568993844046804187977705376289108065126883603562904941748653607836358267359664041064708762154474786168204628181667371305788303624396903323216279110685399145476916585122917284319282272004045859138239853037072761
e = 0x10001
flag = bytes_to_long(open("flag.txt", "rb").read())
print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {pow(flag, e, n)}")
print("""
Transcription of image:
735426165606478775655440367887380252029393814251587377215443983568517874011835161632
289108065126883603562904941748653607836358267359664041064708762154474786168204628181
9145476916585122917284319282272004045859138239853037072761
108294440701045353595867242719660522374526250640690193563048263854806748525172379331
341078269246532299656864881223
679098724593514422867704492870375465007225641192338424726642090768164214390632598250
39563231146143146482074105407
(n, p, q)
""")
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.
from Crypto.Util.number import long_to_bytes
n = 73542616560647877565544036788738025202939381425158737721544398356851787401183516163221837013929559568993844046804187977705376289108065126883603562904941748653607836358267359664041064708762154474786168204628181667371305788303624396903323216279110685399145476916585122917284319282272004045859138239853037072761
P.<x> = PolynomialRing(Zmod(n), implementation='NTL')
poly = 108294440701045353595867242719660522374526250640690193563048263854806748525172379331 * 10^71 + x * 10^30 + 341078269246532299656864881223
f = poly.monic()
d_p = f.small_roots(X=10^41, beta=41/155)[0]
p = int(poly(d_p))
q = n // p
assert p * q == n
e = 65537
ct = 2657054880167593054409755786316190176139048369036893368834913798649283717358246457720021168590230987384201961744917278479195838455294205306264398417522071058105245210332964380113841646083317786151272874874267948107036095666198197073147087762030842808562672646078089825632314457231611278451324232095496184838
d = pow(e, -1, (p-1)*(q-1))
print(long_to_bytes(pow(ct,d,n)))
padding makes everything secure right
server.py
from Crypto.Cipher import AES
from Crypto.Util import Counter
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import bytes_to_long
import os
flag = open("/challenge/flag.txt").read().encode()
key = os.urandom(16)
def encrypt(pt):
iv = os.urandom(16)
ctr = Counter.new(128, initial_value=bytes_to_long(iv))
cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
return iv + cipher.encrypt(pad(pt, 16))
def decrypt(ct):
try:
iv = ct[:16]
ct = ct[16:]
ctr = Counter.new(128, initial_value=bytes_to_long(iv))
cipher = AES.new(key, AES.MODE_CTR, counter=ctr)
pt = cipher.decrypt(ct)
unpad(pt, 16)
return 1
except Exception as e:
return 0
def main():
print(encrypt(flag).hex())
while True:
try:
print(decrypt(bytes.fromhex(input("> "))))
except Exception as e:
pass
main()
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.
from pwn import *
from Crypto.Util.Padding import unpad
import time
s = remote(sys.argv[1],int(sys.argv[2])) #, level='debug')
ct = bytes.fromhex(s.recvline().decode())
t = time.time()
def bxor(ba1,ba2):
return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])
def query(msg):
s.sendlineafter(b">", msg.hex())
if int(s.recvline().decode()):
return 1
else:
return 0
def brute(b, iv, p1, p2, block, ct):
if query(iv + p1[:-1] + bytes([b]) + p2) and ((block+16) < len(ct) or b != ct[-1]):
return True
return False
assert query(ct)
assert not query(b'\x00'*32)
flag = b''
for block in range(16, len(ct), 16):
iv = ct[:block]
p1 = ct[block:block+16]
p2 = b""
i = 1
for i in range (1, 16):
b1, b2 = 0, 128
if p1[-1] >= 128:
b1, b2 = 128, 256
for byte in range(b1, b2):
print(i, byte)
if brute(byte, iv, p1, p2, block, ct):
p2 = bytes([byte]) + p2
p2 = bxor(p2, bytes([i]) * i)
p2 = bxor(p2, bytes([i+1]) * i)
p1 = p1[:-1]
print(i, byte)
break
for byte in range(256):
if query(iv + bytes([byte]) + p2):
p2 = bytes([byte]) + p2
break
flag += (bxor(bxor(p2, b'\x10' * 16), ct[block:block+16]))
print(flag)
print(unpad(flag, 16).decode())
print(f"Solved in {time.time() - t} seconds")
you can't break an lcg with only 2 outputs right
script.py
from random import randrange
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from os import urandom
flag = open("flag.txt", "rb").read()
def und():
p = getPrime(512)
x = randrange(p)
a = p ^ x ^ randrange(2**200)
b = p ^ x ^ randrange(2**200)
return p, a, b, x
p,a,b,x = und()
iv = urandom(16)
key = sha256(long_to_bytes(a) + long_to_bytes(b)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
print(f"c1 = {x}")
print(f"c2 = {(x*a + b) % p}")
print(f"p = {p}")
print(f"iv = '{iv.hex()}'")
print(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.
# from https://github.com/defund/coppersmith
import itertools
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m+1):
base = N^(m-i) * f^i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1/factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B*monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
c1 = 5365904711205493895182988721055598679508066289977091231731349423996531384326997250984304389796311073201846992254794801346573036775490182780952712232258774
c2 = 2351499357088933835557969576916974229915931074692169825269157710226395480997304497294813272746195475744137017453323338362896396977337638862808560417575150
p = 12118911800929768381158064532151564397584328623097191996086479213117076586014730135201334840794700976422626122702191630484231703678287738839516304757792517
iv = 'eacdfb3c2cd33a8ce71dbd9a11be89ad'
ct = 'ed36d8614dd35af75251496eef0bb76582dfb83cde59715df41150054be51ac15aaee8eb540a7dbbe58a6fae8287bd9e69043a4800a1e36055d415fd3f41735d3673b3dd5fbdd21941c48ac24ef9b1e288a8848c94e85cd1bda569d2a87c8f33bc790d9aaf97eed583d35a84cc75655cba591d3da9fa3c6e681a2727f2786ffccab3866006cda27d355d8d0665a88a24815b0133a2ff2c8541bc636ac2cc97e03b6189227d3b5469f736ce7373789809de794f987cfe437be56dbb32444055e23023ccd900934ed853ceb3cbac58775a3b7b1c9f3c5a0a32f273ae30ab8a8a9bf24585c39041c262820343eef64735636450dd8628f8a830e109ae3b2b05bef150c98a417b6632ca00c96ee544853955dc948d28dfff28071c5182656fa2ae56614207b9cd96b40cbe28e20bac396577272d341b86ff242daa904e67f226180a02cd2197f8dafda1dd325437e36e457802cefb692bcf0fe9a38addf1d493bd2d40bb972ceff8337fa81a7b9a29ebc6959617a6370b97b90ef8df90e0ea780a0aaea3affa6d7be74118328ca8e3eb060a5afce6f07487ad841382ee82018ba3f452b7f1a0968606739380572364fdfb3a8dac1ca8f856b4aaafbe9c45ad1f81c30f41606e8228ca59482c191af4ecb4f426863dbdbaf76e97a7f5867647e77837dc1b3c843e1a182cf9463f2215afae0d84f975da68d508ca05117de5f5f21a3d818e45cb7612ab052a36edbd7a2386e26777f597c524be57aad5ad254f8b6caa1cc8182d84e8d5a36ea9c5528f4152edb7ce4b5e58529787862a1e9736b2ab135b914835a72fced8485f736a0d7f18bf3d923c66b4c0acede868a3b3970b322675c85dbaf92b985d47bee0ffc18a7a2827dcf449d304d11fb9265d6367e55891f006ab3313a3df6da8c46f6f736b91f31c9c90b782af9a3a527c25f608a0e2ed62d019839587b647b05697c83f3ffafc10d545c8dfc7516e284ab572cd8216b7dcda698eb979f1cd23ba757bc865b51adb337b61bbb682a52fad42741f559a77d863b2ef8af02a8f7776819b02c9b10123c999f626bb563372e9ff141dbc4ac619c52f5a0e245f873b6cadc324e2ed62c6f1858beb8988cfdeb1fa1b223cd1b2ae295c032aa58b46d12c6ace4515561bfb8276ea4b6536aec2b42cfbb64eb30f39d3e79d220da29cd46bd1c8cca85f6c11a8c1b2c265099d51d10651444eea0bbbb556a8de4bf0df8cf9904f4dc7f7840f82a7b4101b7ff499d6f619555c906ce7381c7fe4f165330d76cda4e36ff421a402b1b8bcfcbbc5c80c71ccc9814996723ba4f30f52537bf99547af16bf51bcc6795f7f2cbbf67b0cd0d8d432ff77d17758af8e6309915f152cab18c56495a0b82bdbeb96386a44bb761ee3da3c262d6eb69ee03cc5acbbac45dda3b75a863508bbab3aac1ec8371c1b62753d9a1931c2e8285295902edec528384264c4ccc2d0f9073eae44b81355b82df39f142d3fc5df63e668ea9c6375bea7ee9685830ae39a64ad30af300b4e56fe10b8cd0b0e03488828af68e6fa03f05bc8c38d12c9025e35767f22d67668d081e9827dbe2cfa6ad29d7d7e5bc88135fad55550406226c0c71f16dc901211475e35b8ad97827ee1d0dc3c015b326f884dd3dd8792864a093f73b68169f206606225c85c28af07cd27e35d6b738307629ef71160ac7717f42f0ad26a5f0ddb0aa8940fc72fd054efffe96bb2b5d3d2c68939b256650f9c3db146b69c0a5749b130424a069a2d75b0df890b86c00af1704dbb3f891dea94c152406c1fa636fce8e96db8e4db3f1f4ba2634fd9344664b788b4289acadb0bc543b65018572503d34227ab3ffbce86247cb740dca70c73c85ac29aa646b760314acd0838f0048728cedec961711c2c7f339ea816411cb87ffbc13a7a3e533505df4ac45357b7e002979496343647e33f6d5becfc3c02e357985708f817ea39b9db2cee18af34fe0f93662120e5c496bce6d39f9fc46ef6817f4183227391d73f815cfdbc3a1c58b554b4407a7dfada42945dff9d5f500b8ba588f20f6db575754bada30049a234ea503147cbaf4de8c72f451bd1c47a51d87f9bebf9e738a631863e01ffe7f32e2b620a17ec373acab84eaa0f02a7656a2d39a405c43e770b46c990230b921d9a1e6c38b45ed14011216a41880149eb2392ed7c8e88568f0bcf0e406f91b9ef98adb59bfc45504b6766074058005c059d1422cf7c343fdc88195977e106b42fcf41e95743ced2a670371013ac4cc86e412d7ee9692e0beb540198ab2661fbeebb38be431811f4ab129eb406fa4d6ab2904848941798ab042b0a05622099cf8244045dc4e0006ed30ada599e2f32cc2e474ed836176e7f5e26488295179b67aca112246d63c7a17a86a087087f39c0abce7fbeed200be9daa6cf638685c3feeb5ec265a3f8fd8ae5ad1f86fc08750b636860b1b8bdc309c31da8278f28e7e3326791998f2e74b88da31ad1090156b182b2d11a1fff2dc43a238b1b103519124ed8db6407525d9da8e3773e7652e4b11978ec0d7df57832d96970ec790a11883428a585d6650f13f37c90679aead37055351fd7852472a19bc5d9df2841fada9fbefd432ea15c548924e477642a04c93b681e1326469aa8919262517cee53657134d9effc3bf68752f7ebfb87862cf34e585b1baacbe73062764915d5d6db44a386473ea07cc13d42260aae8919720ccae0e80e09decec61c5c741fd255b5e789734d9a7b86a2500c9b50c009f6b4b96d832a9ddc1695efeb21a7de77b61eadaa4406e0ae58facd6d6b5f4b4b736a335046dadab07d23b4c171270f2e3f0c29154c2dcd10085999106301069f292402a0fc3d0ba19677b921bd70e7bbc501e7bec663dee6aaa2f6cf62cfa3ee268d57721dfb71ff95301514d404e38b67c2753aa4ab4e4be9949fa495c1fc61143b4c4563021bacbb051bdf9419cddaf0e0015655a46fb53a4c7452a0f15ae9fa45cd8bdfab768456912f6cba7ad066ca493714db1abd1625c3d6971264143fe4ef2513e4c4b6f229272271edb8998ad0a9c3e0ed41a792c22b75c6a4c87d37f7b0aa600fb903857453ee137d880e09882535e8e51d719f5ca83d0fa01d71b5115c9190ae95eaafed8a272f9abd5e040aad5042bfbf7399a6f7f2f6932e9ce8ddb856663c6177864cdae1a7d116bb258de586e621b399e870f3909acdbbcbe4fa6f9f2fcb605ed250e11f43fc3c8645ed980d94a5d3a14aab60ba5725a363f845566f170eede27a65a0a2a30865c22aa7d5cafe0ea3252645b8086f3a5443bb8c869990446ddb34e73b99d1d6cb8cdc9c69b94d20785ffde8ad38f92319d56e90a4569d235581656f6f2df761fb792833b4e72207e157841bcc99b3860abfb37f76dd77615420988e1702751e11aa5579e9f1987f3519bfb0fcf835d63b825f9128db50c8c1eccc88a64b4df432c72654371154884c54abc2c5b31693de5265c685dc7e0eeb10bcdca698bfb75016b1dfec2ece20ec4951fd338775d239db1663f63b328d6c6a0415f35f23cffae21a9db195118f22083c5fcbd7192cfa611748cb79486ab78b16b0f1b8d5e81410b0213ff6f603dec71909c6b07bf12618551e4f9c8eaf7346c890b4c10c02970011242a9c57933cdff2526985c0009341474f7d18d197558585feca1cb0030afc784906b45bef19d4cc32b0ae289a08a3eadad86e512100dde8a85d8ab9cc5740cd2e58848b56b7f07defeb43d28aaa6e5a7e46a221323a928088743845b6dc669868634117a50759e5f144f35297374f79e6059a159ca0596fb26273a219fcdc9e5c56a2b9efa0fe392cf54b0c'
R.<a,b> = PolynomialRing(GF(p))
poly = a * c1 + (p^^c1) * c1 + b + (p^^c1)- c2
_a, _b = small_roots(poly, (2^200, 2^200), m=3, d=2)[0]
print("a =", _a + (p^^c1))
print("b =", _b + (p^^c1))
a, b = _a + (p^^c1), _b + (p^^c1)
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from hashlib import sha256
iv = bytes.fromhex(iv)
ct = bytes.fromhex(ct)
#print(iv)
#print(ct)
key = sha256(long_to_bytes(a) + long_to_bytes(b)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
print(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!}
Can you sign my message for me?
nc crypto.be.ax 6002
Let's look at the source provided in source.py
.
from Crypto.Util.number import bytes_to_long, inverse
from hashlib import sha256
from secrets import randbelow
from private import flag
from fastecdsa.curve import P256
G = P256.G
N = P256.q
class RNG:
def __init__(self, seed, A, b, p):
self.seed = seed
self.A = A
self.b = b
self.p = p
def gen(self):
out = self.seed
while True:
out = (self.A*out + self.b) % self.p
yield out
def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
def sign(m):
k = next(gen)
r = int((k*G).x) % N
s = ((H(m) + d*r)*inverse(k, N)) % N
return r, s
def verify(r, s, m):
v1 = H(m)*inverse(s, N) % N
v2 = r*inverse(s, N) % N
V = v1*G + v2*pub
return int(V.x) % N == r
seed, A, b = randbelow(N), randbelow(N), randbelow(N)
lcg = RNG(seed, A, b, N)
gen = lcg.gen()
d = randbelow(N)
pub = d*G
mymsg = b'i wish to know the ways of the world'
print('public key:', pub)
signed_hashes = []
for _ in range(4):
m = bytes.fromhex(input('give me something to sign, in hex>'))
h = H(m)
if m == mymsg or h in signed_hashes:
print("i won't sign that.")
exit()
signed_hashes.append(h)
r, s = sign(m)
print('r:', str(r))
print('s:', str(s))
print('now, i want you to sign my message.')
r = int(input('give me r>'))
s = int(input('give me s>'))
if verify(r, s, mymsg):
print("nice. i'll give you the flag.")
print(flag)
else:
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.
ri = x(k_i*G) % N
si = (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 si
s 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:
(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
s1 = (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:
import os
os.environ['PWNLIB_NOTERM'] = '1'
from pwn import *
from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from fastecdsa.curve import P256
G = P256.G
N = P256.q
count = 4
Fn = GF(N)
def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
host, port = 'crypto.be.ax', 6002
r = remote(host, port)
ms = [hex(i)[2:].zfill(2).encode() for i in range(count)]
zs = [Fn(H(ms[i])) for i in range(count)]
rs = []
ss = []
for i in range(count):
r.recvuntil(b'give me something to sign, in hex>')
r.sendline(ms[i].hex())
r.recvuntil(b'r:')
rs.append(Fn(int(r.recvline())))
r.recvuntil(b's:')
ss.append(Fn(int(r.recvline())))
P.<k, a, b> = PolynomialRing(Fn)
def lcg(x):
return a*x + b
ks = [k]
for _ in range(count-1):
ks.append(lcg(ks[-1]))
polys = [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)]
I = ideal(polys)
B = I.groebner_basis()
c0s = B[0].coefficients()
c1s = B[1].coefficients()
T.<x> = PolynomialRing(Fn, 'x')
poly = c0s[0]*x^2 + c0s[1]*x + c0s[2]
roots = poly.roots()
# 50-50 here
b = roots[0][0]
print(roots)
k1 = -(c1s[1]*b + c1s[2])*(c1s[0]^-1) % N
d = ((ss[0]*k1 - zs[0])*(rs[0]^-1)) % N
msg = b'i wish to know the ways of the world'
fr = (int(2)*G).x % N
fs = ((H(msg) + d*fr)*inverse_mod(2, N)) % N
r.recvuntil(b'give me r>')
r.sendline(str(fr))
r.recvuntil(b'give me s>')
r.sendline(str(fs))
r.interactive()
corctf{r3l4ted_n0nce5_4re_d4n6er0us_fde6ebafa842716a}
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.
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:
elif op == '8':
actual = bill[idx]
if actual in '01':
measured = qubits[idx].measure('01')
else:
measured = qubits[idx].measure('+-')
if actual == measured:
print('Qubit successfully verified.')
else:
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.
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)
from pwn import *
r = remote('crypto.be.ax', 6005)
mybill = list("?"*50)
def test_X(i):
r.sendline(b'1')
r.recvuntil(b'9. Back')
r.sendline(b'8')
r.recvline()
re = r.recvline()[:-1]
print(re)
if re == b'> Incorrect qubit!': # qubit was not X-eigenvector, so in 0, 1
r.recvuntil(b'9. Back')
r.sendline(b'1')
r.recvuntil(b'9. Back')
r.sendline(b'6')
r.recvuntil(b'The qubit measured as ')
mybill[i] = r.recvline()[:-1].decode()
r.recvuntil(b'9. Back')
r.sendline(b'9')
else: # qubit is in +- basis
r.recvuntil(b'9. Back')
r.sendline(b'7')
r.recvuntil(b'The qubit measured as ')
mybill[i] = r.recvline()[:-1].decode()
r.recvuntil(b'9. Back')
r.sendline(b'9')
def get_qubit(i):
r.recvuntil(b'3. Quit')
r.sendline(b'1')
r.recvuntil(b'index of the qubit you wish to work with: ')
r.sendline(str(i).encode())
r.recvuntil(b'9. Back')
test_X(i)
r.recvuntil(b'Would you like an account? (y/n) ')
r.sendline(b'y')
for i in range(50):
get_qubit(i)
mybill = ''.join(mybill)
print(mybill)
r.recvuntil(b'3. Quit')
r.sendline(b'2')
r.recvuntil(b'Enter your bill: ')
r.sendline(mybill.encode())
r.interactive()
Mysterious stream cipher. Wonder what the seed was...
We are provided two source files and a ciphertext file ct
. Let's take a look at source.py
first:
from random import randrange
from secrets import flag, key
from Crypto.Util.number import long_to_bytes
def bsum(state, taps, l):
ret = 0
for i in taps:
ret ^= (state >> (l - i))
return ret & 1
class Gen:
def __init__(self, key, slength):
self.state = key
self.slength = slength
self.TAPS = [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]
def clock(self):
out = bsum(self.state, self.TAPS, self.slength)
self.state = (out << (self.slength - 1)) + (self.state >> 1)
return out
def insertflag(fn, flag):
txt = b''
with open(fn, 'rb') as f:
txt = f.read()
i = randrange(0, len(txt))
txt = txt[:i] + flag + txt[i:]
with open(fn, 'wb') as f:
f.write(txt)
def gf256_multiply(a,b):
p = 0
for _ in range(8):
if b % 2:
p ^= a
check = a & 0x80
a <<= 1
if check == 0x80:
a ^= 0x1b
b >>= 1
return p % 256
def encrypt(fn, outf, cipher):
pt = b''
with open(fn, 'rb') as f:
pt = f.read()
ct = b''
for byte in pt:
genbyte = 0
for i in range(8):
genbyte = genbyte << 1
genbyte += cipher.clock()
ct += long_to_bytes(gf256_multiply(genbyte, byte))
with open(outf, 'wb') as f:
f.write(ct)
insertflag('pt', flag)
cipher = Gen(key, 64)
encrypt('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:
R.<x> = PolynomialRing(GF(2), 'x')
poly = [REDACTED]
assert poly.degree() == 64
M = [poly.list()[1:]]
for i in range(63):
M.append([1 if j == i else 0 for j in range(64)])
M = Matrix(GF(2), M)
A = M^[REDACTED]
E, S = A.eigenspaces_right(format='galois')[0]
assert E == 1
keyvec = S.random_element()
key = int(''.join([str(d) for d in keyvec]), 2)
print(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 0
s, 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:
def bsum(state, taps, l):
ret = 0
for i in taps:
ret ^= (state >> (l - i))
return ret & 1
class Gen:
def __init__(self, key, slength):
self.state = key
self.slength = slength
self.TAPS = [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]
def clock(self):
out = bsum(self.state, self.TAPS, self.slength)
self.state = (out << (self.slength - 1)) + (self.state >> 1)
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:
R.<x> = PolynomialRing(GF(2), 'x')
taps = [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]
poly = 1
for exp in taps:
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:
p8 = x^8 + x^6 + x^5 + x^4 + 1
p14 = x^14 + x^13 + x^12 + x^2 + 1
p19 = x^19 + x^18 + x^17 + x^14 + 1
p23 = 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:
from Crypto.Util.number import long_to_bytes, bytes_to_long
delim = bytes_to_long(b' ')
F = GF(2^8, 'x', modulus=x^8 + x^4 + x^3 + x + 1)
def div(a, b):
elem = F.fetch_int(a) / F.fetch_int(b)
return elem.integer_representation()
def g256_decrypt(m: bytes, key: list, outf):
ct = b''
for i in range(len(m)):
ct += long_to_bytes(div(m[i], key[i % len(key)]))
with open(outf, 'wb') as f:
f.write(ct)
def g256_crack(ct: bytes, keylen: int, delim: int, outf):
key = ['']*keylen
for i in range(keylen):
index = i
samples = {}
while index < len(ct):
cur = ct[index]
if cur not in samples:
samples[cur] = 0
samples[cur] += 1
index += keylen
maxfreqbyte = max(samples, key=samples.get)
key[i] = div(maxfreqbyte, delim)
g256_decrypt(ct, key, outf)
print("done")
ct = b''
with open('ct', 'rb') as f:
ct = f.read()
g256_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.
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
Let's examine the source given in source.sage
first.
from random import shuffle, randrange, randint
from os import urandom
from Crypto.Util.number import getPrime, getStrongPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from private import flag
import sys
class RNG:
def __init__(self, seed, a, b):
self.state = seed
self.a = a
self.b = b
print('a:', a)
print('b:', b)
def nextbits(self, bitlen):
out = 0
for _ in range(bitlen):
out <<= 1
self.state = self.a * self.state + b
bit = int(sum(self.state[i] for i in range(7)))
out += bit
return out
def get_params(rng, bitlen):
p = next_prime((1 << (bitlen - 1)) | rng.nextbits(bitlen))
q = next_prime((1 << (bitlen - 1)) | rng.nextbits(bitlen))
N = p * q
return N, p, q
LIMIT = 26
P.<x> = PolynomialRing(GF(2))
F.<x> = P.quo(x^128 + x^7 + x^2 + x + 1)
key, a, b = [F.random_element() for _ in range(3)]
bytekey = long_to_bytes(int(''.join(list(map(str, key.list()))), 2))
iv = os.urandom(16)
cipher = AES.new(bytekey, AES.MODE_CBC, IV=iv)
rng = RNG(key, a, b)
N, p, q = get_params(rng, 512)
if randint(0, 1):
p, q = q, p
e = 65537
d = inverse_mod(e, (p-1)*(q-1))
dp = d % (p-1)
r = getStrongPrime(1024)
g = randrange(2, r)
print('iv:', iv.hex())
print('N:', N)
print('e:', e)
print('g:', g)
print('r:', r)
print('encrypted flag:', cipher.encrypt(pad(flag, 16)).hex())
print()
print("now, let's cook some fried rice!")
for _ in range(LIMIT):
sys.stdout.flush()
m = int(input('add something in(in hex)> '), 16)
dp ^^= m
print('flip!', pow(g, dp, r))
print("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
.
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
1
s. 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
:
def search_chunk(nbits, stage, cur, m):
m = int(m << (stage * nbits))
r.recvuntil(b'add something in(in hex)> ')
r.sendline(hex(m)[2:].encode())
r.recvuntil(b'flip! ')
res = int(r.recvline())
cands = [i for i in range(2**nbits)]
ref = {}
# setup
for cand in cands:
c = int(cand << (stage * nbits))
diff = c - (c^^m)
ref[diff] = cand
# perform search
for k, v in ref.items():
if res * pow(g, k, rh) % rh == cur:
return res, v
def recover_dp_MSBs(shift):
dpmsbs = 0
CHUNKSIZE = 14
r.recvuntil(b'add something in(in hex)> ')
r.sendline(b'00')
r.recvuntil(b'flip! ')
cur = int(r.recvline())
m = 2**CHUNKSIZE - 1
for i in range(LIMIT - 1):
cur, chunk = search_chunk(CHUNKSIZE, i + shift, cur, m)
dpmsbs += chunk << (CHUNKSIZE * i)
print(f'completed stage {i+1}')
return Integer(dpmsbs)
d0 = recover_dp_MSBs(12)
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 0
s. 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:
kp < e
, construct the aforementioned latticer
is an integer, so get the integer roots from the polynomialA + 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:
def factor_n_with_dpmsbs(cs, shift):
l = cs * shift
ei = inverse_mod(e, N)
for kp in range(1, e):
R = 2**l
A = R * d0 + ei*(kp - 1)
B = Matrix([
[R**2, R*A, 0],
[0, R, A],
[0, 0, N]])
B = B.LLL()
vec = B[0]
poly = (vec[0]/(R^2))*y^2 + (vec[1]/R)*y + vec[2]
roots = poly.roots(multiplicities=False)
for root in roots:
ff = int(A + root)
fac = gcd(ff, N)
if fac > 1 and fac != N:
print('found!')
return fac, N / fac
p, q = factor_n_with_dpmsbs(14, 12)
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:
self.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:
a*state + b
(a^2)*state + a*b + b
(a^3)*state + (a^2)*b + a*b + b
.
.
.
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:
def recover_key_from_prime(p):
stream = list(map(int, list(bin(p)[3:])))
v = [a*(x^i) for i in range(KEYLEN)] # skip the first bit
ext = b
M = []
vec = []
for j in range(KEYLEN):
v = [a*el for el in v]
ext = a*ext + b
M.append([int(sum(v[k][l] for l in range(7))) for k in range(KEYLEN)])
out = int(sum(ext[l] for l in range(7))) ^^ stream[j]
vec.append(out)
M, vec = Matrix(GF(2), M), vector(GF(2), vec)
key = M.solve_right(vec)
key = long_to_bytes(int(''.join(list(map(str, [bit for bit in key]))), 2))
print('got key!')
return key
def recover_key_and_flag():
key1 = recover_key_from_prime(p)
key2 = recover_key_from_prime(q)
for key in (key1, key2):
try:
cipher = AES.new(key, AES.MODE_CBC, IV=iv)
flag = unpad(cipher.decrypt(enc), 16)
print(flag)
except:
pass
and the final attack script:
import os
os.environ['PWNLIB_NOTERM'] = '1'
from pwn import *
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from time import time
host, port = '35.208.182.172', 6003
r = remote(host, port)
P.<x> = PolynomialRing(GF(2))
F.<x> = P.quo(x^128 + x^7 + x^2 + x + 1)
L.<y> = PolynomialRing(ZZ)
LIMIT = 26
e = 65537
KEYLEN = 128
a, b, iv, N, g, rh, enc = [None for _ in range(7)]
def get_params():
global a, b, iv, N, g, rh, enc
r.recvuntil(b'a: ')
a = sage_eval(r.recvline().decode(), locals={'x':x})
r.recvuntil(b'b: ')
b = sage_eval(r.recvline().decode(), locals={'x':x})
assert a in F and b in F
r.recvuntil(b'iv: ')
iv = bytes.fromhex(r.recvline().decode())
r.recvuntil(b'N: ')
N = int(r.recvline())
r.recvuntil(b'e: ')
e = int(r.recvline())
r.recvuntil(b'g: ')
g = int(r.recvline())
r.recvuntil(b'r: ')
rh = int(r.recvline())
r.recvuntil(b'flag: ')
enc = bytes.fromhex(r.recvline().decode())
def search_chunk(nbits, stage, cur, m):
m = int(m << (stage * nbits))
r.recvuntil(b'add something in(in hex)> ')
r.sendline(hex(m)[2:].encode())
r.recvuntil(b'flip! ')
res = int(r.recvline())
cands = [i for i in range(2**nbits)]
ref = {}
# setup
for cand in cands:
c = int(cand << (stage * nbits))
diff = c - (c^^m)
ref[diff] = cand
# perform search
for k, v in ref.items():
if res * pow(g, k, rh) % rh == cur:
return res, v
def recover_dp_MSBs(shift):
dpmsbs = 0
CHUNKSIZE = 14
r.recvuntil(b'add something in(in hex)> ')
r.sendline(b'00')
r.recvuntil(b'flip! ')
cur = int(r.recvline())
m = 2**CHUNKSIZE - 1
for i in range(LIMIT - 1):
cur, chunk = search_chunk(CHUNKSIZE, i + shift, cur, m)
dpmsbs += chunk << (CHUNKSIZE * i)
print(f'completed stage {i+1}')
return Integer(dpmsbs)
def factor_n_with_dpmsbs(cs, shift):
l = cs * shift
ei = inverse_mod(e, N)
for kp in range(1, e):
R = 2**l
A = R * d0 + ei*(kp - 1)
B = Matrix([
[R**2, R*A, 0],
[0, R, A],
[0, 0, N]])
B = B.LLL()
vec = B[0]
poly = (vec[0]/(R^2))*y^2 + (vec[1]/R)*y + vec[2]
roots = poly.roots(multiplicities=False)
for root in roots:
ff = int(A + root)
fac = gcd(ff, N)
if fac > 1 and fac != N:
print('found!')
return fac, N / fac
def recover_key_from_prime(p):
stream = list(map(int, list(bin(p)[3:])))
v = [a*(x^i) for i in range(KEYLEN)] # skip the first bit
ext = b
M = []
vec = []
for j in range(KEYLEN):
v = [a*el for el in v]
ext = a*ext + b
M.append([int(sum(v[k][l] for l in range(7))) for k in range(KEYLEN)])
out = int(sum(ext[l] for l in range(7))) ^^ stream[j]
vec.append(out)
M, vec = Matrix(GF(2), M), vector(GF(2), vec)
key = M.solve_right(vec)
key = long_to_bytes(int(''.join(list(map(str, [bit for bit in key]))), 2))
print('got key!')
return key
def recover_key_and_flag():
key1 = recover_key_from_prime(p)
key2 = recover_key_from_prime(q)
for key in (key1, key2):
try:
cipher = AES.new(key, AES.MODE_CBC, IV=iv)
flag = unpad(cipher.decrypt(enc), 16)
print(flag)
except:
pass
t = time()
get_params()
d0 = recover_dp_MSBs(12)
print(f'Recovered in {time() - t} seconds')
p, q = factor_n_with_dpmsbs(14, 12)
recover_key_and_flag()
corctf{4nd_a_l1ttl3_bit_0f_gr3en_0ni0ns_on_t0p_dcca3160ef8135ea}
Do you believe in the heart of the cards?
nc crypto.be.ax 6002
We are provided the source file source.py
, so let's take a look at that first:
from Crypto.Util.number import getPrime
from random import randrange, shuffle
from private import flag
class Game():
KEY_LEN = 32
def __init__(self):
self.p = getPrime(256)
while self.p % 4 == 3:
self.p = getPrime(256)
x = randrange(self.p)
while pow(x, (self.p-1)//2, self.p) == 1:
x = randrange(self.p)
self.a = pow(x, (self.p-1)//4, self.p)
self.privgen()
self.signed = []
def privgen(self):
self.priv = [randrange(self.p) for _ in range(self.KEY_LEN)]
def sign(self, m):
s = 0
for i in range(len(self.priv)):
s += (pow(m, i, self.p) * self.priv[i]) % self.p
return s
def verify(self, m, s):
c = self.sign(m)
return c**4 % self.p == s
def getSig():
m = int(input("Enter the message you would like to sign, in hex> "), 16) % game.p
if m not in game.signed:
s = game.sign(m)
game.signed.append(m)
print(f"Signature: {hex(s**4 % game.p)[2:]}")
hints = [-s % game.p, s*game.a % game.p, -s*game.a % game.p]
shuffle(hints)
guess = int(input("Enter a guess for s, in hex> "), 16)
if guess in hints:
hints.remove(guess)
print(f"Hints: {hints[0]} {hints[1]}")
else:
print("You already signed that.")
def verifyPair():
m = int(input("Enter m, in hex> "), 16)
s = int(input("Enter s, in hex> "), 16)
if game.verify(m, s):
print("Valid signature.")
else:
print("Invalid signature.")
def guessPriv():
inp = input("Enter the private key as a list of space-separated numbers> ")
guess = [int(n) for n in inp.split(" ")]
if guess == game.priv:
print(f"Nice. Here's the flag: {flag}")
else:
print("No, that's wrong.")
exit()
def menu():
print("Enter your choice:")
print("[1] Get a signature")
print("[2] Verify a message")
print("[3] Guess the private key")
print("[4] Exit")
options = [getSig, verifyPair, guessPriv, exit]
choice = int(input("Choice> "))
if choice - 1 in range(len(options)):
options[choice - 1]()
else:
print("Please enter a valid choice.")
game = Game()
welcome = f"""Welcome.
I will let you sign as many messages as you want.
If you can guess the private key, the flag is yours.
But you only have one chance. Make it count.
p = {game.p}
"""
print(welcome)
while True:
menu()
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 s
s from the sig
s that we get from the server.
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:
(-s)^4 = s^4 % p
(s * x^((p-1)/4))^4 = s^4 * x^(p-1) = s^4 % p
(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:
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.
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.
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 s
s 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.
(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.(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.
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.
import os
os.environ['PWNLIB_NOTERM'] = '1'
from pwn import *
host, port = 'crypto.be.ax', 6001
r = remote(host, port)
r.recvuntil(b"p = ")
p = Integer(r.recvline())
F = GF(p)
R.<x> = PolynomialRing(F, 'x')
def get_points(n):
points = []
for i in range(n):
r.recvuntil(b"Choice> ")
r.sendline(b"1")
r.recvuntil(b"sign, in hex> ")
r.sendline(hex(i)[2:].encode())
r.recvuntil(b"Signature: ")
sig = Integer(int(r.recvline(), 16))
poly = x^4 - sig
cands = [int(pair[0]) for pair in poly.roots()]
r.recvuntil(b"guess for s, in hex> ")
r.sendline(hex(cands[0])[2:].encode())
r.recvuntil(b"Hints: ")
line = r.recvline().decode().split(" ")
a, b = int(line[0]), int(line[1])
cands.pop(0)
cands.remove(a)
cands.remove(b)
points.append((i, Integer(cands[0])))
return points
def get_matrix_and_b(n, k, points):
M, b = [], []
dQ = n + k - 1
for point in points:
r = []
for j in range(dQ + 1):
r.append(F(point[0])^j)
for j in range(k):
r.append(-F(point[1]) * F(point[0])^j)
M.append(r)
b.append(point[1] * F(point[0])^k)
M = Matrix(F, M)
b = vector(F, b)
return M, b
def get_privkey(a, n, k):
Q = a[0]
for i in range(1, n + k):
Q += a[i]*x^i
E = a[n + k]
for i in range(1, k):
E += a[n + k + i]*x^i
E += x^k
P = Q / E
return P.numerator().list()
def getflag(pay):
r.recvuntil(b"Choice> ")
r.sendline(b"3")
r.recvuntil(b"numbers> ")
r.sendline(pay.encode())
r.interactive()
points = get_points(80)
n, k = 32, len(points) // 4
M, b = get_matrix_and_b(n, k, points)
a = M.solve_right(b)
priv = get_privkey(a, n, k)
pay = ' '.join([str(v) for v in priv])
getflag(pay)
corctf{wh0_n3eds_gue551ng_wh3n_y0u_have_l1ne4r_al6ebr4_526d95eadb9686bb}
Thanks to all the players who tried out crypto challenges. Hope you enjoyed!