Zer0pts CTF 2021 - all crypto challenges (+quantum)
Published on 07 Mar 2021
Writeups
Note: SageMath in used in python mode.
In [1]:
from sage.all import * # python mode
from binteger import Bin
from sock import Sock
from Crypto.Cipher import AES
from base64 import b64decode
from tqdm import tqdm
xor = lambda a, b: bytes(aa ^ bb for aa, bb in zip(a, b))
war(sa)mup
Let's warm up! The challenge:
from Crypto.Util.number import getStrongPrime, GCD
from random import randint
# from flag import flag
import os
def pad(m: int, n: int):
# PKCS#1 v1.5 maybe
ms = m.to_bytes((m.bit_length() + 7) // 8, "big")
ns = n.to_bytes((n.bit_length() + 7) // 8, "big")
assert len(ms) <= len(ns) - 11
ps = b""
while len(ps) < len(ns) - len(ms) - 3:
p = os.urandom(1)
if p != b"\x00":
ps += p
padded = b"\x00\x02" + ps + b"\x00" + ms
print(padded)
return int.from_bytes(padded, "big")
while True:
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 1337
if GCD(phi, e) == 1:
break
flag = b"flag{lol}"
m = pad(int.from_bytes(flag, "big"), n)
c1 = pow(m, e, n)
c2 = pow(m // 2, e, n)
print("n =", n)
print("e =", e)
print("c1=", c1)
print("c2=", c2)
Hmm, seems like usual RSA (PKCS#1 v1.5 is insecure but would need a decryption oracle to exploit). We are given an encryption of $m$ and of $m/2$. This is fishy, we could obtain the latter one by ourselves: $(m/2)^e \equiv m/2^e \pmod{n}$. We can not break plain RSA!
Wait, the division is ... floored! The only chance is that it does not match $m/2$, that is, $m=2k+1$ is odd. Then, we would have
$$
\begin{align}
c_1 &\equiv m^e \equiv (2k+1)^e &\pmod{n},\\
c_2 &\equiv ((m-1)/2)^e \equiv k^e &\pmod{n}.
\end{align}
$$
As usual, we can solve for $k$ using Gröbner basis GCD:
In [2]:
n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
e = 1337
c1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
c2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762
k = PolynomialRing(Zmod(n), names='k').gen()
from fractions import gcd # sage fail
sol = gcd(
(2*k + 1)**e - c1,
k**e - c2,
)
sol
<ipython-input-2-6b5f31fdeb56>:8: DeprecationWarning: fractions.gcd() is deprecated. Use math.gcd() instead. sol = gcd(
Out [2]:
71785124859298185872505780079534027438512279929606066281208367059458844011674431615887555442822500934662083564564059292903055287302485911120893439199323702715667420657814418814873606800819068060373246871576625100671709947513370507201701529975362098126118606868649359861094228711421224066886119444248223786759*k + 27138590512017687417886761444666439571055730684602244727729100454365038529110106243319611458063808415064271105526823593991302533592409137896912256082534429741788638710330565146381476432196417063241294923818431067583902498291499846222600560471445211725272947478903479105195688818171831049300232979097381015049
In [3]:
m = 2*(-sol.monic()(0)) + 1
Bin(int(m)).bytes
Out [3]:
b'\x02\x81\xae\xed \xdd\x07\x12;\x99\xc7d:\x99\x1a8\x16\xfe\xe6<\x18\x1dw\xea&\xfb\xfc\x8a\xa7\xa8\xba\xfa\xd8\xbe\xdf\x01\x13\xcb\xd3\x99\x9c\xf3_\x18qw\xb99}\'Q\xd7~\x03&^\xcd\x9aw\xf0\xef\xb5\x04\x1b\xb7\n\xe1\xcd"\x95ff]\x0c(H\x99\xb5\xed\xc3\x82\x9dl\xe4\x8c\xddx\xfd\x00zer0pts{y0u_g07_47_13457_0v3r_1_p0in7}'
OT or NOT OT
Challenge code:
import os
import signal
import random
from base64 import b64encode
from Crypto.Util.number import getStrongPrime, bytes_to_long
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from flag import flag
p = getStrongPrime(1024)
key = os.urandom(32)
iv = os.urandom(AES.block_size)
aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
c = aes.encrypt(pad(flag, AES.block_size))
key = bytes_to_long(key)
print("Encrypted flag: {}".format(b64encode(iv + c).decode()))
print("p = {}".format(p))
print("key.bit_length() = {}".format(key.bit_length()))
signal.alarm(600)
while key > 0:
r = random.randint(2, p-1)
s = random.randint(2, p-1)
t = random.randint(2, p-1)
print("t = {}".format(t))
a = int(input("a = ")) % p
b = int(input("b = ")) % p
c = int(input("c = ")) % p
d = int(input("d = ")) % p
assert all([a > 1 , b > 1 , c > 1 , d > 1])
assert len(set([a,b,c,d])) == 4
u = pow(a, r, p) * pow(c, s, p) % p
v = pow(b, r, p) * pow(c, s, p) % p
x = u ^ (key & 1)
y = v ^ ((key >> 1) & 1)
z = pow(d, r, p) * pow(t, s, p) % p
key = key >> 2
print("x = {}".format(x))
print("y = {}".format(y))
print("z = {}".format(z))
This is an oblivious transfer: we are expected to learn only one key bit of our choice, but the server won't know which one. We are given $$ \begin{align} x &= a^r c^s \oplus k_0,\\ y &= b^r c^s \oplus k_1,\\ z &= d^r t^s. \end{align} $$ Here, $r,s$ are unknown, but $t$ is known and given to us beforehand! Since $k_0, k_1$ are 1-bit values, we can easily guess them and check if $x,y,z$ are valid. To have such a validity check, we need to choose $a,b,c,d$ wisely. Luckily, with known $t$ it is rather easy.
To remove the unknown $r$, we have to choose $a,b,d$ such that $abd=1$ or $abd=-1$. Then the result $xyz$ will contain $1^r$ or $(-1)^r$ which is easy to spot. This is trivial by e.g. $a=2,b=3,d=1/6$.
To remove the unknown $s$, we have to choose $c$ such that $cct=1$ or $cct=-1$. Then the result $xyz$ will contain $1^s$ or $(-1)^s$ which is easy to spot. We need $c^2=t$ or $c^2=-t$. We can not always ensure this for $p=4k+1$: it can happen that both $t$ and $-t$ are non-residues. But since the prime is chosen at random, we can wait for $p=4k+3$: then precisely one of $t$ and $-t$ will be a square and we can compute $c$.
In [4]:
while True:
f = Sock("crypto.ctf.zer0pts.com 10130")
encflag = b64decode(f.read_until_re(r"Encrypted flag: (\S+)\n"))
p = int(f.read_until_re(r"p = (\d+)\n"))
if p % 4 == 3:
print("ok", p, p%4)
break
print("bad", p, p%4)
bits = []
for i in tqdm(range(128)):
t = int(f.read_until_re(r"t = (\d+)\n"))
# x = a^r c^s xor keybit0
# y = b^r c^s xor keybit1
# z = d^r t^s
a = 2
b = 3
try:
c = int(~GF(p)(t).sqrt())
except:
c = int(~GF(p)(-t).sqrt())
d = ~GF(p)(6)
f.send_line(str(a))
f.send_line(str(b))
f.send_line(str(c))
f.send_line(str(d))
x = int(f.read_until_re(r"x = (\d+)\n"))
y = int(f.read_until_re(r"y = (\d+)\n"))
z = int(f.read_until_re(r"z = (\d+)\n"))
for ks in range(4):
k0, k1 = ks & 1, ks >> 1
if (x ^ k0) * (y ^ k1) * z % p in (1, p-1):
break
else:
assert 0, "fail?!"
bits.append(k0)
bits.append(k1)
key = Bin(bits[::-1]).bytes
AES.new(key=key, mode=AES.MODE_CBC, iv=encflag[:16]).decrypt(encflag[16:])
0%| | 0/128 [00:00<?, ?it/s]
ok 143079328927515630693016714274249445668016378677437811115085698577730083096994226291787383997251399508432115286337575215010064268785750559374659122484608233212018080988402058968193196715797865626211179980396283093501707474276776583293953485367973908371772298558121443424195946814596525998252733160887293521311 3
100%|██████████| 128/128 [00:39<00:00, 3.22it/s]
Out [4]:
b'zer0pts{H41131uj4h_H41131uj4h}\x02\x02'
easy pseudo random
Challenge code:
from Crypto.Util.number import*
from flag import flag
nbits = 256
p = random_prime(1 << nbits)
Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)
b = randrange(p)
d = 2
F = v^2 + b
v0 = randrange(p)
v1 = F(v0)
k = ceil(nbits * (d / (d + 1)))
w0 = (v0 >> (nbits - k))
w1 = (v1 >> (nbits - k))
# encrypt
m = bytes_to_long(flag)
v = v1
for i in range(5):
v = F(v)
m ^^= int(v)
print(f"p = {p}")
print(f"b = {b}")
print(f"m = {m}")
print(f"w0 = {w0}")
print(f"w1 = {w1}")
We have a linear quadratic congruential generator and 2/3 bits leaked from each of first two states. Coppersmith's time!
In [5]:
p = 86160765871200393116432211865381287556448879131923154695356172713106176601077
b = 71198163834256441900788553646474983932569411761091772746766420811695841423780
m = 88219145192729480056743197897921789558305761774733086829638493717397473234815
w0 = 401052873479535541023317092941219339820731562526505
w1 = 994046339364774179650447057905749575131331863844814
load("coppersmith.sage") # amazing https://github.com/defund/coppersmith
x, y = PolynomialRing(GF(p), names='x, y').gens()
t = 85
pol = (w0 * 2**t + x)**2 + b - (w1 * 2**t + y)
rs = small_roots(pol, [2**t, 2**t])
rs
Out [5]:
[(1319495720667326863431558, 1811790233058988426434106)]
In [6]:
x, y = rs[0]
v0 = int(w0*2**t + x)
v1 = int(w1*2**t + y)
assert (v0**2 + b) % p == v1
v = v1
for i in range(5):
v = (v**2+b) % p
m ^= int(v)
Bin(m).bytes
Out [6]:
b'zer0pts{is_blum_blum_shub_safe?}'
janken vs yoshiking
The challenge:
import random
import signal
from flag import flag
from Crypto.Util.number import getStrongPrime, inverse
HANDNAMES = {
1: "Rock",
2: "Scissors",
3: "Paper"
}
def commit(m, key):
(g, p), (x, _) = key
r = random.randint(2, p-1)
c1 = pow(g, r, p)
c2 = m * pow(g, r*x, p) % p
return (c1, c2)
def decrypt(c, key):
c1, c2 = c
_, (x, p)= key
m = c2 * inverse(pow(c1, x, p), p) % p
return m
def keygen(size):
p = getStrongPrime(size)
g = random.randint(2, p-1)
x = random.randint(2, p-1)
return (g, p), (x, p)
signal.alarm(3600)
key = keygen(1024)
(g, p), _ = key
print("[yoshiking]: Hello! Let's play Janken(RPS)")
print("[yoshiking]: Here is g: {}, and p: {}".format(g, p))
round = 0
wins = 0
while True:
round += 1
print("[system]: ROUND {}".format(round))
yoshiking_hand = random.randint(1, 3)
c = commit(yoshiking_hand, key)
print("[yoshiking]: my commitment is={}".format(c))
hand = input("[system]: your hand(1-3): ")
print("")
try:
hand = int(hand)
if not (1 <= hand <= 3):
raise ValueError()
except ValueError:
print("[yoshiking]: Ohhhhhhhhhhhhhhhh no! :(")
exit()
yoshiking_hand = decrypt(c, key)
print("[yoshiking]: My hand is ... {}".format(HANDNAMES[yoshiking_hand]))
print("[yoshiking]: Your hand is ... {}".format(HANDNAMES[hand]))
result = (yoshiking_hand - hand + 3) % 3
if result == 0:
print("[yoshiking]: Draw, draw, draw!!!")
elif result == 1:
print("[yoshiking]: Yo! You win!!! Ho!")
wins += 1
print("[system]: wins: {}".format(wins))
if wins >= 100:
break
elif result == 2:
print("[yoshiking]: Ahahahaha! I'm the winnnnnnner!!!!")
print("[yoshiking]: You, good loser!")
print("[system]: you can check that yoshiking doesn't cheat")
print("[system]: here's the private key: {}".format(key[1][0]))
exit()
print("[yoshiking]: Wow! You are the king of roshambo!")
print("[yoshiking]: suge- flag ageru")
print(flag)
Let's play the game. The commitment by yoshiking has the form:
$$
\begin{align}
c_1 &\equiv g^r &\pmod{p},\\
c_2 &\equiv m g^{rx} \equiv m c_1^x &\pmod{p}.
\end{align}
$$
Here $x$ is the secret key. This scheme has a standard weakness: quadratic residuosity is leaked. Even worse, the group can have other small subgroups! Confusingly, the method getStrongPrime only guarantees one large divisor of $p-1$ and $p+1$, not that $p-1$ is safe ($p=2q+1$)!
This means that with e.g. a subgroup of size 4 we may be able to distinguish all projections of $m$ to the subgroup, using
$$
m^t \equiv (c_2 / c_1^x)^t \equiv c_2^t / c_1^{tx} \pmod{p}.
$$
Although we don't know the value of $x$ in our subgroup (e.g. $x \mod{4}$), we can learn it quickly or just wait until we are lucky.
Note: we could also solve it with a safe prime, since even 1 bit of information may be sufficient to guarantee a winning/draw move.
In [7]:
while True:
f = Sock("crypto.ctf.zer0pts.com 10463")
g = int(f.read_until_re(r"g: (\d+)\b"))
p = int(f.read_until_re(r"p: (\d+)\b"))
e = (p-1)//4
mp = {pow(i, e, p): i for i in (1, 2, 3)}
if p % 4 == 1 and len(mp) == 3:
print("good", p)
break
good 142831596084592375312334945525278791146149139233219553088745321955956268821446715439562872933927367758119893309926112723005901087713319184960854992290138751365392872191340158195827668651208286358986404571368339616387453272103550452388666043298154232874646272114734984512143264653646250715398162939461986361193
In [8]:
for i in range(105):
c1, c2 = map(int, f.read_until_re(r"my commitment is=\((\d+, \d+)\)").split(b","))
hand = mp[pow(c2, e, p) * pow(c1, -e, p) % p]
my = (hand-2)%3+1
assert (hand - my) % 3 == 1
f.send_line(str(my))
try:
print(f.read_until(b": ROUND"))
except EOFError:
break
print(f.read_all())
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 1\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 2\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 3\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 4\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 5\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 6\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 7\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 8\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 9\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 10\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 11\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 12\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 13\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 14\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 15\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 16\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 17\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 18\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 19\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 20\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 21\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 22\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 23\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 24\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 25\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 26\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 27\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 28\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 29\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 30\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 31\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 32\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 33\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 34\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 35\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 36\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 37\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 38\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 39\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 40\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 41\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 42\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 43\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 44\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 45\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 46\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 47\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 48\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 49\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 50\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 51\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 52\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 53\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 54\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 55\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 56\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 57\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 58\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 59\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 60\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 61\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 62\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 63\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 64\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 65\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 66\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 67\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 68\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 69\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 70\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 71\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 72\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 73\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 74\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 75\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 76\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 77\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 78\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 79\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 80\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 81\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 82\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 83\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 84\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 85\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 86\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 87\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 88\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 89\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 90\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 91\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 92\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 93\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 94\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 95\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 96\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 97\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Scissors\n[yoshiking]: Your hand is ... Rock\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 98\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Rock\n[yoshiking]: Your hand is ... Paper\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 99\n[system]: ROUND'
b'\n[system]: your hand(1-3): \n[yoshiking]: My hand is ... Paper\n[yoshiking]: Your hand is ... Scissors\n[yoshiking]: Yo! You win!!! Ho!\n[system]: wins: 100\n[yoshiking]: Wow! You are the king of roshambo!\n[yoshiking]: suge- flag ageru\nzer0pts{jank3n-jank3n-0ne-m0r3-batt13}\n'
3-AES
Challenge code:
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from binascii import hexlify, unhexlify
from hashlib import md5
import os
import signal
from flag import flag
keys = [md5(os.urandom(3)).digest() for _ in range(3)]
def get_ciphers(iv1, iv2):
return [
AES.new(keys[0], mode=AES.MODE_ECB),
AES.new(keys[1], mode=AES.MODE_CBC, iv=iv1),
AES.new(keys[2], mode=AES.MODE_CFB, iv=iv2, segment_size=8*16),
]
def encrypt(m: bytes, iv1: bytes, iv2: bytes) -> bytes:
assert len(m) % 16 == 0
ciphers = get_ciphers(iv1, iv2)
c = m
for cipher in ciphers:
c = cipher.encrypt(c)
return c
def decrypt(c: bytes, iv1: bytes, iv2: bytes) -> bytes:
assert len(c) % 16 == 0
ciphers = get_ciphers(iv1, iv2)
m = c
for cipher in ciphers[::-1]:
m = cipher.decrypt(m)
return m
signal.alarm(3600)
while True:
print("==== MENU ====")
print("1. Encrypt your plaintext")
print("2. Decrypt your ciphertext")
print("3. Get encrypted flag")
choice = int(input("> "))
if choice == 1:
plaintext = unhexlify(input("your plaintext(hex): "))
iv1, iv2 = get_random_bytes(16), get_random_bytes(16)
ciphertext = encrypt(plaintext, iv1, iv2)
ciphertext = b":".join([hexlify(x) for x in [iv1, iv2, ciphertext]]).decode()
print("here's the ciphertext: {}".format(ciphertext))
elif choice == 2:
ciphertext = input("your ciphertext: ")
iv1, iv2, ciphertext = [unhexlify(x) for x in ciphertext.strip().split(":")]
plaintext = decrypt(ciphertext, iv1, iv2)
print("here's the plaintext(hex): {}".format(hexlify(plaintext).decode()))
elif choice == 3:
plaintext = flag
iv1, iv2 = get_random_bytes(16), get_random_bytes(16)
ciphertext = encrypt(plaintext, iv1, iv2)
ciphertext = b":".join([hexlify(x) for x in [iv1, iv2, ciphertext]]).decode()
print("here's the encrypted flag: {}".format(ciphertext))
exit()
else:
exit()
Triple-AES! But each key is only 24 bits. Can we break them one-by-one? Let's write down the encryption/decryption of one block: $$ ct = E_3(iv_2) \oplus E_2(E_1(m)\oplus iv_1). $$ What if we decrypt it with different $iv_1$? We will get a plaintext $r$ such that $$ ct = E_3(iv_2) \oplus E_2(E_1(r)\oplus iv_1'). $$ It follows that $$ E_1(r)\oplus iv_1' = E_1(m)\oplus iv_1. $$ We are left with $E_1$ only! We can bruteforce the key quickly.
Recovering the other two keys is similarly straightforward.
In [9]:
AESenc = lambda key, pt: AES.new(key, mode=AES.MODE_ECB).encrypt(pt)
AESdec = lambda key, ct: AES.new(key, mode=AES.MODE_ECB).decrypt(ct)
In [10]:
f = Sock("crypto.ctf.zer0pts.com 10929")
m = bytes(16)
f.send_line("1") # encrypt
f.send_line(f"{m.hex()}")
iv1, iv2, ct = f.read_until_re(r"ciphertext: (\w+:\w+:\w+)\n").decode().split(":")
iv1 = bytes.fromhex(iv1)
iv2 = bytes.fromhex(iv2)
ct = bytes.fromhex(ct)
iv1, iv2, ct
Out [10]:
(b'\xf3o\x9b\x95\x07\xfa\x10\x0eQ\x91\x10\xd9\xa4\xfd\x14\x84', b'\xd3\x0bgQ\xa0\xc93\xdf7\xc9\x0b:\x9b$v\xb1', b']s\xf9S\x9c\x97\x18/U\x8f$\xd5\xd8\x19\xd8\xb4')
In [11]:
iv1x = bytes(16)
f.send_line("2") # decrypt
f.send_line(f"{iv1x.hex()}:{iv2.hex()}:{ct.hex()}")
r = bytes.fromhex(f.read_until_re(r"plaintext\(hex\): (\w+)").decode())
r, iv1x, iv2, ct
# ct = E3(iv2) ^ E2(E1m ^ iv1)
# ct = E3(iv2) ^ E2(E1r ^ iv1x)
# E1m ^ iv1 = E1r ^ iv1x
# E1m ^ E1r = iv1 ^ iv1x
Out [11]:
(b'\x93\xc4\x84\x1f \x972 \xe7\xd4\xc4\n\xde;G!', b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00', b'\xd3\x0bgQ\xa0\xc93\xdf7\xc9\x0b:\x9b$v\xb1', b']s\xf9S\x9c\x97\x18/U\x8f$\xd5\xd8\x19\xd8\xb4')
In [12]:
ctq = bytes(16)
f.send_line("2") # decrypt
f.send_line(f"{iv1.hex()}:{iv2.hex()}:{ctq.hex()}")
q = bytes.fromhex(f.read_until_re(r"plaintext\(hex\): (\w+)").decode())
q, iv1, iv2, ctq
# ct = E3(iv2) ^ E2(E1m ^ iv1)
# ctq = E3(iv2) ^ E2(E1q ^ iv1)
# ct ^ ctq = E2(E1m ^ iv1) ^ E2(E1q ^ iv1)
Out [12]:
(b'\x81\xed\xd1\x06\x17Z\r\xc8\xbe\xe9\xa1\xda\xb8zJ\xdd', b'\xf3o\x9b\x95\x07\xfa\x10\x0eQ\x91\x10\xd9\xa4\xfd\x14\x84', b'\xd3\x0bgQ\xa0\xc93\xdf7\xc9\x0b:\x9b$v\xb1', b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00')
In [13]:
f.send_line("3") # flag
flag_iv1, flag_iv2, flag_ct = f.read_until_re(r"flag: (\w+:\w+:\w+)\n").decode().split(":")
flag_iv1 = bytes.fromhex(flag_iv1)
flag_iv2 = bytes.fromhex(flag_iv2)
flag_ct = bytes.fromhex(flag_ct)
In [14]:
# E1m ^ E1r = iv1 ^ iv1x
diff = xor(iv1, iv1x)
for key1 in tqdm(range(2**24)):
key1 = hashlib.md5(bytes.fromhex("%06x" % key1)).digest()
c = AES.new(key1, mode=AES.MODE_ECB)
test = xor(c.encrypt(m), c.encrypt(r))
if test == diff:
print("good", key1)
break
68%|██████▊ | 11402596/16777216 [06:52<03:14, 27640.64it/s]
good b'\x96\xbcovrF\xe8\xee\xb3<x-^\xc6\x97\xf1'
In [15]:
# ct ^ ctq = E2(E1m ^ iv1) ^ E2(E1q ^ iv1)
E1m = AESenc(key1, m)
E1q = AESenc(key1, q)
diff = xor(ct, ctq)
for key2 in tqdm(range(2**24)):
key2 = hashlib.md5(bytes.fromhex("%06x" % key2)).digest()
c = AES.new(key2, mode=AES.MODE_ECB)
c1 = c.encrypt(xor(E1m, iv1))
c2 = c.encrypt(xor(E1q, iv1))
if xor(c1, c2) == diff:
print("good", key2)
break
45%|████▍ | 7522574/16777216 [05:38<06:55, 22250.24it/s]
good b'W\xda\xf6\x0f"\xd7P\x87\xb3\x13o\x1f\x8a\x1a\x17\xc2'
In [16]:
# ct = E3(iv2) ^ E2(E1m ^ iv1)
e3iv2 = xor(ct, AESenc(key2, xor(E1m, iv1)))
for key3 in tqdm(range(2**24)):
key3 = hashlib.md5(bytes.fromhex("%06x" % key3)).digest()
if AESenc(key3, iv2) == e3iv2:
print("good", key3)
break
26%|██▌ | 4319342/16777216 [01:36<04:38, 44747.22it/s]
good b'\x1b\xac\x91_\x9dF\xc0\\\xed\xc6\xd5\x97\x1a#\x1fr'
In [17]:
ciphers = [
AES.new(key1, mode=AES.MODE_ECB),
AES.new(key2, mode=AES.MODE_CBC, iv=flag_iv1),
AES.new(key3, mode=AES.MODE_CFB, iv=flag_iv2, segment_size=8*16),
]
m = flag_ct
for c in reversed(ciphers):
m = c.decrypt(m)
m
Out [17]:
b'zer0pts{5kip_7h3_midd13_4nd_m337_in_7h3_midd13!}'
pure division
The challenge:
from Crypto.Util.number import *
from flag import flag
assert len(flag) == 40
p = 74894047922780452080480621188147614680859459381887703650502711169525598419741
a1 = 22457563127094032648529052905270083323161530718333104214029365341184039143821
a2 = 82792468191695528560800352263039950790995753333968972067250646020461455719312
Fp = Zmod(p^3)
E = EllipticCurve(Fp, [a1, a2])
m = bytes_to_long(flag)
S = E(201395103510950985196528886887600944697931024970644444173327129750000389064102542826357168547230875812115987973230106228243893553395960867041978131850021580112077013996963515239128729448812815223970675917812499157323530103467271226, 217465854493032911836659600850860977113580889059985393999460199722148747745817726547235063418161407320876958474804964632767671151534736727858801825385939645586103320316229199221863893919847277366752070948157424716070737997662741835)
T = m * S
with open("output.txt", "w") as f:
f.write("T: {}".format(T))
Elliptic curve... modulo a power of a prime?! Let's find the order over $\mathbb{F}_p$ first:
In [18]:
p = 74894047922780452080480621188147614680859459381887703650502711169525598419741
a1 = 22457563127094032648529052905270083323161530718333104214029365341184039143821
a2 = 82792468191695528560800352263039950790995753333968972067250646020461455719312
Fp = Zmod(p**3)
E = EllipticCurve(Fp, [a1, a2])
S = E(201395103510950985196528886887600944697931024970644444173327129750000389064102542826357168547230875812115987973230106228243893553395960867041978131850021580112077013996963515239128729448812815223970675917812499157323530103467271226, 217465854493032911836659600850860977113580889059985393999460199722148747745817726547235063418161407320876958474804964632767671151534736727858801825385939645586103320316229199221863893919847277366752070948157424716070737997662741835)
T = E(49376632602749543055345783411902198690599351794957124343389298933965298693663616388441379424236401744560279599744281594405742089477317921152802669021421009909184865835968088427615238677007575776072993333868804852765473010336459028, 342987792080103175522504176026047089398654876852013925736156942540831035248585067987750805770826115548602899760190394686399806864247192767745458016875262322097116857255158318478943025083293316585095725393024663165264177646858125759)
ordp = E.change_ring(GF(p)).order()
ordp
Out [18]:
74894047922780452080480621188147614680853399736985793708596679454987247185378
Now we can lift it to the order-$p^2$ subgroup:
In [19]:
ordp*S
ZeroDivisionError: Inverse of 359765749011109625648549536458477363023899206702053218973345795587347095577861903261398214165330550879888913434593126460981870043934433533404558328024032882782338266974355266632190749472422546833365973692516854280280992354119312254 does not exist (characteristic = 420089583322118885570279691377206385525512606178270582354830060900268883960494664480528893014037970167324223701612919114885362891750456800522743723588393622740878961078330775145250173923081026600794652934805034568338780300018686021 = 74894047922780452080480621188147614680859459381887703650502711169525598419741*5609118414259734949117289593564838594648752925364147379401691943275993003729603293905026050758950596801973500139150359571884430462601355273292236418507081)
Auch! It involves division by $p$. Not an issue: similarly to the anomalous discrete log algorithm, we can switch to the $p$-adic field $\mathbb{Q}_p$:
In [20]:
EQp = E.change_ring(Qp(p))
pS = EQp(S)*ordp
pT = EQp(T)*ordp
As in the anomalous discrete log, we can use the elliptic logarithm $x/y$:
In [21]:
sol = ZZ((pT[0] / pT[1]) / (pS[0] / pS[1]))
S*sol == T
Out [21]:
True
In [22]:
Bin(sol).bytes
Out [22]:
b'zer0pts{elliptic_curve_over_p-adic!yey!}'
signme
This is pwn+crypto challenge written in C and with a source code! The challenge consists in the server generating a new RSA key, signing our message and asking to sign a challenge message. If we succeed, we are given a shell.
While there is a memory corruption in the PKCSv1.5 padding function, there is also a weak randomness issue (unintended?). Here is the relevant excerpt:
gmp_randstate_t rstate;
/**
* Generate a random n-bit prime
* @param mpz_t p Prime integer
* @param uint32_t n Bit length of prime to generate
*/
void _get_prime(mpz_t p, uint32_t n) {
mpz_t r;
mpz_init(r);
do {
mpz_urandomb(r, rstate, n);
mpz_setbit(r, n - 1);
mpz_nextprime(p, r);
} while(mpz_sizeinbase(p, 2) >= n + 1);
mpz_clear(r);
}
/**
* Initialize random state (constructor)
*/
__attribute__((constructor))
void _signme_setup(void) {
struct timeval tv;
struct timezone tz;
if (gettimeofday(&tv, &tz)) {
perror("gettimeofday");
exit(1);
}
gmp_randinit_lc_2exp_size(rstate, 16);
gmp_randseed_ui(rstate, tv.tv_sec * 1000000 + tv.tv_usec);
}
Oh! The challenge uses the timestamp with microsecond precision as a seed for generating the RSA key. We know the seconds part when we connect and so there are only about one million possible keys.
Unfortunately, the prime generation is rather slow and we can not exhaust $1M$ keys in the challenge's connection timelimit - 60 seconds.
Fortunately, we can do it beforehand.
We plan ahead and precompute all keys in some chosen timespan in the future. Then, we wait for it and connect several times in the second and we see one of our precomputed keys. Signing then is easy.
On a 4-core laptop with 8 threads the precomputation attempt could take 1-3 hours for 1 second. On a 72-core AWS machine it takes 5 minutes (and <\$1) to precompute the timespan of 0.1s and it is sufficient to win with high probability.
$ id
uid=999(pwn) gid=999(pwn) groups=999(pwn)
$ pwd
/home/pwn
$ ls -al
total 1148
drwxr-xr-x 1 root pwn 4096 Mar 5 10:55 .
drwxr-xr-x 1 root root 4096 Mar 5 10:55 ..
-r-xr-x--- 1 root pwn 1155576 Mar 5 10:54 chall
-r--r----- 1 root pwn 41 Mar 5 10:55 flag-3affdf28df5168b31209eb1c289a3a67.txt
-r-xr-x--- 1 root pwn 37 Mar 5 10:55 redir.sh
$ cat flag*
zer0pts{h4lf_crypt0_h4lf_pWn_l1k3_p1zz4}
NOT Mordell primes
Code:
from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG
p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
E = EllipticCurve(GF(p),[a,b])
P = E(11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991)
Q = k*P
R = (k+1)*P
p = int(Q[0])
q = int(R[0])
assert is_prime(p)
assert is_prime(q)
e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)
print(f'N = {N}')
print(f'c = {c}')
In [24]:
p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
E = EllipticCurve(GF(p),[a,b])
P = E(11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991)
N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387
c = 15850849981973267982600456876579257471708532525108633915715902825196241000151529259632177065183069032967782114646012018721535909022877307131272587379284451827627191021621449090672315265556221217089055578013603281682705976215360078119427612168005716370941190233189775697324558168779779919848728188151630185987
We know that $p,q$ are x-coordinates of points $Q=[k]P$ and $R=[k+1]P$ on the elliptic curve. It follows that $R-Q-P = 0$, which means that $R,-Q,-P$ lie on the same line intersecting the curve. This constraint must have a simple polynomial form. There is probably a simple mathematical way to derive it, but we can also do it in a blind generic way.
In [25]:
n = 20
rows = []
ids = []
for i in range(n):
k = randrange(p)
x1 = (k*P)[0]
x2 = ((k+1)*P)[0]
row = []
for d1 in range(3):
for d2 in range(3):
row.append(x1**d1 * x2**d2)
if i == 0:
ids.append((d1, d2))
rows.append(row)
m = matrix(GF(p), rows)
m.right_kernel()
Out [25]:
Vector space of degree 9 and dimension 1 over Finite Field of size 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073 Basis matrix: [ 1 3750135857057492184519363113165978644184584541011927096786963549061722071043018881113932613730120243825750091105432537969081907140897353893864206603008930 1459662868852085008390483350184604394110126573510147794622959053450582734406588295565866715838138393774570534703526060198583789171590241651696344364860808 3750135857057492184519363113165978644184584541011927096786963549061722071043018881113932613730120243825750091105432537969081907140897353893864206603008930 7825506894143999127288076741165200944581135657525662613519454966285564802821516651161745083505126609867759501257484149388496063539058686373404840990830097 1941794623587796561096265454765053887234895377866706678099331348239458719268180310931123056109009726671770872847987280718580789186289727055621789564656322 1459662868852085008390483350184604394110126573510147794622959053450582734406588295565866715838138393774570534703526060198583789171590241651696344364860808 1941794623587796561096265454765053887234895377866706678099331348239458719268180310931123056109009726671770872847987280718580789186289727055621789564656322 9547981863862374715951691152517578847454830966876884077184668987614961936254637867118336125754559241519430198754472012843390867123030825749397207567371906]
We have one relation! It contains all monomials $x_{Q}^i x_{R}^j$ for $0\le i,j \le 2$:
In [26]:
xQ,xR = PolynomialRing(GF(p), names='xQ,xR', order="lex").gens()
sol = m.right_kernel().matrix()[0]
eq = sum(c * xR**e1 * xQ**e2 for c, (e1, e2) in zip(sol, ids))
eq.monomials()
Out [26]:
[xQ^2*xR^2, xQ^2*xR, xQ^2, xQ*xR^2, xQ*xR, xQ, xR^2, xR, 1]
Together with $x_Rx_Q=N$ this should give a solution:
In [27]:
G = Ideal([eq, xR*xQ-N])
pqs = G.variety()
pqs
verbose 0 (3837: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation. verbose 0 (1081: multi_polynomial_ideal.py, dimension) Warning: falling back to very slow toy implementation. verbose 0 (2274: multi_polynomial_ideal.py, variety) Warning: falling back to very slow toy implementation.
Out [27]:
[{xR: 5266647903652352665309561331835186152327627163271331811555419978564191000470060566535428497675116887002541568904535904345037425011015457585262022604897451,
xQ: 4292528248136861387890911319917455946841411872473250675409509735620572311636407361858881556677385609500178629430025710517411214702704597103005396234440737},
{xR: 4292528248136861387890911319917455946841411872473250675409509735620572311636407361858881556677385609500178629430025710517411214702704597103005396234440737,
xQ: 5266647903652352665309561331835186152327627163271331811555419978564191000470060566535428497675116887002541568904535904345037425011015457585262022604897451}]
Perfect!
Note: SageMath's variety() method fail unless lexicographic monomial order (order="lex") is specified.
In [28]:
pp, qq = map(int, pqs[0].values())
assert pp * qq == N
d = pow(0x10001, -1, N-pp-qq+1)
Bin(pow(c, d, N)).bytes
Out [28]:
b'zer0pts{7h4nk_y0u_j4ck_7h4nk_y0u_cr0wn}'
Tokyo Network (Quantum)
In this challenge, we have a noisy quantum transmission and we need to implement a decoder.
import base64
import random
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad
from qulacs import QuantumState, QuantumCircuit
from qulacs.gate import *
from secret import flag
GATES = {
'CNOT': (CNOT, 2),
'H': (H, 1), 'X': (X, 1), 'Y': (Y, 1), 'Z': (Z, 1),
'S': (S, 1), 'SDAG': (Sdag, 1), 'T': (T, 1), 'TDAG': (Tdag, 1)
}
def parse_circuit(asm, qbits=9):
""" Convert assembly into quantum circuit
i.e. q0 ---+--[Z]--
| <= CNOT 0,1; Z 0; H 1;
q1 --[X]-[H]--
"""
def apply(gate, args):
return gate(*args)
circuit = QuantumCircuit(qbits)
cnt = 0
for instruction in asm.replace('\n', '').split(';'):
t = instruction.strip().split()
if t == []:
continue
if len(t) < 2:
print("[-] Invalid instruction")
exit(0)
opecode, operand = t[0].upper(), t[1:]
if opecode not in GATES:
print("[-] Invalid gate")
exit(0)
operand = list(map(lambda x: int(x), ''.join(t[1:]).split(',')))
if not all(map(lambda x: 0 <= x < qbits, operand)):
print("[-] Invalid quantum bit specified")
exit(0)
if GATES[opecode][1] != len(operand):
print("[-] Invalid number of operands")
exit(0)
gate = apply(GATES[opecode][0], operand)
circuit.add_gate(gate)
cnt += 1
if cnt > 100:
print("[-] Too large circuit")
exit(0)
return circuit
def transfer_and_measure(q):
# Oops, noise might happen :(
noise = QuantumCircuit(9)
idx = random.randrange(0, 9)
noise.add_gate(DephasingNoise(idx, 0.31337))
noise.add_gate(DepolarizingNoise(idx, 0.31337))
noise.add_gate(BitFlipNoise(idx, 0.31337))
noise.update_quantum_state(q)
# Quantum arrived! You can update (or keep) the state :)
circuit = parse_circuit(input('[?] Your Circuit: '))
circuit.update_quantum_state(q)
# Now you measure the quantum state :P
return random.choices(range(2**9),
map(lambda x: abs(x), q.get_vector()))[0] & 1
if __name__ == '__main__':
N = 128
xi, xip = 0.98, 0.98
p = (xi * (1 + xi))**0.5 - xi
Np = int(N * (1 + 2*xi + 2*(xi*(1+xi))**0.5 + xip))
print("[+] Np = " + str(Np))
encoder = parse_circuit("""
CNOT 0,3; CNOT 0,6;
H 0; H 3; H 6;
CNOT 0,1; CNOT 0,2;
CNOT 3,4; CNOT 3,5;
CNOT 6,7; CNOT 6,8;
""")
measured = 0
ra, ba = 0, 0
for i in range(Np):
ra = (ra << 1) | random.choice([0, 1])
ba = (ba << 1) | random.choices([1, 0], [p, 1-p])[0]
q = QuantumState(9)
q.set_zero_state()
if ra & 1:
X(0).update_quantum_state(q)
if ba & 1:
H(0).update_quantum_state(q)
encoder.update_quantum_state(q)
measured = (measured << 1) | transfer_and_measure(q)
del q
print("[+] Measured state: " + bin(measured))
bb = int(input('[?] bb = '), 2)
print("[+] ba = " + bin(ba))
Nx, Nz = 0, 0
for i in range(Np):
if (ba >> i) & 1 == (bb >> i) & 1 == 1:
Nx += 1
elif (ba >> i) & 1 == (bb >> i) & 1 == 0:
Nz += 1
if Nx < N * xi or Nz - N < N * xi:
print("[-] Something went wrong :(")
exit(0)
xa = 0
for i in range(Np):
if (ba >> i) & 1 == (bb >> i) & 1 == 1:
xa = (xa << 1) | ((ra >> i) & 1)
print("[+] xa = " + bin(xa))
l = []
for i in range(Np):
if (ba >> i) & 1 == (bb >> i) & 1 == 0:
l.append(i)
chosen = random.sample(l, Nz - N)
m = 0
for i in chosen:
m |= 1 << i
print("[+] m = " + bin(m))
k = 0
for i in sorted(list(set(l) - set(chosen))):
k = (k << 1) | ((ra >> i) & 1)
key = int.to_bytes(k, N // 8, 'big')
iv = get_random_bytes(AES.block_size)
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(flag, AES.block_size))
print("Result: " + base64.b64encode(iv + ct).decode())
The encoder is rather simple:
CNOT 0,3; CNOT 0,6;
H 0; H 3; H 6;
CNOT 0,1; CNOT 0,2;
CNOT 3,4; CNOT 3,5;
CNOT 6,7; CNOT 6,8;
After that, one randomly chosen qubit (out of 9) is corrupted with 0.31337 fraction of noise. How should we decode such qubits? Naturally, let's try to simply invert the encoder.
In [29]:
from tokyo import *
N = 128
xi, xip = 0.98, 0.98
p = (xi * (1 + xi))**0.5 - xi
Np = int(N * (1 + 2*xi + 2*(xi*(1+xi))**0.5 + xip))
encoder_code = """
CNOT 0,3; CNOT 0,6;
H 0; H 3; H 6;
CNOT 0,1; CNOT 0,2;
CNOT 3,4; CNOT 3,5;
CNOT 6,7; CNOT 6,8;
"""
decoder_code = """
CNOT 6,7; CNOT 6,8;
CNOT 3,4; CNOT 3,5;
CNOT 0,1; CNOT 0,2;
H 0; H 3; H 6;
CNOT 0,3; CNOT 0,6;
"""
encoder = parse_circuit(encoder_code)
decoder = parse_circuit(decoder_code)
def noise(idx):
noise = QuantumCircuit(9)
noise.add_gate(DephasingNoise(idx, 0.31337))
noise.add_gate(DepolarizingNoise(idx, 0.31337))
noise.add_gate(BitFlipNoise(idx, 0.31337))
return noise
In [30]:
nbad = 0
for i in range(Np):
q = QuantumState(9)
q.set_zero_state()
r = random.randrange(2)
if r:
X(0).update_quantum_state(q)
encoder.update_quantum_state(q)
idx = random.randrange(0, 9)
noise(idx).update_quantum_state(q)
decoder.update_quantum_state(q)
res = random.choices(range(2**9), map(lambda x: abs(x), q.get_vector()))[0] & 1
nbad += res != r
nbad, Np
Out [30]:
(142, 860)
This method fails around 10% of the time. Let's sample all possible output states to see if we can correct the bad ones:
In [31]:
good = set()
bad = set()
for idx in range(9):
noise_idx = noise(idx)
for bit in range(2):
vecs = {}
for i in range(100):
q = QuantumState(9)
q.set_zero_state()
if bit:
X(0).update_quantum_state(q)
encoder.update_quantum_state(q)
noise_idx.update_quantum_state(q)
decoder.update_quantum_state(q)
for vec, prob in enumerate(q.get_vector()):
pr = abs(prob * prob.conjugate())
if pr > 0.001:
if bit != vec & 1:
bad.add(vec)
else:
good.add(vec)
print("all good")
for vec in sorted(good):
print(bit, f"{vec:09b}")
print("all bad")
for vec in sorted(bad):
print(bit, f"{vec:09b}")
all good 1 000000000 1 000000001 1 000000010 1 000000011 1 000000100 1 000000101 1 000000110 1 000000111 1 000001000 1 000001001 1 000010000 1 000010001 1 000011000 1 000011001 1 000100000 1 000100001 1 000101000 1 000101001 1 000110000 1 000110001 1 000111000 1 000111001 1 001000000 1 001000001 1 010000000 1 010000001 1 011000000 1 011000001 1 100000000 1 100000001 1 101000000 1 101000001 1 110000000 1 110000001 1 111000000 1 111000001 all bad 1 001001000 1 001001001 1 001001010 1 001001011 1 001001100 1 001001101 1 001001110 1 001001111
Quite few bad vectors! Also, it is easy to see that all bad vecors have pattern ..1..1... which does not fit any good vector! They can be fixed with one $CCNOT$ (Toffoli) gate.
Oops, we don't have such gate... Luckily, it can be implemented using $H,T$ and $CNOT$ gates (and their adjoints) (see wikipedia):
In [32]:
ccnot_code = """
H 0;
CNOT 6,0; TDAG 0; CNOT 3,0;
T 0;
CNOT 6,0; TDAG 0; CNOT 3,0;
T 6; T 0; H 0;
CNOT 3,6; T 3; TDAG 6; CNOT 3,6;
"""
ccnot = parse_circuit(ccnot_code)
nbad = 0
for i in range(Np):
q = QuantumState(9)
q.set_zero_state()
r = random.randrange(2)
if r:
X(0).update_quantum_state(q)
encoder.update_quantum_state(q)
idx = random.randrange(0, 9)
noise(idx).update_quantum_state(q)
decoder.update_quantum_state(q)
ccnot.update_quantum_state(q)
res = random.choices(range(2**9), map(lambda x: abs(x), q.get_vector()))[0] & 1
nbad += res != r
nbad, Np
Out [32]:
(0, 860)
No errors! Let's complete the challenge.
I did not get the idea behind the rest of the challenge (some combinatorial bounds and bit mask processing), but with perfect decoding it's easy to find a way to finish it and retrieve the flag.
In [33]:
f = Sock("others.ctf.zer0pts.com 11099")
circuit = (decoder_code + ccnot_code).replace("\n", "")
print(f.read_line())
for i in tqdm(range(860)):
f.send_line(circuit)
meas = Bin(f.read_until_re(r"Measured state: 0b(\d+)\n").decode()).resize(Np)
guess_indic = 2**350-1
f.send_line(f"{guess_indic:b}")
indic = Bin(f.read_until_re(r"ba = 0b(\d+)\n").decode()).resize(Np)
xa = Bin(f.read_until_re(r"xa = 0b(\d+)\n").decode()).resize(Np)
m = Bin(f.read_until_re(r"m = 0b(\d+)\n").decode()).resize(Np)
f.read_until("Result: ")
ivct = b64decode(f.read_line().strip())
ivct
100%|██████████| 860/860 [00:00<00:00, 4711.45it/s]
b'[+] Np = 860\n'
Out [33]:
b"P\x98\xb9\x0e\x98\x04}H\x1c\x9fG\xef>\x85G\xd0\x97\xb9\x15\xac\x1e\xf4\x8c!I\xbdy\xb0f_\x03\xfa\xab\xcc\xf9|\x0f(1\xb0S\xc4\xde\x96\x91\xd0BY'\x93M\n\xed\xf5\xb4\xd8\xa6\xe0d\xb7\xfa\x96'|"
In [34]:
l = []
for i in range(Np):
if (indic >> i) & 1 == (guess_indic >> i) & 1 == 0:
l.append(i)
len(l)
Out [34]:
311
In [35]:
ms = {j for j in l if m & (1 << j)}
len(ms)
Out [35]:
183
In [36]:
kis = sorted(set(l) - set(ms))
len(kis)
Out [36]:
128
In [37]:
k = Bin([(meas >> i) & 1 for i in kis]).bytes
k
Out [37]:
b'\x83\xda\x9e\xa8\xd4\xffk\xd7\xe0r\x81s\x1b\x96\xf3\xb2'
In [38]:
AES.new(k, mode=AES.MODE_CBC, iv=ivct[:16]).decrypt(ivct[16:])
Out [38]:
b'zer0pts{Sh0r_c0d3+BB84_QKB=5t1ll_53cur3?}\x07\x07\x07\x07\x07\x07\x07'