I remember a very similar technique being used successfully for automatically cracking software (registration keys/keyfiles, serial numbers) before Internet-based validation and stronger crypto became common; the difference is that method didn't require having access to any source code or recompiling the target, as it just traced execution and "evolved" itself toward inputs producing longer and wider (i.e. more locations in the binary) traces.
Pulling JPEGs out of thin air
51–60 of 86 posts
Re: Pulling JPEGs out of thin air
#52At the risk of sounding really stupid. Can someone ELI5 what's going on here and why everyone thinks its so amazing?
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 (secu…
>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.
To expand on this, techniques like this are called whitebox fuzzing (or maybe graybox in afl's case). In their extreme whitebox fuzzers even incorporate constraint solvers to directly solve inputs that take the program to previously unexplored paths. One very impressive project is the SAGE whitebox fuzzer [1,2,3] that's in production use at Microsoft (an internal project sadly). I work in the related field of automated test generation, but all my tools are very much research-grade. However, in SAGE they've done all the work of figuring out how 24/7 whitebox fuzzing can be integrated into the development process. I am somewhat envious of the researchers getting to work in an environment where that is possible. If you're interested I very much recommend reading the papers on SAGE.
[1] Poster about SAGE: http://research.microsoft.com/en-us/um/people/pg/public_psfi...
[2] An approachable article on SAGE: http://research.microsoft.com/en-us/um/people/pg/public_psfi...
[3] The paper with all the details: http://research.microsoft.com/en-us/projects/atg/ndss2008.pd...
Re: Pulling JPEGs out of thin air
#53This is INSANELY COOL. If it's smart enough to learn how to build a JPEG in a day, use it with netcat and it could probably send quite a lot of things down in flames. Who needs static analysis :) ?
The overhead of executing a binary and of doing network traffic are orders of magnitude in difference. This synthesized a jpeg in a day. The equivalent operation with a network connection assuming an always-available fast server would probably take years.
Re: Pulling JPEGs out of thin air
#54Regarding >if (strcmp(header.magic_password, "h4ck3d by p1gZ")) goto terminate_now; How impossible would it be to look at the branching instruction, perform a taint analysis on its input and see if there is any part of the input we can tweak to make it branch/not branch. Like, we jumped because the zero flag was set. And the zero flags was set because these two bytes were equal. Hmm that byte is hardcoded. This other…
https://en.wikipedia.org/wiki/Symbolic_execution Quite possible. More commonly done with higher-level languages rather than machine code, but certainly possible with machine code. A good fuzzer could do this too. The fuzzer from the article, american-fuzzy-lop ( https://code.google.com/p/american-fuzzy-lop/ ), does something similar to this as it moves forward in execution, trying to find interesting inputs that caus…
But it would still have trouble with complex cases.
It seems to me that all these methods would eventually run into the Halting Problem. Trying to fuzz through a hash (or other crypto) this way would essentially involve having to break it by a slightly more "intelligent" version of bruteforce.
Re: Pulling JPEGs out of thin air
#55I remember a very similar technique being used successfully for automatically cracking software (registration keys/keyfiles, serial numbers) before Internet-based validation and stronger crypto became common; the difference is that method didn't require having access to any source code or recompiling the target, as it just traced execution and "evolved" itself toward inputs producing longer and wider (i.e. more locat…
That sounds interesting, do you have any more information on this topic?
Re: Pulling JPEGs out of thin air
#56This what a hacker be.
Re: Pulling JPEGs out of thin air
#57The beginning of this article reads eerily similar to the beginning of Greg Egan's Diaspora, though in a much more limited context.
Re: Pulling JPEGs out of thin air
#58Earlier quoted context omitted.
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 (secu…
>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. To expand on this, techniques like this are called whitebox fuzzing (or maybe graybox in afl's case). In their extreme whitebox fuzzers even incor…
Great links, thanks.
Re: Pulling JPEGs out of thin air
#59I'm not familiar with how the fuzzer was monitoring the executed code path. Would this be thwarted by address space layout randomization?
No. afl requires an instrumented (compiled with extra information) executable, and watches the code paths. When fuzzing a seed finds a new code path, it will recycle that fuzzed version as a new seed.
ASLR can help prevent successful exploitation of bugs that afl might find, but it won't prevent the program from crashing in the first place.
(Plus, since afl requires compiling the binary, I doubt it bothers to enable ASLR. There's no benefit for fuzzing purposes.)
Re: Pulling JPEGs out of thin air
#60This is INSANELY COOL. If it's smart enough to learn how to build a JPEG in a day, use it with netcat and it could probably send quite a lot of things down in flames. Who needs static analysis :) ?
The overhead of executing a binary and of doing network traffic are orders of magnitude in difference. This synthesized a jpeg in a day. The equivalent operation with a network connection assuming an always-available fast server would probably take years.
If you are trying to fuzz a protocol, there is no reason not to test it on a local machine. And it would probably end up _faster_ than the jpeg example because a network request has less overhead than execvp.