Skip to content

PriMeD5

Description

Write Up: offpath
Créateur: randomdude999
Difficulté: Medium - Hard
Points: 100 Format du flag: crypto{flag}

Enoncé

La vérification de la primalité coûte cher, j'ai donc créé un service qui signe les nombres premiers, permettant à quiconque de vérifier rapidement si un nombre est premier.

Primality checking is expensive so I made a service that signs primes, allowing anyone to quickly check if a number is prime.

Solution détaillée

On a un code server et un socket de connexion.

from Crypto.PublicKey import RSA
from Crypto.Hash import MD5
from Crypto.Signature import pkcs1_15
from Crypto.Util.number import long_to_bytes, isPrime
import math
from utils import listener
# from secrets import N, E, D

FLAG = "crypto{??????????????????}"


key = RSA.construct((N, E, D))
sig_scheme = pkcs1_15.new(key)


class Challenge():
    def __init__(self):
        self.before_input = "Primality checking is expensive so I made a service that signs primes, allowing anyone to quickly check if a number is prime\n"

    def challenge(self, msg):
        if "option" not in msg:
            return {"error": "You must send an option to this server."}

        elif msg["option"] == "sign":
            p = int(msg["prime"])
            if p.bit_length() > 1024:
                return {"error": "The prime is too large."}
            if not isPrime(p):
                return {"error": "You must specify a prime."}

            hash = MD5.new(long_to_bytes(p))
            sig = sig_scheme.sign(hash)
            return {"signature": sig.hex()}

        elif msg["option"] == "check":
            p = int(msg["prime"])
            sig = bytes.fromhex(msg["signature"])
            hash = MD5.new(long_to_bytes(p))
            try:
                sig_scheme.verify(hash, sig)
            except ValueError:
                return {"error": "Invalid signature."}

            a = int(msg["a"])
            if a < 1:
                return {"error": "`a` value invalid"}
            if a >= p:
                return {"error": "`a` value too large"}
            g = math.gcd(a, p)
            flag_byte = FLAG[:g]
            return {"msg": f"Valid signature. First byte of flag: {flag_byte}"}

        else:
            return {"error": "Unknown option."}


listener.start_server(port=13392)

on nous fournit un service qui signe des nombres premiers à l'aide de RSA, permettant aux utilisateurs de vérifier rapidement la primalité d'un nombre en vérifiant la validité de la signature RSA. Le service propose deux options principales : signer un nombre premier et vérifier un nombre premier avec une condition supplémentaire impliquant une variable a.

Le code serveur fourni utilise le schéma cryptographique RSA pour signer et vérifier des nombres premiers. Voici un aperçu des fonctionnalités principales :

  1. Signature des Nombres Premiers (option sign):
    • Le serveur accepte un nombre premier ppp.
    • Il vérifie si ppp est un nombre premier et si sa longueur en bits est inférieure ou égale à 1024 bits.
    • Si ppp est valide, il génère un hash MD5 du nombre premier et le signe en utilisant RSA.
    • La signature est ensuite retournée à l'utilisateur.
  2. Vérification des Nombres Premiers (option check):
    • Le serveur accepte un nombre premier ppp, une signature et une variable aaa.
    • Il vérifie la signature RSA pour s'assurer qu'elle correspond au hash MD5 du nombre premier ppp.
    • Ensuite, il vérifie les conditions sur aaa :
      • aaa doit être supérieur à 1 et inférieur à ppp.
      • Si ces conditions sont remplies, le serveur retourne les premiers octets du drapeau (FLAG) en fonction du PGCD de aaa et ppp.

Solution

La solution de ce challenge repose sur une collision de hash MD5 pour deux nombres premiers. Voici comment on peut exploiter cela :

  1. Étape 1 : Obtenir une Signature pour un Premier
    • On envoie un premier nombre premier n1n1n1 au serveur pour obtenir une signature valide.
  2. Étape 2 : Utiliser une Collision MD5
    • On utilise un deuxième nombre n2n2n2 qui produit le même hash MD5 que n1n1n1. Comme le hash MD5 est identique, la signature de n1n1n1 est aussi valide pour n2n2n2.
  3. Étape 3 : Vérification et Extraction de l'Octet du Drapeau
    • En envoyant n2n2n2 avec la signature obtenue de n1n1n1 et différentes valeurs de aaa, on peut déterminer la bonne valeur de aaa qui retourne un message valide contenant les premiers octets du drapeau.

Voici le code de la solution fonctionnelle :

import json
import socket

# with prim collision md5 to get a prime with collision

def breakit():
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(("socket.cryptohack.org", 13392))

    # Recevoir le message d'accueil
    print(s.recv(1024).decode())

    # Envoyer un prime pour obtenir une signature de base
    n1 = 1042949915673747639548394979539773519387432406920217853474982925582324441002369106807062644005773384014539089496972340217284225886262811961269251256830829063
    n2 = 1042949915673747639548394979539773519387432406920217853474982925582324441002369106807076447498466965142113959008696894268189128104207757197289383619865780743

    payload = {"option": "sign", "prime": n1}
    s.send(json.dumps(payload).encode())
    response = s.recv(1024).decode()
    print(response)

    # Extraire la signature
    original_sig = json.loads(response)["signature"]

    for a in range(2, 100):  # Exemple : tester différentes valeurs de 'a' de 2 à 99
        # a = 71 or 77 gives the flag
        payload = {"option": "check", "prime": n2, "signature": original_sig, "a": a}
        s.send(json.dumps(payload).encode())
        result = s.recv(1024).decode()
        print(f"Result with a={a}: {result}")
    s.close()

breakit()