Question

I'm trying to reverse engineer a binary file format, but it has no magic bytes, and no specific extension. I can influence only a single aspect of the file: a short string. By trying different strings, I was able to figure out how data is stored in the file. It seems that the whole file uses some sort of simple encoding. I hope that finding the exact encoding allows me to narrow down my search for the file format. I know the file is generated by a Windows program written in C++.

Now, after much trial-and-error, I found that some sections of the file are encoded in runs. Each run starts with a byte that indicates how many bytes will follow and where the data is retrieved.

  • 000ddddd (1 byte)
    Take the following (ddddd)+1 bytes from the encoded data.
  • 111····· ···ddddd ···bbbbb (3 bytes)
    Go back (bbbbb)+1 bytes in the decoded data, and take the next (ddddd)+9 bytes from it.
  • ddd····· ··bbbbbb (2 bytes)
    Go back (bbbbbb)+1 bytes in the decoded data, and take the next (ddd)+2 bytes from it.

Here's an example:

This is the start of the file, with the UTF-16 string abracadabra encoded in it:

First 224 bytes of the file

  .     .  .  a  .  b  .  r     .  .  c     .  .  d     .  €  .
  0C 20 03 04 61 00 62 00 72 20 05 00 63 20 03 00 64 20 03 80 0D

To decode the string:

  0C                      number of Unicode chars: 12 (11 chars + \0)
  20 03       . . .       ??
  04                      next 5
  61 00       a .
  62 00       b .
  72          r
  20 05       . a .       back 6, take 3
  00                      next 1
  63          c
  20 03       . a .       back 4, take 3
  00                      next 1
  64          d
  20 03       . a .       back 4, take 3
  80 0D       b . r . a . back 14, take 6

This results in (UTF-16):

  a  .  b  .  r  .  a  .  c  .  a  .  d  .  a  .  b  .  r  .  a  .
  61 00 62 00 72 00 61 00 63 00 61 00 64 00 61 00 62 00 72 00 61 00

However, I have no clue as to what encoding/compression algorithm this might be. It looks like some variant of LZ that doesn't use a dictionary (like LZ77), but so far I haven't been able to find any algorithm that matches this description. I'm also not sure whether the entire file is encoded like this, or only portions of it.

Do you know this encoding? Or do you have any hints for things I might look for in the file to identify the encoding?

Was it helpful?

Solution

After your edit I think it's LZF with the following differences to your observations:

  • The magic header and indication of compressed vs uncompressed has been removed in your example (not too surprising if it's embedded in a file).
  • You took the block length as one byte, but it is two bytes and big-endian, so the prior 0x00 is part of the length, which still works.

OTHER TIPS

Could be NTFS compression, which is LZNT1. This idea is supported by the platform and the apparent 2-byte structure, along with the byte-alignment of the actual data.

The following elements are specific to this algorithm.

Chunks: Segments of data that are compressed, uncompressed, or that denote the end of the buffer.

Chunk header: The header for a compressed or uncompressed chunk of data.

Flag bytes: A bit flag whose bits, read from low order to high order, specify the formats of the data elements that follow. For example, bit 0 corresponds to the first data element, bit 1 to the second, and so on. If the bit corresponding to a data element is set, the element is a 2-byte compressed word; otherwise, it is a 1-byte literal value.

Flag group: A flag byte followed by zero or more data elements, each of which is a single literal byte or a 2-byte compressed word.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top