This is a personal blog. My other stuff: book | home page | Twitter | CNC robotics | electronics

January 27, 2015

Technical analysis of Qualys' GHOST

This morning, a leaked note from Qualys' external PR agency made us aware of GHOST. In this blog entry, our crack team of analysts examines the technical details of GHOST and makes a series of recommendations to better protect your enterprise from mishaps of this sort.

Figure 1: The logo of GHOST, courtesy of Qualys PR.

Internally, GHOST appears to be implemented as a lossy representation of a two-dimensional raster image, combining YCbCr chroma subsampling and DCT quantization techniques to achieve high compression rates; among security professionals, this technique is known as JPEG/JFIF. This compressed datastream maps to an underlying array of 8-bpp RGB pixels, arranged sequentially into a rectangular shape that is 300 pixels wide and 320 pixels high. The image is not accompanied by an embedded color profile; we must note that this poses a considerable risk that on some devices, the picture may not be rendered faithfully and that crucial information may be lost.

In addition to the compressed image data, the file also contains APP12, EXIF, and XMP sections totaling 818 bytes. This metadata tells us that the image has been created with Photoshop CC on Macintosh. Our security personnel notes that Photoshop CC is an obsolete version of the application, superseded last year by Photoshop CC 2014. In line with industry best practices and OWASP guidelines, we recommend all users to urgently upgrade their copy of Photoshop to avoid exposure to potential security risks.

The image file modification date returned by the HTTP server at is Thu, 02 Oct 2014 02:40:27 GMT (Last-Modified, link). The roughly 90-day delay between the creation of the image and the release of the advisory probably corresponds to the industry-standard period needed to test the materials with appropriate focus groups.

Removal of the metadata allows the JPEG image to be shrunk from 22,049 to 21,192 bytes (-4%) without any loss of image quality; enterprises wishing to conserve vulnerability-disclosure-related bandwidth may want to consider running jhead -purejpg to accomplish this goal.

Of course, all this mundane technical detail about JPEG images distracts us from the broader issue highlighted by the GHOST report. We're talking here about the fact that the JPEG compression is not particularly suitable for non-photographic content such as logos, especially when the graphics need to be reproduced with high fidelity or repeatedly incorporated into other work. To illustrate the ringing artifacts introduced by the lossy compression algorithm used by the JPEG file format, our investigative team prepared this enhanced visualization:

Figure 2: A critical flaw in GHOST: ringing artifacts.

Artifacts aside, our research has conclusively showed that the JPEG formats offers an inferior compression rate compared to some of the alternatives. In particular, when converted to a 12-color PNG and processed with pngcrush, the same image can be shrunk to 4,229 bytes (-80%):

Figure 3: Optimized GHOST after conversion to PNG.

PS. Tavis also points out that ">_" is not a standard unix shell prompt. We believe that such design errors can be automatically prevented with commercially-available static logo analysis tools.

PPS. On a more serious note, check out this message to get a sense of the risk your server may be at. Either way, it's smart to upgrade.

January 24, 2015

Looking back at three months of afl-fuzz

I originally released afl-fuzz, a security-oriented fuzzer driven by a simple genetic algorithm, somewhere in November of 2013. Back then, it was simply another take on an idea I first toyed with in 2007, inspired in large part by the work on fuzzer corpus distillation done by Tavis Ormandy. It almost ended up in the dustbin of history: early on, the project had many shortcomings, and I was swamped with other work - so I ended up not announcing it properly and not touching it for almost a year.

But then, when the "Shellshock" vulnerability came by in October 2014, and we were increasingly suspicious about the original patch, I decided to dust off an early incarnation of afl-fuzz and take it for a quick spin. I was actually pretty surprised at how good it turned out to be at navigating bash syntax - and how quickly it found additional bugs that weren't predicated simply on flipping random bits, but on being able to synthesize the syntax of the underlying files. A couple of additional tests confirmed that the underlying approach was probably worth more than I have given it credit for.

And so, over the past few months, afl-fuzz has seen almost constant development, with several releases every week. The changes range from sweeping performance and fuzzing strategy improvements, to a clever fork server design proposed by Jann Horn, to visualization capabilities sketched out by Michael Rash, to a crash exploration mode to help in impact analysis, to robust test case and corpus minimization tools (afl-tmin, afl-cmin), to spiffy grammar-aware modes that lessen the need for format-specific tools, to support for *BSD systems, MacOS X, Solaris... and much more.

Since then, afl-fuzz helped squash hundreds of bugs, in part due to a community of folks who found the tool to be fun to use. For example, it has been used by OpenBSD developers to beef up anything from pfctl, to tcpdump, to rcs. Jodie Cunningham relied on it to identify dozens of distinct issues in ImageMagick (GraphicsMagick team had kind words for the tool, too). LLVM developers run it on a corpus of C files to get rid of a sizable pile of compiler issues. Jakub Wilk has worked tirelessly to squash numerous vulnerabilities in the Debian tree. Alex Eubanks used it to find security bugs in PHP and libpng. Many other folks took on "hot" projects such as mozjpeg or libbpg, with predictable results. Out of the few dozen pending security fixes in libtiff, the vast majority likely traces back to afl-fuzz, in part thanks to the work of Tobias Ospelt, William Robinet, and Paris Zoumpouloglou.

Compared to projects such as Mayhem, I'm particularly happy that afl-fuzz has a knack for finding complex issues in relatively tough, security-relevant targets that we actually need to get in a good shape - including security holes in IJG jpeg, libjpeg-turbo, libpng, Firefox, Internet Explorer, GnuTLS, GnuPG, unzip, or file. Heck, the fuzzer even managed to find crash-only bugs in OpenSSH and multiple non-trivial crashing SQL statements in sqlite3. On a much less serious but funny note, it also triggered an somewhat embarrassing security bug in splint, a tool for, quoth, "statically checking C programs for security vulnerabilities and coding mistakes"...

All in all, I'm very happy and humbled with the success of the tool, and how many developers are just grabbing it and running it against their projects without having to spend hours to fiddle various knobs. The afl-users@ mailing list is now 120+ members strong - and I'll do my best to keep the fuzzer useful and enjoyable to play with :-) Many feature suggestions ship in a matter of days - so if you have any ideas, be sure to send them in.

