My personal joke -- at least I hope it's a joke -- is that he's going to break every NIST hash submission without ever seeing any of them.

More later. (I'm sorry, but I missed the name of his student/co-author for this work.)

EDITED TO ADD (8/19): Okay, he thinks that AES is immune to this attack -- the degree of the algebraic polynomial is too high -- and all the blog ciphers we use have a higher degree. But, in general, anything that can be described with a low-degree polynomial equation is vulnerable: that's pretty much every LFSR scheme.

In particular, SSL certificates (as used to identify https websites) might contain one of these weak keys — and so it would be possible for an attacker to successfully impersonate a secure website. Of course the attacker would need to persuade you to mistakenly visit their site — but it just so happens that one of the more devastating attacks on DNS has recently been discovered; so that’s not as unlikely as it must have seemed back in May.

Anyway, my old friend Ben Laurie (who is with Google these days) and I have been trawling the Internet to determine how many certificates there are containing these weak keys — and there’s a lot: around 1.5% of the certs we’ve examined.

But more of that another day! because earlier this week, Ben spotted that one of the weak certs was for Sun’s “OpenID” website, and that two more OpenID sites were weak as well (by weak we mean that a database lookup could reveal the private key!)

OpenID, for those who are unfamiliar with it, is a scheme for allowing you to prove your identity to site A (viz: provide your user name and password) and then use that identity on site B. There’s a queue of people offering the first bit, but rather less offering the second : because it means you rely on someone else’s due diligence in knowing who their users are — where “who” is a hard sort of thing to get your head around in an online environment.

The problem that Ben and I have identified (advisory here), is that an attacker can poison a DNS cache so it serves up the wrong IP address for openid.sun.com. Then, even if the victim is really cautious and uses https and checks the cert, their credentials can be phished. Thereafter, anyone who trusts Sun as an identity provider could be very disappointed. There’s other attacks as well, but you’ve probably got the general idea by now.

In principle Sun should make a replacement certificate and that should be it (and so they have — read Robin Wilton’s comments here). Except that they need to put the old certificate onto a Certificate Revocation List (CRL) because otherwise it will still be trusted from now until it expires (a fair while off). Sadly, many web browsers, and most of the OpenID codebases haven’t bothered with CRLs (or they don’t enable their checking by default so it’s as if it wasn’t there for most users).

One has to conclude that Sun (and the other two providers) should not be trusted by anyone for quite a while to come. But does that matter ? Since OpenID didn’t promise all that much anyway, does a serious flaw (which does require a certain amount of work to construct an attack) make any difference? At present this looks like the modern equivalent of a small earthquake in Chile.

At any rate, legit torrents of the video presentations are available from The Last HOPE Video Tracker. Art of Information Security is seeding torrents, and plans to do so for the next 10 days.

Check ‘em out.

Cheers, Erik

Last HOPE Session Videos - Seeded by AoIS

By the way, you may notice that I'm making fewer posts over the next month or so. I'll be busy studying for the GRE, wish me luck.

Bruce Sterling (11/20/2001):

You know what I want? I don't want a National ID Card. I want a Global Coalition Visa.

Like it or not, we've got a huge global diaspora now. It is a fact of life. Nations with stupid and corrupt politics have seen their clever people brain- drained away, to places where the cops don't shake you down twice a day. And jet-setters go everywhere. And properly so. If you're in a true global society, then you spend a lot of your time among aliens. Quite often you are the alien. You might notice that even Al Qaeda is a genuinely multinational group. They gravitated to wicked, lawless places like Sudan, Chechnya and Afghanistan, where the locals shoot you if you ask for a badge.

But what about all us bright, shiny, world-trading jet setters, huh? There are thirty percent fewer Yankees in Europe this Christmas, and that is bad. Let me pose the problem this way. If I am going into a Japanese restaurant in Japan, I would rather like to be able to haul out some gizmo and flash it at my fellow civilians, and have these kindly people understand with a high degree of likelihood that I am not a mass murderer. On the contrary, I am quite civilized, and I should be brought a beer immediately.

A platinum VISA card and a five-hundred-dollar suit will almost do that, but those are too easy to forge and steal, plus they are not very democratic. The UN should get together on this. We should have a high level summit about digital hardware support for the crippled tourist economy. Fear and ill treatment shut down tourism faster than anything short of open warfare. That is bad for all of us. Killing off tourism harms our civilization and impoverishes our cultures. People in civilized states shouldn't routinely treat one another as criminal suspects. I don't want to get done-over for three hours every time I get off a plane in London. When I go to London, I go with empty suitcases. I don't plan to stay, but I am better news for the London economy than a lot of the people who live there.

They should know all that that before I get off the plane. My arrival is excellent news for Britain, so I should be treated that way. If this is a new kind of war, I don't want to be the evil guy hunkered down in the bunker; I want to fly with the boys from Air Assault. I want one of those handy crypto-style Friend-or-Foe IDs.

These people who normally meet me whenever I am an alien, they don't need to know my nationality, my home address or my shoe size. They just need to know that, despite being alien, I'm sort-of okay.

I want a democratic, citizen-to-citizen device that will bridge those social barriers and language barriers. I think we could invent devices and means of verification that would strengthen the global social fabric that terrorism wants to rip. It wouldn't be easy or simple, but it's not beyond our ingenuity. Our social capital sustains all civilized societies, and it is all about trust. So let's invent new methods of trust.

I added bold to the last sentence because I think this is the mission statement for building out federation systems.

This happened recently to some Amazon S3 customers. There were complaints in the AWS forums about ‘S3 Corruption’. The first post in the forum was recorded at Jun 22, 2008 5:05 PM PDT (although in subsequent posts some people reported emailing Amazon prior to this):

we are having some serious S3 issues.

all data we store on S3 has gone through the same code path for months. starting a couple days ago a small percentage of the objects we are retrieving are not checksumming to the correct values. we hash and store objects by checksum and rehash the objects when we retrieve to ensure there is no data corruption. all the objects we’re having issues with were uploaded at approximately the same time period a few days ago.

we’ve stored 10’s of millions of objects in S3 and never encountered such problems. please let me know ASAP if you have any idea what could be going on here. thanks.

Amazon responded 6 minutes later (!) and started investigating. To troubleshoot they asked customers to email aws@amazon.com with the ‘Bucket-Name and few keys that you believe are having issues’.

Others weighed in reporting similar problems. Amazon provided status updates and on Monday Jun 23rd at 6:10pm PDT, provided the following explanation:

We’ve isolated this issue to a single load balancer that was brought into service at 10:55pm PDT on Friday, 6/20. It was taken out of service at 11am PDT Sunday, 6/22. While it was in service it handled a small fraction of Amazon S3’s total requests in the US. Intermittently, under load, it was corrupting single bytes in the byte stream. When the requests reached Amazon S3, if the Content-MD5 header was specified, Amazon S3 returned an error indicating the object did not match the MD5 supplied. When no MD5 is specified, we are unable to determine if transmission errors occurred, and Amazon S3 must assume that the object has been correctly transmitted. Based on our investigation with both internal and external customers, the small amount of traffic received by this particular load balancer, and the intermittent nature of the above issue on this one load balancer, this appears to have impacted a very small portion of PUTs during this time frame.

What are some of the takeaways?

• If you are directly using the AWS S3 API, make sure to calculate and send MD5 checksums along with actual data. Check status return codes - an HTTP 400 error code means ’something went wrong’ - respond appropriately.
• If you are relying on 3rd party tools to access S3, be sure to check with your software vendor that they are following the advice from Amazon to use MD5. If they are not then your data can get silently corrupted…
• Downloads, aka HTTP GETs, can also be affected. The thread in the forum continues and questions are asked as to whether the corruption caused by the loadbalancer was affecting both incoming and outgoing traffic. The conclusion was yes. If you are hosting media on S3, and the browser is using partial GET requests (to download in chunks) then the corruption will not be automatically detectable.
• If your business relies on Cloud Storage, are you prepared to wait a 36 hours for a resolution? This isn’t a swipe at Amazon, this is true for any provider. Check your SLA’s, check the trouble ticket resolution times, ask about availability of experts for troubleshooting etc.
• Cloud Providers will increasingly need to instrument their services such that they can ‘early detect’ negative operational events. In this case, Amazon has stated plans to use better logging and analysis to automate detection of unusual error patterns (i.e. anomoly detection).
• This incident - caused by an Amazon malfunctioning loadbalancer - did not make it onto the AWS status page at http://status.aws.amazon.com/. Taking Amazon at face value, this incident only affected a small number of transfers, relative to the total number of S3 transfers. But this begs the question, what level of outage or service problem needs to happen before Amazon will flag the issue on their status page? On a sidenote, based on the timestamps, 31 hours passed between the loadbalancer being taken out of service and Amazon providing the explanation on the forum.
• When Amazon update their S3 API documentation, it would be useful to have entries in the S3 API index for ‘checksum’, ‘MD5′, ‘integrity’ and ‘corruption’.
• Stepping back, will customers hold Cloud Service Providers to a higher standard than their own internal IT teams?

I’m sure there are more takeaways I didn’t cover. What say you?

###

Kudos for the heads-up on the S3 issue goes to my friend and colleague Jason Harper - network supremo and crypto-head. Thanks Jason!