Subject: [Cfrg] RFC analyzing IETF use of hash functions [was: Re: [saag] Further MD5 breaks: Creating a rogue CA certificate]

From: David McGrew <[email-masked]>
Date: Mon, 5 Jan 2009 14:50:07 -0800

Hi Ran,

I think it is a great idea to document the IETF applications/uses of  
hashing, and the attacks against particular uses of hashing.  It would  
make a great CFRG informational RFC, if we can find volunteers to  
contribute to and edit it.  I offer to review it.

David

On Dec 31, 2008, at 7:48 AM, RJ Atkinson wrote:

>
> [Distribution trimmed slightly to reduce cross-posting and improve  
> SNR.]
>
> On  30 Dec 2008, at 20:20, Peter Gutmann wrote:
>> The current MD5 attack is very cool but there's no need to worry  
>> about
>> bad guys doing much with it because it's much, much easier to get
>> legitimate CA-issued certs the normal way, you buy them just like
>> everyone else does (except that you use someone else's credit card
>> and identity, obviously).
>
>
> Two thoughts:
>
> 1) Protocol Issues
>
> The IETF ought to be thinking about a wide range of IETF protools
> in the same way that Peter thinks about CA security issues above.
>
> For some IETF protocols, for example all of the IGP authentication
> extensions (excepting RFC-2154, AFAICT), active non-cryptographic
> attacks are feasible (if not yet seen in the deployed world, AFAICT)
> that are much easier than *any* cryptographic attack.  Again, and
> only by way of example, RFC-4822 discusses some of these that are
> specific to RIPv2 authentication.
>
> For protocols where non-cryptographic attacks are feasible AND
> are lower cost than a cryptographic attack, really it does not make
> much difference what cryptographic algorithm gets deployed by a user
> -- and the IETF's focus should be on improving the underlying  
> authentication mechanism BEFORE worrying about which cryptographic
> algorithms are being deployed.
>
> Attackers are generally both smart and lazy, so they won't waste
> time on an expensive cryptographic attack when a lower effort
> non-cryptographic attack exists.
>
>
> 2) Hash algorithm analysis
>
> It would be very helpful if a *set* of mathematicians/cryptographers
> could jointly put together a summary of the known attacks on all
> the widely used hash algorithms (e.g. MD2, MD4, MD5, SHA-0, SHA-1,
> SHA-2, others), *including references to the published literature*.
>
> Ideally, this analysis would also include discussion of whether those
> attacks apply for those same algorithms when used in the modes  
> employed
> by various IETF protocols today (e.g. Keyed-Hash as used in OSPFv2 MD5
> or RIPv2 MD5, HMAC-Hash, and so forth).
>
> This would be most useful to have as an Informational RFC,
> and SOON, so that IETF WGs could have some "consensus" document
> to refer to -- and to cite explicitly -- if any IETF WGs decide
> to make hash algorithm recommendations or decisions.
>
> I don't understand IRTF process details perfectly, but perhaps
> the CFRG chairs might undertake creating such a document as a
> near-term official CFRG group project.
>
> Yours,
>
> Ran
> [email-masked]
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 5 Jan 2009 15:09:58 -0800

At 2:50 PM -0800 1/5/09, David McGrew wrote:
>I think it is a great idea to document the IETF applications/uses of hashing, and the attacks against particular uses of hashing.  It would make a great CFRG informational RFC, if we can find volunteers to contribute to and edit it.  I offer to review it.

I will volunteer to update RFC 4270, and I assume that Bruce Schneier would be willing to still be my co-author.

--Paul Hoffman, Director
--VPN Consortium

---

From: Sean Turner <[email-masked]>
Date: Mon, 05 Jan 2009 22:20:41 -0500

Dave,

When the S/MIME WG penned 
http://tools.ietf.org/html/draft-ietf-smime-multisig-05 we added an 
appendix that addresses where hashes are located in CMS's SignedData and 
the attacks against those hashes.  I'd be willing to help craft any 
other wording necessary for S/MIME|CMS.

spt

David McGrew wrote:
>> [Distribution trimmed slightly to reduce cross-posting and improve SNR.]
>>
>>> The current MD5 attack is very cool but there's no need to worry about
>> attacks apply for those same algorithms when used in the modes employed
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag
>

---

From: Sean Shen <[email-masked]>
Date: Tue, 06 Jan 2009 11:33:31 +0800

Hi,
A draft in CSI work group gives some analysis on hash threats on
CGA(RFC3972) and SeND(RFC3971). Hope it also provides valuable info.
I will be happy to give review or other possible support for this valuable
work.

Best,

Sean

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On 
>Behalf Of Sean Turner
>Sent: Tuesday, January 06, 2009 11:21 AM
>To: David McGrew
>Cc: [email-masked]; [email-masked]
>Subject: Re: [saag] RFC analyzing IETF use of hash functions 
>[was: Re: [Cfrg] Further MD5 breaks: Creating a rogue CA certificate]
>
>Dave,
>
>http://tools.ietf.org/html/draft-ietf-smime-multisig-05 we 
>added an appendix that addresses where hashes are located in 
>CMS's SignedData and the attacks against those hashes.  I'd be 
>willing to help craft any other wording necessary for S/MIME|CMS.
>
>spt
>
>David McGrew wrote:
>> Hi Ran,
>>

---

From: David McGrew <[email-masked]>
Date: Tue, 6 Jan 2009 04:31:32 -0800

Hi Sean,

On Jan 5, 2009, at 7:20 PM, Sean Turner wrote:

> Dave,
>
> When the S/MIME WG penned http://tools.ietf.org/html/draft-ietf-smime-multisig-05 
>  we added an appendix that addresses where hashes are located in  

great, thanks for volunteering.

David

>
>
> spt
>
> David McGrew wrote:
>> Hi Ran,
>> I think it is a great idea to document the IETF applications/uses  
>> of hashing, and the attacks against particular uses of hashing.  It  
>> would make a great CFRG informational RFC, if we can find  
>> volunteers to contribute to and edit it.  I offer to review it.
>> David

---

From: David McGrew <[email-masked]>
Date: Tue, 6 Jan 2009 04:32:13 -0800

thanks for volunteering, Sean.

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 7 Jan 2009 10:34:41 -0500

I have a vested interest in this discussion, as I designed the HITs in 
HIP to be hashes of the public key (the HIs), and I speced SHA-1 with no 
agility for using another cipher.

My ASSuMption was that it would take a post-image attack (think I got 
that right without going back to my old notes) for someone to design a 
public key pair to duplicate a published HIT.

A pre-image attack is just not interesting as so what if someone has two 
HIs with the same HIT, provided they are not 'selling' these, it is easy 
enough for any platform to gen its own HIs and HITs.

If it is the concensus of people that are deeper into hashes than I am 
(doesn't take all that much), I will add HIT hash agility to a proposed 
change to HIP.

Though, another argument for the agility is 5 years down the road we 
might not want SHA-1 in any RFC, so the ablity to 'age it out, 
gracefully' is still needed.

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 07 Jan 2009 08:00:02 -0800

At Wed, 7 Jan 2009 10:34:41 -0500,
> public key pair to duplicate a published HIT.

This would be a 1st preimage attack. 

> enough for any platform to gen its own HIs and HITs.

That would be a collision attack.

-Ekr

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Wed, 7 Jan 2009 08:54:20 -0800

I have been looking into the issue as well, at this point I do not wish to comment on any past circumstances and would appreciate it if others did not attempt to raise them.

One of my major concerns here is what the implications are for the SHA1 to future digest transition. And that is a really difficult problem because I can well imagine a circumstance in which SHA1 is broken while it is still in widespread use. Moreover I can well imagine SHA1 being broken at a point where there is a significant legacy application base that does not support the successor.

The MD5->SHA1 transition does not provide a good model here because every deployment of SSL supported both MD5 and SHA1.

The current situation is that we have known issues with SHA1 that we believe to be manageable. We have SHA256 as a possible replacement but it is from the same family and thus gives only limited additional confidence. And SHA2 is going to be 2010 at the earliest and possibly 2011 or later and even then may be optimized more for speed than for the greatest possible certitude of security.

This all has me looking at using MAC functions and in particular CMAC-AES as a digest function. The simple collision attack using a supplied source text can be defeated entirely using a MAC function and a randomly chosen IV.

The principal advantages of using CMAC-AES with a random IV are

1) It is completely specified today, except for the details of the packaging in RSA and DSA.
2) Simple collision attacks are defeated entirely through use of a sufficiently random IV.
3) Plug compatible with existing crypto APIs
4) A constrained implementation can render every symmetric cryptographic function (encryption, digest, MAC) from a single cryptographic primitive.
5) CMAC construction means that the security of our cryptographic system only depends on the security of a single symmetric primitive - AES and our random number generator.

