BuckeyeCTF 2021 Pseudo

A la Une25/02/2022

Par Florian Picca

Un message est chiffré plusieurs fois en utilisant un PRNG basé sur le symbole de Legendre. On peut prédire la sortie en fournissant un nombre composite passant le test de primalité de Fermat. Le message original peut alors être récupéré statistiquement à l'aide de plusieurs messages chiffrés.

Détails

Catégorie : crypto
Points : 476
Résolutions : 15

Description

“Surely the Legendre symbol is a great random number generator, right?”

nc crypto.chall.pwnoh.io 13375

Code source :

#!/usr/bin/env python3
import random
import os

rand = random.SystemRandom()
FLAG = b"buckeye{?????????????????????}"


def is_prime(n, rounds=32):
    return all(pow(rand.randrange(2, n), n - 1, n) == 1 for _ in range(rounds))


class RNG:
    def __init__(self, p: int, a: int):
        self.p = p
        self.a = a

    def next_bit(self) -> int:
        ans = pow(self.a, (self.p - 1) // 2, self.p)
        self.a += 1
        return int(ans == 1)

    def next_byte(self) -> int:
        ans = 0
        for i in range(8):
            ans |= self.next_bit() << i
        return ans

    def next_bytes(self, n: int) -> bytes:
        return bytes(self.next_byte() for _ in range(n))


def main():
    p = int(input("Give me a prime number: "))

    if not (256 <= p.bit_length() <= 512):
        print("Wrong bit length")
        return

    if not is_prime(p):
        print("Fermat tells me your number isn't prime")
        return

    a = rand.randrange(2, p)
    rng = RNG(p, a)

    plaintext = b"Hello " + os.urandom(48).hex().encode()
    print("Have some ciphertexts:")

    for _ in range(32):
        s = rng.next_bytes(len(plaintext))
        c = bytes(a ^ b for a, b in zip(s, plaintext))
        print(c.hex())

    if plaintext == input("Guess the plaintext:\n").encode():
        print(f"Congrats! Here's the flag: {FLAG}")
    else:
        print("That's wrong")


main()

Comprendre le problème

Nous disposons d’un service qui nous demande un nombre premier et produit 32 chiffrements du même message à l’aide d’un One Time Pad généré par un RNG basé sur le symbole de Legendre :

Give me a prime number: 1262155989087425493470351370868590436767594351714484250533211127492586779277025113624463659
Have some ciphertexts:
e13125f96d4e803d2c113253efa485153f3f48d597981ca080630a6ecb3ff317e5d3dc96838920995837d4c875c4672f6967805cee9185b472c6b43110a431cd63c92db40d5cde640e0a5ee06c01b3bd7f91b32615733d0189244302994cf6380e8058fd6fe8
99cdbe2cf57556d4a76c41a943f213e00250f2a9024c64f46765327c4cfc9853f9c7eedd5557d30bf0b0c3f571fb120cc92d234da42459e3a33a85ef6a5290a0860ed815c08f9a016b932e2913155dac925259f332ca7fdf9ee4ce1557a85852698795c4560c
d7cf827572ba70811cd6b82c6e49a0037d75e046b880aa85e87a14e7ed528095c3d34ca82680dfbf0a6cb0544f22ccc6222a22a100664501c1feb814114785b261331c24a746e97ed1655512b9b0662680a2ded359a4200c0b41ab78374afc66ed449b45aae3
83955f7956c8c72958bf302884ba8a64c520825bfc0b29a3ef44116704aaeea7ef53c5195e09158578e74dcf0bf68b090fcb499eb9d9b8fc31e3edd93a2837b12abc98720eefee5f331cb7831075d5a55db7b2a7eeb4fc9b9f0963addc6e8a95ef44b2bb5104
5061cd02e2e362214c51d2568d7bf56fc63456aa03c39b15b36231b0654d85b610e94d5eddc6921dd0846228066c8f9451c2f0ca94783bf6a7823c7dd35e50c57f563c7a6ea8b40bc8c676264eef0f54d5e09164876ff2de4156f12f4c91f2411e63050b0eae
b2be480a4dca167b97817688c881b9482065e644d03f0517cb133482baf7cbf926c13410ce7359df49a47ed110a89b83377e8bbac648b26147dda4acdab89c693f76e154ec63e8ceaf98940736f4dd8e2aab085fa27ad904f4b912299f55aa8f06ff31be11df
b11a76cba07ffe0d01dcf78f6dd1038f92d11b180833609e55dbe9f7a4f2255fae9a2b6a1a8178e151079b7a097a1bc488223e18449247d6f74d05fbc0428305e17e445ead37c4062bc30ef0fcee5bf24c39ffe73f8a4b2e05d1af8ce3c35dc1c050f70e5579
d5658757d1866dbe388daa213aa7a193cad7bba903e54c0e8f72899a26b2989d4682d2f8489811ebc038922fc1c9a12ab5708ddce3e4f03f4bbe439a1917a37be73815bfa8c05745142dd802f2d22260fe06ba917860d5f657d71e48a3f6f6e08783d49d71b9
ff60839365a5d8989524feb138a9a3c6e9bc9b2a2c6c13038424f781cf7cf6eae9b83e8c477b90049e9a46b4165e6ca072c6fe12d39e587b7dfd70c962a4c6fd36e7c7534115acf1f3c7599a33f1bf7320fd98471c488601e8321c9a5d73f79a55955011f7f7
f414d29095121769d1d209b4ddc932050f0fd58aa84800309bb0c8b71a7660783af5bb12d3d8574a5bb654eb90c7bdc19bf7dd8ac74bd2b6a0dd7b4852bdc24abffaae4e87108195039d173d577f7ed1e0571a2aa59324ce4ba423519be63ed7e1bb3909e4f4
7a507e6048e0ad1c1effea3784bfe50f4a3d5dc6db67f67ece92ffc2deb4169337bda3c58738562d270cd02db7b0378c1682ab3c3a448341bee3e2f880d4f9dd72f66111d6b2dd922f43af9912ee1f133d5a0f275b2f9a6d5678c2630c06ec53826cb28fba26
db74be3f524f80be3069948988af1706fbf4d2a2a6dd2463e946840cfc1411408bffbde19e8c7753e52d14ae46e704babf21d1b6ad9eb150cdc42846fe030f7fb091d422b9a5dcfcb8404566d0c7b74c0fd768b3ec13c21b3557a4b8342d3ac4806d500a1e09
289cbd1aa4ac7ac2339f8155e62b20e2b5c46004a3fa7de31db4d55689a873498e43726d0f2482b19bdd02b7514484243367eee160eaae291daf4acadaeccb9899239af3cf8cedbbc79951aa558b0f58975df9511bcd0d74593a1ea8eb7368c02d7f83bab873
b815e85003f1097e12c973e5e235f9bf8997d26f57c1e82c348816b3c90b21b3ae9841f4752fd2acb03549c5d952db693aa27fcf3e0aa15d006677935c9a901ada36cc9cf9d1a1a8f9facb44ad5673b62a7ab6f44529d050a48d3bcec570ae5de3b88841f88e
9da481148f123c040589de10ca45e466b232d9744d2635cc32e3544c5f7c2501d69801094ee477123fffc70bc44d5a61de264bf9ce2430e5c016bd9c39dffae1d8c33dcebdd622d0b820ad080c8fb108aaac02886634447824940e5dceca2eb6fbb586f308bb
c6de449b4c461df311c54e5cb0a629ba9d3a59280f446203b26e1033d12fe31033b023c8280638c154c74da601d57a2d9cae3812c988279d74b1ad2d23509657ebd5dba9132285833c6fa52772b1f3bf14ff503f5049e1f839c14dee7a492e18cf2c3f0757f7
8f42b8fa6aa315c1ad2b862296254aa652097fb61974bb31254984af100fbb96c57e1554ee200722208a3d4c368baf5506cc087b260117679b24c0ac9eaa9b12c7b9037b7b28f2c4f960778a40c2387c3e6b159740d49e5e9ad71cb0479c54b979d371fc2a59
fb74dc03fbf2a94426863287dd17879e2d07ce14eac0213b025c96770cff9468d26394d1e6a19302e60b8545ae3d80434c887d02c7e4c7f28af2ff266383e5e6d0e7411c531a1eef7ff85e5ee4e581e8ae2f5bbcce4ef3a12984e5f3dcfb8bbd05f92f1b7c70
3f22f5dd480e55d56806cc8975aa9703b9cb5c2dbfa699e4424f4add5a0c8e0fb7f7de66fe5fa1e3e6b70b3d50bdb7c69382f9d0f1a079b3b29447ca5b2fd7a95e12a4cce1ce2da3b3fd593dd542e56592875afe043e070bae444a180f3619c991d0e76bdd47
2c09adbcf423e581f94279effb7520106ef47d1d4109af865e24143095b7a1c6d7d13582a3123026092316aeec24d231a8033d6e026b7ee7c04238eb532f383cff612c23eb65b92082931ecfb1d83324ca63383aacc535f884a97d0aae23cbb86deaceb857d2
fddf2beb4ed25a5d114e6887bfdf6f216b28aa353045d21cabfe1f69b691d3da40076721215d57067514b9e7ad153630f0ae85cdb2521d101f616ac7b8f047ec4d6e07a0ff5884884a5253fd70208acbd29df0947612b106769564b514eb76ba73654e83b1f5
980750b990cde9fce7a70fd02ff6d6f2562e273fe119c1f015cbd9bf4bbf6013389826ff65a32db02ce606cfff6dd4027c8013b6fabfe8c971f0cb3d0ebb82e17c6edec2f31b2c141e8a74235fe35e09eed91fd81674742286df4cd342d3b0593697445437a7
f829e117d8b24af86fe183c92373f72179fde14f0cb63dd05ee979a1c93b56ed8a84df6ccd465bce547fc102e329d552669c783faeaf6eef078b456c21e1ecacdfcad4d3c0477ae0d2edf109be0ac5718482126f98d23baf9c836d9314e19e1de090c6966d07
5742343a7e49a606500dbf013486032802b466c5ac4f9bfca427a4d5bc38d0826cefcccc96136de20d31f14f103f6c1a2982d37ade0bf6ccafdd247af92dadd6ab71412adac031b720e67a3903c598b79332973db69cf6b896ef38edfe812b9dfa10afac974e
c00100bd548eaa21106f72e68258ff4d05807a9f469609c09271045b60a2af76cfe08407459273e5fc82c4d889f091d6ab797474b10d0c71f777ac6ec4091ee5f8d8161a8789fd2c7c97ec03a595d93959afafa6bede2d72ff97618aa935398f17e8fc839eb5
01478268ad3dd104f7e87e7687f4a58435402ca190822ccbaf5accf7ab424b78ec7e478bc54ad7b41a8411692b6e0b676faf17d8c99e1337cbc61633a0ca774ff04f2fca3abba6c316d270cb78e1d41dfa469fa2ab4bbd2a4f9dca15a80b2f0a8415c3291479
6758eead793e3454efb7b7bbe2373271a344423916ede9afb9ee68b75a2c56154a1818f8d44ffa9e04317ad7018b10ec93a0c68ad81d4a29f5ce76d7acc08a5695307548caee171acbd322a9e24fdf28133e768ab09bddb8d049d75ee82e72a0b5d2fd9cdf6c
a99ec4be4d0bc6ff6824dee50efa36034c9e45e4e1d626660ab5e03f26b628c56fb8bb663f678c5980d14062f4c31254a01b8d2496522852a1144da72bbb3b9a3aead9e2e0dddde5d267d5031c67c9bfecdcad4e663ec7b276c14da3088d9158589800e7284a
7c21999af7c5d9e18dcfe9702bca789c404eeee2bfae9de1c7fcc54ab7abc3160fecb1ce418209db9f8cf8a15b8429cde5e89e82ef04a95d650d19fa5c093d3e38d28402ef99d068aeba9e16d5eef3cd1ff3cd7296c217ed3602e4618e98d50ddd8a867ce8e6
1abe3061ddb8cee92f4c1032f3b749a2cc2e36b1a69ce1c67268085358072be6d74bfc1d1689eba343cec02b877e5eee37a349533e7fe858ac3ab180e744e7219f4aa78cac1163088572e75a1ede5cce79178f2f233ad80d84590642da9c7e7daa281add677c
016324c258c0dc31d24ecb097e4e057f95a2a4f8e0035b8f6109319e1e795a25238bc19286230e5ec2e6c89dc2a9767fafd0e9bae553ba829ac253f97776d3ccdb0d6815a895bfca6789ed5667d6ea48343254f9b46b9074ba334cfd0186722da780c7597f62
ad909fea25393e6d82b946a4274da9e0ebf997c19bf77a26bd2b1e948accf4658b84823c72ce3119f0b5c9285ba094e6a28c67cfea033d0d9fcb688f02b31ac5af266b1dd0009c9efdb3804da967a19b5db7a236a6128c7e70a0ab46e3ac843a07a4f90c84c4
Guess the plaintext:
AAAAAAAAAAAAAAAAA
That's wrong

Le but est de récupérer le message original.

On peut essayer de récupérer la graine utilisée par le RNG, en connaissant une partie du message original. Nous savons qu’il commence toujours par “Hello”, ce qui nous donnerait 6*8 = 48 bits consécutifs pour chaque texte chiffré.

Après avoir passé un certain temps à lire des articles comme celui-ci, il semble que la récupération de la graine de ce RNG soit un problème difficile.

L’autre chose qui a attiré notre attention est la fonction is_prime. Au lieu d’utiliser une implémentation bien connue, l’auteur du challenge a décidé d’implémenter un simple test de primalité de Fermat.

Le symbole de Legendre pour le RNG est calculé comme suit :

def next_bit(self) -> int:
        ans = pow(self.a, (self.p - 1) // 2, self.p)
        self.a += 1
        return int(ans == 1)

Cela suppose que p est premier. Si ce n’est pas le cas, la fonction next_bit donnera 0 la plupart du temps, parce que pow(a, (p-1)//2, p) != 1 pour la majorité des valeurs a.

Nous devons trouver un moyen de tromper le test de primalité et fournir un nombre suffisamment grand qui n’est pas premier, afin de pouvoir récupérer le texte en clair en prenant le bit le plus commun à chaque position pour les 32 messages chiffrés.

Résoudre le problème

Il existe des nombres composites qui peuvent satisfaire au test de primalité de Fermat, comme les nombres de Carmichael.

Notre objectif est de trouver un nombre de Carmichael qui passe le test pour plusieurs bases. En cherchant en ligne, nous avons rapidement trouvé un ancien article traitant cette question. L’auteur a même donné un exemple de nombre :

>>> p = 13618186946913248902029336585225618237728639469119284611739065110030838492720163
>>> is_prime(p)
True

Voyons à quoi ressemble la sortie du RNG lorsque nous lui donnons ce nombre premier :

>>> r = RNG(p, 345678918765442567890) # some random number a
>>> r.next_bytes(30)
b'\x00\x00\x00\x00\x04@\x00\x08\x00\x00\x00\x00\x08\x00\x08\x00\x08\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00@\x80'
>>> r.next_bytes(30)
b'\x00\x00\x10\x00\x00\x00\x00\x00\x10\x00 \x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x08\x00\x04'
>>> r.next_bytes(30)
b'\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00 @\x00\x00\x00\x18\x00\x00\x00'
>>> r.next_bytes(30)
b'\x00\x00\x00\x80\x10\x00\x00@\x00\x02@\x08\x80\x00\x00\x00\x82\x00\x02\x08\x00\x00\x00\x00\x80\x00\x00\x00\x00\x00'

Le RNG produit 0 la plupart du temps comme prévu. Récupérer le message original peut être fait facilement en utilisant quelques messages chiffrés.

Implémentation de la solution

Le script complet de résolution est donné ci-dessous :

from pwn import *

def btos(b):
    from Crypto.Util.number import long_to_bytes
    n = int(b, 2)
    return long_to_bytes(n)

def stob(s):
    from Crypto.Util.number import bytes_to_long
    r = bin(bytes_to_long(s))[2:].rstrip("L")
    while len(r) % 8 != 0:
        r = "0" + r
    return r

conn = remote("crypto.chall.pwnoh.io", 13375)
conn.recvuntil(b"Give me a prime number:")
conn.sendline(b"13618186946913248902029336585225618237728639469119284611739065110030838492720163")
conn.recvline()
datas = []
for i in range(32):
    raw = bytes.fromhex(conn.recvline().strip().decode())
    b = stob(raw).ljust(816, "0")
    datas.append(b)

from collections import Counter

flag_bin = []
for i in range(816):
    ctr = Counter()
    for e in datas:
        ctr.update(e[i])
    flag_bin.append(ctr.most_common(1)[0][0])

res = btos(''.join(flag_bin))

conn.recvline()
conn.sendline(res)
conn.interactive()

Flag : buckeye{f3rm4t_l13d_t0_m3_0mg}