From d55363f9833e875a5f2bd52964887e527f013851 Mon Sep 17 00:00:00 2001 From: Michael Lang Date: Wed, 15 Jan 2020 14:07:36 +0100 Subject: [PATCH] add writeup for asis19/close-primes --- writeups/mla/asis19.md | 145 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 145 insertions(+) create mode 100644 writeups/mla/asis19.md diff --git a/writeups/mla/asis19.md b/writeups/mla/asis19.md new file mode 100644 index 0000000..cffe87c --- /dev/null +++ b/writeups/mla/asis19.md @@ -0,0 +1,145 @@ +# ASIS Cyber Security Contest '19 + +## Close Primes + + The people who can do you the most damage are the ones who are closest to you. + "close" means q = next_prime(p) + nc 76.74.177.206 3371 + +The hint `close means q = next_prime(p\)` was released at a later time and I only found out about that hint after the challenge ended. +Upon connecting to the host we get a challenge in the form of `Please submit a printable string X, such that sha256(X)[-6:] = 95b3ff and len(X) = 27`. +That appears to be the same prove-of-work task that is used in the "Yet funny" challenge, for which the source code is given. +The hash can be one of `md5, sha1, sha224, sha256, sha384, sha512` and the length is between `10 and 40`. +Once the PoW has been solved, we are presented with the following task: + + hi all! We are looking for two large close 512-bit primes p and q such that q > p, and √q - √p ≥ 0.000000000000000000000000000000000000000000000000000000000000000000000000016 + Can you find such primes? √ means sqrt, try your best and send to us the first prime p. + Options: + [S]end prime p + [Q]uit! + +### Attempt + +I first wrote a python script to solve the PoW part. + +```python +from pwn import * +import itertools +from time import sleep +from random import choice +from string import * +import pwnlib.util.hashes + +host='76.74.177.206' +port=3371 + +def parse(line): + hash = line[46:line.index('(')] + mindex = line.index('] = ') + match = line[mindex+4:mindex+10] + length = int(line[-3:-1]) + return (hash, match, length) + +def reconnectTillMd5(): + while True: + r = remote(host, port) + line = r.recvline().decode() + (h, m, l) = parse(line) + if h == 'md5': + print(line) + return (r,h,m,l) + else: + r.close() + sleep(0.5) + +def bruteforce_rand(match, length, hashfunc): + l = len(match) + count = 1 + while True: + c = ''.join(choice(ascii_letters + digits) for i in range(length)) + h = hashfunc(c.encode()) + if h[-l:] == match: + print('match found: {} = h({})'.format(h, c)) + return c + if count % 1000000 == 0: + print('tried {} * 10^6 hashes'.format(count/1000000)) + print('{} = h({})'.format(h, c)) + count+=1 + +def bruteforce_seq(match, length, hashfunc): + l = len(match) + count = 1 + for c in itertools.product(ascii_letters+digits, repeat = length): + c = ''.join(c) + h = hashfunc(c.encode()) + if h[-l:] == match: + print('match found: {} = h({})'.format(h, c)) + return c + if count % 1000000 == 0: + print('tried {} * 10^6 hashes'.format(count/1000000)) + print('{} = h({})'.format(h, c)) + count+=1 + +def main(): + (r, h, m, l) = reconnectTillMd5() + c = bruteforce_seq(m,l) + r.sendline(c) + txt = r.recvall() + print(txt) + +if __name__ == '__main__': + #h = md5sumhex + #l = 10 + #plain = 'aaaanaaaaa' #''.join(choice(ascii_letters+digits) for i in range(l)) + #hash = h(plain.encode()) + #match = hash[-6:] + #print('{} characters long ending with {}'.format(l, match)) + #c = bruteforce_seq(match, l, h) + main() +``` +The code connects to the server using the pwntools tubes module, gets the PoW challenge and tries to bruteforce the correct hash. Here I had some problems, because I would often get a timeout before the script could find a correct value. I first thought the problem is that I ran the code in a VM, but running the code directly did not improve the performance. Because I did not want to use a different language because pwntools is so convenient and I did not know (or want to) if multithreading / starting multiple processes would help much I just reconnected till to the host till I got a md5 hash, for which the script got an solution most of the time. Then I received the real challenge as shown above. The challange can be run offline, which is nice. To find primes I used the gmpy2 library, which also has a function `next_prime(q)`, which conveniently finds the next prime `p` such that `p > q`. The code: +```python +from Crypto.Util.number import * +import gmpy2 + +def main(): + c = 0 + start=time.time() + dif = 0.000000000000000000000000000000000000000000000000000000000000000000000000016 + while True: + p = getPrime(512) + q = gmpy2.next_prime(p) + if (gmpy2.sqrt(q) - gmpy2.sqrt(p)) >= dif: + print('found: ', p, q) + return (p,q) + if time.time() - start > 15: + print('{}: {} tested'.format(time.time()-start, c)) + start = time.time() + c +=1 + +if __name__ == '__main__': + p,q = main() + print('(p,q) = ({},{})'.format(p,q)) +``` +I ran that code for about an hour and in the meantime looked another challenge. Unfortunately, the code did not work / return a result. + +## Problems of my code +After the CTF was over, I looked at the writeup from [here][1] to find out why my code did not work. +The code above cannot find a solution because I did not set the precision of the [reals / the mpfr module][2]. +That can be done with `gmpy2.get_context().precision = 1024`. If we do not set the `precision` to a sufficiently high number, the `sqrt` calculations - `gmpy2.sqrt(q)` and `gmpy2.sqrt(p)` - return the same value because the numbers are so huge. As an example: +```python +>>> p = getPrime(512) +>>> p +11631779155100729962586087103617610994659776213061220305417026036717218640211672664963542324251964649791603386004740049118812343848359731655073667497316291 +>>> gmpy2.sqrt(p) +mpfr('1.0785072626135037e+77') +>>> gmpy2.sqrt(p-999999999999999999999999999999) +mpfr('1.0785072626135037e+77') +``` +Therefore, the difference between the two square roots is always 0 and my loop never terminates. + +Performance-wise, I am sure there are some possible improvements ;). + + +[1]: https://github.com/p4-team/ctf/tree/master/2019-11-16-asis-finals/close_primes +[2]: https://gmpy2.readthedocs.io/en/latest/mpfr.html#contexts -- 2.43.0