writeups/icecrax/asis2019/asis_single_bits_writeup.md

   1 # ASIS CTF Finals 2019 - Single bits (crypto / 194 points / 21 solves)
   2 The ASIS CTF Finals consisted of 25 challenges, released on different time intervals (every 8 hours 8 or 9 challenges were being released). `Single bits` was released in the last 3rd phase of the CTF. I wasn't able to solve it during the competition, but I continued working on it after that. Solving it required a lot of research and good math knowledge to understand the theorems and apply them correctly.
   3
   4 ## Overview:
   5 `Single bits` is a crypto reverse challenge. We were given two files: `single_bits.py` and `output.txt`.
   6
   7 ``` python
   8 #!/usr/bin/env python
   9
  10 import random
  11 from Crypto.Util.number import *
  12 from flag import flag
  13
  14 def gen_rand(nbit, l):
  15     R = []
  16     while True:
  17         r = random.randint(0, nbit-1)
  18         if r not in R:
  19             R.append(r)
  20             if len(R) == l:
  21                 break
  22     R.sort()
  23     rbit = '1'
  24     for i in range(l-1):
  25         rbit += (R[i+1] - R[i] - 1) * '0' + '1'
  26     rbit += (nbit - R[-1] - 1) * '0'
  27     return int(rbit, 2)
  28
  29 def genkey(p, l):
  30     n = len(bin(p)[2:])
  31     f, skey = gen_rand(n, l), gen_rand(n, l)
  32     pkey = f * inverse(skey, p) % p
  33     return (p, pkey), skey
  34
  35 def encrypt(msg, pkey):
  36     p, g = pkey
  37     msg, enc, n = bytes_to_long(msg), [], len(bin(p)[2:])
  38     for b in bin(msg)[2:]:
  39         s, t = gen_rand(n, l), gen_rand(n, l)
  40         c = (s * g + t) % p
  41         if b == '0':
  42             enc.append((c, t))
  43         else:
  44             enc.append((p-c, t))
  45     return enc
  46
  47 p = 862718293348820473429344482784628181556388621521298319395315527974911
  48 l = 5
  49
  50 pkey, skey = genkey(p, l)
  51 enc = encrypt(flag, pkey)
  52 H = pkey[1] ** 2 % p
  53
  54 print('H =', H)
  55 print('enc =', enc)
  56 ```
  57
  58 The `output.txt` had the printed `'H'` and `'enc'` variables, where `H = 381704527450191606347421195235742637659723827441243208291869156144963` and `enc` was an array, consisting of every bit from the flag encrypted with the public key: `enc = [(693452030319839722726551032492658894345570855091353510812978453643631 374147273652096600518280302026002167242456968463360, ... `.
  59
  60 ## Short explanation of the given code:
  61 1) Function `gen_rand(nbit, l)` takes 2 parameters, which are always equal to (229, 5). Then it produces 5 random numbers with a bit length of 229, sorts them and saves them into an array. For each number a `rbit` is calculated and all `rbits` are appended together. The final binary number is converted to int and returned.
  62 __*It's worth noticing that although the `rbit` is calculated randomly, because we don't know the 2 numbers used to produce it, we always end up with a number, which binary representation has exactly five `'1'`s and many `'0'`. This information turned out to be useful later.*__
  63
  64 2) Function `genkey()` generates a public and a private key using `gen_rand()`.
  65
  66 3) Function `encrypt()` again `gen_rand()` and the already created public key to encrypt every bit of the flag. For `'0'`s `'c'` is appended to the `'enc'` variable, for '`1'`s `'(p-c)'`
  67
  68 ## Solution / Exploit:
  69 Since the public key is encrypted in H via `H = pkey[1] ** 2 % p`, the reverse engineering started from there. Googling this concrete equation lead me to a Wikipedia article about `Quadratic residues`, which explained in more detail the equation `x^2 ≡ q (mod n).` In our case this corresponds to `pkey^2 ≡ H (mod p)`.
  70
  71 In general finding x is considered a hard problem, but in our case the modulo `'p'` is not a prime number and the solution requires much less time. We can factorize `'p'` and try to find solutions for all the factors pi: `pkey^2 ≡ H (mod pi)` and in the end combine those solutions using the `Chinese remainder theorem`.
  72
  73     p = 862718293348820473429344482784628181556388621521298319395315527974911
  74     factors = [1504073, 20492753, 59833457464970183, 467795120187583723534280000348743236593]
  75
  76 The Wikipedia article didn't have more information about how to solve the quadratic residue problem, only theorems determining if a number is one using the `Legendre symbol` or `Euler’s Criterion`.
  77
  78 I found in another article on the internet two approaches to find a solution.
  79  1) If `'a'` is a quadratic residue (mod p) and `p ≡ 3 (mod 4)` then `a^((p+1)/4)` is a solution to `x^2 ≡ a (mod p)`.
  80  2) If `a ≡ 1 (mod 4)` there is no analogous formula. In that case, one may use the `Tonelli-Shanks algorithm`.
  81
  82 It turned out that all the above factors (mod 4) give 1. So I found a python script with the `Tonnelli-Shanks algorithm` and it produced the following results:
  83
  84     x^2 ≡ H (mod pi), where pi are prime numbers, factors of p
  85     p0 = 1504073:
  86      399666
  87      1104407
  88
  89     p1 = 20492753:
  90      7111848
  91      13380905
  92
  93     p2 = 59833457464970183:
  94      34240854883018057
  95      25592602581952126
  96
  97     p3 = 467795120187583723534280000348743236593:
  98      308269479959806774875048102517512730884
  99      159525640227776948659231897831230505709
 100
 101 Each of the factors had 2 solutions. So from them using the `Chinese remainder theorem` I had to produce a solution for the original equation. And here I was stuck for a long time. I fed a python script implementing this algorithm the 8 solutions and their corresponding factors and because the factors were 4 and the solutions 8, I had to insert the factors twice. But that was the problem, because the numbers I had to input for the factors array had to be relatively prime to each other, meaning repeating them is not allowed!
 102
 103 So I took the 8 solutions and I mixed them into 16 arrays and I fed each separately to the algorithm. It produced 16 possible public keys.
 104
 105     r0 = [1104407, 13380905, 25592602581952126, 159525640227776948659231897831230505709]
 106     r1 = [1104407, 13380905, 25592602581952126, 308269479959806774875048102517512730884]
 107     r2 = [1104407, 13380905, 34240854883018057, 159525640227776948659231897831230505709]
 108     r3 = [1104407, 13380905, 34240854883018057, 308269479959806774875048102517512730884]
 109     r4 = [1104407, 7111848, 25592602581952126, 159525640227776948659231897831230505709]
 110     r5 = [1104407, 7111848, 25592602581952126, 308269479959806774875048102517512730884]
 111     r6 = [1104407, 7111848, 34240854883018057, 159525640227776948659231897831230505709]
 112     r7 = [1104407, 7111848, 34240854883018057, 308269479959806774875048102517512730884]
 113     r8 = [399666, 13380905, 25592602581952126, 159525640227776948659231897831230505709]
 114     r9 = [399666, 13380905, 25592602581952126, 308269479959806774875048102517512730884]
 115     r10 = [399666, 13380905, 34240854883018057, 159525640227776948659231897831230505709]
 116     r11 = [399666, 13380905, 34240854883018057, 308269479959806774875048102517512730884]
 117     r12 = [399666, 7111848, 25592602581952126, 159525640227776948659231897831230505709]
 118     r13 = [399666, 7111848, 25592602581952126, 308269479959806774875048102517512730884]
 119     r14 = [399666, 7111848, 34240854883018057, 159525640227776948659231897831230505709]
 120     r15 = [399666, 7111848, 34240854883018057, 308269479959806774875048102517512730884]
 121
 122
 123     possible_pkeys = [
 124     739258514585797449032297222084055811470702691611125687711372074996687,
 125     460372941321907147479217537764873459531020265638440613169538863817034,
 126     785232755191570522054580268914288666635203565395845945113513087262967,
 127     506347181927680220501500584595106314695521139423160870571679876083314,
 128     861011580078658110931573476857568388286745404020778288869777707662969,
 129     582126006814767809378493792538386036347062978048093214327944496483316,
 130     44267527335610710524512040903173061894857656284200226876603191954338,
 131     628100247420540882400776839368618891511563851832813471730085508749596,
 132     234618045928279591028567643416009290044824769688484847665230019225315,
 133     818450766013209762904832441881455119661530965237098092518712336020573,
 134     280592286534052664050850690246242145209325643473205105067371031491595,
 135     1706713270162362497771005927059793269643217500520030525537820311942,
 136     356371111421140252927843898189521866860867482098137448823635651891597,
 137     77485538157249951374764213870339514921185056125452374281802440711944,
 138     402345352026913325950126945019754722025368355882857706225776664157877,
 139     123459778763023024397047260700572370085685929910172631683943452978224]
 140
 141
 142 So we finally decrypted the public key. Now the next step is to look at the `'encrypt()'` function which uses our public key and try to reverse it. Because the first part of each encrypted bit in `'enc'` could be either `'c'` or `'p-c'`, we have to find a method to distinguish between those two cases when reversing `c = (s * g + t) % p`, where `'g'` is in this case our `'pkey'` and `'s'` and `'t'` are generated by `gen_rand()`.
 143
 144 Now we can use the information I mentioned earlier that all numbers generated by the `gen_rand()` function have in their binary representation exactly five `'1'`. If we menage to reverse `c = (s * g + t) % p` to get just `'s'`, we can check if it is a valid number generated by `'gen_rand()'`.
 145
 146 Trying some modulo arithmetics to inverse the expression:
 147
 148     c = (s * pkey + t) % p
 149     (c - t) ≡ s * pkey (mod p)
 150     (c - t) * pkey ≡ s * pkey^2 (mod p)
 151     (c - t) * pkey ≡ s * H (mod p)      because H ≡ pkey^2 (mod p)
 152
 153     Rule:
 154     a ≡ b mod p
 155     a = b + p * k
 156
 157     s * H = (c - t) * pkey + p * k
 158     s = ((c - t) * pkey + p * k) / H
 159
 160 Bummer! Brute forcing `'s'`  by iterating over `'k'` and checking if `'s'` is a whole integer wasn't a good idea. I tried it for k in `range(10000000)`. No solution...
 161
 162 Then I spend time searching in math forums how to reverse such an expression and I found out, that I can do the following:
 163
 164     c = (s * pkey + t) % p
 165     (c - t) ≡ s * pkey (mod p)
 166     (c - t) * pkey^(-1) ≡ s * pkey * pkey^(-1) (mod p)     pkey^(-1) is modular inverse of pkey mod p
 167     (c - t) * pkey^(-1) ≡ s * 1 (mod p)
 168
 169     Rule:
 170     The value of the modular inverse of a by the modulo n is the value a^(−1) such that aa^(−1) = 1 (mod n). It can be calculated through the "Extended Euclidean Algorithm", which finds solutions to the "Bеzout identity" (ax + by = d).
 171
 172     Note:
 173     Modular inverse of a number n mod m exists only if gcd(n,m) = 1
 174     The library I used "Crypto.Util.number" doesn't check this and might produce wrong answers.
 175     Better alternatives are: "gmpy2" and "sage".
 176
 177 Having now `'s'` produced by `s = ((c - t) * inverse(pkey, p)) % p` we check if it is valid. If it is valid, then it was encrypted with just `'c'` and corresponds to bit `'0'`, if it is not, then it was produced by `s = (((p - c) - t) * inverse(pkey, p)) % p` and it corresponds to bit `'1'`.
 178
 179 Going through all the elements in `'enc'` we reverse the bits and reconstruct the flag = `ASIS{T0y_3XampL3_w1tH__m3rSEnN3__nUmB3r5}`.
 180 `"Mersenne numbers"` are of the form Mn = 2^n − 1. Our `'p'` value was a mersenne number (2^229 - 1)
 181
 182 The final exploit was:
 183
 184 ``` python
 185 #!/usr/bin/env python3
 186 enc = [...]
 187
 188 # Calculated via the "Tonnelli-Shanks algorithm" and the "Chinese remainder theorem"
 189 possible_pkeys = [
 190 739258514585797449032297222084055811470702691611125687711372074996687,
 191 460372941321907147479217537764873459531020265638440613169538863817034,
 192 785232755191570522054580268914288666635203565395845945113513087262967,
 193 506347181927680220501500584595106314695521139423160870571679876083314,
 194 861011580078658110931573476857568388286745404020778288869777707662969,
 195 582126006814767809378493792538386036347062978048093214327944496483316,
 196 44267527335610710524512040903173061894857656284200226876603191954338,
 197 628100247420540882400776839368618891511563851832813471730085508749596,
 198 234618045928279591028567643416009290044824769688484847665230019225315,
 199 818450766013209762904832441881455119661530965237098092518712336020573,
 200 280592286534052664050850690246242145209325643473205105067371031491595,
 201 1706713270162362497771005927059793269643217500520030525537820311942,
 202 356371111421140252927843898189521866860867482098137448823635651891597,
 203 77485538157249951374764213870339514921185056125452374281802440711944,
 204 402345352026913325950126945019754722025368355882857706225776664157877,
 205 123459778763023024397047260700572370085685929910172631683943452978224]
 206
 207 H = 381704527450191606347421195235742637659723827441243208291869156144963
 208 p = 862718293348820473429344482784628181556388621521298319395315527974911
 209
 210 from Crypto.Util.number import *
 211
 212 flag = ''
 213
 214 # Check all possible public keys, because only one of them is used for the encryption
 215 for pkey in possible_pkeys:
 216
 217     # For each flag try to reverse its bits
 218     for i in range(len(enc)):
 219         c = enc[i][0]
 220         t = enc[i][1]
 221
 222         a = ((c - t) * inverse(pkey,p)) % p
 223         x = bin(a)[2:].count('1')
 224         if (x == 5):
 225             flag += '0'
 226             continue
 227
 228         a = (((p - c) - t) * inverse(pkey,p)) % p
 229         y = bin(a)[2:].count('1')
 230         if (y == 5):
 231             flag += '1'
 232             continue
 233
 234     # If we got a meaningful flag, reverse it.
 235     if (flag != ''):
 236         print(long_to_bytes(int(flag,2)))
 237         flag = ''
 238
 239 ```