Skip to content

Instantly share code, notes, and snippets.

@elliptic-shiho

elliptic-shiho/solve.sage

Created June 24, 2024 08:43
Show Gist options
  • Save elliptic-shiho/51e97a1a8552cebb8170623c7339d336 to your computer and use it in GitHub Desktop.
Save elliptic-shiho/51e97a1a8552cebb8170623c7339d336 to your computer and use it in GitHub Desktop.
Download ZIP
Google CTF 2024 Quals: mceliece
Raw
solve.sage
"""
Google CTF 2024 Quals: mceliece
References:
1. V. M. Sidelinkov and S. O. Shestakov. 1992. "On insecurity of cryptosystems based on generalized Reed-Solomon codes".
2. C. Wischebrink. 2009. "Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes".
3. A. Couvreur, P. Gaborit, V. Gauthier-Umaña, A. Otmani, and Jean-Pierre Tillich. 2013 (revised at 2014). "Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes".
4. A. Otmani and H. T. Kalachi. 2015. "Square Code Attack on a Modified Sidelnikov Cryptosystem".
"""
from sage.all import *
from Crypto.Util.number import long_to_bytes
from functools import reduce
from tqdm import tqdm
import itertools
def compute_squared_dimension(C):
comp = []
for v1, v2 in itertools.combinations(C.basis(), r=2):
if v1.is_zero():
continue
if v2.is_zero():
continue
v = vector([e1 * e2 for e1, e2 in zip(v1, v2)]) # component-wise product
if v.is_zero():
continue
comp.append(v)
if len(comp) == 0:
return 0
return span(comp).dimension()
def find_random_position(pk, k, r, n):
# An implementation of [3]
rows, columns = pk.dimensions()
LC = LinearCode(pk)
a = min(LC.length() // 2, k - 1)
print(f"[+] {a = }")
assert a < k
assert 2 * k - 1 + r - n < a
rand = []
odd_code = LC.shortened([x * 2 + 1 for x in range(a)])
odd_dim = compute_squared_dimension(odd_code)
even_code = LC.shortened([x * 2 for x in range(a)])
even_dim = compute_squared_dimension(even_code)
for i in tqdm(range(columns), ascii=True, ncols=64):
C = odd_code if i % 2 == 0 else even_code
d = odd_dim if i % 2 == 0 else even_dim
dim = compute_squared_dimension(C.punctured([i // 2]))
if d - dim == 1:
rand.append(i)
print(rand)
if len(rand) != r:
print("[-] length mismatch")
print(f"Expected: {r}, Actual: {len(rand)}")
return rand
def sidelinkov_shestakov_attack(pubkey, ciphertext):
# An implementation of [1], but I also referenced [2]
k, n = pubkey.dimensions()
M = pubkey.echelon_form()
F = M.base_ring()
# we need to guess c := c_{b1} / c_{b2} \in F
for c in tqdm(F.list(), ascii=True, ncols=64):
a = [0 for _ in range(n)]
# we can assume a[0] = 0 and a[1] = 1
a[0] = 0
a[1] = 1
# find a[k], ..., a[n - 1] using a property of echelon form
failed = False
for j in range(k, n):
# M[0, j] / M[1, j] = c * (a[j] - 1) / a[j]
# <=> a[j] = c / (c - M[0, j] / M[1, j])
x = M[0, j] / M[1, j]
if x == c:
failed = True
break
a[j] = c / (c - x)
if failed:
continue
# find a[2], ..., a[k - 1]
for i in range(2, k):
for j1 in range(k, n - 1):
j2 = j1 + 1
"""
A[j] := M[0, j] / M[i, j] * a[j]
There exists `t` which satisfies A[j] = t * (a[j] - a[i])
t is an independent value to `i` so it holds
A[j1] - A[j2] = t * (a[j1] - a[j2])
<=> (A[j1] - A[j2]) / (a[j1] - a[j2]) = t.
"""
Aj1 = M[0, j1] / M[i, j1] * a[j1]
Aj2 = M[0, j2] / M[i, j2] * a[j2]
if a[j1] == a[j2]:
continue
t = (Aj1 - Aj2) / (a[j1] - a[j2])
if t == 0:
continue
# If we have `t`, we can compute a[i] directly
a[i] = -Aj1 / t + a[j1]
break
else:
failed = True
break
if failed:
continue
try:
C = codes.GeneralizedReedSolomonCode(a, k)
return C.decode_to_code(vector(ciphertext))
except:
# If we can't guess `c` correctly, `a[i]` is not valid
pass
def solve():
p, n, k, r = load("params.sobj")
ciphertext = load("flag_enc.sobj")
pubkey = load("pubkey.sobj")
print("[+] Find random column positions")
assert 2 * k - 1 + r > n
random_positions = find_random_position(pubkey, k, r, n)
print(f"Guessed positions = {random_positions}")
ciphertext = ciphertext.delete_columns(random_positions)
pubkey = pubkey.delete_columns(random_positions)
print("[+] Sidelinkov & Shestakov Attack")
decoded = sidelinkov_shestakov_attack(pubkey, ciphertext)
print(f"{decoded = }")
m = pubkey.solve_left(decoded)
print(f"{m = }")
unpadded_message = long_to_bytes(
reduce(lambda x, y: ZZ(x) * p + ZZ(y), m[: -ZZ(m[-1])][::-1], 0)
)
print(f"{unpadded_message = }")
if __name__ == "__main__":
solve()
"""
Mon Jun 24 17:41:01 JST 2024 ~/Downloads/mceliece
> sage solve.sage
[+] Find random column positions
[+] a = 147
0%| | 0/295 [00:00<?, ?it/s][0]
3%|8 | 9/295 [00:00<00:10, 26.58it/s][0, 9]
5%|#3 | 15/295 [00:00<00:10, 26.59it/s][0, 9, 17]
8%|##1 | 24/295 [00:00<00:10, 26.24it/s][0, 9, 17, 25]
9%|##3 | 27/295 [00:01<00:10, 26.29it/s][0, 9, 17, 25, 28]
13%|###4 | 39/295 [00:01<00:09, 26.45it/s][0, 9, 17, 25, 28, 39]
15%|###9 | 45/295 [00:01<00:09, 26.29it/s][0, 9, 17, 25, 28, 39, 46]
17%|####4 | 51/295 [00:01<00:09, 26.35it/s][0, 9, 17, 25, 28, 39, 46, 53]
21%|#####5 | 63/295 [00:02<00:08, 26.40it/s][0, 9, 17, 25, 28, 39, 46, 53, 65]
23%|###### | 69/295 [00:02<00:08, 26.28it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70]
29%|#######6 | 87/295 [00:03<00:07, 26.22it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89]
32%|########1 | 93/295 [00:03<00:08, 24.71it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95]
39%|#########6 | 114/295 [00:04<00:06, 26.01it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114]
43%|##########6 | 126/295 [00:04<00:06, 26.02it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126]
46%|###########4 | 135/295 [00:05<00:06, 26.16it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137]
47%|###########6 | 138/295 [00:05<00:05, 26.20it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140]
50%|############4 | 147/295 [00:05<00:05, 26.23it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148]
51%|############7 | 150/295 [00:05<00:05, 26.27it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151]
52%|############9 | 153/295 [00:05<00:05, 26.17it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154]
53%|#############2 | 156/295 [00:05<00:05, 26.02it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158]
54%|#############4 | 159/295 [00:06<00:05, 26.09it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161]
55%|#############7 | 162/295 [00:06<00:05, 26.13it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162]
56%|#############9 | 165/295 [00:06<00:04, 26.12it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165]
58%|##############4 | 171/295 [00:06<00:04, 26.04it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173]
61%|###############2 | 180/295 [00:06<00:04, 25.84it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180]
63%|###############7 | 186/295 [00:07<00:04, 26.01it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187]
73%|##################3 | 216/295 [00:08<00:03, 26.19it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218]
76%|################### | 225/295 [00:08<00:02, 25.94it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225]
83%|####################8 | 246/295 [00:09<00:01, 26.16it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246]
87%|#####################8 | 258/295 [00:09<00:01, 26.12it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259]
[0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260]
88%|######################1 | 261/295 [00:09<00:01, 26.14it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261]
93%|#######################1 | 273/295 [00:10<00:00, 26.03it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261, 275]
100%|########################9| 294/295 [00:11<00:00, 26.00it/s][0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261, 275, 294]
100%|#########################| 295/295 [00:11<00:00, 26.12it/s]
Guessed positions = [0, 9, 17, 25, 28, 39, 46, 53, 65, 70, 87, 89, 93, 95, 114, 126, 137, 140, 148, 151, 154, 157, 158, 161, 162, 165, 171, 173, 180, 187, 217, 218, 225, 246, 259, 260, 261, 275, 294]
[+] Sidelinkov & Shestakov Attack
60%|##############9 | 312/521 [00:07<00:04, 42.31it/s]
decoded = (94, 351, 127, 78, 419, 48, 405, 278, 256, 334, 495, 26, 61, 70, 486, 37, 439, 479, 399, 88, 201, 345, 73, 369, 247, 388, 383, 120, 348, 69, 512, 62, 77, 150, 190, 184, 157, 94, 423, 72, 452, 383, 285, 384, 166, 220, 7, 256, 81, 6, 104, 147, 228, 171, 434, 323, 204, 60, 169, 301, 294, 21, 441, 264, 367, 152, 180, 45, 189, 299, 207, 351, 351, 409, 159, 305, 229, 110, 345, 423, 508, 392, 359, 261, 88, 425, 310, 14, 38, 475, 489, 42, 82, 173, 116, 171, 157, 153, 144, 442, 272, 4, 222, 96, 140, 197, 296, 286, 349, 387, 23, 509, 32, 414, 57, 188, 414, 256, 154, 454, 283, 288, 222, 14, 141, 119, 464, 421, 440, 78, 15, 395, 167, 201, 221, 329, 62, 440, 397, 516, 95, 308, 449, 232, 270, 164, 469, 341, 443, 231, 78, 464, 410, 8, 349, 24, 47, 348, 481, 473, 209, 19, 351, 499, 459, 323, 427, 106, 219, 214, 105, 216, 100, 451, 288, 331, 293, 231, 188, 423, 379, 459, 341, 18, 50, 121, 317, 299, 459, 472, 509, 122, 154, 31, 224, 281, 217, 496, 7, 517, 299, 355, 293, 280, 515, 186, 420, 65, 300, 102, 147, 206, 255, 502, 484, 490, 413, 421, 315, 16, 95, 148, 133, 438, 384, 225, 22, 131, 432, 473, 408, 342, 161, 294, 354, 496, 401, 304, 209, 431, 272, 442, 369, 100, 84, 30, 262, 11, 197, 520, 105, 501, 397, 516, 223, 184)
m = (415, 292, 340, 123, 291, 53, 146, 417, 338, 476, 466, 517, 446, 220, 33, 433, 72, 212, 125, 480, 191, 224, 84, 140, 435, 362, 121, 366, 118, 518, 98, 440, 153, 273, 198, 76, 236, 102, 477, 339, 510, 166, 477, 19, 226, 323, 319, 108, 386, 2, 260, 271, 165, 57, 427, 509, 412, 57, 501, 390, 375, 363, 457, 350, 334, 110, 482, 46, 339, 74, 73, 323, 492, 10, 403, 132, 412, 140, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91)
unpadded_message = b'CTF{1f_0nly_th3r3_w45_50m3_c0d3_1nd1st1ngu15h4bl3_fr0m_r4nd0mn355_70c2decd2dd58446e825}\n'
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment