And Now For A Few Words About HP’s “Scrawlr”

Mike Tracy | June 26th, 2008 | Filed Under: Defenses, Malware, New Findings

1.

Some of my favorite reads (there are others) have recently written about about Scrawlr and some of what I have read has been critical. Critical enough? Depending on your level of pedantry with respect to webapp security and/or free software, probably not.

Stop that. Right now. Overlook the limitations of the tool that was released, realize that this is a closely targeted thing designed to help alleviate a specific problem. Go back and think a little harder about what is going on and why this is actually A Good Thing(tm).

This scanner, released as part of the advisory, is specifically designed to help people who run websites that have been targeted by this ongoing and massive SQL injection attack shore things up. The tool has limitations. Quoted from a text file included with the Scrawlr package:

This is a free tool and is intended to find SQL Injection vulnerabilities on pages that hackers can discover using a simple crawler or google query. This application mimics a search engine crawler and lacks the advanced crawling and auditing features of tools such as WebInspect, DevInspect, QAInspect, and AMP. Thus Scrawlr will only find SQL Injection vulnerabilities on GET Parameters; Scrawler will not submit forms, nor audit them. The list below summarizes the limitations:

• 1500 Max Crawled URLs
• No Script parsing during crawl
• No Flash parsing during crawl
• No form submissions during crawl (No POST Parameters)
• Only simple proxy support
• No authentication or login functionality
• Does not check for blind SQL injection

The scanner is built to look for things being indexed by search engines. If those sites are fixed, 99.999% of the problem should go away.

Trying to compare Scrawlr to a full blown SQL Injection scanning tool is like comparing a letter opener to a Swiss Army Knife. Sure, you can do other things with a letter opener (and some of you probably want to slit my throat for that simile. That’s fine, use the knife) —- but its stated purpose is to open letters.

2.

The limitations aren’t that bad. Take the biggest one, authentication. I tried it. For the vast majority of sites, “authentication” means “HTTP forms that set cookies”. For those types of sites, it was easy to get the tool to operate against sites “post authentication”. (I didn’t try for basic/ntlm/digest —- I don’t have a ready test subject. I’d be surprised if it worked.)

Using burp suite do the following:

1. Login to the application using a web browser
2. record the Cookie: header
3. in burp go into the Proxy -> Options tabs
4. go to the “match and replace” section
5. add a new header
   • Type: request-header
   • Match: ^Accept.*$
   • Replace: Cookie:
6. point Scrawlr at your running proxy

Basically, just replacing the Accept: */* header that Scrawlr sends with a Cookie header.

Yay! A free tool that people can use to see if their sites are vulnerable to mischief. Plus! A free code scanner and a free sort of maybe web application firewall to help them protect themselves. Your old ASP sites are now safe from all this ruckus.

3.

I spent some time talking about this with colleagues (colleague n. drinking buddy) at ChiSec last night [if you weren’t there it was a blast and you should come to the next one -ed.] and as much as I love the idea behind this, consternation is bubbling beneath the surface.

What I’m having trouble understanding are the motivations of Microsoft and HP and their estimation of how effective this will actually be. This is either Defense In Depth’s red-headed stepchild cum marketing ploy or… Not sure I actually see an “or”. Half-baked code analyzer (ok I don’t really know that but…)? Check. Web Application Firewall Lite? Check. Hey! Get the guys at SPI to throw in a cripple-ware SQL injection scanner and we’re all set to at least appear like we are trying in some way to maybe have a chance at helping a person or two.

Great!

I want a count of the owners of target audience websites who actually read the advisory, understand it, realize they are affected and then actually use any of the schwag provided to help them solve their problems.

Microsoft seems like a good egg for going to all this trouble and HP gets their name on it. Maybe people will come sniffing around for a “real” security tool or two. Humbug I say!

In the end, motivations are incidental. I’m really just interested in seeing how effective this is.

5 Comments

Introduced: A resolution resolving the semantic quarrel over malloc checking.

Thomas Ptacek | April 17th, 2008 | Filed Under: Defenses, Uncategorized

This is all my fault.

Many moons ago, I wrote a blog post chiding developers for checking the return value of malloc, the C function that allocates chunks of memory for programs to work with. When malloc fails, it returns NULL. According to Hoyle, you’re meant to check for that value, because malloc can fail at absolutely any time (you are not the only program claiming memory).

I stand by that argument, and by most of the wording of that blog post. Now about that word “most”.

Dave LeBlanc and I go back, though he may not remember that. Last bubble, we were dev leads on competing products. We’ve taken different career paths, and, long story short, he’s technically now more of an authority on secure coding than I am. And I’m telling you this because LeBlanc’s response to my last post is —- faithful paraphrase —- “are you high?”

LeBlanc thinks you’d have to be not check malloc returns, because:

• not checking will inevitably crash the program, and crashes are bad,

• not checking leads to the bug class Dowd found, and

• not checking leads to the bug class Dowd found.

LeBlanc is right. I am wrong. “Not checking” is bad. Let me make a very slight semantic adjustment, so that I might be inassailably correct (again).

Here are three (extremely contrived) code examples. The first, let’s call, “unchecked”. It simply doesn’t check the return of malloc.

#define hostile /**/



void *

_setup(unsigned hostile slot, unsigned hostile id) { 

        u_int32_t *slots = malloc(SLOTS_SIZE);



        slots[slot] = id; // XXX write32 corruption



        return slots;

}

The second, we’ll call “caller-checks”. As you can see, it does.

#define hostile /**/



void *

_setup(unsigned hostile slot, unsigned hostile id) { 

        u_int32_t *slots = NULL;



        if((slots = malloc(SLOTS_SIZE))) 

                slots[slot] = id;



        return slots;

}

