Some Assembly Required 3 picoCTF 2021 Solution

Description

1. Step 1Decompile and locate the shuffle function
   Convert the WASM to WAT and find the function that reorders input characters before comparison. Look for a series of indexed memory loads and stores that move characters to non-sequential positions.
   bash

   wasm2wat xSAR3.wasm -o xSAR3.wat

   Copied!

   bash

   wc -l xSAR3.wat  # Check size

   Copied!

   bash

   grep -n 'store\|load\|offset' xSAR3.wat | head -60

   Copied!
   Learn more

   This challenge adds a permutation layer on top of the XOR encoding. Before comparing your input to the expected value, the WASM function rearranges the input characters according to a fixed permutation table. You need to reverse the permutation: figure out where each output character came from in the input, then reconstruct the correct input order.

   In WAT, a permutation looks like: load from input offset X, store to output offset Y, for many different (X, Y) pairs. By tracing all these (X, Y) pairs, you build the permutation mapping. The inverse permutation maps Y back to X, telling you what character should be at each input position.

2. Step 2Extract the permutation table
   Parse the WAT to extract all (source_offset, dest_offset) pairs from the shuffle function. Build the forward permutation array, then compute its inverse.
   python

   python3 - <<'EOF'
   import re
   
   with open('xSAR3.wat', 'r') as f:
       wat = f.read()
   
   # Tested regex for WAT permutation: a store8 to dest paired with a load8_u from src.
   # DOTALL handles multi-line spans between the two instructions.
   pairs = re.findall(
       r'i32.store8 offset=(d+).*?i32.load8_u offset=(d+)',
       wat,
       re.DOTALL,
   )
   
   # Forward permutation maps src -> dest: a byte read from offset src is written to dest.
   # Inverse: kept[dest] = src. To reconstruct the input given the expected (post-shuffle)
   # bytes, walk the inverse: input[src] = expected[dest].
   forward = {int(src): int(dest) for dest, src in pairs}
   inverse = {dest: src for src, dest in forward.items()}
   
   expected = b"..."  # bytes from the data segment (the value compared against)
   out = bytearray(len(expected))
   
   # Edge case: positions not covered by the permutation are identity-mapped.
   for i in range(len(expected)):
       src = inverse.get(i, i)
       out[src] = expected[i]
   
   flag = bytes(out).decode('ascii', errors='replace')
   print(flag)
   
   # Validate
   assert flag.startswith('picoCTF{') and flag.endswith('}'), f"Bad flag: {flag!r}"
   EOF

   Copied!
   Learn more

   Permutation ciphers rearrange the positions of characters without changing the characters themselves. They are trivially reversible: if the permutation maps input position 3 to output position 7, then the inverse maps output position 7 back to input position 3. Applying the inverse permutation to the shuffled expected value gives you the original flag.

   This is why permutation alone provides zero cryptographic security - it is just a transposition cipher, and transposition ciphers have been broken for centuries. Combined with XOR (the previous challenge), you get two layers of weak obfuscation, but reversing them in sequence (XOR first, then inverse permutation, or the other way depending on the order in the WASM) recovers the flag.

Flag

A permutation (shuffle) of input characters before comparison is a transposition cipher - trivially reversible by computing and applying the inverse permutation.