Description

nc cry1.chal.ctf.westerns.tokyo 37992


============================= About ===============================
You are very good ESPer, so that you can change any local variable
value to 2048 bit random integer.

You should specify the ESP string as the line number and variables'
name to change separated by colon.

For example, if the source code is below and your input is "2:x",
the line 2 works the same as "x = rand(2 ** 2048); puts x". So the
output is random number.
+---+-------------------------------------------------------------------------+
| 1| x = 3 |
| 2| puts x |
+---+-------------------------------------------------------------------------+
Encryption Source code is here.
+---+-------------------------------------------------------------------------+
| 1| n, e = read_publickey(ARGV[0]) |
| 2| print "Message m: " |
| 3| STDOUT.flush |
| 4| m = STDIN.gets.to_i |
| 5| c = encrypt(m, e, n) |
| 6| puts "Encrypted: #{c}" |
| 7| STDOUT.flush |
+---+-------------------------------------------------------------------------+

Decryption Source code is here
+---+-------------------------------------------------------------------------+
| 1| p, q, dp, dq, qinvp = read_privkey(ARGV[0]) |
| 2| print "Encrypted Message c: " |
| 3| STDOUT.flush |
| 4| c = STDIN.gets.to_i |
| 5| m1 = decrypt(c, dp, p) |
| 6| m2 = decrypt(c, dq, q) |
| 7| m = merge(m1, m2, p, q, qinvp) |
| 8| puts "Decrypted: #{m}" |
| 9| STDOUT.flush |
+---+-------------------------------------------------------------------------+


Resolution

Après un défi SHA classique pour empêcher le bruteforce du challenge (la résolution du problème se fait en 5/6 secondes), le programme génère une clé privée suffisamment forte qui change donc à chaque fois. Ensuite on a 4 envois possibles avant que le programme nous retourne le flag (avec un padding aléatoire) chiffré avec la clé privée générée (il faut donc à ce moment là disposer de la clé privée pour être capable de l’obtenir).
A chaque envoi, on peut demander au programme soit de chiffrer un message, soit de déchiffrer un message. Avec une possibilité comme indiquée dans l’énoncé de rendre une variable aléatoire parmi toutes les variables utilisées.
A première vue, on se demande en quoi cela va pouvoir nous être utile. Mais regardons de plus près les équations de chiffrement/déchiffrement :

c = m^e [N]

donc c – m^e est un multiple de N.
Or on peut demander au programme de chiffrer ce qu’on veut, par exemple 2 et 3, qui sont des nombres suffisamment petits pour que leur puissance e = 65537 (e ne varie pas à chaque lancement du programme), soit représentable avec assez peu de chiffres (de l’ordre d’une dizaine de milliers).
En demandant le chiffrement de 2 et 3, on obtient donc c1 – 2^65537 et c2 – 3^65537 qui sont des multiples de N. Avec un peu de chance, on a donc :

pgcd(c1 - 2^65537, c2 - 3^65537) = N

On dispose maintenant de N, à partir de deux opérations. Si on trouve p ou q, c’est gagné !