Now the third, which looks suspiciously like the first, we’ll “callee-checks”.

#define hostile /**/



void *

_setup(unsigned hostile slot, unsigned hostile id) { 

        u_int32_t *slots = malloc(SLOTS_SIZE);



        // NOT REACHED ON FAILURE



        slots[slot] = id;



        return slots;

}

What’s the difference between the first and the third? In the third, if malloc fails, it does not return NULL. It instead hands the program off to a recovery regime, which, by default, safely and immediately ends the program.

What’s the difference between caller-checks and callee-checks?

First, callee-checks is safer. You can’t screw it up. The worst you can do is write a program that will abruptly terminate. This is far better than the current worst-case scenario, in which manifestly common programmer errors allow Mark Dowd to upload malicious code into your program.

Second, callee-checks is cleaner. In the caller-checks case, not only does “setup” need to check, but so does “setup“‘s caller, and it’s caller’s caller, and it’s caller’s caller’s caller, all the way down to the place where your program inevitably gives up and terminates the program.

“But, Thomas”, you say, “not all programs do give up and abort. Some have policies for handling out-of-memory conditions”. And so they do. And in most cases, those policies are global, and can simply be substituted for the default behavior of exiting the program.

But I will grant you that in many cases, you have a genuinely useful recovery regime that is specific to one code-path —- say, an arena-style allocation regime for a particular user request —- and no global policy will help. So, I submit to you a fourth option, which I will not name, and which looks suspiciously like example (2):

#define hostile /**/



void *

_setup(unsigned hostile slot, unsigned hostile id) { 

        u_int32_t *slots = NULL;



        if((slots = unsafe_malloc(SLOTS_SIZE))) 

                slots[slot] = id;



        return slots;

}

Did you see the difference? It’s subtle. But it’s also easy to grep for and easy to check.

I am an advocate for checking malloc —- callee-checks style. It is simply harder to screw up, and, in the overwhelming majority of cases, which you can check for yourself by randomly sampling Google Code Search, it costs you nothing in terms of reliability of functionality. Stop caller-checking malloc.

To LeBlanc’s other point about C++ and constructors throwing exceptions, I refer him to Cargill, or back to our blog, noting that exceptions are themselves inherently dangerous. “When a language feature requires you to be that-language-feature-safe”, I believe I said, “you have a security problem”.

As for his specific example: you can’t blindly throw exceptions from a ctor. Even Meyers (MECv1, Item 9) catches that one. DON’T DATE ROBOTS!

55 Comments

Dowd’s Flash Report: What Have We Learned?

Thomas Ptacek | April 15th, 2008 | Filed Under: Defenses

How nasty is the Flash vulnerability Dowd found?

Combined with any DNS vulnerability or any high-profile cross-site scripting vulnerability, the weaponized version of this attack would probably clock in at tens of thousands of compromised browsers per minute.

Is this a new bug class?

Sort of. It depends on what you mean by the term “class”. For example: most researchers consider heap overflows a seperate bug class from stack overflows. In reality, though, the same underlying coding error causes both vulnerabilities: poorly bounded copies. On the other hand, epistimologically, integer overflows are a new bug class, because the underlying coding error is a type violation, which creates an unbounded copy.

See how I used the word “epistemologic” there? That means you don’t care about the difference. Wild writes from NULL pointers are probably their own bug class.

So this is like the heap overflow revelation in the late 90s? NULL pointers are exploitable now?

No. Learn everything you can from Dowd’s paper and NULL pointers still aren’t usually exploitable:

• They need to be written to, not read from; lots of fuzzer advisories trace down to loads, not stores, from NULL.

• The offset needs to be controlled by the attacker; most of the time, offsets are hardcoded (most offsets are structure references).

• The wild write needs to happen before any pointer loads that will crash the program.

Is there a pattern worth looking for here? Absolutely. Look for things that can return NULL that have random-access indexing. Malloc is a perfect example.

Wait a minute. Didn’t you say people shouldn’t check malloc?

Yes. This bug is a perfect case in point for why I’m right.

Consider: it is not the case that the Flash runtime never checks for allocation failure. What happened is, the Flash developers have an allocation checking regime that defaults to unchecked, and requires them to audit every allocation.

The way it should work is, by default, when using the simplest, most common allocation calls (malloc, or, in Flash, mem_Alloc), the program should abort if malloc fails. Returning and catching NULL is inadequate.

“But we can’t just abort when any given malloc fails! What about user-specified sizes?” You don’t have to abort on every malloc. You just have to abort by default. When you know you’re taking a value from a user, or any other unsafe input, you should use “unsafeAlloc”, which is simply malloc. Then you audit your code for the 3 places in the whole project that use “unsafeAlloc” and make sure the checking regime works.

Doesn’t runtime security, like in Vista, solve most of these problems?

Maybe, maybe not. Obviously it didn’t here, because Flash turned runtime security off.

But look at the bigger picture. Runtime security measures like ASLR and cookies and W^X memory all address the “dumb exploit” pattern. The “dumb exploit” pattern is an artifact of hardcoded runtimes generated by C compilers. When your exploit is shotgunned in through a dumb runtime, you lose both predictability and control of the target program. That’s basically what runtime security is capitalizing on: your exploit doesn’t know where DLLs are based, and so it can’t return directly into them.

The problem is, the hardcoded runtimes are going away. The vast majority of code written going forward targets extremely complicated runtimes, like the bytecode VM in ActionScript. In a bytecode VM scenario, an exploit has much more flexibility:

• There might be 10x as many places to overwrite that will compromise the target; for instance, the abstract syntax tree objects containing method tables.