(And if you haven't looked at afl-fuzz recently, give it a try!)

January 09, 2015

afl-fuzz: making up grammar with a dictionary in hand

One of the most significant limitations of afl-fuzz is that its mutation engine is syntax-blind and optimized for compact data formats, such as binary files (e.g., archives, multimedia) or terse human-readable languages (RTF, shell scripts). Any general-purpose fuzzer will have a harder time dealing with more verbose dialects, such as SQL or HTTP. You can improve your odds in a variety of ways, and the results can be surprisingly good - but ultimately, it's never easy to get from Set-Cookie: FOO=BAR to Content-Length: -1 by randomly flipping bits.

The common wisdom is that if you want to fuzz data formats with such ornate grammars, you need to build an one-off, protocol-specific mutation engine with the appropriate syntax templates baked in. Of course, writing such code isn't easy. In essence, you need to manually build a model precise enough so that the generated test cases almost always make sense to the targeted parser - but creative enough to trigger unintended behaviors in that codebase. It takes considerable experience and a fair amount of time to get it just right.

I was thinking about using afl-fuzz to reach some middle ground between the two worlds. I quickly realized that if you give the fuzzer a list of basic syntax tokens - say, the set of reserved keywords defined in the spec - the instrumentation-guided nature of the tool means that even if we just mindlessly clobber the tokens together, we will be able to distinguish between combinations that are nonsensical and ones that actually follow the rules of the underlying grammar and therefore trigger new states in the instrumented binary. By discarding that first class of inputs and refining the other, we could progressively construct more complex and meaningful syntax as we go.

Ideas are cheap, but when I implemented this one, it turned out to be a good bet. For example, I tried it against sqlite, with the fuzzer fed a collection of keywords grabbed from the project's docs (-x testcases/_extras/sql/). Equipped with this knowledge, afl-fuzz quickly spewed out a range of valid if unusual statements, such as:

select sum(1)LIMIT(select sum(1)LIMIT -1,1); select round( -1)````; select group_concat(DISTINCT+1) |1; select length(?)in( hex(1)+++1,1); select abs(+0+ hex(1)-NOT+1) t1; select DISTINCT "Y","b",(1)"Y","b",(1); select - (1)AND"a","b"; select ?1in(CURRENT_DATE,1,1); select - "a"LIMIT- /* */ /* */- /* */ /* */-1; select strftime(1, sqlite_source_id());

(It also found a couple of crashing bugs.)

All right, all right: grabbing keywords is much easier than specifying the underlying grammar, but it still takes some work. I've been wondering how to scratch that itch, too - and came up with a fairly simple algorithm that can help those who do not have the time or the inclination to construct a proper dictionary.

To explain the approach, it's useful to rely on the example of a PNG file. The PNG format uses four-byte, human-readable magic values to indicate the beginning of a section, say:

89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 | .PNG........IHDR
00 00 00 20 00 00 00 20 02 03 00 00 00 0e 14 92 | ................

The algorithm in question can identify "IHDR" as a syntax token by piggybacking on top of the deterministic, sequential bit flips that are already being performed by afl-fuzz across the entire file. It works by identifying runs of bytes that satisfy a simple property: that flipping them triggers an execution path that is distinct from the product of flipping stuff in the neighboring regions, yet consistent across the entire sequence of bytes.

This signal strongly implies that touching any of the affected bytes causes the failure of an underlying atomic check, such as header.magic_value == 0xDEADBEEF or strcmp(name, "Set-Cookie"). When such a behavior is detected, the entire blob of data is added to the dictionary, to be randomly recombined with other dictionary tokens later on.

This second trick is not a substitute for a proper, hand-crafted list of keywords; for one, it will only know about the syntax tokens that were present in the input files, or could be synthesized easily. It will also not do much when pitted against optimized, tree-based parsers that do not perform atomic string comparisons. (The fuzzer itself can often clear that last obstacle anyway, but the process will be slow.)

Well, that's it. If you want to try out the new features, click here and let me know how it goes!

November 30, 2014

afl-fuzz: nobody expects CDATA sections in XML

I made a very explicit, pragmatic design decision with afl-fuzz: for performance and reliability reasons, I did not want to get into static analysis or symbolic execution to understand what the program is actually doing with the data we are feeding to it. The basic algorithm for the fuzzer can be just summed up as randomly mutating the input files, and gently nudging the process toward new state transitions discovered in the targeted binary. That discovery part is done with the help of lightweight and extremely simple instrumentation injected by the compiler.

I had a working theory that this would make the fuzzer a bit smarter than a potato, but I wasn't expecting any fireworks. So, when the algorithm managed to not only find some useful real-world bugs, but to successfully synthesize a JPEG file out of nothing, I was genuinely surprised by the outcome.

Of course, while it was an interesting result, it wasn't an impossible one. In the end, the fuzzer simply managed to wiggle its way through a long and winding sequence of conditionals that operated on individual bytes, making them well-suited for the guided brute-force approach. What seemed perfectly clear, though, is that the algorithm wouldn't be able to get past "atomic", large-search-space checks such as:

if (strcmp(header.magic_password, "h4ck3d by p1gZ")) goto terminate_now;


if (header.magic_value == 0x12345678) goto terminate_now;

This constraint made the tool less useful for properly exploring extremely verbose, human-readable formats such as HTML or JavaScript.

Some doubts started to set in when afl-fuzz effortlessly pulled out four-byte magic values and synthesized ELF files when testing programs such as objdump or file. As I later found out, this particular example is often used as a benchmark for complex static analysis or symbolic execution frameworks. But still, guessing four bytes could have been just a happy accident. With fast targets, the fuzzer can pull off billions of execs per day on a single machine, so it could have been dumb luck.

(As an aside: to deal with strings, I had this very speculative idea of special-casing memory comparison functions such as strcmp() and memcmp() by replacing them with non-optimized versions that can be instrumented easily. I have one simple demo of that principle bundled with the fuzzer in experimental/instrumented_cmp/, but I never got around to actually implementing it in the fuzzer itself.)

Anyway, nothing quite prepared me for what the recent versions were capable of doing with libxml2. I seeded the session with:

<a b="c">d</a>

...and simply used that as the input for a vanilla copy of xmllint. I was merely hoping to stress-test the very basic aspects of the parser, without getting into any higher-order features of the language. Yet, after two days on a single machine, I found this buried in test case #4641 in the output directory:

...<![<CDATA[C%Ada b="c":]]]>...

What the heck?!

As most of you probably know, CDATA is a special, differently parsed section within XML, separated from everything else by fairly complex syntax - a nine-character sequence of bytes that can't be realistically discovered by just randomly flipping bits.

The finding is actually not magic; there are two possible explanations:

  • As a recent "well, it's cheap, so let's see what happens" optimization, AFL automatically sets -O3 -funroll-loops when calling the compiler for instrumented binaries, and some of the shorter fixed-string comparisons will be actually just expanded inline. For example, if the stars align just right, strcmp(buf, "foo") may be unrolled to:
    cmpb   $0x66,0x200c32(%rip)        # 'f'
    jne    4004b6 
    cmpb   $0x6f,0x200c2a(%rip)        # 'o'
    jne    4004b6 
    cmpb   $0x6f,0x200c22(%rip)        # 'o'
    jne    4004b6 
    cmpb   $0x0,0x200c1a(%rip)         # NUL
    jne    4004b6 
    ...which, by the virtue of having a series of explicit and distinct branch points, can be readily instrumented on a per-character basis by afl-fuzz.

  • If that fails, it just so happens that some of the string comparisons in libxml2 in parser.c are done using a bunch of macros that will compile to similarly-structured code (as spotted by Ben Hawkes). This is presumably done so that the compiler can optimize this into a tree-style parser - whereas a linear sequence of strcmp() calls would lead to repeated and unnecessary comparisons of the already-examined chars.

    (Although done by hand in this particular case, the pattern is fairly common for automatically generated parsers of all sorts.)
The progression of test cases seems to support both of these possibilities:

