Archive for the 'Security' Category

Integer overflows

Wednesday, November 1st, 2006

"What is a string library? It's a way to pretend that computers can manipulate strings just as easily as they can manipulate numbers."

-- Joel Spolsky, The Law of Leaky Abstractions.

Most C++ code uses the integer mod 232 (or 264) type C++ calls "int" as if they were integers. This is great for performance -- many operations on int32 are a single CPU instruction -- but dangerous for security and correctness when the numbers can be large. This can cause security holes in at least two ways.

First, code might use int32 arithmetic to decide how much memory to allocate. Consider an image decoder that allocates width * height * 4 bytes to store RGBA pixels and then decodes the image data into the structure. But since width and height are unsigned ints, it doesn't really allocate width*height*4 bytes; it allocates width*height*4 mod 232 bytes. If the integer used to decide how much memory to allocate has overflowed in such a way that it comes out as a small integer, the code is likely to overflow the buffer as it writes the decoded image into the structure.

Second, code might use int32 arithmetic to decide when to deallocate an object. In code that uses reference counting, an extra call to "release" can obviously lead to a dangling pointer situation. But thanks to integer overflows, 232 unbalanced calls to "addref" followed by a normal "release" can have the same effect. (Luckily, you can't cause this situation by merely making 232 objects point to a specific object, because you'd run out of memory first. So this could be addressed by auditing for addref-without-release leak bugs rather than modifying the addref function to make it safer.)

Explicit checks

Some code in Gecko has explicit checks to prevent overflows. (This must be done carefully -- "width*height*4 > 232" doesn't mean anything to a C++ compiler!) If you remember to think "integer mod 232 or 264" every time you see "int", you may be able to avoid introducing new security holes due to integer overflow when you write code.

Michael Howard at Microsoft advocates this approach, at least for C code that is used near things like allocation sizes and reference counts, and provides functions to do checked arithmetic operations. These functions return a boolean indicating whether the arithmetic operation succeeded. This leads to code where it is hard to see what calculation is being done but easy to see that each step of the calculation is done safely.

Safe integer classes

Another strategy is to avoid using "int", at least in code used to compute allocation sizes, and instead use a "safe" integer class. A safe class might do correct arithmetic on large numbers, allocating extra memory when needed, but perhaps that is overkill for keeping allocations safe. A proponent of this approach might say "int is the new char *", referring to how string buffer overflows have been nearly eliminated through the use of string classes, and make fun of Joel Spolsky for the quote at the beginning of this post.

David LeBlanc, also at Microsoft, advocates a slightly different approach: using a class that treats overflow as an error and can throw exceptions. This keeps arithmetic formulas readable at the expense of having to design the function to handle exceptions correctly.

Static analysis can be used to scan for calls to malloc that use "int" and need to be converted to using SafeInt.

Will Gecko soon have a multitude of integer classes, each with different performance characteristics, signedness, and overflow behavior? Probably not, because numbers used to decide how much memory to allocate are almost always unsigned integers where overflows can be treated as errors. But I wouldn't be surprised to see different parts of the code use different strategies, with C code using the "explicit checks with helpers" strategy and XPCOM C++ code using another strategy.

Other languages

Many languages share C++'s behavior of exposing "integer mod 232" types as "int", but JavaScript and Python are two major exceptions. JavaScript has a hybrid "number" type that is sometimes stored as an integer and sometimes stored as a floating-point number. Overflowing integer arithmetic turns your numbers into floating-point numbers, while treating a floating-point number as a bit field tries to turn it back into an integer by computing its value mod 232. While JavaScript's behavior is more useful in most situations than wrapping around, you wouldn't want to use it for memory allocation.

Python instead takes advantage of its dynamic type system to make integers safe. Overflowed integers are replaced with a "long integer" type that is slower to operate on but has safe, correct behavior for integers of any size (until you run out of memory).

Memory safety bugs in C++ code

Wednesday, November 1st, 2006

C++ lets developers work with raw pointers, allowing some performance tricks not available in higher-level languages. By allowing developers to decide when objects are allocated and deallocated, developers have the flexibility to choose between (or mix and match) reference counting, various forms of tracing garbage collection, and ad-hoc calls to "new" and "delete". Developers also have the ability to allocate some objects on the stack rather than the heap, improving performance. While C++ is not the only language that allows stack allocation, it is one of the few that lets you maintain linked lists of stack-allocated objects.

C++ also allows developers to do manual pointer arithmetic, making it possible to steal bits from pointers or implement XOR linked lists. Arrays use implicit pointer arithmetic without bounds-checking, which is nice for performance when bounds-checking would be redundant.

Unfortunately, most C++ compilers do not include theorem provers, so they cannot require you to declare invariants and provide enough proof hints to explain why your use of raw pointers is safe. As a result, it is easy to have bugs that lead to severe security holes.

Common types of memory safety bugs

These memory safety bugs usually manifest themselves as crashes. They're also usually exploitable to run arbitrary code.

  • Using a dangling pointer. A simple read from a dangling pointer usually won't cause too much damage, except perhaps to privacy. But writing to a dangling pointer can corrupt another data structure, and freeing a dangling pointer can leave another data structure open to future corruption. Worst, calling a virtual member function on a dangling pointer will jump to a memory location based on a vtable pointer that is likely to have been overwritten, easily leading to arbitrary code execution. Most of the memory safety bugs I have found in Gecko involve dangling pointers.
  • Buffer overflows, also known as "writing past the end of a string or array". These are the best-known memory safety bugs, and among the first to be exploited to run arbitrary code. They're dangerous whether the array is on the heap or the stack, and whether the overflow is as long as the attacker wants or a single byte.
  • Integer overflows, bugs due to forgetting that what C++ calls "int" is really "integer mod 232" (or 264). If int computation is used to decide how much memory to allocate, overflow can lead to a buffer-overflow situation. If reference counting is implemented using an int counter, overflow can lead to an object being freed prematurely, creating a dangling-pointer situation.

Safe crashes

Several common types of crashes that are not security holes:

  • Dereferencing NULL. Most operating systems never allocate page 0, so userland programs can assume that dereferencing null is a safe crash. This is good because null dereferences are significantly harder to prevent than uses of dangling pointers.
  • Too much recursion. Most operating systems have a guard page at the stack limit to prevent your stack and heap from colliding. This is good because preventing too-much-recursion bugs is hard and has historically not been necessary.

Note that some operating systems have bugs or design flaws that turn these "safe" crashes into security holes. Until recently, Windows had a bug that turned null dereferences in some programs into security holes. And at least as of 2005, some operating systems do not guarantee that null dereferences and too-much-recursion are crashes. IMO, those operating systems need to be fixed, so developers can continue treating null-dereference crashes as having the same severity across operating systems.

Bundled software in security updates

Saturday, October 28th, 2006

Today's Java security update includes a checked-by-default "Install Google Toolbar for Internet Explorer" option. Shame on you, Sun and Google. Automatic security updates are no place to push unrelated, bundled software. Making security updates annoying hurts security almost as much as making security updates complicated: users will be less inclined to update next time.

This is similar to how Flash updates attempt to install the Yahoo Toolbar. It's certainly not as bad as the frequently updated AOL Instant Messenger, which turns on the "Today window" popup on every AIM account and adds a "Netscape ISP" icon to the desktop with every security update. But I thought Google was trying to set a good example.

Safari security hole fixed

Tuesday, August 1st, 2006

Today's Mac OS X security update includes a fix for a Safari/WebKit security hole I reported :)

Description: A maliciously-crafted HTML document could cause a previously deallocated object to be accessed. This may lead to an application crash or arbitrary code execution. This update addresses the issue by properly handling such documents. Credit to Jesse Ruderman of Mozilla Corporation for reporting this issue.

Microsoft patches UI race condition holes in IE

Thursday, December 22nd, 2005

Microsoft has finally fixed some UI race condition holes in Internet Explorer. I think the holes they just fixed include some of the holes I first reported to them in March 2004 and posted to Full Disclosure in July 2004, and which were known the whole time to allow e.g. spyware installation.

Microsoft's fix involves disabling the "Run" button for about a second. One interesting difference between Microsoft's fix and Mozilla's fix is that Internet Explorer doesn't make the button visibly disabled; instead, it makes the button ignore clicks and keypresses for a short period of time. This works well given Microsoft's short timeout of 1 second (compared to Firefox's 2-3 seconds, which might be overkill).

