Subject: RE: multiple digitale signatures

From: "Bland, Graham" <[email-masked]>
Date: Tue, 20 Feb 2001 14:53:39 -0000

Sonke,

Firstly Revocation of algorithms by CAs.

Whenever have seen a compromise of a mainstream algorithm it has never been
a yes/no case, they have been weakened over time. The strength of an
algorithm is only relevant in conjunction with the value and duration of the
service or information it protects.

Where a CA is using algorithms for its own purposes such as signing
certificates or CRLs then it is within the CAs scope to modify the algorithm
strength or the algorithm used for any signature it creates, the same
flexibility applies to any creator of a signature such as an OCSP responder.
The signature is valid at the time it was created.

Where anybody has issued certificates or signed responses it is outside
their scope to revoke certificates which use those algorithms.

An example would be Verisign arbitrarily revoking all 40 bit SSL
certificates on the grounds they are insecure, imagine the chaos which this
would cause.

Also what should the behaviour be where in validating a certificate chain
one CA has revoked an algorithm but other CAs have not. Assuming the CA
hierarchy is A(root) B and C, if B as the second tier revokes RSA but uses
DSA signatures on its certificates whereas A and C use RSA but have not
revoked it what should happen? Should the non revocation by the root CA be
binding on the chain or is a single revocation binding on all CAs even if
they do not agree.  If I have multiple trust points and CAx has revoked an
algorithm is this binding on a path which does not include CAx?

An attack was reported on RSA in the last couple of weeks before it was
realised that this attack was slower than existing methods of factoring.
Should CAs have revoked RSA on the report of an attack and then reinstated
it or ignored it until it had been substantiated. I shudder to think of the
legal implications in the real world of either action.
 
IMHO this is complexity which is unworkable in practice.
 
Secondly multiple digital signatures

As far as I can see the scheme you propose only has historical value, as at
the time the signature was created it presumably was trusted by the creator.
If it is not trusted by the recipient then the option exists to reject it.

To take this to its logical conclusion and to be useful there would have to
be a set of rules create to ensure that the signatures had different
characteristics such as different hash algorithms, no two signatures based
on the same mathematical problem (Factorisation, discreet logarithms etc) as
these could become 'simple' problems at some time in the future. etc. etc.

Again this I believe is unworkable in practice due to the overheads it would
cause and would have little value in practice, as such it should not be
applied in the standards.

Graham Bland

-----Original Message-----
From: Sönke Maseberg [mailto:[email-masked]]
Sent: 19 February 2001 21:28
To: pkix
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
_______________________________________________________________________

This message is confidential and is intended for the addressee only;
unless clearly stated that this disclaimer should not apply, this 
e-mail is not intended to create legally binding commitments on 
behalf of any company in the British Interactive Broadcasting 
Holdings Limited group,  nor do its contents reflect the corporate 
views or policies of any such company. Any unauthorised disclosure, 
use or dissemination, either whole or partial, is prohibited. If you 
are not the intended recipient of the message, please notify the
sender immediately.
_______________________________________________________________________

---

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

Graham,

we are working at the problems if a signature algorithm is compromised
suddenly without any time to change the algorithm parameters, keys oder
key lengths. IMO the CA is responsible for the certificates of the CHs.
If now a failure occurs, the shocked certificates have to be revoked.
The idea is to revoke the certificates not explicitly but implicitly
through the revocation of the used signature algorithms. The benefit
would be a shorter CRL, and the benefit grows up if many CHs are
involved.

I agree that for multiple digital signatures different signature
algorithms have to be used with independent components like hash
algorithm and independent basic mathematical problems. The use of
multiple digital signatures is optional in relation to the specific
application: In authentication applications it makes less sense. But the
signatures in e.g. e-government have to be proofable for many years.

Sönke

---

From: [email-masked] (Peter Gutmann)
Date: Fri, 23 Feb 2001 04:56:32 (NZDT)

SM-vnke Maseberg <[email-masked]> writes:

>But I want to point out, that there is no signature algorithm that is
>proofable secure. Yes, the established algorithms are analysed and they seem
>to be secure, but we cannot exclude the sudden compromise of a signature
>algorithm. On the other hand a lot of companies, banks or governments rely on
>PKI technologies. What would happen if a failure occurs? 

What will happen depends on the signature algorithm which is compromised:

RSA: The entire world will find out.  It'll be on the evening news, and the
     front page of most papers.  As yet undiscovered tribes in the jungles of
     Borneo will have missionaries hacking their way through the undergrowth
     just to tell them.

DSA: The few government users who care will read about it in Government
     Computer News and keep using it anyway while they await orders from on
     high on what to do next.  NIST will convene a standards group to look 
     into the matter with a preliminary draft due in early 2003.  ANSI will
     also work on resolving this with a draft due in 2003, but it won't
     actually be published until 2012.  Neither of these versions will be 
     even remotely compatible with any existing work.  Leaked, obsolete 
     copies will be incorporated in part into some RFCs.

X9.42 DH (which isn't actually a signature algorithm anyway), various ECCs, and
     others: In 6-12 months there will be a paper in Crypto or Eurocrypt which
     cryptographers will agree is a brilliant attack and which everyone else
     will ignore completely.

I can't see that any of these cases require the introduction of any complex new
dual-signature mechanism to augment them.  If there's a sudden compromise
(which, as others have pointed out, is incredibly unlikely), it'll be handled
through standard channels.  End of story, now we can get back to debating how
many name constraints can fit on the head of a pin.

Peter.