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

From: Rob Stradling <[email-masked]>
Date: Tue, 3 Oct 2006 15:35:51 +0100

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

---

From: Rob Stradling <[email-masked]>
Date: Wed, 4 Oct 2006 11:26:02 +0100

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.
>  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.
>      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):
>    - 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".