Subject: Re: Do we need rfc 3161bis?

From: [email-masked]
Date: Tue, 17 Mar 2009 16:02:19 +0100

Stefan wrote his e-mail during a meeting where the priority is to listen to the meeting rather than sending e-mails.

I disagree with points 1 and 2. Point 6 is one way to move forwards, but is not the single way.

Denis

[email-masked] wrote: -----

To: Stefan Santesson <[email-masked]>, Jim Schaad <[email-masked]>, "'Santosh Chokhani'" <[email-masked]>, "'IETF-pkix'" <[email-masked]>
From: Stefan Santesson <[email-masked]>
Sent by: [email-masked]
Date: 03/17/2009 03:29PM
Subject: Re: Do we need rfc 3161bis?

I had an informal face2face meeting here in Barcelona between me, Julien Stern and Denis Pinkas.

I will dare myself to write down some conclusion and trust Julien and Denis to correct me if they disagree.

There is no known threat for which the essCertIDv2 is needed.
It is extremely hard to prove that there will not be any threat or attack made up in the future where essCertIDv2 would be useful
As essCertIDv2 is standardized and has been a focus for EU work in relation to time stamps, it is probably reasonable to allow essCertIDv2 to be used with RFC 3161 time stamps.
For the sake of specifying the time stamp protocol, we only need one named entity representing the signer of the time stamp token (currently TSA in RFC 3161).
There is currently a disconnect between terminology in RFC 3161 and RFC 3628 (the policy document)
A solution that would satisfy all parties of this meeting would be to write an update RFC (not a replacement as current proposal). This update RFC would add the option to use essCertIDv2 AND would include an informational Annex  explaining the basic difference in terminology between RFC 3161 and RFC 3628. Most importantly this informational text would explain that TSU in the policy document corresponds to TSA in the protocol.

I support these conclusions.

/Stefan

On 3/17/09 7:55 AM, "Stefan Santesson" <[email-masked]> wrote:

Exactly as Jim says. Maybe we should add further that this is a bout substituting one valid TSA certificate with another valid TSA certificate since the TSA for some reason has two TSA certificates for the same public key which when hashed, have the same SHA-1 hash.

/Stefan

On 3/17/09 6:26 AM, "Jim Schaad" <[email-masked]> wrote:

The attack we are looking at is a certificate substitution attack with the TSA certificate being changed to a different certificate.  This is not  question of trusting the TSA itself.  Unless of course it is the one trying the attack for some reason.

From: Santosh Chokhani [mailto:[email-masked]]
Sent: Monday, March 16, 2009 9:25 PM
To: Stefan Santesson; Jim Schaad; IETF-pkix
Subject: RE: Do we need rfc 3161bis?

I have not followed the thread well.  But, are we losing forest for the trees here?

Do we not trust the TSA enough to not create collision attack?

From: [email-masked] [mailto:[email-masked]] On Behalf Of Stefan Santesson
Sent: Monday, March 16, 2009 9:01 PM
To: Jim Schaad; 'IETF-pkix'
Subject: Re: Do we need rfc 3161bis?
OK,

The prefix attack only works, as you say yourself, on the tbs bits to create two certs with the same signature. This is ONLY possible if the signature hash algorithm is broken. The hash in the essCertID is calculated on the complete certificates (including signatures), not only the tbs bits.
Thus, the prefix attack is pretty useless if you have a large chunk of random bits in the end that is bound to be different for each cert. And they will be different IF the signature algorithm of the certificates is not broken.

The second question, sorry for missing it, is broader than just RFC 3161bis.

I think we have many protocols, where collision resistance is not an issue, where we don’t provide algorithm agility for all uses of SHA-1. I do think there is a use of SHA-1 in OCSP that is not part of the current update proposal and there is currently a similar discussion in TLS where strong arguments are raised against adding algorithm negotiation complexity when collision resistance is not a security issue. This problem is more political than technical. But if there is any reason to do this, it probably is for political reasons, so your point is valid.

/Stefan

On 3/17/09 1:20 AM, "Jim Schaad" <[email-masked]> wrote:
Stefan,

First I don’t know that I agree.  I think that the entirety of your protection is actually given by the leading sequence/length bytes.  The object is to prevent a prefix attack.  One can create a prefix attack against the TBS bytes – leading to identical signatures for both versions of the certificate.  However adding the leading sequence/length octets probably means that you need to have two different prefix attacks – a much harder condition, but maybe doable.

