Hex and Base64 Encoding Puzzler

This puzzler focused on two forms of encoding for arbitrary binary data: Hex encoding and Base64.

The supplied file was hex-encoded. Decoding it yielded three 16-byte chunks. The first two chunks were ASCII consisting of Base64-encoded text - the first 2/3 of the flag.

The third chunk, after decoding the hex, was not ASCII but rather binary garbage. Solving this part was the hardest. The third part of the flag could be found by XOR-ing the first two encoded parts with the third part.

There was a small hint: the last byte was a newline. Most Unix text files end with a newline, and parts 1 and 2 end with the same character (‘=’). This means that the last character of the third part is unchanged by the XOR operation.

Tips and Techniques

The supporting-files tarball has the creation script and a solve script which show several different techniques for working on this sort of challenge.

Shell Utilities

Head and Tail

The shell contains a number of utilities that cover some of the basic operations of text or binary files. head and tail are very useful for splitting files. The create.sh script uses head and tail for this purpose.

head -c 10 flag.txt : Select the first 10 characters of the file
tail -c +22 flag.txt : Biginning with the 11th character, select the rest of the file
tail -c +11 flag.txt | head -c 11 : Combining the first two, this selects 11 characters from the file, beginning with the 11th character.

The normal use for head and tail is of course separating based on lines. Replacing the -c flag with -n causes the utilities to work on lines, rather than characters.

xxd

xxd without any arguments makes a nice hex dump of a file, showing offsets, formatted hex, and ASCII. However, it can also be used encode and decode plain hex dumps.

xxd -p file simply creates a plain hex encoding of the file
xxd -r -p file.hex decodes plain hex
xxd -p file | xxd -r -p encodes then decodes the file - full cycle

Misc. Tools

There are other tools for various encodings. base64 is used in this puzzler. rot13 and caesar show up from time to time, to perform Caesar ciphers.

Scripting language

While using shell utilities is a quick and basic way to take a look at encoded text, it lacks power and customizability. At that point, it becomes necessary to drop to a real scripting language.

The create.sh script is a good example of this. While most of the operations were done using shell utilities, there isn’t a good way to XOR two strings in a shell, so that part is kicked off to a Ruby script. Additionally, while it is possible, some operations are fairly arcane in the shell. For example, array slicing is much nicer than splitting with head and tail.

Scripting Language Tricks

The solve.rb script was written entirely in Ruby. It is fairly easy to read, but these are some of the tricks used in the script.

Decoding Hex

hex.scan(/../).map{|c| c.hex} Ruby doesn’t have a standard function to encode or decode hex, so decoding the initial file requires scanning two chars at a time and decoding those two chars as a hexadecimal number. This yields an array of numbers, which is the byte array representing the decoded file.

Other languages have convenience functions to make hex encoding and decoding very easy.

Splitting files

Once the file is represented as either a char array or a byte array (in the case of solve.rb, it is a byte array), array slicing makes splitting it into parts very easy.

` p1 = puzzler[0..15] p2 = puzzler[16..31] p3 = puzzler[32..47] `

Most languages support array slicing (or string slicing) of some sort.

Base64 and other encodings

This is just a matter of using the right language features/libraries for the encoding in question. Base64 is very easy in Ruby, and since it is ubiquitous, most languages should support it as well.

Base64.decode64(str)

Zipping and Mapping

map and zip are two higher-order functions common in high-level languages.

The map operation is used to convert an array by performing the same operation on every element of the array. For example, it could be used to add 1 to every number in an array of ints.

[1, 2, 3].map{|e| e + 1} yields the array [2, 3, 4]

The zip operation takes two arrays of equal length “zips” them together, yielding an array of pairs.

[1, 2, 3].zip([4, 5, 6]) produces [[1, 4], [2, 5], [3, 6]].

The general form of “zipping” arrays can be extended beyond two arrays yielding pairs to three arrays yielding triples, up to any number of arrays yielding N-tuples.

Combining “zipping” and “mapping” is how XOR-ing one or more strings together is done.

plain3 = p3.zip(p1, p2).map{|b1, b2, b3| b1 ^ b2 ^ b3}.pack('C*')

This takes the p3 array, zips it with p1 and p2 to get an array of triples. It will iterate through the array of triples, XORing all three bytes together to build a final array of bytes.

pack('C*') is just Ruby magic to turn a byte array into a string.

All of these operations are possible in Python, and probably other languages as well.

Interactivity

Interactivity isn’t just for the shell. Ruby (and Python) have interactive interpreters available. You can test it out by running irb and then trying out the solve.rb script one line at a time - or even breaking the larger one-liners into multiple commands to see how these basic data-manipulation methods can be used.

Other Tools

CyberChef is a tool made for solving this sort of challenge. It has blocks for most of these operations (encoding, hex, string XOR…). It also gives immediate feedback as the recipe is modified.