## Broken Box (Crypto, 300p)
We are given web service signing data for us, and we are told that it is somehow "broken".
Indeed, this service looks suspicious - for example, it sometimes give different signature for the same data.
We guessed that somewhere, somehow bit is flipped, because this is common trope with RSA on CTFs (so called RSA fault attacks). So we hacked simple script, to get more data:
```python    import socket
    s = socket.socket()    s.connect(('crypto.chal.csaw.io', 8002))
    import time    result = open('responses_' + str(int(time.time())), 'w')    print s.recv(9999)    while True:        s.send('2')        response = s.recv(9999)        print 'response', response        result.write(response + '\n')        s.send('yes')        s.recv(9999)        s.recv(9999)```
I promise that someday I will learn pwnlib and stop this socket madness. Nevertheless, this script gave us all the data we needed. It is attached as responses.txt file.
N is the same everywhere, so is was not very interesting. So we used this script, to extract only signatures:
```pythonimport argparse
parser = argparse.ArgumentParser(description='Merge signatures')parser.add_argument('signatures', nargs='+', help='signatures')
args = parser.parse_args()
signatures = set()for sigfile in args.signatures:    with open(sigfile, 'r') as sigdata:        sigdata = sigdata.read()        for line in sigdata.split('\n'):            if len(line) < 3:                continue            signatures.add(line.split(':')[1][:-3])
for sig in signatures:    print sig```
So what can we do with this information?
We know that `pow(sig,e,n) == data` (where sig is correct signature). RSA signature is computed as follows:
```pow(data, d, n) = sig```
When we are given invalid signature, we can assume that it is computed for good data, but some bit in `d` was flipped. In other words:* If k'th bit in d was 1 and, and turned to 0, then `d = d - 2^k`. So `pow(data, d') === pow(data, d - 2^k) === pow(data, d) / pow(data, 2^k)  (mod k)`* If k'th bit in d was 0 and, and turned to 1, then `d = d + 2^k`. So `pow(data, d') === pow(data, d + 2^k) === pow(data, d) * pow(data, 2^k)  (mod k)`
And we can just check all possibilites here (because there is only 1024 possible values of k!).
If `badsig == good_signature * pow(2, pow(2, k, n), n)`, than we know that k-th bit was 0 and turned to 1. Similarly we can determine that bit was 1 and turned to 0.
So every bitflip allows us to recover one bit in private key. We scripted it as follows:
```pythonimport argparse
parser = argparse.ArgumentParser(description='Solve')parser.add_argument('signatures', help='signatures')args = parser.parse_args()
ls = open(args.signatures, 'rb').read().split('\n')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 invmod(a, m):    g, x, y = egcd(a, m)    if g != 1:        raise Exception('modular inverse does not exist')    else:        return x % m    return pow(a, n-2, n)
mod = 123541066875660402939610015253549618669091153006444623444081648798612931426804474097249983622908131771026653322601466480170685973651622700515979315988600405563682920330486664845273165214922371767569956347920192959023447480720231820595590003596802409832935911909527048717061219934819426128006895966231433690709good = 22611972523744021864587913335128267927131958989869436027132656215690137049354670157725347739806657939727131080334523442608301044203758495053729468914668456929675330095440863887793747492226635650004672037267053895026217814873840360359669071507380945368109861731705751166864109227011643600107409036145468092331ls = filter(bool, ls)ls = map(int, ls)ls = list(set(ls))bad_sigs = ls
print 'precomputing +...'good_plus = [(good * pow(2, pow(2, bit, mod), mod)) % mod for bit in range(1024)]print 'precomputing -...'good_minus = [(good * invmod(pow(2, pow(2, bit, mod), mod), mod)) % mod for bit in range(1024)]
bits = {}for bad in bad_sigs:    for bit in range(1024):        # bad == g' == g^d' == g^(d+2**k) == good * g^2**k        if bad == good_plus[bit]:            bits[bit] = 0        # bad == g' == g^d' == g^(d-2**k) == good / g^2**k        if bad == good_minus[bit]:            bits[bit] = 1
import sysfor i in range(1024):    if i in bits:        sys.stdout.write(str(bits[i]))    else:        sys.stdout.write('?')print```
And after few seconds, we had completed flag:
```1010010010000001011011011001100100100110100111111010000111100101111000100111101101111111001001011001001101101010000100111010111110111100100100111110000011001010110101110001011010000010000100001000101001110101100110000101010001000110011101100001001110111001100110001000110100100100010010010001011100111010000101101100011100000111011010011010000010010011101001111110111101011001111011111111110100110001101100101001000110100111111011000010110001111111010000101111001101010001110101111010001011000010000100111010011011100101101111001000011101110111011001111111111101111101110100111010011100001111110000110110011101000000010111101110000100010000110110000000011100011110110111010110111110010010110000000010101000101011000011001101011000110001010111100101011101001100101110111010110001110000001000101100100011011011101110100010001100100001001100100111000000100000000000001010100101100011011101011010101111010100001100010011000110000001111011000000111011110111100111100110110101010011011011001110111011111100000101010010110111011101```
And finally, the flag is ours:
```In [192]: long_to_bytes(s)Out[192]: 'flag{br0k3n_h4rdw4r3_l34d5_70_b17_fl1pp1n6}'```