HackademINT

Club de cybersécurité de Telecom SudParis


CRYPTO.m04r s1gz

Auteur : Headorteil

----------------------------------

L’énoncé

m04r_s1gz

Testez la robustesse de notre SecureSigner !

nc challenges.ecsc-teamfrance.fr 2001

TL;DR

On nous donne l’accès à un netcat ainsi qu’à un code python (qui n’est pas indispensable pour résoudre le challenge étant donné que je ne l’ai pas lu). En ouvrant le netcat, on voit qu’on peut signer en RSA tous les entiers qu’on veut puis on nous demande d’en signer un, le tout en 60 secondes. Le nombre à signer n’est pas excessivement grand et est souvent factorisable, on va donc signer un maximum de nombres premiers et espérer que les facteurs du nombre à signer soient dans la liste des nombres premiers qu’on a eu le temps de signer.

Analyse

Le code

Je mets le code fourni par l’énoncé ici mais comme je l’ai dit précedemment, il n’est pas indispensable pour flag.

#!/usr/bin/python3 -u
from Crypto.PublicKey import RSA
import secrets
import signal
import sys


class SecureSigner():
    def __init__(self):
        self.private_key = RSA.generate(2048)
        self.e, self.n = self.private_key.e, self.private_key.n

    def sign(self, message):
        return self.private_key.sign(m, None)

    def verify(self, message, signature):
        return self.private_key.verify(message, (signature,))


if __name__ == '__main__':
    s = SecureSigner()

    print("Can you beat us and forge a signature in less than 60 seconds?")
    signal.alarm(60)

    print("Here are your parameters:\n - modulus n: {:d}\n - public exponent e: {:d}".format(s.n, s.e))

    while True:
        message = input("Please enter a number to sign (or anything else to stop): ")
        try:
            m = int(message, 10)
        except ValueError:
            break
        signature = s.sign(m)
        print("Signature: {:d}".format(signature[0]))
    
    challenge = secrets.randbelow(2**32)
    print("Here is your challenge: {:d}".format(challenge))
    
    signature = input("Enter the signature of the challenge: ")
    try:
        sig = int(signature, 10)
    except ValueError:
        print("[-] Wrong signature format!")
        sys.exit(-1)
    
    if s.verify(challenge, sig):
        with open("flag", "rb") as f:
            flag = f.read()
            signal.alarm(0)
            print("[+] Here is your flag, fellow signer: {:s}".format(flag.decode()))
    else:
        print("[-] Try again :(")
        sys.exit(-1)

Tatonnons

On ouvre donc le netcat et on regarde ce qu’il nous renvoie.

Can you beat us and forge a signature in less than 60 seconds?
Here are your parameters:
 - modulus n: 27766589501106401431014435787428427816624801484482536912087313994563030561852062054398940233357062811197690979328852429350818737631403729030517874130262602569715227608437328954204255548726288270394698278790931451732642707841066590237549928406895658018298775929288895806051216237807676796509096818661280328945122320091105058878054370520765214918078403254006078042295769582020686428127274037068433030117323976083001865791182819883833858339871194251644180184471404748291252399399140056765465989940641557685932752505932898209965275560108768530688991544742290570750669526605817766574991198515614112681704396654009518214341
 - public exponent e: 65537
Please enter a number to sign (or anything else to stop): 

En voyant le n et le e fournis, on se doute qu’on a affaire à du RSA. On nous demande d’entrer un nombre à signer et on nous indique qu’on devra pouvoir signer un entier après 60 secondes.

On nous renvoie bien la signature en décimal de nos inputs.

Please enter a number to sign (or anything else to stop): 2
Signature: 22373823993238119408658743641013260749890921940836757089105994997174651913702922702811785140043155875618594042261080651877816475042037299632871143747702324107306842426285528098598984316365136052810379946050885460632439159080444819272380077086966789888239808230011884486402516662074673208458789668673830143596872217742674376163092573690797734029598963212442627918979892605486456392990921907978287421228434114717769301403533494503271166390003257016592856582596172077400919151326582256285288418173078079359078266344468162334998212026236015941080133514169669805325215524041190852447646000864464760404786852782782780687782
Please enter a number to sign (or anything else to stop):

En entrant autre chose qu’un nombre, on nous donne le nombre à signer.