[We can also derive a random number generator by using CMAC-AES over a counter plus a secret key.]

Another interesting property is that it gives us the DSA like feature that signing the same message with the same key does not generate the same signature. This means that we have binding to the signature event. and not simply the signing key. It also means that disclosure is limited. An attacker cannot deduce that two messages are the same because the signatures are the same.

Now there are certainly cases where this is not a desirable property. Hash tables are not going to work so well. But that objection could be avoided by using CMAC-AES, (t, 0).

OK so imagine we have our better digest, whether it is CMAC-AES or SHA2. How do we make use of it? In particular what can we start doing today that creates an 'insurance plan' in case the worst should happen to SHA1? In particular any insurance policy must be 100% backwards compatible. We cannot shut off old browsers just because there might be a chance that there is a problem.

One option being suggested for certificates is to sign the cert twice, once with the new algorithm which is added to the cert as an extension and then again with the old one. Ugly, ugly. yuk yuk yuk. And what if you don't have one single algorithm you know in advance you will trust?

I think a better mechanism is to use my OCSP algorithm agility proposal with one additional extension in the OCSP, response, an extension giving the digest value of the cert whose status is being reported using the new algorithm.

So if SHA1 is compromised, a message is sent out to tell browsers that SHA1 can no longer be fully trusted (this can be a Rivest style suicide note, chose a value x, generate s = SHA1(x), pop that in the browser with code that turns off the 'trustworthy' bit for SHA1 if a message is ever delivered containing a value y such that SHA1(y) = s.

At that point the browser requires an OCSP validity token signed using a trusted algorithm and containing an extension with a matching digest value before it will trust any cert signed with SHA1. (OCSP response stapling in SSL is a good plan then).

This appears to me to be a plausible insurance policy that application providers and others could begin work on now. What matters is not whether the CAs deploy the infrastructure now, it is the deployment in the applications that matters. If the worst should happen a heck of a lot of code can be written and deployed at CAs and other service providers in a rather short time. Its the legacy application code that is the concern. 

I therefore propose the following as an action plan:

1) Discuss whether CMAC-AES with a random IV is an approach that provides confidence.

2) If so, develop packaging modes for RSA, DSA and Suite-B.

3) Define the necessary OCSP extensions

4) Application providers begin deployment of 'insured' code at their next regular update cycle.
   Sensible CAs do likewise.

What I like about this approach is that it provides for an insurance policy to be deployed in an orderly manner, without undue haste and without unnecessarily impacting legacy applications.

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 7 Jan 2009 12:35:36 -0500

I would think multiple signatures should be achieved using algorithm OID
in SPKI and in SIGNED MACRO.  This gives X.509 extensibility without
requiring a new extension and provides straightforward signature
chaining (a critical element in certification path).  It also provides
extensibility in terms of number of signatures and whether the hash
and/or signature algorithms are different.

I am still reviewing the rest of the proposal (i.e., hash/MAC and OCSP
extension)

________________________________

From: [email-masked] [mailto:[email-masked]] On Behalf Of
Hallam-Baker, Phillip
Sent: Wednesday, January 07, 2009 11:54 AM
To: Robert Moskowitz; [email-masked]
Subject: Re: [Cfrg] Analyzing IETF use of hash functions -- ORCHIDs

I have been looking into the issue as well, at this point I do not wish
to comment on any past circumstances and would appreciate it if others
did not attempt to raise them.

One of my major concerns here is what the implications are for the SHA1
to future digest transition. And that is a really difficult problem
because I can well imagine a circumstance in which SHA1 is broken while
it is still in widespread use. Moreover I can well imagine SHA1 being
broken at a point where there is a significant legacy application base
that does not support the successor.

The MD5->SHA1 transition does not provide a good model here because
every deployment of SSL supported both MD5 and SHA1.

The current situation is that we have known issues with SHA1 that we
believe to be manageable. We have SHA256 as a possible replacement but
it is from the same family and thus gives only limited additional
confidence. And SHA2 is going to be 2010 at the earliest and possibly
2011 or later and even then may be optimized more for speed than for the
greatest possible certitude of security.

This all has me looking at using MAC functions and in particular
CMAC-AES as a digest function. The simple collision attack using a
supplied source text can be defeated entirely using a MAC function and a
randomly chosen IV.

1) It is completely specified today, except for the details of the
packaging in RSA and DSA.
2) Simple collision attacks are defeated entirely through use of a
sufficiently random IV.
3) Plug compatible with existing crypto APIs
4) A constrained implementation can render every symmetric cryptographic
function (encryption, digest, MAC) from a single cryptographic
primitive.
5) CMAC construction means that the security of our cryptographic system
only depends on the security of a single symmetric primitive - AES and
our random number generator.

[We can also derive a random number generator by using CMAC-AES over a
counter plus a secret key.]

Another interesting property is that it gives us the DSA like feature
that signing the same message with the same key does not generate the
same signature. This means that we have binding to the signature event.
and not simply the signing key. It also means that disclosure is
limited. An attacker cannot deduce that two messages are the same
because the signatures are the same.

Now there are certainly cases where this is not a desirable property.
Hash tables are not going to work so well. But that objection could be
avoided by using CMAC-AES, (t, 0).

OK so imagine we have our better digest, whether it is CMAC-AES or SHA2.
How do we make use of it? In particular what can we start doing today
that creates an 'insurance plan' in case the worst should happen to
SHA1? In particular any insurance policy must be 100% backwards
compatible. We cannot shut off old browsers just because there might be
a chance that there is a problem.

One option being suggested for certificates is to sign the cert twice,
once with the new algorithm which is added to the cert as an extension
and then again with the old one. Ugly, ugly. yuk yuk yuk. And what if
you don't have one single algorithm you know in advance you will trust?

I think a better mechanism is to use my OCSP algorithm agility proposal
with one additional extension in the OCSP, response, an extension giving
the digest value of the cert whose status is being reported using the
new algorithm.

So if SHA1 is compromised, a message is sent out to tell browsers that
SHA1 can no longer be fully trusted (this can be a Rivest style suicide
note, chose a value x, generate s = SHA1(x), pop that in the browser
with code that turns off the 'trustworthy' bit for SHA1 if a message is
ever delivered containing a value y such that SHA1(y) = s.

At that point the browser requires an OCSP validity token signed using a
trusted algorithm and containing an extension with a matching digest
value before it will trust any cert signed with SHA1. (OCSP response
stapling in SSL is a good plan then).

This appears to me to be a plausible insurance policy that application
providers and others could begin work on now. What matters is not
whether the CAs deploy the infrastructure now, it is the deployment in
the applications that matters. If the worst should happen a heck of a
lot of code can be written and deployed at CAs and other service
providers in a rather short time. Its the legacy application code that
is the concern.

1) Discuss whether CMAC-AES with a random IV is an approach that
provides confidence.

