Weird Algorithm

Flag: CYBN{N0t_v3ry_3ff1c1ent_4lg0r1thm}

Challenge

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.

Solution

Le fichier chiffré ne contient que 2 caractères différents et en contient 1190 :

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).

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.

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é :

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é :

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 :

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 :

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}