Subject: Re: Algorithm revocation

From: "Tom Gindin" <[email-masked]>
Date: Mon, 19 Feb 2001 18:37:20 -0500

On the "Algorithm revocation" concept, while an RP would probably not
always want to rely on a CA's ideas about which algorithms are unsafe, at
least it would allow a CA to notify RP software which predates an algorithm
compromise and isn't configurable for a list of weakened algorithms that it
has reason to believe that some algorithm is weakened.  This idea is
actually more useful in having a CA which is a trusted root for some users
impose a constraint on CA's it has cross-certified than it is in simply
avoiding individual revocations, since a CA is expected to perform such
revocations as needed whether issuing a large number of revocations is
costly or not.
     If you're going to provide revocation facilities for an algorithm in
this way, wouldn't it be better to allow for the possibility that an
algorithm is revoked for certain key lengths and not for others (e.g.,
RSA-512 may be broken while RSA-2048 is not)?  If this is indeed a
reasonable idea, revokedAlgorithms would be a CRL extension (not a CRL
entry extension) with approximately the following syntax:

RevokedAlgorithmsSyntax ::= SEQUENCE OF CompromisedAlgorithm
CompromisedAlgorithm ::= SEQUENCE {
      signatureAlgorithm      AlgorithmIdentifier,
      minimumSafeKeyBits INTEGER DEFAULT 1000000000,  -- or any very large
number
     -- would a combination of { KeyUsage flag, Size } be more useful?
      revocationDate     Time,
      explanatoryText    UTF8String OPTIONAL
}
     I don't see the point of having entry extensions inside
revokedAlgorithms, nor do I see any need to extend the base CRL structure
for them.  The criticality of this extension as a whole is a matter of
opinion.
     On multiple signatures, is it really wise to encourage the inclusion
of multiple CMS SignerInfo's or equivalents as an extension to an OCSP
responses?  I know that there are some non-repudiation situations where
this might be of slightly greater use than having the RP choose its desired
signature algorithm using a requestExtension, while being more efficient
than asking for the same answer multiple times with such an extension and
getting multiple identical response bodies with different signatures.
However, signed timestamp pyramiding ought to protect against later
compromises of algorithms which are not believed to be questionable at the
time of the OCSP check.

          Tom Gindin

Sönke Maseberg <[email-masked]> on 02/19/2001 04:27:48 PM

To:   pkix <[email-masked]>
cc:
Subject:  multiple digitale signatures

Hello,

we are working at the problem, that it couldn't be excluded that one
component of a public key infrastructure can be compromised, since no
proofable secure signature algorithm or hash function exists.

For example nowadays the hash functions SHA-1 or RIPEMD-160 and the
signature algorithms RSA with 1024 bit or ECDSA with 160 bit keylength
are qualified for cryptographic purposes. The public key cryptograpy is
based on mathematical problems which are supposed to be hard to solve,
but it is not known for sure. If a failure occurs the security of the
PKI could not be guaranteed any longer as a whole, this means the
electronic communication may be insecure.

That is the reason why we develop a public key infrastructure which will
keep its functionality in the case of failure and which is able to be
repaired and where generated digital signatures won't lose their
proofability.

As a basic restriction the technical components must be integrated in
the PKI in such a flexible manner, that an exchange could be possible.
The flexible public key infrastructure which is developed at the chair
of Professor Buchmann of the Technical University of Darmstadt/Germany
in the "FlexiPKI" project is following this philosophy.

The main idea is to build up a public key infrastructure upon several
independent cryptographic components, where in the case, one component
is compromised the other components still can be used to:
- Exchange the compromised component securely
- Sign electronic documents multiple (concept of multiple digital
signatures)

To support standards of PKIX, we ask for some discussions about our
ideas and extensions:

1. multiple digital signatures

We want to use multiple digital signatures, that are digital signatures
generated of independent signature algorithms, for example RSA with
SHA-1 and ECDSA with RIPEMD-160. PKCS#7 supports those signatures. But
we would  like to extend OCSP responses [RFC 2560] and CRLs (Certificate
and CRL Profile) [<draft-ietf-pkix-new-part1-04.txt>] with multiple
digital signatures in the following manner:

OCSP response:

   BasicOCSPResponse  ::=  SEQUENCE {
      tbsResponseData       ResponseData,
      signatureAlgorithm    AlgorithmIdentifier,
      signature             BIT STRING,
      certs                 [0]  EXPLICIT SEQUENCE OF Certificate
OPTIONAL,
      additionalsignatures  [1]  SEQUENCE OF SEQUENCE {        --
EXTENSION
           signatureAlgorithm         AlgorithmIdentifier,
           signature                  BIT STRING }
           }  OPTIONAL
      }

CRL:

   CertificateList  ::=  SEQUENCE  {
      tbsCertList            TBSCertList,
      signatureAlgorithm     AlgorithmIdentifier,
      signatureValue         BIT STRING,
      additionalsignatures   SEQUENCE OF SEQUENCE {           --
EXTENSION
         signatureAlgorithm     AlgorithmIdentifier,
         signatureValue         BIT STRING
         }  OPTIONAL
      }

2. revoked algorithms

If a signature algorithms is compromised, all certificates have to be
revoked. But the number of those certificates can be very large, so we
would like to revoke an algorithm. For this reason we propose the
following extension of CRL (Certificate and CRL Profile)
[<draft-ietf-pkix-new-part1-04.txt>]:

   TBSCertList  ::=  SEQUENCE  {
      version                Version OPTIONAL,
      signature              SEQUENCE OF AlgorithmIdentifier,  --
EXTENSION
      issuer                 Name,
      thisUpdate             Time,
      nextUpdate             Time OPTIONAL,
      revokedCertificates    SEQUENCE OF SEQUENCE  {
         userCertificate        CertificateSerialNumber,
         revocationDate         Time,
         crlEntryExtensions     Extensions OPTIONAL
         }  OPTIONAL,
      crlExtensions          [0]  EXPLICIT Extensions OPTIONAL,
      revokedAlgorithms      [1]  SEQUENCE OF SEQUENCE {       --
EXTENSION
         signatureAlgorithm          AlgorithmIdentifier,
         revocationDate              Time,
         crlEntryExtensions          Extensions OPTIONAL
         }  OPTIONAL
      }

What do you think about it?

Thanks in advance,
Sönke

---

Sönke Maseberg       GMD - Institut für Sichere Telekooperation
Dipl.-Math.          Rheinstr. 75, D-64295 Darmstadt
                     Tel: 06151/869-60036, Fax: 06151/869-224

                     Technische Universität Darmstadt
                     Institut fuer Theoretische Informatik
                     Lehrstuhl Prof. J. Buchmann
                     Alexanderstr. 10, D-64283 Darmstadt

---

From: Soenke Maseberg <[email-masked]>
Date: Tue, 20 Feb 2001 14:36:26 +0100

Hi.

> for them.  The criticality of this extension as a whole is a matter of