4) Application providers begin deployment of 'insured' code at their
next regular update cycle.
   Sensible CAs do likewise.

What I like about this approach is that it provides for an insurance
policy to be deployed in an orderly manner, without undue haste and
without unnecessarily impacting legacy applications.

---

From: David McGrew <[email-masked]>
Date: Wed, 7 Jan 2009 15:26:24 -0800

Hi Paul,

thanks for volunteering.  For a CFRG doc it would be good to point out  
how existing standards can benefit from newer research results, and  
what open problems could be addressed with future research.

David

On Jan 5, 2009, at 3:09 PM, Paul Hoffman wrote:

> I will volunteer to update RFC 4270, and I assume that Bruce  
> Schneier would be willing to still be my co-author.
>
> --Paul Hoffman, Director
> --VPN Consortium

---

From: "Joseph Salowey (jsalowey)" <[email-masked]>
Date: Wed, 7 Jan 2009 16:03:06 -0800

I think this is an area where there is much ambiguity.  When a hash
function is used within a protocol it is often unclear what properties
are expected from it.  This causes problems when a flaw is uncovered and
the impact to the protocol is uncertain.  I think it would improve
things if we were a bit more specific about it. I'd be glad to
participate by reviewing, editing, contributing text or whatever else is
needed. 

Cheers,

Joe

> Behalf Of David McGrew (mcgrew)
> Sent: Wednesday, January 07, 2009 3:26 PM
> To: Paul Hoffman
> Cc: RJ Atkinson; [email-masked]; [email-masked]
> Subject: Re: [saag] [Cfrg] RFC analyzing IETF use of hash 
> functions [was:Re: Further MD5 breaks: Creating a rogue CA 
> certificate]
> 
> Hi Paul,
> 
> thanks for volunteering.  For a CFRG doc it would be good to 
> point out how existing standards can benefit from newer 
> research results, and what open problems could be addressed 
> with future research.
> 
> David
> 
> >> hashing, and the attacks against particular uses of hashing.  It 
> volunteers 
> >> to contribute to and edit it.  I offer to review it.
> >
> > I will volunteer to update RFC 4270, and I assume that 
> Bruce Schneier 
> > would be willing to still be my co-author.
> >
> > --Paul Hoffman, Director
> > --VPN Consortium
>

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Thu, 8 Jan 2009 06:04:04 -0800

Ugh, that kinda makes me not want to use CMAC construction for a MAC function either. HMAC has the property that knowing the key does not allow the output to be controlled, I am somewhat surprised it was not considered a necessary property for a MAC.

Certainly, it means that we cannot certify CMAC as a drop in replacement for cases where HMAC has been used. It might well be the case that none of the uses of HMAC depend on this property being true, but there is no way to be sure without re-analysing the security of the protocol from scratch. 

We have plenty of experience of problems coming from people using a stream cipher to do the work of a block cipher. Those problems are the result of having what are actually two primitives that are closely related enough to be considered equivalent but with one offering only a subset of the security guarantees of the other.

We have a strong cryptographic primitive here, a cipher function. Seems to me that if we do the job right it should be possible to create a strong one way function. I know Rogaway has argued that building everything on a one way function gives provable security. Problem is that one way functions have been the most troublesome function in practice. It is the only symmetric function which we have had standard algorithms broken through cryptanalytic attack, and not just once, we have had MD2, MD4 and MD5 broken and SHA1 is making us worried.

The problem for the strategy outlined is that it kinda depends on having a digest function that is fully certified right now. We can use the same strategy to use SHA256 or SHA512 as an insurance policy. But we can't fix CMAC and certify the result before the digest competition reads out.

I still like the idea of using a keyed digest function with a randomly chosen key as a digest. We should not be talking about ways to add randomness into the object being signed as protection. If we want randomness it should be input to the cryptographic layer and be - random.

I know that in an ideal world a digest function should be secure and not need some kind of backup, but given the experience of digest functions being the most likely to fail, I really like having the insurance of being able to add in the randomness.

-----Original Message-----
From: David Jacobson [mailto:[email-masked]]
Sent: Thu 1/8/2009 2:27 AM
To: Hallam-Baker, Phillip; [email-masked]
Cc: Robert Moskowitz
Subject: Re: [Cfrg] Analyzing IETF use of hash functions -- ORCHIDs
 
Hallam-Baker, Phillip wrote:
[snip]
> function (encryption, digest, MAC) from a single cryptographic primitive.
[snip]

We are in the context of replacing MD5 with some other hash function.

Item 3 is kind of slippery.

CMAC-AES as a plug is compatible with the socket labeled MAC, but it is 
not compatible with the socket labeled HASH.

More concretely, applications written for MD5 and SHA1 are not prepared 
to provide a secret key, which is needed for CMAC-AES.  And then there 
is the IV as well.

The definition of CMAC-AES in Wikipedia does not mention an IV, but I 
presume the intent is that first message block is XORd with E_k(IV), 
rather than E_k(0) as specified in CMAC-AES.

But there is a security problem, too.  Let us temporarily ignore the IV. 
  I believe that the strength of MACs derives from the fact that the 
secret key is secret. For signatures, the verifier has to know what 
value to use for the key so it has to be a constant, or be sent, or be 
derivable from stuff that is sent.   Finding a pre-image that works with 
CMAC_AES is trivial if the attacker knows k and can tolerate the last 
block being arbitrary:    He runs the CMAC_AES algorithm up to the last 
block, resulting in V. The attacker computes k1 (key for a last block 
that is full) according the the CMAC algorithm.  He decrypts the target 
hash value using k1 as the AES key.  Call that value W.  He makes the 
last block be V XOR W.

