Subject: Re: Hash Algorithm Agility via Certificate/CRL/OCSP Extensions

From: "Denis Pinkas" <[email-masked]>
Date: Wed, 4 Oct 2006 17:14:12 +0200

Rob,

Before describing a technical solution, it would be nice to explain in details 
what the problem you want to solve is.

Denis

>Hi Hoyt.
>
>Maybe I'm not using the word "agility" correctly.  My aim was to find a way to 
>include *multiple* hashes (with each hash generated by a different hash 
>algorithm) in a *single* Certificate/CRL/etc, so that we no longer have to 
>rely on the strength of a single hash algorithm.
>
>PKCS#1 defines various AlgorithmIdentifiers for digital 
>signatures: "sha1WithRSAEncryption", "sha256WithRSAEncryption", etc.  Each of 
>these is for 1 hash algorithm and 1 encryption algorithm.
>PKCS#1 does not define anything like "sha1AndSha256WithRSAEncryption" (i.e. 2 
>or more hash algorithms and 1 encryption algorithm).
>
>We could of course define new {SupportedAlgorithms} OIDs 
>for "sha1AndSha256WithRSAEncryption", "sha1AndSha512WithRSAEncryption", etc, 
>but no existing software would recognize these.
>
>I'm not saying that my "Additional Hashes" Extension idea is a particularly 
>clean solution from a purist's point of view.  It would be best if there was 
>a way for all of the algorithm identifiers/signatures/hashes to continue to 
>be stored in the "standard" X.509 places (Certificate->signature, etc).
>
>But the problem is...
>
>The definition of Certificate->signature, which we can't change, is...
>         signature                            AlgorithmIdentifier,
>...rather than...
>         signature                            SEQUENCE OF AlgorithmIdentifier,
>
>...and the definition of SIGNED, which we can't change, is...
>SIGNED { ToBeSigned } ::= SEQUENCE {
>         toBeSigned                         ToBeSigned,
>         COMPONENTS OF            SIGNATURE { ToBeSigned }}
>...rather than something like...
>SIGNED { ToBeSigned } ::= SEQUENCE {
>         toBeSigned                         ToBeSigned,
>         SEQUENCE OF                  SIGNATURE { ToBeSigned }}
>
>I hope this post clarifies where I was coming from with the "Advantages 
>(IMHO)" from my previous post.
>
>-- 
>Rob Stradling
>Comodo CA Limited
>
>On Tuesday 03 October 2006 16:49, you wrote:
>> i'd consider the signature algorithm OID before I would state that x.509
>> has no algorithm agility
>>
>>         Certificate   ::=       SIGNED { SEQUENCE {
>>         version                 [0]     Version DEFAULT v1,
>>         serialNumber                    CertificateSerialNumber,
>>         signature                               AlgorithmIdentifier,
>>         issuer                          Name,
>>         validity                                Validity,
>>         subject                         Name,
>>         subjectPublicKeyInfo            SubjectPublicKeyInfo,
>>     issuerUniqueIdentifier  [1]     IMPLICIT UniqueIdentifier OPTIONAL,
>>                                                                      
>>         -- if present, version shall be v2 or v3 subjectUniqueIdentifier
>> [2]     IMPLICIT UniqueIdentifier OPTIONAL, -- if present, version shall be
>> v2 or v3 extensions              [3]     Extensions OPTIONAL
>>                                                                        
>>         -- If present, version shall be v3 -- } }
>>
>>         Version                 ::=             INTEGER { v1(0), v2(1),
>> v3(2) } CertificateSerialNumber ::=             INTEGER
>>         AlgorithmIdentifier             ::=             SEQUENCE {
>>         algorithm               ALGORITHM.&id ({SupportedAlgorithms}),
>>         parameters   ALGORITHM.&Type ({SupportedAlgorithms}{ @algorithm})
>> OPTIONAL }
>>
>> I assume you meant to say that the list of OIDs for agreed combinations of
>> hash algorithms, encryption algorithms, and key lengths needs to be
>> expanded.
>>
>> Note that although 509 allows parameters to be associated with an algorithm
>> OID, the practice from the days of PKCS has been that each OID identifies a
>> specific combination.
>>
>>      hoyt
>>
>>
>> Hi.  I'm new to this list, so please forgive me if the following idea has
>> been aired before, or if better ideas are already under discussion...
>>
>>  As http://www3.ietf.org/proceedings/06mar/slides/pkix-1/sld3.htm points
>> out, X.509 certificates have no algorithm agility.  This breaks down into 3
>> areas: 1. A certificate only contains 1 public key (which will almost
>> certainly only be useable with 1 particular asymmetric encryption
>> algorithm). 2. Only 1 CA private key (and 1 asymmetric encryption
>> algorithm) is used to generate a certificate's signature.
>>    3. Only 1 hash algorithm is used to generate a certificate's signature.
>>
>>  I don't want to address areas 1 and 2 here, but I have an idea for adding
>> some agility to area 3...
>>
>>  I suggest that we define an "Additional Hashes" Certificate Extension. 
>> This Extension would contain 1 or more hashes, generated using different
>> hash algorithm(s) to the hash algorithm used in the generation of the
>>  certificate's signature.
>>  To issue a certificate, a CA would need to do something like this:
>>      A. Create the "to be signed" certificate (as per the CA's existing
>>  process).
>>      B. Generate the SHA-256 hash of the "to be signed" certificate.
>>      C. Put the SHA-256 hash from Step B into an "Additional Hashes"
>> extension, and add that extension to the "to be signed" certificate from
>> step A. D. Sign the "to be signed" certificate from step C using SHA-1 as
>> the hash algorithm for the signature.
>>  Relying parties would then be able to verify all (or as many as they can)
>> of the hashes.  Future software could choose to reject certificates that
>> don't contain an "Additional Hashes" extension with enough different hash
>> algorithms represented.
>>
>>  Advantages (IMHO):
>>    - We would be able to start using SHA-256/384/512 immediately.  :-)
>>    - Various bodies are recommending phasing out SHA-1 in the very near
>> future (NIST say 2010, IIRC, but I'm sure I've also seen a reference to
>> 2008).  I think that my idea might be the only approach that could at least
>> "phase in" newer hash algorithms before these deadlines.  The "phase out"
>> of SHA-1 would become arguably less urgent and could take place at a later
>> time. - Backwards compatibility: new software would be able to take
>> advantage of multiple hashes to enhance their security; existing software
>> would continue to work as it does today (i.e. it would simply ignore the
>> "Additional Hashes" extension").  This is potentially a very useful
>> property, given that (IIRC) Microsoft have said that support for
>> SHA-256/384/512 will be added in Windows Vista, but not backported to older
>> versions of Windows.  I expect that many, many users will continue to use
>> Windows 2000/XP/etc well beyond 2008/2010, and will be quite happy to rely
>> on SHA-1 until such time as it is
>>  definitely "broken".
>>    - This same idea could also be used in CRLs, OCSP Requests and OCSP
>>  Responses, because they can all contain Extensions.
>>
>>  --
>>  Rob Stradling
>>  Comodo CA Limited
>

Regards,

Denis Pinkas

---

From: Rob Stradling <[email-masked]>
Date: Thu, 5 Oct 2006 16:24:43 +0100

Hi Denis.  I'll try again... :-)

Most currently valid X.509 certificates rely on the SHA-1 algorithm.  If/when 
SHA-1 gets sufficiently "broken", the signatures on those certificates will 
become worthless.  Some experts believe that SHA-1 might get broken really 
quite soon.
X.509 allows us to stop using SHA-1 and start using SHA-256 (or SHA-384, or 
SHA-512, etc) instead.  However, if we were to do this today, most existing 
software (including all versions of Windows prior to Vista...which isn't even 
launched yet) would not be able to verify the signatures on the certificates 
at all.

I want to be able to do *all* of the following (in no particular order)...
  1. Start using SHA-256/384/512/etc in X.509 certificates ASAP, so that the 
latest software can take advantage of these (hopefully) more secure hash 
algorithms.
  2. Avoid keeping SHA-1 as a single point of failure until such time as there 
is widespread support for SHA-256/384/512/etc.
  3. Stop having to rely on any single hash algorithm when verifying the 
signature of an X.509 Certificate.

I hope this explains my aims more clearly.

On Wednesday 04 October 2006 16:14, Denis Pinkas wrote:
> Rob,
>
> Before describing a technical solution, it would be nice to explain in
> details what the problem you want to solve is.
>
> Denis
>
> >Hi Hoyt.
> >
> >Maybe I'm not using the word "agility" correctly.  My aim was to find a
> > way to include *multiple* hashes (with each hash generated by a different
> > hash algorithm) in a *single* Certificate/CRL/etc, so that we no longer
> > have to rely on the strength of a single hash algorithm.
> >
> >signatures: "sha1WithRSAEncryption", "sha256WithRSAEncryption", etc.  Each
> > of these is for 1 hash algorithm and 1 encryption algorithm.
> >PKCS#1 does not define anything like "sha1AndSha256WithRSAEncryption"
> > (i.e. 2 or more hash algorithms and 1 encryption algorithm).
> >
> >for "sha1AndSha256WithRSAEncryption", "sha1AndSha512WithRSAEncryption",
> > etc, but no existing software would recognize these.
> >
> >I'm not saying that my "Additional Hashes" Extension idea is a
> > particularly clean solution from a purist's point of view.  It would be
> > best if there was a way for all of the algorithm
> > identifiers/signatures/hashes to continue to be stored in the "standard"
> > X.509 places (Certificate->signature, etc).
> >
> >But the problem is...
> >
> >> [2]     IMPLICIT UniqueIdentifier OPTIONAL, -- if present, version shall
> >> be v2 or v3 extensions              [3]     Extensions OPTIONAL
> >>                                                                        
> >>         parameters   ALGORITHM.&Type ({SupportedAlgorithms}{
> >> @algorithm}) OPTIONAL }
> >>
> >> I assume you meant to say that the list of OIDs for agreed combinations
> >> of hash algorithms, encryption algorithms, and key lengths needs to be
> >> expanded.
> >>
> >> Note that although 509 allows parameters to be associated with an
> >> algorithm OID, the practice from the days of PKCS has been that each OID
> >> identifies a specific combination.
> >>
> >>      hoyt
> >>
> >>
> >> Hi.  I'm new to this list, so please forgive me if the following idea
> >> has been aired before, or if better ideas are already under
> >> discussion...
> >>
> >> out, X.509 certificates have no algorithm agility.  This breaks down
> >> into 3 areas: 1. A certificate only contains 1 public key (which will
> >> almost certainly only be useable with 1 particular asymmetric encryption
> >>  I don't want to address areas 1 and 2 here, but I have an idea for
> >> adding some agility to area 3...
> >>
> >> step A. D. Sign the "to be signed" certificate from step C using SHA-1
> >> as the hash algorithm for the signature.
> >>  Relying parties would then be able to verify all (or as many as they
> >> can) of the hashes.  Future software could choose to reject certificates
> >> that don't contain an "Additional Hashes" extension with enough
> >> different hash algorithms represented.
> >>
> >>  Advantages (IMHO):
> >> 2008).  I think that my idea might be the only approach that could at
> >> least "phase in" newer hash algorithms before these deadlines.  The
> >> "phase out" of SHA-1 would become arguably less urgent and could take
> >> place at a later time. - Backwards compatibility: new software would be
> >> able to take advantage of multiple hashes to enhance their security;
> >> existing software would continue to work as it does today (i.e. it would
> >> simply ignore the "Additional Hashes" extension").  This is potentially
> >> a very useful property, given that (IIRC) Microsoft have said that
> >> support for SHA-256/384/512 will be added in Windows Vista, but not
> >> backported to older versions of Windows.  I expect that many, many users
> >> will continue to use Windows 2000/XP/etc well beyond 2008/2010, and will
> >> be quite happy to rely on SHA-1 until such time as it is
> >>  definitely "broken".

-- 
Rob Stradling
Digital Certification and Identity Management Solutions Manager - Comodo
Comodo - Creating Trust Online
Office Tel Europe: +44 (0) 1274 730505
Office Tel US: +1 888 COMODO 1   (1 888 266 6361)
Fax Europe: +44 (0) 1274 730909
Fax US: +1 201 963 9003
www.comodo.com, www.trustix.com, www.enterprisessl.com, 
www.contentverification.com
Join the online fax revolution! Send your faxes online with TrustFax 
www.TrustFax.com !

This e-mail and any files transmitted with it are confidential and intended
solely for the use of the individual or entity to whom they are addressed.
If you have received this email in error please notify the sender by replying
to the e-mail containing this attachment. Replies to this email may be
monitored by Comodo for operational or business reasons. Whilst every
endeavour is taken to ensure that e-mails are free from viruses, no liability
can be accepted and the recipient is requested to use their own virus checking
software.

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 5 Oct 2006 12:19:17 -0700

>become worthless.  Some experts believe that SHA-1 might get broken really

Sorry, but this is silly FUD. Please name one "expert" who believes 
that. None of the "experts" with whom I spoke at the second NIST hash 
workshop about a month ago expressed any such belief, and many of 
them said the opposite.

So far, the attacks on SHA-1 have been to reduce the collision 
resistance. No one has shown useful attacks on PKIX certs that can 
use the current attack methods, even if they get much better.

Everyone agrees that if the pre-image resistance of SHA-1 were to 
weaken to be within the work effort of an attacker, things would be 
quite grim for PKIX certificates. There have been literally zero 
published attacks that even suggest this is possible.

--Paul Hoffman, Director
--VPN Consortium

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 5 Oct 2006 14:45:20 -0700

At 11:27 AM -0800 10/5/06, Michael Myers wrote:
>Is it then your opinion that we should not take action with respect this
>thread's subject?

Not at all. However, it is unclear what action we should take in 
light of the recent attacks on the collision-resistance of popular 
hash functions. Four major routes that have been proposed are:

- to allow more than one hash algorithm (as proposed at the beginning 
of the thread)
- to use different signing algorithms that are immune to collision attacks
- to use a different hash function that is provably collision-resistant
- to do nothing but to encourage CAs to add randomness to their 
serial numbers to make collision attacks infeasible

Each proposal has its own value; each has its own cost. The first, 
second, and third require major retooling of the I part of PKI. The 
first is PKIX-specific; the second and third could be used in other 
protocols such as S/MIME. The third will require a fair amount of 
cryptographic research and publishing. The fourth costs nothing for 
retooling PKIX receivers and only a trivial amount for CAs, but it 
doesn't feel substantial.

Given that there are no viable attacks today, we might go with the 
least-cost option (the fourth) but consider the other three for the 
future.

--Paul Hoffman, Director
--VPN Consortium

---

From: "Michael Myers" <[email-masked]>
Date: Thu, 5 Oct 2006 11:27:57 -0800

Paul,

Is it then your opinion that we should not take action with respect this
thread's subject?  In particular amending RFC2560, as I had some time ago
proposed.

Mike

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of Paul Hoffman
Sent: Thursday, October 05, 2006 11:19 AM
To: [email-masked]
Subject: Re: Hash Algorithm Agility via Certificate/CRL/OCSP Extensions

--Paul Hoffman, Director
--VPN Consortium

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 5 Oct 2006 18:46:29 -0700

At 4:50 PM -0800 10/5/06, Michael Myers wrote:
>What I am reading is:
>
>1) These vulnerabilities continue to be theoretical;
>
>2) Modification to extant standards impacts the
>    installed base for no apparent value; and thus
>
>3) Until or unless theory proves true, let us not
>    as a standards body change the status quo.
>
>A fair reading?

