Subject: Do we need rfc 3161bis?

From: Stefan Santesson <[email-masked]>
Date: Sat, 14 Mar 2009 15:05:54 +0100

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: "Jim Schaad" <[email-masked]>
Date: Sat, 14 Mar 2009 12:00:43 -0700

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 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.

valid certificate (exceopt for some DoS case that I don't think is relevant

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: Sun, 15 Mar 2009 01:53:49 +0100

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
>  
>  
> 
> 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).
> 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.
> 
> 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?
>

---

From: Peter Sylvester <[email-masked]>
Date: Sun, 15 Mar 2009 09:46:01 +0100

What would be the impact, if a timestamp would not contain
a signingCertficate in the signed attributes?

- A TSA could extend the lifetime of its TSA certificate by
  getting another with a different validity period?

- The CA goes out of business, the CA cert gets revoked somehow;
  the TSA can get a replacement certificate with the same
  public key by another CA, so timestamps can still be
  verified,

... bad idea? Any security problem? I don't want to start
a discussion about long term verifiability (vs validity
of a timestamp).

The 10 years old EU directive concerning  signatures do
require that the signatary is clearly identified. This is
sufficiently fulfilled by the 'tsa' field in the time stamp.

Another point:

Most time stamp clients, if not all, verify that the timestamp
contains an essSigningCertficate. a v2 thus cannot simply
replace it without a risk that a client would not be able to
verify. The following piece of 3161bis may be problematic.

   The time-stamp token MUST NOT contain any signatures other than the
   signature of the TSA.  The certificate identifier (either ESSCertID 
   or ESSCertIDv2) of the TSU certificate MUST be included as a 
   signerInfo attribute inside a SigningCertificate attribute.

   Note: As mentioned in RFC 5035 [ESSV2], the SigningCertificateV2 
         attribute MUST be used if any algorithm other than SHA-1 
         is used and SHOULD NOT be used for SHA-1

A TSA that starts using V2 after 3161bis publication would
be probably unable to produce verifiable time stamps for
many clients.

In fact, it restricts the possibilities of a TSA, which today can
set both attributs.

Peter

---

From: Stefan Santesson <[email-masked]>
Date: Sun, 15 Mar 2009 12:31:02 +0100

Peter, 

If we were designing the time stamp protocol from scratch today, I would
probably argue that it is unnecessary to bind the signer's certificate to
the time stamp token, or at least to make that optional.

In most security services/protocols (such as OCSP) we do not bother to bind
the signer's certificate to the signed data. In the general case the relying
party is the one who reasonably relies on the signature and is therefore
responsible for deciding if the certificate used to validate the signature
is adequate for that trust decision.

But since we already have 3161 out there, unless implementers and users have
huge problems with it. I would not change anything.

In all other aspects I agree.

/Stefan

---

From: Peter Sylvester <[email-masked]>
Date: Sun, 15 Mar 2009 14:26:33 +0100

> is adequate for that trust decision.
The "name of responder" is bound to the signature, as part
of the OCSP response similar to tsaName. Using essSigningCertficate
was overkill, but well, I am not asking to remove it.

If some update woul be necessary, I would rather remove the
MUST that requires a client to validate essSigningCert. IMO
tsaName match is sufficient.

At least one known public domain client
also verifies that the asserted date lies
in the validity period of the certificate. I am
not sure whether this is good.
> huge problems with it. I would not change anything.
clarification and maybe simplifications that don't break interoperability
may be possible. The eesSigncert stuff is not in this category I think/

> In all other aspects I agree.
/P

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 16 Mar 2009 12:17:25 -0700

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?

/Stefan

Stefan,

Jim

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 17 Mar 2009 01:08:45 +0100

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:

> 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
>  
> 
> 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.
>

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 16 Mar 2009 17:20:06 -0700

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,

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

bits. As the signature algorithm is good, you can't control the bits of

/Stefan

Stefan,

 
jim

/Stefan

 
Jim

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 17 Mar 2009 02:00:30 +0100

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
> 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
> 
>

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 17 Mar 2009 00:24:50 -0400

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

		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

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

		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?

		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.

		/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: "Jim Schaad" <[email-masked]>
Date: Mon, 16 Mar 2009 22:26:43 -0700

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?

  _____  

OK,

where we don't provide algorithm agility for all uses of SHA-1. I do think

/Stefan

Stefan,

 
jim

Jim,

You ask,

/Stefan

 
 
jim

/Stefan

 
Jim

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 17 Mar 2009 07:55:03 +0100

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.
>  
>  
> 
> I have not followed the thread well.  But, are we losing forest for the trees
> here?
>  
>> 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.
>> 
>> First I don¹t know that I agree.  I think that the entirety of your
>> 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
>> signatures in any meaningful way, leaving you basically with a trial and
>> error approach. That even if SHA-1 is broken.
>> 
>> /Stefan
>> 
>>

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 17 Mar 2009 15:29:57 +0100

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.

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.

I support these conclusions.

/Stefan

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

> 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
> 
> 
>>> against the TBS bytes  leading to identical signatures for both versions of