Observons maintenant les équations de déchiffrement, avec la méthode des restes chinois (http://www.di-mgt.com.au/crt_rsa.html) :

dp = e^-1 [p-1]
dq = e^-1 [q-1]
qinvp = q^-1 [p]
m1 = c^dp [p]
m2 = c^dq [q]
h = qinvp (m1-m2) [p]
m = m2 + hq

On peut voir que si on déchiffre un message c une première fois et qu’on déchiffre le même message avec qinv différent, on obtient m = m2 + h1*q et m = m2 + h2*q et donc en soustrayant les clairs obtenus :

0 = (h1-h2)*q

On obtient donc un multiple de q. Or on sait que N est également un multiple de q, donc si on a bien des qinv différents, on a de fortes chances d’obtenir :

pgcd(N, (h1-h2)*q) = q

On a donc 2 opérations supplémentaires, la dernière en demandant un qinvp aléatoire. On arrive à 4 opérations, le programme nous renvoie le flag chiffré et quitte. Mais c’est suffisant pour terminer !
On a N et q, donc p, et on peut tout reconstruire pour déchiffrer le flag !

import sys
import socket
import string
import re, time
import base64,binascii,hashlib
from pwn import *
# coding:utf-8
from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
import os,binascii

HOST = "cry1.chal.ctf.westerns.tokyo"
PORT = 37992

myreg=re.compile(r'hashlib.(\w*)\(str\(number\)\)\.hexdigest\(\)\.startswith\(\'(\w*)\'\) == true and (\d*) <= number <= (\d*)')


def test_connexion(HOST, PORT):
    print "-=-=-= Starting -=-=-=-"
    sh = remote(HOST, PORT)
    datas = sh.recvuntil('\n')
    print datas
    datas = sh.recvuntil('\n')
    print datas
    res=myreg.findall(datas)
    print res
    found_value=calculate(algo=res[0][0],startvalue=res[0][1],min=int(res[0][2]),max=int(res[0][3]))
    sh.sendline(str(found_value))
    datas = sh.recvuntil('Your choice>')
    print datas
    ######
    M = "4"*129
    m = message_to_int(M)
    encrypted1 = enc_with_choice(sh, '', message=M)
    encrypted2 = enc_with_choice(sh, '', message="\x02")
    encrypted3 = enc_with_choice(sh, '', message="\x03")
    decrypted1 = m
    decrypted2 = dec_with_choice(sh, '5:qinvp', message=str(encrypted1))
   
    kp1 = (pow(2,65537)-encrypted2)
    kp2 = (pow(3,65537)-encrypted3)
    N = gcd(kp1,kp2)

    print(N)

    q = gcd(decrypted1-decrypted2,N)
    if q<0:
        q *= -1
    p = N/q

    print("P="+str(p))
    print("Q="+str(q))
    print(N==p*q)

    sh.interactive()


def enc_with_choice(sh,my_esp,message):
    sh.sendline('1')
    datas = sh.recvuntil('string:')
    print datas
    sh.sendline(my_esp)
    print '>',my_esp
    datas = sh.recvuntil('m:')
    print datas
    sh.sendline(str(message_to_int(message)))
    print '>',message_to_int(message)
    datas = sh.recvuntil('Encrypted:')
    print datas
    datas = sh.recvuntil('\n')
    encrypted = int(datas)
    print encrypted
    return encrypted

def dec_with_choice(sh,my_esp,message):
    sh.sendline('2')
    datas = sh.recvuntil('string:')
    print datas
    sh.sendline(my_esp)
    datas = sh.recvuntil('c:')
    print datas
    sh.sendline(str(message))
    datas = sh.recvuntil('Decrypted:')
    print datas
    datas = sh.recvuntil('\n')
    decrypted = int(datas)
    print decrypted
    print "Decrypted message is :",int_to_message(decrypted)
    return decrypted

def message_to_int(message):
    return int(binascii.hexlify(message),16)
def int_to_message(value):
    return binascii.unhexlify(hex(value)[2:].replace('L',''))


def calculate(algo='sha1',min=0,max=0,startvalue='00000'):
    value = min
    while value < max:
        if algo=='sha1':
            if hashlib.sha1(str(value)).hexdigest().startswith(startvalue):
                print "Found : ",value,' : ',hashlib.sha1(str(value)).hexdigest()
                return value

        if algo == 'md5':
            if hashlib.md5(str(value)).hexdigest().startswith(startvalue):
                print "Found : ", value, ' : ', hashlib.md5(str(value)).hexdigest()
                return value

        else :
            value+=1


if __name__ == '__main__':
    test_connexion(HOST, PORT)


c = 20942956699330319872158409337924190768213456440565922005083726149156131319192722266288327376512373093552743741537930146382601041542929377509300469883924139257384027475699337072356975755181363855026874101098018831259509230510614253551911419783143187866166090002439803837394314492529167063370411308830963711887986514763550997451779965339957895690182830706313809461304944934907671556696483912876601762427437849527918472117274401661397336225404466434179028166762919079103353579947811270492811254517930142583940861572063335290025091077596774000201919743055015057170449334693390974291566063266101608180982168026191439705859
p = 152337050375069076443241765930164873212779468869178184814666105307945151519389973978733969613680584364143135979268598609761681856569421887186735180153106187906765810044628863040395244931778690492117035090747931829041031964467601572873479004054439845004053698991546208889514048762758247627755719714630055191923
q = 148841929038545009318690416092183995236183322684180431048606510674672413170977265381738608407239792487225483072439344038384029523766183714339920751585959898774873888725434712835014635204105183878500741908493814854395896721022995104642305763922731222897928475518252168472146918176790825627840600871705120989089

e = 65537
N = p*q
phi = (p-1)*(q-1)


def egcd(a, b):
   if a == 0:
       return (b, 0, 1)
   else:
       g, y, x = egcd(b % a, a)
       return (g, x - (b // a) * y, y)

def modinv(a, m):
   g, x, y = egcd(a, m)
   if g != 1:
       raise Exception('modular inverse does not exist')
   else:
       return x % m

d = modinv(e,phi)

m = pow(c,d,N)

import binascii
print(binascii.unhexlify(hex(m).replace('0x','').replace('L','')))

TWCTF{I_don't_Lik3_ESPer_problems!}