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

From: "Denis Pinkas" <[email-masked]>
Date: Thu, 5 Oct 2006 17:55:48 +0200

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

Thanks for the explanations.

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

Some of the goals you mention are incompatibe with the following requirement:
"current applications shall continue to work without any change".

If the definition of a certificate had been based on CMS, the last requirement 
could have been met. However, this is not the case.

Every PKI should have a Disaster Recovey Plan ready, in particular in case 
a given algorithm or key length is broken. This does not mean that this can only be obtained 
by changing the format of certificates, CRLs and so on.

A few year ago (december 2001), I proposed to work on the topic and even drafted a document.
I asked for a co-editor, but none volunteered.

Should there now be an interrest, a volonteer co-editor and should a work item be adopted on the topic 
by the WG, then (and only then) I would be happy to re-issue the draft.

The title was:  Key Compromise, Rollover and Loss
 
The abstract was:

   This document presents a framework to assist the writers of policy 
   or practice statements and the designers of a Public Key 
   Infrastructure to prepare disaster recovery plans in case of a
   private key compromise or a private key loss. This may happen to 
   end-user keys, Certification Authorities, Revocation Authorities, 
   Attribute Authorities, Time Stamping Authorities. Since keys do not 
   last for ever, key rollover is should be planned in advance and 
   some guidance is necessary. In addition, the case of the denial of 
   service attacks on Repositories holding certificates and/or CRLs 
   has also to be considered. The framework provides a comprehensive 
   list of potential key compromise or key loss conditions that 
   (at the writer's discretion) should be addressed so that it is 
   possible to nicely recover from situations which normally should 
   not happen, but might happen.
 
Denis

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

Regards,

Denis Pinkas

---

From: Arshad Noor <[email-masked]>
Date: Thu, 05 Oct 2006 11:39:20 -0700

Denis,

I will volunteer to be your co-editor on this topic; please
contact me off-line to discuss this.  Thanks.

Arshad Noor
StrongAuth, Inc.

---

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

On Thursday 05 October 2006 16:55, Denis Pinkas 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.
> >
> >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.
> >
> >  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.
> Some of the goals you mention are incompatibe with the following
> requirement: "current applications shall continue to work without any
> change".

That's where my idea comes in.  By putting additional hashes (generated by a 
variety of hash algorithms) into a non-critical Certificate Extension, and by 
requiring (or at least recommending) new software to check *all* of these 
additional hashes, I believe that we could accomplish all of these goals.

Each certificate's signature would continue to be generated using 
sha1WithRSAEncryption, allowing current applications to continue to work 
without any code changes.  These current applications would simply ignore the 
non-critical "Additional Hashes" Certificate Extension.

If SHA-1 is ever sufficiently compromised, then we can expect attackers to 
create fake certificates using sha1WithRSAEncryption signatures from valid 
certificates.  My hope is that new software would be able to detect and 
reject these fake certificates, simply by checking all of the hashes in 
the "Additional Hashes" extension.

Do you think my idea is worth considering at all?

> If the definition of a certificate had been based on CMS, the last
> requirement could have been met. However, this is not the case.

Agreed.  If CMS (PKCS#7) had been used as the basis of X.509, my idea would be 
completely redundant.

> a given algorithm or key length is broken. This does not mean that this can
> only be obtained by changing the format of certificates, CRLs and so on.
>
> A few year ago (december 2001), I proposed to work on the topic and even
> drafted a document. I asked for a co-editor, but none volunteered.
>
> Should there now be an interrest, a volonteer co-editor and should a work
> item be adopted on the topic by the WG, then (and only then) I would be
> happy to re-issue the draft.
>
> >> > 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.
> >> > 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...
> >> >
> >> >> i'd consider the signature algorithm OID before I would state that
> >> >> x.509 has no algorithm agility
> >> >>
> >> >>     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
> >> >>         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.
> >> >>
> >> >> algorithm OID, the practice from the days of PKCS has been that each
> >> >> OID identifies a specific combination.
> >> >>
> >> >>      hoyt
> >> >>
> >> >>
> >> >>  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.
> >> >>  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.
> >> >>      A. Create the "to be signed" certificate (as per the CA's
> >> >> existing process).
> >> >> 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.
> >> >> 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
> >> >>    - 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
> >
> >--
> >Rob Stradling
> >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.
>
> Regards,
>
> Denis Pinkas

---

From: Joel Kazin <[email-masked]>
Date: Fri, 06 Oct 2006 12:38:44 -0400

I am also volunteering for this topic as it is part of CP and CPS 
development.

Arshad Noor wrote:

>> Should there now be an interrest, a volonteer co-editor and should a 
>> work item be adopted on the topic by the WG, then (and only then) I 
>> would be happy to re-issue the draft.
>>
>>    Attribute Authorities, Time Stamping Authorities. Since keys do 
>> not    last for ever, key rollover is should be planned in advance 
>> and    some guidance is necessary. In addition, the case of the 
>> denial of    service attacks on Repositories holding certificates 
>> and/or CRLs    has also to be considered. The framework provides a 
>> comprehensive    list of potential key compromise or key loss 
>> conditions that    (at the writer's discretion) should be addressed 
>> so that it is    possible to nicely recover from situations which 
>> normally should    not happen, but might happen.
>>  
>
>
>
>