However I don’t believe that you addressed my second point at all.  That is people completely migrate away from SHA-1 because it is considered to be broken.

jim

From: Stefan Santesson [mailto:[email-masked]]
Sent: Monday, March 16, 2009 5:09 PM
To: Jim Schaad; 'IETF-pkix'
Subject: Re: Do we need rfc 3161bis?

Jim,

You ask,
The question becomes can I create two certificates that can have the same hash, NOT will it happen by chance.

I totally agree. And I don’t think you can.

Not if the two certificates are signed with a good signature algorithm.
If these certificates are signed with a bad signature algorithm that allows different certificates to share the same signature, then all bets are off anyway.

If the signature algorithms are good, then the signatures of these certificates will be composed of a substantial amount of vastly different bits. As the signature algorithm is good, you can’t control the bits of these signatures in any meaningful way, leaving you basically with a trial and error approach. That even if SHA-1 is broken.

/Stefan

On 3/16/09 8:17 PM, "Jim Schaad" <[email-masked]> wrote:
Stefan,

The property that is being used is not the randomness property, it is a collision property.  (Or more specifically resistance to collisions.)   The question becomes can I create two certificates that can have the same hash, NOT will it happen by chance.   If I can do so then I have a successful attack at this point.

However one needs to assume that if SHA-1 is significantly broken, people will be removing it from the trusted algorithm list and would then need a migration path of what to put in place of the current SHA-1 attribute.  This is the main reason for doing the update.

jim

From: [email-masked] [mailto:[email-masked]] On Behalf Of Stefan Santesson
Sent: Saturday, March 14, 2009 5:54 PM
To: Jim Schaad; 'IETF-pkix'
Subject: Re: Do we need rfc 3161bis?

Yes, a good question indeed.

Say that SHA-1 is completely broken in the sense that we can produce collisions at will, of all sorts and forms.
Say also that we have a few valid TSA certificates issued for the same key pair, signed using good hash algorithms (or else all bets are off anyway).

The randomness properties of SHA-1 will remain intact even if SHA-1 is broken. This means that the risk/chance that two valid certificates, signed with safe signature algorithms, will by chance produce collisions, is still totally negligible.

Where am I thinking wrong here?

/Stefan

On 3/14/09 8:00 PM, "Jim Schaad" <[email-masked]> wrote:
Stefan,

The question you need to be asking is – Do you believe that SHA-1 will be broken one day, and if it is broken do you want to have in place a solution to deal with it.

Jim

From: [email-masked] [mailto:[email-masked]] On Behalf Of Stefan Santesson
Sent: Saturday, March 14, 2009 7:06 AM
To: IETF-pkix
Subject: Do we need rfc 3161bis?

The more I look into this the more I get to doubt that we actually need 3161bis.

The only substantial technical change I know of is to allow the updated ESS certIDv2 to be used to identify the signer’s certificate IF the TSA for some reason choose to hash its certificate with another hash then SHA-1.

The rationale for the certID identifier is given in section 5 of RFC 2634 and describes attacks where one valid certificate is substituted by another valid certificate (exceopt for some DoS case that I don’t think is relevant here).
Now I have to ask myself. How likely is it that a legitimate TSA has 2  or more legitimate certificates for the same public key with conflicting information (or information different enough to actually have a security impact) AND where the hash of these certificates produce a SHA-1 collision.

This is not the previously discussed certificate collision attack using weak certificate signing hash, where I may prepare a certificate request in a way where I can fool the CA to produce two valid certificates with the same certificate signature. If I would use that technique I would have to find a way to prepare the TSA certificate requests, the TSA certificate hash need to be weak in addition to the certID hash AND In addition to that the complete certificates (not only the to be signed part) need to create a hash collision when computing the certID.

So, my first question is if this change addresses any real security threat?
Can someone provide a reasonable threat analysis?
And consequently, if there are no real threats to solve, does this update motivate the potential interoperability issues that might be the result of by allowing ESS CertIDv2 in time stamp tokens?

If we do come to the conclusion that it is worth it, then why not just create an update RFC updating RFC 3161 instead of replacing it?