The IV doesn't help any.  Rather it completely defeats security. If it 
is a random value, it has to be communicated to the verifier, and the 
attacker can choose it. Let the attacker's desired message blocks be 
M_1, M_2, ... M_n.  Let the values entering the AES encryptions be P_1, 
P_2, ... P_n.  (Somewhere in the middle, P_k = M_k XOR E_k{P_{k-1}.) 
The attacker works backwards from the output, and  eventually computes 
what P_1 has to be.  He chooses IV = D_k{P_1 XOR M_1}.

   -- David Jacobson

---

From: David McGrew <[email-masked]>
Date: Thu, 8 Jan 2009 07:44:02 -0800

Hi Phillip,

On Jan 8, 2009, at 6:04 AM, Hallam-Baker, Phillip wrote:
> Ugh, that kinda makes me not want to use CMAC construction for a MAC  
> function either. HMAC has the property that knowing the key does not  
> allow the output to be controlled, I am somewhat surprised it was  
> not considered a necessary property for a MAC.
>
The property that you're describing assumes that there is an entity  
that knows the secret key, yet is not trusted, and that's outside of  
all of the definitions and models of MACs.  AES-CMAC is a perfectly  
good MAC, and can be substituted for HMAC whenever a MAC is needed.

Also, that property holds only if HMAC output is not truncated to a  
length below the security level for collision resistance.  For  
instance, it doesn't hold for HMAC-SHA1 truncated to 96 bits.
>
>
> Certainly, it means that we cannot certify CMAC as a drop in  
> replacement for cases where HMAC has been used. It might well be the  
> case that none of the uses of HMAC depend on this property being  
> true, but there is no way to be sure without re-analysing the  
> security of the protocol from scratch.
>

You're  right that there are uses of HMAC that require something  
stronger/different than just a MAC, though many protocols use it as  
just a MAC.  One rule of thumb for telling the difference would be to  
look at the output size of HMAC.

David
>
>
> We have plenty of experience of problems coming from people using a  
> stream cipher to do the work of a block cipher. Those problems are  
> the result of having what are actually two primitives that are  
> closely related enough to be considered equivalent but with one  
> offering only a subset of the security guarantees of the other.
>
>
> We have a strong cryptographic primitive here, a cipher function.  
> Seems to me that if we do the job right it should be possible to  
> create a strong one way function. I know Rogaway has argued that  
> building everything on a one way function gives provable security.  
> Problem is that one way functions have been the most troublesome  
> function in practice. It is the only symmetric function which we  
> have had standard algorithms broken through cryptanalytic attack,  
> and not just once, we have had MD2, MD4 and MD5 broken and SHA1 is  
> making us worried.
>
> The problem for the strategy outlined is that it kinda depends on  
> having a digest function that is fully certified right now. We can  
> use the same strategy to use SHA256 or SHA512 as an insurance  
> policy. But we can't fix CMAC and certify the result before the  
> digest competition reads out.
>
>
> I still like the idea of using a keyed digest function with a  
> randomly chosen key as a digest. We should not be talking about ways  
> to add randomness into the object being signed as protection. If we  
> want randomness it should be input to the cryptographic layer and be  
> - random.
>
> I know that in an ideal world a digest function should be secure and  
> not need some kind of backup, but given the experience of digest  
> functions being the most likely to fail, I really like having the  
> insurance of being able to add in the randomness.
>
>

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Thu, 8 Jan 2009 08:09:41 -0800

It is not a secret key, it is an input to a mathematical function. 

It only becomes a secret key when a protocol designer decides to make it secret. Until then it is simply a key.

Cryptographers have no business assuming that particular information is or is not available to an attacker. That is my prerogative as a protocol designer. Only a protocol can determine if information is secret or not.

To take another example. It is generally considered to be desirable for an encryption cipher to resist disclosure of the key in the case that an attacker has a known plaintext/ciphertext pair. That is not a necessary property for an encryption cipher if you have absolutely perfect operational security, but its one that any sensible protocol designer is going to insist on whether they are going to depend on the property or not.

HMAC is used with the assumption of a specific set of cryptographic properties. CMAC does not provide the same properties. Therefore CMAC MUST NOT be used as a replacement for a HMAC unless there is a full ground up review of the security considerations.

WEP is acceptably secure if you use a block cipher as the encryption mechanism. It becomes hopelessly insecure when you replace the block cipher with RC4 or any other stream cipher.

There are two distinct approaches to security protocol design. Most of us tend to avoid any construction that they feel falls short of the highest standards and might lead to a design oversight. I do not use stream ciphers and I am going to avoid using CMAC. Other folk sail closer to the wind, and there is certainly equipment out there that can support stream ciphers but not block ciphers.

I don't think this is an argument that is particularly worth having unless it turns out that it is impossible to create a MAC function from an encryption primitive that is also a strong one way function or that doing so imposes an unacceptable performance cost.

-----Original Message-----
From: David McGrew [mailto:[email-masked]]
Sent: Thu 1/8/2009 10:44 AM
To: Hallam-Baker, Phillip
Cc: David Jacobson; [email-masked]; Robert Moskowitz
Subject: Re: [Cfrg] Analyzing IETF use of hash functions -- ORCHIDs
 
Hi Phillip,

The property that you're describing assumes that there is an entity that knows the secret key, yet is not trusted, and that's outside of all of the definitions and models of MACs.  AES-CMAC is a perfectly good MAC, and can be substituted for HMAC whenever a MAC is needed.   

Also, that property holds only if HMAC output is not truncated to a length below the security level for collision resistance.  For instance, it doesn't hold for HMAC-SHA1 truncated to 96 bits.

You're  right that there are uses of HMAC that require something stronger/different than just a MAC, though many protocols use it as just a MAC.  One rule of thumb for telling the difference would be to look at the output size of HMAC.  

David

	

	-----Original Message-----
	From: David Jacobson [mailto:[email-masked]]
	Sent: Thu 1/8/2009 2:27 AM
	To: Hallam-Baker, Phillip; [email-masked]
	Cc: Robert Moskowitz
	Subject: Re: [Cfrg] Analyzing IETF use of hash functions -- ORCHIDs
	
	[snip]

	

	

	   -- David Jacobson

---

From: David McGrew <[email-masked]>
Date: Thu, 8 Jan 2009 09:57:53 -0800

Phillip,

On Jan 8, 2009, at 8:09 AM, Hallam-Baker, Phillip wrote:

> It only becomes a secret key when a protocol designer decides to  
> make it secret. Until then it is simply a key.
>
> Cryptographers have no business assuming that particular information  
> is or is not available to an attacker.
>
that's not right.  Cryptographers use models and definitions that  
determine what information is available to an attacker.  See, for  
example, Section 2.1 of "Keying Hash Functions for Message  
Authentication", the main reference for HMAC.  These precise models  
and definitions are a major part of modern cryptography.

> That is my prerogative as a protocol designer. Only a protocol can  
> determine if information is secret or not.
>
> To take another example. It is generally considered to be desirable  
> for an encryption cipher to resist disclosure of the key in the case  
> that an attacker has a known plaintext/ciphertext pair. That is not  
> a necessary property for an encryption cipher if you have absolutely  
> perfect operational security, but its one that any sensible protocol  
> designer is going to insist on whether they are going to depend on  
> the property or not.
>
>
> HMAC is used with the assumption of a specific set of cryptographic  
> properties. CMAC does not provide the same properties. Therefore  
> CMAC MUST NOT be used as a replacement for a HMAC unless there is a  
> full ground up review of the security considerations.
>
You're overstating this.  In what case can AES-CMAC not replace HMAC- 
SHA1 when the length of the ICV is truncated to 96 bits?

Perhaps I would understand your point better if you could describe an  
example of a use of HMAC that is motivating your concern.

>
>
> WEP is acceptably secure if you use a block cipher as the encryption  
> mechanism. It becomes hopelessly insecure when you replace the block  
> cipher with RC4 or any other stream cipher.
>
>
> There are two distinct approaches to security protocol design. Most  
> of us tend to avoid any construction that they feel falls short of  
> the highest standards and might lead to a design oversight. I do not  
> use stream ciphers and I am going to avoid using CMAC. Other folk  
> sail closer to the wind, and there is certainly equipment out there  
> that can support stream ciphers but not block ciphers.
>
>
> I don't think this is an argument that is particularly worth having  
> unless it turns out that it is impossible to create a MAC function  
> from an encryption primitive that is also a strong one way function  
> or that doing so imposes an unacceptable performance cost.
>
AES-CMAC is a strong pseudorandom function, and a PRF is a good one- 
way function (being pseudorandom is harder than being one-way) (see  
"Improved security analyses for CBC MACs", for example).   Of course,  
it's one-way in terms of the key, but not in terms of the message.

David
>         Ugh, that kinda makes me not want to use CMAC construction  
> for a MAC function either. HMAC has the property that knowing the  
> key does not allow the output to be controlled, I am somewhat  
> surprised it was not considered a necessary property for a MAC.
>
> just a MAC.  One rule of thumb for telling the difference would be  
> to look at the output size of HMAC.
>
> David
>
>
>
>         We have plenty of experience of problems coming from people  
> using a stream cipher to do the work of a block cipher. Those  
> problems are the result of having what are actually two primitives  
> that are closely related enough to be considered equivalent but with  
> one offering only a subset of the security guarantees of the other.
>
>
>         We have a strong cryptographic primitive here, a cipher  
> function. Seems to me that if we do the job right it should be  
> possible to create a strong one way function. I know Rogaway has  
> argued that building everything on a one way function gives provable  
> security. Problem is that one way functions have been the most  
> troublesome function in practice. It is the only symmetric function  
> which we have had standard algorithms broken through cryptanalytic  
> attack, and not just once, we have had MD2, MD4 and MD5 broken and  
> SHA1 is making us worried.
>
>         The problem for the strategy outlined is that it kinda  
> depends on having a digest function that is fully certified right  
> now. We can use the same strategy to use SHA256 or SHA512 as an  
> insurance policy. But we can't fix CMAC and certify the result  
> before the digest competition reads out.
>
>
>         I still like the idea of using a keyed digest function with  
> a randomly chosen key as a digest. We should not be talking about  
> ways to add randomness into the object being signed as protection.  
> If we want randomness it should be input to the cryptographic layer  
> and be - random.
>
>         I know that in an ideal world a digest function should be  
> secure and not need some kind of backup, but given the experience of  
> digest functions being the most likely to fail, I really like having  
> the insurance of being able to add in the randomness.
>
>

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Fri, 9 Jan 2009 08:02:28 -0800

I am not sure that there are many prototcols where truncation takes place, apart from IPSEC and similar transport layer security I can't think of a good reason to do that. And in the case of IPSEC the practical use of the protocol is a very small subset of the original design intent.
 
Given the previous experience of security breaches that have occured when a substitution of this type takes place without a full reconsideration of the security requirements of the protocol, my preference would be to avoid CMAC-AES for any purpose.

Sent: Thu 1/8/2009 12:57 PM

Phillip, 

	
	
	Cryptographers have no business assuming that particular information is or is not available to an attacker.

that's not right.  Cryptographers use models and definitions that determine what information is available to an attacker.  See, for example, Section 2.1 of "Keying Hash Functions for Message Authentication", the main reference for HMAC.  These precise models and definitions are a major part of modern cryptography.

	That is my prerogative as a protocol designer. Only a protocol can determine if information is secret or not.

You're overstating this.  In what case can AES-CMAC not replace HMAC-SHA1 when the length of the ICV is truncated to 96 bits?  

Perhaps I would understand your point better if you could describe an example of a use of HMAC that is motivating your concern.

	

AES-CMAC is a strong pseudorandom function, and a PRF is a good one-way function (being pseudorandom is harder than being one-way) (see "Improved security analyses for CBC MACs", for example).   Of course, it's one-way in terms of the key, but not in terms of the message.  

David

	-----Original Message-----
	From: David McGrew [mailto:[email-masked]]
	Sent: Thu 1/8/2009 10:44 AM
	To: Hallam-Baker, Phillip
	Cc: David Jacobson; [email-masked]; Robert Moskowitz
	Subject: Re: [Cfrg] Analyzing IETF use of hash functions -- ORCHIDs
	
	Hi Phillip,

	

	       

	David

	       

	        -----Original Message-----
	       
	        [snip]

	       

	       

	           -- David Jacobson

	

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: David McGrew <[email-masked]>
Date: Fri, 9 Jan 2009 10:17:39 -0800

Hi Phillip,

On Jan 9, 2009, at 8:02 AM, Hallam-Baker, Phillip wrote:

> I am not sure that there are many prototcols where truncation takes  
> place, apart from IPSEC and similar transport layer security I can't  
> think of a good reason to do that. And in the case of IPSEC the  
> practical use of the protocol is a very small subset of the original  
> design intent.
>
> Given the previous experience of security breaches that have occured  
> when a substitution of this type takes place without a full  
> reconsideration of the security requirements of the protocol, my  
> preference would be to avoid CMAC-AES for any purpose.
>

I strongly disagree; security wise, CMAC is well suited for use as a  
MAC in ESP, IKE, SRTP, TLS, SSH, TCP-AO, and other protocols.  CMAC is  
a peer-reviewed variant of CBC-MAC, and that mode of operation may be  
the one that has seen the most formal analysis - at least three  
different proof-of-security methods have been presented in the  
literature (first Bellare, Killian, and Rogaway, then Bernstein, then  
Bellare, Pietrzak, Rogaway).  Also note that XCBC-MAC (see RFC 3566)  
has identical security properties to CMAC, and that the authentication  
properties of AES-CCM are similar.

David

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Fri, 9 Jan 2009 12:21:59 -0800

What is the use of a proof of security if it does not cover every security property that might be expected?
 
An algorithm can be acceptable for use without being a member of the prefered set. Identifying the fact that there is a defect with the CMAC formation when applied in certain situations is the starting point for replacing it with a better one.
 
There are many people looking at randomized hashing generally. We need a MAC function that can be used for randomized hashing that is not composed using a questionable primitive. So having a construction that is unencumbered, can perform all the functions of CMAC and in addition support random hashing would be useful.
 
Preferably with full proofs of security.

From: David McGrew [mailto:[email-masked]]
Sent: Fri 1/9/2009 1:17 PM
To: Hallam-Baker, Phillip
Cc: David Jacobson; [email-masked]; Robert Moskowitz
Subject: suitability of AES-CMAC (was: Re: [Cfrg] Analyzing IETF use of hash functions -- ORCHIDs)

Hi Phillip, 

	 

I strongly disagree; security wise, CMAC is well suited for use as a MAC in ESP, IKE, SRTP, TLS, SSH, TCP-AO, and other protocols.  CMAC is a peer-reviewed variant of CBC-MAC, and that mode of operation may be the one that has seen the most formal analysis - at least three different proof-of-security methods have been presented in the literature (first Bellare, Killian, and Rogaway, then Bernstein, then Bellare, Pietrzak, Rogaway).  Also note that XCBC-MAC (see RFC 3566) has identical security properties to CMAC, and that the authentication properties of AES-CCM are similar.

David

---

From: "Hal Finney" <[email-masked]>
Date: Fri, 9 Jan 2009 12:30:38 -0800

Isn't the issue you are talking about collision resistance? You want it to
be hard to create two messages with the same MAC. Unfortunately this is not
a standard security property for MACs.

Hal Finney

On Jan 9, 2009 12:22 PM, "Hallam-Baker, Phillip" <[email-masked]>
wrote:

 What is the use of a proof of security if it does not cover every security
property that might be expected?

An algorithm can be acceptable for use without being a member of the
prefered set. Identifying the fact that there is a defect with the CMAC
formation when applied in certain situations is the starting point for
replacing it with a better one.

There are many people looking at randomized hashing generally. We need a MAC
function that can be used for randomized hashing that is not composed using
a questionable primitive. So having a construction that is unencumbered, can
perform all the functions of CMAC and in addition support random hashing
would be useful.

------------------------------
*From:* David McGrew [mailto:[email-masked]]
*Sent:* Fri 1/9/2009 1:17 PM
*To:* Hallam-Baker, Phillip
*Cc:* David Jacobson; [email-masked]; Robert Moskowitz
*Subject:* suitability of AES-CMAC (was: Re: [Cfrg] Analyzing IETF use of
hash functions -- ORCHIDs)

Hi Phillip, On Jan 9, 2009, at 8:02 AM, Hallam-Baker, Phillip wrote: > I am
not sure that there ar...

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Fri, 9 Jan 2009 12:33:49 -0800

You think you know how to create a collision in HMAC? How about HTTP Digest?
 
It was a concern in HTTP digest because I knew that there was a risk that the construction would be reused in other circumstances where collision resistance might have been an issue.

From: Hal Finney [mailto:[email-masked]]
Sent: Fri 1/9/2009 3:30 PM
To: Hallam-Baker, Phillip
Cc: [email-masked]; David McGrew; Robert Moskowitz
Subject: Re: [Cfrg] suitability of AES-CMAC (was: Re: Analyzing IETF use of hash functions -- ORCHIDs)

Isn't the issue you are talking about collision resistance? You want it to be hard to create two messages with the same MAC. Unfortunately this is not a standard security property for MACs.

Hal Finney

	On Jan 9, 2009 12:22 PM, "Hallam-Baker, Phillip" <[email-masked]> wrote:

	 

	Hi Phillip, On Jan 9, 2009, at 8:02 AM, Hallam-Baker, Phillip wrote: > I am not sure that there ar...

---

From: Ken Raeburn <[email-masked]>
Date: Fri, 9 Jan 2009 16:47:30 -0500

On Jan 9, 2009, at 15:21, Hallam-Baker, Phillip wrote:
> What is the use of a proof of security if it does not cover every  
> security property that might be expected?

If there's one thing clear in this discussion, it's that different  
people have different ideas of which security properties might be  
expected, or even what properties would be considered "security  
properties"; one person's "security property" may be another's  
"vulnerability".  It's kind of hard to prove that an algorithm has  
properties you haven't thought of.

> Identifying the fact that there is a defect with the CMAC formation  
> when applied in certain situations is the starting point for  

All the hammers at my local hardware store seem particularly ill- 
suited to the task of brushing my teeth.  Clearly, this is a defect  
with the design of the hammers, no one should use these defective  
devices for any purposes, and they should be replaced with better  
ones. :-)

