1 # ASIS Cyber Security Contest '19
5 The people who can do you the most damage are the ones who are closest to you.
6 "close" means q = next_prime(p)
9 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.
10 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`.
11 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.
12 The hash can be one of `md5, sha1, sha224, sha256, sha384, sha512` and the length is between `10 and 40`.
13 Once the PoW has been solved, we are presented with the following task:
15 hi all! We are looking for two large close 512-bit primes p and q such that q > p, and √q - √p ≥ 0.000000000000000000000000000000000000000000000000000000000000000000000000016
16 Can you find such primes? √ means sqrt, try your best and send to us the first prime p.
23 I first wrote a python script to solve the PoW part.
28 from time import sleep
29 from random import choice
31 import pwnlib.util.hashes
37 hash = line[46:line.index('(')]
38 mindex = line.index('] = ')
39 match = line[mindex+4:mindex+10]
40 length = int(line[-3:-1])
41 return (hash, match, length)
43 def reconnectTillMd5():
45 r = remote(host, port)
46 line = r.recvline().decode()
47 (h, m, l) = parse(line)
55 def bruteforce_rand(match, length, hashfunc):
59 c = ''.join(choice(ascii_letters + digits) for i in range(length))
60 h = hashfunc(c.encode())
62 print('match found: {} = h({})'.format(h, c))
64 if count % 1000000 == 0:
65 print('tried {} * 10^6 hashes'.format(count/1000000))
66 print('{} = h({})'.format(h, c))
69 def bruteforce_seq(match, length, hashfunc):
72 for c in itertools.product(ascii_letters+digits, repeat = length):
74 h = hashfunc(c.encode())
76 print('match found: {} = h({})'.format(h, c))
78 if count % 1000000 == 0:
79 print('tried {} * 10^6 hashes'.format(count/1000000))
80 print('{} = h({})'.format(h, c))
84 (r, h, m, l) = reconnectTillMd5()
85 c = bruteforce_seq(m,l)
90 if __name__ == '__main__':
93 #plain = 'aaaanaaaaa' #''.join(choice(ascii_letters+digits) for i in range(l))
94 #hash = h(plain.encode())
96 #print('{} characters long ending with {}'.format(l, match))
97 #c = bruteforce_seq(match, l, h)
100 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:
102 from Crypto.Util.number import *
108 dif = 0.000000000000000000000000000000000000000000000000000000000000000000000000016
111 q = gmpy2.next_prime(p)
112 if (gmpy2.sqrt(q) - gmpy2.sqrt(p)) >= dif:
113 print('found: ', p, q)
115 if time.time() - start > 15:
116 print('{}: {} tested'.format(time.time()-start, c))
120 if __name__ == '__main__':
122 print('(p,q) = ({},{})'.format(p,q))
124 I ran that code for about an hour and in the meantime looked another challenge. Unfortunately, the code did not work / return a result.
126 ## Problems of my code
127 After the CTF was over, I looked at the writeup from [here][1] to find out why my code did not work.
128 The code above cannot find a solution because I did not set the precision of the [reals / the mpfr module][2].
129 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:
131 >>> p = getPrime(512)
133 11631779155100729962586087103617610994659776213061220305417026036717218640211672664963542324251964649791603386004740049118812343848359731655073667497316291
135 mpfr('1.0785072626135037e+77')
136 >>> gmpy2.sqrt(p-999999999999999999999999999999)
137 mpfr('1.0785072626135037e+77')
139 Therefore, the difference between the two square roots is always 0 and my loop never terminates.
141 Performance-wise, I am sure there are some possible improvements ;).
144 [1]: https://github.com/p4-team/ctf/tree/master/2019-11-16-asis-finals/close_primes
145 [2]: https://gmpy2.readthedocs.io/en/latest/mpfr.html#contexts