This update does not change any bits on the wire for implementations of the current protocol. The only thing it does is to add an option to use ESS certIDv2 IF SHA-1 is not used as hash to identify the TSA’s certificate.
This seems like a perfect thing for an update RFC. Another argument is that the old editors that rightfully should have the credit for RFC 3161 are not part of this minor amendment but are completely erased from the update. That may be reasonable if the changes are major but I’m not so sure in this case.

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 17 Mar 2009 18:06:13 +0100

Denis,

On your first remark    :D

On your second remark:
Good, even that level of agreement is a great step forward. I think 1 and 2
was more an agreement between me and Julien. But since the conclusion is to
allow essCertIDv2, point 1 and 2 is of less importance.

/Stefan

On 3/17/09 4:02 PM, "[email-masked]" <[email-masked]> wrote:

> Stefan wrote his e-mail during a meeting where the priority is to listen to
> the meeting rather than sending e-mails
> 
>  
> To: Stefan Santesson <[email-masked]>, Jim Schaad
> <[email-masked]>, "'Santosh Chokhani'" <[email-masked]>,
> "'IETF-pkix'" <[email-masked]>
> 1. There is no known threat for which the essCertIDv2 is needed.
> 2. It is extremely hard to prove that there will not be any threat or attack
> made up in the future where essCertIDv2 would be useful
> 3. As essCertIDv2 is standardized and has been a focus for EU work in relation
> to time stamps, it is probably reasonable to allow essCertIDv2 to be used with
> RFC 3161 time stamps.
> 4. For the sake of specifying the time stamp protocol, we only need one named
> entity representing the signer of the time stamp token (currently TSA in RFC
> 3161). 
> 5. There is currently a disconnect between terminology in RFC 3161 and RFC
> 3628 (the policy document)
> 6. A solution that would satisfy all parties of this meeting would be to write
> an update RFC (not a replacement as current proposal). This update RFC would
> add the option to use essCertIDv2 AND would include an informational Annex
> explaining the basic difference in terminology between RFC 3161 and RFC 3628.
> Most importantly this informational text would explain that TSU in the policy
> document corresponds to TSA in the protocol.
> 
>> Exactly as Jim says. Maybe we should add further that this is a bout
>> substituting one valid TSA certificate with another valid TSA certificate
>> since the TSA for some reason has two TSA certificates for the same public
>> key which when hashed, have the same SHA-1 hash.
>> 
>> /Stefan
>> 
>> 
>>> The attack we are looking at is a certificate substitution attack with the
>>> TSA certificate being changed to a different certificate.  This is not
>>> question of trusting the TSA itself.  Unless of course it is the one trying
>>> the attack for some reason.
>>>  
>>>  
>>> 
>>>> The prefix attack only works, as you say yourself, on the tbs bits to
>>>> create two certs with the same signature. This is ONLY possible if the
>>>> signature hash algorithm is broken. The hash in the essCertID is calculated
>>>> on the complete certificates (including signatures), not only the tbs bits.
>>>> Thus, the prefix attack is pretty useless if you have a large chunk of
>>>> random bits in the end that is bound to be different for each cert. And
>>>> they will be different IF the signature algorithm of the certificates is
>>>> not broken.
>>>> 
>>>> I think we have many protocols, where collision resistance is not an issue,
>>>> where we don¹t provide algorithm agility for all uses of SHA-1. I do think
>>>> there is a use of SHA-1 in OCSP that is not part of the current update
>>>> proposal and there is currently a similar discussion in TLS where strong
>>>> arguments are raised against adding algorithm negotiation complexity when
>>>> collision resistance is not a security issue. This problem is more
>>>> political than technical. But if there is any reason to do this, it
>>>> probably is for political reasons, so your point is valid.
>>>> 
>>>> /Stefan
>>>> 
>>>> First I don¹t know that I agree.  I think that the entirety of your
>>>> protection is actually given by the leading sequence/length bytes.  The
>>>> object is to prevent a prefix attack.  One can create a prefix attack
>>>> against the TBS bytes  leading to identical signatures for both versions
>>>> of the certificate.  However adding the leading sequence/length octets
>>>> probably means that you need to have two different prefix attacks  a much
>>>> harder condition, but maybe doable.
>>>>  
>>>> However I don¹t believe that you addressed my second point at all.  That is
>>>> people completely migrate away from SHA-1 because it is considered to be
>>>> broken.
>>>>  
>>>> jim
>>>>  
>>>> 
>>>> I totally agree. And I don¹t think you can.
>>>> 
>>>> If these certificates are signed with a bad signature algorithm that allows
>>>> different certificates to share the same signature, then all bets are off
>>>> anyway.
>>>> 
>>>> If the signature algorithms are good, then the signatures of these
>>>> certificates will be composed of a substantial amount of vastly different
>>>> bits. As the signature algorithm is good, you can¹t control the bits of
>>>> these signatures in any meaningful way, leaving you basically with a trial
>>>> and error approach. That even if SHA-1 is broken.
>>>> 
>>>> /Stefan
>>>> 
>>>> 
>>>> The property that is being used is not the randomness property, it is a
>>>> collision property.  (Or more specifically resistance to collisions.)   The
>>>> question becomes can I create two certificates that can have the same hash,
>>>> NOT will it happen by chance.   If I can do so then I have a successful
>>>> attack at this point.
>>>>  
>>>> However one needs to assume that if SHA-1 is significantly broken, people
>>>> will be removing it from the trusted algorithm list and would then need a
>>>> migration path of what to put in place of the current SHA-1 attribute.
>>>> This is the main reason for doing the update.
>>>>  
>>>> jim
>>>>  
>>>> 
>>>> Say that SHA-1 is completely broken in the sense that we can produce
>>>> collisions at will, of all sorts and forms.
>>>> Say also that we have a few valid TSA certificates issued for the same key
>>>> pair, signed using good hash algorithms (or else all bets are off anyway).
>>>> 
>>>> The randomness properties of SHA-1 will remain intact even if SHA-1 is
>>>> broken. This means that the risk/chance that two valid certificates, signed
>>>> with safe signature algorithms, will by chance produce collisions, is still
>>>> totally negligible.
>>>> 
>>>> The question you need to be asking is  Do you believe that SHA-1 will be
>>>> broken one day, and if it is broken do you want to have in place a solution
>>>> to deal with it.
>>>>  
>>>> Jim
>>>>  
>>>>  
>>>> 
>>>> The only substantial technical change I know of is to allow the updated ESS
>>>> certIDv2 to be used to identify the signer¹s certificate IF the TSA for
>>>> some reason choose to hash its certificate with another hash then SHA-1.
>>>> 
>>>> The rationale for the certID identifier is given in section 5 of RFC 2634
>>>> and describes attacks where one valid certificate is substituted by another
>>>> valid certificate (exceopt for some DoS case that I don¹t think is relevant
>>>> here).
>>>> Now I have to ask myself. How likely is it that a legitimate TSA has 2  or
>>>> more legitimate certificates for the same public key with conflicting
>>>> information (or information different enough to actually have a security
>>>> impact) AND where the hash of these certificates produce a SHA-1 collision.
>>>> 
>>>> This is not the previously discussed certificate collision attack using
>>>> weak certificate signing hash, where I may prepare a certificate request in
>>>> a way where I can fool the CA to produce two valid certificates with the
>>>> same certificate signature. If I would use that technique I would have to
>>>> find a way to prepare the TSA certificate requests, the TSA certificate
>>>> hash need to be weak in addition to the certID hash AND In addition to that
>>>> the complete certificates (not only the to be signed part) need to create a
>>>> hash collision when computing the certID.
>>>> 
>>>> And consequently, if there are no real threats to solve, does this update
>>>> motivate the potential interoperability issues that might be the result of
>>>> by allowing ESS CertIDv2 in time stamp tokens?
>>>> 
>>>> 
>>>> If we do come to the conclusion that it is worth it, then why not just
>>>> create an update RFC updating RFC 3161 instead of replacing it?
>>>> 
>>>> This update does not change any bits on the wire for implementations of the
>>>> current protocol. The only thing it does is to add an option to use ESS
>>>> certIDv2 IF SHA-1 is not used as hash to identify the TSA¹s certificate.
>>>> This seems like a perfect thing for an update RFC. Another argument is that
>>>> the old editors that rightfully should have the credit for RFC 3161 are not
>>>> part of this minor amendment but are completely erased from the update.
>>>> That may be reasonable if the changes are major but I¹m not so sure in this
>>>> case.
>>>> 
>>>>