Updated Greasemonkey scripts

Thursday, December 1st, 2005

I updated a few of my Greasemonkey scripts to work with versions of Greasemonkey that use XPCNativeWrappers. Greasemonkey 0.5 introduced the use of XPCNativeWrapper for the document object (but only when running on "Deer Park" builds of Firefox that were leading up to Firefox 1.5, not when running on Firefox 1.0.x). Greasemonkey 0.6.4 uses XPCNativeWrappers for everything except unsafeWindow, including the script's global scope. Using XPCNativeWrappers increases security but requires some scripts to be modified.

Most of my scripts didn't require any changes. Several only required minor changes to work with XPCNativeWrappers, such as using addEventListener instead of setting the onclick property.

The trickier scripts to fix had relied on the ability to set properties on DOM objects. I refactored Valid XHTML and Drag 43 Things to use closures instead.

Another problem I ran into was that the normal XMLHttpRequest syntax does not work with XPCNativeWrappers (bug 318489). instant voting used XMLHttpRequest, so I modified it to use GM_xmlhttpRequest instead.

I also updated Pike's Google Maps Mousewheel Zooming script to work with Greasemonkey 0.6.4. This was the most difficult script to update because it interacts with page scripts rather than just interacting with a DOM. The normal way for a Greasemonkey 0.6.4 script to interact with page scripts is to use unsafeWindow, but using it allows the page to see the source of your script, and in some cases allows the page to call GM_ functions. (It would be bad if an evil web page were able to use GM_xmlhttpRequest, since it is not restricted with a same-host policy.) One might argue that I trust Google, which is true, but I don't trust, which is also matched by the script's URL pattern. My version of the script works by setting location.href to a "javascript:" URL when it wants to call in-page functions. I think this is safe and hides the Greasemonkey script's functions from the JavaScript stack seen by webpage functions.

