Les registres à décalage à rétroaction linéaire (LFSR) constituent un mécanisme fondamental en cryptographie symétrique, souvent utilisé pour générer des flux pseudo-aléatoires. Lors d'un challenge CTF, un flag était protégé par ce type de primitive. Voici une analyse détaillée du fonctionnement et de la méthode d'attaque.

Le challenge

Le script génère un identifiant UUID aléatoire, l'encapsule dans un flag, puis le découpe en quatre blocs de 32 bits. Chaque bloc sert d'état initial pour un LFSR qui produit 1000 bits de sortie. Le masque de rétroaction est fixé à 0b10001001000010000100010010001001.

from Crypto.Util.number import *
import uuid

def generer_flux(etat, masque):
    nouvel_etat = (etat << 1) & 0xFFFFFFFF
    combinaison = etat & masque
    bit_sortie = bin(combinaison).count('1') % 2
    nouvel_etat ^= bit_sortie
    return nouvel_etat, bit_sortie

identifiant = str(uuid.uuid4())
drapeau = 'hgame{' + identifiant + '}'
print(drapeau)

identifiant_nettoye = identifiant.replace('-', '')
blocs_initiaux = [int(identifiant_nettoye[i*8:i*8+8], 16) for i in range(4)]

masque = 0b10001001000010000100010010001001
sequences = []

for bloc in blocs_initiaux:
    etat_courant = bloc
    bits_produits = ''
    for _ in range(1000):
        etat_courant, bit = generer_flux(etat_courant, masque)
        bits_produits += str(bit)
    sequences.append(bits_produits)

print(f'sequences={sequences}')
# sequences=['1111110110111011110000101011010001000111111001111110100101000011110111111100010000111110110111100001001000101101011110111100010010100000011111101101110101011010111000000011110000100011101111011011000100101100110100101110001010001101101110000010001000111100101010010110110111101110011011001011111011010101011000011011000111011011111001101010111100101100110001011010010101110011101001100111000011110111000001101110000001111100000100000101111100010110111001110011010000011011110110011000001101011111111010110011010111010101001000010011110110011110110101011110111010011010010110111111010011101000110101111101111000110011111110010110000100100100101101010101110010101001101010101011110111010011101110000100101111010110101111110001111111110010000000001110011100100001011111110100111011000101001101001110010010001100011000001101000111010010000101101111101011000000101000001110001011001010010001000011000000100010010010010111010011111111011100100100100101111111001110000111110110001111001111100101001001100010', '0010000000001010111100001100011101111101111000100100111010101110010110011001011110101100011101010000001100000110000000011000000110101111111011100100110111011010000100011111000111001000101001110010110010001000110010101011110011101000011111101101011000011110001101011111000110111000011000110011100100101100111100000100100101111001011101110001011011111111011010100010111011000010010101110110100000110100000100010101000010111101001000011000000000111010010101010111101101011111011001000101000100011001100101010110110001010010001010110111011011111101011100111001101111111111010011101111010010011110011111110100110011111110110001000111100010111000101111000011011011111101110101110100111000011100001010110111100011001011010011010111000110101100110100011101101011101000111011000100110110001100110101010110010011011110000111110100111101110000100010000111100010111000010000010001111110110100001000110110100100110110010110111010011111101011110000011101010100110101011110000110101110111011010110110000010000110001', '1110110110010001011100111110111110111001111101010011001111100100001000111001101011010100010111110101110101111010111100101100010011001001011101000101011000110111000010000101001000100111010110001010000111110110111000011001100010001101000010001111111100000101111000100101000000001001001001101110000100111001110001001011010111111010111101101101001110111010111110110011001000010001010100010010110110101011100000101111100100110011110001001001111100101111001111011011010111001001111010001100110001100001100000110000011111010100101111000000101011111010000111110000101111100010000010010111010110100101010101001111100101011100011001001011000101010101001101100010110000010001110011110011100111000110101010111010011010000001100001011000011101101000000011111000101111101011110011000011011000100100110111010011001111101100101100011000101001110101111001000010110010111101110110010101101000000101001011000000001110001110000100000001001111100011010011000000011011101111101001111110001011101100000010001001010011000001', '0001101010101010100001001001100010000101010100001010001000100011101100110001001100001001110000110100010101111010110111001101011011101110000011001000100100101000011011101000111001001010011100010001010110111011100100111110111001010010111010100000100111110101110010010110100001000010010001101111001110100010001011101100111011101011101100100101011010101000101001000101110011011111110110011111111100000000011100000010011000110001000110101010001011000010101000110000101001110101010111011010010111011001010011100010101001100110000110101100010000100110101110100001101001011011110011100110011001010110100101010111110110111100000111010001111101110000000000111011011101000011001010010111001110111000100111011110100101000100011011101100011111000101110110110111111001111000000011100011000010000101001011001101110101000010101001000100110010000101001111100101000001011011010011110001101000001101111010100101001100010100000111000011110101010100011011001110001011110111010111011010101101100000110000001010010101111011']

Analyse du LFSR

Le LFSR fonctionne en décalant son état d'un bit vers la gauche à chaque itération. Le bit de rétroaction est calculé par parité (XOR) des positions actives du masque. La clé de l'attaque réside dans la linéarité de cette opération : connaissant les bits de sortie, on peut reconstituer l'état initial bit par bit.

La première étape consiste à identifier les positions actives du masque :