minimumSafeKeyBits is a good idea. But I think, revokedAlgorithms is at the
same level as revokedCertificates.
What about the following extensions of Certificate and CRL Profile)
[<draft-ietf-pkix-new-part1-04.txt>]?

      additionalsignatures   SEQUENCE OF SEQUENCE {           --EXTENSION

  TBSCertList  ::=  SEQUENCE  {
      version                Version OPTIONAL,
      signature              SEQUENCE OF AlgorithmIdentifier,  --  EXTENSION
      issuer                 Name,
      thisUpdate             Time,
      nextUpdate             Time OPTIONAL,
      revokedCertificates    SEQUENCE OF SEQUENCE  {
         userCertificate        CertificateSerialNumber,
         revocationDate         Time,
         crlEntryExtensions     Extensions OPTIONAL
         }  OPTIONAL,
      crlExtensions          [0]  EXPLICIT Extensions OPTIONAL,
      revokedAlgorithms      [1]  SEQUENCE OF CompromisedAlgorithm
OPTIONAL      -- EXTENSION
      }

   CompromisedAlgorithm ::= SEQUENCE {
      signatureAlgorithm      AlgorithmIdentifier,
      minimumSafeKeyBits      INTEGER DEFAULT 1000000000,  -- or any very
large number
                           -- would a combination of { KeyUsage flag, Size }
be more useful?
      revocationDate          Time,
      explanatoryText         UTF8String OPTIONAL
      }

> compromises of algorithms which are not believed to be questionable at the

The problem of timestamps occurs if they uses the compromised signature
algorithm too.

Regards,
Sönke

---

Sönke Maseberg
Dipl.-Math.

GMD - Institut für Sichere Telekooperation
Rheinstr. 75, D-64295 Darmstadt
Tel: 06151/869-60036, Fax: 06151/869-224

---

From: Stephen Kent <[email-masked]>
Date: Tue, 20 Feb 2001 18:33:36 -0500

Soenke,

While I am sympathetic to the concern that motivated the suggestion 
of revoking an algorithm, I think the list discussion has pointed out 
pitfalls with the proposed approach. Fundamentally, a decision to 
accept or reject use of algorithm is more an RP issue that a CA 
revocation issue.  I am less sympathetic to the proposed dual 
signature proposal for PKI data structures, including your specific 
OCSP example. Use of multiple signatures are appropriate in some 
application contexts, but have been explored and rejected in X.509 
infrastructure data elements, e.g., certs & CRLs, long ago.

Steve

---

From: Sönke Maseberg <[email-masked]>
Date: Wed, 21 Feb 2001 11:00:38 +0100

Steve,

I would like to quote 'PKIX Roadmap- March 10, 2000'
[<draft-ietf-pkix-roadmap-05.txt>], part 3.5.6.2. Key Compromise

 In the case of a key compromise, the transition will not be
 "graceful" in that there will be an unplanned switch of PKCs and
 keys; users will not have known in advance what was about to happen.
 Still, the PKI must support the ability to declare that the previous
 PKC is now invalid and shall not be used, and to announce the
 validity and availability of the new PKC.

 Note: compromise of a private key associated with a Root CA is
 catastrophic for users relying on that Root CA. If a Root CA's
 private key is compromised, that CA's PKC must be revoked and all
 PKCs subordinate to it must also be revoked. Until such time as the
 Root CA has been issued a new PKC and the Root CA issues PKCs to
 users relying upon it, users relying on that Root CA are cut off
 from the rest of the system, as there is no way to develop a valid
 certification path back to a trusted node.

 Further, users will likely have to be notified by out-of-band
 mechanisms about the change in CA keys. [...]

To avoid these out-of-band mechanisms IMO multiply-signed CRLs or OCSP
responses are necessary.

Sönke

---

From: Stephen Kent <[email-masked]>
Date: Wed, 21 Feb 2001 21:03:41 -0500

Sönke,

>To avoid these out-of-band mechanisms IMO multiply-signed CRLs or OCSP

As Graham noted, the text here refers to private key compromise, not 
to what you have termed algorithm compromise (definitely not a 
standard term). Also, as Graham noted, algorithm compromises for 
widely deployed, well analyzed algorithms have not been sudden 
events. So, while one might argue for multiple signatures on CRLs and 
OCSP responses to address this concern, it seems rather late in the 
game to make such substantial changes for what appears to be a very 
low likelihood event.

Steve

---

From: Joerg Seidel <[email-masked]>
Date: Thu, 22 Feb 2001 13:43:11 +0100

Hi,

> The problem of timestamps occurs if they uses the compromised signature

timestamp should be logged for this reason. This avoids the problems with the
signature algorithm.

Jörg
-- 
__________________________________________________________________

Jörg Seidel                             phone  +49-40-76629-1911
Director Technology                     fax    +49-40-76629-551
timeproof GmbH                          
Harburger Schloßstraße 6-12             mailto:[email-masked]
DE 21079 Hamburg                        http://www.timeproof.de
__________________________________________________________________

---

From: Sönke Maseberg <[email-masked]>
Date: Fri, 23 Feb 2001 10:12:44 +0100

Joerg,

IMO logging transfers the problem only. How do you protect the logged data? With
breaking of the media ('Medien-Bruch')?

Sönke

---

From: Joerg Seidel <[email-masked]>
Date: Fri, 23 Feb 2001 11:59:17 +0100

Soenke,

Sönke Maseberg wrote:
> > timestamp should be logged for this reason. This avoids the problems with
> > the signature algorithm.
> >
> IMO logging transfers the problem only. How do you protect the logged data?
> With breaking of the media ('Medien-Bruch')?

It is an additional security layer. Logged data can be secured by securing the
access, by using WORM devices and/or by using interlinked lists. If you would
like to have a secure system, you would better not relay on security feature
(eg. digital signature) but use other independent security measures.

If one of the layers fails the other can help...

Joerg

---

From: [email-masked]
Date: Tue, 27 Feb 2001 10:52:03 +0100 (MET)

> If one of the layers fails the other can help...

Our proposal follows the same paradigm, I think. 

Soenke