Solution de SayWess pour Mille Fautes

Table des matières

Analyse

Plusieurs fichiers sont fournis, une explication de chacun d’entre eux est nécessaire.

`assembly.py`

Il s’agit du fichier qui permet de transformer du code assembleur en du bytecode en hexadécimal.

Pour l’utiliser, on crée un assembleur.asm dans lequel on écrit notre code assembleur (se référer à la doc de la VM pour voir les opérations permises). On le transforme en bytecode de la manière suivante :

python3 assembly.py assembleur.asm

Cela nous donne une sortie en hexadécimal, correspondant à notre code assembleur.

`crypto_accelerator.py`

Il s’agit d’un fichier utilisé par machine.py afin d’implémenter certaines fonctions utiles en crypto de manière efficace pour la machine. Il n’y a pas besoin d’en comprendre le contenu pour résoudre le challenge.

`machine.py`

Implémentation d’une machine exécutant du code assembleur, comprendre son implémentation en entier n’est pas le plus facile, seulement quelques portions sont utiles pour comprendre et résoudre le challenge.

On peut y repérer notamment les différents registres qu’on manipule en assembleur :

#Initialize registers
self.a  = 0
self.b  = 0
self.dst = 0
self.R0 = 0
self.R1 = 0
self.R2 = 0
self.R3 = 0
self.R4 = 0
self.R5 = 0
self.R6 = 0       # p
self.R7 = 0       # q
self.R8 = 0       # iq
self.R9 = 0       # dp
self.RA = 0       # dq
self.RB = e       # e
self.exponent = 0 # d
self.module = N   # n

Les registres au-delà de R9 sont notés en hexa : R10 = RA
exponent est équivalent à RC
module est équivalent à RD
a est l’accumulateur ou ACC (Accumulator). Il s’agit du registre de travail principal. Il est utilisé par un grand nombre d’instructions dans lesquelles il est référencé en tant que A (ou a dans le code ici présent).
b est utilisé par les opérations multiplication et division. Dans les autres cas, il peut être utilisé comme un second registre de travail.

`machine-faulted.py`

Cette classe hérite de machine dans machine.py et override sa fonction finalize_move.

class FaultedMachine(Machine):

    def __init__(self, code, list_faults = []):
        super().__init__(code)
        self.list_faults = list_faults

    def finalize_move(self):
        if self.nbInstruction in self.list_faults:
            self.a = randrange(1 << maxBitSize)
        super().finalize_move()

Elle consiste principalement à mettre une valeur aléatoire dans l’accumulateur (a) lorsque l’on est à l’instruction présente dans la liste list_faults, puis continuer ce que la fonction originale faisait.

def finalize_move(self):
    if (self.a).bit_length() < maxBitSize:
        if 0 == self.dst:  self.R0 = self.a
        if 1 == self.dst:  self.R1 = self.a
        if 2 == self.dst:  self.R2 = self.a
        if 3 == self.dst:  self.R3 = self.a
        if 4 == self.dst:  self.R4 = self.a
        if 5 == self.dst:  self.R5 = self.a
        if 6 == self.dst:  self.R6 = self.a
        if 7 == self.dst:  self.R7 = self.a
        if 8 == self.dst:  self.R8 = self.a
        if 9 == self.dst:  self.R9 = self.a
        if 10 == self.dst: self.RA = self.a
        if 11 == self.dst: self.RB = self.a
        if 12 == self.dst: self.exponent = self.a
        if 13 == self.dst: self.module = self.a
        if 14 == self.dst: self.lr = self.a
        if 15 == self.dst: self.pc = self.a
    else:
        self.error = True

La fonction originale met a dans le registre indiqué par self.dst

`RSA.asm`

Un joli code assembleur, de quoi faire fuir pas mal de monde… même s’il n’a rien de bien sorcier au final car il s’agit du code pour une exponentiation de type ‘Square and Multiply Always’ comme indiqué dans l’énoncé

    MOV     R0, #0
    MOV     R1, #1
    MOV     R2, R1          ;initialize output with 1
loop:
    MUL     R4, R2, R6      ;current_result * A     (multiply)
    MOD     R4, R4
    AND     R3, R5, R1      ;read lsb of exponent
    MUL     R4, R3, R4      ;R4 = current_result * A if lsb is 1
    XOR     R3, R3, R1
    MUL     R2, R3, R2      ;R2 = current_result if lsb is 0
    ADD     R2, R2, R4
    POW     R6, R6          ;A**2                   (square)
    SRL     R5, R5, R1      ;drop lsb of exponent
    CMP     R5, R0          ;is exponent > 0 ?
    JNZR    loop
    STP

Si on essaie de comprendre un peu ce qu’il se passe (on veut que R2 = R6**R5 = A**d):

R4 = R2 * R6 où R6 est une valeur constante (ie A)
R4 = R4 % RD (où RD = N)
R3 = lsb(R5) (où R5 est l’exposant d)
R4 = R3 * R4
R3 = R3 ^ 1
R2 = R3 * R2
R2 = R2 + R4
R6 = R6 ** RC (où RC vaut 2, on le verra plus tard)
R5 = R5 » 1
R5 > 0 ?
loop ou stop

