API tools faq
paste
Guest User

Untitled

a guest
Jun 1st, 2025
101
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.05 KB | None | 0 0
raw download clone embed print report
  1. import sys
  2. sys.path.append("dist")
  3.  
  4. from base64 import b64encode, b64decode
  5. import re, random
  6. from sage.modules.finite_submodule_iter import FiniteZZsubmodule_iterator
  7. from itertools import product
  8. from functools import reduce
  9.  
  10. ##########################################
  11. ########## START From challenge ##########
  12. ##########################################
  13.  
  14. NROUNDS = 10
  15. SEED = int(0xcaffe *3* 0xc0ffee)
  16.  
  17. # https://people.maths.bris.ac.uk/~matyd/GroupNames/61/Q8s5D4.html
  18. G = PermutationGroup([
  19. [(1,2,3,4),(5,6,7,8),(9,10,11,12),(13,14,15,16),(17,18,19,20),(21,22,23,24),(25,26,27,28),(29,30,31,32)],
  20. [(1,24,3,22),(2,23,4,21),(5,14,7,16),(6,13,8,15),(9,27,11,25),(10,26,12,28),(17,31,19,29),(18,30,20,32)],
  21. [(1,5,12,30),(2,6,9,31),(3,7,10,32),(4,8,11,29),(13,25,19,21),(14,26,20,22),(15,27,17,23),(16,28,18,24)],
  22. [(1,26),(2,27),(3,28),(4,25),(5,14),(6,15),(7,16),(8,13),(9,23),(10,24),(11,21),(12,22),(17,31),(18,32),(19,29),(20,30)]
  23. ])
  24. num2e = [*G]
  25. e2num = {y:x for x,y in enumerate(num2e)}
  26. b64encode_map = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0987654321+/"
  27. b64decode_map = {c:i for i,c in enumerate(b64encode_map)}
  28.  
  29. def gen_random_mat(seed: int, size: int):
  30. random.seed(seed)
  31. return matrix(size, size, random.choices([0,1], k=size*size))
  32.  
  33. def mat_vec_mul(mat, vec):
  34. return [reduce(lambda x,y: x*y, (a^b for a,b in zip(vec, m))) for m in mat]
  35.  
  36. def hash_msg(msg: bytes):
  37. emsg = b64encode(msg).decode().strip("=")
  38. sz = len(emsg)
  39. vec = [num2e[b64decode_map[c]] for c in emsg]
  40. mat = gen_random_mat(SEED, sz)
  41. for _ in range(NROUNDS):
  42. # Since G is non-abelian so this is a pretty good hash function!
  43. vec = mat_vec_mul(mat, vec)
  44. return ''.join((b64encode_map[e2num[c]] for c in vec))
  45.  
  46. ct = "aO3qDbHFoittWTN6MoUYw9CZiC9jdfftFGw1ipES89ugOwk2xCUzDpPdpBWtBP3yarjNOPLXjrMODD"
  47.  
  48. ########################################
  49. ########## END From challenge ##########
  50. ########################################
  51.  
  52. def find_generators():
  53. """
  54. Find elements a,b,c,d of G such that
  55. 1. All elements of G are uniquely of the form: a^x b^y c^z d^w
  56. 2. a^x b^y c^z d^w |-> ((a, (b, c)), d) exibits an isomorphism
  57. G -> (C4 × (C4 ⋊ C2)) ⋊ C2
  58. │ │ │ │
  59. 0th 1st 2nd 3rd - component
  60. """
  61.  
  62. e_ord = {}
  63. for o,e in ((e.order(), e) for e in num2e):
  64. if o not in e_ord: e_ord[o] = []
  65. e_ord[o].append(e)
  66.  
  67. for a,b,c,d in product(e_ord[4], e_ord[4], e_ord[2], e_ord[2]):
  68. if a == b or c == d: continue
  69. if len(set(a^x * b^y * c^z * d^w for x,y,z,w in product(*map(range, (4,4,2,2))))) != 64: continue
  70. if b*c != c*b^(-1): continue
  71. if a*b*a^(-1) != b: continue
  72. if a*c*a^(-1) != c: continue
  73. break
  74.  
  75. return a,b,c,d
  76.  
  77. a,b,c,d = find_generators()
  78. # Maps elements in G to-and-fro tuple representation. See `find_generators`.
  79. e2tuple = {a^x * b^y * c^z * d^w: (x,y,z,w) for x,y,z,w in product(*map(range, (4,4,2,2)))}
  80. tuple2e = {y:x for x,y in e2tuple.items()}
  81.  
  82. def cast_vec(vec, dim):
  83. """
  84. Cast a vector of elements in G to the `dim`-th
  85. component. See `find_generators`
  86. """
  87. return [e2tuple[c][dim] for c in vec]
  88.  
  89. def my_hash(vec):
  90. """
  91. Like `hash_msg but without the base64 part`
  92. """
  93. sz = len(vec)
  94. mat = gen_random_mat(SEED, sz)
  95. for _ in range(NROUNDS):
  96. vec = mat_vec_mul(mat, vec)
  97. return vec
  98.  
  99. def modq_kernel(matx, q):
  100. """
  101. Solves for the kernel of `matx` which is a matrix
  102. with elements in ZZ/`q`ZZ
  103. """
  104. # From: https://ask.sagemath.org/question/49365/computing-the-mod-q-kernel-of-a-matrix-for-q-composite/
  105. source_dim = matx.ncols()
  106. target_dim = matx.nrows()
  107. domain = ZZ^source_dim / (q * ZZ^source_dim)
  108. codomain = ZZ^target_dim / (q * ZZ^target_dim)
  109. phi = domain.hom([codomain(matx.columns()[i]) for i in range(source_dim)])
  110.  
  111. full_kernel = matrix([domain(b) for b in phi.kernel()]).T
  112.  
  113. pivot_cols = full_kernel.echelon_form().pivots()
  114. reduced_kernel = matrix(full_kernel.columns()[i] for i in pivot_cols)
  115. return reduced_kernel.change_ring(Zmod(q))
  116.  
  117. def matq_solve_right_all(mat, vec, q):
  118. """
  119. Solves for all vectors u such that
  120. `mat * u = vec`, where we are working
  121. in ZZ/`q`ZZ.
  122. """
  123. v = mat.solve_right(vec)
  124. if is_prime(q):
  125. return [v + k for k in mat.right_kernel()]
  126. kernel = modq_kernel(mat, q)
  127. print(f"Kernel has {kernel.nrows()} rows")
  128. if kernel.nrows() > 8: raise Exception(f"Too many solutions, regen challenge")
  129. if kernel.nrows() == 0: return [v]
  130. unique_v = set(tuple(v + k) for k in FiniteZZsubmodule_iterator([*kernel]))
  131. return list(vector(Zmod(q), v) for v in unique_v)
  132.  
  133.  
  134. sz = len(ct)
  135. ct_vec = [num2e[b64decode_map[c]] for c in ct]
  136.  
  137. # By working in the quotient G -> G/(C4 × (C4 ⋊ C2)),
  138. # isomorphic to C2,
  139. # find all possible 3rd component of the flag.
  140.  
  141. ct_vec_3 = vector(Zmod(2), cast_vec(ct_vec, 3))
  142. mat_3 = gen_random_mat(SEED, sz).change_ring(Zmod(2))^NROUNDS
  143. pos_pt_3s = matq_solve_right_all(mat_3, ct_vec_3, 2)
  144.  
  145. print("No. possible 3rd component:", len(pos_pt_3s), end="\n\n")
  146. for pt_vec_3 in pos_pt_3s:
  147.  
  148. # By commutating with (known) 3rd component,
  149. # and working in the quotient
  150. # (C4 × (C4 ⋊ C2)) -> (C4 × (C4 ⋊ C2))/C4/C4,
  151. # isomorphic to C2,
  152. # find all possible 2nd component of the flag.
  153.  
  154. mat = []
  155. for j in range(sz):
  156. v = [tuple2e[(0,0,int(i==j),b)] for i,b in enumerate(pt_vec_3)]
  157. v = cast_vec(my_hash(v), 2)
  158. mat.append(v)
  159. mat = matrix(Zmod(2), mat).T
  160.  
  161. known = my_hash([tuple2e[(0,0,0,b)] for b in pt_vec_3])
  162. diff = [a * b^(-1) for a,b in zip(ct_vec, known)]
  163. diff = vector(Zmod(2), cast_vec(diff, 2))
  164. pos_pt_2s = matq_solve_right_all(mat, diff, 2)
  165.  
  166. print(f"Assuming 3rd component is: {''.join(map(str, pt_vec_3))},\n"
  167. "No. possible 2nd component:", len(pos_pt_2s), end="\n\n")
  168. for pt_vec_2 in pos_pt_2s:
  169.  
  170. # By commutating with (known) 3rd component,
  171. # and working in the quotient
  172. # (C4 × (C4 ⋊ C2)) -> (C4 × (C4 ⋊ C2))/C4,
  173. # and commutating with (known) 2nd component,
  174. # we can work in C4 to
  175. # find all possible 1st component of the flag.
  176.  
  177. mat = []
  178. for j in range(sz):
  179. v = [tuple2e[(0, int(i==j), *v)]
  180. for i, v
  181. in enumerate(zip(pt_vec_2, pt_vec_3))]
  182. v = cast_vec(my_hash(v), 1)
  183. mat.append(v)
  184. mat = matrix(Zmod(4), mat).T
  185.  
  186. known = my_hash([tuple2e[(0, 0, *v)] for v in zip(pt_vec_2, pt_vec_3)])
  187. diff = [a * b^(-1) for a,b in zip(ct_vec, known)]
  188. diff = vector(Zmod(4), cast_vec(diff, 1))
  189. pos_pt_1s = matq_solve_right_all(mat, diff, 4)
  190.  
  191. # Since `matq_solve_right_all` is super slow when
  192. # the modulus isn't prime, we can optimize by filtering out
  193. # possible 1st component of the flag since we know
  194. # the flag has to start with `grey{`.
  195.  
  196. knownflag_b64 = b64encode(b"grey{")[:6].decode()
  197. possible_pt_vec_1_values_first_6 = [
  198. set((tuple2e[(x,0,0,0)]
  199. * num2e[b64decode_map[c]]
  200. * tuple2e[(0,0,0,b3)]
  201. * tuple2e[(0,0,b2,0)] for x in range(4))
  202. )
  203. - set((tuple2e[(0,x,0,0)] for x in range(4)))
  204. for c,b2,b3
  205. in zip(knownflag_b64, pt_vec_2, pt_vec_3)]
  206. possible_pt_vec_1_values_first_6 = [
  207. set([e2tuple[x][1] for x in c])
  208. for c in possible_pt_vec_1_values_first_6]
  209.  
  210. pos_pt_1s = filter(
  211. lambda s: all(a in b for a,b in zip(s, possible_pt_vec_1_values_first_6)),
  212. pos_pt_1s)
  213. pos_pt_1s = list(pos_pt_1s)
  214.  
  215. print(f"Assuming 3rd component is: {''.join(map(str, pt_vec_3))},\n"
  216. f"Assuming 2nd component is: {''.join(map(str, pt_vec_2))},\n"
  217. "No. possible 1st component:", len(pos_pt_1s), end="\n\n")
  218. for pt_vec_1 in pos_pt_1s:
  219.  
  220. # By commutating with (known) 3rd component,
  221. # and working in the quotient
  222. # (C4 × (C4 ⋊ C2)) -> (C4 × (C4 ⋊ C2))/(C4 ⋊ C2),
  223. # isomorphic to C4,
  224. # find all possible 1st component of the flag.
  225.  
  226. mat = []
  227. for j in range(sz):
  228. v = [tuple2e[(int(i==j), *v)]
  229. for i, v
  230. in enumerate(zip(pt_vec_1, pt_vec_2, pt_vec_3))]
  231. v = cast_vec(my_hash(v), 0)
  232. mat.append(v)
  233. mat = matrix(Zmod(4), mat).T
  234.  
  235. known1 = my_hash([tuple2e[(0,0,0,b3)] for b3 in pt_vec_3])
  236. known2 = my_hash([tuple2e[(0,*v,0)] for v in zip(pt_vec_1, pt_vec_2)])
  237. diff = [a * b^(-1) * c^(-1) for a,b,c in zip(ct_vec, known1, known2)]
  238. diff = vector(Zmod(4), cast_vec(diff, 0))
  239. pos_pt_0s = matq_solve_right_all(mat, diff, 4)
  240.  
  241. print(f"Assuming 3rd component is: {''.join(map(str, pt_vec_3))},\n"
  242. f"Assuming 2nd component is: {''.join(map(str, pt_vec_2))},\n"
  243. f"Assuming 1st component is: {''.join(map(str, pt_vec_1))},\n"
  244. "No. possible 0th component:", len(pos_pt_0s), end="\n\n")
  245. for pt_vec_0 in pos_pt_0s:
  246.  
  247. # Finally, with all 4 components,
  248. # we can check if the components we have found
  249. # is actually the flag.
  250.  
  251. b64_flag = ''.join(
  252. b64encode_map[e2num[a^x * b^y * c^z * d^w]]
  253. for x,y,z,w in zip(pt_vec_0, pt_vec_1, pt_vec_2, pt_vec_3)
  254. )
  255. print(f"Found Base64:", b64_flag)
  256. try: decoded = b64decode(b64_flag + "="*2, validate=False).decode()
  257. except: continue
  258. if not re.match(r"^grey\{.+\}$", decoded): continue
  259.  
  260. print("Possible flag:", decoded)
  261.  
  262.  
  263. # No. possible 3rd component: 2
  264. #
  265. # Assuming 3rd component is: 000011001001000101001110010110000010011101111011100000110110001111011000000110,
  266. # No. possible 2nd component: 2
  267. #
  268. # Kernel has 3 rows
  269. # Assuming 3rd component is: 000011001001000101001110010110000010011101111011100000110110001111011000000110,
  270. # Assuming 2nd component is: 010111101010010000011110001011010000011000011010110000010101000010001011011010,
  271. # No. possible 1st component: 1
  272. #
  273. # Kernel has 3 rows
  274. # Assuming 3rd component is: 000011001001000101001110010110000010011101111011100000110110001111011000000110,
  275. # Assuming 2nd component is: 010111101010010000011110001011010000011000011010110000010101000010001011011010,
  276. # Assuming 1st component is: 131232113220100022303201322230012222003032230000303012213203120132202221022230,
  277. # No. possible 0th component: 4
  278. #
  279. # Found Base64: K4J8eW/KeH8iIyBhFmOzfURJNl9mcwA2HFmHARfiPkkfTAQhfzNBJGmZOXi4LGiucmGgXE92D07keC
  280. # Found Base64: J3I9eW2IcH8hLyAhHkMydXRKOk9mdyB1FEkEDSchMkleSCQidzMCJFkbMWg6JEgudmEjXG91B80kfA
  281. # Found Base64: I3I0eW1JdH8gKyAhGlNycWRLPk9mdzB1EElFCTdgNkleSDQjczMDJElaNWh5IFhudmFiXH91A79kfB
  282. # Found Base64: L4J7eW+LfH8jJyBhEnPzeVRIMl9mcxA2GFnGBQejOkkfTBQgezNAJHnYPXj3KHjucmHhXF92C98keD
  283. # Kernel has 3 rows
  284. # Assuming 3rd component is: 000011001001000101001110010110000010011101111011100000110110001111011000000110,
  285. # Assuming 2nd component is: 110011010011110011110011101010011011100110011111010101101110111010111111100011,
  286. # No. possible 1st component: 0
  287. #
  288. # Assuming 3rd component is: 100111110000100110100011110111001001100011111110000101001101110111101100111111,
  289. # No. possible 2nd component: 2
  290. #
  291. # Kernel has 3 rows
  292. # Assuming 3rd component is: 100111110000100110100011110111001001100011111110000101001101110111101100111111,
  293. # Assuming 2nd component is: 010111101010010000011110001011010000011000011010110000010101000010001011011010,
  294. # No. possible 1st component: 0
  295. #
  296. # Kernel has 3 rows
  297. # Assuming 3rd component is: 100111110000100110100011110111001001100011111110000101001101110111101100111111,
  298. # Assuming 2nd component is: 110011010011110011110011101010011011100110011111010101101110111010111111100011,
  299. # No. possible 1st component: 1
  300. #
  301. # Kernel has 3 rows
  302. # Assuming 3rd component is: 100111110000100110100011110111001001100011111110000101001101110111101100111111,
  303. # Assuming 2nd component is: 110011010011110011110011101010011011100110011111010101101110111010111111100011,
  304. # Assuming 1st component is: 131232113220100022303201322230012222003032230000303012213203120132202221022230,
  305. # No. possible 0th component: 4
  306. #
  307. # Found Base64: b4JmfXvaPH8zYyAhV8eyPFRZdl9nchA2WE7XQAPyfklfSRQxPzMRIW8IfXyqaXzudnXwWU91SlnlfT
  308. # Found Base64: Z3JleXtZMG8wbzAhX0dyNHRael9ncjB1UF9USDMwcllfTTRzNzNSIV9KdWxpYUxvdmVzWW91QnllfQ
  309. # Possible flag: grey{Y0o0o0!_Gr4tZz_gr0uP_TH30rY_M4s73R!_JuliaLovesYouBye}
  310. # Found Base64: Y3JkeXsYNG8xazAhW9cyMGRbfl9nciB1VF0VTCNxdllfTSRyMzNTIU0LcWwoZVwvdmUyWX91RmklfR
  311. # Found Base64: a4JnfXubOH8yZyAhU7fyOERYcl9ncgA2XE8WRBOzeklfSQQwOzMQIX7JeXzrbWyudnWxWV91TkmlfS
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!