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
149 A sincere gift for cryptographers, enjoy solving it!
151 We got an archive with the following files:
155 output.txt contains two large numbers, `c and n`:
157 c = 78643169701772559588799235367819734778096402374604527417084323620408059019575192358078539818358733737255857476385895538384775148891045101302925145675409962992412316886938945993724412615232830803246511441681246452297825709122570818987869680882524715843237380910432586361889181947636507663665579725822511143923
158 n = 420908150499931060459278096327098138187098413066337803068086719915371572799398579907099206882673150969295710355168269114763450250269978036896492091647087033643409285987088104286084134380067603342891743645230429893458468679597440933612118398950431574177624142313058494887351382310900902645184808573011083971351
160 serifin.py contains code that encodes the flag by performing `c = encrypt(flag, n)`. It seems we have to reverse engineer the code and somehow calculate the flag given the two values `c,n` from the output.txt file.
163 First I looked at the source code: two prime numbers p and q are generated but with some condition
165 p%9 = 1, q%9 = 1, p%27 > 1, q%27 > 1 and q = next_prime(fun(p))
167 Then, the flag is encoded with `c = flag^3 mod n` with `n=p*q`.
168 Essentially we have to solve the congruence `f³ = c mod n` with c and n given.
169 First, I tried solving this with z3 and the python bindings for it. Unfortunately, that didn't work.
170 I then took a closer look at the serifin function and found that it basically calculates the partial sum of the geometric series `a + a/l + a/l² + a/l³ + ..`, but with the caveat that if the difference between the current and last term is smaller than `0.0001`, the function stops. Maybe that information can be used to factor `n` into `p and q`.
172 I then spent a long time reading up about modular arithmetic and RSA.
173 Apparently, the solution has something to do with the [Chinese Remainder Theorem][1], because I found and [stackexchange entry][2]. I spent some more time reading up on the CRT but unfortunately did not learn how to solve the problem.
175 [1]: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
176 [2]: https://math.stackexchange.com/questions/2689987/solving-cubic-congruence