> There are many people looking at randomized hashing generally. We  
> need a MAC function that can be used for randomized hashing that is  
> not composed using a questionable primitive. So having a  
> construction that is unencumbered, can perform all the functions of  
> CMAC and in addition support random hashing would be useful.

One might be able to build a hybrid hammer-toothbrush.  That doesn't  
mean it's a good idea to insist that people shouldn't use a  
traditional hammer for the tasks it's good for, or a traditional  
toothbrush for the tasks it's good for.

Ken

---

From: David McGrew <[email-masked]>
Date: Fri, 9 Jan 2009 14:05:05 -0800

Phillip,

On Jan 9, 2009, at 12:21 PM, Hallam-Baker, Phillip wrote:

> prefered set. Identifying the fact that there is a defect with the  
> CMAC formation when applied in certain situations is the starting  
> point for replacing it with a better one.

It is completely unfair to CMAC to claim that it is defective because  
it doesn't meet your goal.   It is like condemning a knife because it  
makes a poor spoon.  How many MACs meet that goal?    None of the MACs  
based on block cipher modes or universal hashing do.

> not composed using a questionable primitive.

The randomized hashing that I'm aware of (RMX mode of Halevi and  
Krawczyk, as in draft-irtf-cfrg-rhash-01.txt) uses a hash, not a  
MAC.   If there is a random hash proposal based on a MAC, can you  
please send out a reference to it?

