This post will present my writeups for some crypto challenges I solved in the Imaginary CTF 2023. Thanks the authors for the amazing challenges.
Rsa
Description: I think I did my RSA right…
Solves: 262
Just extract d and n from key file to decrypt ciphertext.
1
2
3
4
5
6
7
8
9
10
11
12
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization
from cryptography import x509
with open("private.pem", "rb") as f:
key = serialization.load_pem_private_key(f.read(), None, default_backend())
n=key.private_numbers().public_numbers.n
d=key.private_numbers().d
with open("flag (1).enc", "rb") as f2:
print(long_to_bytes(pow(bytes_to_long(f2.read()),d,n)))
Flag is: ictf{keep_your_private_keys_private}
Signer
Description: My new secure signing service is up! It uses state-of-the-art cryptographically secure hashes and can sign anything! Except, of course, the password.
Solves: 94
Given source
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import textwrap
from binascii import crc32
from Crypto.Util.number import getPrime
p, q = getPrime(1024), getPrime(1024)
n = p*q
e = 65537
d = pow(e, -1, (p-1)*(q-1))
PASSWORD = b"give me the flag!!!"
while True:
print("1. Sign")
print("2. Get flag")
choice = int(input())
if choice == 1:
print("Enter message:")
message = input().encode()
# crc32 is secure and has no collisions, but just in case
if message == PASSWORD or crc32(message) == crc32(PASSWORD):
print("Stop this trickery!")
exit()
print("Signature:", pow(crc32(message), d, n))
elif choice == 2:
print("Enter the signature for the password:")
s = int(input())
if pow(s, e, n) == crc32(PASSWORD):
print("You win! The flag is", open("flag.txt").read())
exit()
else:
print("Wrong.")
exit()
They give us an oracles of computing signatures and we need to submit a valid signature for crc32(PASSWORD) to get the flag. We can use homomorphic property of RSA to bypass check in the oracles
\[\begin{equation} \begin{split} \epsilon(m_1).\epsilon(m_2) \: mod \: n & = {m_1}^e{m_2}^e \: mod \: n \\ & = {(m_1m_2)}^e \: mod \: n \\ & = \epsilon(m_1.m_2) \end{split} \end{equation}\]Assume $ crc32(Password) = a*b $, we can compute signatures of $a$ and $b$ and submit $ sig(a) * sig(b) $ to get the flag. One more problem is that the oracles compute sig(crc(m)) not sig(m) so we need to calculate preimage $a_1$ such that $ a = crc(a_1) $. I use https://github.com/theonlypwner/crc32 to calculate preimage.
Flag is: ictf{m4ybe_crc32_wasnt_that_secure_after_all_1ab93213}
Wasteful
Description: I am going to make RSA encryption more time-consuming for no reason 😛
Solves: 31
Given source
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from Crypto.Util.number import *
from math import gcd
def keygen(sz):
p = getPrime(sz // 2)
q = getPrime(sz // 2)
n = p * q
phi = (p - 1) * (q - 1)
e_fast = getPrime(sz // 2)
# to make encryption more time consuming :P
e_slow = e_fast + getPrime(sz // 3) * phi
d = pow(e_fast, -1, phi)
return (n, e_slow), (n, e_fast), (n, d)
def encrypt(pub, m):
n, e = pub
return pow(m, e, n)
def decrypt(priv, c):
n, d = priv
return pow(c, d, n)
pub, pub_fast, priv = keygen(2048)
m = bytes_to_long(open("flag.txt", "rb").read().strip())
c = encrypt(pub, m)
assert c == encrypt(pub_fast, m)
assert decrypt(priv, c) == m
print(f"{pub = }")
print(f"{c = }")
#pub = (13922840822259331816327061476419085409003512519528232469661604921423111313933598569871108546042864180459201549111178812056125732062953204575105829153985440916358190133642640001059768522480269302460718708597523393249631888987925111597599833550446912844403320258488415701628616610291446078064678789122886626285576964983117608034972639529880315364530395658464093479171544352975507100901794069628879853771787404835325718642690170628943504486705897282590391844395048189949020318348859452241379637822658476872641393738097989171169214581791719140741349554748016829670973465416125341357284757048506380319235703137899963208097, 277280553454648256942834244379334472844168843473349557354045626945887508188843789771287658693103957086560979814144224475018152887866998026452048010146805033029525535857427508882228600591838528622357772029813779190474001956391284442790327418967008241712383374750163158501752035607501218757269377329115862935993211034408859090869371053922670217394364484435238584857739198196990517123089953446738914179515819217861804510588560805960014326909359351025582398395246863003472699126965102937701727970546875134667199496557865907051073237849103589853403297723219825816214258909806838856777367332603146213417602038287539276024671910161582026600672105045278321812944891449538504092047724097803562730455612681768718159973804451251572816656604960574129566605495957657313103014678987914865218770999608008584731005908772508291497450420251)
#c = 3829822460565637897613746990073994763941184171034737019836828390881076647859928468862763977005814025279072259387758773244151849201650347661717265009919615554395232777636705330792559486048004076300537706604078026741727734943374711480077394341022197696120902084993991738576670236710557122356593411988288326114827264936321401579532665129353852827951354347055111972043781820183887400365339563091888343224947709711699474542183525971689156145628294192147447087789859929759168015997297169275809161690938900939934830602427271340102001253593076013316161869089892572516396348368906753304918487695981844135741146949836634949417
Solution:
After searching for a while, I found in the RSA survey by Dan Boneh that the idea of this challenge is actually one of the techniques that Wiener describes to avoid his famous Wiener attack, which is replacing the public key by $e_1 = e + k*\phi(n)$. Note that the output of encryption/decryption process are still the same.
In this challenge, $e_{fast}$, $e_{slow}$ is $e$ and $e_1$, but only $e_{slow}$ is given. Also $k$ is private, however, in this challenge we can leak $k$ due to it being small. We have
\[e_{fast} = e_{slow} + k*\phi(n) = e_{slow} - k*(p+q-1) + k*n\]Because $e_{slow} - k*(p+q-1)$ is small compare to $n$, we can take $e_{slow}$ modulo $n$ to get an approximate of k, in this challenge is $k-1$.
1
2
3
4
5
6
n=pub[0]
e_slow=pub[1]
k = e_slow//n+1
print(k)
assert isPrime(k) # recheck if k is correct?
# k=19915515590133170748373804800708533672571612647466247083266942377756576397466826465379590032305304204393555346411013151213971274909418468886929609093882043135613083658266238483093902691215386168949233079363
Next, by computing
\[\frac{k*n+k-e_{slow}}{k}=\frac{e_{fast}}{k} + p + q\]We can get MSB of $p+q$ as \(\frac{e_{fast}}{k}\) is only ~2048/6=341 bits. Now we can solve the equation $x^2 - MSB(p+q)*x+n$ to get MSB of p or q (You can try to prove it, I’m too lazy to post my proof xD. My approach is to deal with the quadratic equation root formula xD).
Finally, the challenge turn into a simple Coppersmith problem.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
k=19915515590133170748373804800708533672571612647466247083266942377756576397466826465379590032305304204393555346411013151213971274909418468886929609093882043135613083658266238483093902691215386168949233079363
msb=-(e_slow-k*n-k)//k
delta= msb**2 - 4*pub[0]
approx_p=(msb+isqrt(delta))//2
K=Zmod(n)
x = PolynomialRing(K,'x').gen()
f = x + K((approx_p>>355)<<355)
p=int(f.small_roots(X=2**355,beta=0.49,epsilon=1/8)[0]+K((approx_p>>355)<<355))
assert n%p==0 and p<n
q=n//p
phi=(p-1)*(q-1)
print(long_to_bytes(pow(c,inverse(e_slow,phi),n)))
Flag is ictf{just_an_obligatory_coppersmith_challenge}
Blind guess
Given source:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from random import getrandbits
from galois import GF
import numpy as np
DECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"
F = GF(13) # lucky number
n = 10
# Let's not use a singular matrix, please.
# We do quality random over here.
M = [[0]]
while np.linalg.det(M) == 0:
M = F.Random((n, n))
money = 15000
cards = F.Random(n)
while all(int(c) == 0 for c in cards):
cards = F.Random(n)
while money > 0:
print('balance:', money)
choice = input('> ')
if choice == 'buy flag':
if money < 1_000_000_000:
print("You're too poor!")
continue
from redacted import FLAG
money -= 1_000_000_000
print("What a guess god! Here's your flag:", FLAG)
elif choice == 'play':
bet = int(input('bet: '))
assert money >= bet > 0
print("Can you blindly guess my cards?")
cards = np.linalg.matrix_power(M, getrandbits(32)) @ cards # shuffle cards
guess = M @ F([*map(DECK.index, input('guess: ').split())]) # blind guess
total = sum(cards == guess)
print(f'You guessed {total} cards! My hand was:', *[DECK[c] for c in cards])
money += 2*(total - 5)*bet
elif choice == 'exit':
print("Chickened out, huh? No flag for you.")
exit()
print("Woops... Looks like you guessed your way out of money :>")
Description: So guessy… I sure hope there’s no guess gods out there.
Solves: 8
I will explain my solution later when I has free time TvT.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from random import getrandbits
from galois import GF as gl
import numpy as np
from pwn import *
from sage.all import *
from randcrack import RandCrack
DECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"
F = gl(int(13)) # lucky number
conn = remote('blind-guess.chal.imaginaryctf.org',1337)
q=conn.recvlines(1)
mat=[]
guess=[]
hist=[]
for j in range(10):
print(j)
freq=[[0 for i in range(13)] for _ in range(10)]
for i in range(125):
conn.sendline(b'play')
conn.sendline(b'1')
q=conn.recvlines(1)
if j!=0 or i != 0:
q=conn.recvlines(1)
a=[0 for i in range(j)]+[1]+[0 for i in range(10-j-1)]
payl=''
for ind in a:
payl+=DECK[ind]
payl+=' '
conn.sendline(payl.encode())
q=conn.recvlines(1)
total=int(q[0].split(b'guessed ')[1].split(b' cards')[0])
card=[DECK.index(i) for i in q[0].split(b'My hand was: ')[1].decode().split()]
hist.append(card)
if total == 0:
for i in range(10):
freq[i][card[i]] -= 9999
else:
for i in range(10):
freq[i][card[i]] += total
guess=[i.index(max(i)) for i in freq]
mat.append(guess)
mat=Matrix(GF(13),mat)
mat=mat.transpose()
print(mat)
mat1=list(mat)
R.<z>=mat.charpoly().splitting_field()
J, P = mat.change_ring(R).jordan_form(transformation=True)
DECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"
rc=RandCrack()
for i in range(624):
print(i)
lam = J[-1][-1]
c=vector(GF(13),hist[-624+i])
d=vector(GF(13),hist[-625+i])
l=(P^-1*d)
r=(P^-1*c)
rand=int((r[-1]*l[-1]^-1).log(J[-1][-1]))
rc.submit(rand)
money=[100,1100,12100,133100,1464100,16105100,177156100]
for i in range(7):
conn.sendline(b'play')
conn.sendline(str(money[i]).encode())
pred=rc.predict_getrandbits(32)
c=vector(GF(13),hist[-1])
mat2=Matrix(GF(13),mat1)
d=list((mat2**pred)*c)
hist.append(d)
print(d)
payload=''
for ind in d:
payload+=DECK[ind]
payload+=' '
print(payload)
conn.sendline(payload.encode())
conn.sendline(b'buy flag')
conn.interactive()
Flag is: ictf{Why_gu355_wh3n_y0u_c4n_j0rd4n}