ebCTF 2013: crypto400

In this challenge we have an RSA signing service:

input: public_key (e,n) , data
It calculates the fingerprint of the provided public key sha1(public_key)
And then searches in ( fingerprint, d ) pair database for it.
Then it calculates $$m = sha1(current\_timestamp,data)$$ and $$signature = m^d (mod\ n)$$
output: current_timestamp, signature


Our task is to sign data with timestamp from 21.10.2005.
Signing service has a bug in searching procedure: only two bytes of fingerprint are compared. So it was possible to create public key with chosen n and bruteforce e with the same fingerprint which is used in real public_key.
After sending fake private key we are receiving: $$c=m^d mod\ n_{fake}$$ For given m,c,n when n is small we can bruteforce all x which satisfy conditions:

• $$0<=x<=\varphi(n)$$
• $$m^x = c\ ( mod\ n ) $$

We have also $$a^b\ mod\ n = a^{b\ mod\ \varphi(n)} mod\ n$$ $$b\ mod\ p\ =\ b\ mod\ \varphi(n)\ mod\ p\ if\ p|\varphi(n)$$ So when we choose small n and $$p|\varphi(n)$$ and we send it to the service, we will receive $$c = m^d\ mod\ n$$ where m is known. If for all x such that:

• $$0<=x<=\varphi(n)$$
• $$m^x = c\ (\ mod\ n )$$

$$y = x\ mod\ p$$ is the same value then we are sure that $$y = d\ mod\ p$$ When we have a lot of pairs $$(y_i,p_i)$$ and $$p_i$$ are pairwise coprime and $$\prod_i p_i>n_{real} $$ then we can calculate d using chinese remainder theorem. In my solution I used n and p values which satisfy $$n=2*p+1$$ and n,p are primes. Then $$\varphi(n)= n-1$$and$$p |\varphi(n)$$

#!/usr/bin/env python

import sys
import hashlib
import os
import socket
import time
import base64
import random
import datetime

from crt import ChineseRemainder

hostport = ('54.217.0.233', 2407)

# interpret string as little-endian long integer
def bin2int(s):
    return int(s[::-1].encode('hex'), 16)

# store integer as little-endian binary string of given length
def int2bin(i,n):
    return ("%x" % i).rjust(n*2,'0').decode('hex')[::-1]

def solve_dlp(x,y,n,p):
    solutions = set()
    for i in xrange(0,n):
        if pow(x,i,n) == y:
            solutions.add(i % p)
    return solutions

# read public key from file
with open("./pubkey0") as f:
    n = bin2int(f.read(1024 / 8))
    e = bin2int(f.read(32 / 8))


pubkeystring = int2bin(n,1024/8) + int2bin(e,32/8)
fingerprint=hashlib.sha1(pubkeystring).digest()


SIEVE_LEN = 1000000

sieve = [0]*SIEVE_LEN

for i in xrange(2,SIEVE_LEN):
    if sieve[i] == 0:
        j=2*i
        while j < SIEVE_LEN:
            sieve[j] = 1
            j+=i

primes_product = 1
crt = []
last_index = 100000
while primes_product < n:
    while sieve[last_index] == 1 or sieve[last_index*2+1] == 1:
        last_index+=1

    fake_n = 2*last_index+1
    prime = last_index 
    last_index+=1
    
    print 'using primes: ',fake_n,prime

    fake_e = 0
    while 1:
        fake_pubkeystring = int2bin(fake_n,1024/8) + int2bin(fake_e,32/8)
        fake_fingerprint=hashlib.sha1(fake_pubkeystring).digest()
        if fake_fingerprint[:2] == fingerprint[:2]:
            break
        fake_e += 1
    
    s = socket.create_connection(hostport)
    
    data = str(random.randint(0,1000))
    
    s.send(fake_pubkeystring + int2bin(len(data),32/8) + data)

    responsestring = ''
    while True:
        tmp = s.recv(1024)
        if not tmp: break
        responsestring += tmp


    ts = bin2int(responsestring[:4])
    sig = bin2int(responsestring[4:])
    if sig==0:
        continue

    m = bin2int(hashlib.sha1(int2bin(ts, 32/8) + data).digest() )
    m %= fake_n
    print 'received sig: ',sig
    print 'm: ',m
    x = solve_dlp(m,sig,fake_n,prime)
    if len(x)==1:
        x=x.pop()
        print 'solved: ',x
        crt.append( (x, prime) )
        primes_product *= prime

d = ChineseRemainder(crt)[0]
print 'private_key: ',d

ts = int(( datetime.datetime(2015, 10, 21) - datetime.datetime(1970, 1, 1)).total_seconds())
m = bin2int(hashlib.sha1(int2bin(ts, 32/8) + data).digest() )
sig = pow(m,d,n)
responsestring = int2bin(ts, 4) + int2bin(sig, 1024/8)
print base64.b64encode(pubkeystring + responsestring + data)