> So having a construction that is unencumbered, can perform all the  
> functions of CMAC and in addition support random hashing would be  
> useful.
>

Your position on proofs of security seems convoluted.  Above you  
dismiss the proofs for the vast majority of MACs since they don't  
include the additional property that you're looking for.  For that  
matter, is there *any* MAC for which there is a published analysis  
showing that the MAC has the property that you want?    Do HMAC-MD5 or  
HMAC-SHA1 have that property?

It is unreasonable to expect that all MACs should meet this new  
criterion that you are proposing.  The property that you want is not a  
natural extension of the MAC model, but rather something more like  
collision resistance, as Hal pointed out.

David

>> place, apart from IPSEC and similar transport layer security I  
>> can't think of a good reason to do that. And in the case of IPSEC  
>> the practical use of the protocol is a very small subset of the  
>> original design intent.
>>
>> Given the previous experience of security breaches that have  
>> occured when a substitution of this type takes place without a full  
> MAC in ESP, IKE, SRTP, TLS, SSH, TCP-AO, and other protocols.  CMAC  
> is a peer-reviewed variant of CBC-MAC, and that mode of operation  
> may be the one that has seen the most formal analysis - at least  
> three different proof-of-security methods have been presented in the  
> literature (first Bellare, Killian, and Rogaway, then Bernstein,  
> then Bellare, Pietrzak, Rogaway).  Also note that XCBC-MAC (see RFC  
> 3566) has identical security properties to CMAC, and that the  
> authentication properties of AES-CCM are similar.
>
> David

---

From: "John Wilkinson" <[email-masked]>
Date: Fri, 9 Jan 2009 17:17:47 -0500

> You think you know how to create a collision in HMAC? How about HTTP Digest?