<![C b="c">
<![CDb m="c">

I find this result a bit spooky because it's an example of the fuzzer defiantly and secretly working around one of its intentional and explicit design limitations - and definitely not something I was aiming for =)

Of course, treat this first and foremost as a novelty; there are many other circumstances where similar types of highly verbose text-based syntax would not be discoverable to afl-fuzz - or where, even if the syntax could be discovered through some special-cased shims, it would be a waste of CPU time to do it with afl-fuzz, rather than a simple syntax-aware, template-based tool.

(Coming up with an API to make template-based generators pluggable into AFL may be a good plan.)

By the way, here are some other gems from the randomly generated test cases:

<?xml version="2.666666666666666666667666666">
<?xml standalone?>

November 24, 2014

afl-fuzz: crash exploration mode

One of the most labor-intensive portions of any fuzzing project is the work needed to determine if a particular crash poses a security risk. A small minority of all fault conditions will have obvious implications; for example, attempts to write or jump to addresses that clearly come from the input file do not need any debate. But most crashes are more ambiguous: some of the most common issues are NULL pointer dereferences and reads from oddball locations outside the mapped address space. Perhaps they are a manifestation of an underlying vulnerability; or perhaps they are just harmless non-security bugs. Even if you prefer to err on the side of caution and treat them the same, the vendor may not share your view.

If you have to make the call, sifting through such crashes may require spending hours in front of a debugger - or, more likely, rejecting a good chunk of them based on not much more than a hunch. To help triage the findings in a more meaningful way, I decided to add a pretty unique and nifty feature to afl-fuzz: the brand new crash exploration mode, enabled via -C.

The idea is very simple: you take a crashing test case and give it to afl-fuzz as a starting point for the automated run. The fuzzer then uses its usual feedback mechanisms and genetic algorithms to see how far it can get within the instrumented codebase while still keeping the program in the crashing state. Mutations that stop the crash from happening are thrown away; so are the ones that do not alter the execution path in any appreciable way. The occasional mutation that makes the crash happen in a subtly different way will be kept and used to seed subsequent fuzzing rounds later on.

The beauty of this mode is that it very quickly produces a small corpus of related but somewhat different crashes that can be effortlessly compared to pretty accurately estimate the degree of control you have over the faulting address, or to figure out whether you can get past the initial out-of-bounds read by nudging it just the right way (and if the answer is yes, you probably get to see what happens next). It won't necessarily beat thorough code analysis, but it's still pretty cool: it lets you make a far more educated guess without having to put in any work.

As an admittedly trivial example, let's take a suspect but ambiguous crash in unrtf, found by afl-fuzz in its normal mode:

unrtf[7942]: segfault at 450 ip 0805062b sp bf957e60 error 4 in unrtf[8048000+1c000]

When fed to the crash explorer, the fuzzer took just several minutes to notice that by changing {\cb-44901990 in the converted RTF file to printable representations of other negative integers, it could quickly trigger faults at arbitrary addresses of its choice, corresponding mostly-linearly to the integer set:

unrtf[28809]: segfault at 88077782 ip 0805062b sp bff00210 error 4 in unrtf[8048000+1c000]
unrtf[26656]: segfault at 7271250 ip 0805062b sp bf957e60 error 4 in unrtf[8048000+1c000]

Given a bit more time, it would also almost certainly notice that choosing values within the mapped address space get it past the crashing location and permit even more fun. So, automatic exploit writing next?

November 10, 2014

Exploitation modelling matters more than we think

Our own Krzysztof Kotowicz put together a pretty neat site called the Bughunter University. The first part of the site deals with some of the most common non-qualifying issues that are reported to our Vulnerability Reward Program. The entries range from mildly humorous to ones that still attract some debate; it's a pretty good read, even if just for the funny bits.

Just as interestingly, the second part of the site also touches on topics that go well beyond the world of web vulnerability rewards. One page in particular deals with the process of thinking through, and then succinctly and carefully describing, the hypothetical scenario surrounding the exploitation of the bugs we find - especially if the bugs are major, novel, or interesting in any other way.

This process is often shunned as unnecessary; more often than not, I see this discussion missing, or done in a perfunctory way, in conference presentations, research papers, or even the reports produced as the output of commercial penetration tests. That's unfortunate: we tend to be more fallible than we think we are. The seemingly redundant exercise in attack modelling forces us to employ a degree of intellectual rigor that often helps spot fatal leaps in our thought process and correct them early on.

Perhaps the most common fallacy of this sort is the construction of security attacks that fully depend on the exposure to pre-existing risks of a magnitude that is comparable or greater than the danger posed by the new attack. Familiar examples of this trend may include:
  • Attacks on account data that can be performed only if the attacker already has shell-level access to said account. Some of research in this category deals with the ability to extract HTTP cookies by examining process memory or disk, or to backdoor the browser by placing a DLL in a directory not accessible to other UIDs. Other publications may focus on exploiting buffer overflows in non-privileged programs through a route that is unlikely to ever be exposed to the outside world.

  • Attacks that require physical access to brick or otherwise disable a commodity computing device. After all, in almost all cases, having the attacker bring a hammer or wire cutters will work just as well.

  • Web application security issues that are exploitable only against users who are using badly outdated browsers or plugins. Sure, the attack may work - but so will dozens of remote code execution and SOP bypass flaws that the client software is already known to be vulnerable to.

  • New, specific types of attacks that work only against victims who already exhibit behaviors well-understood to carry unreasonable risk - say, the willingness to retype account credentials without looking at the address bar, or to accept and execute unsolicited downloads.

  • Sleight-of-hand vectors that assume, without explaining why, that the attacker can obtain or tamper with some types of secrets (e.g., capability-bearing URLs), but not others (e.g., user's cookies, passwords, server's private SSL keys), despite their apparent similarity.

Some theorists argue that security issues exist independently of exploitation vectors, and that they must be remedied regardless of whether one can envision a probable attack vector. Perhaps this distinction is useful in some contexts - but it is still our responsibility to precisely and unambiguously differentiate between immediate hazards and more abstract thought experiments of that latter kind.

November 07, 2014

Pulling JPEGs out of thin air

This is an interesting demonstration of the capabilities of afl; I was actually pretty surprised that it worked!

$ mkdir in_dir
$ echo 'hello' >in_dir/hello
$ ./afl-fuzz -i in_dir -o out_dir ./jpeg-6b2/djpeg

In essence, I created a text file containing just "hello" and asked the fuzzer to keep feeding it to a program that expects a JPEG image (djpeg is a simple utility bundled with the ubiquitous IJG jpeg 6b image library). Of course, my input file does not resemble a valid picture, so it gets immediately rejected by the utility:

$ ./djpeg '../out_dir/queue/id:000000,orig:hello'
Not a JPEG file: starts with 0x68 0x65

Such a fuzzing run would be normally completely pointless: there is essentially no chance that a "hello" could be ever turned into a valid JPEG by a traditional, format-agnostic fuzzer, since the probability that dozens of random tweaks would align just right is astronomically low.

Luckily, afl-fuzz can leverage lightweight assembly-level instrumentation to its advantage - and within a millisecond or so, it notices that although setting the first byte to 0xff does not change the externally observable output, it triggers a slightly different internal code path in the tested app. Equipped with this information, it decides to use that test case as a seed for future fuzzing rounds:

$ ./djpeg '../out_dir/queue/id:000001,src:000000,op:int8,pos:0,val:-1,+cov'
Not a JPEG file: starts with 0xff 0x65

When later working with that second-generation test case, the fuzzer almost immediately notices that setting the second byte to 0xd8 does something even more interesting:

$ ./djpeg '../out_dir/queue/id:000004,src:000001,op:havoc,rep:16,+cov'
Premature end of JPEG file
JPEG datastream contains no image

At this point, the fuzzer managed to synthesize the valid file header - and actually realized its significance. Using this output as the seed for the next round of fuzzing, it quickly starts getting deeper and deeper into the woods. Within several hundred generations and several hundred million execve() calls, it figures out more and more of the essential control structures that make a valid JPEG file - SOFs, Huffman tables, quantization tables, SOS markers, and so on:
$ ./djpeg '../out_dir/queue/id:000008,src:000004,op:havoc,rep:2,+cov'
Invalid JPEG file structure: two SOI markers
$ ./djpeg '../out_dir/queue/id:001005,src:000262+000979,op:splice,rep:2'
Quantization table 0x0e was not defined
$ ./djpeg '../out_dir/queue/id:001282,src:001005+001270,op:splice,rep:2,+cov' >.tmp; ls -l .tmp
-rw-r--r-- 1 lcamtuf lcamtuf 7069 Nov  7 09:29 .tmp

The first image, hit after a day or two on an 4-core system, looks very unassuming: it's a blank grayscale image, 3 pixels wide and 784 pixels tall. But the moment it is discovered, the fuzzer starts using the image as a seed - rapidly producing a wide array of more interesting pics for every new execution path:

Of course, synthesizing a complete image out of thin air is an extreme example, and not necessarily a very practical one. But more prosaically, fuzzers are meant to stress-test every feature of the targeted program. With instrumented, generational fuzzing, lesser-known features (e.g., progressive, black-and-white, or arithmetic-coded JPEGs) can be discovered and locked onto without requiring a giant, high-quality corpus of diverse test cases to seed the fuzzer with.

The cool part of the libjpeg demo is that it works without any special preparation: there is nothing special about the "hello" string, the fuzzer knows nothing about image parsing, and is not designed or fine-tuned to work with this particular library. There aren't even any command-line knobs to turn. You can throw afl-fuzz at many other types of parsers with similar results: with bash, it will write valid scripts; with giflib, it will make GIFs; with fileutils, it will create and flag ELF files, Atari 68xxx executables, x86 boot sectors, and UTF-8 with BOM. In almost all cases, the performance impact of instrumentation is minimal, too.

Of course, not all is roses; at its core, afl-fuzz is still a brute-force tool. This makes it simple, fast, and robust, but also means that certain types of atomically executed checks with a large search space may pose an insurmountable obstacle to the fuzzer; a good example of this may be:

if (strcmp(header.magic_password, "h4ck3d by p1gZ")) goto terminate_now;

In practical terms, this means that afl-fuzz won't have as much luck "inventing" PNG files or non-trivial HTML documents from scratch - and will need a starting point better than just "hello". To consistently deal with code constructs similar to the one shown above, a general-purpose fuzzer would need to understand the operation of the targeted binary on a wholly different level. There is some progress on this in the academia, but frameworks that can pull this off across diverse and complex codebases in a quick, easy, and reliable way are probably still years away.

PS. Several folks asked me about symbolic execution and other inspirations for afl-fuzz; I put together some notes in this doc.

PPS. An earlier version of the post mistakenly named libjpeg-turbo as the instrumented library, rather than IJG jpeg 6b. I've been doing working with both and mixed them up. Either variant should work, but large portions of libjpeg-turbo are written in opaque SIMD assembly, likely requiring several extra CPU-days days of brute-force effort (or compilation via ./configure --without-simd).

October 24, 2014

PSA: don't run 'strings' on untrusted files (CVE-2014-8485)

Many shell users, and certainly most of the people working in computer forensics or other fields of information security, have a habit of running /usr/bin/strings on binary files originating from the Internet. Their understanding is that the tool simply scans the file for runs of printable characters and dumps them to stdout - something that is very unlikely to put you at any risk.

It is much less known that the Linux version of strings is an integral part of GNU binutils, a suite of tools that specializes in the manipulation of several dozen executable formats using a bundled library called libbfd. Other well-known utilities in that suite include objdump and readelf.

Perhaps simply by the virtue of being a part of that bundle, the strings utility tries to leverage the common libbfd infrastructure to detect supported executable formats and "optimize" the process by extracting text only from specific sections of the file. Unfortunately, the underlying library can be hardly described as safe: a quick pass with afl (and probably with any other competent fuzzer) quickly reveals a range of troubling and likely exploitable out-of-bounds crashes due to very limited range checking, say:

$ wget
$ strings strings-bfd-badptr2
Segmentation fault
strings[24479]: segfault at 4141416d ip 0807a4e7 sp bf80ca60 error 4 in strings[8048000+9a000]
      while (--n_elt != 0)
        if ((++idx)->shdr->bfd_section)                                ← Read from an attacker-controlled pointer
          elf_sec_group (idx->shdr->bfd_section) = shdr->bfd_section;  ← Write to an attacker-controlled pointer
(gdb) p idx->shdr
$1 = (Elf_Internal_Shdr *) 0x41414141

The 0x41414141 pointer being read and written by the code comes directly from that proof-of-concept file and can be freely modified by the attacker to try overwriting program control structures. Many Linux distributions ship strings without ASLR, making potential attacks easier and more reliable - a situation reminiscent of one of the recent bugs in bash.

Interestingly, the problems with the utility aren't exactly new; Tavis spotted the first signs of trouble some nine years ago.

In any case: the bottom line is that if you are used to running strings on random files, or depend on any libbfd-based tools for forensic purposes, you should probably change your habits. For strings specifically, invoking it with the -a parameter seems to inhibit the use of libbfd. Distro vendors may want to consider making the -a mode default, too.

PS. I actually had the libbfd fuzzing job running on this thing!

October 14, 2014

Two more browser memory disclosure bugs (CVE-2014-1580 and #19611cz)

To add several more trophies to afl's pile of image parsing memory disclosure vulnerabilities:
  • MSFA 2014-78 (CVE-2014-1580) fixes another case of uninitialized memory disclosure in Firefox - this time, when rendering truncated GIF images on <canvas>. The bug was reported on September 5 and fixed today. For a convenient test case, check out this page. Rough timeline:

    • September 5: Initial, admittedly brief notification to vendor, including a simple PoC.
    • September 5: Michael Wu confirms the exposure and pinpoints the root cause. Discussion of fixes ensues.
    • September 9: Initial patch created.
    • September 12: Patch approved and landed.
    • October 2: Patch verified by QA.
    • October 13: Fixes ship with Firefox 33.

  • MSRC case #19611cz (MS14-085) is a conceptually similar bug related to JPEG DHT parsing, seemingly leaking bits of stack information in Internet Explorer. This was reported to MSRC on July 2 and hasn't been fixed to date. Test case here. Rough timeline:

    • July 2: Initial, admittedly brief notification to vendor, mentioning the disclosure of uninitialized memory and including a simple PoC.
    • July 3: MSRC request to provide "steps and necessary files to reproduce".
    • July 3: My response, pointing back to the original test case.
    • July 3: MSRC response, stating that they are "unable to determine the nature of what I am reporting".
    • July 3: My response, reiterating the suspected exposure in a more verbose way.
    • July 4: MSRC response from an analyst, confirming that they could reproduce, but also wondering if "his webserver is not loading up a different jpeg just to troll us".
    • July 4: My response stating that I'm not trolling MSRC.
    • July 4: MSRC opens case #19611cz.
    • July 29: MSRC response stating that they are "unable identify a way in which an attacker would be able to propagate the leaked stack data back to themselves".
    • July 29: My response pointing the existence of the canvas.toDataURL() API in Internet Explorer, and providing a new PoC that demonstrates the ability to read back data.
    • September 24: A notification from MSRC stating that the case has been transferred to a new case manager.
    • October 7: My response noting that we've crossed the 90-day mark with no apparent progress made, and that I plan to disclose the bug within a week.
    • October 9: Acknowledgment from MSRC.
Well, that's it. Enjoy!

Fuzzing random programs without execve()

The most common way to fuzz data parsing libraries is to find a simple binary that exercises the interesting functionality, and then simply keep executing it over and over again - of course, with slightly different, randomly mutated inputs in each run. In such a setup, testing for evident memory corruption bugs in the library can be as simple as doing waitpid() on the child process and checking if it ever dies with SIGSEGV, SIGABRT, or something equivalent.

This approach is favored by security researchers for two reasons. Firstly, it eliminates the need to dig into the documentation, understand the API offered by the underlying library, and then write custom code to stress-test the parser in a more direct way. Secondly, it makes the fuzzing process repeatable and robust: the program is running in a separate process and is restarted with every input file, so you do not have to worry about a random memory corruption bug in the library clobbering the state of the fuzzer itself, or having weird side effects on subsequent runs of the tested tool.

Unfortunately, there is also a problem: especially for simple libraries, you may end up spending most of the time waiting for execve(), the linker, and all the library initialization routines to do their job. I've been thinking of ways to minimize this overhead in american fuzzy lop, but most of the ideas I had were annoyingly complicated. For example, it is possible to write a custom ELF loader and execute the program in-process while using mprotect() to temporarily lock down the memory used by the fuzzer itself - but things such as signal handling would be a mess. Another option would be to execute in a single child process, make a snapshot of the child's process memory and then "rewind" to that image later on via /proc/pid/mem - but likewise, dealing with signals or file descriptors would require a ton of fragile hacks.

Luckily, Jann Horn figured a different, much simpler approach, and sent me a patch for afl out of the blue :-) It boils down to injecting a small piece of code into the fuzzed binary - a feat that can be achieved via LD_PRELOAD, via PTRACE_POKETEXT, via compile-time instrumentation, or simply by rewriting the ELF binary ahead of the time. The purpose of the injected shim is to let execve() happen, get past the linker (ideally with LD_BIND_NOW=1, so that all the hard work is done beforehand), and then stop early on in the actual program, before it gets to processing any inputs generated by the fuzzer or doing anything else of interest. In fact, in the simplest variant, we can simply stop at main().

Once the designated point in the program is reached, our shim simply waits for commands from the fuzzer; when it receives a "go" message, it calls fork() to create an identical clone of the already-loaded program; thanks to the powers of copy-on-write, the clone is created very quickly yet enjoys a robust level of isolation from its older twin. Within the child process, the injected code returns control to the original binary, letting it process the fuzzer-supplied input data (and suffer any consequences of doing so). Within the parent, the shim relays the PID of the newly-crated process to the fuzzer and goes back to the command-wait loop.

Of course, when you start dealing with process semantics on Unix, nothing is as easy as it appears at first sight; here are some of the gotchas we had to work around in the code:
  • File descriptor offsets are shared between processes created with fork(). This means that any descriptors that are open at the time that our shim is executed may need to be rewound to their original position; not a significant concern if we are stopping at main() - we can just as well rewind stdin by doing lseek() in the fuzzer itself, since that's where the descriptor originates - but it can become a hurdle if we ever aim at locations further down the line.

  • In the same vein, there are some types of file descriptors we can't fix up. The shim needs to be executed before any access to pipes, character devices, sockets, and similar non-resettable I/O. Again, not a big concern for main().

  • The task of duplicating threads is more complicated and would require the shim to keep track of them all. So, in simple implementations, the shim needs to be injected before any additional threads are spawned in the binary. (Of course, threads are rare in file parser libraries, but may be more common in more heavyweight tools.)

  • The fuzzer is no longer an immediate parent of the fuzzed process, and as a grandparent, it can't directly use waitpid(); there is also no other simple, portable API to get notified about the process' exit status. We fix that simply by having the shim do the waiting, then send the status code to the fuzzer. In theory, we should simply call the clone() syscall with the CLONE_PARENT flag, which would make the new process "inherit" the original PPID. Unfortunately, calling the syscall directly confuses glibc, because the library caches the result of getpid() when initializing - and without a way to make it reconsider, PID-dependent calls such as abort() or raise() will go astray. There is also a library wrapper for the clone() call that does update the cached PID - but the wrapper is unwieldy and insists on messing with the process' stack.

    (To be fair, PTRACE_ATTACH offers a way to temporarily adopt a process and be notified of its exit status, but it also changes process semantics in a couple of ways that need a fair amount of code to fully undo.)
Even with the gotchas taken into account, the shim isn't complicated and has very few moving parts - a welcome relief compared to the solutions I had in mind earlier on. It reads commands via a pipe at file descriptor 198, uses fd 199 to send messages back to parent, and does just the bare minimum to get things sorted out. A slightly abridged verion of the code is:

  /* Phone home and tell the parent that we're OK. */

  pushl $4          /* length    */
  pushl $__afl_temp /* data      */
  pushl $199        /* file desc */
  call  write
  addl  $12, %esp


  /* Wait for parent by reading from the pipe. This will block until
     the parent sends us something. Abort if read fails. */

  pushl $4          /* length    */
  pushl $__afl_temp /* data      */
  pushl $198        /* file desc */
  call  read
  addl  $12, %esp

  cmpl  $4, %eax
  jne   __afl_die

  /* Once woken up, create a clone of our process. */

  call fork

  cmpl $0, %eax
  jl   __afl_die
  je   __afl_fork_resume

  /* In parent process: write PID to pipe, then wait for child. 
     Parent will handle timeouts and SIGKILL the child as needed. */

  movl  %eax, __afl_fork_pid

  pushl $4              /* length    */
  pushl $__afl_fork_pid /* data      */
  pushl $199            /* file desc */
  call  write
  addl  $12, %esp

  pushl $2             /* WUNTRACED */
  pushl $__afl_temp    /* status    */
  pushl __afl_fork_pid /* PID       */
  call  waitpid
  addl  $12, %esp

  cmpl  $0, %eax
  jle   __afl_die

  /* Relay wait status to pipe, then loop back. */

  pushl $4          /* length    */
  pushl $__afl_temp /* data      */
  pushl $199        /* file desc */
  call  write
  addl  $12, %esp

  jmp __afl_fork_wait_loop


  /* In child process: close fds, resume execution. */

  pushl $198
  call  close

  pushl $199
  call  close

  addl  $8, %esp
But, was it worth it? The answer is a resounding "yes": the stop-at-main() logic, already shipping with afl 0.36b, can speed up the fuzzing of many common image libraries by a factor of two or more. It's actually almost unexpected, given that we still keep doing fork(), a syscall with a lingering reputation for being very slow.

The next challenge is devising a way to move the shim down the stream, so that we can also skip any common program initialization steps, such as reading config files - and stop just few instructions shy of the point where the application tries to read the mutated data we are messing with. Jann's original patch has a solution that relies on ptrace() to detect file access; but we've been brainstorming several other ways.

PS. On a related note, some readers might enjoy this.

October 01, 2014

Bash bug: the other two RCEs, or how we chipped away at the original fix (CVE-2014-6277 and '78)

The patch that implements a prefix-based way to mitigate vulnerabilities in bash function exports has been out since last week and has been already picked up by most Linux vendors (plus by Apple). So, here's a quick overview of the key developments along the way, including two really interesting things: proof-of-concept test cases for two serious, previously non-public RCE bugs tracked as CVE-2014-6277 and CVE-2014-6278.

NOTE: If you or your distro maintainers have already deployed Florian's patch, there is no reason for alarm - you are almost certainly not vulnerable to attacks. If you do not have this patch, and instead relied only on the original CVE-2014-6271 fix, you probably need to act now. See this entry for a convenient test case and other tips.

Still here? Good. If you need a refresher, the basic principles of the underlying function export functionality, and the impact of the original bash bug (CVE-2014-6271), are discussed in this blog post. If you have read the earlier post, the original attack disclosed by Stephane Chazelas should be very easy to understand:

HTTP_COOKIE='() { 0; }; echo hi mom;' bash -c :

In essence, the internal parser invoked by bash to process the specially encoded function definitions passed around in environmental variables had a small problem: it continued parsing the code past the end of the function definition itself - and at that point, flat out executed whatever instructions it came across, just as it would do in a normal bash script. Given that the value of certain environmental variables can be controlled by remote attackers in quite a few common settings, this opened up a good chunk of the Internet to attacks.

The original vulnerability was reported privately and kept under embargo for roughly two weeks to develop a fairly conservative fix that modified the parser to bail out in a timely manner and do not parse any trailing commands. As soon as the embargo was lifted, we all found out about the bug and scrambled to deploy fixes. At the same time, a good chunk of the security community reacted with surprise and disbelief that bash is keen to dispatch the contents of environmental variables to a fairly complex syntax parser - so we started poking around.

Tavis was the quickest: he found that you can convince the parser to keep looking for a file name for output redirection past the boundary between the untrusted string accepted from the environment and the actual body of the program that bash is being asked to execute (CVE-2014-7169). His original test case can be simplified at:

HTTP_COOKIE='() { function a a>\' bash -c echo

This example would create an empty file named "echo", instead of executing the requested command. Tavis' finding meant that you would be at risk of remote code execution in situations where attacker-controlled environmental variables are mixed with sanitized, attacker-controlled command-line parameters passed to calls such as system() or popen(). For example, you'd be in trouble if you were doing this in a web app:

system("echo '"+ sanitized_string_without_quotes + "' | /some/trusted/program");

...because the attacker could convince bash to skip over the "echo" command and execute the command given in the second parameter, which happens to be a sanitized string (albeit probably with no ability to specify parameters). On the flip side, this is a fairly specific if not entirely exotic coding pattern - and contrary to some of the initial reports, the bug probably wasn't exploitable in a much more general way.

Chet, the maintainer of bash, started working on a fix to close this specific parsing issue, and released it soon thereafter.

On the same day, Todd Sabin and Florian Weimer have independently bumped into a static array overflow in the parser (CVE-2014-7186). The bug manifested in what seemed to be a non-exploitable crash, trying to dereference a non-attacker-controlled pointer at an address that "by design" should fall well above the end of heap - but was enough to cast even more doubt on the robustness of the underlying code. The test for this problem was pretty simple - you just needed a sequence of here-documents that overflowed a static array, say:

HTTP_COOKIE='() { 0 <<a <<b <<c <<d <<e <<f <<g <<h <<i <<j <<k <<l <<m; }' bash -c :

Florian also bumped into an off-by-one issue with loop parsing (CVE-2014-7187); the proof-of-concept function definition for this is a trivial for loop nested 129 levels deep, but the effect can be only observed under memory access diagnostics tools, and its practical significance is probably low. Nevertheless, all these revelations prompted him to start working on an unofficial but far more comprehensive patch that would largely shield the parser from untrusted strings in normally encountered variables present in the environment.

In parallel to Tavis' and Florian's work, I set up a very straightforward fuzzing job with american fuzzy lop. I seeded it with a rudimentary function definition: () { foo() { foo; }; >bar; } ...and simply let it run with a minimalistic wrapper that took the test case generated by the fuzzer, put it in a variable, and then called execve() to invoke bash.

Although the fuzzer had no clue about the syntax of shell programs, it had the benefit of being able to identify and isolate interesting syntax based on coverage signals, deriving around 1,000 other distinctive test cases from the starting one while "instinctively" knowing not to mess with the essential "() {" prefix. For the first few hours, it kept hitting only the redirect issue originally reported by Todd and the file-creation issue discovered by Tavis - but soon thereafter, it spewed out a new crash illustrated by this snippet of code (CVE-2014-6277):

HTTP_COOKIE='() { x() { _; }; x() { _; } <<a; }' bash -c :

This proved to be a very straightforward use of uninitialized memory: it hit a code path in make_redirect() where one field in a newly-allocated REDIR struct - here_doc_eof - would not be set to any specific value, yet would be treated as a valid pointer later on (somewhere in copy_redirect()).

Now, if bash is compiled with both --enable-bash-malloc and --enable-mem-scramble, the memory returned to make_redirect() by xmalloc() will be set to 0xdf, making the pointer always resolve to 0xdfdfdfdf, and thus rendering the prospect of exploitation far more speculative (essentially depending on whether the stack or any other memory region can be grown by the attacker to overlap with this address). That said, on a good majority of Linux distros, these flags are disabled, and you can trivially get bash to dereference a pointer that is entirely within attacker's control:

HTTP_COOKIE="() { x() { _; }; x() { _; } <<`perl -e '{print "A"x1000}'`; }" bash -c :
bash[25662]: segfault at 41414141 ip 00190d96 sp bfbe6354 error 4 in[110000+191000]

The actual fault happens because of an attempt to copy here_doc_eof to a newly-allocated buffer using a C macro that expands to the following code:

strcpy(xmalloc(1 + strlen(redirect->here_doc_eof)), (redirect->here_doc_eof))

This appears to be exploitable in at least one way: if here_doc_eof is chosen by the attacker to point in the vicinity of the current stack pointer, the apparent contents of the string - and therefore its length - may change between stack-based calls to xmalloc() and strcpy() as a natural consequence of an attempt to pass parameters and create local variables. Such a mid-macro switch will result in an out-of-bounds write to the newly-allocated memory.

A simple conceptual illustration of this attack vector would be: char* result; int len_alloced; main(int argc, char** argv) { /* The offset will be system- and compiler-specific */; char* ptr = &ptr - 9; result = strcpy (malloc(100 + (len_alloced = strlen(ptr))), ptr); printf("requested memory = %d\n" "copied text = %d\n", len_alloced + 1, strlen(result) + 1); } When compiled with the -O2 flag used for bash, on one test system, this produces:

requested memory = 2
copied text = 28

Of course, the result will vary from system to system, but the general consequences of this should be fairly evident. The issue is also made worse by the fact that only relatively few distributions were building bash as a position-independent executable that could be fully protected by ASLR.

(In addition to this vector, there is also a location in dispose_cmd.c that calls free() on the pointer under some circumstances, but I haven't really really spent a lot of time trying to develop a functioning exploit for the '77 bug for reasons that should be evident in the text that follows... well, just about now.)

It has to be said that there is a bit less glamour to such a low-level issue that still requires you to go through some mental gymnastics to be exploited in a portable way. Luckily, the fuzzer kept going, and few hours later, isolated a test case that, after minimization, yielded this gem (CVE-2014-6278):

HTTP_COOKIE='() { _; } >_[$($())] { echo hi mom; id; }' bash -c :

I am... actually not entirely sure what happens here. A sequence of nested $... statements within a redirect appears to cause the parser to bail out without properly resetting its state, and puts it in the mood for executing whatever comes next. The test case works as-is with bash 4.2 and 4.3, but not with more ancient releases; this is probably related to changes introduced few years ago in bash 4.2 patch level 12 (xparse_dolparen()), but I have not investigated if earlier versions are patently not vulnerable or simply require different syntax.

The CVE-2014-6278 payload allows straightforward "put-your-commands-here" remote code execution on systems that are protected only with the original patch - something that we were worried about for a while, and what prompted us to ask people to update again over the past few days.

Well, that's it. I kept the technical details of the last two findings embargoed for a while to give people some time to incorporate Florian's patch and avoid the panic associated with the original bug - but at this point, given the scrutiny that the code is under, the ease of discovering the problems with off-the-shelf open-source tools, and the availability of adequate mitigations, the secrecy seems to have outlived its purpose.

Any closing thoughts? Well, I'm not sure there's a particular lesson to be learnt from the entire story. There's perhaps one thing - it would probably have been helpful if the questionable nature of the original patch was spotted by any of the notified vendors during the two-week embargo period. That said, I wasn't privy to these conversations - and hindsight is always 20/20.

September 27, 2014

Bash bug: apply Florian's patch now (CVE-2014-6277 and CVE-2014-6278)

OK, rebuild bash and deploy Florian's unofficial patch or its now-upstream version now. If you're a distro maintainer, please consider doing the same.

My previous post has more information about the original vulnerability (CVE-2014-6271). It also explains Tavis' and my original negative sentiment toward the original upstream patch. In short, the revised code did not stop bash from parsing the code seen in potentially attacker-controlled, remotely-originating environmental variables. Instead, the fix simply seeks to harden the parsing to prevent RCE. It relies on two risky assumptions:
  • That spare for this one bug we're fixing now, the process of parsing attacker-controlled functions is guaranteed to have no side effects on the subsequently executed trusted code.

  • That the underlying parser, despite probably not being designed to deal with attacker-supplied inputs, is free from the usual range of C language bugs.
From the very early hours, we have argued on the oss-security mailing list that a more reasonable approach would be to shield the parser from remotely-originating strings. I proposed putting the function export functionality behind a runtime flag or using a separate, prefixed namespace for the exported functions - so that variables such as HTTP_COOKIE do not go through this code path at all. Unfortunately, we made no real progress on that early in the game.

Soon thereafter, people started to bump into additional problems in the parser code. The first assumption behind the patch - the one about the parsing process not having other side effects - was quickly proved wrong by Tavis, who came up with a code construct that would get the parser in an inconsistent state, causing bash to create a bogus file and mangle any subsequent code that /bin/sh is supposed to execute.

This was assigned CVE-2014-7169 and led to a round of high-profile press reports claiming that we're still doomed, and people assigning the new bug CVSS scores all the way up to 11. The reality was a bit more nuanced: the glitch demonstrated by Tavis' code is a bit less concerning, because it does not translate into a universally exploitable RCE - at least not as far as we could figure it out. Some uses of /bin/sh would be at risk, but most would just break in a probably-non-exploitable way. The maintainer followed with another patch that locked down this specific hole.

The second assumption started showing cracks, too. First came a report from Todd Sabin, who identified an static array overflow error when parsing more than ten stacked redirects. The bug, assigned CVE-2014-7186, would cause a crash, but given the nature of the underlying assignment, immediate exploitability seemed fairly unlikely. Another probably non-security off-by-one issue with line counting in loops cropped up shortly thereafter (CVE-2014-7187).

The two latter issues do not have an officially released upstream patch at that point, but they prompted Florian Weimer of Red Hat to develop an unofficial patch that takes a seemingly more durable approach that we argued for earlier on: putting function exports in a separate namespace. Florian's fix effectively isolates the function parsing code from attacker-controlled strings in almost all the important use cases we can currently think of.

(One major outlier would be any solutions that rely on blacklisting environmental variables to run restricted shells or restricted commands as a privileged user - sudo-type stuff - but it's a much smaller attack surface and a a very dubious security boundary to begin with.)

Well... so, to get to the point: I've been fuzzing the underlying function parser on the side - and yesterday, bumped into a new parsing issue (CVE-2014-6277) that is almost certainly remotely exploitable and made easier to leverage due to the fact that bash is seldom compiled with ASLR. I'll share the technical details later on; for now, I sent the info to the maintainer of bash and to several key Linux distros. In general terms, it's an attempt to access uninitialized memory leading to reads from, and then subsequent writes to, a pointer that is fully within attacker's control. Here's a pretty telling crash: bash[3054]: segfault at 41414141 ip 00190d96 ... Soon after posting this entry, I also bumped in the sixth and most severe issue so far, essentially permitting very simple and straightforward remote code execution (CVE-2014-6278) on the systems that are patched against the first bug. It's a "put your commands here" type of a bug similar to the original report. I will post additional details in a couple of days to give people enough time to upgrade.

At this point, I very strongly recommend manually deploying Florian's patch unless your distro is already shipping it. (Florian's patch has been also finally included upstream shortly after I first posted this entry.)

From within the shell itself, the simplest way to check if you already have it installed would be: _x='() { echo vulnerable; }' bash -c '_x 2>/dev/null || echo not vulnerable' If the command shows "vulnerable", you don't have the patch and you are still vulnerable to a (currently non-public) RCE, even if you applied the original one (or the subsequent upstream patch that addressed the issue found by Tavis).

September 25, 2014

Quick notes about the bash bug, its impact, and the fixes so far

We spent a good chunk of the day investigating the now-famous bash bug (CVE-2014-6271), so I had no time to make too many jokes about it on Twitter - but I wanted to jot down several things that have been getting drowned out in the noise earlier in the day.

Let's start with the nature of the bug. At its core, the problem caused by an obscure and little-known feature that allows bash programs to export function definitions from a parent shell to children shells, similarly to how you can export normal environmental variables. The functionality in action looks like this: $ function foo { echo "hi mom"; } $ export -f foo $ bash -c 'foo' # Spawn nested shell, call 'foo' hi mom The behavior is implemented as a hack involving specially-formatted environmental variables: in essence, any variable starting with a literal "() {" will be dispatched to the parser just before executing the main program. You can see this in action here: $ foo='() { echo "hi mom"; }' bash -c 'foo' hi mom The concept of granting magical properties to certain values of environmental variables clashes with several ancient customs - most notably, with the tendency for web servers such as Apache to pass client-supplied strings in the environment to any subordinate binaries or scripts. Say, if I request a CGI or PHP script from your server, the env variables $HTTP_COOKIE and $HTTP_USER_AGENT will be probably initialized to the raw values seen in the original request. If the values happen to begin with "() {" and are ever seen by /bin/bash, events may end up taking an unusual turn.

And so, the bug we're dealing with stems from the observation that trying to parse function-like strings received in HTTP_* variables could have some unintended side effects in that shell - namely, it could easily lead to your server executing arbitrary commands trivially supplied in a HTTP header by random people on the Internet.

With that out of the way, it is important to note that the today's patch provided by the maintainer of bash does not stop the shell from trying to parse the code within headers that begin with "() {" - it merely tries to get rid of that particular RCE side effect, originally triggered by appending commands past the end of the actual function def. But even with all the current patches applied, you can still do this: Cookie: () { echo "Hello world"; } ...and witness a callable function dubbed HTTP_COOKIE() materialize in the context of subshells spawned by Apache; of course, the name will be always prefixed with HTTP_*, so it's unlikely to clash with anything or be called by incident - but intuitively, it's a pretty scary outcome.

In the same vein, doing this will also have an unexpected result: Cookie: () { oops If specified on a request to a bash-based CGI script, you will see a scary bash syntax error message in your error log.

All in all, the fix hinges on two risky assumptions:
  1. That the bash function parser invoked to deal with variable-originating function definitions is robust and does not suffer from the usual range of low-level C string parsing bugs that almost always haunt similar code - a topic that, when it comes to shells, hasn't been studied in much detail before now. (In fact, I am aware of a privately made now disclosed report of such errors in the parser - CVE-2014-7186 and CVE-2014-7187.)

    Update (Sep 26): I also bumped into what seems to be a separate and probably exploitable use of an uninitialized pointer in the parser code; shared the details privately upstream.

  2. That the parsing steps are guaranteed to have no global side effects within the child shell. As it happens, this assertion has been already proved wrong by Tavis (CVE-2014-7169); the side effect he found probably-maybe isn't devastating in the general use case (at least until the next stroke of brilliance), but it's certainly a good reason for concern.

    Update (Sep 26): Found a sixth and most severe issue that is essentially equivalent to the original RCE on all systems that only have the original, maintainer-provided patch.

Contrary to multiple high-profile reports, the original fix was not "broken" in the sense that there is no universal RCE exploit for it - but if I were a betting man, I would not bet on the patch holding up in the long haul (Update: as noted above, it did not hold up). A more reasonable solution would involve temporarily disabling function imports, putting them behind a runtime flag, or blacklisting some of the most dangerous variable patterns (e.g., HTTP_*); and later on, perhaps moving to a model where function exports use a distinct namespace while present in the environment.

What else? Oh, of course: the impact of this bug is an interesting story all in itself. At first sight, the potential for remote exploitation should be limited to CGI scripts that start with #!/bin/bash and to several other programs that explicitly request this particular shell. But there's a catch: on a good majority of modern Linux systems, /bin/sh is actually a symlink to /bin/bash!

This means that web apps written in languages such as PHP, Python, C++, or Java, are likely to be vulnerable if they ever use libcalls such as popen() or system(), all of which are backed by calls to /bin/sh -c '...'. There is also some added web-level exposure through #!/bin/sh CGI scripts, <!--#exec cmd="..."> calls in SSI, and possibly more exotic vectors such as mod_ext_filter.

For the same reason, userland DHCP clients that invoke configuration scripts and use variables to pass down config details are at risk when exposed to rogue servers (e.g., on open wifi). A handful of MTAs, MUAs, or FTP server architectures may be also of concern - in particular, there are third-party reports of qmail installations being at risk. Finally, there is some exposure for environments that use restricted SSH shells (possibly including Git) or restricted sudo commands, but the security of such approaches is typically fairly modest to begin with.

Exposure on other fronts is possible, but probably won't be as severe. The worries around PHP and other web scripting languages, along with the concern for userspace DHCP, are the most significant reasons to upgrade - and perhaps to roll out more paranoid patches, rather than relying solely on the two official ones. On the upside, you don't have to worry about non-bash shells - and that covers a good chunk of embedded systems out there. In particular, contrary to several claims, Busybox should be fine.

Update (Sep 28): the previously-unofficial namespace isolation patch from Florian has eventually made it upstream. You should deploy that patch ASAP.

PS. As for the inevitable "why hasn't this been noticed for 15 years" / "I bet the NSA knew about it" stuff - my take is that it's a very unusual bug in a very obscure feature of a program that researchers don't really look at, precisely because no reasonable person would expect it to fail this way. So, life goes on.

September 02, 2014

CVE-2014-1564: Uninitialized memory with truncated images in Firefox

The recent release of Firefox 32 fixes another interesting image parsing issue found by american fuzzy lop: following a refactoring of memory management code, the past few versions of the browser ended up using uninitialized memory for certain types of truncated images, which is easily measurable with a simple <canvas> + toDataURL() harness that examines all the fuzzer-generated test cases.

In general, problems like that may leak secrets across web origins, or more prosaically, may help attackers bypass security measures such as ASLR. For a slightly more detailed discussion, check out this post.

Here's a short proof-of-concept that should work if you haven't updated to 32 yet: This is tracked as CVE-2014-1564, Mozilla bug 1045977. Several more should be coming soon.

Some notes on web tracking and related mechanisms

Artur Janc and I put together a nice, in-depth overview of all the known fingerprinting and tracking vectors that appear to be present in modern browsers. This is an interesting, polarizing, and poorly-studied area; my main hope is that the doc will bring some structure to the discussions of privacy consequences of existing and proposed web APIs - and help vendors and standards bodies think about potential solutions in a more holistic way.

That's it - carry on!

August 08, 2014

Binary fuzzing strategies: what works, what doesn't

Successful fuzzers live and die by their fuzzing strategies. If the changes made to the input file are too conservative, the fuzzer will achieve very limited coverage. If the tweaks are too aggressive, they will cause most inputs to fail parsing at a very early stage, wasting CPU cycles and spewing out messy test cases that are difficult to investigate and troubleshoot.

Designing the mutation engine for a new fuzzer has more to do with art than science. But one of the interesting side effects of the design of american fuzzy lop is that it provides a rare feedback loop: you can carefully measure what types of changes to the input file actually result in the discovery of new branches in the code, and which ones just waste your time or money.

This data is particularly easy to read because the fuzzer also approaches every new input file by going through a series of progressively more complex, but exhaustive and deterministic fuzzing strategies - say, sequential bit flips and simple arithmetics - before diving into purely random behaviors. The reason for this is the desire to generate the simplest and most elegant test cases first; but the design also provides a very good way to quantify how much value each new strategy brings in to the table - and whether we need it at all.

The measurements of afl fuzzing efficiency for reasonably-sized test cases are remarkably consistent across a variety of real-world binary formats - anything ranging from image files (JPEG, PNG, GIF, WebP) to archives (gzip, xz, tar) - and because of this, I figured that sharing the data more broadly will be useful to folks who are working on fuzzers of their own. So, let's dive in:
  • Walking bit flips: the first and most rudimentary strategy employed by afl involves performing sequential, ordered bit flips. The stepover is always one bit; the number of bits flipped in a row varies from one to four. Across a large and diverse corpus of input files, the observed yields are:

    • Flipping a single bit: ~70 new paths per one million generated inputs,
    • Flipping two bits in a row: ~20 additional paths per million generated inputs,
    • Flipping four bits in a row: ~10 additional paths per million inputs.

    (Note that the counts for every subsequent pass include only the paths that could not have been discovered by the preceding strategy.)

    Of course, the strategy is relatively expensive, with each pass requiring eight execve() per every byte of the input file. With the returns are diminishing rapidly, afl stops after these three passes - and switches to a second, less expensive strategy past that point.

  • Walking byte flips: a natural extension of walking bit flip approach, this method relies on 8-, 16-, or 32-bit wide bitflips with a constant stepover of one byte. This strategy discovers around ~30 additional paths per million inputs, on top of what could have been triggered with shorter bit flips.

    It should be fairly obvious that each pass takes approximately one execve() call per one byte of the input file, making it surprisingly cheap, but also limiting its potential yields in absolute terms.

  • Simple arithmetics: to trigger more complex conditions in a deterministic fashion, the third stage employed by afl attempts to subtly increment or decrement existing integer values in the input file; this is done with a stepover of one byte. The experimentally chosen range for the operation is -35 to +35; past these bounds, fuzzing yields drop dramatically. In particular, the popular option of sequentially trying every single value for each byte (equivalent to arithmetics in the range of -128 to +127) helps very little and is skipped by afl.

    When it comes to the implementation, the stage consists of three separate operations. First, the fuzzer attempts to perform subtraction and addition on individual bytes. With this out of the way, the second pass involves looking at 16-bit values, using both endians - but incrementing or decrementing them only if the operation would have also affected the most significant byte (otherwise, the operation would simply duplicate the results of the 8-bit pass). The final stage follows the same logic, but for 32-bit integers.

    The yields for this method vary depending on the format - ranging from ~2 additional paths per million in JPEG to ~8 per million in xz. The cost is relatively high, averaging around 20 execve() calls per one byte of the input file - but can be significantly improved with only a modest impact on path coverage by sticking to +/- 16.

  • Known integers: the last deterministic approach employed by afl relies on a hardcoded set of integers chosen for their demonstrably elevated likelihood of triggering edge conditions in typical code (e.g., -1, 256, 1024, MAX_INT-1, MAX_INT). The fuzzer uses a stepover of one byte to sequentially overwrite existing data in the input file with one of the approximately two dozen "interesting" values, using both endians (the writes are 8-, 16-, and 32-bit wide).

    The yields for this stage are between 2 and 5 additional paths per one million tries; the average cost is roughly 30 execve() calls per one byte of input file.

  • Stacked tweaks: with deterministic strategies exhausted for a particular input file, the fuzzer continues with a never-ending loop of randomized operations that consist of a stacked sequence of:

    • Single-bit flips,
    • Attempts to set "interesting" bytes, words, or dwords (both endians),
    • Addition or subtraction of small integers to bytes, words, or dwords (both endians),
    • Completely random single-byte sets,
    • Block deletion,
    • Block duplication via overwrite or insertion,
    • Block memset.

    Based on a fair amount of testing, the optimal execution path yields appear to be achieved when the probability of each operation is roughly the same; the number of stacked operations is chosen as a power-of-two between 1 and 64; and the block size for block operations is capped at around 1 kB.

    The absolute yield for this stage is typically comparable or higher than the total number of execution paths discovered by all deterministic stages earlier on.

  • Test case splicing: this is a last-resort strategy that involves taking two distinct input files from the queue that differ in at least two locations; and splicing them at a random location in the middle before sending this transient input file through a short run of the "stacked tweaks" algorithm. This strategy usually discovers around 20% additional execution paths that are unlikely to trigger using the previous operation alone.

    (Of course, this method requires a good, varied corpus of input files to begin with; afl generates one automatically, but for other tools, you may have to construct it manually.)

As you can see, deterministic block operations (duplication, splicing) are not attempted in an exhaustive fashion; this is because they generally require quadratic time (or worse) - so while their yields may be good for very short inputs, they degrade very quickly.

Well, that's it! If you ever decide to try out afl, you can watch these and other cool stats on your screen in real time.

August 04, 2014

A bit more about american fuzzy lop

Fuzzing is one of the most powerful strategies for identifying security issues in real-world software. Unfortunately, it also offers fairly shallow coverage: it is impractical to exhaustively cycle through all possible inputs, so even something as simple as setting three separate bytes to a specific value to reach a chunk of unsafe code can be an insurmountable obstacle to a typical fuzzer.

There have been numerous attempts to solve this problem by augmenting the process with additional information about the behavior of the tested code. These techniques can be divided into three broad groups:
  • Simple coverage maximization. This approach boils down to trying to isolate initial test cases that offer diverse code coverage in the targeted application - and them fuzzing them using conventional techniques.

  • Control flow analysis. A more sophisticated technique that leverages instrumented binaries to focus the fuzzing efforts on mutations that generate distinctive sequences of conditional branches within the instrumented binary.

  • Static analysis. An approach that attempts to reason about potentially interesting states within the tested program and then make educated guesses about the input values that could possibly trigger them.
The first technique is surprisingly powerful when used to pre-select initial test cases from a massive corpus of valid data - say, the result of a large-scale web crawl. Unfortunately, coverage measurements provide only a very simplistic view of the internal state of the program, making them less suited for creatively guiding the fuzzing process later on.

The latter two techniques are extremely promising in experimental settings. That said, in real-world applications, they are not only very slow, but frequently lead to irreducible complexity: most of the high-value targets will have a vast number of internal states and possible execution paths, and deciding which ones are interesting and substantially different from the rest is an extremely difficult challenge that, if not solved, usually causes the "smart" fuzzer to perform no better than a traditional one.

American fuzzy lop tries to find a reasonable middle ground between sophistication and practical utility. In essence, it's a fuzzer that relies on a form of edge coverage measurements to detect subtle, local-scale changes to program control flow without having to perform complex global-scale comparisons between series of long and winding execution traces - a common failure point for similar tools.

In almost-plain English, the fuzzer does this by instrumenting every effective line of C or C++ code (or any other GCC-supported language) to record a tuple in the following format:

[ID of current code location], [ID of previously-executed code location]

The ordering information for tuples is discarded; the primary signal used by the fuzzer is the appearance of a previously-unseen tuple in the output dataset; this is also coupled with coarse magnitude count for tuple hit rate. This method combines the self-limiting nature of simple coverage measurements with the sensitivity of control flow analysis. It detects both explicit conditional branches, and indirect variations in the behavior of the tested app.

The output from this instrumentation is used as a part of a simple, vaguely "genetic" algorithm:
  1. Load user-supplied initial test cases into the queue,

  2. Take input file from the queue,

  3. Repeatedly mutate the file using a balanced variety of traditional fuzzing strategies (see later),

  4. If any of the generated mutations resulted in a new tuple being recorded by the instrumentation, add mutated output as a new entry in the queue.

  5. Go to 2.
The discovered test cases are also periodically culled to eliminate ones that have been made obsolete by more inclusive finds discovered later in the fuzzing process. Because of this, the fuzzer is useful not only for identifying crashes, but is exceptionally effective at turning a single valid input file into a reasonably-sized corpus of interesting test cases that can be manually investigated for non-crashing problems, handed over to valgrind, or used to stress-test applications that are harder to instrument or too slow to fuzz efficiently. In particular, it can be extremely useful for generating small test sets that may be programatically or manually examined for anomalies in a browser environment.

(For a quick partial demo, click here.)

Of course, there are countless "smart" fuzzer designs that look good on paper, but fail in real-world applications. I tried to make sure that this is not the case here: for example, afl can easily tackle security-relevant and tough targets such as gzip, xz, lzo, libjpeg, libpng, giflib, libtiff, or webp - all with absolutely no fine-tuning and while running at blazing speeds. The control flow information is also extremely useful for accurately de-duping crashes, so the tool does that for you.

In fact, I spent some time running it on a single machine against libjpeg, giflib, and libpng - some of the most robust best-tested image parsing libraries out there. So far, the tool found:
  • CVE-2013-6629: JPEG SOS component uninitialized memory disclosure in jpeg6b and libjpeg-turbo,

  • CVE-2013-6630: JPEG DHT uninitialized memory disclosure in libjpeg-turbo,

  • MSRC 0380191: A separate JPEG DHT uninitialized memory disclosure in Internet Explorer,

  • CVE-2014-1564: Uninitialized memory disclosure via GIF images in Firefox,

  • CVE-2014-1580: Uninitialized memory disclosure via <canvas> in Firefox,

  • Chromium bug #398235, Mozilla bug #1050342: Probable library-related JPEG security issues in Chrome and Firefox (pending),

  • PNG zlib API misuse bug in MSIE (DoS-only),

  • Several browser-crashing images in WebKit browsers (DoS-only).
More is probably to come. In other words, you should probably try it out. The most significant limitation today is that the current fuzzing strategies are optimized for binary files; the fuzzer does:
  • Walking bitflips - 1, 2, and 4 bits,

  • Walking byte flips - 1, 2, and 4 bytes,

  • Walking addition and subtraction of small integers - byte, word, dword (both endians),

  • Walking insertion of interesting integers (-1, MAX_INT, etc) - byte, word, dword (both endians),

  • Random stacked flips, arithmetics, block cloning, insertion, deletion, etc,

  • Random splicing of synthetized test cases - pretty unique!
All these strategies have been specifically selected for an optimal balance between fuzzing cost and yields measured in terms of the number of discovered execution paths with binary formats; for highly-redundant text-based formats such as HTML or XML, syntax-aware strategies (template- or ABNF-based) will obviously yield better results. Plugging them into AFL would not be hard, but requires work.

June 22, 2014

Boolean algebra with CSS (when you can only set colors)

Depending on how you look at it, CSS can be considered Turing-complete. But in one privacy-relevant setting - when styling :visited links - the set of CSS directives you can use is extremely limited, effectively letting you control not much more than the color of the text nested between <a href=...> and </a>. Can you perform any computations with that?

Well, as it turns out, you can - in a way. Check out this short write-up for a discussion on how to implement Boolean algebra by exploiting an interesting implementation-level artifact of CSS blending to steal your browsing history a bit more efficiently than before.

Vulnerability logo and vanity domain forthcoming - stay tuned.

March 20, 2014

Messing around with <a download>

Not long ago, the HTML5 specification has extended the semantics for <a href=...> links by adding the download attribute. In a nutshell, the markup allows you to specify that an outgoing link should be always treated as a download, even if the hosting site does not serve the file with Content-Disposition: attachment:

<a href="" download>What a cute kitty!</a>

I am unconvinced that this feature scratches any real itch for HTTP links, but it's already supported in Firefox, Chrome, and Opera.

Of course, there are some kinks: in absence of the Content-Disposition header, the browser needs to figure out the correct file name for the download. In practice, this is always done based on the path seen in the URL. That's not great, because a good majority of web frameworks will tolerate trailing garbage in the path segment; indeed, so does Let's try it out:

<a href="" download>What a cute kitty!</a>

But we shouldn't dwell on this, because the download syntax makes it easy for the originating page to simply override that logic and pick any file name and extension it likes:

<a href="" download="KittyViewer.exe">What a cute kitty!</a>

That's odd - and keep in mind that the image we are seeing is at least partly user-controlled. A location like this can be found on any major destination on the Internet: if not an image, you can always find a JSON API or a HTML page that echoes something back.

It also helps to remember that it's usually pretty trivial to build files that are semantically valid to more than one parser, and have a different meaning to each one of them. Let's put it all together for a trivial PoC:

<a href=""
  download="AltavistaToolbar.bat">Download Bing toolbar from</a>

That's pretty creepy: if you download the file on Windows and click "open", the payload will execute and invoke notepad.exe. Still, is it a security bug? Well... the answer to that is not very clear.

For one, there is a temptation to trust the tooltip you see when you hover over a download link. But if you do that, you are in serious trouble, even in absence of that whole download bit: JavaScript code can intercept the onclick event and take you somewhere else. Luckily, most browsers provide you with a real security indicator later on: the download UI in Internet Explorer, Firefox, and Safari prominently shows the origin from which the document is being retrieved. And that's where the problem becomes fairly evident: never really meant to serve you with an attacker-controlled AltavistaToolbar.bat, but the browser says otherwise.

The story gets even more complicated when you consider that some browsers don't show the origin of the download in the UI at all; this is the case for Chrome and Opera. In such a design, you simply have to put all your faith in the origin from which you initiated the download. In principle, it's not a completely unreasonable notion, although I am not sure it aligns with user expectations particularly well. Sadly, there are other idiosyncrasies of the browser environment that mean the download you are seeing on a trusted page might have been initiated from another, unrelated document. Oops.

So, yes, browsers are messy. Over the past few years, I have repeatedly argued against <a download> on the standards mailing lists (most recently in 2013), simply because I think that nothing good comes out of suddenly taking the control over how documents are interpreted by the browser away from the hosting site. I don't think that my arguments were particularly persuasive, in part because nobody seemed to have a clear vision for the overall trust model around downloads on the Web.

PS. Interestingly, Firefox decided against the added exposure and implemented the semantics in a constrained way: the download attribute is honored only if the final download location is same-origin with the referring URL.