Reverse engineering a compression algorithm.
Wednesday November 3rd 2021 after maintenance done to a game by Pearl Abyss called Black Desert, an in-game API that we used to retrieve market data was moved to a CDN and in addition to this the response of the endpoints we used was changed from a string format to a binary stream, one that wasn’t readable and we at first couldn’t make any sense of.
We took this as a challenge and in this post will explain how we tackled this change and managed to turn this binary string back into a valid response.
Comparing input and output.
Since we had experience with this endpoint before the change, we had a general idea of what the output should be looking like.
Using a man-in-the-middle attack and the real in-game market, we were able to construct what we expected to be the output for several streams.
Input:
77 00 00 00 00 00 00 00 0a 00 00 00 06 00 00 00 2d 00 00 00 13 00 00 00 30 00 00 00 03 00 00 00 31 00 00 00 02 00 00 00 32 00 00 00 03 00 00 00 33 00 00 00 01 00 00 00 34 00 00 00 03 00 00 00 35 00 00 00 02 00 00 00 37 00 00 00 03 00 00 00 39 00 00 00 02 00 00 00 7c 00 00 00 78 00 00 00 0f 00 00 00 2c 00 00 00 8a 27 34 97 5a f8 0f 45 11 9a fe fe 9e f4 1eOutput:
59003-0-30019-1400000|59005-0-1202-37700000|Analyzing the entropy of the input.
Using a few of these examples helped us split the stream into two parts by looking at the entropy.
The first part we labeled as the header had recurring patterns across all the examples, and then the high entropy part seemed to be (compressed) data.
Low entropy “header” part:
77 00 00 00 00 00 00 00 0a 00 00 00 06 00 00 00 2d 00 00 00 13 00 00 00 30 00 00 00 03 00 00 00 31 00 00 00 02 00 00 00 32 00 00 00 03 00 00 00 33 00 00 00 01 00 00 00 34 00 00 00 03 00 00 00 35 00 00 00 02 00 00 00 37 00 00 00 03 00 00 00 39 00 00 00 02 00 00 00 7c 00 00 00 78 00 00 00 0f 00 00 00 2c 00 00 00High entropy “data” part:
8a 27 34 97 5a f8 0f 45 11 9a fe fe 9e f4 1eAnalyzing “header” patterns.
First we split up the header in 4 byte chunks and after doing that we started looking at the ASCII and integer representation of these segments.
Get Ghxst’s stories in your inbox
Join Medium for free to get updates from this writer.
Doing this across many examples and comparing the values against the expected output, we were eventually able to decode the following.
77 00 00 00 # int: 119 (total length)00 00 00 000a 00 00 00 # int: 10 (unique characters in output)06 00 00 00 # int: 6 (char count in decompressed / original)
2d 00 00 00 # chr: "-"13 00 00 00 # int: 19 (char count in decompressed / original)
30 00 00 00 # chr: "0"03 00 00 00 # int: 3 (char count in decompressed / original)
31 00 00 00 # chr: "1"02 00 00 00 # int 2 (char count in decompressed / original)
32 00 00 00 # chr: "2"03 00 00 00 # int: 3 (char count in decompressed / original)
33 00 00 00 # chr: "3"01 00 00 00 # int: 1 (char count in decompressed / original)
34 00 00 00 # chr: "4"03 00 00 00 # int: 3 (char count in decompressed / original)
35 00 00 00 # chr: "5"02 00 00 00 # int: 2 (char count in decompressed / original)
37 00 00 00 # chr: "7"03 00 00 00 # int: 3 (char count in decompressed / original)
39 00 00 00 # chr: "9"02 00 00 00 # int: 2 (char count in decompressed / original)
7c 00 00 00 # chr: "|"78 00 00 00 # int: 1200f 00 00 00 # int: 15 (compressed length)2c 00 00 00 # int: 44 (decompressed / original length)
Determining the compression algorithm.
Having decoded most of the header segments we were pretty confident we had enough info to determine the compression algorithm.
After a lot of research on known compression algorithms for strings we stumbled on Huffman Coding.
Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters.
This seemed most likely by looking at the header segments and seeing that character and character frequency were a core part of the compression.
