**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 ) $$

- $$0<=x<=\varphi(n)$$
- $$m^x = c\ (\ mod\ 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)

## No comments:

## Post a Comment