Disclaimer: cryptography is not my strongest CTF category. I’ll do my best to avoid maths errors, but please DM me on Discord if you find any so I can correct them!
Silent Hint
We are given the source code that was used to encrypt a secret communication, and a single encrypted message alongside a “hint” related to the encryption key.
import string
from my_secrets import secret_key, secret_message
p = 71
N = 11
ALPHABET = string.ascii_lowercase + string.ascii_uppercase + string.digits + " {}_,.!?'"
HINT_STR = 'ROOT ME'
assert len(ALPHABET) == p
assert all(c in ALPHABET for c in secret_message)
F = GF(p)
MS = MatrixSpace(F, N, N)
VS = VectorSpace(F, N)
assert secret_key in MS
P.<z> = PolynomialRing(F)
HINT_POLY = P([ALPHABET.index(c) for c in HINT_STR])
def gen_hint(key):
return HINT_POLY(key)
def encrypt(plain, key):
assert len(plain) % N == 0
assert all(c in ALPHABET for c in plain)
cipher = ""
for i in range(0, len(plain), N):
x = VS([F(ALPHABET.index(c)) for c in plain[i:i+N]])
y = key * x
cipher += "".join(ALPHABET[c] for c in y)
return cipher
# Encrypted message
ciphertext = encrypt(secret_message, secret_key)
print(f'Encrypted message: |{ciphertext}|')
# Hints
hint = gen_hint(secret_key)
hint_text = ''.join(''.join(ALPHABET[c] for c in row) for row in hint)
assert sorted([t[1] for t in secret_key.eigenvectors_left()]) == sorted([t[1] for t in hint.eigenvectors_left()])
assert 'RM{' in secret_message
print(f'Hint: |{hint_text}|')
"""
Encrypted message: |82Ol_LHBNsjbdXHN_JEYy_xeiASgg!OCf28CV U'Rnkt89KFOpLYt4T4{7Qtxf64JXwQtJCo8OEI4}GHWkVs7Li'm{DV'8,JBWtq4d41rs.fORDhkiGIY!3EX|
Hint: |h7Eh}6KGRF.g'rsW Yeo_KXmE9prYHzIQGU.MJkkKo9ZgX'bd}QbJ7FM5W1TYFoIIo,Q?{{5{g,ZmptJXiH!Yz9K953ig pfIz, vJLg Vpopm'I4c5z{f,h7|
"""
This is a linear algebra challenge. The encryption function is a simple Hill cipher and the secret key is an 11x11 square matrix, hopefully invertible. The original Hill cipher uses 26 letters but here the alphabet is longer so we are working modulo 71 instead (which is a prime number).
This is how we can decrypt the message, assuming we know the encryption matrix and that it is invertible.
# Decrypt Hill cipher with the key
def decrypt(cipher, key):
inv_key = key.inverse()
plain = ""
for i in range(0, len(cipher), N):
x = VS([F(ALPHABET.index(c)) for c in cipher[i:i+N]])
y = inv_key * x
plain += "".join(ALPHABET[c] for c in y)
return plain
The challenge description hints that we should not try a known-plaintext attack, the usual critical weakness of the Hill cipher. This is because the matrix size and alphabet length are too big, we would need to guess too many characters of the original message (the secret message was also designed to try to avoid this from being possible).
Instead we are given a “hint”. Let $M \in \text{GL}_{11}(\mathbb{F}_{71})$ be the secret key matrix and $I$ the identity matrix. We are given another matrix $H$, a polynomial in $M$ equal to $H=30M^6 + 38M^5 + 62M^4 + 45M^3 + 40M^2 + 40M + 43I$. That polynomial is nothing special, it is derived from the string “ROOTME”. It is not straightforward to find arbitrary matrices roots of such a polynomial.
There is also another hint in the source code.
sorted([t[1] for t in secret_key.eigenvectors_left()]) == sorted([t[1] for t in hint.eigenvectors_left()])
"""
sage: M.eigenvectors_left?
Docstring:
Compute the left eigenvectors of a matrix.
OUTPUT:
For each distinct eigenvalue, returns a list of the form (e,V,n)
where e is the eigenvalue, V is a list of eigenvectors forming a
basis for the corresponding left eigenspace, and n is the algebraic
multiplicity of the eigenvalue.
"""
It states that the eigenspaces of the key matrix and the hint matrix are the same, but not necessarily for the same eigenvalues. Note that even if $H$ is a polynomial in $M$, this is not always the case. For example over the reals, $M_1=\begin{pmatrix}0 & -1\\1 & 0\end{pmatrix}$ (rotation by 90°) has no eigenspace but $I=(M_1)^4=\begin{pmatrix}1&0\\0&1\end{pmatrix}$ has the entire 2D space as an eigenspace for eigenvalue 1.
Then let’s investigate the eigenspaces of the hint matrix.
sage: hint.eigenvectors_left()
[(63, [(1, 30, 46, 27, 20, 41, 13, 13, 59, 6, 4)], 1),
(52, [(1, 46, 4, 56, 59, 61, 36, 29, 25, 59, 34)], 1),
(50, [(1, 48, 59, 7, 41, 22, 47, 27, 63, 21, 30)], 1),
(48, [(1, 40, 6, 9, 41, 21, 50, 40, 64, 68, 0)], 1),
(46, [(1, 68, 36, 38, 30, 12, 41, 52, 69, 47, 39)], 1),
(42, [(1, 53, 32, 41, 57, 37, 7, 46, 67, 39, 1)], 1),
(39, [(1, 39, 22, 29, 44, 39, 64, 58, 61, 9, 50)], 1),
(33, [(1, 11, 53, 15, 55, 16, 28, 3, 32, 14, 35)], 1),
(21, [(1, 34, 51, 49, 40, 0, 31, 1, 11, 34, 36)], 1),
(14, [(1, 64, 14, 18, 70, 53, 67, 10, 12, 38, 18)], 1),
(11, [(1, 22, 58, 5, 12, 13, 6, 2, 64, 55, 5)], 1)]
Very interesting, the hint matrix has 11 distinct eigenspaces of dimension 1 and that is also true for the key matrix. This means that both matrices are diagonalizable. But we actually have something stronger here. The eigenspaces of both matrices are the same and therefore the matrices are actually simultaneously diagonalizable.
This means that there exists $P \in \text{GL}_{11}(\mathbb{F}_{71})$ such that $M=PD_MP^{-1}$ and $H=PD_HP^{-1}$ where both $D_M$ and $D_H$ are diagonal matrices with the respective eigenvalues of $M$ and $H$ on their diagonal.
Finally, it is easy to show that $\text{poly}(M)=\text{poly}(PD_MP^{-1})=P\text{poly}(D_M)P^{-1}$ for any polynomial. Let $p$ be the hint polynomial and apply that formula with $p$. We find that $PD_HP^{-1}=H=p(M)=p(PD_MP^{-1})=Pp(D_M)P^{-1}$. Multiplying on the left by $P^{-1}$ and on the right by $P$, we get that $D_H=p(D_M)$.
Since $D_M$ is diagonal, $D_H=p(D_M)$ is equal to the diagonal matrix with $p$ applied to each diagonal entry of $D_M$ independently. To find the original $D_M$, we can search for the possible roots of that polynomial for each diagonal entry of $D_H$ (in $\mathbb{F}_{71}$). We iterate over the possible roots to search for candidate key matrices, until we find the correct matrix $M$ that decrypts the message containing the flag.
import itertools
import math
import string
data = """
Encrypted message: |82Ol_LHBNsjbdXHN_JEYy_xeiASgg!OCf28CV U'Rnkt89KFOpLYt4T4{7Qtxf64JXwQtJCo8OEI4}GHWkVs7Li'm{DV'8,JBWtq4d41rs.fORDhkiGIY!3EX|
Hint: |h7Eh}6KGRF.g'rsW Yeo_KXmE9prYHzIQGU.MJkkKo9ZgX'bd}QbJ7FM5W1TYFoIIo,Q?{{5{g,ZmptJXiH!Yz9K953ig pfIz, vJLg Vpopm'I4c5z{f,h7|
"""
ciphertext = data.split("|")[1]
hint_text = data.split("|")[3]
p = 71
N = 11
ALPHABET = string.ascii_lowercase + string.ascii_uppercase + string.digits + " {}_,.!?'"
HINT_STR = 'ROOT ME'
assert len(ALPHABET) == p
F = GF(p)
MS = MatrixSpace(F, N, N)
P.<z> = PolynomialRing(F)
VS = VectorSpace(F, N)
HINT_POLY = P([ALPHABET.index(c) for c in HINT_STR])
# Decrypt Hill cipher with the key
def decrypt(cipher, key):
inv_key = key.inverse()
plain = ""
for i in range(0, len(cipher), N):
x = VS([F(ALPHABET.index(c)) for c in cipher[i:i+N]])
y = inv_key * x
plain += "".join(ALPHABET[c] for c in y)
return plain
# We start by calculating the diagonalization of the hint matrix
hint = MS([ALPHABET.index(hint_text[N*i+j:N*i+j+1]) for j in range(N)] for i in range(N))
hintD, P = hint.diagonalization()
# Now each eigenvalue D[i][i] is a root of the polynomial (HINT_POLY - hintD[i][i])
candidates = []
for i in range(N):
candidates.append([root for (root, mult) in (HINT_POLY - hintD[i][i]).roots() if root != 0])
print("Candidates for each eigenvalue:", candidates)
print("Potential key matrices:", math.prod(len(roots) for roots in candidates))
# Try all possible combinations of eigenvalues until we find the flag
for it in itertools.product(*candidates):
D = MS([[it[i] if i == j else 0 for i in range(N)] for j in range(N)])
# Recover a possible original key matrix from the possible diagonal matrix
M = P * D * P.inverse()
assert HINT_POLY(M) == hint
# Try to decrypt ciphertext with that key
plain = decrypt(ciphertext, M)
if 'RM{' in plain:
print("Possible plaintext:", plain)
"""
Candidates for each eigenvalue: [[29], [70, 48, 19], [63], [60, 43], [52, 46], [36, 22], [69], [42, 34], [62, 3], [55, 23, 2, 1], [54, 13, 5]]
Potential key matrices: 1152
Possible plaintext: Pl3aS3_k3eP Wr1t!n5_L!ke TH4t t0 4v0!d_Kwn0WN t3xT_4TT4cK5!!N3xT_R!Tu4l_1nC4Nt4T!0n !S_RM{4Ll_H4Il_tH3_dIAg0nal1z4ti0N}
"""
The flag is RM{4Ll_H4Il_tH3_dIAg0nal1z4ti0N}.
Silenter Hint
Congratulations to zblxst for being the only person to solve this challenge during the CTF!
This is a harder version of the previous challenge. Please read the explanations above if needed. The source code for the challenge is almost the exact same, except for a single line (isn’t that beautiful?).
< assert sorted([t[1] for t in secret_key.eigenvectors_left()]) == sorted([t[1] for t in hint.eigenvectors_left()])
---
> assert [(f[0].degree(), f[1]) for f in factor(secret_key.minimal_polynomial())] == [(1, 1), (1, 2), (2, 1), (3, 1), (3, 1)]
If we try to apply the assertion to the hint matrix instead of the secret key matrix, we notice that it is also true.
sage: assert [(f[0].degree(), f[1]) for f in factor(hint.minimal_polynomial())]
sage: factor(hint.minimal_polynomial())
(x + 55) * (x + 25)^2 * (x^2 + 8*x + 19) * (x^3 + 23*x^2 + 52*x + 31) * (x^3 + 54*x^2 + 36*x + 30)
This time the matrices are not diagonalizable. Instead we are given information about the degrees of the polynomial factors of the minimal polynomial of $M$. The minimal polynomial of $M$, denoted $m_M$, is the unique monic polynomial with coefficients in $\mathbb{F}_{71}$ such that $m_M(M)=0$. Plus, the eigenvalues of $M$ are exactly the roots of $m_M$. However, notice that the minimal polynomial does not factor completely into linear factors here!
The hint matrix is not diagonalizable, but we can try to calculate its Jordan normal form instead. It is some kind of generalization using an upper-triangular matrix $J$ instead of a diagonal matrix $D$, and a basis of generalized eigenvectors instead of regular eigenvectors.
sage: hint.jordan_form()
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
Cell In[6], line 1
----> 1 hint.jordan_form()
File /usr/lib/python3.13/site-packages/sage/matrix/matrix2.pyx:11675, in sage.matrix.matrix2.Matrix.jordan_form (build/cythonized/sage/matrix/matrix2.c:95772)()
11673 evals = A.charpoly().roots()
11674 if sum(mult for (_, mult) in evals) < n:
> 11675 raise RuntimeError("Some eigenvalue does not exist in %s." % (A.base_ring()))
11676
11677 # Compute the block information. Here, ``blocks`` is a list of pairs,
RuntimeError: Some eigenvalue does not exist in Finite Field of size 71.
Unfortunately, this is not immediately possible and we get an error. The issue is that the minimal polynomial does not split completely into linear factors in $\mathbb{F}_{71}$. Some eigenvalues simply do not exist in that field.
This is the same problem you can face when working over $\mathbb{R}$. Since it is not an algebraically closed field, some polynomial roots / eigenvalues are not in $\mathbb{R}$. But we can always solve this issue by working over $\mathbb{C}$ instead, which is an algebraic closed extension of $\mathbb{R}$ that contains all the missing roots (for example, $i$).
It turns out we can do the same here and find an extension of $\mathbb{F}_{71}$ where the minimal polynomial splits completely. Galois theory tells us that any degree 2 polynomial with coefficients in $\text{GF}(71)$ will factor completely into linear factors if we work in the galois field $\text{GF}(71^2)$. Similarly, $\text{GF}(71^3)$ is the splitting field of any irreducible polynomial of degree 3 with coefficients in $\text{GF}(71)$.
Another result of Galois theory is that $\text{GF}(p^n)$ “contains” all the fields $\text{GF}(p^k)$ where $k$ divides $n$. Therefore, we will now work in $\text{GF}(71^6)$, which contains the fields $\mathbb{F}_{71}$, $\text{GF}(71^2)$ and $\text{GF}(71^3)$. In that field the minimal polynomial of $M$ and $H$ split completely into linear factors and we can successfully compute the Jordan normal form.
sage: F2 = GF(p ** 6)
sage: factor(hint.change_ring(F2).minimal_polynomial())
(x + 55) * (x + 44*z6^5 + 18*z6^4 + 11*z6^3 + 54*z6 + 10) * (x + 4*z6^5 + 34*z6^4 + 28*z6^3 + 49*z6^2 + 62*z6 + 10) * (x + 18*z6^5 + 10*z6^4 + 15*z6^3 + 25*z6^2 + 15*z6 + 20) * (x + 27*z6^5 + 59*z6^4 + 8*z6^3 + 52*z6^2 + 18*z6 + 36) * (x + 34*z6^5 + 20*z6^4 + 45*z6^3 + 70*z6^2 + 18*z6 + 38) * (x + 64*z6^5 + 33*z6^4 + 15*z6^3 + z6^2 + 70*z6 + 46) * (x + 67*z6^5 + 37*z6^4 + 43*z6^3 + 22*z6^2 + 9*z6 + 69) * (x + 26*z6^5 + 2*z6^4 + 48*z6^3 + 65*z6^2 + 38*z6 + 69) * (x + 25)^2
sage: hint.change_ring(F2).eigenvalues()
[16,
27*z6^5 + 53*z6^4 + 60*z6^3 + 17*z6 + 61,
67*z6^5 + 37*z6^4 + 43*z6^3 + 22*z6^2 + 9*z6 + 61,
53*z6^5 + 61*z6^4 + 56*z6^3 + 46*z6^2 + 56*z6 + 51,
44*z6^5 + 12*z6^4 + 63*z6^3 + 19*z6^2 + 53*z6 + 35,
37*z6^5 + 51*z6^4 + 26*z6^3 + z6^2 + 53*z6 + 33,
7*z6^5 + 38*z6^4 + 56*z6^3 + 70*z6^2 + z6 + 25,
4*z6^5 + 34*z6^4 + 28*z6^3 + 49*z6^2 + 62*z6 + 2,
45*z6^5 + 69*z6^4 + 23*z6^3 + 6*z6^2 + 33*z6 + 2,
46,
46]
sage: hint.change_ring(F2).jordan_form()
# No error!
Good! This is what $J_H$, the Jordan form matrix of $H$ looks like.
a 0 0 0 0 0 0 0 0 0 0
0 b 0 0 0 0 0 0 0 0 0
0 0 c 0 0 0 0 0 0 0 0
0 0 0 d 0 0 0 0 0 0 0
0 0 0 0 e 0 0 0 0 0 0
0 0 0 0 0 f 0 0 0 0 0
0 0 0 0 0 0 g 0 0 0 0
0 0 0 0 0 0 0 h 0 0 0
0 0 0 0 0 0 0 0 i 0 0
0 0 0 0 0 0 0 0 0 46 1
0 0 0 0 0 0 0 0 0 0 46
Almost diagonal, so close to greatness… There is a 1 in the bottom right corner in case you missed it.
The eigenvalues a to i are distinct with multiplicity 1. Based on the minimal polynomials of $M$ and $H$ having the same form, with overwhelming probability (experimental evidence, I can’t prove it), the eigenspaces for these entries are the same for $M$ and $H$ and we can basically do the same as in the previous challenge: find nine 1-dimensional subspaces of eigenvectors and map these eigenvalues of $H$ with eigenvalues of $M$ by finding polynomial roots in $\mathbb{F}_{71}$.
Now we only have to deal with the last 2-dimensional subspace. We run into the second issue. The value 46 is an eigenvalue of $H$ with algebraic multiplicity 2 (it is a double root of the characteristic polynomial), but with geometric multiplicity only 1 (the eigenspace associated with that eigenvalue has dimension 1). This is also visible in the minimal polynomial: the factor (x + 25)^2 is squared. Informally, applying $H-46I$ once is not enough to “vanish” a 2-dimensional space, it must be applied twice.
Let’s focus on that remaining 2D space and work with 2x2 matrices. Again, the eigenvalue 46 must map to a corresponding double multiplicity eigenvalue of $M$. Let $P_H$ such that $H=P_HJ_HP_H^{-1}$ is the Jordan normal form of $H$. There is no reason for the matrix $P_H$ to be equal to the corresponding matrix $P_M$ of the Jordan normal form of $M$.
However, we can write $M=P_HT_MP_H^{-1}$ where $T_M$ is upper triangular with the corresponding double multiplicity eigenvalue of $M$ on the diagonal. The top right value of $T_M$ will not necessarily be 1, but we can find the possible candidates using the formula $\text{poly}(P_HT_MP_H^{-1})=P_H\text{poly}(T_M)P_H^{-1}$ and $\begin{pmatrix}f & x \\ 0 & f\end{pmatrix}^n=\begin{pmatrix}f^n & nxf^{n-1}\\0 & f^n\end{pmatrix}$.
Like in the previous challenge, we iterate over all possible eigenvalues of $M$ (but this time we are working in $\text{GF}(71^6)$) and possible values in the upper right corner of the remaining 2x2 matrix, until we find the correct key matrix and decrypt the message.
import itertools
import math
import string
data = """
Encrypted message: |MYXOXLI_QqVxMm0,2Fm8FHcqANQ7DV?zmyv!eEN8gD!ep.a94TGTtrI5In7,Usga3fj,}zSWf,2xjPgQ.ihFbIu7K_.lNqk2ON {mEleWcu,SEK40cygXMazK|
Hint: |bI?'sLmU8po4A13o nHbVx6K!ZOc7bb2DPrDea85Do.n{e'Tom5yuK4F,7_6!2Ha_Vo_5GJHNgY0!SxKh11PjuifbrQ}ti6A7d_3q8LgzmrZyfcrJP,F.TgQ,|
"""
ciphertext = data.split("|")[1]
hint_text = data.split("|")[3]
p = 71
N = 11
ALPHABET = string.ascii_lowercase + string.ascii_uppercase + string.digits + " {}_,.!?'"
HINT_STR = 'ROOT ME'
assert len(ALPHABET) == p
F = GF(p)
MS = MatrixSpace(F, N, N)
P.<z> = PolynomialRing(F)
VS = VectorSpace(F, N)
HINT_POLY = P([ALPHABET.index(c) for c in HINT_STR])
# Decrypt Hill cipher with the key
def decrypt(cipher, key):
inv_key = key.inverse()
plain = ""
for i in range(0, len(cipher), N):
x = VS([F(ALPHABET.index(c)) for c in cipher[i:i+N]])
y = inv_key * x
plain += "".join(ALPHABET[c] for c in y)
return plain
hint = MS([ALPHABET.index(hint_text[N*i+j:N*i+j+1]) for j in range(N)] for i in range(N))
# Since we are working with irreducible polynomials of degree 2 and 3, we work in the splitting field GF(71 ** (2 * 3)) where they factor completely into linear factors
F2 = GF(p ** 6)
MS2 = MatrixSpace(F2, N, N)
P2.<z2> = PolynomialRing(F2)
# The Jordan form of the hint matrix looks like this, with b,c,d,e,f,g,h,i in GF(71 ** 6) and a, j in GF(71)
# a 0 0 0 0 0 0 0 0 0 0
# 0 b 0 0 0 0 0 0 0 0 0
# 0 0 c 0 0 0 0 0 0 0 0
# 0 0 0 d 0 0 0 0 0 0 0
# 0 0 0 0 e 0 0 0 0 0 0
# 0 0 0 0 0 f 0 0 0 0 0
# 0 0 0 0 0 0 g 0 0 0 0
# 0 0 0 0 0 0 0 h 0 0 0
# 0 0 0 0 0 0 0 0 i 0 0
# 0 0 0 0 0 0 0 0 0 j 1
# 0 0 0 0 0 0 0 0 0 0 j
hintJ, P = hint.change_ring(F2).jordan_form(transformation=True)
P_inv = P.inverse()
# Like in the previous challenge, we find candidate eigenvalues by finding roots of HINT_POLY
# a,b,c,d,e,f,g,h,i have single multiplicities and f has multiplicity 2
candidates_singles = []
for i in range(N - 2):
candidates_singles.append([root for (root, mult) in (P2(HINT_POLY) - hintJ[i][i]).roots() if root != 0])
candidates_double = [root for (root, mult) in (P2(HINT_POLY) - hintJ[N-1][N-1]).roots() if root in F and root != 0]
print("Candidates for each single eigenvalue:", candidates_singles)
print("Candidates for the double multiplicity eigenvalue:", candidates_double)
# Try all possible combinations of eigenvalues until we find the flag
for f in candidates_double:
# Find the possible values in the upper right corner of the 2x2 matrix
POLY_2_2 = 0
for power, coeff in enumerate(HINT_POLY):
POLY_2_2 += coeff * power * f ** (power - 1) * z
possible_corner_values = [r[0] for r in (POLY_2_2 - F(1)).roots()]
for it in itertools.product(*candidates_singles):
for corner in possible_corner_values:
# Construct the possible original Jordan-like matrix, relatively to the base of eigenvectors spanned by P
J = []
for i in range(N - 2):
J.append([it[i] if i == j else 0 for j in range(N)])
J.append([0 for _ in range(N - 2)] + [f, corner])
J.append([0 for _ in range(N - 2)] + [0, f ])
J = MS2(J)
# Recover a possible original key matrix
M = P * J * P_inv
# If it has values outside of GF(71), it cannot be the original matrix
if M not in MS:
continue
M = MS(M)
assert HINT_POLY(M) == hint
# Try to decrypt ciphertext with that key
plain = decrypt(ciphertext, M)
if 'RM{' in plain:
print("Possible plaintext:", plain)
"""
Candidates for each single eigenvalue: [[25, 25*z6^5 + 18*z6^4 + 47*z6^3 + 48*z6^2 + 11*z6 + 61, ...]]
Candidates for the double multiplicity eigenvalue: [52, 46]
Possible plaintext: pA0diN9p4001ngPA0d!ngP40d1N9p4dDINgp4d0InGpa00InGPA0d!N9 xXx RM{ !! C4M1!L3 J0rD4n 4EV3r !! } xXx P4Dd!n9P400INGp4d0!N9
"""
The flag is RM{ !! C4M1!L3 J0rD4n 4EV3r !! }.
RSA Customer Service
This is the obligatory RSA challenge every CTF is required to have. Funnily, there was a very similar challenge released for TRX CTF 2025 one week after I finished writing this one. I think the solution is basically the same, but their challenge is also more cleverly implemented than mine, so check it out.
Anyway, we must recover a message encrypted with a broken implementation of RSA.
from Crypto.Util.number import bytes_to_long, long_to_bytes
import random
p, q = random.randint(1, 2**1024), random.randint(1, 2**1024)
N = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
def encrypt(m):
return pow(m, e, N)
def decrypt(c):
return pow(c, d, N)
m = bytes_to_long(b'RM{***************************}')
c = encrypt(m)
m = decrypt(c)
#assert b'RM{' in long_to_bytes(m) # WTF it's broken???
# Please help me recover my flag, you can have my keys too
print(f'{N = }')
print(f'{e = }')
print(f'{d = }')
print(f'{m = }')
# N = 48921293858887224030390392915499421209361472785297107570441579369219582586327360718700341151162832516000059999564184947958429549705574583982047340592409498033915354838573257326849530254640417419267505599835640052751354608422307378800176289888903388607580829535040019436813995704505333996127590836033740152049429560823748755172792507946158682274980781253533243411730146177334104305396882628039828048922349815361451376053909896353349692731959793841675270794961914705303745586489740082643006900467330266563263755590109923790976777881980570847493731222268347492905811314483769040554335232470491163725032120337609719410
# e = 65537
# d = 8119335845447859007561473728457012138093363130532014572587897810381943021369344073383029597039811545791425494228598191539799475291019344034251322514360408778474713743063633061387343646790726158801480971198136271934578697160526685066596235792324979139793653704817588406766037982786891647098277393282252645568056720874646258109593558709726827522464258459128074923488699478438440745408598998343859680349278920276985086132560949935075314958445198298478905213117626488382975516675980717124449852846660733217119278525839717219642029098241126189067469946906175813469680767946653438691255329980390076466587760051694441617
# m = 47784205793711787008854526749795117517610448843342585383906841923807211914267962151355459011588114961361517783754862576804770521202945469898361539646579610322735540727254766867905421103432033411630435358582021234214935156999181083078019738703952272903959743491646793283553035934609461534229608138114436372840528711390930682691330686240861292319220592250117651000581945525115471154625649421288763319557130951702291806874163406300332807676997503370277224372039850635793324036797382508083979770550718335899036891147387319478066056290147078002537062736993406793664976511591658673455884778946375216880618062123812557743
The obvious flaw here is that $p$ and $q$ are supposed to be prime numbers in the RSA cryptosystem, but they are generated with random.randint instead. Consequently, the calculated $\phi$ and the private exponent $d$ are incorrect and decryption fails.
In order to recover the message, we are given the modulus $N = pq$, public exponent $e = 65537$, incorrect private exponent $d \equiv e^{-1} \pmod{\phi}$ and $m \equiv (m_{\text{flag}})^{ed} \pmod{N}$. The goal is to recover $m_\text{flag}$
Now we often say that the security of RSA is about factoring large integers. Well yes, but actually no. The security of the RSA cryptosystem relies at least on the following assumptions:
- Given a composite number $N=pq$ and the encrypted message $c \equiv m^e \pmod{N}$, it is hard to find $m$, the $e$-th root of $c$. This is the actual “RSA assumption” which guarantees the security of the cryptosystem (when it is correctly implemented with $e$ coprime with $\phi$, the root is unique).
- Given a composite number $N$, it is hard to find the number of invertible elements modulo $N$. In other words, it is hard to find $\phi$, the order of the unit group $\mathbb{Z}/n\mathbb{Z}^\times$.
- Given a composite number $N$, it is hard to find its unique prime factorization.
When we say that RSA relies on the hardness of factoring large integers (3), the implication is that if we are able to factor $N$ (3), then we can calculate the order $\phi$ (2) and use that to calculate the correct private exponent and recover the $e$-th root (1). The actual correct assumption is (1). To my knowledge, it is only believed that there is no easier way to find the $e$-th root (1) than to find $\phi$ (2) and factor $N$ (3). In other words, (1) and (3) are not proven to be strictly equivalent.
Back to the challenge, what do we really need to do to get the flag?
- If we could factor $N$ completely, then it would be easy to recover the original message by calculating the correct $\phi$, etc. But we don’t have to do that, and we won’t be able to.
- If we could find the possible $de$-th roots of $m \pmod{N}$, then one of them would be the original message. Maybe that’s easier, but it’s probably not.
- But it turns out that we don’t need to find the $de$-th roots modulo $N$. If we can find the roots modulo a smaller $M$, a divisor of $N$ that is larger than the original message, then that would be good enough to! Note that this would not be possible if we used padding.
The way to solve this challenge is to find enough prime factors of $N$ such that their product $M$ is larger than the original message, find the $de$-th roots modulo these prime factors and combine them using the Chinese Remainder Theorem to find $de$-th roots modulo $M$. Then one of them will be the flag.
Finding the $k$-th roots of an integer modulo a prime $p$ is not a “hard” problem. The Tonelli-Shanks algorithm can find square roots modulo a prime, and it can be generalized to find arbitrary $k$-th roots. Even more generally, there are fast algorithms to find the roots of polynomials modulo a prime like the Cantor-Zassenhaus algorithm. Of course this is included in softwares such as SageMath and we don’t need to implement any of that if we use SageMath .nth_root method.
# Example with 1024 bit prime p
p = random_prime(2**1024)
Fp = GF(p)
k = 65537
c = Fp(123)^k
# Finding all the k-th roots of c is instant!
roots = c.nth_root(k, all=True)
assert 123 in roots
Now we just need to find enough factors of $N$ for our attack to succeed. The hint release during the CTF points at the Lenstra elliptic-curve factorization. That’s the fastest method to find small prime factors (up to 50-60 digits). To find enough prime factors to solve this challenge, you can use:
- https://alpertron.com.ar/ECM.HTM - A browser application that implements ECM. It takes about 5 minutes to find enough factors.
- https://github.com/bbuhrow/yafu - YAFU, an optimized free software for prime factorization. Less than a minute here.
- FactorDB - A database for known prime factorization, where I added the factors you need prior to the CTF. I thought maybe it could help, but it would be the crypto CTF original sin to make a challenge rely on it. At least it is not required to solve the challenge!
Finally, here is the solve script that recovers the flag. The first solution is what I described, the second solution is the same but we let SageMath do the magic for us.
from sage.all import *
import itertools
from Crypto.Util.number import long_to_bytes
N = 48921293858887224030390392915499421209361472785297107570441579369219582586327360718700341151162832516000059999564184947958429549705574583982047340592409498033915354838573257326849530254640417419267505599835640052751354608422307378800176289888903388607580829535040019436813995704505333996127590836033740152049429560823748755172792507946158682274980781253533243411730146177334104305396882628039828048922349815361451376053909896353349692731959793841675270794961914705303745586489740082643006900467330266563263755590109923790976777881980570847493731222268347492905811314483769040554335232470491163725032120337609719410
e = 65537
d = 8119335845447859007561473728457012138093363130532014572587897810381943021369344073383029597039811545791425494228598191539799475291019344034251322514360408778474713743063633061387343646790726158801480971198136271934578697160526685066596235792324979139793653704817588406766037982786891647098277393282252645568056720874646258109593558709726827522464258459128074923488699478438440745408598998343859680349278920276985086132560949935075314958445198298478905213117626488382975516675980717124449852846660733217119278525839717219642029098241126189067469946906175813469680767946653438691255329980390076466587760051694441617
m = 47784205793711787008854526749795117517610448843342585383906841923807211914267962151355459011588114961361517783754862576804770521202945469898361539646579610322735540727254766867905421103432033411630435358582021234214935156999181083078019738703952272903959743491646793283553035934609461534229608138114436372840528711390930682691330686240861292319220592250117651000581945525115471154625649421288763319557130951702291806874163406300332807676997503370277224372039850635793324036797382508083979770550718335899036891147387319478066056290147078002537062736993406793664976511591658673455884778946375216880618062123812557743
factors = [2, 5, 163, 8263, 11617, 11909899, 1515847349, 12600377473, 37984123211381, 7775904744864652956285367]
assert all(N % f == 0 for f in factors)
# === Solution 1 ===
# Find all (de)-th roots modulo a few known prime factors of N
possible_remainders = []
for f in factors:
R = Zmod(f)
possible_remainders.append([int(r) for r in R(m).nth_root(d * e, all=True)])
# Combine the roots with CRT to find roots modulo the product of prime factors
# Original message is smaller than this moduli product, so we are able to recover it
for remainders in itertools.product(*possible_remainders):
m_recovered = long_to_bytes(crt(list(remainders), factors))
if b'RM{' in m_recovered:
print(m_recovered)
# === Solution 2 ===
# SageMath is smart enough to find all roots in Zmod(product(factors))
# Internally it will factor the product and use the CRT for us
R = Zmod(product(factors))
for root in R(m).nth_root(d * e, all=True):
m_recovered = long_to_bytes(int(root))
if b'RM{' in m_recovered:
print(m_recovered)
The flag is RM{prime_suspect_was_composite} (please laugh).
RMUTES
This one has the “memory corruption” tag on it… To stand against crypto enthusiasts adding crypto in our beloved reverse engineering challenges, I wrote a crypto challenge with some pwn in it! Do not worry, it is not that bad.
#include <fcntl.h>
#include <openssl/conf.h>
#include <openssl/evp.h>
#include <openssl/err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define FLAG_FILENAME "./flag.txt"
#define RANDOM_SOURCE "/dev/urandom"
#define MAX_PLAIN_LEN 4096
#define KEY_LEN 32
#define IV_LEN 16
#define CKS_POLY 0xEDB88320U
#define MIN(a,b) ((a) < (b) ? (a) : (b))
int randomfd;
unsigned char masterKey[KEY_LEN];
char* flag;
typedef struct {
unsigned int keyChecksum;
unsigned short plaintext_len;
unsigned char plaintext[MAX_PLAIN_LEN];
unsigned char key[KEY_LEN];
unsigned char iv[IV_LEN];
} encrypt_parameters_t;
/* Print cnt hexadecimal characters from address data */
void printHex2(void* data, size_t cnt, int newline) {
if (cnt == 0) {
return;
}
printf("0x");
for (size_t i = 0; i < cnt; i++) {
printf("%02hhx", *(((char*) data) + i));
}
if (newline) {
puts("");
}
}
void printHex(void* data, size_t cnt) { printHex2(data, cnt, 1); }
/* Generate a random IV_LEN bytes IV */
void getRandomIV(unsigned char iv[IV_LEN]) {
while (read(randomfd, iv, IV_LEN) != IV_LEN);
}
/* Return the checksum of data */
unsigned int computeChecksum(unsigned char* data, size_t data_len) {
size_t i, j;
unsigned int s = 0xFFFFFFFF;
for (i = 0; i < data_len; i++) {
s = s ^ data[i];
for (j = 0; j < 8; j++) {
if ((s & 1) == 1) {
s = s >> 1;
s ^= CKS_POLY;
} else {
s = s >> 1;
}
}
}
s = s ^ 0xFFFFFFFF;
return s;
}
/* Handle unexpected OpenSSL errors */
void handleErrors(void)
{
ERR_print_errors_fp(stderr);
exit(EXIT_FAILURE);
}
/* Encrypt data using enc_parameters and output the results in ciphertext */
int doEncrypt(encrypt_parameters_t *enc_parameters, unsigned char* ciphertext) {
EVP_CIPHER_CTX *ctx;
int len;
int ciphertext_len;
unsigned int checksum;
/* Verify key integrity */
checksum = computeChecksum(enc_parameters->key, KEY_LEN);
if (enc_parameters->keyChecksum != checksum) {
printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
printf("!!! KEY INTEGRITY CHECK FAILED !!!\n");
printf("!!! INVALID CHECKSUM: 0x%08x !!!\n", checksum);
printf("!!! ENCRYPTION ABORTED !!!\n");
printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
return 0;
}
/* https://wiki.openssl.org/index.php/EVP_Symmetric_Encryption_and_Decryption */
if (!(ctx = EVP_CIPHER_CTX_new()))
handleErrors();
if(1 != EVP_EncryptInit_ex(ctx, EVP_aes_256_cbc(), NULL, enc_parameters->key, enc_parameters->iv))
handleErrors();
if(1 != EVP_EncryptUpdate(ctx, ciphertext, &len, enc_parameters->plaintext, enc_parameters->plaintext_len))
handleErrors();
ciphertext_len = len;
if(1 != EVP_EncryptFinal_ex(ctx, ciphertext + len, &len))
handleErrors();
ciphertext_len += len;
EVP_CIPHER_CTX_free(ctx);
return ciphertext_len;
}
void init() {
FILE* flag_file;
setbuf(stdout, NULL);
setbuf(stderr, NULL);
/* Load flag */
size_t len = 0;
if ((flag_file = fopen(FLAG_FILENAME, "r")) == NULL) {
perror("Could not read the flag. This should not happen, please contact an organizer.\n");
exit(EXIT_FAILURE);
}
getline(&flag, &len, flag_file);
fclose(flag_file);
/* Open secure random source */
randomfd = open(RANDOM_SOURCE, O_RDONLY);
if (randomfd < 0) {
perror("Error opening " RANDOM_SOURCE);
exit(EXIT_FAILURE);
}
/* Generate random key */
while (read(randomfd, masterKey, KEY_LEN) != KEY_LEN);
}
void menu() {
printf("Please make your choice.\n");
printf("1) I want to encrypt some text for absolutely no reason.\n");
printf("2) Just give me the flag already, who cares about crypto.\n");
printf("3) This challenge sucks, let me leave.\n");
printf("> ");
fflush(stdout);
}
void choice1Encrypt() {
char buf[10];
unsigned char ciphertext[MAX_PLAIN_LEN+32];
int plain_len, cipher_len;
encrypt_parameters_t parameters;
/* Get encryption key / IV */
memcpy(parameters.key, masterKey, KEY_LEN);
parameters.keyChecksum = computeChecksum(parameters.key, KEY_LEN);
getRandomIV(parameters.iv);
/* Get plaintext length */
printf("Length of text to encrypt: ");
fflush(stdout);
fgets(buf, sizeof(buf), stdin);
parameters.plaintext_len = atoi(buf);
/* Get plaintext */
printf("Text to encrypt: ");
fflush(stdout);
plain_len = MIN(parameters.plaintext_len, MAX_PLAIN_LEN - 1); /* -1 for null byte */
fgets((char*)parameters.plaintext, plain_len + 1, stdin);
parameters.plaintext[parameters.plaintext_len] = '\0'; /* Null terminate text */
parameters.plaintext_len = strlen((char*)parameters.plaintext); /* Set true length of text */
/* Encrypt */
puts("");
cipher_len = doEncrypt(¶meters, ciphertext);
if (cipher_len > 0) {
printf("Your plaintext: ");
printHex(parameters.plaintext, parameters.plaintext_len);
printf("Your IV: ");
printHex(parameters.iv, IV_LEN);
printf("Your encrypted text: ");
printHex(ciphertext, cipher_len);
}
}
void choice2GetFlag() {
unsigned char ciphertext[MAX_PLAIN_LEN+32];
int cipher_len;
encrypt_parameters_t parameters;
/* Encrypt the flag */
memcpy(parameters.key, masterKey, KEY_LEN);
parameters.keyChecksum = computeChecksum(parameters.key, KEY_LEN);
getRandomIV(parameters.iv);
parameters.plaintext_len = strlen(flag);
memcpy(parameters.plaintext, flag, parameters.plaintext_len);
cipher_len = doEncrypt(¶meters, ciphertext);
/* Send the encrypted flag */
if (cipher_len > 0) {
puts("");
printf("Congratulations! Here is your flag: ");
printHex(ciphertext, cipher_len);
printf("But it is encrypted hahahaha... ");
printf("I guess you can have your IV too: ");
printHex(parameters.iv, IV_LEN);
}
exit(EXIT_SUCCESS);
}
void choice3Leave() {
printf("Wow, rude.\n");
exit(EXIT_FAILURE); // This means you failed the challenge
}
int main() {
char choice, c;
init();
printf("Welcome to RMUTES (Root Me Useless Text Encryption Service)\n");
while (1) {
menu();
while ((choice = getchar()) == '\n');
while ((c = getchar()) != '\n' && c != EOF);
switch (choice) {
case '1':
choice1Encrypt();
break;
case '2':
choice2GetFlag();
break;
case '3':
choice3Leave();
break;
default:
printf("Try making a better choice...\n");
break;
}
printf("\n");
}
}
The C code is quite verbose, but it’s a simple service with only two options.
$ nc localhost 1337
Welcome to RMUTES (Root Me Useless Text Encryption Service)
Please make your choice.
1) I want to encrypt some text for absolutely no reason.
2) Just give me the flag already, who cares about crypto.
3) This challenge sucks, let me leave.
> 1
Length of text to encrypt: 5
Text to encrypt: Hello
Your plaintext: 0x48656c6c6f
Your IV: 0x2d181d27d1c1d0b59f21be6503438304
Your encrypted text: 0x59130235c36723057f66485faf54f549
Please make your choice.
1) I want to encrypt some text for absolutely no reason.
2) Just give me the flag already, who cares about crypto.
3) This challenge sucks, let me leave.
> 2
Congratulations! Here is your flag: 0x9d0868d09c12dc0965b496fc7033e2fc
But it is encrypted hahahaha... I guess you can have your IV too: 0x8d5e6d05eb12388391782c8f2b946f3e
This service generates a secure random AES-256 key and uses the openssl library for all crypto tasks. We can pick the first option to encrypt arbitrary text with AES-256-CBC. If we pick the second choice, we get the encrypted flag with its corresponding IV and the program stops.
There is no common vulnerability such as IV reuse and we can only ask for encryption. But there is a very suspicious additional feature. Before encrypting anything, the service checks the integry of the AES key by calculating a checksum. If that checksum is incorrect, it is leaked through an error message.
int doEncrypt(encrypt_parameters_t *enc_parameters, unsigned char* ciphertext) {
EVP_CIPHER_CTX *ctx;
int len;
int ciphertext_len;
unsigned int checksum;
/* Verify key integrity */
checksum = computeChecksum(enc_parameters->key, KEY_LEN);
if (enc_parameters->keyChecksum != checksum) {
printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
printf("!!! KEY INTEGRITY CHECK FAILED !!!\n");
printf("!!! INVALID CHECKSUM: 0x%08x !!!\n", checksum);
printf("!!! ENCRYPTION ABORTED !!!\n");
printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
return 0;
}
[...]
}
Also note that the key is initialized to its correct value every time a new message is encrypted.
void choice1Encrypt() {
char buf[10];
unsigned char ciphertext[MAX_PLAIN_LEN+32];
int plain_len, cipher_len;
encrypt_parameters_t parameters;
/* Get encryption key / IV */
memcpy(parameters.key, masterKey, KEY_LEN);
parameters.keyChecksum = computeChecksum(parameters.key, KEY_LEN);
getRandomIV(parameters.iv);
/* Get plaintext length */
printf("Length of text to encrypt: ");
fflush(stdout);
fgets(buf, sizeof(buf), stdin);
parameters.plaintext_len = atoi(buf);
/* Get plaintext */
printf("Text to encrypt: ");
fflush(stdout);
plain_len = MIN(parameters.plaintext_len, MAX_PLAIN_LEN - 1); /* -1 for null byte */
fgets((char*)parameters.plaintext, plain_len + 1, stdin);
parameters.plaintext[parameters.plaintext_len] = '\0'; /* Null terminate text */
parameters.plaintext_len = strlen((char*)parameters.plaintext); /* Set true length of text */
/* Encrypt */
puts("");
cipher_len = doEncrypt(¶meters, ciphertext);
if (cipher_len > 0) {
printf("Your plaintext: ");
printHex(parameters.plaintext, parameters.plaintext_len);
printf("Your IV: ");
printHex(parameters.iv, IV_LEN);
printf("Your encrypted text: ");
printHex(ciphertext, cipher_len);
}
}
The memory corruption bug is in the choice1Encrypt function. The call to fgets is correct and our plaintext will never overflow outside of the plaintext buffer. However, the line parameters.plaintext[parameters.plaintext_len] = '\0'; will write a null byte out of bounds if the user-controlled parameters.plaintext_len value is larger than the plaintext buffer length.
$ nc localhost 1337
Welcome to RMUTES (Root Me Useless Text Encryption Service)
Please make your choice.
1) I want to encrypt some text for absolutely no reason.
2) Just give me the flag already, who cares about crypto.
3) This challenge sucks, let me leave.
> 1
Length of text to encrypt: 999999
Text to encrypt: oops
[CRASH!]
By carefully setting parameters.plaintext_len, we are able to write a null byte at any position in the AES key. For simplicity, we will assume that there is no null byte in the original AES key and that will always trigger the key integrity check. This will be the case about 88% of the time and we can just connect to a new instance otherwise.
$ nc localhost 1337
Welcome to RMUTES (Root Me Useless Text Encryption Service)
Please make your choice.
1) I want to encrypt some text for absolutely no reason.
2) Just give me the flag already, who cares about crypto.
3) This challenge sucks, let me leave.
> 1
Length of text to encrypt: 4096
Text to encrypt: oops
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!! KEY INTEGRITY CHECK FAILED !!!
!!! INVALID CHECKSUM: 0xb4b20f68 !!!
!!! ENCRYPTION ABORTED !!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
[...]
Now let’s investigate the checksum calculation.
#define CKS_POLY 0xEDB88320U
/* Return the checksum of data */
unsigned int computeChecksum(unsigned char* data, size_t data_len) {
size_t i, j;
unsigned int s = 0xFFFFFFFF;
for (i = 0; i < data_len; i++) {
s = s ^ data[i];
for (j = 0; j < 8; j++) {
if ((s & 1) == 1) {
s = s >> 1;
s ^= CKS_POLY;
} else {
s = s >> 1;
}
}
}
s = s ^ 0xFFFFFFFF;
return s;
}
A quick search for 0xEDB88320 clarifies that this is one of the most common CRC-32 implementations. How bad is it to leak the wrong CRC when the key is corrupted? Pretty bad actually. CRC-32 is linear in $\text{GF}(2)$. This is also true when calculating the CRC32 of n-byte inputs.
In this case we are working with 32-byte inputs. If $a_{32}$ is any 32 bytes, $b_{32}$ is any 32 bytes and $0_{32}$ is a chain of 32 null bytes, we have the following equality.
$$ \text{CRC32}(a_{32} \oplus b_{32}) = \text{CRC32}(a_{32}) \oplus \text{CRC32}(b_{32}) \oplus \text{CRC32}(0_{32}) $$
from pwn import xor
import zlib
import random
a = bytes([random.randint(0, 255) for _ in range(32)])
b = bytes([random.randint(0, 255) for _ in range(32)])
zero = bytes([0 for _ in range(32)])
assert zlib.crc32(xor(a, b)) == zlib.crc32(a) ^ zlib.crc32(b) ^ zlib.crc32(zero)
Using the previous vulnerability, we can leak 32 invalid CRC32 checksums. That is one checksum for each of the corrupted keys where the i-th byte was replaced with a null byte. Then we solve the linear system of equations (or bruteforce 2 bytes at a time because I’m lazy) to recover the original bytes of the key.
After we recover the key, we ask for the encrypted flag and decrypt it with AES-256-CBC.
import zlib
from pwn import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import bytes_to_long, long_to_bytes
KEY_LEN = 32
p = remote("localhost", 1337)
# Leak a list of wrong CRC by corrupting one different byte of the key each time
wrong_crcs = []
for i in range(32):
print(f"Leaking wrong CRC {i+1}/32")
p.recvuntil(b"> ")
p.sendline(b"1")
p.recvuntil(b"Length of text to encrypt: ")
p.sendline(str(4096 + i).encode())
p.recvuntil(b"Text to encrypt: ")
p.sendline(b"XXX")
invalid = p.recvuntil(b"INVALID CHECKSUM: ", timeout=1)
if not invalid:
print("Null byte in key, try again.")
exit(1)
crc = int(p.recvuntil(b" "), 16)
wrong_crcs.append(crc)
# Recover encryption key from CRCs of corrupted keys
print("Recovering encryption key")
recovered_key = b''
null_crc = zlib.crc32(b'\x00' * KEY_LEN)
for n in range(KEY_LEN - 1):
for key_i in range(256):
for key_j in range(256):
if wrong_crcs[n] ^ wrong_crcs[n + 1] == null_crc ^ zlib.crc32(b'\x00' * n + bytes((key_i,key_j)) + b'\x00' * (KEY_LEN - n - 2)):
if n == 0:
recovered_key += bytes((key_i,))
recovered_key += bytes((key_j,))
assert len(recovered_key) == KEY_LEN
print(f"Found key: {hex(bytes_to_long(recovered_key))}")
# Get encrypted flag
p.recvuntil(b"> ")
p.sendline(b"2")
p.recvuntil(b"flag: ")
encrypted_flag = long_to_bytes(int(p.recvline(), 16))
p.recvuntil(b"IV too: ")
encrypted_flag_iv = int.to_bytes(int(p.recvline(), 16), 16)
# Decrypt flag
flag = unpad(AES.new(recovered_key, AES.MODE_CBC, encrypted_flag_iv).decrypt(encrypted_flag), 16)
print("Flag:", flag.decode())
The flag is RM{The_CRC32_of_this_flag_is_0x608be48e}. Isn’t that a cool flag?
assert zlib.crc32(b'RM{The_CRC32_of_this_flag_is_0x608be48e}') == 0x608be48e
ECDHivemind (unintended)
Congratulations to Mister7F and $in for finding the unintended solution!
What could go wrong if I create a challenge 24 hours before the CTF starts, no one has time to test it and I use a lazy script to generate a curve faster?! This one was doomed to have an unintended solution but it’s a cool solution so that’s OK. Plus it can be prevented with a revenge version (see below) so we just get an extra challenge for free!
from sage.all import *
from random import SystemRandom
from itertools import combinations
proof.all(False)
random = SystemRandom()
p = 0x9099d209a20bfbb731c9a003158ba131c4a0352415365d8f014c2bfd4913c2aaa67b910b4540582c29c8f1e54b7c6df8584d473237cdda8256f0377edd8cdde5316b5e245d426cee05ee97b45d7ac8b1fa161d568aa51ada54bf56b8ab997cb315f5c06e29b79cde39e0cf50efb55eed72e2a001a7333e75d5f1ac3b247bec1e5b545c0cffa519586b02c5e30a77d86e896a0b863d65d82d339a9f9724fe1eb9a87a27d108fa64e088a3e81468cb4d51a8b51064e34c7969fe3da3001fcfd36c81f14135a0f8fd13037bd5da457f5e1683324655b20ad2dbee44401f0eedd273af5e9df2a266983b32c897a9451a2a8989cc049fc619c6348d693b7aa0422a41
K = GF(p)
a = K(0)
b = K(0x135fa0fd3ed8926a72df7d8bb9b51961f06d609672f14a6838c3a8e7512bbc6d7a6764d15eb57d3cbffe042863fdab9760364dae6952b12d8be958fae44f1270ef9a9febff6f6d3c8fd134786ee207e6f737d1066cf0d303408c4074036dc0ac67dccb83dd0cddb3081fbc59f2e24d53a8fe2433be4cefaad018a72969f7dafc59c92f9d33294205cb7072e45ff5d03486b838379223d8b74b0d7dcfc85f3dc6bc629f2d3de5b7b4626d948c9f0eabb2926386efce4c46a5a5ed1a0f488199896b707d1f62896e72fee7fca2f9447c05c62afc560a463a7f8fe8eefbd9620c3f34cf710afd1f32c5661d7aeafe9c92b1ec58b7deb62335208683cde99ed142f6)
E = EllipticCurve(K, (a, b))
G = E(0x3fef464bb8efc071f9c88f875d776d12908edbad377ce38899a706b0d433ddd614e03b6a7c542ef3d0fb1870e9085647600d3886a8ba28762be85b6d9d450ef737a00ae29f63d6ac10986a79d6889b4500ecca629222cea29ac6c11f5037904fc95d6afbe7c61c8e2dfff116c96f31f21a8889ca020dc142e6577f02b791c785e0297adf592daf8b67b1465c288e7a5217e037d4561750aa35a5294d30f30e83fee74405c27f57f66c8c0c6159cd9f003e0e920edf201b211cf5abe09a3a3a9c94b358d2549782b041139523eeacd17715b761ddfdaef3091745ca84eb6ac825da1740815ce78a0cdbb9b3e90ef705a796b41a35068f96465476d89c27ab26fe, 0x5e2d616ab0da861b8ff8b667dac308dcd833a5bbb2772d34bcbf5f6d441e605acb465369d2c4a1259ee33711b3ed06c891c72afe4a4932cf8017d525d4e9be6d3524abb61438d3960f14742a01eab183dbc511904266edc964b738ad34ffdbb8032beb6db85970f961df3b5170606d9c02197ca8efdfc8cb91085aebabd22006c143436d7bd5c0bf9d51ded26b8e113cf58c87bf8591b279ae0a8c94d1210dd50ba77037418bd5b055fafe9827014ced892e8ea5b446e181b42a0640cc8fb2c446c5deacde8e12c2656d8a13ef9d07e5fc57b135944d884ad2458e4675e61be1a99765d9579e0430a5786e65850c12d99a9869dcca98dd01991d10fa097b2c03)
G.set_order(0x9099d209a20bfbb731c9a003158ba131c4a0352415365d8f014c2bfd4913c2aaa67b910b4540582c29c8f1e54b7c6df8584d473237cdda8256f0377edd8cdde5316b5e245d426cee05ee97b45d7ac8b1fa161d568aa51ada54bf56b8ab997cb315f5c06e29b79cde39e0cf50efb55eed72e2a001a7333e75d5f1ac3b247bec1e5b545c0cffa519586b02c5e30a77d86e896a0b863d65d82d339a9f9724fe1eb9a87a27d108fa64e088a3e81468cb4d51a8b51064e34c7969fe3da3001fcfd36c81f14135a0f8fd13037bd5da457f5e1683324655b20ad2dbee44401f0eedd273af5e9df2a266983b32c897a9451a2a8989cc049fc619c6348d693b7aa0422a42)
class Interceptor:
def __init__(self):
self.comms = []
def intercept(self, comm):
self.comms.append(comm)
return comm
def dump(self):
for comm in self.comms:
print(comm)
INTERCEPTOR = Interceptor()
class ECDHivemind:
def __init__(self, curve, G, size=24):
self.curve = curve
self.G = G
self.size = size
self.p = self.curve.base_field().order()
self.xs = [random.randint(0, self.curve.order() - 1) for _ in range(self.size)]
self.combinations = list(combinations(range(self.size), 2))
self.knowledge = set()
def awake(self):
self.Xs = INTERCEPTOR.intercept([x * self.G for x in self.xs])
def synchronize(self):
self.Ss = {(a, b): self.xs[a] * self.Xs[b] for a in range(self.size) for b in range(self.size) if a != b}
def share(self, msg):
for b in msg:
n1, n2 = self.combinations[b]
S = INTERCEPTOR.intercept(self.Ss[(n1, n2)])
enc = (b * S).x() % self.p
self.learn((n1, n2, enc))
def learn(self, data):
self.knowledge.add(data)
flag = open('flag.txt', 'rb').read().strip()
hivemind = ECDHivemind(E, G)
hivemind.awake()
hivemind.synchronize()
hivemind.share(flag)
INTERCEPTOR.dump()
If we ignore the formidable lore of an extra-terrestrial collective consciousness life form, we are left with the following problem.
- An elliptic curve $E$ is defined over a prime field $\text{GF}(p)$ with a generator $G$.
Alice, Bob, …24 participants can communicate using $\binom{24}{2}=276$ shared keys. Each shared key was generated using the Elliptic Curve Diffie Hellman (ECDH) key exchange protocol on $E$.- During each key exchange, we intercepted the public point $A_i=a_iG$ and $A_j=a_jG$ of the two participants doing the exchange.
- For each byte of the flag, two participants are selected uniquely based on that byte. We intercept the shared key $S=a_ia_jG=a_{i,j}G$ generated by these two participants. Note that we don’t know who the participants are, only their shared key.
For each shared key we intercepted, we want to find out who were the participants that generated this key with ECDH.
I will focus on the unintended solution now. The critical weakness of the curve in this setup is that the order of the generator is divisible by multiple small prime factors.
sage: print(factor(G.order()))
2 * 3 * 181 * 757 * 3853 * 5762850060927107392022347066357549620994019469856294785348978961707389043954605112653017616082038365937976128687115706416102336484799919610312464007246935864827852236124441868927856859819940885425474736937583024745785269955856944009781392597978939787188095696135008407608734943964074042234316534836446680504816798310752312085561769545938550574980761380162844488558985006039623697057656577557316333265126063171467110505526046763584576186932284768283748672007657659988987450276187849475952210151251690399972672065971363507878380364070612446312858486903936265865513944601163677625845334489340676328379437419823
sage: 2 * 3 * 181 * 757 * 3853
3167559006
We can’t solve the Discrete Logarithm Problem because of the large prime factor. However, we can easily solve it modulo 3167559006, the product of the small prime factors. For every $A_i=a_iG$, we can recover $a_i \pmod{3167559006}$ using the same idea as in the Pohlig-Hellman algorithm. We solve the DLP modulo each small prime factor and then use the Chinese Remainder Theorem to get $a_i \pmod{3167559006}$.
For each $S=a_{i,j}G=a_ia_jG$ derived from the flag, we recover $a_{i,j} \pmod{3167559006}$ in the same way.
Since $a_{i,j} \pmod{3167559006} \equiv a_i \times a_j \pmod{3167559006}$, we can try each pair $(i, j)$ until the equation is verified. The moduli is large enough that there is a single solution for every byte of the flag.
from sage.all import *
from itertools import combinations
proof.all(False)
p = 0x9099d209a20bfbb731c9a003158ba131c4a0352415365d8f014c2bfd4913c2aaa67b910b4540582c29c8f1e54b7c6df8584d473237cdda8256f0377edd8cdde5316b5e245d426cee05ee97b45d7ac8b1fa161d568aa51ada54bf56b8ab997cb315f5c06e29b79cde39e0cf50efb55eed72e2a001a7333e75d5f1ac3b247bec1e5b545c0cffa519586b02c5e30a77d86e896a0b863d65d82d339a9f9724fe1eb9a87a27d108fa64e088a3e81468cb4d51a8b51064e34c7969fe3da3001fcfd36c81f14135a0f8fd13037bd5da457f5e1683324655b20ad2dbee44401f0eedd273af5e9df2a266983b32c897a9451a2a8989cc049fc619c6348d693b7aa0422a41
K = GF(p)
a = K(0)
b = K(0x135fa0fd3ed8926a72df7d8bb9b51961f06d609672f14a6838c3a8e7512bbc6d7a6764d15eb57d3cbffe042863fdab9760364dae6952b12d8be958fae44f1270ef9a9febff6f6d3c8fd134786ee207e6f737d1066cf0d303408c4074036dc0ac67dccb83dd0cddb3081fbc59f2e24d53a8fe2433be4cefaad018a72969f7dafc59c92f9d33294205cb7072e45ff5d03486b838379223d8b74b0d7dcfc85f3dc6bc629f2d3de5b7b4626d948c9f0eabb2926386efce4c46a5a5ed1a0f488199896b707d1f62896e72fee7fca2f9447c05c62afc560a463a7f8fe8eefbd9620c3f34cf710afd1f32c5661d7aeafe9c92b1ec58b7deb62335208683cde99ed142f6)
E = EllipticCurve(K, (a, b))
G = E(0x3fef464bb8efc071f9c88f875d776d12908edbad377ce38899a706b0d433ddd614e03b6a7c542ef3d0fb1870e9085647600d3886a8ba28762be85b6d9d450ef737a00ae29f63d6ac10986a79d6889b4500ecca629222cea29ac6c11f5037904fc95d6afbe7c61c8e2dfff116c96f31f21a8889ca020dc142e6577f02b791c785e0297adf592daf8b67b1465c288e7a5217e037d4561750aa35a5294d30f30e83fee74405c27f57f66c8c0c6159cd9f003e0e920edf201b211cf5abe09a3a3a9c94b358d2549782b041139523eeacd17715b761ddfdaef3091745ca84eb6ac825da1740815ce78a0cdbb9b3e90ef705a796b41a35068f96465476d89c27ab26fe, 0x5e2d616ab0da861b8ff8b667dac308dcd833a5bbb2772d34bcbf5f6d441e605acb465369d2c4a1259ee33711b3ed06c891c72afe4a4932cf8017d525d4e9be6d3524abb61438d3960f14742a01eab183dbc511904266edc964b738ad34ffdbb8032beb6db85970f961df3b5170606d9c02197ca8efdfc8cb91085aebabd22006c143436d7bd5c0bf9d51ded26b8e113cf58c87bf8591b279ae0a8c94d1210dd50ba77037418bd5b055fafe9827014ced892e8ea5b446e181b42a0640cc8fb2c446c5deacde8e12c2656d8a13ef9d07e5fc57b135944d884ad2458e4675e61be1a99765d9579e0430a5786e65850c12d99a9869dcca98dd01991d10fa097b2c03)
G.set_order(0x9099d209a20bfbb731c9a003158ba131c4a0352415365d8f014c2bfd4913c2aaa67b910b4540582c29c8f1e54b7c6df8584d473237cdda8256f0377edd8cdde5316b5e245d426cee05ee97b45d7ac8b1fa161d568aa51ada54bf56b8ab997cb315f5c06e29b79cde39e0cf50efb55eed72e2a001a7333e75d5f1ac3b247bec1e5b545c0cffa519586b02c5e30a77d86e896a0b863d65d82d339a9f9724fe1eb9a87a27d108fa64e088a3e81468cb4d51a8b51064e34c7969fe3da3001fcfd36c81f14135a0f8fd13037bd5da457f5e1683324655b20ad2dbee44401f0eedd273af5e9df2a266983b32c897a9451a2a8989cc049fc619c6348d693b7aa0422a42)
# Map each (i, j) combination to an ASCII char
combi_to_char = {combi: chr(c) for c, combi in enumerate(combinations(range(24), 2))}
# Parse challenge data
output = open('output.txt', 'r').read().replace(':', ',').split('\n')[:-1]
Xs = [E(X) for X in eval(output[0])]
# Notice that the order of G has multiple small factors
factors = [f[0] for f in factor(G.order())]
assert factors == [2, 3, 181, 757, 3853, 5762850060927107392022347066357549620994019469856294785348978961707389043954605112653017616082038365937976128687115706416102336484799919610312464007246935864827852236124441868927856859819940885425474736937583024745785269955856944009781392597978939787188095696135008407608734943964074042234316534836446680504816798310752312085561769545938550574980761380162844488558985006039623697057656577557316333265126063171467110505526046763584576186932284768283748672007657659988987450276187849475952210151251690399972672065971363507878380364070612446312858486903936265865513944601163677625845334489340676328379437419823]
# Using the Pohlig-Hellman algorithm, we can solve the DLP modulo N = 2 * 3 * 181 * 757 * 3853, ignoring the last very large prime
# This will give us the value of x mod N for each X=xG
# Map the index of each xG to that remainder
N = product(factors[:-1])
xs_mod_N = {}
for i, X in enumerate(Xs):
remainders = []
for f in factors[:-1]:
m = G.order() // f
G_i = m * G
P_i = m * X
r_i = P_i.log(G_i)
remainders.append(r_i)
x_mod_N = crt(remainders, factors[:-1])
xs_mod_N[i] = x_mod_N
print(i, x_mod_N)
flag = ''
# Now we do the same, but for each S
# This will give us the value of xy mod N for each S=xyG of the flag
for line in output[1:]:
S = E(eval(line))
remainders = []
for f in factors[:-1]:
m = G.order() // f
G_i = m * G
P_i = m * S
r_i = P_i.log(G_i)
remainders.append(r_i)
xy_mod_N = crt(remainders, factors[:-1])
# N is big enough so there is only one possible corresponding (x%N,y%N) pair for each xy%N
s = ''
for i, X1 in enumerate(Xs):
for j, X2 in enumerate(Xs):
if (i, j) not in combi_to_char: continue
if (xs_mod_N[i] * xs_mod_N[j]) % N == xy_mod_N:
s += combi_to_char[(i, j)]
assert len(s) == 1 # Only one solution for each S
flag += s
print(flag)
The flag is RM{DDHP_EZ?!}, which may hint at the intended solution.
ECDHivemind (Revenge)
The revenge version of ECDHivemind is the only challenge of the category that wasn’t solved during the CTF. You should probably read the previous paragraphs that discuss the challenge and its unintendend solution.
The only modification is the curve used for ECDH.
p = 0x3aabd973dcbe9f8af5c669825c6f6a3faa1c85ebd7127d677c7c727dd22de7a26569feb9ef87658ab71f240b4ceb4ab431b466ec4b5134eee4e38d2d94bdbf0bc1e22ad554c5514974883b7783cf11151bddc99cf41d22373ed88578f569829552f1affd8f0e36e5767e4c4e775e1f1c873bc29a41d3ec5ab841fd25ee3b733f7a153383b5039f32cacd0d8afb67e43496aa9c033110ad6802ebefdc9d5da9a145b7b3cc1f0bf0834d0573dae3a7a500d538fde7867b0d9cbb8fa2ee912ce923f8ce6dc109a9712880f306d5e337ffd80f466505c929eee293a19a28f972b1b362c62135ac64e4bb7f329dab35746e0ee7c885e04c3fec2b72e7e6be3e7512235
K = GF(p)
a = K(0)
b = K(0x27b234860be206c013ec7982a0bb8291293ee6a1750814b9f2e61a0747f6cd0e90a0d90d94f267a8bcb7a0c8a0d64225c444684c12ba3b2c4ab04293ecdd4d58171c32a0b7a4420709c8caef11000428a6e8fe87d3ecc183452a3e7af684677680354cbe7b193c9a99adea3332587b95d98cd4f9718ab8da6d39d1f782cd71277d74c14fb578d053392397f4385e67bc20988a3dea171d448c7e047b8ea0c9124dba9367e366a34d57d772252310301506a14676bae428d192f2859b38a4b52a845f471a5ac94ca99e4c4808e0f300302af8c53a992fc6ab0bd0e6620332f252df9ad00be7d86fbace1c6708301a48fd37eb5ee48abf7990af7213ebe86865329)
E = EllipticCurve(K, (a, b))
G = E(0x14363e3f823c8704ac621e14a4c6ac1ed095633566cca4217116cbd2ddec5b67924638876a217ea0932a59dcd0d27f5567ba28587f4f5056d79952586a0c2509be862e42a41b6c44fde23fe6e033ba6f6d4abefb9060e9ab7bef59eee768e096cecfeb6bf9ba860ba15700215909c69bc78028a4c3f78658add57a96edc21194065602a58abf445b5ed84413b25b292d1448747f65733a6691414742c7d81a3a2ecc6c693bae35b74d901d56778039a2a6b481811f9fc7e585cd0d5abdd2c723c4e1d487884b62560edc83ef9e569e5835a75871f8411613f38648d6dbf350e8375defa34777d5e21d6219543960a2d96b3d1910500ac842bedf032ab56de4921, 0x22059e98efeaffddfd7a3d386fcbeebc64849e5b20461e99a997bc9e576395782df83afc9058ef7d6db09825319fffd2653aef7aafc7943d373d93ca336b497466d47c3c158a9f7859610ab7f211180a082f9814e9b2f38f3cd8a040cf5d173423f080f740cc0e82b9a8acd2ac5238b7e4bb82fdcf4b8d863bf7bcb3e8924774a987332e8dcf235564f99e7017f3adbb79d9d762bde9f596aeab57778ddf84e13514f080487589f8e5f407dfe6b22ced5046873387d32cf53090c4f21a0ae10409b3499889a387874baa439c2d7dc82fc01494cc089b2ee093bd93e8b0a91574f5d821ebe05467d8b09ec9189842369a35ef9e89739c491cf9075015fa6aec387)
G.set_order(0x3aabd973dcbe9f8af5c669825c6f6a3faa1c85ebd7127d677c7c727dd22de7a26569feb9ef87658ab71f240b4ceb4ab431b466ec4b5134eee4e38d2d94bdbf0bc1e22ad554c5514974883b7783cf11151bddc99cf41d22373ed88578f569829552f1affd8f0e36e5767e4c4e775e1f1c873bc29a41d3ec5ab841fd25ee3b733f7a153383b5039f32cacd0d8afb67e43496aa9c033110ad6802ebefdc9d5da9a145b7b3cc1f0bf0834d0573dae3a7a500d538fde7867b0d9cbb8fa2ee912ce923f8ce6dc109a9712880f306d5e337ffd80f466505c929eee293a19a28f972b1b362c62135ac64e4bb7f329dab35746e0ee7c885e04c3fec2b72e7e6be3e7512236)
Now the only prime factors of $G$ we can find are 2 and 3. The unintended solution will not work because we can only recover $a_{i,j} \pmod{6}$ and now the equation $a_{i,j} \pmod{6} \equiv a_i \times a_j \pmod{6}$ has too many solutions $(i,j)$. By the way, I should have just chosen a $G$ with prime order to avoid any of that in the first place.
The curve is very strange. First of all, it is defined over a 2048-bit prime field, which is totally overkill for ECDH (usually 256 bits is enough). But most importantly, the order of the curve is one more than $p$, meaning that $E$ is supersingular.
sage: E.order() == p + 1
True
sage: E.is_supersingular()
True
It is well-known that the Elliptic Curve Discrete Logarithm Problem (ECDLP) on supersingular curves can be transferred to DLPs over finite fields using the MOV attack, because such curves have a low embedding degree. However, the curve is defined over such an absurdly large prime field that this will not be helpful here. We would need to factor the curve order and then it would still be too hard to solve the DLP because of the field sizes.
But to solve this challenge, we do not strictly need to solve the ECDLP.
Then we may try to calculate $(ab)G$ from $aG$ and $bG$. This would mean breaking the computational Diffie Hellman Problem (CDHP). The Wikipedia page tells us that this is probably won’t be easy either.
Computing the discrete logarithm is the only known method for solving the CDH problem. But there is no proof that it is, in fact, the only method. It is an open problem to determine whether the discrete log assumption is equivalent to the CDH assumption, though in certain special cases this can be shown to be the case.
But to solve this challenge, we do not strictly need to solve the CDHP either.
The problem we need to solve is called the decisional Diffie Hellman Problem (DDHP). That is the problem, given the values $aG$, $bG$ and $Q$, of detecting if $Q$ equals $(ab)G$. This is slightly different from the CDHP. We are not asked to find $(ab)G$ from $aG$, $bG$, but to recognize when the value $Q$ equals $(ab)G$. This is exactly the setup of this challenge, and this time the Wikipedia page gives us more hope.
The DDH assumption does not hold on elliptic curves over GF(p) with small embedding degree, a class which includes supersingular elliptic curves. This is because the Weil pairing or Tate pairing can be used to solve the problem directly.
Good, so we just need to implement that! Unfortunately, the page does not give any pointer on how to construct that pairing… But the solution has been studied in the litterature. I invite you to read Chapter 6.2 (Diffie-Hellman Key Exchange), in “Elliptic Curves, Number Theory And Cryptography”, by Lawrence C. Washington. The author proves and explains how the pairing works a lot better than I would be able to.
The construction of an oracle to solve the DDHP in that particular case (supersingular curve $E:y^2=x^3+b$ with $p \equiv 2 \pmod{3}$ and embedding 2) is the following:
- Let $\omega \in \mathbb{F}_{p^2}$ be a primitive third root of unity, with $\omega \notin \mathbb{F}_p$.
- Define the map $\beta: E(\overline{\mathbb{F_p}}) \to E(\overline{\mathbb{F_p}})$ by $(x,y) \to (\omega x, y)$ and $\beta(O)=O$. Using the formulas for the addition law, we can show that $\beta$ is a group isomorphism.
- Let $n$ be the order of $G$. Define the modified Weil pairing $\tilde{e}_n(P_1, P_2)=e_n(P_1, \beta(P_2))$, where $e_n$ is the usual Weil pairing.
- Suppose that we know $G$, $aG$, $bG$ and $Q$. Then $Q=abG$ if and only if $\tilde{e}_n(aG, bG) = \tilde{e}_n(Q, G)$.
With this method, we can solve the DDHP without solving any DLP. For each shared secret $bG$ corresponding to a byte of the flag, we try every pair of participants $(i,j)$ until our oracle tells us that $bG = a_{i} a_{j}G$.
from sage.all import *
from itertools import combinations
proof.all(False)
p = 0x3aabd973dcbe9f8af5c669825c6f6a3faa1c85ebd7127d677c7c727dd22de7a26569feb9ef87658ab71f240b4ceb4ab431b466ec4b5134eee4e38d2d94bdbf0bc1e22ad554c5514974883b7783cf11151bddc99cf41d22373ed88578f569829552f1affd8f0e36e5767e4c4e775e1f1c873bc29a41d3ec5ab841fd25ee3b733f7a153383b5039f32cacd0d8afb67e43496aa9c033110ad6802ebefdc9d5da9a145b7b3cc1f0bf0834d0573dae3a7a500d538fde7867b0d9cbb8fa2ee912ce923f8ce6dc109a9712880f306d5e337ffd80f466505c929eee293a19a28f972b1b362c62135ac64e4bb7f329dab35746e0ee7c885e04c3fec2b72e7e6be3e7512235
K = GF(p)
a = K(0)
b = K(0x27b234860be206c013ec7982a0bb8291293ee6a1750814b9f2e61a0747f6cd0e90a0d90d94f267a8bcb7a0c8a0d64225c444684c12ba3b2c4ab04293ecdd4d58171c32a0b7a4420709c8caef11000428a6e8fe87d3ecc183452a3e7af684677680354cbe7b193c9a99adea3332587b95d98cd4f9718ab8da6d39d1f782cd71277d74c14fb578d053392397f4385e67bc20988a3dea171d448c7e047b8ea0c9124dba9367e366a34d57d772252310301506a14676bae428d192f2859b38a4b52a845f471a5ac94ca99e4c4808e0f300302af8c53a992fc6ab0bd0e6620332f252df9ad00be7d86fbace1c6708301a48fd37eb5ee48abf7990af7213ebe86865329)
E = EllipticCurve(K, (a, b))
G = E(0x14363e3f823c8704ac621e14a4c6ac1ed095633566cca4217116cbd2ddec5b67924638876a217ea0932a59dcd0d27f5567ba28587f4f5056d79952586a0c2509be862e42a41b6c44fde23fe6e033ba6f6d4abefb9060e9ab7bef59eee768e096cecfeb6bf9ba860ba15700215909c69bc78028a4c3f78658add57a96edc21194065602a58abf445b5ed84413b25b292d1448747f65733a6691414742c7d81a3a2ecc6c693bae35b74d901d56778039a2a6b481811f9fc7e585cd0d5abdd2c723c4e1d487884b62560edc83ef9e569e5835a75871f8411613f38648d6dbf350e8375defa34777d5e21d6219543960a2d96b3d1910500ac842bedf032ab56de4921, 0x22059e98efeaffddfd7a3d386fcbeebc64849e5b20461e99a997bc9e576395782df83afc9058ef7d6db09825319fffd2653aef7aafc7943d373d93ca336b497466d47c3c158a9f7859610ab7f211180a082f9814e9b2f38f3cd8a040cf5d173423f080f740cc0e82b9a8acd2ac5238b7e4bb82fdcf4b8d863bf7bcb3e8924774a987332e8dcf235564f99e7017f3adbb79d9d762bde9f596aeab57778ddf84e13514f080487589f8e5f407dfe6b22ced5046873387d32cf53090c4f21a0ae10409b3499889a387874baa439c2d7dc82fc01494cc089b2ee093bd93e8b0a91574f5d821ebe05467d8b09ec9189842369a35ef9e89739c491cf9075015fa6aec387)
G.set_order(0x3aabd973dcbe9f8af5c669825c6f6a3faa1c85ebd7127d677c7c727dd22de7a26569feb9ef87658ab71f240b4ceb4ab431b466ec4b5134eee4e38d2d94bdbf0bc1e22ad554c5514974883b7783cf11151bddc99cf41d22373ed88578f569829552f1affd8f0e36e5767e4c4e775e1f1c873bc29a41d3ec5ab841fd25ee3b733f7a153383b5039f32cacd0d8afb67e43496aa9c033110ad6802ebefdc9d5da9a145b7b3cc1f0bf0834d0573dae3a7a500d538fde7867b0d9cbb8fa2ee912ce923f8ce6dc109a9712880f306d5e337ffd80f466505c929eee293a19a28f972b1b362c62135ac64e4bb7f329dab35746e0ee7c885e04c3fec2b72e7e6be3e7512236)
# First, the curve has the form y^2 = x^3 + B (mod p) with p % 3 == 2
# It is a typical construction to generate a supersingular curve
assert p % 3 == 2
assert E.is_supersingular()
# We could try to solve the DLP using the MOV attack, but p+1 has a prime factor too large to solve the DLP in a finite field, so we have to find another way
# Note that the goal is to solve the Decisional Diffie-Hellman problem (DDH), we don't actually need to solve the DLP
# https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption
# Taken from https://github.com/jvdsn/crypto-attacks/blob/master/shared/ecc.py#L18
def get_embedding_degree(q, n, max_k):
for k in range(1, max_k + 1):
if q ** k % n == 1:
return k
return None
# Supersingular curve always have a low embedding degree
assert get_embedding_degree(p, E.order(), 10) == 2
# According to Wikipedia
# "The DDH assumption does not hold on elliptic curves over GF(p) with small embedding degree"
# "This is because the Weil pairing or Tate pairing can be used to solve the problem directly"
# Solution based on "Elliptic Curves, Number Theory And Cryptography" - Washington
# Section 6.2 - DECISION DIFFIE-HELLMAN PROBLEM
K2 = GF(p ** 2, 'a')
E2 = EllipticCurve(K2, (a, b))
P = PolynomialRing(K2, 'x')
x = P.gen()
# w is a 3-rd root of unity in K2
w = (x ** 3 - 1).roots()[1][0]
assert w in K2 and w not in K
# beta: x, y -> (wx, y) is a group isomorphism
def beta(P):
assert P in E2
if P == E2.zero():
return E2.zero()
else:
return E2(w * P.x(), P.y())
# Define the modified weil pairing
def modified_weil(P1, P2):
return P1.weil_pairing(beta(P2), G.order())
# Return true if Q == abG, knowing G, aG and bG
def ECDH_decision(G, aG, bG, Q):
return modified_weil(E2(aG), E2(bG)) == modified_weil(E2(Q), E2(G))
# Map combination to an ASCII char
combi_to_char = {combi: chr(c) for c, combi in enumerate(combinations(range(24), 2))}
output = open('output.txt', 'r').read().replace(':', ',').split('\n')[:-1]
Xs = [E(X) for X in eval(output[0])]
from tqdm import trange
import string
ALPHABET = string.printable[:-4]
# Solve each DDH problem to recover the flag
flag = ''
for line_i in trange(len(output)-1):
line = output[1+line_i]
S = E(eval(line))
S = E2(S)
found = False
for i, X1 in enumerate(Xs):
if found: break
for j, X2 in enumerate(Xs):
if found: break
if (i, j) not in combi_to_char: continue
if combi_to_char[(i, j)] not in ALPHABET: continue
if ECDH_decision(G, X1, X2, S):
flag += combi_to_char[(i, j)]
found = True
print(i, j)
print(flag)
We recover the flag after a few minutes: RM{h4RD3rDDHPIH0pE}.