Dysfunctional Writeup (ångstromCTF 2021)

README.md

Part 1: Debugging

Load the binary into Ghidra, find these important parts:

  file_stream = fopen("/dev/urandom","r");
  flag_ctri = 0;
  while (flag_ctri < flag_len) {
    rand_3bytes = 0;
    ctr3 = 0;
    while (ctr3 < 3) {
      rand_byte = fgetc(file_stream);
      rand_3bytes = (rand_3bytes + rand_byte) * 0x100;
      ctr3 = ctr3 + 1;
    }
    padded[flag_ctri] = flag[flag_ctri] + rand_3bytes;
    flag_ctri = flag_ctri + 1;
  }

Here, the program pads each byte of the flag with 3 additional random bytes from /dev/urandom.

  fn1 = closure(0xdead,0xbeef,0xfeed,(long)lookup);
  fn2 = closure(0x1337,0xcafe,0x1234,(long)lookup);
  fn3 = compose(fn1,fn2);
  fn4 = compose(fn2,fn1);
  enc1 = map((undefined *)fn3,padded,flag_len);
  enc1 = map((undefined *)fn4,enc1,flag_len);

They left some debug symbols in! Some quick and dirty definitions:

• closure: Anonymous function
• compose: Take two functions, then an argument; apply one after the other
• map : Take a function and a collection, create a new collection by applying the function to every element

The important thing here is that map (with a non-side-effecting function) ensures that this is a block cipher on blocks of 4 bytes.

Then, replace the usage of /dev/urandom with a normal local file like ./bad_random, and start testing it a little bit.

If you try two runs of the cipher with your ./bad_random set to something like all 0xFFFFFFs;
then set to cycling 0xFF00FFs, then you might notice...

Part 2: Getting lucky

... that the cipher degenerates a little.

Say we had the character a in the flag.
It'll get padded to 0x....PQ61, where . is a placeholder for any hex digit, and P,Q are fixed hex digits, and 0x61 == ord('a')
Then, it gets encrpyed to 0x....WXYZ, where W,X,Y,Z end up being fixed hex digits too.

To see this:

Set the flag to b"abcdefghijklmnoprstuvwxyzABCDEFGHIJKLMNOPRSTUVWXYZ{_}0123456789".

Here's a run where PQ = 0xFF, and the .... are (truly) randomized:

cc349523 ef6c49b5 5c860fe8 c99fce41 f40b0422 485f93f3 fc347d56 f8ee5521 2defa69 94fc1e63 5bc3aec0 5a51a055 76c0073c 1908ed05 40fb95d6 e104f89a 45a888e7 9d0ce93d dbf2c822 e225990a d4035ba8 d24c5904 2604d646 7a2c1c84 395eed9 61f055cf 79134bc1 4c78a725 ac914346 46fee863 ffd82741 cff57e37 66eefe8d 51d79362 aa469e81 f8cdfed1 b94f18fa 77ec6ed0 4a1c9331 2a3f9748 e7f7c166 cda57abf c3febbd5 712e5f02 c01ac2dd 7253963a 2be355ae 8c72a68a 5dd2d41a 81925d42 388e0af8 1ba062a8 6c81b494 4016b5d1 c4ced765 e81e9e03 75cffbd 7e15b89f 3206c64b b62f0bee 8900320b 6420d3f 144ef3f8

Here's another run with a different .... randomization, but with PQ = 0xFF still:

7c069523 a2f449b5 b6300fe8 f395ce41 62f10422 518b93f3 a4267d56 ecac5521 ef7bfa69 972a1e63 c96eaec0 52bfa055 dc1073c ccd5ed05 6b5a95d6 faf2f89a cf2f88e7 a6cce93d 392ec822 abc6990a b89f5ba8 c9ad5904 7254d646 87f91c84 a9c7eed9 a5055cf fa554bc1 175a725 f13c4346 4ba0e863 a8b32741 fd827e37 6dc7fe8d af9e9362 ac1d9e81 510cfed1 8b1818fa 9c996ed0 d36a9331 c6aa9748 c98dc166 6d9e7abf facdbbd5 ac355f02 bde6c2dd 35d3963a 25c355ae fb16a68a c752d41a b1fa5d42 2a430af8 d16e62a8 eed6b494 ffd6b5d1 4e27d765 97559e03 790cffbd a7c9b89f a7a4c64b da800bee b44c320b 44100d3f cef4f3f8

As long as PQ is fixed, the WXYZ (last 2 bytes) are always the same.

As a sanity check, here's a run with PQ = 3F:

5ab9e4ce 24283322 f25cb6fc 4b71f547 b5d71702 c91a82ba e56022cd 5aa08b6c 2695243 873d77d2 5a70313f 7d35c8d 1c127ece a82ac33a 284d3975 508f397d aa99a16 66f5dfdc af93ead 5e17f2e5 2f9b6e79 9966162f a4ac76ee ca63571b b4a3c851 8e06bff7 803eeaad 9db934a9 c450eaf9 153f4c15 2f380f92 6a62ee69 cdc9b53d e04170a4 26d63b30 71f143e7 1277165a ae869bd1 4fa4487f 213a274c ce9b76f3 2c79e715 904834e0 1ca5abd0 f9e0c238 52e33ab2 1518b34 ac427914 569c95fd 27a1dd80 cdd37f7c ef744b3d 71623298 c970fe65 c0d4f07b 337c4480 8e407c60 ff7f926e d81e62a0 82f6fc56 e4041cbf 5d3d1684 6318d5f1

Completely different than the above, as expected. The last byte of padding IS significant.

Now, we just need to build a table of all ciphertexts of PQRS, for each byte PQ and each printable ascii RS.

rainbow_tbl.py

from random import randrange as rand
from pwn import *
from collections import defaultdict
import itertools as it

urandom_replacement = "./bad_random"

flag = "abcdefghijklmnoprstuvwxyzABCDEFGHIJKLMNOPRSTUVWXYZ{_}0123456789"

def rand_bytes(sig):
  return [(rand(0xFFFF) * 0x100 + sig).to_bytes(3, 'big') for _ in range(len(flag))]

with open("flag", 'w') as f: f.write(flag)

def go(cur):
  global prog
  with open(urandom_replacement, 'wb') as f: f.write(b"".join(rand_bytes(cur)))

  prog = process(["dysfx_EDITED"]) # the given binary, but edited to use `./bad_random` instead of `/dev/urandom`
  ret = prog.recv()
  prog.close()

  ret = ret.decode().split()[:len(flag)]
  ret = [(w[-4:], c) for w, c in zip(ret, flag)]
  return ret

rets = [go(cur) for cur in range(0x100)]

enc_raw = "5400f172 949c5165 c6bc4607 c621d63f c20c0970 f2b3f53c aabb67f9 fe0e7abb 6ae46e55 dd212d25 fb681ccb 2ef2f900 75dbefc4 a4e3a8dd 3c6ad4ea 2fa95919 4e6d7b44 b66bacf2 a0b7b0a3 ee57fd81 452a0ba4 a05d8829 05911680 0439efce 75346c63 e2e8d40c 82551eb7 15f70f1 3365c553 4d88f5f1 1ea5b8ab faa1a4ae 91567996 13d89930 6b159c81 35779a3c 5d8573aa 075908ec 0b902a84 1501d8a0"

enc = [w[-4:] for w in enc_raw.split()]

unhash = defaultdict(list)
for ln in rets:
  for k,v in ln:
    unhash[k].append(v)

print(
  *map(''.join, it.product(*[unhash[c] or ['?'] for c in enc]))
)