These are write-ups for the crypto challenges I wrote for BuckeyeCTF 2021. Source code and solve scripts can be found here: https://github.com/cscosu/buckeyectf-2021/tree/master/crypto
Stats: 141 solves / 40 points / easy
Let's exchange the flag (securely):
nc crypto.chall.pwnoh.io 13374
import random
import hashlib
# Mac/Linux: pip3 install pycryptodome
# Windows: py -m pip install pycryptodome
import Crypto.Util.number as cun
from Crypto.Cipher import AES
rand = random.SystemRandom()
FLAG = b"buckeye{???????????????????????????????????????????????????????}"
def diffie_hellman(message: bytes):
p = cun.getPrime(512)
g = 5
print(f"p = {p}")
print(f"g = {g}")
a = rand.randrange(2, p - 1) # private key
A = pow(g, a, p) # public key
# g ^ a === A (mod p)
# It's computationally infeasible for anyone else to derive a from A
print(f"A = {A}")
B = int(input("Give me your public key B: "))
if not (1 < B < p - 1):
print("Suspicious public key")
return
# B ^ a === (g ^ b) ^ a === g ^ (ab) (mod p)
# Nobody can derive this shared secret except us!
shared_secret = pow(B, a, p)
# Use AES, a symmetric cipher, to encrypt the flag using the shared key
key = hashlib.sha1(cun.long_to_bytes(shared_secret)).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(message)
print(f"ciphertext = {ciphertext.hex()}")
print("I'm going to send you the flag.")
print("However, I noticed that an FBI agent has been eavesdropping on my messages,")
print("so I'm going to send it to you in a way that ONLY YOU can decrypt the flag.")
print()
diffie_hellman(FLAG)
This is Diffie-Hellman key exchange: the server plays the role of Alice, and you play the role of Bob.
To calculate the shared key, pick a random
import pwn
import Crypto.Util.number as cun
from Crypto.Cipher import AES
import hashlib
import random
if pwn.args.REMOTE:
io = pwn.remote("localhost", 1024)
else:
io = pwn.process("python3 ../deploy/server.py", shell=True)
io.recvuntil("decrypt the flag.\n")
io.recvline()
p = int(io.recvlineS().strip().split(" = ")[-1])
g = int(io.recvlineS().strip().split(" = ")[-1])
A = int(io.recvlineS().strip().split(" = ")[-1])
b = random.randrange(2, p - 1)
B = pow(g, b, p)
io.sendlineafter("Give me your public key B: ", str(B))
ct = bytes.fromhex(io.recvlineS().strip().split(" = ")[-1])
shared_secret = pow(A, b, p)
key = hashlib.sha1(cun.long_to_bytes(shared_secret)).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
pt = cipher.decrypt(ct)
print(pt)
Stats: 34 solves / 90 points / easy
No public key this time!
nc crypto.chall.pwnoh.io 13386
This is the same as the first Key exchange challenge, but no public key
for i in range(3, 1024):
if (p - 1) % i == 0:
break
else:
io.close()
return False
print(i)
b = (p - 1) // i
B = pow(g, b, p)
Stats: 21 solves / 465 points / medium
I heard everyone uses Curve25519 these days. I'm sure it's super secure, so I'll even let you pick a base point!
nc crypto.chall.pwnoh.io 13373
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import size, long_to_bytes
import os
import hashlib
from collections import namedtuple
FLAG = b"buckeye{???????????????????}"
Point = namedtuple("Point", ("x", "z"))
Curve = namedtuple("Curve", ("a", "b"))
p = 2 ** 255 - 19
C = Curve(486662, 1)
"""
Implements the Montgomery Ladder from https://eprint.iacr.org/2017/212.pdf
"""
def point_add(P: Point, Q: Point, D: Point) -> Point:
"""
Algorithm 1 (xADD)
"""
V0 = (P.x + P.z) % p
V1 = (Q.x - Q.z) % p
V1 = (V1 * V0) % p
V0 = (P.x - P.z) % p
V2 = (Q.x + Q.z) % p
V2 = (V2 * V0) % p
V3 = (V1 + V2) % p
V3 = (V3 * V3) % p
V4 = (V1 - V2) % p
V4 = (V4 * V4) % p
x = (D.z * V3) % p
z = (D.x * V4) % p
return Point(x, z)
def point_double(P: Point) -> Point:
"""
Algorithm 2 (xDBL)
"""
V1 = (P.x + P.z) % p
V1 = (V1 * V1) % p
V2 = (P.x - P.z) % p
V2 = (V2 * V2) % p
x = (V1 * V2) % p
V1 = (V1 - V2) % p
V3 = (((C.a + 2) // 4) * V1) % p
V3 = (V3 + V2) % p
z = (V1 * V3) % p
return Point(x, z)
def scalar_multiplication(P: Point, k: int) -> Point:
"""
Algorithm 4 (LADDER)
"""
if k == 0:
return Point(0, 0)
R0, R1 = P, point_double(P)
for i in range(size(k) - 2, -1, -1):
if k & (1 << i) == 0:
R0, R1 = point_double(R0), point_add(R0, R1, P)
else:
R0, R1 = point_add(R0, R1, P), point_double(R1)
return R0
def normalize(P: Point) -> Point:
if P.z == 0:
return Point(0, 0)
return Point((P.x * pow(P.z, -1, p)) % p, 1)
def legendre_symbol(x: int, p: int) -> int:
return pow(x, (p - 1) // 2, p)
def is_on_curve(x: int) -> bool:
y2 = x ** 3 + C.a * x ** 2 + C.b * x
return legendre_symbol(y2, p) != (-1 % p)
def main():
print("Pick a base point")
x = int(input("x: "))
if size(x) < 245:
print("Too small!")
return
if x >= p:
print("Too big!")
return
if not is_on_curve(x):
print("That x coordinate is not on the curve!")
return
P = Point(x, 1)
a = int.from_bytes(os.urandom(32), "big")
A = scalar_multiplication(P, a)
A = normalize(A)
key = hashlib.sha1(long_to_bytes(A.x)).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(FLAG, 16))
print(ciphertext.hex())
if __name__ == "__main__":
main()
This is the same setup as Key exchange 2, except now the group is Curve25519. Since the order of the group has a small factor of 8, we can do a small subgroup attack again:
# Pick a generator G
G = Point(6, 1)
subgroup_order = (2 ** 252 + 27742317777372353535851937790883648493)
order = 8 * subgroup_order
assert normalize(scalar_multiplication(G, 2)) != Point(0, 0)
assert normalize(scalar_multiplication(G, 4)) != Point(0, 0)
assert normalize(scalar_multiplication(G, 8)) != Point(0, 0)
assert normalize(scalar_multiplication(G, subgroup_order)) != Point(0, 0)
assert normalize(scalar_multiplication(G, order)) == Point(0, 0)
B = normalize(scalar_multiplication(G, order // 8))
assert normalize(scalar_multiplication(B, 8)) == Point(0, 0)
subgroup = [normalize(scalar_multiplication(B, i)) for i in range(1, 8 + 1)]
xs = sorted([B.x for B in subgroup])
shared_secrets = [hashlib.sha1(long_to_bytes(x)).digest()[:16] for x in xs]
io = pwn.process("python3 ../src/chall.py", shell=True)
io.sendlineafter("x: ", str(xs[-1]))
ct = bytes.fromhex(io.recvlineS().strip())
for shared_secret in shared_secrets:
cipher = AES.new(shared_secret, AES.MODE_ECB)
print(cipher.decrypt(ct))
Stats: 33 solves / 441 points / hard
I use whatever exponent I want
from Crypto.Util.number import getPrime, inverse, bytes_to_long
e = 1440
p = getPrime(1024)
q = getPrime(1024)
n = p * q
flag = b"buckeye{???????????????????????????????}"
c = pow(bytes_to_long(flag), e, n)
print(f"e = {e}")
print(f"p = {p}")
print(f"q = {q}")
print(f"c = {c}")
# e = 1440
# p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
# q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
# c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754
This is a typical RSA encryption except:
Instead find all x satisfying:
Actually
Final script:
import Crypto.Util.number as cun
from pprint import pprint
def roots_of_unity(e, phi, n, rounds=500):
# Divide common factors of `phi` and `e` until they're coprime.
phi_coprime = phi
while cun.GCD(phi_coprime, e) != 1:
phi_coprime //= cun.GCD(phi_coprime, e)
# Don't know how many roots of unity there are, so just try and collect a bunch
roots = set(pow(i, phi_coprime, n) for i in range(1, rounds))
assert all(pow(root, e, n) == 1 for root in roots)
return roots, phi_coprime
e = 1440
p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754
n = p * q
# Problem: e and phi are not coprime - d does not exist
phi = (p - 1) * (q - 1)
# Find e'th roots of unity modulo n
roots, phi_coprime = roots_of_unity(e, phi, n)
# Use our `phi_coprime` to get one possible plaintext
d = pow(e, -1, phi_coprime)
m = pow(c, d, n)
assert pow(m, e, n) == c
# Use the roots of unity to get all other possible plaintexts
ms = [(m * root) % n for root in roots]
ms = [cun.long_to_bytes(m) for m in ms]
pprint(ms)
for m in ms:
if m.startswith(b"buckeye"):
print(f"Flag: {m}")
break
else:
print("No flag found :(")
If you know a better way to implement roots_of_unity()
, let me know. I implemented an algorithm from Wikipedia but it doesn't seem very clean.
This challenge is based on Broken RSA from CryptoHack, but the intended solution is different. Unfortunately, almost nobody did the intended solution and instead did something similar to Y-CTF's solution:
from Crypto.Util.number import long_to_bytes
e = 1440
p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754
rmodp = (c % p).nth_root(e, all=True)
rq = (c % q).nth_root(e)
for rp in rmodp:
r = crt(int(rp), int(rq), p, q)
flag = long_to_bytes(r)
if b"buckeye" in flag:
print(flag.decode())
I'm not sure how to prevent these kind of solutions, but I at least should've made the flag much longer (more than 2048 bytes) so that people would actually need to enumerate all possible plaintexts.
Stats: 15 solves / 476 points / hard
Surely the Legendre symbol is a great random number generator, right?
nc crypto.chall.pwnoh.io 13375
#!/usr/bin/env python3
import random
import os
rand = random.SystemRandom()
FLAG = b"buckeye{?????????????????????}"
def is_prime(n, rounds=32):
return all(pow(rand.randrange(2, n), n - 1, n) == 1 for _ in range(rounds))
class RNG:
def __init__(self, p: int, a: int):
self.p = p
self.a = a
def next_bit(self) -> int:
ans = pow(self.a, (self.p - 1) // 2, self.p)
self.a += 1
return int(ans == 1)
def next_byte(self) -> int:
ans = 0
for i in range(8):
ans |= self.next_bit() << i
return ans
def next_bytes(self, n: int) -> bytes:
return bytes(self.next_byte() for _ in range(n))
def main():
p = int(input("Give me a prime number: "))
if not (256 <= p.bit_length() <= 512):
print("Wrong bit length")
return
if not is_prime(p):
print("Fermat tells me your number isn't prime")
return
a = rand.randrange(2, p)
rng = RNG(p, a)
plaintext = b"Hello " + os.urandom(48).hex().encode()
print("Have some ciphertexts:")
for _ in range(32):
s = rng.next_bytes(len(plaintext))
c = bytes(a ^ b for a, b in zip(s, plaintext))
print(c.hex())
if plaintext == input("Guess the plaintext:\n").encode():
print(f"Congrats! Here's the flag: {FLAG}")
else:
print("That's wrong")
main()
In short:
When I wrote this problem, my first idea was just to use a Carmichael number in order to pass the Fermat primality test.
def carmichael(start):
start = start if start % 2 == 0 else start - 1
k = start
while True:
p1 = 6 * k + 1
p2 = 12 * k + 1
p3 = 18 * k + 1
if cun.isPrime(p1) and cun.isPrime(p2) and cun.isPrime(p3):
n = p1 * p2 * p3
return n
k += 2
This passed the Fermat primality test, but it seemed to produce 50% ones and zeros from the RNG.
I wasn't sure why this was the case, but next I tried strong pseudoprimes. Specifically, I chose
Somehow, this made the RNG produce 97% zero bits in its output, which was more than enough to get the flag. It still isn't clear to me why some Carmichael numbers produce more biased outputs than others, but it seems like an interesting problem.
Stats: 15 solves / 476 points / medium
You'll need a supercomputer to pass my VDF
nc crypto.chall.pwnoh.io 13376
from gmpy2 import is_prime, mpz
from random import SystemRandom
rand = SystemRandom()
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
def get_prime(bit_length):
while True:
x = mpz(1)
while x.bit_length() < bit_length:
x *= rand.choice(PRIMES)
if is_prime(x + 1):
return x + 1
def get_correct_answer():
# Implementation redacted
return -1
p = get_prime(1024)
q = get_prime(1024)
n = p * q
print(f"n = {n}")
print("Please calculate (59 ** 59 ** 59 ** 59 ** 1333337) % n")
ans = int(input(">>> "))
if ans == get_correct_answer():
print("WTF do you own a supercomputer? Here's your flag:")
print("buckeye{????????????????????????????????????}")
else:
print("WRONG")
VDF stands for Verifiable Delay Function: there's an existing VDF where you have to calculate
The solution here is to first factor
To solve the challenge, notice that
e = 1333337
phi = (p - 1) * (q - 1)
phi1 = euler_phi(phi)
phi2 = euler_phi(phi1)
a = pow(59, e, phi2)
b = pow(59, a, phi1)
c = pow(59, b, phi)
ans = pow(59, c, n)
I also saw some creative solutions from randomdude999 and Yehonatan which did not require factoring