]> git.somenet.org - pub/jan/ctf-seminar.git/blob - writeups/mla/asis19.md
Update seccon19.md
[pub/jan/ctf-seminar.git] / writeups / mla / asis19.md
1 # ASIS Cyber Security Contest '19
2
3 ## Close Primes
4
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)
7     nc 76.74.177.206 3371
8
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:
14
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.
17         Options:
18                 [S]end prime p
19                 [Q]uit!
20                 
21 ### Attempt
22
23 I first wrote a python script to solve the PoW part. 
24
25 ```python
26 from pwn import *
27 import itertools
28 from time import sleep
29 from random import choice
30 from string import *
31 import pwnlib.util.hashes
32
33 host='76.74.177.206'
34 port=3371
35
36 def parse(line):
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)
42
43 def reconnectTillMd5():
44         while True:
45                 r = remote(host, port)
46                 line = r.recvline().decode()
47                 (h, m, l) = parse(line)
48                 if h == 'md5':
49                         print(line)
50                         return (r,h,m,l)
51                 else:
52                         r.close()
53                         sleep(0.5)
54
55 def bruteforce_rand(match, length, hashfunc):
56     l = len(match)
57     count = 1
58     while True:
59         c = ''.join(choice(ascii_letters + digits) for i in range(length))
60         h = hashfunc(c.encode())
61         if h[-l:] == match:
62             print('match found: {} = h({})'.format(h, c))
63             return c
64         if count % 1000000 == 0:
65             print('tried {} * 10^6 hashes'.format(count/1000000))
66             print('{} = h({})'.format(h, c))
67         count+=1
68
69 def bruteforce_seq(match, length, hashfunc):
70     l = len(match)
71     count = 1
72     for c in itertools.product(ascii_letters+digits, repeat = length):
73         c = ''.join(c)
74         h = hashfunc(c.encode())
75         if h[-l:] == match:
76             print('match found: {} = h({})'.format(h, c))
77             return c
78         if count % 1000000 == 0:
79             print('tried {} * 10^6 hashes'.format(count/1000000))
80             print('{} = h({})'.format(h, c))
81         count+=1
82
83 def main():
84     (r, h, m, l) = reconnectTillMd5()
85     c = bruteforce_seq(m,l)
86     r.sendline(c)
87     txt = r.recvall()
88     print(txt)
89
90 if __name__ == '__main__':
91     #h = md5sumhex
92     #l = 10
93     #plain = 'aaaanaaaaa' #''.join(choice(ascii_letters+digits) for i in range(l))
94     #hash = h(plain.encode())
95     #match = hash[-6:]
96     #print('{} characters long ending with {}'.format(l, match))
97     #c = bruteforce_seq(match, l, h)
98     main() 
99 ```
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:
101 ```python
102 from Crypto.Util.number import *
103 import gmpy2
104
105 def main():
106         c = 0
107         start=time.time()
108         dif = 0.000000000000000000000000000000000000000000000000000000000000000000000000016
109         while True:
110                 p = getPrime(512)
111                 q = gmpy2.next_prime(p)
112                 if (gmpy2.sqrt(q) - gmpy2.sqrt(p)) >= dif:
113                         print('found: ', p, q)
114                         return (p,q)
115                 if time.time() - start > 15:
116                         print('{}: {} tested'.format(time.time()-start, c))
117                         start = time.time()
118                 c +=1
119
120 if __name__ == '__main__':
121         p,q = main()
122         print('(p,q) = ({},{})'.format(p,q))
123 ```
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. 
125
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:
130 ```python
131 >>> p = getPrime(512)
132 >>> p
133 11631779155100729962586087103617610994659776213061220305417026036717218640211672664963542324251964649791603386004740049118812343848359731655073667497316291
134 >>> gmpy2.sqrt(p)
135 mpfr('1.0785072626135037e+77')
136 >>> gmpy2.sqrt(p-999999999999999999999999999999)
137 mpfr('1.0785072626135037e+77')
138 ```
139 Therefore, the difference between the two square roots is always 0 and my loop never terminates.
140
141 Performance-wise, I am sure there are some possible improvements ;).
142
143
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
146
147
148 ## Serifin (crypto)
149     A sincere gift for cryptographers, enjoy solving it!
150
151 We got an archive with the following files:
152 + output.txt
153 + serifin.py
154
155 output.txt contains two large numbers, `c and n`:
156
157     c = 78643169701772559588799235367819734778096402374604527417084323620408059019575192358078539818358733737255857476385895538384775148891045101302925145675409962992412316886938945993724412615232830803246511441681246452297825709122570818987869680882524715843237380910432586361889181947636507663665579725822511143923
158     n = 420908150499931060459278096327098138187098413066337803068086719915371572799398579907099206882673150969295710355168269114763450250269978036896492091647087033643409285987088104286084134380067603342891743645230429893458468679597440933612118398950431574177624142313058494887351382310900902645184808573011083971351
159
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.
161
162 ### Attempt
163 First I looked at the source code: two prime numbers p and q are generated but with some condition
164     
165     p%9 = 1, q%9 = 1, p%27 > 1, q%27 > 1 and q = next_prime(fun(p))
166
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`.
171
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.
174
175 [1]: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
176 [2]: https://math.stackexchange.com/questions/2689987/solving-cubic-congruence