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