Kind of, but missing some important points.

1) There are no known practical attacks on PKIX certificates based on 
collision-reduction attacks on hashes;

2) Modification to extant standards impacts the installed base and 
therefore should, if undertaken, get the most long-term value for the 
least disruption (yes, that is weighing two orthogonal and 
unmeasurable quantities...); and thus

3) Until or unless practical attacks can be specified, implement the 
things with essentially-zero costs and continue to try to measure and 
weigh long-term value and cost of disruption.

That's more long-winded, but over-simplifying could easily cause us 
to lurch or do too little.

--Paul Hoffman, Director
--VPN Consortium

---

From: "Michael Myers" <[email-masked]>
Date: Thu, 5 Oct 2006 16:50:20 -0800

Paul,

What I am reading is:

A fair reading?

Mike

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of Paul Hoffman
Sent: Thursday, October 05, 2006 1:45 PM
To: Michael Myers; [email-masked]
Subject: RE: Hash Algorithm Agility via Certificate/CRL/OCSP Extensions

--Paul Hoffman, Director
--VPN Consortium

---

From: Rob Stradling <[email-masked]>
Date: Fri, 6 Oct 2006 12:36:45 +0100

On Thursday 05 October 2006 20:19, Paul Hoffman wrote:
> >Most currently valid X.509 certificates rely on the SHA-1 algorithm. 
> > If/when SHA-1 gets sufficiently "broken", the signatures on those
> > certificates will become worthless.  Some experts believe that SHA-1
> > might get broken really quite soon.
>
> that.

