Category: Security

Improving ASLR with internal randomization

~ Nate Lawson ~ 11 Comments

Most security engineers are familiar with address randomization (ASLR). In the classic implementation, the runtime linker or image loader chooses a random base offset for the program, its dynamic libraries, heap, stack, and mmap() regions.

At a higher level, these can all be seen as obfuscation. The software protection field has led with many of these improvements because cracking programs is a superset of exploiting them. That is, an attacker with full access to a program’s entire runtime state is much more advantaged than one with only remote access to the process, filtered through an arbitrary protocol. Thus, I predict that exploit countermeasures will continue to recapitulate the historical progress of software protection.

The particular set of obfuscations used in ASLR were chosen for their ease of retrofitting existing programs. The runtime linker/loader is a convenient location for randomizing various memory offsets and its API is respected by most programs, with the most notable exceptions being malware and some software protection schemes. Other obfuscation mechanisms, like heap metadata checksumming, are hidden in the internals of system libraries. Standard libraries are a good, but less reliable location than the runtime linker. For example, many programs have their own internal allocator, reducing the obfuscation gains of adding protection to the system allocator.

A good implementation of ASLR can require attackers to use a memory disclosure vulnerability to discover or heap fung shui to create a known memory layout for reliable exploitation. While randomizing chunks returned from the standard library allocator can make it harder for attackers to create a known state, memory disclosure vulnerabilities will always allow a determined attacker to subvert obfuscation. I expect we’ll see more creativity in exercising partial memory disclosure vulnerabilities as the more flexible bugs are fixed.

ASLR has already forced researchers to package multiple bugs into a single exploit, and we should soon see attackers follow suit. However, once the base offsets of various libraries are known, the rest of the exploit can be applied unmodified. For example, a ROP exploit may need addresses of gadgets changed, but the relative offsets within libraries and the code gadgets available are consistent across systems.

The next logical step in obfuscation would be to randomize the internals of libraries and code generation. In other words, you re-link the internal functions and data offsets within libraries or programs so that code and data are at different locations in DLLs from different systems. At the same time, code generation can also be randomized so that different instruction sequences are used for the same operations. Since all this requires deep introspection, it will require a larger change in how software is delivered.

Fortunately, that change is on the horizon for other reasons. LLVM and Google NaCl are working on link-time optimization and runtime code generation, respectively. What this could mean for NaCl is that a single native executable in LLVM bitcode format would be delivered to the browser. Then, it would be translated to the appropriate native instruction set and executed.

Of course, we already have a form of this today with the various JIT environments (Java JVM, Adobe ActionScript, JavaScript V8, etc.) But these environments typically cover only a small portion of the attack surface and don’t affect the browser platform itself. Still, randomized JIT is likely to become more common this year.

One way to implement randomized code delivery is to add this to the installer. Each program could be delivered as LLVM IR and then native code generation and link addresses could be randomized as it was installed. This would not slow down the installation process significantly but would make each installation unique. Or, if the translation process was fast enough, this could be done on each program launch.

Assuming this was successfully deployed, it would push exploit development to be an online process. That is, an exploit would include a built-in ROP gadget generator and SMT solver to generate a process/system-specific exploit. Depending on the limitations of available memory disclosure vulnerabilities and specific process state, it might not be possible to automatically exploit a particular instance. Targeted attacks would have to be much more targeted and each system compromised would require the individual attention of a highly-skilled attacker.

I’m not certain software vendors will accept the nondeterminism of this approach. Obviously, it makes debugging production systems more difficult and installation-specific. However, logging the random seed used to initiate the obfuscation process could be used to recreate a consistent memory layout for testing.

For now, other obfuscation measures such as randomizing the allocator may provide more return on investment. As ROP-specific countermeasures are deployed, it will become easier to exploit a program’s specific internal logic (flags, offsets, etc.) than to try to get full code execution. It seems that, for now, exploit countermeasures will stay focused on randomizing and adding checksums to data structures, especially those in standard libraries.

But is this level of obfuscation where exploit countermeasures are headed? How long until randomized linking and code generation are part of a mainline OS?

State space explosion in program analysis and crypto

~ Nate Lawson ~ 11 Comments

While analyzing some software the other day, I was struck by the duality of cryptanalyzing block ciphers and program analysis techniques. Both present a complex problem and similar tools can be applied to each.

The three main program analysis techniques are dynamic analysis (e.g., execution traces or debugging), symbolic execution, and abstract interpretation. Each has its place but also has unique disadvantages.

Dynamic analysis tests one set of paths through a program with some variance in inputs (and thus program state). Fuzzing is an attempt to increase the path coverage and number of states for each path via random inputs. Smart fuzzing directs the choice of these inputs by discovering constraints via an SMT solver. While dynamic analysis is fast and doesn’t give any false positives (a crash is a crash), it is extremely limited in coverage, both of code paths and program states.

