Description

Testez la robustesse de notre SecureSigner !

nc challenges.ecsc-teamfrance.fr 2001

Resolution

Connecting to the server we got:

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

Each time we connected to the server a new RSA key was generated.
The server returns the modulus and exponent, and the only thing we could do for one minute was to sign numbers or try to sign the provided challenge:

Please enter a number to sign (or anything else to stop): 1337
Signature: 21788765474516882817850325547933469427810645389313863258683864628880441544560123182182543843962589019547606383318778941236271941702735395506463646098302680207039259185657570657806899441356295033123534898568315445070942584694103819225400802024098435642495244429950254489276303169504526195316673007011101089171610099487254612457571981131594704875293934297856998128052099395994901546322951299979834356178118302875469763735850923308399895322778461497594208137718228886335354575523739104918185533709705406726845221772572944646565251292000769007211231108801657254237394626624929147740995739098617069254626938705206399305341
Please enter a number to sign (or anything else to stop): stop
Here is your challenge: 4186415493
Enter the signature of the challenge:

In order to provide a good signature, we needed to generate n signatures by providing n numbers to sign. WTF? Let’s explain this!
Signature: s = m^d (mod n), with s (signature), m (message to be signed), d (private exponent), n (public modulus)
Verify: s^e = m (mod n), with s (signature), e (public exponent), m (message that was signed), n (public modulus)
As we could compute signature for controlled numbers, we generated n primes numbers to be signed.
primes = primes(range(0, 15000))
For each prime we asked the challenge:
sign_prime1 = challenge(prime1)
When the provided challenge needed to be signed, we splited it in primes factors like:
prime1, prime2, primex, primen = prime_factors(challenge)
Then we calculated the signature as:
signature = (challenge(prime1) * challenge(prime2) * challenge(primex) * challenge(primen)) % N, with N the modulus given on connect

#!/usr/bin/python3

from pwn import *
from pprint import pprint
from gmpy2 import next_prime
import time

def compute_primes(n):
    global primes
    i = 0
    while i < n:
        i = int(next_prime(i))
        primes.append(i)

# https://stackoverflow.com/questions/16996217/prime-factorization-list/32608286#32608286
def prime_factors(x):
    factorlist=[]
    loop=2
    while loop<=x:
        if x%loop==0:
            x//=loop
            factorlist.append(loop)
        else:
            loop+=1
    return factorlist

def main():
    begin = time.time()
    r = remote('challenges.ecsc-teamfrance.fr', 2001)
    r.recvuntil('modulus n: ', drop=True)
    n = int(r.recvline(keepends=False).decode())
    r.recvuntil('exponent e: ', drop=True)
    e = int(r.recvuntil('\n', drop=True).decode())
    print('N:',n)
    print('e:',e)
    i = 0
    payload=''
    signs = {}
    print('Retrieving challenges for 50s...')
    while True:
        r.recvuntil('to stop): ', drop=True).decode()
        payload = str(primes[i])
        i+=1
        r.sendline(payload)
        r.recvuntil('Signature: ', drop=True)
        sign = r.recvline(keepends=False).decode()
        signs[int(payload)] = sign
        exectime = time.time()-begin
        if exectime > 55:
            print('Exec time:',str("{0:.2f}".format(exectime))+'s')
            break
    r.sendline('gimmetehchallenge!')
    r.recvuntil('Here is your challenge: ', drop=True)
    chall = r.recvline(keepends=False).decode()
    print('Challenge:',chall)
    challprimes = prime_factors(int(chall))
    signature = 1
    for num in challprimes:
        try:
            signature = signature * int(signs.get(int(num)))
        except:
            print('No solution found! Trying again...')
            r.close()
            main()
    signature = str(signature % n)
    print('sign:',signature)
    r.sendline(signature)
    r.interactive()

if __name__ == '__main__':
    primes = []
    compute_primes(15000)
    main()

Flag was ECSC{f861bb26b32459970ed27dcc804e52c136f48f0c}