MASQUE_BINAIRE = '10001001000010000100010010001001'
positions_feedback = [idx for idx, bit in enumerate(MASQUE_BINAIRE) if bit == '1']
# [0, 4, 7, 12, 17, 21, 24, 28, 31]

Récupération de l'état initial

Après 31 itérations, l'état original de 32 bits a été entièrement décalé. Les 31 premiers bits de sortie occupent les positions 0 à 30 du registre, et il ne reste qu'un seul bit inconnu (le bit 31 original). En testant les deux valeurs possibles (0 ou 1) pour ce bit, on peut valider laquelle est correcte en vérifiant la cohérence avec le bit de sortie suivant. Ce processus se répète pour chaque bit, du LSB vers le MSB.

MASQUE_BINAIRE = '10001001000010000100010010001001'
POSITIONS_FEEDBACK = [idx for idx, bit in enumerate(MASQUE_BINAIRE) if bit == '1']

def calculer_parite(registre):
    resultat = 0
    for pos in POSITIONS_FEEDBACK:
        resultat ^= int(registre[pos])
    return resultat

def reconstruire_etat(sequence_bits):
    bits_recuperes = []
    for _ in range(32):
        taille_connue = len(bits_recuperes)
        remplissage = sequence_bits[:(31 - taille_connue)]
        candidat = '0' + ''.join(bits_recuperes) + remplissage
        bit_attendu = int(sequence_bits[31 - taille_connue])
        parite_calculee = calculer_parite(candidat)
        if parite_calculee == bit_attendu:
            bits_recuperes.insert(0, '0')
        else:
            bits_recuperes.insert(0, '1')
    valeur_hex = hex(int(''.join(bits_recuperes), 2))[2:]
    return valeur_hex

sequences = ['1111110110111011110000101011010001000111111001111110100101000011110111111100010000111110110111100001001000101101011110111100010010100000011111101101110101011010111000000011110000100011101111011011000100101100110100101110001010001101101110000010001000111100101010010110110111101110011011001011111011010101011000011011000111011011111001101010111100101100110001011010010101110011101001100111000011110111000001101110000001111100000100000101111100010110111001110011010000011011110110011000001101011111111010110011010111010101001000010011110110011110110101011110111010011010010110111111010011101000110101111101111000110011111110010110000100100100101101010101110010101001101010101011110111010011101110000100101111010110101111110001111111110010000000001110011100100001011111110100111011000101001101001110010010001100011000001101000111010010000101101111101011000000101000001110001011001010010001000011000000100010010010010111010011111111011100100100100101111111001110000111110110001111001111100101001001100010', '0010000000001010111100001100011101111101111000100100111010101110010110011001011110101100011101010000001100000110000000011000000110101111111011100100110111011010000100011111000111001000101001110010110010001000110010101011110011101000011111101101011000011110001101011111000110111000011000110011100100101100111100000100100101111001011101110001011011111111011010100010111011000010010101110110100000110100000100010101000010111101001000011000000000111010010101010111101101011111011001000101000100011001100101010110110001010010001010110111011011111101011100111001101111111111010011101111010010011110011111110100110011111110110001000111100010111000101111000011011011111101110101110100111000011100001010110111100011001011010011010111000110101100110100011101101011101000111011000100110110001100110101010110010011011110000111110100111101110000100010000111100010111000010000010001111110110100001000110110100100110110010110111010011111101011110000011101010100110101011110000110101110111011010110110000010000110001', '1110110110010001011100111110111110111001111101010011001111100100001000111001101011010100010111110101110101111010111100101100010011001001011101000101011000110111000010000101001000100111010110001010000111110110111000011001100010001101000010001111111100000101111000100101000000001001001001101110000100111001110001001011010111111010111101101101001110111010111110110011001000010001010100010010110110101011100000101111100100110011110001001001111100101111001111011011010111001001111010001100110001100001100000110000011111010100101111000000101011111010000111110000101111100010000010010111010110100101010101001111100101011100011001001011000101010101001101100010110000010001110011110011100111000110101010111010011010000001100001011000011101101000000011111000101111101011110011000011011000100100110111010011001111101100101100011000101001110101111001000010110010111101110110010101101000000101001011000000001110001110000100000001001111100011010011000000011011101111101001111110001011101100000010001001010011000001', '0001101010101010100001001001100010000101010100001010001000100011101100110001001100001001110000110100010101111010110111001101011011101110000011001000100100101000011011101000111001001010011100010001010110111011100100111110111001010010111010100000100111110101110010010110100001000010010001101111001110100010001011101100111011101011101100100101011010101000101001000101110011011111110110011111111100000000011100000010011000110001000110101010001011000010101000110000101001110101010111011010010111011001010011100010101001100110000110101100010000100110101110100001101001011011110011100110011001010110100101010111110110111100000111010001111101110000000000111011011101000011001010010111001110111000100111011110100101000100011011101100011111000101110110110111111001111000000011100011000010000101001011001101110101000010101001000100110010000101001111100101000001011011010011110001101000001101111010100101001100010100000111000011110101010100011011001110001011110111010111011010101101100000110000001010010101111011']

drapeau = ''
for seq in sequences:
    drapeau += reconstruire_etat(seq)
print(drapeau)
# fbbbee823f434f919337907880e4191a
# hgame{fbbbee82-3f43-4f91-9337-907880e4191a}