On peut voir qu’il y a 2 possibilités suivant la valeur de R3.

Si R3 = 1 (on reprend juste après R3 = lsb(R5) pour détailler les valeurs):

R4 = R4
R3 = 0
R2 = 0
R2 = R4

Si R3 = 0:

R4 = 0
R3 = 1
R2 = R2
R2 = R2

On observe que dans un cas, R2 dépend de R4, dans l’autre, R2 ne dépend pas de R4

`mille-fautes.py`

Voici le cœur du challenge.

La fonction RSAKeyGen() génère une clé RSA, elle renvoie N et d, la clé privée

def RSAKeyGen(nbits, e):
    N = 2
    while N.bit_length() != nbits:
        p = getPrime(nbits // 2)
        q = getPrime(nbits // 2)
        N = p * q
    d = gmpy2.invert(e, (p - 1) * (q - 1))
    return N, d

La fonction authenticate() met le registre R5 à d et R6 à M, l’exposant à 2 et le module à N, puis run un code assembleur.

Elle renvoie le registre R2 ainsi que le nombre d’instructions executées

def authenticate(c, M, N, d):
    c.R5 = d
    c.R6 = M
    c.exponent = 2
    c.module = N

    c.runCode()
    if c.error:
        return 0, c.nbInstruction

    return c.R2, c.nbInstruction

Enfin verifyAuthentication() vérifie que M == s**e % N

def verifyAuthentication(s, M, N, e):
    return M == gmpy2.powmod(s, e, N)

On peut maintenant comprendre le code principal

if __name__ == "__main__":
    nbits = 1024
    e = 65537
    N, d = RSAKeyGen(nbits, e)
    print(f"{N = }")

    code = open("RSA.asm").read().splitlines()
    code = assembly(code)

    for i in range(nbits):
        print("Enter the index of the instruction you want to fault")
        fault = [ int(input(">>> ")) ]
        machine = FaultedMachine(code, fault)
        M = randrange(N)
        s, n = authenticate(machine, M, N, d)
        print(f"{i:5d} {fault[0]:5d} {n:5d} {verifyAuthentication(s, M, N, e)}")

On génère une clé RSA de 1024 bits, récupère le bytecode de l’assembleur RSA.asm, puis pour chaque bit de la clé :

Demande un numéro d’instruction où engendrer une faute (le a aléatoire vu dans la machine-faulted)
Génère un M aléatoire
Exécute le code assembleur avec une faute à l’instruction choisie et récupère le registre R2 à la fin de l’exécution du code, ainsi que le nombre d’instructions exécutées.

Le code est censé mettre R2 à M**d.

Print le numéro de bit, le numéro d’instruction où il y a eu une faute, le nombre d’instructions et si M == s**e % N où s = M**d

`mille-fautes.txt`

Contient tous les print effectués dans la fonction principale de mille-fautes.py donc :

le numéro de bit, le numéro d’instruction où il y a eu une faute, le nombre d’instructions et si M == s**e % N où s = M**d

Solve

Maintenant qu’on a analysé tout ça, il est assez facile de comprendre comment solve ce challenge.

En regardant la sortie de mille-fautes.txt, on remarque que l’instruction qui est fautée est probablement toujours la même

Enter the index of the instruction you want to fault
>>>     0     3 11268 False
Enter the index of the instruction you want to fault
>>>     1    14 11268 True
Enter the index of the instruction you want to fault
>>>     2    25 11268 True

Si on compare avec le code assembleur de RSA.asm, la 3ème (4ème en réalité, la première est considérée comme la 0ème) instruction est :

MUL R4, R2, R6 ;current_result * A (multiply)

Soit R4 = R2*R6

Lorsque cette instruction est fautée, la valeur de l’accumulateur a qui est censé contenir le résultat de la multiplication et le mettre dans R4, contient alors une valeur aléatoire mise dans R4. Cela fait qu’on obtient plus M**d à la fin, mais M**l où l != d car la multiplication est fausse pour 1 bit de d.

En se souvenant que dans RSA.asm, le résultat dans R2 à chaque tour de boucle dépend uniquement de la valeur de R3, qui est le lsb de R5, cela dépend juste du ième bit de d.

Lorsque le ième bit de d vaut 0, R2 ne dépend pas de R4, donc le résultat n’est pas faussé.

Lorsque le ième bit de d vaut 1, R2 dépend de R4, donc le résultat est faussé.

Ainsi, si dans mille-fautes.txt on a bien True, c’est que le ième bit de d valait 0, si on a False, le ième bit de d vallait 1.

On peut ainsi récupérer d et flag !

with open('mille-fautes.txt') as f:
    data = f.readlines()

data = data[1:]
data = data[1::2]
data = [line.strip().split()[-1] for line in data]
print(data)
d = "".join(["0" if bit == "True" else "1" for bit in data[::-1]])
print(int(d,2))

Flag :

FCSC{105242162543788743337252980031094540410286920689651093978118453037560701236944536116502819554965696785102170204949088553998761871348511118790932114247603701322088137236444818782787447039245943523349114909236634220118498903093045370684591251550088750568851495851919215974128144936137495423947422756508385773521}