• Valuable information might be readily accessible from known relative offsets or, better still, from registers kept loaded with intepreter state.

• Just as with ActionScript, the content buffer that vectors your exploit in might be executable in the target runtime, leaving you only with the problem of compromising the verifier.

• Just as with ActionScript, there may be an extremely powerful executive running on top of the CPU, rather than just machine code instructions running directly on the CPU.

These are all ways that high-level languages make runtime security harder.

But high-level languages are supposed to be a huge security win!

They probably are. But remember, even in the most intricate schemes (and Javscript compiled to a bytecode VM that runs off the system stack qualifies), high-level languages are really just glue around low-level languages: the most interesting features in Python, Ruby, and Javascript are implemented natively.

So, you get two interesting phenomenon:

• You need to audit the runtime to make sure that the C code that implements the core language isn’t vulnerable (this is why Perl was a bad bet in 1995, when everyone was saying that buffer overflows were C’s fault).

• You need to audit all the native extensions (such as Quicktime for Java), bearing in mind that unlike a server or a client, the attack surface for a language extension is arbitrary callers with arbitrary arguments —- a much more painful place to be.

Has Mark Dowd simply outclassed us? Should we pack it up and quit?

Yes. But don’t feel bad about that. You’re a human being, and he’s a remorseless killing machine. Big Blue crushed Kasparov, and now he’s not the prime minister of Russia! At a certain point, you have to concede the field, moving on to games where human beings still have the advantage. Computers haven’t solved Go, for instance. For us researchers, I suggest we take advantage of Mark Dowd’s robotic inability to love, and take up the arts, such as watercolors or interpretive dance.

16 Comments

Thoughts on Ten Years of qmail Security

Thomas Ptacek | November 2nd, 2007 | Filed Under: Defenses, Uncategorized

Ahh, qmail. What is it about Daniel J. Bernstein’s full-featured Sendmail replacement that we can’t shut up about? Oh yeah, maybe it’s the nine years that have gone by since its last major release in 1998 which saw not one exploitable vulnerability. qmail is one of the top 5 Internet mail servers. Not one other project of similar standing shares this track record. It’s actually kind of spooky.

So, we’ve written about qmail before. And, if Georgi Guninski reads our blog, our qmail writing could conceivably cost me $500. What excuse can we make to keep talking about it?

How about a just-published retrospective on qmail and software security by DJB himself?

DJB isn’t really talking about qmail; he’s using it to illustrate lessons learned about software security. Here’s an example: three answers for eliminating security vulnerabilities from software:

1. Eliminate bugs from code. As Theo said, “we assume all bugs are vulnerabilities”. Kill bugs, close vulnerabilities. How do we kill bugs? Engineering has wrestled with that for decades. Some answers: formalized software engineering. Automated QA and coverage testing. Unit testing. Code review. Up-front security design.

   It works. qmail won by replacing 80’s era C library interfaces with new libraries that made it hard to write incorrect code. Microsoft won by beating the living crap out of their code and release schedule with security-focused QA.

2. Eliminate code. More code? More potential bugs. Minimizing code footprint reduces exposure to bugs. “Complexity is the enemy of security”. How do we eliminate code? Bernstein’s best answer is reuse: expend effort so your programs exploits your platform, instead of reinventing the wheel.

   It works. qmail won by taking advantage of somewhat obscure Unix features like programmable resource limits. The major enterprise web stacks like J2EE and .NET allow web apps to eliminate code by building on well-tested session, database, and templating libraries.

3. Eliminate trusted code. If you have to spend lines of code to deliver a feature, at least keep the code out of the line of fire. How do we minimize trusted code? Bernstein grapples with this question, arriving at two answers: use the operating system to compartmentalize code, so that vulnerabilities can’t do real damage, and run sensitive code in interpreters, trading speed for security.

   It works. Minimizing trusted code (or what consultants would call “the attack surface”) in qmail is the signature architectural trait of qmail. But you get the impression that Bernstein is least satisfied with qmail’s execution here. At the same time, it’s impossible to miss the wins other projects see with this approach: the vast majority of deployed enterprise software is innoculated against memory corruption vulnerabilities because they’re run in high-level languages like C# and Java.

Bernstein has a few grenades to toss. I disagree with his take on “least privilege”; revoking program rights to operating system resources like files and sockets isn’t a distraction. Yes, there’s a (subtle) difference between sandboxing a broken chunk of code and designing it properly to begin with; and yes, it’s true that access control schemes are plagued with “game-over-equivalence” problems (“you can read everyone’s mail, but at least you didn’t get root”). But I found his argument mushy, seeming to contradict his second “minimize the TCB” strategy, and Saltzer’s principals still seem vital to me.

There’s a conspiracy theory among those who have audited qmail’s idiosyncratic codebase that Bernstein didn’t actually write it in C, but rather in a language he compiled down to C. Here he in on the subject:

When I wrote qmail I rejected many languages as being much more painful than C for the end user to compile and use. I was inexplicably blind to the possibility of writing code in a better language and then using an automated translator to convert the code into C as a distribution language.

Of course, now that he’s spending his time writing compiler backends, maybe the new plan is to ship the entire language stack along with his applications.

Bernstein had the benefit of hindsight with buffer overflows, but had to weather integer vulnerabilities along with everyone else. qmail fared remarkably well (the only known integer overflow in qmail isn’t exploitable on any real deployment). The jury’s still out on what the next major bug class will be (our money has been on uninitialized stack variables). We may eke out a few more qmail bugs over the next 10 years. But relying on it seems like a safe bet.

32 Comments

The X86 Memory System And Why It’s Hard To Virtualize Securely

Thomas Ptacek | September 28th, 2007 | Filed Under: Defenses, Uncategorized