No, I'm sure I don't. However, collision resistance is not generally
accepted as a required property for a MAC; the fact that HMAC *may*
have collision resistance is an artifact of it being constructed from
primitive functions that were designed to be collision resistant (but
aren't, in the cases of MD5 and SHA-1).

HMAC has been proven to be a secure PRF (and therefore a secure MAC)
only when the key is kept secret. It has *no* useful provable
properties (that I am aware of) when used with a public "key" in a
randomized hashing scheme as you suggest. This was part of the
motivation for the RMX randomized hashing mode David refers to.
_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: David Wagner <[email-masked]>
Date: Fri, 9 Jan 2009 14:26:22 -0800 (PST)

[My earlier email seems to have been dropped by the list.
I'll try again.]

>preference would be to avoid CMAC-AES for any purpose.

Well, I guess I disagree.  I'll lay out my reasoning.

It sounds like you've been surprised to have discover that CMAC-AES is
not secure in a mode of use that it was not designed for and was never
claimed to be secure for, and this surprise has shaken your confidence in
CMAC-AES.  I'm not sure that's logical.  The root cause of your surprise
seems to be a misunderstanding of the security properties that CMAC-AES
was claimed to have, not an unexpected security failure of CMAC-AES.
I suspect that everyone who understands CMAC-AES, the security theorem
for CMAC-AES, and the distinction between a MAC, PRF, and random oracle
should not be surprised in the least by the properties of CMAC-AES.

Once upon a time, we sometimes used to design protocols and throw in
hashes without thinking deeply about what purpose they serve.  Today,
we understand that it is helpful to think more carefully what purpose
each primitive is serving and what security properties we need it
to have.  Does it need to be a secure PRF?  a MAC?  a random oracle?
CMAC-AES is a perfectly good PRF or MAC; it's a lousy random oracle.
As long as you understand that, and think carefully during protocol
design whether you need a PRF vs a random oracle, then you're fine.
Don't send a CMAC-AES to do a random oracle's job, but it's perfectly
fine where a PRF or MAC is needed.

One might even be able to make an argument that CMAC-AES is a better
choice than MD5-HMAC or SHA1-HMAC for new designs where a MAC or PRF
is needed.  It's plausible that we should have higher confidence in the
security of CMAC-AES (as a PRF) than MD5-HMAC or SHA1-HMAC (as a PRF).
AES was designed to be a secure PRP, and we have confidence that it
meets this goal.  In contrast, our confidence in MD5 and SHA1 have been
somewhat shaken, and while we don't have a strong reason to expect this
to affect MD5-HMAC or SHA1-HMAC, it's also true that we don't have a
security reduction proof for HMAC that reduces its security to some
property about MD5 or SHA1 that we have high confidence of (to the same
degree as we have confidence in AES's security as a PRP).

Personally I think a policy of avoiding CMAC-AES for any purpose is
not warranted.  I think rather than criticizing CMAC-AES, you should
criticize protocol designers who use primitives in a way that violates
their security warranty and that there is no reason to expect them to
be secure in.  Just my opinion.
_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Fri, 9 Jan 2009 14:28:36 -0800

Again, this is an existing property of HMAC and of keyed digest formations in general.
 
So the analogy is inappropriate. 
 
A better analogy would be a toothbrush that explodes if you attempt to use it for the purpose of cleaning electronic equipment. Yes, that may not be the generally expected use of the tool, but that particular tool is commonly used for that purpose.
 
Yes we can all make an issue appear to look ridiculous by choosing an inappropriate analogy.

From: Ken Raeburn [mailto:[email-masked]]
Sent: Fri 1/9/2009 4:47 PM
To: Hallam-Baker, Phillip
Cc: [email-masked]
Subject: Re: [Cfrg] suitability of AES-CMAC (was: Re: Analyzing IETF use of hash functions -- ORCHIDs)

Ken

---

From: David Wagner <[email-masked]>
Date: Fri, 9 Jan 2009 14:30:06 -0800 (PST)

[My earlier email seems to have been dropped by this list.
I'm not sure why.  Perhaps the list moderators could take a
look and whitelist whatever email address of mine the list
doesn't like.]

>security property that might be expected?

Huh?  What a peculiar question.

The purpose of a proof of security is to identify a set of security
properties that the primitive does have.  In this way protocol designers
are supposed to use the security theorem to determine their expectations:
typically, it's reasonable to assume that a primitive has the security
properties promised by the theorem but unreasonable to expect it to
have other properties not proven.  Any protocol designer who expects
a "provably secure" primitive to have a security property that is not
guaranteed by any security theorem and that has not been carefully vetted
by the community, is skating on thin ice and has no right to use the
proof of security to justify his/her use of that primitive.

This is basic stuff.  Surely I've misunderstood you.

>Identifying the fact that there is a defect with the CMAC

Nonsense.  It's a starting point for educating people about the
proper use of security primitives.  But I suspect that qualified
cryptographers already know this well.

>We need a
>MAC function that can be used for randomized hashing [..]

I do not see the relevance to the question of whether CMAC is safe to
use in protocols that require a secure MAC.  CMAC is perfectly fine
when the security protocol needs a MAC (with no further properties).
Of course if a security protocol needs a primitive that is both a MAC
and also simultaneously has other security properties, then that becomes
a different question that has to be studied separately.  Of course if a
protocol designer is using a generic MAC when the protocol's security
requires the MAC to have other non-standard properties, and if the
protocol designer is unaware of this, then the protocol designer has
done a poor job of protocol design.
_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Fri, 9 Jan 2009 14:52:12 -0800

The problem with your approach is that it is predicated on people doing the right thing and understanding what they are doing.
 
In the real world things break because most people do not know what they are doing - and that includes academics who are purportedly expert in their field..
 
Reference to formal approaches does not give me any more confidence here. My thesis was on the use of formal methods, my college tutor was Tony Hoare. I know the value of that approach, I also know the failure modes. In particular formal methods very frequently break precisely because the requirements were not fully explained to the designer.

The conclusion I reach here is that it is not possible to take a random protocol and substitute CMAC for HMAC without going through a full security analysis. I don't think anyone is disputing that.
 
Where we disagree is that you think that this is likely to happen and I suspect it rather likely that it will not.

There is no formal necessity for many security properties of cryptographic algorithms. There is no formal requirement for zero-knowledge as far as I am aware. But if it is cheap and it is on offer I will take it. Having a MAC function that is also a random oracle is better than having one that merely supports the minimum criteria for being a MAC.

From: [email-masked] on behalf of David Wagner
Sent: Fri 1/9/2009 5:26 PM
To: [email-masked]
Subject: [Cfrg] Analyzing IETF use of hash functions -- ORCHIDs

---

From: David Wagner <[email-masked]>
Date: Fri, 9 Jan 2009 15:35:54 -0800 (PST)

> The conclusion I reach here is that it is not possible to take a random
> protocol and substitute CMAC for HMAC without going through a full
> security analysis. I don't think anyone is disputing that.

I would suggest that a more appropriate lesson to draw might be:

  If someone proposes to replace HMAC with CMAC in a particular
  protocol, feel free to go ahead and ask them for evidence that
  the protocol only needs a MAC or a PRF and does not rely upon
  any other properties of HMAC.  Ask to see their security analysis.

For newly designed protocols that use a MAC, I would suggest
something more along the lines of:

  Feel free to go ahead and ask the protocol designer for evidence
  that the protocol is not assuming anything more than the standard
  properties of the MAC.  Ask to see their security analysis.

It seems reasonable to ask for the security analysis and to request
CFRG to weigh in about whether the security analysis is persuasive.
But a conclusion that "we must avoid all use of AES-CMAC" seems
unwarranted and too inflexible to me.

> There is no formal necessity for many security properties of
> cryptographic algorithms. There is no formal requirement for
> zero-knowledge as far as I am aware. But if it is cheap and it is on
> offer I will take it. Having a MAC function that is also a random oracle
> is better than having one that merely supports the minimum criteria for
> being a MAC.

OK.  I have no problem with taking this consideration into account.
But this does not support the inflexible "avoid AES-CMAC under all
circumstances" policy that I understood you to be advocating earlier.

Are you aware that MD5-HMAC is not a random oracle?  There are non-random
properties of MD5-HMAC that are not shared by a random oracle (e.g., if
the key is known, I believe it is feasible to find a pair of messages that
produce the same digest; a random oracle does not have this property).
Perhaps some would advocate that we eliminate all use of MD5-HMAC?
Is there a reason to single out AES-CMAC but not MD5-HMAC?

And, of course, it is known that neither MD5 nor SHA1 act like random
oracles (e.g., due to length-extension properties; even ignoring the
sophisticated collision-finding attacks).

P.S. I think I understood the gist of your message but I believe you
have misused the term "zero-knowledge"; that has a precise meaning in
the cryptographic literature which seems inapplicable here.

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 9 Jan 2009 18:39:59 -0500

Phil,

If we knew how to build a cryptographic primitive that could be plugged in
for all cryptographic purposes we would be very happy. But so far we have
had a hard time even designing things that are much less ambitious and are
tailored to more modest goals (such as collision resistance).

As you mention in the msg below, what you really want is a "random oracle",
but these are mathematical abstractions useful in the analysis of protocols
but not something we can really build. It is better to accept our
limitations and be conscious of what roles each cryptographic primitive and
function can offer. This does not make things easy for the engineer that is
not a crypto expert but telling that engineer that we have a fully
multi-purpse constructs would be cheating. Fortunately, we have standards
that engineers can follow. The best we can do is to design these standards
with good cryptographic expertise and with as much rationale as possible.

Even though I have some "personal feelings" for HMAC, I have worked very
hard in many instances to make sure that HMAC is NOT wired in into protocols
as a magic function. The fact that you have acronyms such as "PRF" and "MAC"
in ipsec and TLS follows this view. Call your component by a name that
represents its functionality not by a specifc implementation.

Now, regarding your original post that wanted to use CMAC as a randomized
hashing algorithm: You were disappointed by the limitations of CMAC for this
(and other) purposes. You seem to find HMAC more versatile but
(unfortunately) HMAC is not a great candidate for randomizing a hash
function for the purpose of countering collision attacks. As it was already
pointed out in this thread, it was this realization that motivated building
a special purpose mechanism that does have the required properties.

I guess that you are familiar with the randomized hashing work presented in
http://tools.ietf.org/html/draft-irtf-cfrg-rhash-01 and being standardized
by NIST
http://csrc.nist.gov/publications/drafts/800-106/2nd-Draft_SP800-106_July2008.pdf
.

Do you see any special reason why this mechanism would not fulfill your hash
randomization goals?

Hugo

On Fri, Jan 9, 2009 at 5:52 PM, Hallam-Baker, Phillip
<[email-masked]>wrote:

>  The problem with your approach is that it is predicated on people doing
> the right thing and understanding what they are doing.
>
> In the real world things break because most people do not know what they
> are doing - and that includes academics who are purportedly expert in their
> field..
>
> Reference to formal approaches does not give me any more confidence here.
> My thesis was on the use of formal methods, my college tutor was Tony Hoare.
> I know the value of that approach, I also know the failure modes. In
> particular formal methods very frequently break precisely because the
> requirements were not fully explained to the designer.
>
>
> protocol and substitute CMAC for HMAC without going through a full security
> analysis. I don't think anyone is disputing that.
>
> Where we disagree is that you think that this is likely to happen and I
> suspect it rather likely that it will not.
>
>
> There is no formal necessity for many security properties of cryptographic
> algorithms. There is no formal requirement for zero-knowledge as far as I am
> aware. But if it is cheap and it is on offer I will take it. Having a MAC
> function that is also a random oracle is better than having one that merely
> supports the minimum criteria for being a MAC.
>
> *From:* [email-masked] on behalf of David Wagner
> *Sent:* Fri 1/9/2009 5:26 PM
> *To:* [email-masked]
> *Subject:* [Cfrg] Analyzing IETF use of hash functions -- ORCHIDs
>

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Fri, 9 Jan 2009 16:09:12 -0800

The problem is PR.

Past experience of HMAC-SHA1 is that when any attack that might affect the security of SHA1 is raised, the security of HMAC-SHA1 may be called into question both by journalists and by competitor's salespersons whose product happens to use a different algorithm.

So while RMX-SHA256 might provide a perfectly adequate insurance policy for a defect in SHA256 on a technical level, it is not adequate on the PR level. And since that is a sales driver that is a significant consideration. 

Given that we are now onto our third mainstream digest function whose security has become questionable as a result of non-brute force attack, I would prefer to have an insurance policy based on a block cipher.

A secondary concern is to do with the way that process failures turn into security failures. If you operate anything on a sufficiently extended scale you are eventually going to see process failures. I have a habit of over-designing systems according to some tastes and building in contingency plans that most people tend to consider unnecessary precisely because I have been doing this long enough to have had recourse to them.

Murphy originally proposed his law because he recognized that the way to avoid such process failures was to avoid giving the option to do something wrong.

-----Original Message-----
From: [email-masked] on behalf of Hugo Krawczyk
Sent: Fri 1/9/2009 6:39 PM
To: Hallam-Baker, Phillip
Cc: [email-masked]
Subject: Re: [Cfrg] Analyzing IETF use of hash functions -- ORCHIDs
 
Phil,
 
If we knew how to build a cryptographic primitive that could be plugged in for all cryptographic purposes we would be very happy. But so far we have had a hard time even designing things that are much less ambitious and are tailored to more modest goals (such as collision resistance).
 
As you mention in the msg below, what you really want is a "random oracle", but these are mathematical abstractions useful in the analysis of protocols but not something we can really build. It is better to accept our limitations and be conscious of what roles each cryptographic primitive and function can offer. This does not make things easy for the engineer that is not a crypto expert but telling that engineer that we have a fully multi-purpse constructs would be cheating. Fortunately, we have standards that engineers can follow. The best we can do is to design these standards with good cryptographic expertise and with as much rationale as possible.
 
Even though I have some "personal feelings" for HMAC, I have worked very hard in many instances to make sure that HMAC is NOT wired in into protocols as a magic function. The fact that you have acronyms such as "PRF" and "MAC" in ipsec and TLS follows this view. Call your component by a name that represents its functionality not by a specifc implementation.
 
Now, regarding your original post that wanted to use CMAC as a randomized hashing algorithm: You were disappointed by the limitations of CMAC for this (and other) purposes. You seem to find HMAC more versatile but (unfortunately) HMAC is not a great candidate for randomizing a hash function for the purpose of countering collision attacks. As it was already pointed out in this thread, it was this realization that motivated building a special purpose mechanism that does have the required properties.
 
I guess that you are familiar with the randomized hashing work presented in http://tools.ietf.org/html/draft-irtf-cfrg-rhash-01 and being standardized by NIST
http://csrc.nist.gov/publications/drafts/800-106/2nd-Draft_SP800-106_July2008.pdf.
 
Do you see any special reason why this mechanism would not fulfill your hash randomization goals?
 
Hugo

On Fri, Jan 9, 2009 at 5:52 PM, Hallam-Baker, Phillip <[email-masked]> wrote:

---

From: David McGrew <[email-masked]>
Date: Fri, 9 Jan 2009 16:11:12 -0800

On Jan 9, 2009, at 12:33 PM, Hallam-Baker, Phillip wrote:

> You think you know how to create a collision in HMAC?
>

sure, if I get to choose the hash function.  More seriously, if an  
attacker gets to choose the HMAC key, and the attacker can generate a  
collision in the underlying hash function, then the attacker can  
generate HMAC collisions by causing a collision in the inner  
invocation of the hash.  If the attacker doesn't get to choose the  
key, but can generate two inputs to the inner hash that have identical  
prefixes (at least as long as ipad) that cause a collision in the  
hash, then the attacker can find collisions in HMAC.   As you know,  
the details for HMAC-MD5 and HMAC-SHA1 will depend on the adversary's  
resources and on what control if any the attacker has over the HMAC  
key in your security model.

David

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 9 Jan 2009 19:18:11 -0500

Phil,

I understand the PR issues. But we also have to take care of the real
security issues. Saying we tried a solution based on block ciphers maybe a
PR sttaement but probably not very useful to achieve real security. Note
that you have to be very careful here. If you add a randomization as a front
end to existing (or future) hash functions, which is the most practical way
to do it (in particular for compatibility reasons), you must be very careful
not to add collisions in that front end module. Using a block cipher with a
known key (this is necessary since your hash operation must be non-secret)
can easily lead to collisions. Thus, you may end with collisions due to
randomization even if your hash function is fully collision resistant.
So let's not ignore PR (a serious consideration in the secuity industry) but
let's not sacrifice actual security on the name of PR.

Hugo
On Fri, Jan 9, 2009 at 7:09 PM, Hallam-Baker, Phillip
<[email-masked]>wrote:

>  The problem is PR.
>
> Past experience of HMAC-SHA1 is that when any attack that might affect the
> security of SHA1 is raised, the security of HMAC-SHA1 may be called into
> question both by journalists and by competitor's salespersons whose product
> happens to use a different algorithm.
>
> So while RMX-SHA256 might provide a perfectly adequate insurance policy for
> a defect in SHA256 on a technical level, it is not adequate on the PR level.
> And since that is a sales driver that is a significant consideration.
>
>
> Given that we are now onto our third mainstream digest function whose
> security has become questionable as a result of non-brute force attack, I
> would prefer to have an insurance policy based on a block cipher.
>
>
> A secondary concern is to do with the way that process failures turn into
> security failures. If you operate anything on a sufficiently extended scale
> you are eventually going to see process failures. I have a habit of
> over-designing systems according to some tastes and building in contingency
> plans that most people tend to consider unnecessary precisely because I have
> been doing this long enough to have had recourse to them.
>
> Murphy originally proposed his law because he recognized that the way to
> avoid such process failures was to avoid giving the option to do something
> wrong.
>
>         The problem with your approach is that it is predicated on people
> doing the right thing and understanding what they are doing.
>
>         In the real world things break because most people do not know what
> they are doing - and that includes academics who are purportedly expert in
> their field..
>
>         Reference to formal approaches does not give me any more confidence
> here. My thesis was on the use of formal methods, my college tutor was Tony
> Hoare. I know the value of that approach, I also know the failure modes. In
>         The conclusion I reach here is that it is not possible to take a
> random protocol and substitute CMAC for HMAC without going through a full
>         Where we disagree is that you think that this is likely to happen
> and I suspect it rather likely that it will not.
>
>
> cryptographic algorithms. There is no formal requirement for zero-knowledge
> as far as I am aware. But if it is cheap and it is on offer I will take it.
> Having a MAC function that is also a random oracle is better than having one
> that merely supports the minimum criteria for being a MAC.
>
> can't
> occured

---

From: Greg Rose <[email-masked]>
Date: Fri, 9 Jan 2009 16:50:12 -0800

> aren't, in the cases of MD5 and SHA-1).

Interestingly, HMAC has less collision resistance than the underlying  
hash function, simply because you might get a collision in either the  
inner or outer hash, thus doubling its probability. So you basically  
lose one bit of collision resistance.

Greg.