TSJ CTF 2022 WriteUps
This time I created several challenges for TSJ CTF 2022, and I published my challenges and writeups in maple3142/My-CTF-Challenges. Due to GitHub's poor support of mathjax rendering in markdown, I decided to create this one for readers of Crypto writeups.
For other categories, please read it here
Futago
- Category: Crypto, CSC (Cursed Shaman Challenges, guessy challenges in TSJ CTF)
- Score: 56/100 (CSC)
- Solves: 14/428
Description
Who need source for RSA challenges?
Overview
See the README of this challenge.
Solution
Stage 1
Guess that two public keys shares a prime, so you can factor it with gcd.
Stage 2
Found out that
Stage 3
You got two seemingly normal 2048 bits RSA public key
If you write them like this:
Then substracting them:
Suppose
Then you can multiply them together:
It is easy to see 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
67from Crypto.PublicKey import RSA
from Crypto.Util.number import *
def read_stage(stage):
with open(f"{stage}/key1.pub", "rb") as f:
key1 = RSA.import_key(f.read())
with open(f"{stage}/key2.pub", "rb") as f:
key2 = RSA.import_key(f.read())
with open(f"{stage}/flag.txt.key1.enc", "rb") as f:
c1 = bytes_to_long(f.read())
with open(f"{stage}/flag.txt.key2.enc", "rb") as f:
c2 = bytes_to_long(f.read())
ret = (key1.n, key1.e, c1, key2.n, key2.e, c2)
return map(ZZ, ret)
def solve1():
n1, e1, c1, n2, e2, c2 = read_stage("stage1")
p = gcd(n1, n2)
q = n1 // p
d = inverse_mod(e1, (p - 1) * (q - 1))
m = power_mod(c1, d, n1)
return long_to_bytes(m)
def solve2():
n1, e1, c1, n2, e2, c2 = read_stage("stage2")
g, a, b = xgcd(e1, e2)
mg = power_mod(c1, a, n1) * power_mod(c2, b, n1) % n1
m = mg.nth_root(g)
return long_to_bytes(m)
def solve3():
n1, e1, c1, n2, e2, c2 = read_stage("stage3")
def fermat(x, mx):
a = floor(sqrt(x))
b2 = a * a - x
cnt = 0
while True:
if is_square(b2):
b = floor(sqrt(b2))
yield a + b, a - b
a += 1
cnt += 1
if cnt == mx:
return
b2 = a * a - x
ar = list(fermat(n1 * n2, 1000000))
# print(ar)
assert len(ar) == 2
assert set(ar[1]) == set([n1, n2])
p1 = gcd(ar[0][1], n1)
# print(p1)
p2 = gcd(ar[0][0], n2)
# print(p2)
q1 = n1 // p1
d1 = inverse_mod(e1, (p1 - 1) * (q1 - 1))
m = power_mod(c1, d1, n1)
return long_to_bytes(m)
print(solve1() + solve2() + solve3())
RNG++
- Category: Crypto
- Score: 213/500
- Solves: 21/428
This is actually a broken version of
RNG+++
.
Description
I encrypted the flag and messages by xoring them with a random number generator.
Overview
You got a simple LCG with randmsg
are encrypted by the same way.
Solution
The first thing to notice is randmsg
generated messages are all decimal digits, and they are 0x30
to 0x39
in ASCII. It is obvious that their binary representation are all 0011????
, so we can get serveral non continuous bits of states
The most simple unintended solution is to use z3
. You just let the state be
Another more mathematical unintended solution by @Kuruwa: Since
The intended solution will be in the writeup of RNG+++
.
babyRSA
- Category: Crypto
- Score: 276/500
- Solves: 13/428
Description
Overview
We have
Solution
By substituting the coorinates of
Define another polynomial
For more details: Extensions of Coppersmith algorithm
Once you got 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
28from Crypto.Util.number import *
proof.arithmetic(False)
n = 1084688440161525456565761297723021343753253859795834242323030221791996428064155741632924019882056914573754134213933081812831553364457966850480783858044755351020146309359045120079375683828540222710035876926280456195986410270835982861232693029200103036191096111928833090012465092747472907628385292492824489792241681880212163064150211815610372913101079146216940331740232522884290993565482822803814551730856710106385508489039042473394392081462669609250933566332939789
xx, yy = (
1079311510414830031139310538989364057627185699077021276018232243092942690870213059161389825534830969580365943449482350229248945906866520819967957236255440270989833744079711900768144840591483525815244585394421988274792758875782239418100536145352175259508289748680619234207733291893262219468921233103016818320457126934347062355978211746913204921678806713434052571635091703300179193823668800062505275903102987517403501907477305095029634601150501028521316347448735695,
950119069222078086234887613499964523979451201727533569872219684563725731563439980545934017421736344519710579407356386725248959120187745206708940002584577645674737496282710258024067317510208074379116954056479277393224317887065763453906737739693144134777069382325155341867799398498938089764441925428778931400322389280512595265528512337796182736811112959040864126090875929813217718688941914085732678521954674134000433727451972397192521253852342394169735042490836886,
)
e = 65537
r = ZZ((yy ^ 2 - xx ^ 3) % n)
P = PolynomialRing(Zmod(n), "q")
q = P.gen()
f = r - q
q = ZZ(f.monic().small_roots(X=2 ^ 512, epsilon=0.8, beta=0.66)[0])
p = n // q
assert p * q == n
print((log(p) / log(n)).n())
E = EllipticCurve(Zmod(n), [p, q])
phi = E.change_ring(GF(p)).order() * E.change_ring(GF(q)).order()
d = inverse_mod(e, phi)
x, y = (d * E(xx, yy)).xy()
print(long_to_bytes(x))
Another way to factor it by @Kuruwa:
Since
Since
Top Secret
- Category: Crypro
- Score: 325/500
- Solves: 9/428
Description
In year 2087, the TSJ corporation invented a new patented stream cipher to protect their communication. One day, another member stole an important file from the CEO's computer, but it turns out to be encrypted. Fortunately, the script used to encrypt the file were stolen too. You, as a member of Nantou Resistance, accept the challenge to decrypt it.
Overview
This is a weird stream cipher that has an internal state s
, and it will update its state using the forward
/fast_forward
function:1
2
3
4def forward(s: int, n: int, k: int) -> int:
for _ in range(n):
s = (s >> 1) ^ ((s & 1) * k)
return s
The k
is a known constant, and the n
is the key of the cipher. The initialize state of the cipher is fixed too. The objective is to decrypt a PNG encrypted by it.
Solution
First, it is necessary to understand the meaning of s = (s >> 1) ^ ((s & 1) * k)
. If you ever tried to read the implementation of AES, you may find that it is pretty similar to the xtime
operation. (An example in C)
xtime
operation means multiplying an
In this challenge, the order of bits are swapped, so the bit shifting direction are different. And the constant k
obvious represents a 128 degree polynomial...?
Actually, key = randbelow(2 ** 128)
is meant to confuse people. If you try to construct the polynomial by f'{k:0128b}1'
you will see it is not a prime polynomial, because its leftmost bit is 0
. The correct degree is 127, so you can construct the field in Sage and implements fast_forward
like this:1
2
3
4
5
6
7
8
9
10
11
12
13from sage.all import GF, var
def fast_forward(s, n, k):
x = var("x")
coefs = [int(x) for x in (f"{k:0127b}1")]
poly = sum(c * x ** i for i, c in enumerate(coefs))
F = GF(2 ** 127, "a", modulus=poly)
a = F.gen()
s_coefs = [int(x) for x in f"{s:0127b}"]
ss = sum(c * a ** i for i, c in enumerate(s_coefs))
sn = ss * a ** n
return int("".join(map(str, sn.polynomial().list())).ljust(127, "0"), 2)
The next step is to observe that the first 16 bytes of PNG is known, not just 8 bytes, because of the IHDR chunk. Xor the first chunk of ciphertext and the first 16 bytes of PNG gives second state of the cipher. This can be written as:
So this is a discrete log problem in
The intended way is to use Fast Evaluation of Logarithms in Fields of Characteristic Two, which can solve discrete log in this size easily, and it is implemented in pari too.
In Sage, you can just use pari.fflog(e, g)
to find x
such that g^x == e
. In newer version of Sage (9.5 or above), e.log(g)
works too.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
30from sage.all import var, GF, pari
s = 0x6BF1B9BAE2CA5BC9C7EF4BCD5AADBC47
k = 0x5C2B76970103D4EEFCD4A2C681CC400D
x = var("x")
coefs = [int(x) for x in (f"{k:0127b}1")]
poly = sum(c * x ** i for i, c in enumerate(coefs))
F = GF(2 ** 127, "a", modulus=poly)
alpha = F.gen()
def int2el(r):
return sum(c * alpha ** i for i, c in enumerate(int(x) for x in f"{r:0127b}"))
with open("flag.png.enc", "rb") as f:
data = f.read()
pngheader = bytes.fromhex("89504E470D0A1A0A0000000d49484452")
ks = bytes(x ^ y for x, y in zip(data, pngheader))
A = int2el(s)
B = int2el(int.from_bytes(ks, "big"))
key = int(pari.fflog(B / A, alpha)) # https://trac.sagemath.org/ticket/32842
from challenge import Cipher
with open("flag.png", "wb") as f:
f.write(Cipher(key).decrypt(data))
By the way, @Utaha tells me that it is not necessary to compute the discrete log to solve this challenge. Because the key stream is just
Cipher Switching Service
- Category: Crypto
- Score: 416/500
- Solves: 4/428
Description
You can freely swap the encrypted flag between two cryptosystem, but you still don't know what is the flag.
Overview
The server prints one 1024 bits RSA public key and one 1024 bits ElGamal public key on connection, and gives an RSA encrypted randomly padded flag (padded length is 96 bytes). The length of the flag is 20.
Server supports two operations, allowing you to decrypt a RSA ciphertext and encrypt it using ElGamal, and vice versa.
Solution
Note: There is a much more simpler unintended solution idea from @Mystiz, scroll to the bottom to see
Using the homomorphic property of RSA, we can get any ciphertext of
I use
When it decrypts
Suppose
Since the oracle is not really robust, might need to use some heuristic to make it more stable.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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110from pwn import *
import ast
from Crypto.Util.number import *
from gmpy2 import powmod as pow
def to_elgamal(c):
io.sendlineafter(b"> ", b"1")
io.sendlineafter(b"c = ", str(c).encode())
return ast.literal_eval(io.recvlineS())
def to_rsa(c1, c2):
io.sendlineafter(b"> ", b"2")
io.sendlineafter(b"c1 = ", str(c1).encode())
io.sendlineafter(b"c2 = ", str(c2).encode())
return int(io.recvlineS())
def legendre(a, p):
return pow(a, (p - 1) // 2, p)
io = remote("localhost", 8763)
io.recvuntil(b"RSA")
n, e = ast.literal_eval(io.recvlineS())
io.recvuntil(b"ElGamal")
p, g, y = ast.literal_eval(io.recvlineS())
io.recvuntil(b"len(flag) = ")
flagln = ast.literal_eval(io.recvlineS())
io.recvuntil(b"flagenc = ")
c = ast.literal_eval(io.recvlineS())
assert legendre(g, p) == 1
def legendre(a, p):
r = pow(a, (p - 1) // 2, p)
return r if r != p - 1 else -1
cnt = 0
def get_legendre(a):
# get legendre((a * m) % n, p)
global cnt
cnt += 1
ca = pow(a, e, n)
cc = (ca * c) % n
c1, c2 = to_elgamal(cc)
lc2 = legendre(c2, p)
return lc2
ln = 96
k_lb = int.from_bytes(b"TSJ{" + b"\x00" * (ln - 4), "big")
k_ub = int.from_bytes(b"TSJ{" + b"\xff" * (ln - 4), "big")
a_lb = n // k_ub
a_ub = n // k_lb
expected = get_legendre(1)
def oracle(a, b):
# return True if a * k < n
# no guarantee
for i in range(a - b, a + b):
if get_legendre(i) * legendre(i, p) != expected:
return False
return True
b = 3 # 3~4 is the best
t = 10
until = (a_ub - a_lb).bit_length() - (flagln - 4) * 8 - 5
def search(l, r, hist):
# dfs with some pruning
global b
if (r - l).bit_length() < until:
for aa in range(l, r):
f = long_to_bytes(n // aa)
if f.startswith(b"TSJ{"):
print(f)
break
print(f"{cnt = }")
exit()
if sum(hist[-t:]) >= t or sum(hist[-t:]) <= -t:
# because oracle may have false positive
# discard current branch if it is search on a single direction
print("bad", f"{t = }")
b = min(b + 1, 10) # increase bruteforcing window
return t # rewind t recursive call
print((r - l).bit_length(), b)
m = (r + l) // 2
while True:
if oracle(m, b):
r = search(m, r, hist + [1])
if r is not None and r > 0:
return r - 1
else:
r = search(l, m, hist + [-1])
if r is not None and r > 0:
return r - 1
if r != 0:
break
search(a_lb, a_ub, [])
An unintended solution by @Mystiz is to find a
Signature
- Category: Crypto
- Score: 469/500
- Solves: 2/428
Description
Another boring crypto challenge about signatures.
Overview
This challenge signs 6 signatures using ECDSA on Secp256k1. The nonce
Solution
This challenge is based on jonasnick/ecdsaPredictableNonce.
Need to use two basic facts:
- For two n bits integer
, , where and is their n-th bit.
So
In Secp256k1,
But it forgot an important fact:
Details are in the solution script
After recovering Congrats! This is your flag:
in the plaintext, we can take the first block and xor it with the first block of ciphertext, they decrypt it with the key. This is how AES-CTR works.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
48from fastecdsa.curve import secp256k1 as CURVE
from Crypto.Cipher import AES
from hashlib import sha256
from operator import xor
import ast
with open("output.txt") as f:
sigs = []
for _ in range(6):
z, r, s = map(int, f.readline().strip().split())
sigs.append((z, r, s))
msgct = ast.literal_eval(f.readline())
def recover_d(sigs):
P = PolynomialRing(Zmod(CURVE.q), "d", 256)
ds = P.gens()
dd = sum([2 ** i * di for i, di in enumerate(ds)])
polys = []
for z, r, s in sigs:
d_and_z = sum([2 ** i * ((z & (1 << i)) >> i) * di for i, di in enumerate(ds)])
# fact: (a xor b) = a + b - 2 * (a and b)
k = dd + z - 2 * d_and_z
polys.append((s * k) - (z + r * dd))
M, v = Sequence(polys).coefficient_matrix()
print(v.T)
M = M.T.dense_matrix()
a, b = M.dimensions()
B = block_matrix(
ZZ, [[matrix.identity(b) * CURVE.q, matrix.zero(b, a)], [M, matrix.identity(a)]]
)
B[:, :b] *= 2 ^ 64
print("LLL", B.dimensions())
for row in B.LLL():
if row[:b] == 0 and row[-1] == 1 and all(0 <= x <= 1 for x in row[b:-1]):
dbits = row[b:-1]
d = int("".join(map(str, dbits[::-1])), 2)
return d
d = recover_d(sigs)
print(f"{d = }")
key = sha256(str(d).encode()).digest()[:16]
nonce = AES.new(key, AES.MODE_ECB).decrypt(
bytes(map(xor, b"Congrats! This is your flag: "[:16], msgct[:16]))
)[:8]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(msgct))
RNG+++
- Category: Crypto
- Score: 469/500
- Solves: 2/428
This upgraded version of
RNG++
, so you might want to read it before reading this.
Description
I encrypted the flag and messages by xoring them with a random number generator again. But it should be harder to break this time.
Overview
Basically same as RNG++
, but
Solution
Since we only know some bits in each state
1
0011????0011????0011????0011????0011????...
It is easy to see
Using coefficient matrix of those polynomials (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
79
80from Crypto.Util.number import *
from operator import xor
with open("output.txt") as f:
lines = f.readlines()
M, A, C = [ZZ(x) for x in lines[0].strip().split()]
sz = round(M.log(2))
cts = [bytes_to_long(bytes.fromhex(line.strip())) for line in lines[1:]]
flagct = cts[0]
cts = cts[1:1+4]
n = len(cts)
mask1 = sum(
[
(1 << (7 + 8 * i))
+ (1 << (6 + 8 * i))
+ (1 << (5 + 8 * i))
+ (1 << (4 + 8 * i))
for i in range(sz // 8)
]
)
mask2 = sum([+(1 << (5 + 8 * i)) + (1 << (4 + 8 * i)) for i in range(sz // 8)])
ys = [xor((mask1 & s), mask2) for s in cts]
F = Zmod(M)
# t = F(C / (1 - A))
unames = ",".join(sum([[f"u_{i}_{j}" for j in range(sz // 8)] for i in range(n)], []))
P = PolynomialRing(F, unames)
U = matrix(n, sz // 8, P.gens())
rs = [ys[i] + sum([2 ^ (8 * j) * U[i, j] for j in range(sz // 8)]) for i in range(n)]
fs = [A * r + C - rr for r, rr in zip(rs, rs[1:])]
# rs = [r - t for r in rs] # substitution
# fs = [A ^ 1 * r - rr for r, rr in zip(rs, rs[1:])]
B, v = Sequence(fs).coefficient_matrix()
print(vector(v))
B = B.T.dense_matrix().change_ring(ZZ)
target = (-B[-1]).list()
B = B[:-1]
a, b = B.dimensions()
print(a, b)
I = matrix.identity(a)
B = block_matrix([[B, I], [M * matrix.identity(b), matrix.zero(b, a)]])
print(B.dimensions())
def Babai_CVP(mat, target):
# M = mat.LLL()
M = mat.BKZ(algorithm="NTL", prune=5)
G = M.gram_schmidt()[0]
diff = target
for _ in range(1):
for i in reversed(range(G.nrows())):
diff -= M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
return target - diff
cvp_target = vector(target + [8] * (n * sz // 8))
rr = Babai_CVP(B, cvp_target)
xx = B.solve_left(rr)
print("CVP")
print(rr)
print(xx)
print((rr - cvp_target).norm().n())
print()
found = xx[: n * (sz // 8)]
print(found)
if all(0 <= x < 16 for x in found):
print("good")
mat = matrix(n, sz // 8, found)
ss = [
ys[i] + sum([2 ^ (8 * j) * mat[i, j] for j in range(sz // 8)]) for i in range(n)
]
print(ss)
assert (A * ss[0] + C) % M == ss[1]
flag = long_to_bytes(xor(ZZ(F(ss[0] - C) / A), flagct)).decode()
print(f"TSJ{{{flag}}}")