The X86 memory system causes surprising confusion. By way of analogy: take iTunes on Windows, to machines talking to the Internet from a corporate network. Here’s how memory breaks down in the analogy:

• User virtual addresses: Pretend iTunes is a VMware guest image, running in bridged networking mode, assigned 10.0.1.8 (a private IP).

• Kernel virtual addresses: Windows iTunes runs under the Windows NTOSKRNL kernel; in our analogy, this is VMWare’s host operating system. Like the bridged VMware guest, it’s on the internal net, with 10.0.1.4.

• Physical addresses: NTOSKRNL works with the CPU’s MMU to map virtuals into physical addresses. In our analogy, the MMU is like a NAT firewall, translating 10.0.1.4 and 10.0.1.8 to external addresses, like 66.178.176.10.

• IO Addresses: A firewall can’t get you onto the Internet without a router. An MMU can’t get you to memory or devices without a chipset. The “northbridge” in the chipset is like that router. A router figures out that when you use an external address like 66.178.176.10, you mean ESCAPE.COM, but when you say 69.61.87.163, you mean SKODA.SOCKPUPPET.ORG, which is on your own network. The chipset northbridge figures out that some physical addresses go to memory, and some go to devices.

• The PCI Bus: is like the Internet. Nobody on the Internet can talk to you using your 10.0.1.8 address. 10-net addresses don’t route. PCI devices don’t use virtual addresses, like iTunes sees. They use physical addresses. The backbone routers PCI devices use to get to physical memory are, in X86 parlance, the “southbridge”.

• Sound cards: are machines on the Internet. They want to talk to iTunes, which is on a private network. This works for PCI the same way it does for Skype on the real Internet. iTunes, via the kernel, somehow tells the sound card the extenal address of a block of memory it will read and write to. The sound card talks to the chipset to get access to that memory. That’s called DMA. It’s how pretty much all your peripherals work.

In pictures. The memory and DMA story:

Compared to the enterprise networking story:

Clear as mud? You’re welcome. Why is this important for security? Mostly because of virtualization.

In 5 years, nobody will deploy new servers for applications. Every application will run on a virtual machine. Inevitably. And as we approach this end-state, more and more of our applications are virtualized, and performance becomes a bigger concern.

One of the ways virtualization hurts performance is to come between the operating system and the hardware.

So we’d like some way of giving virtual machines direct access to slices of hardware. For example: a high-performance web server might want to own a NIC. The problem is, the web server lives alongside 10 other guest VMs that don’t trust it. The NIC’s DMA access forces them to.

X86 hypervisors do an elaborate dance with guest OS kernels, tricking them into believing they control the physical/virtual “NAT” table. That dance happens entirely within the CPU. On the Internet, Petko D. Petkov does not care about your 10.0.1.8 address. If your firewall will let him talk to you at 69.61.87.160, he can attack you. On your computer, a NIC does not care about your kernel and user virtual addresses. It’s using physical addresses, which address all the memory shared by all the VMs in the machine.

This is a hole in the X86 VMM security strategy. Today, if you want your guest VMs not to have to trust each other, and one of them needs direct access to NIC, you have to trust that the NIC can’t be coerced into copying network packets with executable code directly into the kernel memory of the other machines.

Nate Lawson is writing a series on the nuts and bolts of this. CPU vendors are proposing features, such as IOMMUs, that will regulate device access to memory in much the same manner as the CPU’s MMU regulates access between processes. These features may or may not work in the long run; in the short run, it looks like they provide show-stopping performance problems of their own.

You only need to read Nate’s posts if you (a) believe virtualization will be ubiquitous within the next 5 years, (b) work in security, and (c) believe you need to sound like you know what you’re talking about. Otherwise, Nate’s posts are entirely optional.

12 Comments

Adam Bozanich Did Not Uncover An NSA IPsec Conspiracy: Diffie Hellman Parameter Validation Explained

Thomas Ptacek | September 25th, 2007 | Filed Under: Defenses, New Findings, Uncategorized

Alice and Bob want to arrange a tryst. Bob’s wife Eve is sniffing their Instant Messenger traffic.

No problem! Alice and Bob will encrypt their messages with AES-256-CBC. Eve won’t be able to decode the traffic before the heat death of the universe.

One small problem: what AES key to use? Actually: not a small problem. No matter what key Alice comes up with, she can’t send it to Bob without exposing it. She can’t encrypt the key; chicken and egg.

There’s a solution to this problem. Alice and Bob will run the Diffie-Hellman protocol (DH) to securely exchange a key.

Alice and Bob agree on a prime number p, and a smaller number g with a special relationship with p ([1]). These are parameters to Diffie Hellman. “23” and “7” are valid p and g parameters. So are “37” and “5”. They aren’t secret. Think of them like a “version” of DH that Alice and Bob agree to use.

For the sake of argument, Alice and Bob agree on “37, 5” DH.

Bust out your calculator. I’ll be Bob.

Generate a random number a, modulo 37 (divide your number by 37 and a is the remainder).

I’ll do the same thing to generate a different b.