Sorry Paul.  I completely withdraw my comments on how "broken" SHA-1 is, might 
soon be, or might ever be.  I am not an "expert" cryptographer.  I guess I 
was basing my comments on other peoples' FUD and my own assumptions / 
lack-of-understanding.  Please accept my apologies.

> None of the "experts" with whom I spoke at the second NIST hash

I'm very glad to hear this.  :-)

> use the current attack methods, even if they get much better.

I hadn't fully appreciated this before.  Thanks.

> published attacks that even suggest this is possible.

My purpose in starting this thread was definitely not to inadvertently spread 
FUD, but rather to propose a solution to a "quite grim" problem that *might* 
arise at some point in the future.
My proposed solution could be introduced without breaking compatibility with 
existing software (although existing software would not see any benefit), 
unlike all other proposed solutions I've seen.  This "backwards 
compatibility" angle is the primary reason I started this thread, because I 
thought there was some merit to it.

If SHA-1 will *definitely* remain suitable for digital signatures until such 
time as there is widespread support for SHA-256/512/etc, then my idea is 
arguably redundant.
But unless we can say "definitely", then I still think that my idea is worth 
considering.

---

From: Daniel Brown <[email-masked]>
Date: Fri, 6 Oct 2006 10:37:06 -0400

> Most currently valid X.509 certificates rely on the SHA-1 algorithm. 
If/when 

