3. Chiffrement XOR mono-octet

Single-byte XOR cipher

The hex encoded string:
1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736
... has been XOR'd against a single character. Find the key, decrypt the message.
You can do this by hand. But don't: write code to do it for you.
How? Devise some method for "scoring" a piece of English plaintext. Character frequency is a good metric. Evaluate each output and choose the one with the best score.
Achievement Unlocked: You now have our permission to make "ETAOIN SHRDLU" jokes on Twitter.

Le but de cet exercice est de trouver le caractère unique qui a été utilisé pour chiffrer avec XOR chacun des caractères de la chaine hexadécimale fournie.

Le chiffrement XOR avec un seul caractères fonctionne de la manière suivante :

• un caractère unique est choisi comme clef de chiffrement ; par exemple a
• on l'utilise pour chiffrer un à un chacun des caractères d'une phrase

Par exemple, si on veut chiffrer le mot cryptopals, le résultat sera la concaténation de c ⊕ a, r ⊕ a, y ⊕ a, p ⊕ a, t ⊕ a, o ⊕ a, p ⊕ a, a ⊕ a, l ⊕ a et s ⊕ a.

On pourrait aussi écrire cryptopals ⊕ aaaaaaaaaa.

Attaque par force-brute

En réutilisant la fonction xor_hex de l'exercice précédent, on peut facilement essayer de déchiffrer la chaîne de caractères donnée en testant l'ensemble des caractères de la table ASCII de l'index 32 (correspondant à un espace ) jusqu'à l'index 126 (~). Ces caractères correspondent à ceux usuellement présent sur un clavier et celui utilisé pour cette exercice est sans doute contenu dans cet intervalle.

En terme de code on peut donc écrire:

def xor_hex(string_one, string_two):
    return format(int(string_one, 16) ^ int(string_two, 16), "x")

def xor_single_char_breaker(hex_string):
    length = len(hex_string) // 2

    for i in range(32, 127):
        xored_hex = xor_hex(hex_string, format(i, "x")*length)
        print(chr(i), bytearray.fromhex(xored_hex).decode())

xor_single_char_breaker("1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736")

Lorsque l'on exécute ce script, on va donc obtenir 94 lignes correspondant à chaque tentative de déchiffrement de la chaîne de caractère de l'exercice avec un des caractères de la table ASCII entre 32 et 126.

On remarque qu'à la ligne correspondant au caractère X on trouve:

Cooking MC's like a pound of bacon

Analyse fréquentielle

La solution du paragraphe précédent fonctionne en l'état car il n'y a que 94 possibilités. Le travail devient cependant très fastidieux si il faut déchiffrer plusieurs chaines de caractères, car cela revient à scruter les différentes lignes de résultat du script jusqu'à trouver la bonne solution.

Une solution alternative à laquelle l'énoncé fait allusion avec les mots ETAOIN SHRDLU est l'anaylse fréquentielle des résultats.

En deux mots, l'analyse fréquentielle est le concept selon lequel un texte écrit dans une langue a une fréquence distincte d'apparition pour chacun des caractères qui le compose. Par exemple, en anglais la lettre e est celle apparaissant le plus souvent (il représente 13% du texte), suivi du a (8.2%), puis du o (7.5%), etc.

En se basant sur la fréquence des caractères en anglais, il est facile de coder une fonction élisant le candidat le plus probable pour les différents déchiffrement de la section précédent :

FREQUENCY_SCORES = {
    "A": 8.2,
    "B": 4.4,
    "C": 5.2,
    "D": 4.3,
    "E": 13,
    "F": 4,
    "G": 1.6,
    "H": 6.1,
    "I": 7,
    "J": 0.51,
    "K": 0.86,
    "L": 2.4,
    "M": 3.8,
    "N": 6.7,
    "O": 7.5,
    "P": 4.3,
    "Q": 0.22,
    "R": 6,
    "S": 6.3,
    "T": 9.1,
    "U": 2.8,
    "V": 0.82,
    "W": 5.5,
    "X": 0.045,
    "Y": 0.76,
    "Z": 0.045,
    "'": 1,
    " ": 15,
}
def char_frequency_score(string):
    string = string.upper()
    score = 0
    for char in string:
        if(char in FREQUENCY_SCORES):
            score += FREQUENCY_SCORES[char]
        else:
            score -= 1
    return score

def xor_hex(string_one, string_two):
    return format(int(string_one, 16) ^ int(string_two, 16), "x")

def xor_single_char_breaker(hex_string):
    length = len(hex_string) // 2

    xor_list = []

    for i in range(33, 127):
        xored_hex = xor_hex(hex_string, format(i, "x")*length)
        xor_list.append({
            "char": chr(i),
            "string": bytearray.fromhex(xored_hex).decode(),
            "score": char_frequency_score(bytearray.fromhex(xored_hex).decode())
        })
    return sorted(xor_list, key=lambda d: -d['score'])

print(xor_single_char_breaker("1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736")[0])

Remarque: On notera qu'il est également important de prendre en compte les caractères et ' dans l'élection du meilleur candidat étant donné leur forte présence dans un texte. Par ailleurs on ne se soucie pas pour le moment de distinguer majuscule et minuscule.

En exécutant ce script on obtient directement la solution au problème:

{'char': 'X', 'string': "Cooking MC's like a pound of bacon", 'score': 159.21999999999997}