News for hackers. Stuff that matters.
Re:The Little MAC Attack by sdevlin on Tuesday May 12, 2015 @08:56PM (#9536038)
> And yet. This is novel

No.

EDIT: I've been told to elaborate.

This is just direct fallout from the way Merkle-Damgard hash functions work. MD hash functions look like this:

    function MD(C, h, M):
        M <- pad(M)
        for m in blocks(M):
            h <- C(h, m)
        return h
The core of an MD hash is the compression function C, which takes an input state h and a message block m and produces a new state. When you find a collision in an MD hash function, you're really finding a collision in C. That is, some state h and some pair of message blocks m1 and m2 such that C(h, m1) = C(h, m2).

Now, HMAC. HMAC is defined over a hash function, and it looks like this:

    function HMAC(H, k, M):
        k1 <- ipad ^ k
        k2 <- opad ^ k 
        return H(k2 || H(k1 || M))
Where "||" is the concatenation operator. A simplified view of HMAC is that the key is used to scramble the initial state of H. This prevents the attacker from finding collisions on the inner hash function, because they don't know any interior state h. (The outer hash prevents length-extension attacks.)

Which makes this article pretty silly: the whole point of HMAC is that the attacker doesn't get to know interior hash states. It pretty much goes without saying that if a) an attacker can find collisions on H for arbitrary states h and b) they know some interior state h of the HMAC, then it follows directly that they can find collisions on the HMAC.

Hey, want to see some more practical "attacks" on HMAC? Here we go!

    In [11]: HMAC(b'\x00', b'chili dog', sha256).hexdigest()
    Out[11]: '3128a12ed7dd6cd4ad9d2720126698d1c0c3e2d991ddbf73ebbecd947581acd9'

    In [12]: HMAC(b'\x00\x00', b'chili dog', sha256).hexdigest()
    Out[12]: '3128a12ed7dd6cd4ad9d2720126698d1c0c3e2d991ddbf73ebbecd947581acd9'
Whoaaa, what?! Again!

    In [17]: HMAC(sha256(b'A'*500).digest(), b'chili dog', sha256).hexdigest()
    Out[17]: '426b6ec9b0e6b5fae9d12924432c023e8bc3444aa3adc4c48fdc875357c54c2f'

    In [18]: HMAC(b'A'*500, b'chili dog', sha256).hexdigest()
    Out[18]: '426b6ec9b0e6b5fae9d12924432c023e8bc3444aa3adc4c48fdc875357c54c2f'
Oh nooo! HMAC!
Re:The Little MAC Attack by sarciszewski on Tuesday May 12, 2015 @09:56PM (#9536279)
I especially like the second one, because it's less obvious even to someone used to breaking apps with null bytes. :)
Re:The Little MAC Attack by sdevlin on Tuesday May 12, 2015 @10:00PM (#9536296)
The two collision examples I used both rely on the key expansion step in HMAC, which I glossed over in my explanation. If you go look up the HMAC spec, it should be pretty clear why these work.
Re:The Little MAC Attack by sarciszewski on Tuesday May 12, 2015 @10:33PM (#9536415)
I recall someone (maybe solardiz) commenting on this property of the HMAC spec a few months back. It's not something I would have expected.
Re:The Little MAC Attack by dakami on Tuesday May 12, 2015 @10:44PM (#9536441)
Yeah, a message less than blocksize bytes is padded with 0's, and a message greater than blocksize bytes is hashed to blocksize bytes. It "follows" just as much as Little MAC, is about as security relevant, and is no less clever (arguably a bit more).
Re:The Little MAC Attack by tptacek on Tuesday May 12, 2015 @10:48PM (#9536451)
Can you be a little more specific about the cleverness you're referring to here?
Re:The Little MAC Attack by dakami on Tuesday May 12, 2015 @11:30PM (#9536571)
Sure!

HMAC keys are exactly one block long. But lets say an app wants to have a key that's two blocks long. No big deal, hash that app key and now two is one.

Ah, but now let's say the attacker has control of input keys. He can provide both the two block key which HMAC will hash for him, or he can do the work himself and prehash the two into one. Now two different input keys seem to provide the same output (assuming identical messages, of course).

Clever, no likely security impact.

Re:The Little MAC Attack by sarciszewski on Wednesday May 13, 2015 @01:00AM (#9536844)
Because of the way HN structures comments, it took me a second to realize this wasn't a reply to my comment. (Or maybe I need glasses.)
Re:The Little MAC Attack by marshray on Tuesday May 12, 2015 @11:10PM (#9536510)
Message, or key?

(Hi guys something unrelated finally prompted me to unfreeze my HN account!)

Re:The Little MAC Attack by dakami on Tuesday May 12, 2015 @11:27PM (#9536559)
You're right. HMAC keys, from the internal hash perspective, are always one block long. So if the key coming into HMAC is less than blocksize, it's zero padded to blocksize. And if the key coming into HMAC is length greater than blocksize, it's hashed down to blocksize. Obviously this does create collisions if the key ends with nulls and is less than 64 bytes, or if the attacker can specify keys.

None of this likely matters in practice.

Re:The Little MAC Attack by dakami on Tuesday May 12, 2015 @10:42PM (#9536437)
It's novel in that I wasn't able to find anyone else who had posted a colliding HMAC pair, and the couple papers people have found have sniffed around but hadn't quite gotten to the point of "Oh, yeah, compensate for ipad and collide after the first block".

You're correct that it went without saying in that people did not actually say it.

Way to not cite Solar Designer though.

Re:The Little MAC Attack by tptacek on Tuesday May 12, 2015 @10:44PM (#9536442)
What exactly should he have cited Solar Designer about? If you're going to criticize someone for not citing, and the citation isn't obvious, you should probably provide a link.

Are you referring to the key expansion property that Scott mentioned downthread? He cited the appropriate source: the HMAC specification. The properties he's talking about are obvious: the key is zero-padded to the block size and, if longer than the block size, hashed.

Re:The Little MAC Attack by dakami on Tuesday May 12, 2015 @11:24PM (#9536548)
You're right. I'm specifically referring to his attacks.

I'm curious if you can find any references to the key expansion / hashing collision before Solar Designer started talking about it a little while ago.

If they're obvious you should be able to find dozens of references. Because they're obvious.

Re:The Little MAC Attack by tptacek on Tuesday May 12, 2015 @11:42PM (#9536620)
This took 15 seconds to find: https://eprint.iacr.org/2012/684.pdf
Re:The Little MAC Attack by dakami on Tuesday May 12, 2015 @11:39PM (#9536614)
I stand corrected, there are in fact a decent number of people who mentioned HMAC(K,X)==HMAC(H(K),X) when len(K)>blocksize. So, you had no reason to cite Solar Designer and I shouldn't have implied you should. Sorry about that!

Still interested if you can find an earlier cite for HMAC collision. Most of what I find implies mad crypto cleverness, not this silly little construction.

Re:The Little MAC Attack by mckiddy on Tuesday May 12, 2015 @09:18PM (#9536124)
If you know the HMAC key, why would you ever need to generate a collision? You can just reevaluate the MAC and replace the old one.
Re:The Little MAC Attack by jessaustin on Tuesday May 12, 2015 @09:31PM (#9536177)
I think the point was that if some dumb protocol were misusing HMAC (and I'm not good enough at thinking about protocols to imagine how it might do so), it could be vulnerable to collisions generated this way.
Re:The Little MAC Attack by tptacek on Tuesday May 12, 2015 @09:50PM (#9536257)
The point of the parent commenter is that a misuse of HMAC that gives attackers knowledge of the key admits much simpler attacks than this.
Re:The Little MAC Attack by tptacek on Tuesday May 12, 2015 @09:18PM (#9536125)
Yup.

"This almost certainly doesn’t have any security impact, but I’m happy(ish) to be proved wrong."

There's a few words I'd remove from that sentence, I guess.

Re:The Little MAC Attack by sdevlin on Tuesday May 12, 2015 @09:39PM (#9536212)
SNARK REDACTED
Re:The Little MAC Attack by tptacek on Tuesday May 12, 2015 @09:50PM (#9536261)
See this kind of snark is usually what gets 'pbsd to come out of the shadows and smack me down. Your turn this time!
Re:The Little MAC Attack by sarciszewski on Wednesday May 13, 2015 @02:55PM (#9541178)
I think it's because you're not wrong here. :D
Re:The Little MAC Attack by oldmanjay on Tuesday May 12, 2015 @08:05PM (#9535865)
> (!= is nerd for Not Equal.)

made me laugh out loud. how many not-nerds would have made it that far?

Re:The Little MAC Attack by ekimekim on Tuesday May 12, 2015 @08:13PM (#9535899)
I could feasibly see a mathematician understanding all this but not being familiar with that symbol, which is mostly used in programming (math prefers a ≠ b instead of a != b).
Re:The Little MAC Attack by oldmanjay on Wednesday May 13, 2015 @11:59AM (#9539921)
good point, I paid more attention to the code listing than anything else so in retrospect, I hadn't really considered that.
Re:The Little MAC Attack by dakami on Tuesday May 12, 2015 @11:31PM (#9536576)
It's the crazy little things that people don't understand. You can't spell tax, without syntax.
Re:The Little MAC Attack by dakami on Tuesday May 12, 2015 @11:32PM (#9536579)
Er, syntax without tax. ANYWAY