Please enter a number to sign (or anything else to stop): a
Here is your challenge: 915153094

Solution

Méthode

Signer un nombre en RSA revient à donner le module de sa dième puissance par n, d étant l’inverse modulaire de e par rapport à l’indicatrice d’euler de n. Si vous n’avez rien compris à ce qui précède, aucun soucis, l’attaque que j’ai implémenté n’utilise que des mathématiques relativement basiques, je n’utilise même pas le e fourni.

On ne cherchera donc pas ici à retrouver d pour ensuite passer notre nombre à signer à la puissance d.

Etant donné qu’on nous donne 60 secondes pour solve, on peut raisonnablement supposer qu’on doit utiliser au maximum le temps qui nous est alloué pour signer un maximum de nombres.

On ne va cependant pas gaspiller notre temps en signant n’importe quels nombres en espérant qu’on nous demandera de signer un nombre qu’on a déjà signé, ca serait bien trop long au vu de la taille des nombres qu’on nous demande de signer.

On sait que tout nombre entier est factorisable en produit de nombres premiers, on va donc signer un maximum de nombres premiers puis factoriser le nombre à signer en espérant qu’on aura eu le temps de signer tous les facteur premier du nombre à signer, ça réduit grandement le champ des possibles.

Si on a eu le temps de signer les facteur premier du nombre à signer on n’a plus qu’à renvoyer le produit des signatures des facteurs du nombre à signer puisque le produit des puissances est égal à la puissance du produit.

L’implémentation

#! /bin/python


import pwn
import re
from time import time
import subprocess
from Crypto.Util.number import isPrime


def findprimes(nb_primes):
    primes = []
    for i in range(nb_primes):
        if isPrime(i):
            primes.append(i)
    return primes


def solve(primes):
    t = time()
    r = pwn.remote('challenges.ecsc-teamfrance.fr', 2001)

    txt = r.recv().decode()

    n = int(re.findall(r'modulus n: (.+)\n', txt)[0])
    e = int(re.findall(r'exponent e: (.+)\n', txt)[0])

    signprimes = []

    with pwn.log.progress('Sign all primes') as p:
        for i in primes:
            p.status(str(i))
            r.sendline(str(i))
            txt = r.recv().decode()
            signprimes.append(int(re.findall(r'Signature: (.+)\n', txt)[0]))
            #On signe un maximum de nombres premiers en 55 secondes
            if time() - t > 55:
                break

    r.sendline("a")

    txt = r.recv().decode()
    x = re.findall(r'Here is your challenge: (.+)\n', txt)[0]

    #Pour trouver les facteurs de x, j'utilise yafu
    output = subprocess.check_output("yafu factor\(" + x + "\)", shell=True).decode()
    factors = [ int(i) for i in re.findall(r' = (.+)\n', output)[1:-1] ]

    if factors[-1] > primes[-1] or primes.index(factors[-1]) > len(signprimes):
        pwn.log.info("Biggest factor is {} and biggest signed prime is {}".format(factors[-1], primes[len(signprimes)]))
        r.close()

	#Si on n'a pas pu signer assez de nombres, on relance un nouveau netcat
        solve(primes)
        return

    signed = 1

    for i in factors:
        signed *= signprimes[primes.index(i)]

    r.sendline(str(signed%n))

    print(r.recv().decode())

    r.close()

    return


if __name__ == "__main__":
    #En 55 secondes, j'arrive au maximum à signer 45000 nombres, je génère donc 50000 nombres premiers pour être large
    solve(findprimes(50000))

Le flag

En exécutant notre code on récupère l’output suivant :

[+] Opening connection to challenges.ecsc-teamfrance.fr on port 2001: Done
[+] Sign all primes: Done
[*] Biggest factor is 12929753 and biggest signed prime is 22229
[*] Closed connection to challenges.ecsc-teamfrance.fr port 2001
[+] Opening connection to challenges.ecsc-teamfrance.fr on port 2001: Done
[+] Sign all primes: Done
[+] Here is your flag, fellow signer: ECSC{f861bb26b32459970ed27dcc804e52c136f48f0c}


[*] Closed connection to challenges.ecsc-teamfrance.fr port 2001

Ici, on a réussi à trouver le flag au 2eme essai.