# Weird Algorithm **Flag:** CYBN{N0t\_v3ry\_3ff1c1ent\_4lg0r1thm} ## Challenge {% hint style="info" %} **Description** *** Nous avons intercepté un fichier contenant des informations top secrètes. Cependant, ce fichier semble totalement vide. Nous pensons que ses auteurs ont utilisé un algorithme dont nous avons réussi à obtenir une partie de la documentation. Votre mission est simple : rendre ces informations lisibles. {% endhint %} ## Solution Le fichier chiffré ne contient que 2 caractères différents et en contient 1190 : ```python with open('flag.enc', 'r') as f: encrypted = f.read() print(f'Size: {len(encrypted)}') print(f'Caracters: {len(set(encrypted))}') print(f'Divisors: {divisors(len(encrypted))}') # Size: 1190 # Caracters: 2 # Divisors: [1, 2, 5, 7, 10, 14, 17, 34, 35, 70, 85, 119, 170, 238, 595, 1190] ``` Il faut partir sur l'hypothèse que tous les nombres dans la matrice finale montrée dans le PDF sont écrit en binaire où l'on a remplacé 0 et 1 par 2 caractères random. De là, il faut forcément que les paramètres bits et depth soient des diviseurs de 1190, puisqu'ils représentent la largeur et la hauteur de la matrice. On sait qu'on a chiffré de l'ASCII (*la valeur max est 127*), on en déduit que **`bits = 7`** Concernant **`depth`**, **`5`** est la seule valeur plausible, car pour toutes les valeurs ASCII possibles, le maximum de nombres de facteurs premiers est 6 (*et il est n'est pas diviseur de 1190*). ```python from sympy import factorint print(max([len(factorint(n, multiple=True)) for n in range(128)])) # 6 ``` Maintenant, on va réassembler tous les bits ensemble pour former des nombres. Le caractère qui correspond à 0 ou 1 n'a pas d'importance. ```python with open('flag.enc', 'r') as f: encrypted = f.read() bits = 7 depth = 5 encrypted = ''.join(['1' if c == ' ' else '0' for c in encrypted]) numbers = [int(encrypted[i:i+bits], 2) for i in range(0, len(encrypted), bits)] print(f'\nNumbers:\n{numbers}') # Numbers: # [41, 113, 41, 41, 41, 42, 42, 41, 41, 41, 57, 43, 41, 41, 41, 43, 41, 41, 41, 41, 41, 45, 42, 41, 41, 42, 41, 42, 41, 47, 42, 37, 69, 45, 41, 41, 42, 41, 41, 41, 42, 42, 45, 41, 41, 42, 35, 59, 41, 41, 57, 41, 35, 41, 77, 41, 42, 41, 41, 43, 41, 43, 59, 41, 41, 42, 41, 45, 41, 41, 35, 37, 41, 37, 42, 41, 41, 41, 41, 41, 41, 41, 41, 57, 43, 41, 41, 47, 41, 41, 41, 45, 42, 42, 79, 42, 42, 41, 42, 41, 41, 41, 41, 41, 43, 42, 43, 41, 42, 53, 59, 42, 43, 59, 35, 45, 43, 41, 42, 47, 43, 41, 41, 42, 41, 41, 37, 43, 41, 42, 41, 47, 41, 42, 41, 45, 107, 41, 41, 43, 1, 43, 43, 42, 41, 19, 41, 41, 41, 41, 57, 42, 41, 47, 43, 47, 41, 35, 53, 59, 42, 43, 41, 42, 43, 41, 53, 42, 41, 41] ``` On voit que 41, 42 et 43 reviennent énormément. C'est normal, ils correspondent aux facteurs 1, 2 et 3 comme on peut le déduire du tableau montré dans l'exemple :
Maintenant, il faut déterminer la clé du XOR. Pour ça on va faire l'hypothèse que le nombre le plus présent est le facteur 1, de là, on pourra déterminé avec quoi il a été XOR et donc la clé : ```python stats = sorted([(n, numbers.count(n)) for n in set(numbers)], key=lambda o: o[1], reverse=True) print(f'\nStats:\n{stats}') # On prend le nombre le plus présent xored_one = stats[0][0] key = 1 ^ xored_one print(f'\nKey: {key}') # Stats: # [(41, 82), (42, 30), (43, 17), (45, 7), (47, 6), (35, 5), (59, 5), (37, 4), (57, 4), (53, 3), (1, 1), (69, 1), (107, 1), (77, 1), (79, 1), (113, 1), (19, 1)] # # Key: 40 ``` On peut désormais XOR tous les nombres avec cette clé : ```python numbers = [n ^ key for n in numbers] print(f'\nNumbers:\n{numbers}') # Numbers: # [1, 89, 1, 1, 1, 2, 2, 1, 1, 1, 17, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 5, 2, 1, 1, 2, 1, 2, 1, 7, 2, 13, 109, 5, 1, 1, 2, 1, 1, 1, 2, 2, 5, 1, 1, 2, 11, 19, 1, 1, 17, 1, 11, 1, 101, 1, 2, 1, 1, 3, 1, 3, 19, 1, 1, 2, 1, 5, 1, 1, 11, 13, 1, 13, 2, 1, 1, 1, 1, 1, 1, 1, 1, 17, 3, 1, 1, 7, 1, 1, 1, 5, 2, 2, 103, 2, 2, 1, 2, 1, 1, 1, 1, 1, 3, 2, 3, 1, 2, 29, 19, 2, 3, 19, 11, 5, 3, 1, 2, 7, 3, 1, 1, 2, 1, 1, 13, 3, 1, 2, 1, 7, 1, 2, 1, 5, 67, 1, 1, 3, 41, 3, 3, 2, 1, 59, 1, 1, 1, 1, 17, 2, 1, 7, 3, 7, 1, 11, 29, 19, 2, 3, 1, 2, 3, 1, 29, 2, 1, 1] ``` Il n'y a que des nombres premiers, notre hypothèse se confirme et nous sommes sur la bonne voie. Dans le PDF, on sait que tous les caractères ASCII sont décomposés en **`depth`** facteurs premiers, donc ici en 5 facteurs chacun. La question est de savoir comment ils sont disposés dans notre tableau :
On peut tester les deux, mais c'est bien la seconde façon de faire qui est la bonne : ```python def mul(values: list[int]) -> int: acc = 1 for n in values: acc *= n return acc # Donne des valeurs qui ne sont pas ASCII groups = [numbers[i:i+depth] for i in range(0, len(numbers), depth)] print(f'Groups:\n{groups}') caracters = [mul(group) for group in groups] print(f'Caracters:\n{caracters}') # Groups: # [[1, 89, 1, 1, 1], [2, 2, 1, 1, 1], [17, 3, 1, 1, 1], [3, 1, 1, 1, 1], [1, 5, 2, 1, 1], [2, 1, 2, 1, 7], [2, 13, 109, 5, 1], [1, 2, 1, 1, 1], [2, 2, 5, 1, 1], [2, 11, 19, 1, 1], [17, 1, 11, 1, 101], [1, 2, 1, 1, 3], [1, 3, 19, 1, 1], [2, 1, 5, 1, 1], [11, 13, 1, 13, 2], [1, 1, 1, 1, 1], [1, 1, 1, 17, 3], [1, 1, 7, 1, 1], [1, 5, 2, 2, 103], [2, 2, 1, 2, 1], [1, 1, 1, 1, 3], [2, 3, 1, 2, 29], [19, 2, 3, 19, 11], [5, 3, 1, 2, 7], [3, 1, 1, 2, 1], [1, 13, 3, 1, 2], [1, 7, 1, 2, 1], [5, 67, 1, 1, 3], [41, 3, 3, 2, 1], [59, 1, 1, 1, 1], [17, 2, 1, 7, 3], [7, 1, 11, 29, 19], [2, 3, 1, 2, 3], [1, 29, 2, 1, 1]] # Caracters: # [89, 4, 51, 3, 10, 28, 14170, 2, 20, 418, 18887, 6, 57, 10, 3718, 1, 51, 7, 2060, 8, 3, 348, 23826, 210, 6, 78, 14, 1005, 738, 59, 714, 42427, 36, 58] # Fonctionne width = len(numbers) // depth groups = [[numbers[width * x + w] for x in range(depth)] for w in range(width)] print(f'Groups 2:\n{groups}') caracters = [mul(group) for group in groups] print(f'Caracters 2:\n{caracters}') # Groups 2: # [[1, 1, 1, 1, 67], [89, 1, 1, 1, 1], [1, 2, 11, 3, 1], [1, 1, 13, 2, 3], [1, 1, 1, 3, 41], [2, 1, 13, 1, 3], [2, 2, 2, 2, 3], [1, 2, 1, 29, 2], [1, 5, 1, 19, 1], [1, 1, 1, 2, 59], [17, 1, 1, 3, 1], [3, 2, 1, 19, 1], [1, 11, 1, 11, 1], [1, 19, 1, 5, 1], [1, 1, 1, 3, 17], [3, 1, 17, 1, 2], [1, 17, 3, 2, 1], [1, 1, 1, 7, 7], [1, 11, 1, 3, 3], [1, 1, 7, 1, 7], [1, 101, 1, 1, 1], [5, 1, 1, 2, 11], [2, 2, 1, 1, 29], [1, 1, 5, 1, 19], [1, 1, 2, 13, 2], [2, 3, 2, 3, 3], [1, 1, 103, 1, 1], [2, 3, 2, 2, 2], [1, 19, 2, 1, 3], [7, 1, 1, 7, 1], [2, 1, 2, 1, 29], [13, 2, 1, 2, 2], [109, 1, 1, 1, 1], [5, 5, 1, 5, 1]] # Caracters 2: # [67, 89, 66, 78, 123, 78, 48, 116, 95, 118, 51, 114, 121, 95, 51, 102, 102, 49, 99, 49, 101, 110, 116, 95, 52, 108, 103, 48, 114, 49, 116, 104, 109, 125] ``` Le script complet : ```python with open('flag.enc', 'r') as f: encrypted = f.read() bits = 7 depth = 5 encrypted = ''.join(['1' if c == ' ' else '0' for c in encrypted]) numbers = [int(encrypted[i:i+bits], 2) for i in range(0, len(encrypted), bits)] stats = sorted([(n, numbers.count(n)) for n in set(numbers)], key=lambda o: o[1], reverse=True) xored_one = stats[0][0] key = 1 ^ xored_one numbers = [n ^ key for n in numbers] def mul(values: list[int]) -> int: acc = 1 for n in values: acc *= n return acc # Fonctionne width = len(numbers) // depth groups = [[numbers[width * x + w] for x in range(depth)] for w in range(width)] caracters = [mul(group) for group in groups] flag = bytes([mul(group) for group in groups]).decode() print(flag) # CYBN{N0t_v3ry_3ff1c1ent_4lg0r1thm} ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://ctf.thaysan.com/ctf-and-writeups/2024-or-efrei-cybernight/cryptographie/weird-algorithm.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.