What does it mean that Hmac is secure?

Question

I'm not taking about general collision attack on weak hash function such as MD5 or SHA-1. I'm wondering security of HMAC which is based on weak hash function

If there are key k, message m

Hmac(k,m) = hash(k`xor opad) || hash( (k` xor ipad) || m ) )

First Question, What does it mean that Hmac is secure?

1. Attacker cannot generates valid Hmac of given message m without knowing key

2. Attacker cannot finds collision that satisfy Hmac(k',m') = Hmac(k,m) such k',m'

3. Attacker can recover key k

4. others

And Second Question.

I'm reading about paper Transcript Collision

Transcript Collision Attacks: Breaking Authentication in TLS,IKE, and SSH

In this paper, They introduce Transcript collision Attacker know m1 and m2. And can find collision that satisfy hash(m1 || m2' ) == hash(m1' || m2 ) such m1' and m2'

If adversary uses this Transcript Collision Attacks in weak hash function, Can he also finds collision that satisfy Hmac(k',m') = Hmac(k,m) such k',m'??

Answer 1

There is some research that strictly defines and proofs how HMAC is secure:

• Keying Hash Functions for Message Authentication
• The Exact PRF-Security of NMAC and HMAC
• New Proofs for NMAC and HMAC: Security without Collision-Resistance

HMAC is a message authentication mechanism. This means that if an attacker changes a message, it can be detected because the HMAC no longer matches. This basically means that there is no message m' so that HMAC(k, m') == HMAC(k, m). Note that k is the same here. If the attacker finds a collision with another key, so that HMAC(k', m') == HMAC(k, m), this can not be used to spoof a message.

Answer 2

Cryptographers have a generally accepted definition of MAC security: resistance to existential forgery under adaptive chosen-message attack. Most cryptography textbooks cover this definition—for example, the Handbook of Applied Cryptography is a good source for this. The HAC is available online, so you might want to browse Chapter 9. It's a bit dated on the algorithms side, but the definitions are generally still applicable.

But to just coarsely expand this, the security goal for MACs is this. Assume that:

1. The attacker doesn't know the defender's secret key;
2. The attacker can cause the defender to compute tags for messages of their choice;
3. The attacker can use the results of earlier queries to refine later ones.

Then a MAC is broken if an efficient attacker is able to forge any valid (message, tag) pair for a message they didn't query as part of #2. (Note that proper formulations of this definition have some math attached to them quantifying the effort that the attacker puts into the attack and what probability of success is unacceptable.)

If the key is secret this definition implies the security goals that you list (see the HAC for more detail):

1. Attacker cannot generate valid Hmac of given message m without knowing key
2. Attacker cannot finds collision that satisfy Hmac(k',m') = Hmac(k,m) such k',m'
3. Attacker cannot recover key k

HMAC is designed to meet at least MAC security, but there are also proofs that HMAC supports another, stronger goal, called PRF security ("PRF" = pseudorandom function), which says that an efficient attacker can't tell the function apart from a randomly selected function of the same domain and range.