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.
deffermat(x, mx): a = floor(sqrt(x)) b2 = a * a - x cnt = 0 whileTrue: 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
I encrypted the flag and messages by xoring them with a random number generator.
Overview
You got a simple LCG with , where are prime and is a power of . The flag are encrypted by xor it with initial state . Some random messages are generated by 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 bits unsigned bitvector, and write LCG and specify the constraints, and it will magically found the state, so you can get the flag too.
Another more mathematical unintended solution by @Kuruwa: Since is a power of , reducing it to works too. And just do some bruteforce searching over the digits to see if it holds.
The intended solution will be in the writeup of RNG+++.
babyRSA
Category: Crypto
Score: 276/500
Solves: 13/428
Description
is this rsa?
Overview
We have , where is 1024 bit prime and is 512 bit prime. Define an elliptic curve over , flag (with some random padding) are encoded as x coordinate of a point on curve. The ciphertext is another point , where .
Solution
By substituting the coorinates of back to the original curve, we have , where are known. If we change this equation to , we get .
Define another polynomial , it is easy to see . Since is small compared to , we use Coppersmith's method to solve for the root and factor .
Once you got , the remaining part should be easy. Change the curve to and and compute the order separately, and invert the scalar multiplication to get the flag.
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 , the vector will be in lattice spanned by the following basis .
Since is just 512 bits, is probably a short vector in it. Run LLL or Lagrange-Gauss algorithm could produce the vector .
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 4
defforward(s: int, n: int, k: int) -> int: for _ inrange(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 element by , and each element is represented by a polynomial of , modulo . In AES, the lowest bit represents , and the highest bit represents .
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 13
from sage.allimport GF, var
deffast_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 inenumerate(coefs)) F = GF(2 ** 127, "a", modulus=poly) a = F.gen() s_coefs = [int(x) for x inf"{s:0127b}"] ss = sum(c * a ** i for i, c inenumerate(s_coefs)) sn = ss * a ** n returnint("".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 . Unfortunately, is a mersenne prime, so you can't use Pohlig–Hellman to compute .
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 inenumerate(coefs)) F = GF(2 ** 127, "a", modulus=poly) alpha = F.gen()
defint2el(r): returnsum(c * alpha ** i for i, c inenumerate(int(x) for x inf"{r:0127b}"))
withopen("flag.png.enc", "rb") as f: data = f.read()
ks = bytes(x ^ y for x, y inzip(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
withopen("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 like a geometric progression. And can be simply computed by , so it is enough to decrypt the flag actually.
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 . ElGamal is encrypted as for some random number and public key .
I use to denote Legendre Symbol here because it is hard to type in Latex. Obviously, . Also, by how is generated, it is easy to see , so we have .
When it decrypts with RSA private, it actually gives , so it is actually.
Suppose , is just , so should hold. If , might not hold. From this, it is possible find such that with binary search, so the flag is approximately .
Since the oracle is not really robust, might need to use some heuristic to make it more stable.
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
deflegendre(a, p): r = pow(a, (p - 1) // 2, p) return r if r != p - 1else -1
cnt = 0
defget_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
deforacle(a, b): # return True if a * k < n # no guarantee for i inrange(a - b, a + b): if get_legendre(i) * legendre(i, p) != expected: returnFalse returnTrue
b = 3# 3~4 is the best t = 10 until = (a_ub - a_lb).bit_length() - (flagln - 4) * 8 - 5
defsearch(l, r, hist): # dfs with some pruning global b if (r - l).bit_length() < until: for aa inrange(l, r): f = long_to_bytes(n // aa) if f.startswith(b"TSJ{"): print(f) break print(f"{cnt = }") exit() ifsum(hist[-t:]) >= t orsum(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 whileTrue: if oracle(m, b): r = search(m, r, hist + [1]) if r isnotNoneand r > 0: return r - 1 else: r = search(l, m, hist + [-1]) if r isnotNoneand r > 0: return r - 1 if r != 0: break
search(a_lb, a_ub, [])
An unintended solution by @Mystiz is to find a such that is just slightly above , this means is . By using homomorphic property of ElGamal you can get the RSA ciphertext of , which is just . And you can just do to find the plaintext.
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 is generated by xoring hash and private key . The flag is encrypted with AES-CTR, key are derived from ECDSA private and IV are unknown.
For two n bits integer , , where and is their n-th bit.
So can be written as . And it can be substituted back to to get a bunch of equations that have as their roots.
In Secp256k1, is a 256 bit number. So in the jonasnick/ecdsaPredictableNonce, you can collect 256 signatures and solve with linear algebra.
But it forgot an important fact: . This problem can be transform into finding a short vector in lattice, and use LLL to solve it.
Details are in the solution script
After recovering , we still need IV to decrypt the flag with AES-CTR. Notice there is a prefix 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.
from fastecdsa.curve import secp256k1 as CURVE from Crypto.Cipher import AES from hashlib import sha256 from operator import xor import ast
withopen("output.txt") as f: sigs = [] for _ inrange(6): z, r, s = map(int, f.readline().strip().split()) sigs.append((z, r, s)) msgct = ast.literal_eval(f.readline())
defrecover_d(sigs): P = PolynomialRing(Zmod(CURVE.q), "d", 256) ds = P.gens() dd = sum([2 ** i * di for i, di inenumerate(ds)]) polys = [] for z, r, s in sigs: d_and_z = sum([2 ** i * ((z & (1 << i)) >> i) * di for i, di inenumerate(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] == 0and row[-1] == 1andall(0 <= x <= 1for 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 is a prime this time.
Solution
Since we only know some bits in each state , it can be written as:
is a known part of each state and are unknowns.This is equivalent to this binary representation:
1
0011????0011????0011????0011????0011????...
It is easy to see , and trying to substitute with will find out that it is just some linear combination of . And the fact tells us we need to find something small, so it isn't too hard to think about lattice.
Using coefficient matrix of those polynomials (), we can transform this problem into finding closest vector of a lattice. And using Babai Nearest Plane algorithm on a BKZ reduced basis (LLL reduced basis doesn't work well here) allows you to find the correct .
from Crypto.Util.number import * from operator import xor
withopen("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:]]
F = Zmod(M) # t = F(C / (1 - A)) unames = ",".join(sum([[f"u_{i}_{j}"for j inrange(sz // 8)] for i inrange(n)], [])) P = PolynomialRing(F, unames) U = matrix(n, sz // 8, P.gens()) rs = [ys[i] + sum([2 ^ (8 * j) * U[i, j] for j inrange(sz // 8)]) for i inrange(n)] fs = [A * r + C - rr for r, rr inzip(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())
defBabai_CVP(mat, target): # M = mat.LLL() M = mat.BKZ(algorithm="NTL", prune=5) G = M.gram_schmidt()[0] diff = target for _ inrange(1): for i inreversed(range(G.nrows())): diff -= M[i] * ((diff * G[i]) / (G[i] * G[i])).round() return target - diff
ifall(0 <= x < 16for x in found): print("good") mat = matrix(n, sz // 8, found) ss = [ ys[i] + sum([2 ^ (8 * j) * mat[i, j] for j inrange(sz // 8)]) for i inrange(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}}}")