I also found out that my Valid XHTML script was broken in Greasemonkey 0.6.4 because it uses DOMParser, probably for the same reason scripts using XMLHttpRequest are broken. I gave up and used unsafeWindow to access DOMParser.

Firefox 1.5 released

Tuesday, November 29th, 2005

Firefox 1.5 has been released! If you've been using Firefox 1.5 Release Candidate 3, congratulations: you already have Firefox 1.5.

Power users upgrading from Firefox 1.0.7 will appreciate draggable tabs, a much faster Back button, and the replacement of many error dialogs with error pages. Web developers and can now take advantage of SVG, Canvas, E4X, and several new CSS selectors and properties. See the release notes or my detailed changelog for more about what's new.

Firefox 1.5 also includes a number of security fixes, as well as architectural changes that should reduce the number of security holes without us having to enumerate the holes. These changes can also be thought of as making it easier to write code that doesn't contain security holes. For example, XPCNativeWrappers, which isolate JavaScript in extensions and Firefox itself from JavaScript in web pages they manipulate, have been improved and turned on by default for extensions.

Equally important for security is an overhaul to the software update system. From now on, security updates will be small binary patches, usually between 200KB and 500KB. These updates can be installed with one click, in contrast to using the new version's installer (like you would to update from Firefox 1.0.6 to Firefox 1.0.7). Update notification has also been improved; the subtle red button in the menu bar has been replaced with a dialog. The result of these changes is that it's now much easier to keep your copy of Firefox up to date.

For an idea of the size of updates, the update from Firefox 1.5 RC2 to RC3 (fixing two bugs) on Windows was 218K, while the update from RC1 to RC2 (fixing about ten bugs) was 390K. Major updates, such as the update from Firefox 1.5.0.x to Firefox 2.0, will likely be bigger but I don't know how much bigger. The binary patch system is based on bsdiff; you can read about the algorithm if you're interested.

Security holes in Google Desktop Search fixed

Sunday, July 17th, 2005

Google recently fixed several holes in Google Desktop Search that I found. This is the email I sent to to report the holes:

This combination of security holes in mulitple products allows an attacker to read text files indexed and cached by Google Desktop Search. Its success rate is proportional to the amount of time the attacker can keep the victim on the attacker's site and the victim's CPU speed. I think all parts of this attack would work against both Firefox and Internet Explorer, but I've only tested part 1 and only in Firefox.

Recover the URL for the home page of Google Desktop Search

The URL for the front page of Google Desktop Search is for some 10-digit string nnnnnnnnnn. If the string is incorrect, GDS returns a page that says "Invalid Request". This seems to be a second line of defense against XSS and CSRF attacks.

Most browsers have information leaks that allow web scripts to determine whether a link is visited. The attacker assumes that the user has visited the GDS start page with the correct value for nnnnnnnnnn recently enough that the URL is in the browser's global history. Based on my experiments and calculations, it would take several days of CPU time for a script in an untrusted web page in Firefox to find out which of the 10^10 links of the form is visited. An attacker might try to keep a victim on a page for several days, or might try to keep a large number of users on his site for a shorter peroid of time. I don't know what algorithm generates the value nnnnnnnnnn, so I don't know if it has weaknesses that might allow the attacker's script to test fewer than 10^10 URLs.

Solutions: GDS could use a longer salt, to make iterating through every possible salt value harder. GDS could restrict salts to single use, but I think this would break too many things. Firefox (and other browsers) could plug the information leaks in global history.


Perform a Princeton DNS attack

First, make resolve to an IP under the control of the attacker, with a short TTL. Make the victim load, which contains a script. Then make resolve to The script then creates an iframe that loads and uses cross-frame scripting to control the page served by GDS.

You can check that GDS does not prevent this part of the attack by loading GDS and then replacing in the URL with (which resolves to

Solutions: GDS could reject requests where the hostname is not "" or "localhost" (IMO, the HTTP protocol requires it to do so). Firefox, Windows XP, the Windows XP firewall, or my ISP could prevent "external" DNS names from resolving to "internal" IP


Combining the holes

Once the attacker has script access to, has resolving to, and knows the hash for the home page, he can search for text files and view cached text files. (The links to cached text files are absolute and have as the hostname, but they continue to work when is replaced by, which resolves to

I sent this email on Feb 13, 2005. The first part was fixed in version 20050227 by making the salt longer. The second part was fixed in version 20050325 by making GDS reject requests with hostnames other than "" and "localhost". Google started pushing the updated version to existing users on June 2, 2005, so most users should be upgraded by now. You can see what version of GDS you have by clicking "About".

This is not the same as the hole found by Rice students (Slashdot article), which had been fixed previously.