Rotating Secret Assembler

3 minutos de lectura

Se nos proporciona un socket al que conectarnos. Al realizar la conexión se muestra el código fuente usado para cifrar la flag:

$ nc puzzler7.imaginaryctf.org 3000
================================================================================

#!/usr/bin/env python3

from Crypto.Util.number import *

class Rotator:
    QUEUE_LENGTH = 10

    def __init__(self):
        self.e = 65537
        self.m = bytes_to_long(open('flag.txt', 'rb').read())
        self.queue = [getPrime(512) for i in range(self.QUEUE_LENGTH)]  

    def get_new_primes(self):
        ret = self.queue[-2:]
        self.queue.pop()
        while(len(self.queue) < self.QUEUE_LENGTH):
            self.queue = [getPrime(512)] + self.queue
        return tuple(ret)

    def enc_flag(self):
        p, q = self.get_new_primes()
        n = p*q
        print(f"Public key: {(n, self.e)}")
        print(f"Your encrypted flag: {pow(self.m, self.e, n)}")

rot = Rotator()

print('='*80)
print(open(__file__).read())
print('='*80)

while True:
    inp = input("Would you like an encrypted flag (y/n)? ")
    if 'y' in inp.lower():
        rot.enc_flag()
        print()
    else:
        break

================================================================================  
Would you like an encrypted flag (y/n)? ^C

El criptosistema utilizado es RSA, pero la implementación es errónea. La manera de obtener los dos números primos $p$ y $q$ es usando una lista de 10 número primos. El problema es que utiliza los primos #9 y #10, elimina el último primo de la lista y añade otro al principio.

Por tanto, si ciframos la flag otra vez, los números primos #9 y #10 son los antiguos #8 y #9. Entonces, los dos módulos $n_1$ y $n_2$ tienen un factor primo en común, por lo que lo podemos calcular mediante el Máximo Común Divisor (Greatest Common Divisor, GCD):

$ nc puzzler7.imaginaryctf.org 3000
================================================================================
...
================================================================================
Would you like an encrypted flag (y/n)? y
Public key: (96703909946448187810080059928860289847334838421345682013476154093401516765135280790240748288018738898773300957888698818329609720254183468520955600410824182661260651475354846583794678409061342257380126990919258631778574644009046899146628324485287628710454832937953442848153274308105256237934059406671514368669, 65537)  
Your encrypted flag: 59178952773280983701929213365655160414345333604813929581573406427317973306869828507777582501496996849288063597376183280909545034065032431890181707370065107503683394760116243008932175061294230315842811989143511271380367848125619781509436529057342192685755008501371415788491821709728063365374407957399759308403

Would you like an encrypted flag (y/n)? y
Public key: (67521112267846681759399501276451660075611114138321414686289669627378193951857898222612601048796706669289048949898237532495727093603797701087528981834411985551974275328675230434122883600996218065032476293749234911283805641424141314863236316629221906963122154907092242556815579427166899630607780645315510611627, 65537)
Your encrypted flag: 17472971162377108034479702090513254186993682961319105294905663470809265628036722391463644486154580853360833837492388701203988503690522100670413712708369683451190130374033333827066594624190360243317258296768874842826927768445323829689267057977209895049163051260509473831629782589375685789931957272431150099185

Would you like an encrypted flag (y/n)? ^C

$ python3 -q
>>> import math
>>> math.gcd(
...     96703909946448187810080059928860289847334838421345682013476154093401516765135280790240748288018738898773300957888698818329609720254183468520955600410824182661260651475354846583794678409061342257380126990919258631778574644009046899146628324485287628710454832937953442848153274308105256237934059406671514368669,  
...     67521112267846681759399501276451660075611114138321414686289669627378193951857898222612601048796706669289048949898237532495727093603797701087528981834411985551974275328675230434122883600996218065032476293749234911283805641424141314863236316629221906963122154907092242556815579427166899630607780645315510611627
... )
9363717537480322078371747028261742962030931062610359488017319347844327325330269179209776316998302502579512167515356510999614768902498349936434046242471613

Y ahí está. Ahora que tenemos un número primo, podemos encontrar el otro usando la división entera sobre $n_1$ y descifrar el cifrado RSA de la manerahabitual. Este es el script en Python que soluciona el reto:

#!/usr/bin/env python3

from math import gcd
from pwn import remote


def main():
    r = remote('puzzler7.imaginaryctf.org', 3000)

    r.sendlineafter(b'Would you like an encrypted flag (y/n)? ', b'y')  
    r.recvuntil(b'Public key: ')
    n1, e = eval(r.recvline().decode())
    r.recvuntil(b'Your encrypted flag: ')
    c = int(r.recvline().decode())

    r.sendlineafter(b'Would you like an encrypted flag (y/n)? ', b'y')
    r.recvuntil(b'Public key: ')
    n2, _ = eval(r.recvline().decode())
    r.close()

    p = gcd(n1, n2)
    q = n1 // p

    phi_n = (p - 1) * (q - 1)
    d = pow(e, -1, phi_n)
    m = pow(c, d, n1)

    print(bytes.fromhex(hex(m)[2:]).decode())


if __name__ == '__main__':
    main()

Y obtenemos la flag:

$ python3 solve.py
[+] Opening connection to puzzler7.imaginaryctf.org on port 3000: Done  
[*] Closed connection to puzzler7.imaginaryctf.org port 3000
ictf{why_would_I_throw_away_perfectly_good_primes?}

El script completo se puede encontrar aquí: solve.py.