## Thursday, August 15, 2013

### 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:
return solutions

# read public key from file
with open("./pubkey0") as f:

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 '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)