4 ms·
Wow, I had a very similar LZSS related experience just a few weeks ago reverse-engineering a VW ECU, although my process didn't end up being as painful. Through
by bri3d 8y ago
Wow, I had a very similar LZSS related experience just a few weeks ago reverse-engineering a VW ECU, although my process didn't end up being as painful. Through luck (and no skill of my own, really), I chose to approach the decompression process by analyzing the data rather than disassembling the decompression routine. LZSS compressed data appears more compressed/garbled as the file goes on as the previous contents of the file are used as the dictionary for compression. LZSS basically works by encoding what I'll call a "copy command" - a series of bits which tell the decompressor whether to copy subsequent bytes from the "dictionary" (which is an offset into the previous content of the file) or to copy the bytes verbatim. Thankfully, the beginning of my file didn't have much repetition for the first 20-30 bytes, so I was able to recognize the periodically-zero bitfield "commands." Next I was able to recognize as they became nonzero (as items were available in the dictionary) and begin to see how the bitfield drove the decompressor. Doing this again, I could spot LZSS from orbit, but having never seen it (and having no versing or background in compression algorithms), I ended up putting together enough Google terms around "dictionary compression copy bitfield" to get exceptionally lucky (again!) and land on a page about LZ77, which took me to enough example implementations to allow me to rapidly implement a decompressor.
- souprock 8y agoI've dealt with a few. One turned out to be LZRW3, kind of like LZSS but with the 12-bit string source being a hash table index. That was totally reverse engineered from staring at hex bytes, and then later we found out the identity of the compression algorithm. Another was never discovered. It was one of two compression algorithms used by VxWorks, as part of transitioning between boot stages. My solution was to put the entire RAM content into an ELF file (including all of VxWorks) as one big section, then hack it up to run as a Linux binary. I thus made a decompression program. Writing an emulator is also a great choice. I do that a lot.
- userbinator 8y agoA wide background experience on computing in general helps greatly for RE; in this case the specific variant of LZ that's used is categorised by an old document I have as "LZ 12/4" (4K sliding window, 16-bit match offsets split into 12 and 4 for offset and length) which was very common in the late 80s/early 90s. A decompressor for it fits in a few dozen bytes of x86, which certainly helped its popularity, and the simplicity meant it was extremely fast. Unfortunately Google's forgetfulness is infuriating, since the only reference to this variant name I could find is a previous comment I made here about compression algorithms: https://news.ycombinator.com/item?id=14965064 https://news.ycombinator.com/item?id=14965064