> I hope this explains my aims more clearly.

As I understand your proposal (please correct me as necessary), if M is 
the ToBeSigned - before your new SHA256 extension - a CA with RSA private 
key (n,d) would generate a signature essentially like

S = PKCS1(SHA1(M | SHA256(M)))^d mod n

That's a clever idea if it stops the known SHA1 attacks, but has it been 
carefully scrutinized against other attacks?  In particular, is some of 
the benefit of using SHA256 lost once it has gone through the SHA1 output 
(since 256 bits has been crunched to 160 bits).  For example, birthday 
attacks on SHA256 should take about 2^128 hashes, but with your 
construction birthday attacks should take about 2^81 hashes, which is 
certainly better than the 2^63 (the current SHA1 strength), but much worse 
than 2^128 (the current SHA256 strength).  Admittedly, these are rather 
theoretically high levels of security, which the very pragmatic PKIX group 
may not be terribly concerned about, but it leads me to question whether 
your objective 2 will be fully met.

Aside: Does the PKIX group feel that the paper "Colliding X.509 
Certificates" http://eprint.iacr.org/2005/067 is of no concern (assuming 
that it can eventually be extended to SHA1)?  (I've been getting that 
impression from various comments.)  If so, why?  Some possible reasons 
are: (1) pre-existing certs (issued before collision attack) are not 
affected and are still verifiable and usable, (2) when a collision attack 
is discovered, CAs can halt issuing certs and upgrade to a better hash. In 
particular, these reasons make it seems that PKIX can afford to wait until 
the very last minute, i.e. when SHA1 is actually broken, rather than to 
upgrade to some fix like SHA256 before SHA1 is broken.  If new hashes such 
as SHA256 are ready to go, then that should be enough preparation for the 
least amount of downtime during the upgrade.  Older implementations will 
not be able to process the new certs, though.   My concern with a 
last-minute approach is that perhaps somebody will use the collision 
attacks before a CA becomes aware of it?  Is there some other good reason 
that I should not have this concern?  For example, is there something else 
about the "Colliding X.509 Certs" paper that means it will not be useful 
for a realistic attack.

Thanks,

Dan Brown
(905) 501-3857
http://www.certicom.com

---

From: Rob Stradling <[email-masked]>
Date: Fri, 6 Oct 2006 16:13:29 +0100

On Friday 06 October 2006 15:37, Daniel Brown wrote:
> ...
> ...

In essence, yes, that's my proposal.

> carefully scrutinized against other attacks?

Not by me.

> In particular, is some of 
> than 2^128 (the current SHA256 strength).

Thanks for your assessment on this.
It had occurred to me that this might be the case, but I'm a programmer rather 
than a cryptographer...and I'm not going to make any more wild 
speculations.  :-)

> Admittedly, these are rather 

I guess the obvious alteration to my proposal would be to define 
an "Additional Signatures" Certificate Extension rather than (or in addition 
to) an "Additional Hashes" extension.
Each additional signature would be generated by a different hash algorithm, 
but the same CA Private Key and asymmetric algorithm would be used for all of 
them.