From d55363f9833e875a5f2bd52964887e527f013851 Mon Sep 17 00:00:00 2001
From: Michael Lang <None>
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