Symbolic execution covers all possible inputs and code paths but has really poor performance. Since it models the exact behavior of the program for each state and code path, it does not lead to false positives or false negatives. The downside is that it is much too slow to handle more than a few simple functions.

Abstract interpretation has characteristics in common with both. It deploys three-valued logic (0, 1, and “unknown”) to predict a program’s behavior. While not fast, it is fast enough to be performed on the whole program (like dynamic analysis) and gives better coverage of inputs without the nondeterminism of fuzzing. Unlike symbolic execution, it is an under-approximation of behavior and thus leaves many questions unanswered. However, unlike fuzzing, you know exactly which states are indeterminate and can iterate on those areas.

One big problem with the two static techniques is state space explosion. Every time a conditional branch is encountered, the number of possible states doubles. Thinking cryptographically, this is analagous to adding one bit to a cipher’s key or a 1-bit S-box.

All modern block ciphers are based on the substitution and permutation primitives. Permutation is a linear operation and is easy to represent with a polynomial. Substitution (e.g., an S-box) is non-linear and increases the degree of the polynomial drastically, usually squaring it.

Algebraic cryptanalysis is a means of solving for a key by treating a cipher as a system of overdetermined equaations. What algorithms like XL do is convert a set of polynomials into linear equations, which are solvable by means such as Gaussian elimination. XL replaces each polynomial term with a single new variable, and then tries to reduce the equations in terms of the new variables. While it hasn’t broken AES yet, algebraic cryptanalysis will need to be accounted for as new ciphers are designed.

The duality between program analysis and cryptanalysis is interesting to me. Would it be useful to represent unknown conditional branches as bits of a key and the entire program as a cipher, then attempt to reduce with XLS? What about converting cipher operations on bits of an unknown key to conditional branches (or jump tables for bytewise operations) and reducing using abstract interpretation?

While this musing doesn’t have practical applications, it’s still fun to find parallels between distinct areas of your work.

Encrypted Google Docs done well

~ Nate Lawson ~ 6 Comments

There’s a nice new paper out called “Private Editing Using Untrusted Cloud Services” by Yan Huang and David Evans. They also provide a Firefox extension that implements their scheme. I like their approach for a few reasons.

First, their core advancement is to implement incremental encryption efficiently. Incremental encryption is an often-overlooked method of performing insert, delete, and replace operations on ciphertext. It’s a useful branch of applied cryptography — one that should be used more.

However, the naive implementation of incremental encryption would involve encrypting each character separately, slowing down client/server communications a lot. To get around this, they organize deltas in an Indexed Skip List. This makes it easy to group characters into variable-sized blocks, as well as update them quickly.

I am also happy that they deployed their code as a browser extension instead of client-side JavaScript. As I have mentioned before, client-side JS crypto is a bad idea. There are fundamental integrity and trust problems that can’t be solved in that environment. However, except for the potential for side-channel attacks and lack of control of low-level details like key zeroization, JavaScript crypto in a browser extension is more acceptable, as long as it is properly reviewed. This is one use of the Stanford JS crypto library that is defensible.

For those of you implementing “secure” note-taking web services, this is the right way to do it.

Baysec update and announcement change

~ Nate Lawson ~ 4 Comments

The next Baysec is April 26, 7-11 pm at Irish Bank. Next month will be the fourth anniversary of Baysec!

I won’t be announcing these events on this blog any more because I’d like to reserve it for articles instead. The Baysec announcements are ephemeral and of no value to people outside the Bay Area.

I will still be posting Baysec announcements on the @rootlabs Twitter account. And if you want to participate in discussing Baysec events, please join the mailing list at baysec.net. It is very low traffic — less than 10 messages per month.

More certs may indicate less security

~ Nate Lawson ~ 14 Comments

In my last post, I mentioned how warning users when a previously-seen cert changes may generate false positives for some sites. If a website has a multiple servers with different certs, the browser may often generate spurious errors for that site. But could this be a symptom of a genuine security problem?

Citibank appears to have one certificate per server. You can verify this yourself by going to their website and multiple times, clearing your browser each time. Clicking on the SSL icon to the left of the URL will show a different cert.

Here are the first 4 bytes of  three serial numbers of certs observed at Citibank:

  • 43:8e:67:66
  • 61:22:d4:81
  • 3e:f4:5b:7c

The Citibank certs are all identical except for a few fields. As you would expect, the domain name (CN) field is identical for each. The organizational unit (OU) differs (e.g., “olb-usmtprweb3” versus “…web1”), but this field is not interpreted by browsers and is more of a convenience. The web server’s public key is different in each cert. And, of course, the serial number and signature fields also differ, as they should for all certs.