Now take your a and make A. Raise 5 to the a‘th power, modulo 37 (in Ruby, do “(5 ** a) % 37”. I’ll do the same with b to make B.

A is your public key. a is your private key. Send me A. I’ll send you B. It’s 29.

Take 29 and raise it to the a‘th power mod 37 (I don’t know what a is; it’s your private key, so I can’t tell you what you’ll get.) That’s “(B ** a) % 37” in Ruby. I’ll do the same with B.

We just arrived at the same number. Was your private key 7? We came up with 8. Was your private key 26? We came up with 27. 27 is our session key.

Funny thing about our session key: you know it, and I know it, but Eve can’t know it. Even though we did this computation out in the open. This is the deep magic, yo.

Well OK, Eve totally knows what number we came up with, because we used a ridiculously small p. Instead of 37, 5, try this:

FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
670C354E 4ABC9804 F1746C08 CA237327 FFFFFFFF FFFFFFFF

Just use 2 as g. Remember now that your private key a is a random number modulo this huge p. It will also be huge.

Raising a number to a power modulo another number is modular exponentiation (modexp). A modexp is straightforward to compute.

The opposite of exponentiation is a logarithm. Taking a log mod another number is a discrete logarithm. Discrete logs are extremely hard to solve. With large enough numbers, “racing heat death of the universe” hard; “every atom in the Solar System is a computer trying to solve it, still unsolvable” hard.

So you have two closely related operations, exponentiation and logarithm mod p, one of which is easy to compute and one of which is hard. This is a cryptographic building block and the foundation of DH.

We got 26 for our session key. Let’s say we MD5 the text value of “26”, to get “4e732ced3463d06de0ca9a15b6153677”. Tack a “0x” at the front of that value, and we now have a 128 bit number we can use as an AES key. Eve can’t know we came up with 26, and so can’t know what the MD5 of the session key is, and so doesn’t know what our AES key is.

Problem solved! Cue arbitrary foreshadowing device. We’ll come back to this.

Adam works for Mu Security. Mu is writing an IKE fuzzer. IKE is a key exchange protocol for IPSec. IKE is probably one of the worst protocols ever to come out of the IETF, and I’m not going to explain it.

What you need to know is that IKE generates the keys that secure dynamically-keyed IPSec tunnels (layer-3 VPNs), and that IKE uses DH to do that.

Adam remembers a DH gotcha. When Alice and Bob run DH, they have to be careful not to allow any of the parameters —- p, g, A, or B —- be zero or one mod p.

Why’s that? Bust out your 37, 5 DH math again. Alice’s session key computation is “(B ** a) % 37”. Bob sends B. If B is 1, the session key is… wait for it… 1. If B is 0, it’s 0. No matter what Alice’s private key is.

If Eve sees a public key that works out to 0 or 1 mod p, Eve knows what the session key was; it’s zero or one. Remember that there are infinitely many values that work out to 0 or 1 mod p. 0 is 0 mod 37. So is 37. So is 74. And so on. Bob could have sent any one of those bad public key values.

Alice and Bob are supposed to check for this. Adam looked at a bunch of IKE implementations. None of them did.

This is a well-known problem. It’s in Eric Rescorla’s DH RFC. It’s in an ANSI standard. You can’t use p - 1 mod p either. You also have to be careful with g; broken values will generate subgroups, not the entire group. And real DH implementations have optimizations that can be attacked mathematically if you’re not careful.

Just because it’s well known doesn’t mean people won’t make the mistake. That’s why Nate and I pointed the problem out last year (almost to the day!).

The general class of problems we’re talking about is parameter validation. You attack them by looking at the messages a protocol exchanges, and sending malicious bad values that will break the computation.

Are you a security researcher? Go look for some of these bugs. They rock. More in a sec.

So it’s interesting that IKE implementations don’t validate parameters, but it’s not particularly meaningful.

IKE Bob can send IKE Alice a bad public key. This key will cause Eve to know the session key Bob and Alice use. But why would Bob do this? He’s negating his own security!

Eve can try to inject a bad public key into the session. But so what? If Bob and Alice don’t agree on A and B, the public keys, they can’t run DH. Maybe a different attacker, Mallory, can get between Alice and Bob and proxy the messages. She’ll be a “man in the middle”.

In this case, Mallory wins. No matter what parameters you use and what bugs your code has, Mallory beats DH. This is a basic challenge with DH. The solution involves more crypto.

DH is a useful building block, but protocols that use DH usually depend on some other operation to ensure security. For instance, DH SSL uses RSA certificates to beat Mallory. DH is useful to SSL; it gives you perfect forward secrecy by not tying your SSL session key to a fixed RSA key that can be compromised. But DH SSL depends on RSA for security.

So it’s not a good sign that IKE implementations aren’t smart enough to do parameter validation. But it doesn’t make much of a difference. The “vulnerability” allows an IKE participant to elect an insecure session.

Adam wants to take this somewhere. So he writes a blog post suggesting that the uniform weakness of IKE implementations could be evidence of a conspiracy.

I don’t think he’s being entirely serious, but here’s his argument: the NSA —- no wait, it’s 2007, let’s make it the RIAA —- demands the ability to snoop on everyone’s IPSec sessions. They get all the IKE vendors to ship backdoored IKE agents. On some secret signal, the IKE agent will send public keys that work out to 0 mod p, and the RIAA can break these sessions with the sniffers they’ve installed at every exchange point on the Internet.

There’s a reason this is silly besides the fact that it involves backdooring one of the least important security mechanisms on the Internet: it’s a dumb attack.

Mallory knows p and g. So does Seth, the secops guy. Mallory can watch for A and B values that are 0 mod p. So can Seth. Why would the RIAA install a secret backdoor you could write an IDS signature for?

There are much more subtle things you can do to backdoor DH. Start with, IKE implementations can just be backdoored with a known private key value, or a root backdoor private key and an algorithm for generating variants of it. Move on from there.

This isn’t a conspiracy. This is just ignorance.

Because this vulnerability happens all over the place.

Take SRP for example. SRP is a derivative of DH. Alice is a client, Bob is a server. Alice and Bob know Alice’s password. Alice generates a public key that is related to the SHA-1 hash of the password. Alice and Bob do a DH exchange to prove Alice knows the password, and if the exchange works, Alice wins.

Mallory sends Bob a public key of 0 mod p. Mallory wins. She can log in as Alice without knowing Alice’s password.

This vulnerability is well known. It’s in the RFC for SRP. But I’ve tested SRP implementations written by smart security people, and they’ve had this vulnerability. (Due credit: I got this trick from Trevor Perrin, via Nate Lawson).

Compare the SRP vulnerability to the DH vulnerability. The SRP parameter validation problem is really, really bad. It’s auth bypass. The DH vulnerability is just a dumb way to backdoor an IKE agent.

IKE is a mess of a protocol. Crypto parameter validation attacks are totally underappreciated. Adam’s blog post is cool. It was smart of him to check for this, and interesting that he found it.

Not much about IKE. It’s as secure as you thought it was before you heard about Adam’s finding.

Hopefully a lot about crypto, though. Like I said, we wrote a post last year talking about parameter validation tricks for DH, SRP, Elliptic Curve, and RSA.

Forget about algorithmic attacks and advances in factorization and quantum computers. Parameter validation attacks are a systems flaw; systems depend on code, and code is riddled with bugs. All bugs are vulnerabilities. Most… any? cryptosystems will be beaten by stupid bugs like this.

Go look for them!

[1]: g is a primitive root modulo p. For values of x from 0 to p - 1, raise g to x modulo p. If g is a primitive root modulo p, you’ll end up with every number between 1 and p - 1, in some order. For instance, the following Ruby snippet asks if 3 is a primitive root mod 37.

lst = [] ; 0.upto(36) {|d| lst << ((3 ** d) % 37)} ; lst.sort

elicits the following output:

[1, 1, 1, 3, 3, 4, 4, 7, 7, 9, 9, 10, 10, 11, 11, 
 12, 12, 16, 16, 21, 21, 25, 25, 26, 26, 27, 27, 28, 
 28, 30, 30, 33, 33, 34, 34, 36, 36]

2’s missing. So’s 5 and 6, etc. 3 is not a primitive root mod 37. Now try 5:

lst = [] ; 0.upto(36) {|d| lst << ((3 ** d) % 37)} ; lst.sort

[1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 
 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 
 29, 30, 31, 32, 33, 34, 35, 36]

All the numbers between 1 and 36 are there. 5 is primitive root mod 37.

Why is this important? Because if you’re working with a 1024 bit prime, you want session key values to possibly be any one of those 1024 bit values. Another word for “primitive root” is generator. Generators generate the entire group of values mod p. Bad values of g generate subgroups, with fewer than 1024 bits of possible values. The worst g values generate only two possible values!

7 Comments

Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes

Thomas Ptacek | September 10th, 2007 | Filed Under: Defenses, Uncategorized

The socialbookmarkosphere is abuzz with talk of “rainbow tables”, what they mean for password security, and why they prove that Microsoft did a shoddy job of securing Windows for Workgroups 15 years ago. This really freaks me out. If the “advanced” pole of your threat model is “rainbow tables”, stop working on your social shopping cart calendar application right now: I can’t trust you with my Reddit karma score, let alone my credit card number.

To begin, password storage 101: servers don’t usually store actual passwords. Instead, they hash the password, store the hash, and discard the password. The hash can verify a password from a login page, but can’t be reversed back to the text of the password. So when you inevitably lose your SQL password table, you haven’t exposed all the passwords; just the crappy ones.

Now let’s re-explain rainbow tables:

1. take a “dictionary” —- say, of all combinations of alphanumerics less than 15 characters

2. hash all of them

3. burn the results onto a DVD.

You now have several hundred billion hash values that you can reverse back to text —- a “rainbow table”. To use,

1. take your stolen table of hashes

2. for each hash

3. find it in the rainbow table.

If it’s there, you cracked it.

Here’s what you need to know about rainbow tables: no modern password scheme is vulnerable to them.

Rainbow tables are easy to beat. For each password, generate a random number (a nonce). Hash the password with the nonce, and store both the hash and the nonce. The server has enough information to verify passwords (the nonce is stored in the clear). But even with a small random value, say, 16 bits, rainbow tables are infeasible: there are now 65,536 “variants” of each hash, and instead of 300 billion rainbow table entries, you need quadrillions. The nonce in this scheme is called a “salt”.

Cool, huh? Yeah, and Unix crypt —- almost the lowest common denominator in security systems —- has had this feature since 1976. If this is news to you, you shouldn’t be designing password systems. Use someone else’s good one.

No, really. Use someone else’s password system. Don’t build your own.

Most of the industry’s worst security problems (like the famously bad LANMAN hash) happened because smart developers approached security code the same way they did the rest of their code. The difference between security code and application code is, when application code fails, you find out right away. When security code fails, you find out 4 years from now, when a DVD with all your customer’s credit card and CVV2 information starts circulating in Estonia.

Here’s a “state of the art” scheme from a recent blog post on rainbow tables and salts:

hash = md5('deliciously-salty-' + password)

There are at least two problems with this code. Yeah, the author doesn’t know what a salt is; “deliciously-salty-” is not a nonce (also, Jeff, your computer really doesn’t care if you seperate the password from the nonce with a dash; it’s a computer, not a 2nd grade teacher).

But there’s a much bigger problem with this code: the letters “md5”.

Two reasons.

1.

You’re expecting me to go off on a rant about how there is no redeeming quality to justify using MD5 in 2007. That’s true (MD5 is broken; it’s too slow to use as a general purpose hash; etc). But that’s not the problem.

2.

The problem is that MD5 is fast. So are its modern competitors, like SHA1 and SHA256. Speed is a design goal of a modern secure hash, because hashes are a building block of almost every cryptosystem, and usually get demand-executed on a per-packet or per-message basis.

Speed is exactly what you don’t want in a password hash function.

Modern password schemes are attacked with incremental password crackers.

Incremental crackers don’t precalculate all possible cracked passwords. They consider each password hash individually, and they feed their dictionary through the password hash function the same way your PHP login page would. Rainbow table crackers like Ophcrack use space to attack passwords; incremental crackers like John the Ripper, Crack, and LC5 work with time: statistics and compute.

The password attack game is scored in time taken to crack password X. With rainbow tables, that time depends on how big your table needs to be and how fast you can search it. With incremental crackers, the time depends on how fast you can make the password hash function run.

The better you can optimize your password hash function, the faster your password hash function gets, the weaker your scheme is. MD5 and SHA1, even conventional block ciphers like DES, are designed to be fast. MD5, SHA1, and DES are weak password hashes. On modern CPUs, raw crypto building blocks like DES and MD5 can be bitsliced, vectorized, and parallelized to make password searches lightning fast. Game-over FPGA implementations cost only hundreds of dollars.

Using raw hash functions to authenticate passwords is as naive as using unsalted hash functions. Don’t.

What is the state of the art here?

1.

First, what your operating system already gives you: a password scheme “optimized” to be computationally expensive. The most famous of these is PHK’s FreeBSD MD5 scheme.

The difference between PHK’s scheme and the one you were about to use for your social shopping cart 2.0 application is simple. You were just going to run MD5 on a salt and a password and store the hash. PHK runs MD5 for thousands of iterations. That’s called “stretching”.

PHK’s MD5 scheme is straightforward to code and comes with Linux and BSD operating systems. If you have to choose between the PHP code you have now and PHK’s scheme, you choose PHK’s scheme or you fail your PCI audit. [∗]

2.

The best simple answer is “adaptive hashing”, which Neils Provos and David Mazieres invented for OpenBSD in 1999. Their original scheme is called “bcrypt”, but the idea is more important than the algorithm.

There are three big differences between Provos-Mazieres and PHK’s scheme:

1. Bcrypt was invented by two smart guys and PHK’s was only invented by one smart guy. That’s literally twice the smart.

2. Bcrypt uses Blowfish instead of MD5. Blowfish is a block cipher with a notoriously expensive setup time. To optimize Blowfish to run much faster, you’d have to contribute a major advance to cryptography. We security practioners are all “betting people”, and we usually like to place our bets on the side that “demands major advances in cryptography”.

3. Provos and Mazieres extended Blowfish. They call theirs “Eksblowfish”. Eksblowfish is pessimized: the setup time takes even longer than Blowfish. How long? Your call. You can make a single password trial take milliseconds, or you can make it take hours.

Why is bcrypt such a huge win? Think of the problem from two perspectives: the server, and the attacker.

First, the server: you get tens of thousands of logins per hour, or tens per second. Compared to the database hits and page refreshes and IO, the password check is negligable. You don’t care if password tests take twice as long, or even ten times as long, because password hashes aren’t in the 80/20 hot spot.

Now the attacker. This is easy. The attacker cares a lot if password tests take twice as long. If one password test takes twice as long, the total password cracking time takes twice as long.

Get it?

The major advantage of adaptive hashing is that you get to tune it. As computers get faster, the same block of code continues to produce passwords that are hard to crack.

3.

Finally, as your attorney in this matter, I am required to inform you about SRP.

SRP is the Stanford Secure Remote Password protocol. It is a public key cryptosystem designed to securely store and validate passwords without storing them in the clear or transmitting them in the clear.

That design goal is cooler than it sounds, because there’s usually a tradeoff in designing password systems:

1. You can store a hash of the password. Now if you lose the password database, you haven’t exposed the good passwords. However, you also don’t know the password cleartext, which means that to validate passwords, your customers need to send them to you in the clear.

2. You can use a challenge-response scheme, where both sides use a math problem to prove to each other that they know the password, but neither side sends the password over the wire. These schemes are great, but they don’t work unless both sides have access to the cleartext password —- in other words, the server has to store them in the clear.

Most practitioners will select the hashing scheme. Both attacks —- stolen databases and phished passwords —- happen all the time. But stolen databases compromise more passwords.

SRP resolves the tradeoff. It’s an extension of Diffie-Hellman. The salient detail for this post: instead of storing a salted password hash, you store a “verifier”, which is a number raised to the (obviously very large) power of the password hash modulo N.

If you understand DH, SRP is just going to make sense to you. If you don’t, the Wikipedia will do a better job explaining it than I will. For the test next Wednesday, you need to know:

• SRP is related to Diffie-Hellman.

• SRP is a challenge-response protocol that lets a server prove you know your password without your password ever hitting the wire.

• SRP doesn’t require you to store plaintext passwords; you store non-reversable cryptographic verifiers.

• “Cracking” SRP verifiers quickly would involve a significant advancement to cryptography.

• SRP is simple enough to run out of browser Javascript.

Awesome! Why aren’t you using SRP right now? I’ll give you three reasons:

• SRP is patented.

• To make it work securely in a browser, you have to feed the login page over SSL; otherwise, like Meebo, you wind up with a scheme that can be beaten by anyone who can phish a web page.

• SRP is easy to fuck up, so the first N mainstream Rails or PHP or Pylons SRP implementations are going to be trivially bypassable for at least the first year after they’re deployed.

We learned that if it’s 1975, you can set the ARPANet on fire with rainbow table attacks. If it’s 2007, and rainbow table attacks set you on fire, we learned that you should go back to 1975 and wait 30 years before trying to design a password hashing scheme.

We learned that if we had learned anything from this blog post, we should be consulting our friends and neighbors in the security field for help with our password schemes, because nobody is going to find the game-over bugs in our MD5 schemes until after my Mom’s credit card number is being traded out of a curbside stall in Tallinn, Estonia.

We learned that in a password hashing scheme, speed is the enemy. We learned that MD5 was designed for speed. So, we learned that MD5 is the enemy. Also Jeff Atwood and Richard Skrenta.

Finally, we learned that if we want to store passwords securely we have three reasonable options: PHK’s MD5 scheme, Provos-Maziere’s Bcrypt scheme, and SRP. We learned that the correct choice is Bcrypt.

This blog post was brought to you in part by a grant from the Jon M. Olin Foundation. Major underwriting for Matasano Chargen is provided by Archer Daniel Midland Company. ADM: Feeding A Hungry World. And of course, readers like you!

[∗] Disclaimer: I cannot actually flunk your PCI audit.

120 Comments

You Can Detect Hypervisor Rootkits Even If You’re Virtualized

Thomas Ptacek | August 27th, 2007 | Filed Under: Defenses, Uncategorized

Rich Mogull, reacting to our virtualization work:

[R]eading up on Nate and Tom’s work I can’t see any techniques for detecting an unapproved hypervisor in an already virtualized environment.

This is a misconception. Defenders will not have a hard time detecting unauthorized hypervisors, even when the defenders are already running VMware or Microsoft Virtual Server.

Here’s why: the defender is embedded in VMware or Microsoft Virtual Server.

Sound crazy? It isn’t. To detect kernel malware, you (typically) already need to be running in-kernel; in other words, you have to be part of the operating system. For the most part, to detect virtualization, you have to be in-kernel as well.

Both Blue Pill and Samsara need access to the hardware. The trick is, Samsara works even when Blue Pill is actively trying to “cheat” it, making it believe it’s talking to the hardware when it’s talking to a Blue Pill facade instead.

Joanna contests this argument. “Microsoft and VMware would never embed detection hacks into their hypervisors!” We agree. Microsoft and VMware are unlikely to ever need to. Hypervisor rootkits are not a major threat. But if they ever become one, hypervisor rootkit authors will find themselves a sitting duck for detectors. Joanna had the right idea, “chickening out” into the OS kernel to hide from Samsara.

15 Comments

Visual Cryptanalysis

Thomas Ptacek | August 25th, 2007 | Filed Under: Defenses, Development, Uncategorized

Daniel J. Bernstein visualizes ciphers by rendering their DAGs —- an intermediate representation, as would be used by a compiler as a step towards generating object code.

(If you’re not familiar with the concept, a DAG is just a tree where a node can have more than one parent. Single inheritance: tree. Multiple inheritance: DAG. If you are familiar with the concept, I apologize for saying “a DAG is just a tree…”).

How cool is this? For starters: I must have this poster. Here’s a snippet of MD5:

And of SHA-256:

More substantively, from the (short) paper:

The right half of the SHA-1 graph is the SHA-1 message expansion, and the right half of the SHA-256 graph is the more complex SHA-256 message expansion; for comparison, the MD5 graph has many long edges, allowing an attacker to effortlessly pierce deep into the heart of the MD5 computation.

Using visualization tools to find vulnerabilities has been in vogue among the RCE crowd for years now. It’s the whole idea behind Halvar’s excellent BinNavi tool. Now here’s an example of how cryptographers have been using the same idea.

[…] I certainly can’t claim that the tools have saved time in cryptanalysis. But I think that the tools will save time in cryptanalysis, automating several tedious tasks that today are normally done by hand.

Worth watching. Funny quote:

[M]y initial experiments with bit DAGs for MD5 have crashed every standard drawing tool that I’ve tried. My own drawing tools are much more careful in their use of memory.

Ok, maybe it’s only funny if you’ve tried to do large layouts in Graphviz before, or wrote your own crappy graph layout code.

3 Comments

Nate Lawson: Exploiting Error-Correcting Codes To Patch-Proof Software

Thomas Ptacek | August 22nd, 2007 | Filed Under: Defenses, Uncategorized

Common problem in software protection:

1. You have a subprogram that checks to make sure no debugger is attached to your code.

2. Attackers patch the subprogram, or its callers, to avoid the check.

3. You verify the subprogram and its callsites with a hash.

4. Attackers patch the verification code, or its callers, to avoid the check.

5. Repeat ad infinitum.

Nate Lawson has two cool “mesh design” answers for this problem.

The first is “hash and decrypt”. A “check for a condition” is a boolean function. Patching boolean functions is trivial (usually just a one-byte change). Instead of emitting a boolean, make your “check” compute a condition-dependent value, and use it as a key. A sketch:

1. Instead of a true-false function, write a function that computes a value that depends on the condition. For instance, an antidebugging function might use log-scaled instruction cycle timings.

2. Collect these measurements and hash them.

3. Use the hash as an AES key.

4. Use the key to decrypt and execute the “success” path through your program. If the “check” for the condition failed, the key will be wrong, and the success path won’t execute.

What’s cool about this is that hashes are an inherently strong way of aggregating lots of different measurements (the integrity of program text, stored state, and the results of explicit measurements), and the unlock-and-execute pattern means no simple patch can detour the programs self-checks.

Nate’s next idea, just posted in his blog, thus invalidating his future patent claims, is to use error correcting codes to do the same thing.

Instead of verifying program text by hashing and generating a key, Nate proposes to use Turbo codes to generate parity blocks for security-sensitive functions. Instead of simply calling these functions in the text, programs copy them, apply the parity to correct any “errors” (read: unauthorized patches), and execute.

Clever! Read the post. As always, Nate’s posts are required reading.

11 Comments