2022 idekCTF
I ran idekCTF as team ‘thehackerscrew’.
I was surprised that ‘thehackerscrew’ contacted me through Discord, and asking me to join their team.
It was an honor running as a top team, and meeting other fantastic people in our team.
As a Crypto fanatic, I solved 4 crypto Challenges.
ECRSA (40 solves)
main.sage
p, q = [random_prime(2^512, lbound = 2^511) for _ in range(2)]
e = 3
while gcd(p - 1, e) != 1: p = next_prime(p)
while gcd(q - 1, e) != 1: q = next_prime(q)
n = p*q
d = inverse_mod(e, (p-1)*(q-1))
# d stands for debug. You don't even know n, so I don't risk anything.
print('d =', d)
m = ZZ(int.from_bytes(b"It is UNBREAKABLE, I tell you!! I'll even bet a flag on it, here it is: idek{REDACTED}", 'big'))
t = ZZ(int.from_bytes(b"ECRSA offers added security by elliptic entropy.", 'big'))
ym = randint(1, n)
yt = 2
# I like it when my points lie on my curve.
a, b = matrix([[m, 1], [t, 1]]).solve_right([ym^2 - m^3, yt^2 - t^3])
E = EllipticCurve(Zmod(n), [a, b])
M = E(m, ym)
T = E(t, yt)
E.base_field = E.base_ring # fix multiplication over rings (might not work depending on sage version!)
print('Encrypted flag:', M*e)
print('Encrypted test:', T*e)
First of all, We don’t know the value for n, so we have to recover it with informations we know..
There is 3 points we know, enc_flag, enc_test, t
So theoretically we can recover all 3 unknown values: n, a, b
But when we try to remove a, b, and get a multiple of n, we only find a very large multiple of n.
Gladly, we know t * 3 is enc_test on the elliptic curve.
Since we don’t know the value for a yet, we can add t, t, t and compare with enc_test.
But point addition(or subtraction) doesn’t need the value for a, just 2 points and n.
So we can think:
(enc_test - t) - t == t (mod n)
After that, obviously the x value for the left point and the right point should be eqaul mod n.
If we subtract one from one another, we get another multiple of n.
Calculating gcd with 2 multiples of n will easily give us n, which is:
148789535372424163728266646450060056789282887632409478972504939920226619164297864570138212065846604310648872389662317508759494232616904707691022520428483000923260778669946008689451863137527523684502948570798504215922534787506491833325381174139925947167122783344470619692746866285435276907642606269209931602317
Recovering a and b is easy now.
After that, we have to recover flag from enc_flag(flag * 3) with elliptic curve calculation.
If we know the order for the curve, we can find inverse of 3 mod order, and get the flag point.
But we can see it is impossible because n is composite, so we’ll have to factor n to p, q.
Gladly, the challenge gave us d value, and since e is 3
3 * d should be phi(n) + 1 or 2 * phi(n) + 1. It turns out second one is correct.
We make 2 elliptic curves mod p and q, and find order for both.
(It took more time than I thought, I first thought I was missing something.)
With CRT, we can get the flag point mod n, and get the flag.
ex.sage
from Crypto.Util.number import *
d = 99193...8587
enc_flag = (11507...8789, 74232...2318)
enc_test = (79615...4937, 11457...0982)
t = (ZZ(int.from_bytes(b"ECRSA offers added security by elliptic entropy.", 'big')), 2)
points = [enc_test, enc_flag, t]
def point_to_eq(P):
x, y = P
a_coefficient = x
b_coefficient = 1
constant = x^3 - y^2
return (a_coefficient, b_coefficient, constant)
def kill_b(eq1, eq2):
a1, b1, c1 = eq1
a2, b2, c2 = eq2
a_coefficient = a1 * b2 - a2 * b1
constant = c1 * b2 - c2 * b1
return (a_coefficient, constant)
def kill_a(eq1, eq2):
a1, c1 = eq1
a2, c2 = eq2
constant = c1 * a2 - c2 * a1
return constant # which is multiple of p
eq_1 = []
for point in points:
eq_1.append(point_to_eq(point))
eq_3 = []
for i in range(len(eq_1)):
for j in range(i + 1, len(eq_1)):
eq_3.append(kill_b(eq_1[i], eq_1[j]))
p_multiple = []
for i in range(len(eq_3)):
for j in range(i + 1, len(eq_3)):
p_multiple.append(kill_a(eq_3[i], eq_3[j]))
p = p_multiple[0]
for n in p_multiple:
p = gcd(p, n)
nmul = 29408...7069
t_3 = enc_test
negt = (ZZ(int.from_bytes(b"ECRSA offers added security by elliptic entropy.", 'big')), -2)
lamb = (t_3[1] - negt[1]) / (t_3[0] - negt[0])
x = lamb^2 - t_3[0] - negt[0]
y = lamb * (t_3[0] - x) - t_3[1]
t_2 = (x, y)
lamb = (t_2[1] - negt[1]) / (t_2[0] - negt[0])
x = lamb^2 - t_2[0] - negt[0]
y = lamb * (t_2[0] - x) - t_2[1]
t_1 = (x % nmul, y % nmul)
n = 148789535372424163728266646450060056789282887632409478972504939920226619164297864570138212065846604310648872389662317508759494232616904707691022520428483000923260778669946008689451863137527523684502948570798504215922534787506491833325381174139925947167122783344470619692746866285435276907642606269209931602317
phi = (3 * d - 1) // 2
x1, y1 = enc_test
x2, y2 = enc_flag
a = (((y1^2 - x1^3) - (y2^2 - x2^3)) / (x1 - x2)) % n
b = (y1^2 - x1^3 - a * x1) % n
E = EllipticCurve(Zmod(n), [a, b])
eeeee_flag = E(enc_flag)
add = n + 1 - phi
p = Integer((add - sqrt(add^2 - 4 * n)) / 2)
q = Integer((add + sqrt(add^2 - 4 * n)) / 2)
assert p * q == n
Ep = EllipticCurve(Zmod(p), [a, b])
Eq = EllipticCurve(Zmod(q), [a, b])
f_p = Ep(enc_flag)
f_q = Eq(enc_flag)
test_p = Ep(enc_test)
t_p = Ep(t)
assert t_p * 3 == test_p
ep_order = 12106285759457603837646209698473787447139576157605716627376889077738609086595367760906757844814552719704303248523074103662114018990337565151986764666812769
eq_order = 12290271213546041363951851773787980582602437964255454723585180242187866091592930408418132906142473580819234492550892403489633401195027564397193372497063650
flag_p = Integer((f_p * pow(3, -1, ep_order)).xy()[0])
flag_q = Integer((f_q * pow(3, -1, eq_order)).xy()[0])
x = crt([flag_p, flag_q], [p, q])
print(long_to_bytes(x))
Cleithrophobia (58 solves)
Easy symmetric cipher challenge with xoring blocks.
cleithrophobia.py
#!/usr/bin/env python3
#
# Polymero
#
# Imports
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import os
# Local imports
with open('flag.txt', 'rb') as f:
FLAG = f.read()
f.close()
# Header
HDR = r"""|
|
| __ _ ___ ____ ______ __ __ ____ ___ ____ __ __ ___ ____ ____ ____
| / ] | / _] | | | | \ / \| \| | |/ \| \| |/ |
| / /| | / [_ | || | | | D ) | o ) | | | o )| || o |
| / / | |___/ _]| ||_| |_| _ | /| O | _/| _ | O | || || |
| / \_| | [_ | | | | | | | \| | | | | | | O || || _ |
| \ | | || | | | | | | . \ | | | | | | || || | |
| \____|_____|_____|____| |__| |__|__|__|\_|\___/|__| |__|__|\___/|_____|____|__|__|
|
|"""
# Server encryption function
def encrypt(msg, key):
pad_msg = pad(msg, 16)
blocks = [os.urandom(16)] + [pad_msg[i:i+16] for i in range(0,len(pad_msg),16)]
itm = [blocks[0]]
for i in range(len(blocks) - 1):
tmp = AES.new(key, AES.MODE_ECB).encrypt(blocks[i+1])
itm += [bytes(j^k for j,k in zip(tmp, blocks[i]))]
cip = [blocks[0]]
for i in range(len(blocks) - 1):
tmp = AES.new(key, AES.MODE_ECB).decrypt(itm[-(i+1)])
cip += [bytes(j^k for j,k in zip(tmp, itm[-i]))]
return b"".join(cip[::-1])
# Server connection
KEY = os.urandom(32)
print(HDR)
print("| ~ I trapped the flag using AES encryption and decryption layers, so good luck ~ ^w^")
print(f"|\n| flag = {encrypt(FLAG, KEY).hex()}")
# Server loop
while True:
try:
print("|\n| ~ Want to encrypt something?")
msg = bytes.fromhex(input("|\n| > (hex) "))
enc = encrypt(msg, KEY)
print(f"|\n| {enc.hex()}")
except KeyboardInterrupt:
print('\n|\n| ~ Well goodbye then ~\n|')
break
except:
print('|\n| ~ Erhm... Are you okay?\n|')
The main idea is
We can both get the value for
dec(a ^ enc(b)) and enc(c) ^ dec(a ^ enc(b)) so we can encrypt any block we want.
After knowing the encrypted block, decryption is easy too.
ex.py
from pwn import *
r = remote("cleithrophobia.chal.idek.team", 1337)
r.recvuntil("flag = ")
res = bytes.fromhex(r.recv(96 * 2).decode())
inv = b""
for i in range(len(res) // 16):
inv += res[len(res) - (i + 1) * 16:len(res) - i * 16]
enc_flag = inv
# print(len(enc_flag))
# 96 (6 blocks)
def send(msg):
r.sendlineafter("| > (hex) ", bytes.hex(msg))
r.recvline()
res = bytes.fromhex(r.recvline()[4:].decode())
inv = b""
for i in range(len(res) // 16):
inv += res[len(res) - (i + 1) * 16:len(res) - i * 16]
return inv
def enc(block):
b1 = b"\x10" * 16
b2 = block
b3 = b"\x10" * 16
res = send(b1 + b2)
b0 = res[0:16]
b1_eb2_db0_eb1 = res[48:64]
res2 = send(b1 + b0)
db0_eb1 = xor(res2[0:16], res2[16:32])
return xor(xor(b1_eb2_db0_eb1, db0_eb1), b1)
def dec(block):
b2 = b"\x10" * 16
res = send(xor(enc(b2), block))
return xor(res[0:16], res[16:32])
testblock = b"soon_haari_idiot"
print(dec(enc(testblock)))
print(enc(dec(testblock)))
b0 = enc_flag[:16]
itm = [b0, 0, 0, 0, 0, 0]
for i in range(5, 0, -1):
itm[i] = enc(xor(itm[(i + 1) % 6], enc_flag[16 * (6 - i):16 * (7 - i)]))
blocks = [b0]
for i in range(5):
blocks.append(dec(xor(blocks[i], itm[i + 1])))
print(b"".join(blocks[1:]))
r.interactive()
Primonumerophobia (10 solves)
source.py
#!/usr/bin/env python3
from Crypto.Util.number import *
import random
import os
class LFSR():
def __init__(self, taps):
d = max(taps)
self.taps = [d-t for t in taps]
self.state = [random.randint(0, 1) for _ in range(d)]
def _sum(self, L):
res = 0
for t in L:
res ^= t
return res
def next(self):
s = self.state[0]
self.state = self.state[1:] + [self._sum([self.state[t] for t in self.taps])]
return s
def getPrime(self, nbits):
count = 0
while True:
count += 1
p = int("".join([str(self.next()) for _ in range(nbits)]), 2)
if isPrime(p) and p > 2**(nbits-1):
print(f"[LOG] It takes {count} trials to find a prime.")
return p
if __name__ == '__main__':
lfsr = LFSR([47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2])
p, q = lfsr.getPrime(512), lfsr.getPrime(512)
with open("flag.txt", "rb") as f:
flag = f.read()
print(f"n = {p*q}")
print(f"enc = {pow(bytes_to_long(flag), 0x10001, p*q)}")
It use LSFR to generate prime numbers, and we know how far the two prime numbers are in LFSR.
So theoretically we can set 47 variables with only 0 and 1, and form all bits of p and q with those 47 variables’ addition mod 2.
The main idea is we know the value for p * q, so if we know last 24 bits of p, we can find q’s last 24 bits of q by n / p (mod 2^24).
So we don’t need 47 bit brute-force, we only need 24 bit brute-force to solve this.
I commented most of the codes, because running single steps took long, so I copiedd the needed values and pasted in the code.
ex.sage
import random
from Crypto.Util.number import *
'''
add = [47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2]
arr = []
for i in range(47):
line = [0] * 47
line[i] = 1
arr.append(line)
for i in range(47, 512 * (447 + 1)):
line = [0] * 47
for j in add:
for k in range(47):
line[k] += arr[i - j][k]
line[k] %= 2
arr.append(line)
print(i)
assert len(arr) == 512 * (447 + 1)
print(arr[:512])
print(arr[-512:])
'''
'''
p = {redacted}
q = {redacted}
assert len(p) == 512 and len(q) == 512
n = 78189483779073760819769596415493404181115737255987326126790953924148600157623709942134043192581448967829591214999561812461790206591977861764710056434977125005626712442593271233036617073503751799983263888626278748439349756982639988997517983470845431197233107232933125334078771472039280629203017666578936360521
enc = 39952631182502523101053953538875437560829302998610236142339435591980522271590392249355510253125310494063081880512061476177621613835835483055753316172267380484804011034657479491794064534740537749793563744927827732170347495398050941609682485707331552759412916426691849669362897656967530464847648838434750188588
mat = []
#mat.append(p[0])
for i in range(24):
mat.append(p[511 - i])
for i in range(23):
mat.append(q[511 - i])
mat = matrix(IntegerModRing(2), mat)
inv = mat.inverse()
P = 0
Q = 0
get_p_vec = [0] * 47
for i in range(512):
for j in range(47):
get_p_vec[j] += (1 << (511 - i)) * p[i][j]
for k in range(1 << 24):
if k % 2 == 0:
continue
mod = 1 << 23
p_ = k
q_ = (n * pow(p_, -1, mod)) % mod
res = []
for i in range(24):
if p_ & (1 << i) > 0:
res.append([1])
else:
res.append([0])
for i in range(23):
if q_ & (1 << i) > 0:
res.append([1])
else:
res.append([0])
res = matrix(IntegerModRing(2), res)
vals = inv * res
p_val = 0
for i in range(47):
p_val ^^= get_p_vec[i] * int(vals[i, 0])
assert p_val % mod == p_
if n % p_val == 0:
P = p_val
Q = n // P
break
print(k)
print(P)
'''
p = 8148641146281585626599965707019875487540363795516672614500530970713004312213378852992447549855928600229171345524388095399807768385341698813126095446000969
n = 78189483779073760819769596415493404181115737255987326126790953924148600157623709942134043192581448967829591214999561812461790206591977861764710056434977125005626712442593271233036617073503751799983263888626278748439349756982639988997517983470845431197233107232933125334078771472039280629203017666578936360521
enc = 39952631182502523101053953538875437560829302998610236142339435591980522271590392249355510253125310494063081880512061476177621613835835483055753316172267380484804011034657479491794064534740537749793563744927827732170347495398050941609682485707331552759412916426691849669362897656967530464847648838434750188588
q = n // p
assert p * q == n
d = pow(0x10001, -1, (p - 1) * (q - 1))
print(long_to_bytes(pow(enc, d, n)))
Psychophobia (11 solves)
This is a challenge that uses inverse function’s action when gcd of two values isn’t 1.
(That’s why I always use pow(val, -1, mod).)
psychophobia.py
#!/usr/bin/env python3
#
# Polymero
#
# Imports
from Crypto.Util.number import inverse
from secrets import randbelow
from hashlib import sha256
# Local imports
with open('flag.txt', 'rb') as f:
FLAG = f.read()
f.close()
# Header
HDR = r"""|
| _ ___
| | | / _ \
| _ _ _ _ ___ _____ _| |_ ___ | |_) )_ __ __
| | || || | | | \ \ / / _ \ / \ / _ \| _ <| |/ \/ /
| | \| |/ | |_| |\ v ( (_) | (| |) | (_) ) |_) ) ( () <
| \_ _/ \___/ > < \___/ \_ _/ \___/| __/ \_)__/\_\
| | | / ^ \ | | | |
| |_| /_/ \_\ |_| |_|
|
|"""
# Curve 25519 :: By^2 = x^3 + Ax^2 + x mod P
# https://en.wikipedia.org/wiki/Curve25519
# Curve Parameters
P = 2**255 - 19
A = 486662
B = 1
# Order of the Curve
O = 57896044618658097711785492504343953926856930875039260848015607506283634007912
# ECC Class
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
if not self.is_on_curve():
raise ValueError("Point NOT on Curve 25519!")
def is_on_curve(self):
if self.x == 0 and self.y == 1:
return True
if ((self.x**3 + A * self.x**2 + self.x) % P) == ((B * self.y**2) % P):
return True
return False
@staticmethod
def lift_x(x):
y_sqr = ((x**3 + A * x**2 + x) * inverse(B, P)) % P
v = pow(2 * y_sqr, (P - 5) // 8, P)
i = (2 * y_sqr * v**2) % P
return Point(x, (y_sqr * v * (1 - i)) % P)
def __repr__(self):
return "Point ({}, {}) on Curve 25519".format(self.x, self.y)
def __eq__(self, other):
return self.x == other.x and self.y == other.y
def __add__(self, other):
if self == self.__class__(0, 1):
return other
if other == self.__class__(0, 1):
return self
if self.x == other.x and self.y != other.y:
return self.__class__(0, 1)
if self.x != other.x:
l = ((other.y - self.y) * inverse(other.x - self.x, P)) % P
else:
l = ((3 * self.x**2 + 2 * A * self.x + 1) * inverse(2 * self.y, P)) % P
x3 = (l**2 - A - self.x - other.x) % P
y3 = (l * (self.x - x3) - self.y) % P
return self.__class__(x3, y3)
def __rmul__(self, k):
out = self.__class__(0, 1)
tmp = self.__class__(self.x, self.y)
while k:
if k & 1:
out += tmp
tmp += tmp
k >>= 1
return out
# Curve25519 Base Point
G = Point.lift_x(9)
# ECDSA Functions
# https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
def ECDSA_sign(m, priv):
h = int.from_bytes(sha256(m.encode()).digest(), 'big')
assert h % 2 == 0
assert priv % 2 == 1
k = (4 * randbelow(O)) % O
r = (k * G).x % O
s = (inverse(k, O) * (h + r * priv)) % O
if r % 2 == 1 and s % 2 == 0:
assert inverse(k, O) % 2 == 0
assert k % 8 == 0
return (r, s)
def ECDSA_verify(m, pub, sig):
r, s = sig
if r > 0 and r < O and s > 0 and s < O:
h = int.from_bytes(sha256(m.encode()).digest(), 'big')
u1 = (h * inverse(s, O)) % O
u2 = (r * inverse(s, O)) % O
if r == (u1 * G + u2 * pub).x % O:
return True
return False
# Server connection
print(HDR)
print("|\n| ~ Are you the psychic I requested? What can I call you?")
name = input("| > ")
msg = f"{name} here, requesting flag for pick-up."
print('|\n| ~ Alright, here is the message I will sign for you :: ')
print(f'| m = \"{msg}\"')
ITER = 500
RATE = 0.72
print(f'|\n| ~ The following {ITER} signatures are all broken, please fix them for me to prove your psychic abilities ~')
print(f'| If you get more than, say, {round(RATE * 100)}% correct, I will believe you ^w^')
# Server loop
success = 0
for k in range(ITER):
try:
d = (2 * randbelow(O) + 1) % O
Q = d * G
while True:
sig = ECDSA_sign(msg, d)
if not ECDSA_verify(msg, Q, sig):
break
print(f"|\n| {k}. Please fix :: {sig}")
fix = [int(i.strip()) for i in input("| > (r,s) ").split(',')]
if (sig[0] == fix[0]) and ECDSA_verify(msg, Q, fix):
print("nice!")
success += 1
else:
print("fuck you") # I added this part to check locally..
except KeyboardInterrupt:
print('\n|')
break
except:
continue
print(f"|\n| ~ You managed to fix a total of {success} signatures!")
if success / ITER > RATE:
print(f"|\n| ~ You truly are psychic, here {FLAG}")
else:
print("|\n| ~ Seems like you are a fraud after all...")
print('|\n|')
The challenge uses curve25519 for Elliptic Curve.
I did some search on it, and found that the order of the curve is 8 * (prime number).
Let’s call it Order = 8 * o.
And in the sign function, it’s setting k as multiple of 4.
Which will make multiple of 8, and multiple of 4 but not 8.
If we find the implementation for the inverse function, it looks like this:
def inverse(u, v):
"""inverse(u:long, v:long):long
Return the inverse of u mod v.
"""
u3, v3 = long(u), long(v)
u1, v1 = 1L, 0L
while v3 > 0:
q=divmod(u3, v3)[0]
u1, v1 = v1, u1 - v1*q
u3, v3 = v3, u3 - v3*q
while u1<0:
u1 = u1 + v
return u1
Without the last while loop,
we know inverse(v, m) == inverse(v // gcd(v, m), m // gcd(v, m))
So let’s observe the inverse(k, O) value which is in s.
It can be written to inverse(k, 8 * o).
If k is multiple of 4, but not 8, let’s write k = 4 * k0, k0 is odd.
Then we know inverse(k, O) == inverse(k0, 2 * o) without last while loop.
But in this case, while loop only adds 8 * o or 2 * o, so in conclusion
We can say inverse(k, O) == inverse(k0, 2 * o) (mod 2 * o).
(Important, this can say inverse(k, O) is always odd.)
So, inverse(k, O) == inverse(k // 4, O) (mod o).
Our goal is to divide the s value by 4 in this case.
(And make sure if the sending s is even, add p to make it odd, so that inverse function in verify won’t give any exceptions.)
send = (s * pow(4, -1, p)) % p
if send % 2 == 0:
send += p
io.sendlineafter("> (r,s) ", f"{r}, {send}")
In the same way, if k is multiple of 8, our goal is to divide s by 8.
send = (s * pow(8, -1, p)) % p
if send % 2 == 0:
send += p
io.sendlineafter("> (r,s) ", f"{r}, {send}")
The verifying is only consistent to p, not 8, because the curve’s base point is multiple of 8 already, so the order is o, not 8 * o.
Now we have to know if its multiple of 8, or multiple of 4 by over 72% accuracy.
We have some clues to do that.
r should be 50% even and 50% odd,
and s is defined this way,
s = (inverse(k, O) * (h + r * priv)) % O
If we know inverse(k, O) is even, we know that k is mutiple of 8.
Because as I said earlier, if k is multiple of 4, inverse(k, O) is always odd.
So we can count how many 2s are multiplied to (h + r*priv) and s.
If s has more 2, k is multiple of 8.
Now comes the trick. The chall said priv is odd, and h can be setted by ourselves.
So let’s find a h which is multiple of 8.
Then 2s contained in (h + r*priv) and r are the same.
Since we know both r and s, we can calculate this.
When r has more than s, or the same, we assume that k is multiple of 4.
When we run this with simple algorithm. It gives more accuracy than 72% more than 50% probability.
ex.sage
from Crypto.Util.number import *
from pwn import *
import random
from hashlib import sha256
p = 2^252 + 27742317777372353535851937790883648493
O = p * 8
#io = process(["python3", "psychophobia.py"])
io = remote("psychophobia.chal.idek.team", 1337)
def count2(n):
if n % 2 == 1:
return 0
if n % 4 == 2:
return 1
if n % 8 == 4:
return 2
return 3
name = ""
for i in range(10000):
name = str(i)
msg = f"{name} here, requesting flag for pick-up."
h = int.from_bytes(sha256(msg.encode()).digest(), 'big')
if h % 8 == 0:
break
io.sendlineafter(" ~ Are you the psychic I requested? What can I call you?\n| > ", name)
for i in range(500):
io.recvuntil("Please fix :: (")
r = Integer(int(io.recvuntil(", ")[:-2]))
s = Integer(int(io.recvuntil(")")[:-1]))
if r % 2 == 1 and s % 2 == 0:
send = (s * pow(8, -1, p)) % p
if send % 2 == 0:
send += p
io.sendlineafter("> (r,s) ", f"{r}, {send}")
elif r % 2 == 1 and s % 2 == 1:
send = (s * pow(4, -1, p)) % p
if send % 2 == 0:
send += p
io.sendlineafter("> (r,s) ", f"{r}, {send}")
else:
rcount = count2(r)
scount = count2(s)
if scount > rcount:
send = (s * pow(8, -1, p)) % p
if send % 2 == 0:
send += p
io.sendlineafter("> (r,s) ", f"{r}, {send}")
else:
send = (s * pow(4, -1, p)) % p
if send % 2 == 0:
send += p
io.sendlineafter("> (r,s) ", f"{r}, {send}")
print(i)
io.interactive()
Unsolved - Formal Security Poop (6 solves)
During the CTF, I knew the challenge’s vulnerabilty was that it doesn’t check if the point is on the curve. But till I heard the solution after the CTF ended, I have never heard about invalid curve attack(wish there is a challenge about this on cryptohack), so I couldn’t solve it during it. Next time when this attack appears, I wish I can solve it.
main.py
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
from ecc import *
class Vault:
def __init__(self) -> None:
self.secrets = {}
def authenticate(self, owner: str) -> None:
# Please see https://en.wikipedia.org/wiki/Proof_of_knowledge#Schnorr_protocol for how to interact
# But we do it over ellipthicc curves, because we already have a group setup :D
P, _ = self.secrets[owner]
print(f"Please prove that you are {owner}:")
T = Point.input("Give me the point T: ")
print('c =', c := randbelow(p))
s = int(input('s = '))
if s*G == T + c*P:
print("Successfully authenticated!")
else:
print("Who are you?? Go away!")
exit()
def sign(self, owner: str):
_, secret = self.secrets[owner]
m = int.from_bytes(sha512(secret).digest(), 'big') % p
k = randbelow(1 << 64) # [Note to self: make the bound dynamic on Y's order]
r = (k*G).x
s = (m + r*y)*pow(k, -1, p) % p
# Verify the signature with (r, _) == (1/s)*(m*G + r*Y)
return r, s
def store(self, secret: bytes, owner: str, P: Point):
if owner not in self.secrets:
self.secrets[owner] = P, secret
return
self.authenticate(owner)
self.secrets[owner] = P, secret
def retrieve(self, owner: str):
_, secret = self.secrets[owner]
self.authenticate(owner)
return secret
def session():
# x, X = gen_key(): your ephemeral keypair
X = Point.input("What is your ephemeral key?")
assert X != E.O
y, Y = gen_key()
B.print("Here is my public key:")
Y.print("Here is my ephemeral key:")
S = (y + H(Y)*b)*(X + H(X)*A) # Shared knowledge
return y, Y, sha512(H(S).to_bytes(32, 'big')).digest()[:16]
if __name__ == '__main__':
with open('flag.txt', 'rb') as f:
flag = f.read()
# a, A = gen_key(): your long term keypair
A = Point.input("What is your public key?")
b, B = gen_key()
y, Y, key = session()
# Communication is encrypted so that third parties can't steal your secrets!
aes = AES.new(key, AES.MODE_ECB)
#print(key)
vault = Vault()
vault.store(flag, 'Bob', B)
print(vault.secrets)
while 1:
print("""
[1] Store a secret
[2] Retrieve a secret
[3] Sign a secret
[4] Reinitialize session
""".strip())
opt = int(input('>>> '))
if opt == 1:
owner = input("Who are you? ")
secret = aes.decrypt(bytes.fromhex(input('secret = ')))
vault.store(unpad(secret, 16), owner, A)
print("Secret successfully stored!")
elif opt == 2:
owner = input("Who are you? ")
secret = pad(vault.retrieve(owner), 16)
print("Here is your secret:")
print('secret =', aes.encrypt(secret).hex())
elif opt == 3:
owner = input("Whose secret should I sign? ")
r, s = vault.sign(owner)
print("Here is the signature:")
print('r =', r)
print('s =', s)
elif opt == 4:
y, Y, key = session()
aes = AES.new(key, AES.MODE_ECB)
else:
print("My secrets are safe forever!", flush=True)
exit()
I will skip the ecc.py. It is a file implementing elliptic curve for secp128r1, but without checking if a point is on the curve.
The basic idea for this chall is using this info of S:
When we set $A$ to 0, and $X$ to a point(doesn’t have to be on secp128r1) with low order, we can get the value for $y + H(Y)*b$ with discrete_log. If we get $y$ and $H(Y)$, we can get $b$ as remainder of $X$’s order as modulus.
This attack(Invalid curve attack) works because curve parameter b is never used during point addition or multiplication. So we can use any kind of curve with GF(p) and parameter a. Lots of order exist in that kind of code, and we can dig up some small prime orders, and use Pohlig-Hellman algorithm.
To get value y from this chall, we have to use the sign function, which sets k to a small value under 2^64. https://eprint.iacr.org/2019/023.pdf this explains very well about this attack.
It was pretty surprising that eventually I have to use all the choices that exist to solve this.
I implemented getting small-ordered points by myself, and it wasn’t much different from the author’s.
ex.sage
from Crypto.Util.number import *
from pwn import *
import random
from ecc import *
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
#io = process(["python3", "main.py"])
io = remote("formal-security-poop.chal.idek.team", 1337)
io.sendlineafter("x = ", "0")
io.sendlineafter("y = ", "0")
io.sendlineafter("x = ", str(Gx))
io.sendlineafter("y = ", str(Gy))
io.recvuntil("x = ")
Bx = int(io.recvline())
io.recvuntil("y = ")
By = int(io.recvline())
io.recvuntil("x = ")
Yx = int(io.recvline())
io.recvuntil("y = ")
Yy = int(io.recvline())
A = Point(E, 0, 0)
B = Point(E, Bx, By)
X = G
Y = Point(E, Yx, Yy)
S = Y + H(Y)*B
key = sha512(H(S).to_bytes(32, 'big')).digest()[:16]
secret = b"soon_haari_stupid_idiot_doesnt_know_invalid_curve_attack"
name = "soon_haari"
io.sendlineafter(">>> ", "1")
io.sendlineafter("Who are you? ", name)
aes = AES.new(key, AES.MODE_ECB)
send = aes.encrypt(pad(secret, 16))
io.sendlineafter("secret = ", bytes.hex(send))
pairs = []
prod = 1
while 1:
b_ = Integer(random.randrange(1, p - 1))
E_ = EllipticCurve(GF(p), [0xfffffffdfffffffffffffffffffffffc, b_])
factors = list(E_.order().factor())
for a, b in factors:
if b > 1:
continue
if a < 10000 or a >= 100000:
continue
if prod % a == 0:
continue
while 1:
G_ = E_.random_element() * (E_.order() // a)
if G_.order() == a:
break
pairs.append((b_, a, G_))
prod *= a
if prod > p:
break
#print(pairs)
remain = []
modular = []
print(f"Number of steps: {len(pairs)}")
for pair in pairs:
while 1:
io.sendlineafter(">>> ", "4")
b_, a, G_ = pair
G_ = Point(E, G_.xy()[0], G_.xy()[1])
io.sendlineafter("x = ", str(G_.x))
io.sendlineafter("y = ", str(G_.y))
io.recvuntil("x = ")
Bx = int(io.recvline())
io.recvuntil("y = ")
By = int(io.recvline())
io.recvuntil("x = ")
Yx = int(io.recvline())
io.recvuntil("y = ")
Yy = int(io.recvline())
Y = Point(E, Yx, Yy)
if H(Y) % a > 0:
break
num_data = 5
m = int.from_bytes(sha512(secret).digest(), 'big') % p
t_list = []
a_list = []
B_ = 2^64
for i in range(num_data):
io.sendlineafter(">>> ", "3")
io.sendlineafter("Whose secret should I sign? ", name)
io.recvuntil("r = ")
r = Integer(int(io.recvline()))
io.recvuntil("s = ")
s = Integer(int(io.recvline()))
t_list.append((r / s) % p)
a_list.append((-m / s) % p)
mat = []
for i in range(num_data):
line = [0] * (num_data + 2)
line[i] = p
mat.append(line)
t_list.append(B_ / p)
t_list.append(0)
a_list.append(0)
a_list.append(B_)
mat.append(t_list)
mat.append(a_list)
mat = Matrix(mat).LLL()
ks = mat[1]
k = -ks[i]
y = ((k + a_list[i]) / t_list[i]) % p
assert G * y == Y
io.sendlineafter(">>> ", "2")
io.sendlineafter("Who are you? ", name)
io.sendlineafter("x = ", "0")
io.sendlineafter("y = ", "0")
io.sendlineafter("s = ", "0")
io.recvuntil("secret = ")
enc = bytes.fromhex(io.recvline().decode()[:-1])
assert len(enc) == 64
S = Point(E, 0, 0)
for i in range(a):
S = Point(E, int(S.x), int(S.y))
key = sha512(H(S).to_bytes(32, 'big')).digest()[:16]
aes = AES.new(key, AES.MODE_ECB)
if aes.encrypt(pad(secret, 16)) == enc:
assert i * G_ == S
b_remain = ((i - y) / H(Y)) % a
remain.append(b_remain)
modular.append(a)
print(b_remain, a)
break
S = S + G_
b = crt(remain, modular)
assert b * G == B
io.sendlineafter(">>> ", "2")
io.sendlineafter("Who are you? ", "Bob")
io.sendlineafter("x = ", "0")
io.sendlineafter("y = ", "0")
io.recvuntil("c = ")
c = Integer(int(io.recvline()))
io.sendlineafter("s = ", str(c * b))
io.recvuntil("secret = ")
secret = bytes.fromhex(io.recvline().decode())
flag = unpad(aes.decrypt(secret), 16)
print(flag)
io.interactive()