On the other hand, Wells Fargo appears to have only one cert. This cert (serial 41:c5:cd:90) is the same even after accessing their site via a proxy to ensure some load-balancing magic isn’t getting in the way. It’s easy to ignore this difference, but there might be something else going on.

Protecting the web server’s private key is one of the most important operational security duties. If it is discovered, all past and present encrypted sessions are compromised. (Yes, I know about DHE but it’s not widely used). After cleaning up the mess, the organization needs to get a new certificate and revoke the old one. This is no easy task as CRLs and OCSP both have their downsides.

One key question to ask an opsec department is “have you ever done a live cert revocation?” It’s one of those things that has to be experienced to be understood. In the recent Comodo fiasco, leaf cert revocations were embedded in browser software updates because the existing revocation mechanisms weren’t reliable enough.

Since web servers run commodity operating systems, most big sites use a hardware security module (HSM) to protect the private key. This is a dedicated box with some physical tamper resistance that is optimized for doing private key operations. By limiting the API to the server, HSMs can be hardened to prevent compromise, even if the server is hacked. The main downsides are that HSMs are expensive and may not live up to the original security guarantees as the API surface area grows.

Now, back to the two banks. Why would one have multiple certs but not the other? Certificates cost money, so if you’re offloading SSL to a single accelerator, there’s no reason to give it multiple certs. If each server has a dedicated HSM, you could use separate certs or just generate one and export it to all the others. You need to do this anyway for backup purposes.

This is just supposition, but one thing this could indicate is a different approach to securing the private key. Instead of generating one cert and private key, you create one per server and store it without an HSM. If a server gets compromised, you revoke the private key and move on. This might seem like a good idea to some since the cost of a cert must be lower than an HSM. However, the ineffectiveness of revocation today shows this to be a dangerous choice.

There may be other explanations for this. Perhaps Citi uses individual HSMs and Wells Fargo has a single SSL accelerator with plaintext HTTP in the backend. Perhaps they got a bargain on certs by buying in bulk. However, any time a system has more keys than necessary, it can lead to complicated key management. Or worse, it may indicate a weaker system design overall.

There’s no way to know the real story, but it’s good food for thought for anyone else who might be considering multiple certs as a substitute for strong private key protection. Cert revocation doesn’t currently work and should not be relied on.

Fixing the SSL cert nightmare

~ Nate Lawson ~ 36 Comments

Recently, there has been an uproar as Comodo failed to do the one thing their business is supposed to do — issue certificates only to authenticated parties. (But what do you expect for a $5, few-questions-asked cert?) I’m glad there’s renewed focus on fixing the current CA and SSL browser infrastructure because this is one of the largest and most obvious security flaws in an otherwise successful protocol.

In response to this compromise, many people are recommending drastic changes. One really bad idea is getting rid of root certs in favor of SSH-style host verification. There are also some good proposals though:

Paring down number of root certs in common browsers

Root cert proliferation has gotten out-of-hand in all the major browsers. It would be great if someone analyzed which CAs are essential for all hostnames in the top 1000 sites. That info could be used to prune root certs to a smaller initial set.

It is unlikely the browser vendors will do this work themselves. They have clear financial and political incentives to add new CAs and few incentives to remove them. Even if you just consider the collateral damage to innocent sites when a root cert is removed, the costs can be huge.

The EFF had a promising start but not as much appears to have been done recently. However, they did publish this article including a list of CAs yesterday, sorted by number of times each CA signed an unqualified hostname. (Comodo is only second to Go Daddy, by the way, and Verisign is pretty high as well).

Notifying the user when a site’s cert changes

This is a pretty simple idea that has some merit. Your browser would cache the cert the first time you connect to a given server. If it changes when you revisit the site, you would get a warning. (Bonus: maintain a worldwide cache of these certs and correlate observations from various locations, like Perspectives or Google’s DNS-based cert history.)

This would have helped in the Comodo case but wouldn’t notify the user if the compromised CA were the same as the server’s current one. This scenario actually occurred in 2001 when Verisign issued another Microsoft code-signing cert to someone posing as an employee.

One usability problem of persistent cert chains is the fact that some sites use many different certs. For example, Citibank appears to have one cert per webserver, something we discuss more in our next post. This means users would get lots of spurious warnings when using their site.

Keep a hit count of CAs previously seen

This is a simple idea I came up with the other day that may be worth investigating. I’d like to see a CA “hit count” displayed alongside the list of root certs in my browser. This would help in auditing which certs are actually used by sites I visit and which are dormant. This could include the hostnames themselves as a collapsible list under each CA cert.

The important goal in considering all these proposals is to avoid making the problem worse. Nearly everyone agrees that the current situation has become untenable, and we need solutions to certificate problems now.