Pulling JPEGs out of thin air

It starts with an invalid .jpg (literally a text file containing "hello"), and by trying over and over, changing random bytes and tracing the execution of the decoder program as it is fed the corrupted input, it will drill deeper and deeper into the program until it has gotten far enough that the input is actually a valid .jpg, without any human input.

Fuzzing like this is a very effective technique for finding (security) bugs in programs that parse input, because you will quickly end up with "impossible" input nobody thought to check for (but is close enough that it won't be rejected outright), and whoops there's your buffer overflow.

In this particular case, the fuzzer is going beyond just throwing random input, as it considers which changes to the input trigger new code paths in the target binary, and therefore should have a higher success rate in triggering bugs compared to just trying random stuff. And don't forget, this will work with any type of program and file type, not just .jpgs and the djpeg binary.

This is how I understand it:

1) JPEG file structure is complex (much more so than a BMP file for example). 2) Imagine you didn't know what it looked, but had a tool that could "read" them. djpeg in this case 3) What the fuzzer does is "peek" at how the djpeg tool reacts to random "fuzzed" data. It's smart about it, understanding when a bit of data makes the tool do something new (code path) 4) After millions of iterations it "learns" how JPEG file structure works and can generate valid JPEGs.

This might not be very relevant for JPEGs, given that you can just Google their structure. This is cool because it shows how the tool could figure out (or find a weakness in) something where you don't know how it works.

This describes a program (afl) which is given another program (djpeg, some kind of JPEG parser - takes arbitrary data and decides if its JPEG or not) to play with.

afl starts feeding it random inputs gradually gaining limited understanding about what it accepts and what it does not.

Eventually, it gathers enough info (based on strace'ing, google it, and its output) to start pulling JPEG images out of thin air like it's nothing.

The catch is, that this afl program learns this all by itself, and it can do so with any other parser program (like ELF parsers, GIF parsers, whatever). It is a general purpose tool.

Also, similar concept can be applied to things like web servers, or any other servers (since they parse what clients send them).

Not really, because it depends on collecting traces from the target, and if you can do that you can usually just read the password out of memory.

...or just preload a special implementation of strcmp that makes notes of its inputs.