Subject: multiple digitale signatures

From: Sönke Maseberg <[email-masked]>
Date: Mon, 19 Feb 2001 22:27:48 +0100

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: Juergen Brauckmann <[email-masked]>
Date: Tue, 20 Feb 2001 08:36:20 +0100

Hi.

> digital signatures in the following manner:

Why do you want to do that? If a client has an old OCSP response with an
expired algorithm, then the client could simply request a new OCSP
response.

If the old OCSP response is that important that you must reuse it, then
you may use timestamps.

I think it would be a big performance burden on the OCSP responder if it
would be forced to sign the response multiple times.

Regards,
   Juergen

---

From: Soenke Maseberg <[email-masked]>
Date: Tue, 20 Feb 2001 13:53:22 +0100

Hi Juergen.

> expired algorithm, then the client could simply request a new OCSP

How do the CA (certification authority) informs the CHs (certificate holder)
about a compromised signature algorithm or key?

I think the CA should use CRLs, where CRLs are multiple signed. Because
otherwise the information about a compromised algorithm or key could be
forged. Moreover a CH don't know, when such a case occurs, so that the CRL
should have multiple digital signatures ever. A CH can decide which of them
he proofs. All under the assumption that the possibility of occurence of
failures for all used signature algorithms at the same time is very small.
The used signature algorithms in the PKI have to be independent from each
other.

Analogous a OCSP reponse have to be multiple signed.

> If the old OCSP response is that important that you must reuse it, then

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

> would be forced to sign the response multiple times.

Performance is a big theme: But I think it is feasible. For example: today
you use RSA signatures with 1024 bit and in the FlexiPKI you expand it with
an ECDSA signature with 160 bit.

Best regards,
Soenke