writeups/toaster/overthewire-advent-bonanza.md

   1 # OverTheWire Advent Bonanza 2019
   2
   3 #### day-01 7110 (~3h)
   4 ##### Overview
   5 There were some `.csv` and `.txt` files given. The `.csv` files contained timestamps, I assumed (which turned out to be correct) and the keycodes of the keys which were pressed at the corresponding timestamps. The `.txt` files contained the translated SMS, but only for three of the four `.csv` files. The challenge was to translate the last `.csv` file. Also, there was a `.c` file, which explained how the keycodes work.
   6 With the help of the challenge description I knew that the keys were pressed on an old phone, where you had to press one button multiple times to get a single letter and the letter changes depending on how many times you press the button. Now I could write a simple python program, which parses the `.csv` file.
   7
   8 ##### Exploit
   9 Here is the script I wrote, explanation is below:
  10 ```python
  11 keys= [" 0", ".,'?!\"1-()@/:", "abc2", "def3", "ghi4", "jkl5", "mno6", "pqrs7", "tuv8", "wxyz9", "@/:_;+&%*[]{}"]
  12 filepath = 'sms4.csv'
  13
  14 with open(filepath) as fp:
  15     last_keycode = -1
  16     last_keycount = 0
  17     last_timestamp = 0
  18     line = fp.readline().strip()
  19     out = ""
  20     while line:
  21         arr = line.split(",")
  22         timestamp = int(arr[0])
  23         keycode = int(arr[1])
  24         # Either another key was pressed or the time between the key presses was high enough that two separate characters should be typed
  25         if (last_keycode != keycode or timestamp - last_timestamp > 1200) and last_keycode != -1:
  26             out += keys[last_keycode][last_keycount % len(keys[last_keycode])]
  27             last_keycount = 0
  28         elif last_keycode == keycode:
  29             last_keycount += 1
  30         last_keycode = keycode
  31         last_timestamp = timestamp
  32         if last_keycode < 0 or last_keycode > 10:
  33             if last_keycode == 101: # Backspace
  34                 out = out[:-1]
  35             last_keycode = -1
  36             last_timestamp = 0
  37
  38         line = fp.readline().strip()
  39     print(out)
  40 ```
  41 The script reads the file line by line. In every line, it checks if the keycode is other than the previous one. If so, the letter (according to the amount of presses of this button) is added to the output string. The same thing happens when the time which passed since the last button was pressed exceeds a threshold (1200 in this case). This means that a new character is meant to be typed. We need to use modulo to get the correct character, as there is a "wrap-around" when you press a button more often than there are characters. For example, if you press "2" five times it should result in the letter a.
  42 If the last keycode does not differ from the previous one, we simply add one to the current keycount.
  43 Then, the last keycode and last timestamp variables are set. After this, it is checked if the keycode is one of the standard keys (like "1", "2", etc.). If not, ignore it. There is an exception with keycode "101", as this code represents the "Backspace" or "Delete character" button. If this button was pressed we simply delete the last character of our output string.  At the end the output string is printed.
  44
  45 The output of the script is the following: `alright pal herse ye flag gnd lucj enteking it with those hnves lol its aotw{l3ts_dr1nk_s0m3_eggn0g_y0u_cr4zy_d33r}0m.. .l ,p`
  46 I don't think I got the message 100% correct but it was enough for the flag:
  47
  48 Flag: `AOTW{l3ts_dr1nk_s0m3_eggn0g_y0u_cr4zy_d33r}`
  49
  50 #### day-03 Northpole Airwaves (~3h)
  51 ##### Overview
  52 This is a forensics challenge. Given was a ~700MB large file where you probably have to extract some information.
  53
  54 ##### Attempts
  55 First I looked for some strings in the file, but of course this would have been too easy, so nothing useful here.
  56 I then used `binwalk` to get an idea of the files which hide in here. I got the following output:
  57
  58 ```
  59 DECIMAL       HEXADECIMAL     DESCRIPTION
  60 --------------------------------------------------------------------------------
  61 25161462      0x17FEEF6       Windows Script Encoded Data (screnc.exe)
  62 30103466      0x1CB57AA       Windows Script Encoded Data (screnc.exe)
  63 104543102     0x63B337E       Windows Script Encoded Data (screnc.exe)
  64 220329450     0xD21F5EA       Windows Script Encoded Data (screnc.exe)
  65 492700718     0x1D5E042E      Windows Script Encoded Data (screnc.exe)
  66 ```
  67
  68 I did some research on what this "Windows Script Encoded Data (screnc.exe)" is and found out that `screnc.exe` is some tool to obfuscate different types of scripts, including Visual Basic Script, for example.
  69 After this, I was looking for a way to decode such an encrypted script. I found a script: https://www.interclasse.com/scripts/decovbe.php
  70 This looked very promising, so I tried it out. Unfortunately, I got only gibberish as an output.
  71
  72 My next idea was to split the large file up into the different files it contains (I could tell this by the binwalk output). To do so, I used `binwalk` again:
  73 ```
  74 binwalk --dd='.*' d6d0f728ac3ff4848f849b8cf222fb38a14aee870184cc22f2efe01336b2ec17-northpole-airwaves.bin
  75 ```
  76 The `--dd` option extracts the given type signatures. In this case (`.*`) all of them. This creates a new directory containing all the files. I then used the decoding script I found before on all the files separately. Again only gibberish...
  77
  78 Well, turned out that what I did was nonsense and I should've read the description. I didn't get any further though.
  79
  80 #### day-04 mooo (~4h)
  81 ##### Overview
  82 Given was a simple webpage with one textfield, one dropdown and one button. The textfield lets you specify a message and you can choose a "Cow" in the dropdown. The whole thing is powered by `cowsay` as the footer states which is a tool to generate ASCII pictures of a cow saying the message you provided.
  83
  84 ##### Attempts and Solution
  85 First, I looked up the man pages of cowsay [here](https://linux.die.net/man/1/cowsay). There is a very interesting section:
  86
  87 ```
  88 A cowfile is made up of a simple block of perl(1) code, which assigns a picture of a cow to the variable $the_cow. Should you wish to customize the eyes or the tongue of the cow, then the variables $eyes and $tongue may be used. The trail leading up to the cow's message balloon is composed of the character(s) in the $thoughts variable. Any backslashes must be reduplicated to prevent interpolation. The name of a cowfile should end with .cow, otherwise it is assumed not to be a cowfile. Also, at-signs (''@'') must be backslashed because that is what Perl 5 expects.
  89 ```
  90
  91 "A cowfile is made up of perl code" sounds really promising. I thought that maybe we can execute arbitrary perl code somehow which would also allow us to execute system commands like `ls` or something.
  92
  93 In the dropdown you can choose different cows which are all predefined except one. The "custom" entry lets you create your own cow. I expected that this is done by using cowfiles.
  94 So here I could change the cow's appereance, but was not able to inject perl code yet. I took a look at an example cowfile from [here](https://github.com/piuccio/cowsay/blob/master/cows/default.cow):
  95
  96 ```perl
  97 $the_cow = <<"EOC";
  98         $thoughts   ^__^
  99          $thoughts  ($eyes)\\_______
 100             (__)\\       )\\/\\
 101              $tongue ||----w |
 102                 ||     ||
 103 EOC
 104 ```
 105
 106 I don't know perl, but `EOC` remembered me of `EOF` or something, so I just tried to use `EOC` as a separator. I quickly looked up how to execute commands in perl (`system()`) and tried it with the following input.
 107
 108 ```perl
 109 $thoughts   ^__^
 110  $thoughts  ($eyes)\\_______
 111     (__)\\       )\\/\\
 112      $tongue ||----w |
 113         ||     ||
 114 EOC
 115 system("ls")
 116 ```
 117
 118 It worked! I got the directory listing and the only thing I had to do now is to execute `cat flag` in the same way and I got the flag.
 119
 120 Flag: `AOTW{th3_p3rl_c0w_s4ys_M0oO0o0O}`
 121
 122 #### day-05 Sudo Sudoku (~3h)
 123 The solution was already solved by our team when I got to it, but I used the chance to take a look at Z3 which I never did before.
 124
 125 ##### Overview
 126 Given was a `.txt` file which contained a special sudoku. It had very few prefilled numbers but instead there were some formulas given which must be fullfilled in addition to the standard sudoku rules. The formulas where basically just additions of different cells where the result has to be a specific number.
 127
 128 ##### Solution
 129 The solution is pretty straight forward - just solve the sudoku. Of course this would take ages to do by hand, so I used Z3 in python. To do so, I used the sudoku example from the [Z3Py Guide](https://ericpony.github.io/z3py-tutorial/guide-examples.htm) and added the additional constraints:
 130
 131 ```python
 132 from z3 import *
 133
 134 # 9x9 matrix of integer variables
 135 X = [ [ Int("x_%s_%s" % (i+1, j+1)) for j in range(9) ]
 136       for i in range(9) ]
 137
 138 # each cell contains a value in {1, ..., 9}
 139 cells_c  = [ And(1 <= X[i][j], X[i][j] <= 9)
 140              for i in range(9) for j in range(9) ]
 141
 142 # each row contains a digit at most once
 143 rows_c   = [ Distinct(X[i]) for i in range(9) ]
 144
 145 # each column contains a digit at most once
 146 cols_c   = [ Distinct([ X[i][j] for i in range(9) ])
 147              for j in range(9) ]
 148
 149 # each 3x3 square contains a digit at most once
 150 sq_c     = [ Distinct([ X[3*i0 + i][3*j0 + j]
 151                         for i in range(3) for j in range(3) ])
 152              for i0 in range(3) for j0 in range(3) ]
 153
 154 # formulas from challenge specification
 155 formulas =  [X[1][8] + X[1][7] + X[2][0] + X[7][3] + X[7][3] == 23,
 156             X[0][4] + X[3][6] + X[8][4] + X[6][7] + X[1][2] + X[0][4] == 19,
 157             X[8][1] + X[8][2] + X[5][1] + X[4][8] == 15,
 158             X[8][6] + X[7][7] + X[2][1] + X[3][8] == 26,
 159             X[8][5] + X[0][4] + X[8][2] + X[1][7] + X[2][2] == 20,
 160             X[8][6] + X[3][8] + X[1][5] + X[0][7] + X[0][2] + X[2][3] == 27,
 161             X[2][6] + X[7][8] + X[8][6] + X[1][1] + X[7][7] + X[6][2] == 31,
 162             X[3][2] + X[8][7] + X[0][3] + X[8][5] == 27,
 163             X[5][4] + X[1][7] + X[5][7] + X[8][6] + X[5][0] == 33,
 164             X[0][1] + X[0][7] + X[3][6] + X[4][3] == 21,
 165             X[2][0] + X[8][3] + X[2][1] + X[8][0] + X[0][3] == 20,
 166             X[5][7] + X[2][0] + X[5][5] + X[3][2] + X[1][5] == 25]
 167
 168 sudoku_c = cells_c + rows_c + cols_c + sq_c + formulas
 169
 170 # sudoku instance, we use '0' for empty cells
 171 instance = ((0,0,0,0,0,0,0,0,1),
 172             (0,1,2,0,0,0,0,0,0),
 173             (0,0,0,0,0,0,2,0,0),
 174             (0,0,0,0,0,0,0,0,2),
 175             (0,2,0,0,0,0,0,0,0),
 176             (0,0,0,0,0,0,0,0,0),
 177             (0,0,0,0,0,0,1,2,0),
 178             (1,0,0,0,0,2,0,0,0),
 179             (0,0,0,1,0,0,0,0,0))
 180
 181 instance_c = [ If(instance[i][j] == 0,
 182                   True,
 183                   X[i][j] == instance[i][j])
 184                for i in range(9) for j in range(9) ]
 185
 186 s = Solver()
 187 s.add(sudoku_c + instance_c)
 188 if s.check() == sat:
 189     m = s.model()
 190     r = [ [ m.evaluate(X[i][j]) for j in range(9) ]
 191           for i in range(9) ]
 192     print_matrix(r)
 193
 194     # Print flag
 195     print("AOTW{", end='')
 196     for i in r[0]:
 197         print(i, end='')
 198     for i in range(1,len(r)):
 199         print(r[i][len(r)-1], end='')
 200     for i in range(len(r[len(r)-1])-2, 0, -1):
 201         print(r[len(r)-1][i], end='')
 202     for i in range(len(r)-1, 0, -1):
 203         print(r[i][0], end='')
 204     print("}")
 205 else:
 206     print("failed to solve")
 207 ```
 208
 209 This takes a while to solve but then the solved sudoku is printed. Also, the flag is printed which can be obtained by reading the numbers of the solved sudoku clockwise.
 210
 211 Flag: `AOTW{86472953189247356794813521457639}`
 212
 213 #### day-16 Musical Stegano (~10h)
 214 This challenge was particularly interesting for me because I play guitar and the piano, so I know how to read sheet music which was helpful for this challenge. Also, this challenge was very special compared to other CTF challenges which was a nice variety.
 215
 216 ##### Overview
 217 Given was a midi file. This can be opened with a music notation program, like [Musescore](https://musescore.org/) for example, to get the corresponding sheet music. The piece is written in G major.
 218
 219 ##### Attempts and Solution
 220 My first attempt was to somewhow get a character based on the note and its duration. So for example, if there is a A as a half note, I calculated 2 (second note in G major) * 4 (one half note contains 4 eighth notes). Don't know how I came to this, just tried some random things out.
 221
 222 After a few unsuccessful attempts, I was trying a more systematical approach. We know that the flag starts with `A` and ends with `}`. So the `}` character has to be encoded somewhere at the end of the sheet music. In the challenge description there is something written like "BASS SEVEN TRIGRAPHS". I interpreted "Bass" as "Base" and this could make sense (base of number system, 7 in this case), as we have 7 different notes in the G major scale. Also, I knew that G should be translated to 0, A to 1, B to 2, C to 3, D to 4, E to 5 and F# to 6 based on a hint.
 223 Now I looked up the `}` in an ASCII table. The decimal ASCII value for `}` is 125. I converted this decimal value into base 7 which results in 236. After this, I translated this value to its "note value" based on the mapping I mentioned before. This results in BCF. (We can ommit the # in F# as it is not relevant for this challenge)
 224 Now I was looking for the notes B, C and F somewhere at the end of the sheet music - and I found them. It turned out that every second sixteenth note is relevant (doesn't matter if it's in treble or bass clef). Now also the term "trigraph" in the challenge description makes sense. Three relevant notes next to each other represent one character of the flag. I also tried this with the character `A` at the beginning of the sheet music to confirm my assumption.
 225
 226 In summary you have to do the following:
 227  - Take every second sixteenth note (Those are the relevant notes)
 228  - Form groups of three out of those relevant notes (Each group represents one character)
 229  - Convert the notes of each group to the corresponding number representation (as mentioned above, G = 0, A = 1, etc.)
 230  - Convert this 3-digit number to base 10 and look up the corresponding ASCII character in an ASCII table
 231
 232 I wrote a very small python script to do so:
 233
 234 ```python
 235 notes = ['G', 'A', 'B', 'C', 'D', 'E', 'F']
 236
 237 # Every second sixteenth note from the sheet music
 238 music = 'ABB ADB AEG AEC BCD ADG BBE BBC AGG ABD AFF BAC AFD BGD AEA ADA BCF'.replace(' ', '')
 239
 240 # Groups of three
 241 for i in range(0, len(music), 3):
 242     # Maps the notes to the number representations and converts it to a decimal integer
 243     char_code = int(str(notes.index(music[i])) + str(notes.index(music[i+1])) + str(notes.index(music[i+2])), 7)
 244     print(chr(char_code), end='') # Print the char with this character code
 245
 246 print()
 247 ```
 248
 249 Flag: `AOTW{Mus1Cal_fUN}`
 250
 251
 252 #### day-19 santa's signature (~4h)
 253 ##### Overview
 254 Given was a service to connect to. Upon connecting, it outputs a public key and it says we should sign 3 different messages with our private key (which belongs to the given public key, we don't have this one obviously). Additionaly, the python source code of this service is given.
 255
 256 ##### Attempts and Solution
 257 After taking a look at the source code, I googled what crypto library was used. Turned out it was `pycrypto`. I also looked for the source code and found it on GitHub [here](https://github.com/dlitz/pycrypto).
 258 After analyzing the source code a bit further, it was obvious that the function we have to exploit is `verify`. I looked up the source code of this function in the GitHub repo.
 259
 260 ```python
 261  def verify(self, M, signature):
 262         """Verify the validity of an RSA signature.
 263         :attention: this function performs the plain, primitive RSA encryption
 264          (*textbook*). In real applications, you always need to use proper
 265          cryptographic padding, and you should not directly verify data with
 266          this method. Failure to do so may lead to security vulnerabilities.
 267          It is recommended to use modules
 268          `Crypto.Signature.PKCS1_PSS` or `Crypto.Signature.PKCS1_v1_5` instead.
 269
 270         :Parameter M: The expected message.
 271         :Type M: byte string or long
 272         :Parameter signature: The RSA signature to verify. The first item of
 273          the tuple is the actual signature (a long not larger than the modulus
 274          **n**), whereas the second item is always ignored.
 275         :Type signature: A 2-item tuple as return by `sign`
 276         :Return: True if the signature is correct, False otherwise.
 277         """
 278         return pubkey.pubkey.verify(self, M, signature)
 279 ```
 280
 281 As you can see above, this says that this method uses textbook RSA (without padding), which means we can exploit the weaknesses of it. I looked up how the verifying of signatures works in textbook RSA. I found [this](https://people.eecs.berkeley.edu/~luca/cs276/lecture20.pdf) document of Berkely University.
 282 It basically says that a message is verified by checking if the following equation holds: $$S^e~mod~n = M~mod ~n$$ where $$S$$ is the signature, $$M$$ the message and $$n$$ and $$e$$ the integers of the public key.
 283 Trivially, this equation holds for $$M=S=0$$ and $$M=S=1$$. So now we have to find a third (different) message and signature which fulfills the equation. This isn't a problem tho, as we can extract $$n$$ and $$e$$ out of the public key (`key.e`/`key.n` in python). Now we can basically take a message (like `-1` for example) take it to the power of $$e$$ and mod $$n$$ ($$S=M^e~mod~n$$). The result of this formula is a signature $$S$$ which is valid for the message $$M$$.
 284
 285 Finally, I wrote a python script to calculate this and also to solve the challenge (using `pwntools`):
 286
 287 ```python
 288 from pwn import *
 289 from Crypto.PublicKey import RSA
 290
 291 public_key = RSA.importKey(open('key.pub', 'r').read()) # key.pub contains the public key which I copied from the output when connecting to the service
 292 msg = hex(pow(-1, public_key.e, public_key.n)) # pow(a, b, c) = a^b % c
 293
 294 r = remote("3.93.128.89", 1219)
 295 r.recvuntil("Message 1 you signed (hex encoded):")
 296 r.sendline("0")
 297 r.sendline("0")
 298 r.sendline("1")
 299 r.sendline("1")
 300 r.sendline(msg)
 301 r.sendline("-1")
 302 r.interactive()
 303 ```
 304
 305 Flag: `AOTW{RSA_3dg3_c4s3s_ftw}`