19-Apr-2016: Bug in LZHuf.c by Haruyasu Yoshizaki

There is a highly popular LZHuf compressor/decompressor written by Haruyasu Yoshizaki as early as in 1988.

Andrey "herm1t" Baranovich (owner of VX Heaven website) found that many variations of this source code has a bug (archived):

...

unsigned freq[T + 1];	/* frequency table */

...

void reconst(void)
{

...
l = (j - k) * 2; // "sizeof(unsigned)" should be instead of "2"
memmove(&freq[k + 1], &freq[k], l);
freq[k] = f;
memmove(&son[k + 1], &son[k], l);

...


The reconst() function treats freq[] array's elements as 16-bit ones (notice * 2 in expression, calculates address within freq[] array), and they really are if the code is compiled on 16-bit platform, but by C standard, unsigned type has size of 32 bit on any modern 32-bit and 64-bit architectures.

I tried to crash it, and found a very easy way to do so: just try to compress big enough file (I had success with 178KiB text file), and it crashes during compressing. Now we can fix a bug (to set unsigned short type instead of unsigned), the program giving us compressed file, which is, in turn, can crash older unfixed LZHuf.c decompression function.

Input file (no matter, compressed or plain) must be big enough, so reconst() function will be called.

Probably (I'm not sure) this is a way to crash unfixed LZHuf.c program on a 32-bit or 64-bit system, just feed this file to it. Unfixed LZHuf.c version has unsigned type for freq[] array, fixed has unsigned short type for it.

For example, this one is unfixed, but still very popular: https://raw.githubusercontent.com/tyll/tinyos-2.x-contrib/89a1419cb84ccf0747f95cdea2423a18e4fb13a7/eon/eon/src/util/lzss-c/lzhuf.c

Crash happens in DecodePosition() function, when it attempts to read beyond d_code[] array. Perhaps, someone else may check this and analyze further.

File I used as a plain text (~178KiB): https://github.com/dennis714/yurichev.com/blob/master/blog/lzhuf/files/plain.txt.

Compressed file which crashes unfixed LZHuf.c (~45KiB): https://github.com/dennis714/yurichev.com/blob/master/blog/lzhuf/files/compressed.dat.

Unfixed LZHuf.c I used: https://github.com/dennis714/yurichev.com/blob/master/blog/lzhuf/files/lzhuf.c.

This open sourced site and this page in particular is hosted on GitHub. Patches, suggestions and comments are welcome.

→ [list of blog posts, my twitter/facebook]