beVX Conference Challenge
Credit to Author: SSD / Noam Rathaus| Date: Sun, 04 Mar 2018 07:27:05 +0000
During the event of OffensiveCon, we launched a reverse engineering and encryption challenge and gave the attendees the change to win great prizes.
The challenge was divided into two parts, a file – can be downloaded from here: https://www.beyondsecurity.com/bevxcon/bevx-challenge-1 – that you had to download and reverse engineer and server that you had to access to have a running version of this file.
The challenge could not have been resolved without access to the server as the encryption key that you were supposed to extract was only available in the running version on the server.
We had some great solutions sent to us, some of them were posted below – some arrived after the deadline, and some were not eligible as their solution was incomplete, but in the end we had three winners.
First place winner got an all paid, flight and hotel, and entry to our security conference beVX in September, second place prize winner got flight and entry to our security conference and the third place winner got a free entry to our event.
Challenge Source Code
If you don’t want to get a solution or hints to how to solve it – don’t continue reading – you have been warned 🙂
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 | #include <iostream> #include <thread> #include <chrono> #ifdef _WIN #define IMPORT extern __declspec(dllimport) #else #define IMPORT extern #endif IMPORT size_t encrypt(size_t num); IMPORT size_t decrypt(size_t num); IMPORT const char private_key[]; IMPORT const size_t private_key_length; IMPORT const size_t number_of_rows; class Algo { public: static const size_t ROWS = 0x20; static const size_t COLS = 0x20; char table[ROWS][COLS] = { {0} }; char * password; union { struct { size_t unused : 3; size_t init : 1; } s1; size_t number_of_rows : 5; } u1 = {}; struct { size_t row : 7; int i : 7; char exponent[COLS]; size_t x; } expo_data = {}; static void StoreNumber(char * row, size_t num, bool enc = true) { if (enc) num = encrypt(num); for (int i = COLS – 1; i >= 0; i—) { row[i] = num % 2; num = num / 2; } } static void RetrieveNumber(char * row, size_t& num) { num = 0; for (int i = 0; i < COLS; i++) { num = num * 2 + row[i]; } num = decrypt(num); } void Calculate_next() { expo_data.x = expo_data.x * expo_data.x; if (expo_data.exponent[expo_data.i++] == 1) { size_t num = 0; RetrieveNumber(table[expo_data.row], num); expo_data.x = expo_data.x * num; } } void End_calc() { StoreNumber(table[expo_data.row], std::hash<size_t>()(expo_data.x)); u1.s1.init = 0; u1.s1.init = false; } void InitializeExp(size_t row1, size_t row2) { std::copy(table[row2], table[row2] + COLS, expo_data.exponent); expo_data.i = 0; while (expo_data.exponent[expo_data.i] == 0 && expo_data.i < COLS) { ++expo_data.i; } expo_data.x = 1; expo_data.row = row1; } void Multiply(size_t row1, size_t row2, size_t row3) { size_t num1 = 0, num2 = 0, num3 = 0; RetrieveNumber(table[row1], num1); RetrieveNumber(table[row2], num2); num3 = num1 * num2; StoreNumber(table[row3], num3); } void Add(size_t row1, size_t row2, size_t row3) { size_t num1 = 0, num2 = 0, num3 = 0; RetrieveNumber(table[row1], num1); RetrieveNumber(table[row2], num2); num3 = num1 + num2; StoreNumber(table[row3], num3); } void Sub(size_t row1, size_t row2, size_t row3) { size_t num1 = 0, num2 = 0, num3 = 0; RetrieveNumber(table[row1], num1); RetrieveNumber(table[row2], num2); num3 = num1 – num2; StoreNumber(table[row3], num3); } void Divide(size_t row1, size_t row2, size_t row3) { size_t num1 = 0, num2 = 0, num3 = 0; RetrieveNumber(table[row1], num1); RetrieveNumber(table[row2], num2); if (num2 == 0) { return; } num3 = num1 / num2; StoreNumber(table[row3], num3); } bool ValidateRowIndex(size_t row) { return (row < u1.number_of_rows); } void Encryption() { if (expo_data.i > COLS – 1) { End_calc(); return; } char op = 0; std::cout << “Continue Encryption? (y/n)” << std::endl; std::cin >> op; switch (op) { case ‘y’: case ‘Y’: Calculate_next(); break; case ‘n’: case ‘N’: End_calc(); break; } return; } void CopyTable(char t1[ROWS][COLS], char t2[ROWS][COLS]) { for (unsigned int i = 0; i < ROWS; i++) { size_t num = 0; RetrieveNumber(t1[i], num); StoreNumber(t2[i], num, false); } } void PrintTable() { #ifdef DEBUG char t[ROWS][COLS] = { 0 }; CopyTable(table, t); size_t col_size = 0x20; std::cout << ” “; for (int i = 0; i < col_size; i++) { std::cout << “–“; } std::cout << std::endl; for (int i = 0; i < u1.number_of_rows; i++) { std::cout << “<|”; for (int j = 0; j < ROWS; j++) { std::cout << (char)((‘0’ + t[i][j])) << “|”; } std::cout << “>” << std::endl; } std::cout << ” “; for (int i = 0; i < col_size; i++) { std::cout << “–“; } std::cout << std::endl; #endif } void Init() { #ifdef _DEBUG for (unsigned int i = 0; i < ROWS; i++) { StoreNumber(table[i], 0); } #endif } void MainLoop() { bool done = false; Init(); password = table[number_of_rows + 2]; std::copy(&private_key[0], &private_key[0] + private_key_length, password); password[private_key_length – 1] |= 1; u1.number_of_rows = number_of_rows; while (!done) { if (u1.s1.init) { Encryption(); continue; } size_t op = 0; std::cout << “Please choose your option:” << std::endl; std::cout << “0. Store Number” << std::endl; std::cout << “1. Get Number” << std::endl; std::cout << “2. Add” << std::endl; std::cout << “3. Subtract” << std::endl; std::cout << “4. Multiply” << std::endl; std::cout << “5. Divide” << std::endl; std::cout << “6. Private Key Encryption” << std::endl; std::cout << “7. Binary Representation” << std::endl; std::cout << “8. Exit” << std::endl; std::cin >> op; if (!std::cin) { done = true; break; } switch (op) { case 0: { size_t row = 0; size_t num = 0; std::cout << “Enter row and number” << std::endl; std::cin >> row >> num; if (!std::cin) { done = true; break; } if (!ValidateRowIndex(row)) { std::cout << “Row number is out of range” << std::endl; break; } StoreNumber(table[row], num); break; } case 1: { size_t row = 0; size_t num = 0; std::cout << “Enter row” << std::endl; std::cin >> row; if (!std::cin) { done = true; break; } if (!ValidateRowIndex(row)) { std::cout << “Row number is out of range” << std::endl; break; } RetrieveNumber(table[row], num); std::cout << “Result is “ << num << std::endl; break; } case 2: { size_t row1 = 0, row2 = 0, row3 = 0; std::cout << “Enter row of arg1, row of arg2 and row of result” << std::endl; std::cin >> row1 >> row2 >> row3; if (!std::cin) { done = true; break; } if (!(ValidateRowIndex(row1) && ValidateRowIndex(row2) && ValidateRowIndex(row3))) { std::cout << “Row number is out of range” << std::endl; break; } Add(row1, row2, row3); break; } case 3: { size_t row1 = 0, row2 = 0, row3 = 0; std::cout << “Enter row of arg1, row of arg2 and row of result” << std::endl; std::cin >> row1 >> row2 >> row3; if (!std::cin) { done = true; break; } if (!(ValidateRowIndex(row1) && ValidateRowIndex(row2) && ValidateRowIndex(row3))) { std::cout << “Row number is out of range” << std::endl; break; } Sub(row1, row2, row3); break; } case 4: { size_t row1 = 0, row2 = 0, row3 = 0; std::cout << “Enter row of arg1, row of arg2 and row of result” << std::endl; std::cin >> row1 >> row2 >> row3; if (!std::cin) { done = true; break; } if (!(ValidateRowIndex(row1) && ValidateRowIndex(row2) && ValidateRowIndex(row3))) { std::cout << “Row number is out of range” << std::endl; break; } Multiply(row1, row2, row3); break; } case 5: { size_t row1 = 0, row2 = 0, row3 = 0; std::cout << “Enter row of arg1, row of arg2 and row of result” << std::endl; std::cin >> row1 >> row2 >> row3; if (!std::cin) { done = true; break; } if (!(ValidateRowIndex(row1) && ValidateRowIndex(row2) && ValidateRowIndex(row3))) { std::cout << “Row number is out of range” << std::endl; break; } Divide(row1, row2, row3); break; } case 6: { size_t row1 = 0, row2 = 0; u1.s1.init = 1; std::cout << “Enter row of message, row of key” << std::endl; std::cin >> row1 >> row2; if (!std::cin) { done = true; break; } if (!(ValidateRowIndex(row1) && ValidateRowIndex(row2))) { u1.s1.init = 0; std::cout << “Row number is out of range” << std::endl; break; } InitializeExp(row1, row2); break; } case 7: { PrintTable(); break; } case 8: { done = true; break; } default: { std::cout << “Unknown option.” << std::endl; break; } } } } }; Algo a; int main() { a.MainLoop(); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | .PHONY: all clean CCFLAGS=–std=c++11 –s –Os OUT_DIR=$(PWD)/build/ all: out_dir bevx_cha1 bevx_lib.so: bevx_lib.o g++ –shared –o build/bevx_lib.so build/bevx_lib.o bevx_lib.o: out_dir bevx_lib.cpp g++ $(CCFLAGS) –fPIC –c bevx_lib.cpp –o build/bevx_lib.o bevx_cha1: bevx_cha1.cpp bevx_lib.so g++ –o build/bevx_cha1 $(CCFLAGS) bevx_cha1.cpp –L$(OUT_DIR) –l:./bevx_lib.so –lstdc++ out_dir: mkdir –p $(OUT_DIR) clean: rm –rf build/ |
Solution (Tim)
The “encryption” routine operates on 1 bit of the key at a time, modifying an internal ongoing value each step. If the bit is a zero then this value is squared. If the bit is a one then the value is squared and then further multiplied by the value of the “message” that is selected to encrypt.
Because you can stop the encryption at any point, you can encrypt progressively more of the message, allowed each bit to be extracted by comparing the result with the result for the previous number of bits.
Script output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | [+] Connecting to x.x.x.x on port 22: Done [+] Opening new channel: ‘shell’: Done [*] Bit 0 result: 0x1 [*] Key: 0 [*] Bit 1 result: 0x11 [*] Key: 01 [*] Bit 2 result: 0x1331 .... [*] Bit 28 result: 0xb11e13b1 [*] Key: 01100010011001010101011001011 [*] Bit 29 result: 0x60ffc061 [*] Key: 011000100110010101010110010110 [*] Bit 30 result: 0x91cfa4c1 [*] Key: 0110001001100101010101100101100 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | #!/usr/bin/env python2 # beVX Challenge 1 exploit script # – timpwn import pwn # pip install pwn import logging remote = True # pwn.context.log_level = logging.DEBUG def set_value(row, value): r.sendline(“0”) r.sendline(str(row)) r.sendline(str(value)) r.readuntil(prompt) def get_value(row): r.sendline(“1”) r.readline() r.sendline(str(row)) r.readuntil(“Result is “) response = r.readline() value = int(response) r.readuntil(prompt) return value def encrypt(message_row, key_row, bit_count): r.sendline(“6”) r.readline() r.sendline(str(message_row)) r.sendline(str(key_row)) continue_prompt = “Continue Encryption? (y/n)” r.readuntil(continue_prompt) r.readline() for i in range(bit_count): r.sendline(“y”) response = r.readline().strip() # The remote system echoes our input back if response == “y”: response = r.readline().strip() if response != continue_prompt: pwn.log.debug(“No more encryption at bit {}”.format(i)) r.readuntil(prompt) return r.sendline(“n”) r.readuntil(prompt) def decode_key_row(row): result = “” previous_value = 1 # Get data out for incremental encryption key bits p = pwn.log.progress(“Reading row {}”.format(row)) for bit in range(0, 32): # Encrypt 0x11 using the key in the row specified p.status(“Getting bit {}”.format(bit)) multiplier = 0x11 set_value(0, multiplier) encrypt(0, row, bit) v = get_value(0) pwn.log.debug(“Bit {} result: 0x{:x}”.format(bit, v)) # See if our multiplier has been used, which indicates that # the key has a “1” in this position previous_squared = previous_value * previous_value if v == previous_squared & 0xffffffff: result += “0” elif v == (previous_squared * multiplier) & 0xffffffff: result += “1” elif v == previous_value: # This means that we’ve gone past the end of the key, # so now we know that the first N bits were zeroes break else: pwn.log.warn(“Unexpected value!”) result += “?” pwn.log.debug(“Progress: “ + result) previous_value = v # Add the zeroes that we didn’t get to see at the start of the key result = (“0” * (32–len(result))) + result p.success(“Got row, value: “ + result) return result def connect(): if remote: ssh = pwn.ssh(user=“challenge”, host=“x.x.x.x”, password=“challenge”) r = ssh.shell() prompt = “8. Exitrn” else: r = pwn.process(“./cha1”) prompt = “8. Exitn” return (r, prompt) r, prompt = connect() r.readuntil(prompt) # We can get rows 18-20 ok, after which no encryption cycles are possible – # this is most likely because the rows are all zeroes. rows_bits = list() for row in range(18, 21): partial_key = decode_key_row(row) rows_bits.append(partial_key) # Pad out and combine the key parts combined = “” for r in rows_bits: padded = (“0” * (32 – len(r))) + r print “Row value:”, hex(int(padded, 2)) combined += “{:04x}”.format(int(padded, 2)) pwn.log.info(“Key: “ + repr(combined.decode(“hex”))) |
Solution (mongo)
Key: “beVX Sep 20!”
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | import operator import ctypes, sys, re, os from pwn import * from pwnlib.tubes.ssh import * remote = 1 if not remote: conn = ssh(host=‘192.168.1.5’, user=‘cha1’, password=‘cha1’) else: conn = ssh(host=‘x.x.x.x’, user=‘challenge’, password=‘challenge’) s = conn.shell() s.sendall = s.send s.recvuntil(“rn”) s.recvuntil(“8. Exit”) def store(idx, val): s.sendall(“0n%dn%dn” % (idx, val)) s.recvuntil(“8. Exit”) def get(idx): s.sendall(“1n%dn” % (idx)) s.recvuntil(“Result is “) v = int(s.recvuntil(“rn”)) s.recvuntil(“8. Exit”) return v def privateenc(msg_idx, key_idx): s.sendall(“6n”) s.recvuntil(“Enter row of message, row of keyrn”) s.sendall(“%dn%dn” % (msg_idx, key_idx)) s.recvuntil(“n”) s.recvuntil(“n”) def reset(): for i in range(16): store(i, 0) def get_key_part(key_idx): privateenc(16, key_idx) times = 0 “”” check the number of bits left in this key part “”” for i in range(32): v = s.recvuntil(“rn”).strip() #print “<<“, v if “Continue Encryption” in v: s.sendall(“yn”) s.recvuntil(“n”) times += 1 else: break s.recvuntil(“8. Exit”) print “key %d bits = %d” % (key_idx, times) num_bits = times “”” now, get key_part keep in mind result is multiplied by itself at every step if key bit is 1, we also multiply by 3 (baseval) “”” baseval = 3 pos = 32 – num_bits – 1 skip = 0 cur_val = 1 key_part = 0 for i in range(32 – num_bits, 32): store(0, baseval) privateenc(0, key_idx) val_if_1 = ((cur_val * cur_val) * baseval) & 0xFFFFFFFF val_if_0 = ((cur_val * cur_val)) & 0xFFFFFFFF times = 0 for i in range(skip + 1): v = s.recvuntil(“n”).strip() s.sendall(“yn”) s.recvuntil(“n”) v = s.recvuntil(“n”).strip() if “Continue” in v: s.sendall(“nn”) s.recvuntil(“n”) s.recvuntil(“8. Exit”) res = get(0) #print “res=”, res if res not in [val_if_0, val_if_1]: print res print [val_if_0, val_if_1] raise “Fail” key_part = (key_part << 1) | (1 if res == val_if_1 else 0) cur_val = res skip += 1 print bin(key_part), “%08X” % key_part, (“%08X” % key_part).decode(‘hex’) for i in range(18, 22): get_key_part(i) s.close() |
Solution (Dmitry)
Secret key is “beVX Sep 20!”
Solution:
It is easy to detect that valid row numbers are 0..15 (thanks to error messages).
“Private Key Encryption” handling routine sets bit 3 (& 8) of number of rows thus allowing access to rows 16..23. Key is stored in rows 18..20. Each row represents 32-bit value.
Encryption is just calculation of pow(msgRow, keyRow, 1<<32)
Fastest method (using timing attack) allows recovering of row value in single pass. Each non-zero bit in exponent requires additional call to decrypt(), that causes sensitive delay.
But due to difficulties in automation of SSH interactive communication I derives each row in 3 steps:
1. Find number of bits if exponent (by counting “Continue Encryption? (y/n)” prompts)
2. Find highest 16 bits of exponent (by stopping encryption 16 bits before its end and brute-forcing 16 bit exponent value)
3. Find complete exponent (by brute-forcing lowest 16 bits)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | import sys, subprocess, time class SSH_beVX(object): EMSG = “8. Exit” def send_command(self, cmd): self.proc.stdin.write(cmd + “n”) self.proc.stdin.flush() ln = self.proc.stdout.readline() assert ln.startswith(cmd) self.started = time.clock() def read_line(self): return self.proc.stdout.readline() def read_until(self, msg=EMSG): lines = [] while True: lines.append(self.read_line()) if lines[–1].startswith(msg): return lines def write_row(self, row, val): self.send_command(“0”) self.read_line() # Enter row and number self.send_command(“%d %d” % (row, val)) self.read_until() # Please choose your option: def read_row(self, row): self.send_command(“1”) self.read_line() # Enter row self.send_command(“%d” % row) ln = self.read_line() # Result is assert ln.startswith(“Result is”) self.read_until() # Please choose your option: return int(ln.split()[–1]) def measure_crypt(self, keyRow, msgRow=0, val=3): self.write_row(msgRow, val) self.send_command(“6”) self.read_line() # Enter row of message, row of key self.send_command(“%d %d” % (msgRow, keyRow)) exp = 0 while True: ln = self.read_line() delta = time.clock() – self.started bit = 1 if delta > 0.7 else 0 exp = (exp*2) + bit sys.stderr.write(“r%8X” % exp) if not ln.startswith(“Continue Encryption? (y/n)”): break self.send_command(“Y”) self.read_until() # Please choose your option: res = self.read_row(msgRow) if res != pow(val, exp, 1<<32): exp ^= 1 if res != pow(val, exp, 1<<32): raise Exception(“Can’t find key[%d]” % keyRow) s = (“%08X” % exp).decode(“hex”) sys.stderr.write(“r%08X [%s]n” % (exp, s)) return s def __init__(self, host, username, password, port=22): args = [“plink”, “-l”, username, “-pw”, password, “-P”, “%d” % port, host] self.proc = subprocess.Popen(args, stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE, bufsize=1) def main(): ssh = SSH_beVX(“x.x.x.x”, “challenge”, “challenge”) ssh.read_until() # Please choose your option: r = [ssh.measure_crypt(keyRow, 0, 7) for keyRow in xrange(18, 21)] print “Key is [%s]” % “”.join(r) # “beVX Sep 20!” ssh.send_command(“8”) if __name__==“__main__”: main() |
