Moving the blog

After quite a bit of work, I’ve decided to move the blog to my own server and transition to WordPress. It worked for Scoble, and I have really just wanted a more modern blogging platform for a while. .Text is not exactly a spring chicken.

So, please come visit me at http://kernelmustard.com. You will have to re-subscribe your RSS feed – the new feed url is http://www.kernelmustard.com/feed – which is RSS2, as far as I know. 🙂

In case anyone out there is using Vienna, I had to manually change the feed type from atom to rss2; it detected it wrong when I clicked Safari’s RSS button in the address bar.

So, no more posts here; come visit me at my new place!

Results of the MD5 collision program and implications

MD5 has been seriously broken for a while, but when I saw the news that Patrick Stach has posted super-efficient collision-generating code, I was surprised that it was that broken. I tried the code on a few boxes, and generally had trouble getting it to finish in the time my patience allotted me, but Matt Miller did get it to produce results:

$ time ./md5coll 
block #1 done
block #2 done
unsigned int m0[32] = {
0x298640cf, 0x60bd40e2, 0xf2d40369, 0x2883fcb5,
0x5c85f76d, 0x35336462, 0xca28a356, 0xd355d92c,
0x0634ed41, 0x62120dff, 0xa172ecd7, 0x8eb22b63,
0xb9b99104, 0x34698bfa, 0x80ab939e, 0x705166dd,
0x287db57a, 0x52d249c7, 0x6ab58d44, 0xe3e7f0e3,
0xb6cedb4a, 0xfdab2203, 0x36b6dd1a, 0x90054d51,
0x0d3b3725, 0xeb3bd937, 0x87df3006, 0xbd2af47b,
0x7fbaecc0, 0xa494156b, 0xc8e0ec64, 0xfdb9a844,
};
unsigned int m1[32] = {
0x298640cf, 0x60bd40e2, 0xf2d40369, 0x2883fcb5,
0xdc85f76d, 0x35336462, 0xca28a356, 0xd355d92c,
0x0634ed41, 0x62120dff, 0xa172ecd7, 0x8eb2ab63,
0xb9b99104, 0x34698bfa, 0x00ab939e, 0x705166dd,
0x287db57a, 0x52d249c7, 0x6ab58d44, 0xe3e7f0e3,
0x36cedb4a, 0xfdab2203, 0x36b6dd1a, 0x90054d51,
0x0d3b3725, 0xeb3bd937, 0x87df3006, 0xbd2a747b,
0x7fbaecc0, 0xa494156b, 0x48e0ec64, 0xfdb9a844,
};
real    239m18.508s
user    238m34.440s
sys     0m3.390s 

Well, that’s nice, isn’t it? But what does this mean? Well, it means that MD5 is no longer useful as a signature hash: it is no longer the case that you can believe that a person’s signed document is identical to your version of that document, even if the checksum matches. More implications of collisions can be found in cryptography.com’s Hash Collision Q&A.

These attacks are not, however, preimage attacks. That means that it is still infeasible for an attacker to generate a particular input to a hash function that is guaranteed to produce a particular output. Because of this, many applications, such as the HMAC-related protocols, are unaffected by this break. Still, Schneier reported a 2^106 preimage attack against SHA-1 that is a hell of a lot under the 2^160 work that would be expected by brute force. Totally completely impractical at the moment, but worth keeping in the back of your mind regardless, particularly if you’re designing a cryptosystem.

Blog host problems today

I’m sorry for the amazingly high unavailability of my blog today; the blog host has been having issues. I am actively working to resolve them.

Also, I’ve been updating the MD5 article throughout the day; if you haven’t looked at it since my first post, lots has changed. Bottom line: it turns out that both MD5 and SHA-1 have been broken, and that that fact is rather old news.

Efficient collision generation for MD4 and MD5

Patrick Stach has announced a new implementation of an MD4/5 collision generation algorithm that can generate MD4 collisions instantaneously and MD5 collisions in under an hour on commodity hardware. MD4 hasn’t been considered to be secure in a while, but MD5 is a mainstay of digital signatures, IPSEC, and tons of other security applications.

The practical implications of this are easy enough: switch to SHA-1, now. Quit using MD5 for secure anything. Even if this attack turns out to be impractical (although it certainly looks reasonable), it’s still evidence that the aging hash is nearing its end. [Update: even if this code doesn’t work (still testing), the attack is very real.]

Patrick is a smart dude and he has been working on this problem for a while. Nice work, Pat!

UPDATE:: I have ported the code to windows; it builds with the .net DDK and is still running on a test box.

UPDATE 2: Matt Miller points out that SHA-1 has its own problems and should be regarded with great skepticism for its application in secure systems. Pat pointed out that there are possible attacks against SHA-256, 384, and 512, and that VSH is the only published algorithm he considers secure. Bruce Schneier doesn’t have much to say about it yet, and it’s too new to trust IMO, but it’s interesting to consider the reality check that it’s impossible to prove these algorithms secure.

