News for hackers. Stuff that matters.
Re:MD5 hash extension attack breaks API authentication in Fl... by tptacek on Monday September 28, 2009 @11:55AM (#848638)
Good work from Bruce Leidl's team at Netifera (Bruce is brl, a regular).

Long story short: with all the mainstream hash algorithms, if you know the length of a hashed message, you can take its hash and from it synthesize the hashes of messages with arbitrary suffixes. It's called a message extension attack.

A really common pattern in hand-rolled authentication schemes is to hash a message needing authentication with a secret key, and then send the message and the hash. If you know the secret key, you can verify the message. The secret key doesn't need to be sent at all.

If your scheme is vulnerable to message extension attacks, attackers can mint arbitrary messages with valid authentication by taking an already-authenticated message and extending it to cover a suffix that changes the meaning of the legitimate message. It's a game-over flaw.

Colin Percival noticed a related (but less serious) flaw in Amazon's AWS authentication scheme. At the time, people asked if he'd looked at Flickr's scheme. He had, but not very closely. Colin's flaw was in canonicalization of messages, which is a more obscure attack (by a little bit) than message extension, which is is described in the Wikipedia under "Cryptographic Hash Function". Colin didn't flag this flaw.

Which just shows to go you: crypto primitives are radioactive. You are not going to get them right. Use high-level interfaces like GPG or SSL or cryptlib, or design your app not to need crypto.

Re:MD5 hash extension attack breaks API authentication in Fl... by cperciva on Tuesday September 29, 2009 @01:37AM (#849877)
Colin didn't flag this flaw.

To be fair, I didn't notice message extension attacks because AWS used an HMAC -- not a hash function -- and thus wasn't vulnerable.

crypto primitives are radioactive. You are not going to get them right

It doesn't take an expert cryptographer to know that if you want a MAC you should use a MAC.

Re:MD5 hash extension attack breaks API authentication in Fl... by tptacek on Tuesday September 29, 2009 @12:36PM (#850683)
No, but apparently it takes better than Google can muster to implement that MAC in such a way that Nate Lawson can't extract secrets from it remotely. You will never win this argument.
Re:MD5 hash extension attack breaks API authentication in Fl... by NateLawson on Wednesday September 30, 2009 @02:34PM (#853288)
I was surprised that both flaws they exploited were mentioned in the talk I gave at Yahoo back in June. One of the researchers that found this attack informed me that they independently found this in Flickr, not as a result of my talk. Interesting coincidence!

http://rdist.root.org/2009/06/10/when-crypto-attacks-slides-...

Re:MD5 hash extension attack breaks API authentication in Fl... by dfranke on Monday September 28, 2009 @06:36PM (#849389)
Isn't "game-over flaw" a bit overstated? It's a serious blunder, but if the data you're authenticating is highly structured then in many cases it won't be exploitable because the final padding from the original message becomes part of the body of the extended message, as unparseable gibberish.
Re:MD5 hash extension attack breaks API authentication in Fl... by thaidn on Monday September 28, 2009 @11:05PM (#849716)
The final padding is never parsed if we put set them as (part of) the value of an unknown key, i.e., setting a=pi_key....<pading>
Re:MD5 hash extension attack breaks API authentication in Fl... by dfranke on Tuesday September 29, 2009 @01:27AM (#849861)
I'm talking about exploitation of this vulnerability in general, not the specific case of Flickr. Not everything is a sequence of key-value pairs formatted in UTF-8.
Re:MD5 hash extension attack breaks API authentication in Fl... by tptacek on Tuesday September 29, 2009 @12:38PM (#850688)
Most of the crypto you're going to run across as a pentester will be in apps written in Java and C#, and in almost every one of those cases, garbage characters won't break a parse. ".split()" works just fine even if you have 16 characters of random high ASCII. It's one of those things C programmers definitely have to unlearn.
Re:MD5 hash extension attack breaks API authentication in Fl... by dfranke on Tuesday September 29, 2009 @01:35PM (#850868)
Eeeeeeewwwww.

If you're using .split() to "parse" untrusted input, and not even validating it against a regex first, that's an epic fail in its own right.

Re:MD5 hash extension attack breaks API authentication in Fl... by tptacek on Wednesday September 30, 2009 @04:00PM (#853511)
What a weird thing to say. You trust a regex engine more than you trust "split()"?
Re:MD5 hash extension attack breaks API authentication in Fl... by dfranke on Wednesday September 30, 2009 @04:07PM (#853526)
I trust a generated parser more than a hand-written one. Any parsing algorithm that involves the use of split() is almost certain to be weakly thought-out and have ill-defined behavior for unexpected input. A well-written parser will never read past the first unexpected character, or at least token.
Re:MD5 hash extension attack breaks API authentication in Fl... by juli on Tuesday September 29, 2009 @02:20AM (#849925)
Attacker controls the length of the message so he can make the padding be only 9 bytes long
Re:MD5 hash extension attack breaks API authentication in Fl... by NateLawson on Wednesday September 30, 2009 @02:32PM (#853279)
This is equivalent to the old claim, "Since an attacker can only write a 0-byte somewhere in memory, this is a crash-only bug."
Re:MD5 hash extension attack breaks API authentication in Fl... by wizard_2 on Monday September 28, 2009 @11:47AM (#848630)
This reminds me a lot of the problem the amazon s3api v1 suffered from. (It's referenced in this paper.) Colin Percival did a wonderful job alerting amazon and getting it fixed. Reading the paper it looks like they tried to alert people, but they didn't go into detail.

You can read more about the amazon problem at Colin's blog. http://www.daemonology.net/blog/2008-12-18-AWS-signature-ver...

Re:MD5 hash extension attack breaks API authentication in Fl... by idlewords on Monday September 28, 2009 @01:59PM (#848863)
Yahoo has dedicated internal people who, if you ask them nicely, will pick your app apart to find these kinds of design and implementation errors. Reviewing your code with them is very educational but not pleasant to the ego. Either they completely fell down on the job, or the Flickr devs decided they were smart enough to do security by themselves.
Re:MD5 hash extension attack breaks API authentication in Fl... by tptacek on Monday September 28, 2009 @03:55PM (#849093)
Every major tech firm has an in-house app security or "SDLC" team. But outside of Microsoft --- or, even in some cases at Microsoft --- most people sub crypto design and verification out to people like Paul Kocher's CRI.

It's probably not fair to trace a cryptosystem flaw back to a web app security team.

Re:MD5 hash extension attack breaks API authentication in Fl... by thaidn on Monday September 28, 2009 @02:39PM (#848935)
afaik, the API was built before Yahoo! bought Flickr
Re:MD5 hash extension attack breaks API authentication in Fl... by lanstein on Monday September 28, 2009 @05:17PM (#849243)
Link is the one mentioned above, http://www.flickr.com/services/api/auth.spec.html
Re:MD5 hash extension attack breaks API authentication in Fl... by lanstein on Monday September 28, 2009 @05:17PM (#849242)
Perhaps, but there's an author listed on the API docs page with an internal Yahoo email address FWIW.
Re:MD5 hash extension attack breaks API authentication in Fl... by juli on Monday September 28, 2009 @03:15PM (#849013)
Sites using this vulnerable signing method must add a warning to their documentation.

Flickr authentication spec lists ludicorp.com authors,

http://www.flickr.com/services/api/auth.spec.html

Re:MD5 hash extension attack breaks API authentication in Fl... by pwpwp on Monday September 28, 2009 @08:35PM (#849547)
The takeaway for me was: 1) use a HMAC instead of using message digests directly 2) don't throw away structure in the strings you sign.
Re:MD5 hash extension attack breaks API authentication in Fl... by NateLawson on Wednesday September 30, 2009 @02:29PM (#853273)
Once you reach number 30 or 40 in this list, you get a lot more leery of takeaways.