If you’re using commercial hardware or software, or otherwise lack the ability to choose anything but md5 and sha-1, pick sha-1.

Update 3: Matt, Pat, and I continue to discuss the issue.

Pat says:

  • There is no reason to switch to SHA-1, because it is next up to be cracked. He says he has an attack against it and just has to tune the loops.
  • SHA-256, 384, and 512 are all [potentially] vulnerable – its the design of the cipher. I [Pat] have a differential that might work for SHA-512
  • VSH is about the best generally published algorithm
  • basically all you’re buying with sha-256 is about 3 years

My opinion is that SHA-1 is the best we’ve got at the moment unless you happen to have source code, and that excludes almost all commercial hardware (Cisco, Juniper, …). VSH looks neato, but don’t use it until it has had some more peer review. I have no idea how bad SHA-512 will hurt perf, but it might be worth looking into.

Schneier liveblogged the NIST hash workshop that recently took place; the first post says the following:

Xiaoyun Wang, the cryptographer who broke SHA-1, spoke about her latest results. They are the same results Adi Shamir presented in her name at Crypto this year: a time complexity of 2^63.

Wow! 2^63 is a huge break for a 160-bit hash. Birthday attack was only good for 2^80.

Update 4: Ken Johnson suggested an improvement to the ported Windows code; it has been updated (along with the link in update 1). Thanks, Ken.

Rootkit detection

A lot of people were wondering why Microsoft couldn’t have (or didn’t) detect the Sony DRM rootkit without writing new code. I covered that topic yesterday.

Today, an NTDEV reader named Daniel Terhell posted a tool that has the potential to detect some kinds of hooks by analyzing the system service dispatch table and seeing where the functions pointers point. Anything that points outside of the kernel is flagged as possibly hooked. The tool is known as Hook Analyzer and can be downloaded from his website.

I installed the tool and tried it with an old version of Regmon, but apparently Mark used another mechanism besides syscall hooking in the product. I haven’t looked into it yet; if I get around to it I’ll write my own syscall hook driver to test.

But the real question is this: what level of value do you see in a tool like this? There are, after all, legitimate reasons to use syscall hooking, although they are rare. There are plenty of other kinds of hooks that a tool like this won’t cover, but what about the ones it does cover? Useful?

Server-based Excel and the bandwidth-delay product

Microsoft is adding support for server-based Excel in version 12. This may not seem like it’s relevant content here, and that’s because it’s not. But boy howdy, this has been the #1 gripe of Positive Networks users for years. 5MB Excel worksheet + 1Mbps Internet access == toothache-like pain.

Reminds me of a story that used to be passed around in networking circles a few years ago. My friend Deep Medhi is fond of reminding people to never underestimate the bandwidth of a station wagon loaded with backup tapes driving down the highway at 55mph. If you do the math, it turns out to be much higher bandwidth than most people’s network pipes (imagine 60 cubic feet worth of 8GB DVDs on a 4 hour drive, for example).

The problem is the round-trip time. The bandwidth-delay product is a really useful characteristic to know about your network pipe; in general, smaller is better. Needless to say, our station wagon has a very high BD product.

Why couldn’t Microsoft detect the Sony DRM kit automatically?

Microsoft has decided to add support for removing the Sony DRM rootkit to its various malicious software removal tools. My article at ArsTechnica on the subject has more info.

One of the commenters on the Ars post said something to the effect of “Why didn’t Microsoft just remove this automatically (rather than needing to write custom code for removing it after it happened)?” This is an interesting question, and I’d like to discuss it a bit. As Mark’s original blog post points out, the thing manages to spray garbage all over the system, by hooking, modifying, cloaking, and otherwise not playing nice in the sandbox.

The problem here is that any single action by the rootkit is not necessarily an illegal operation. Granted, most would say that system call hooking is totally wrong, but there can be legitimate uses for this too. Furthermore, although any number of things that rootkit authors do could theoretically be stopped, Microsoft can’t just break badly behaved apps.

Some have discussed the hook question on NTDEV again this week. This topic seems to pop up with regularity; this time, it was Don Burn who started the fun by requesting that Microsoft implement the same system call hooking preventions that it has implemented for x64 windows. Microsoft’s reason for not doing this is that they are afraid that too many apps would break. Scary thought… so many apps need hooks that Microsoft thinks it would be unwise to break them all. Woah.

One possible solution to the hook problem, and by extension, to the problem of crapware doing immoral (if not illegal) things to the operating system would be to support opt-in mechanisms for the increased restrictions. Microsoft has already employed this technique for hardware-based DEP (although this method has its shortcomings).

Whatever the case, even given that increased controls might be present in the system, there’s still no good way for Microsoft to say, with certainty, that software is doing illegal or immoral things in many cases. In some cases (such as most hooks), there is currently no way to even tell that the behavior is taking place.

So, bottom line, I’d rather my anti-crapware software not make guesses. I’ll stick to what works for me: staying current with updates, running as a restricted user, keeping my firewall on, and keeping my head firmly attached during web surfing.