Subject: Re: I-D ACTION:draft-ietf-pkix-okid-00.txt

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 1 Feb 2002 11:35:39 +0300

On 31 Jan 02, at 17:03, Paul Hoffman / IMC wrote:

Paul,

[...]

> We disagree here. Given Alice's OCID (it is now a cert ID, not a key
> ID), Mallory creates a template certificate with his own public key
> in it. In the template, he adds an extension that has an octet stream
> of length 10. He then cycles through all the combinations of 2^80
> values in the octet stream until the hash over the template
> certificate matches Alice's OCID, signs the cert, and is done.
>
> Mallory does *not* need to change the public key in an OCID: he can
> change any value in the certificate to get the right hash.

But doesn't he still need to sign certificate before hashing?
Clearly, signing is less computationly expensive than creating public
key, but it is still much more expensive than just hashing.

> --Paul Hoffman, Director
> --Internet Mail Consortium

Regards,
Valery Smyslov.

---

From: Denis Pinkas <[email-masked]>
Date: Fri, 01 Feb 2002 09:54:10 +0100

Paul,

> At 5:11 PM +0100 1/31/02, Denis Pinkas wrote:
> >1) The current document addresses only the verification of self-signed
> >    certificates, but is subject to security attacks (i.e. substitution
> >    of self-signed certificates) because only the hash of the public key
> >    contained in the self-signed certificate is verified:
> 
> Correct. I have yet to hear of an interesting attack where Mallory
> has some good reason to substitute "Alice A" for "Alice B" on Bob's
> system when "Alice A" and "Alice B" are both self-signed.

We are talking of trust anchors. A self-signed certificate contains among
other things a validity period and naming constraints.

1) The validity period limits the duration of the trust anchor.

It is not mandatory to change the value of the public key when a self-signed
certificate is renewed. Hence a replay attack is possible by re-installing
the current self-signed certifiace instead of a new one.

2) Clients may install different self-signed certificates that contain
different naming constraints. If naming constraints are not part of the
hash, then substitution of trust anchors with different naming constraints
is possible.

So the requirement is to have the hash of the certificate, not simply 
the hash of the public key (and of the algorithm identifier).  

The question of the security comes just *after*.

As soon as a hash is truncated, the security is indeed lower. I let
cryptographers discuss this issue, since I am not a cryptographer. We might
consider different levels of security: the bigger the number of characters
being typed will be, the better the security will be.

Denis

> >  this would mandate
> >    that a CA is not allowed to issue more than one self-signed certificate
> >    with the same public key in it,
> 
> Where in the document did it say this? CAs and non-CA self-signers
> are allowed to do whatever they want.
> 
> >  which is indeed a restriction that is
> >    not acceptable.
> 
> Agree; that's why it doesn't say it.
> 
> >    So the document should be changed to consider the hash of the certificate
> >    instead of only the hash of the public key (and of the algorithm
> >    identifier).
> 
> You then make Mallory's job many orders of magnitude easier. Instead
> of having to create 2^79 key pairs, he only has to create 2^79 hashes
> looking for one that matches Alice's OKID. That doesn't seem like a
> good security choice, particularly because we can assume that it is
> more likely that people will work on hardware hash acceleration than
> they will on hardware key generation.
> 
> >    If we do so, then the "protocol" will also be usable for any type of
> >    certificate, not only self-signed certificates.
> 
> Correct, but at the cost of making the protocol much easier to break.
> 
> >2) The abstract should rephrased as:
> >
> >    The Out-of-Band Key Identifier Protocol (OKID) is a user-friendly
> >    out-of-band way to install certificates.
> 
> Disagree. This protocol does not install certificates. It helps with
> only one step of that process.
> 
> --Paul Hoffman, Director

---

From: "todd glassey" <[email-masked]>
Date: Fri, 1 Feb 2002 07:20:38 -0800

Paul

> are allowed to do whatever they want.

The sentence you are looking for is not in the document, or any document
that PKIX has produced. It is in fact in everything that this WG (PKIX) does
by virtue of the fact that PKIX refesues to put in place Working Models for
how to use its protocols and its management refuses to consider this as a
requirement to separating submitted projects and their work products from
those that would more rightly belong in the realm of the IRTF.

This is a critical realization because what it implies is that SO LITTLE OF
WHAT PKIX IS DOING WILL EVER GET USED  in the commercial world and likely
much of it really does belong in a PKI group under the IRTF and not here.

And by the way Dr. Stephen Kent - That is your responsibility as the Senior
Chair of the WG... yours and the rest of the management's fault - and once
again I suggest that you personally consider moving-on becuase of it and
letting some fresher blood get into PKIX management with Tim.

---

From: Jean-Marc Desperrier <[email-masked]>
Date: Fri, 01 Feb 2002 20:01:17 +0100

Paul Hoffman / IMC wrote:

> At 12:28 AM +0100 2/1/02, Jean-Marc Desperrier wrote:
> >Clearly  if finding a collision does not suffice for Mallory in the
> >first case,
> >but that he has to find a collision for valid data, in that case a
> >valid key, then
> >in the second case, he also has to find a collision for valid data,
> >therefore a
> >valid certificate.

Right, my reasonning was wrong.

Still a few remarks.
Mallory does not  need a strong key.
He only needs a key that's OK enough to be used in the RSA algorithm without
fatal errors.
That might mean he can speed up the generation process.

If the value of the hash is cleverly calculated on the signature and excludes
non-signed parts, Mallory will have to sign the certificate before
calculating the hash.

This would have to be checked in details before being sure there's that much
speed difference between the two processes.

---

From: Paul Hoffman / IMC <[email-masked]>
Date: Fri, 1 Feb 2002 11:24:06 -0800

>That might mean he can speed up the generation process.

If so, such exploits would make Mallory's job easier. However, can 
creating 2^79 weak RSA public keys ever be faster than computing 2^79 
SHA-1 hashes over a small message? That is the balance between 
choosing OKID and OCID.

--Paul Hoffman, Director

---

From: Dr S N Henson <[email-masked]>
Date: Sat, 02 Feb 2002 00:35:39 +0000

> change any value in the certificate to get the right hash.

I think the OCID would be the whole certificate including the digital
signature. If the client checks the signature that would mean that any
changes to the signed portion would require the signature to be
recalculated.

However as Peter pointed out if the unsigned portion of the certificate
does not need to be DER encoded then all manner of ASN1 variations could
be tried without the need to recalculate the signature. These could
include...

Changing some SEQUENCEs to use indefinite length constructed encoding.

Modifying the encoding of the signature to use lots of constructed
encoding variations. That by itself is enough if the decoder will
tolerate it because the BER allow a BIT STRING to be partitioned into
arbitrary chunks to arbitrary depths IIRC.

Steve.
-- 
Dr Stephen N. Henson.   http://www.drh-consultancy.demon.co.uk/
Personal Email: [email-masked] 
Senior crypto engineer, Gemplus: http://www.gemplus.com/
Core developer of the   OpenSSL project: http://www.openssl.org/
Business Email: [email-masked] PGP key: via homepage.

---

From: Dr S N Henson <[email-masked]>
Date: Sat, 02 Feb 2002 00:39:21 +0000

> That might mean he can speed up the generation process.

As I indicated in another message the RSA key generation process can be
speeded up so that all that is needed is to look up primes from a large
table and calculate their product.

Steve.

---

From: "Valery Smyslov" <[email-masked]>
Date: Mon, 4 Feb 2002 10:37:25 +0300

> changes to the signed portion would require the signature to be

I also think so.

> arbitrary chunks to arbitrary depths IIRC.

This problem is easy to avoid by requiring OCID hash to be always
produced only over DER-encoded certificates. In this case all other-
encoded certificates must be unambiguously reencoded (into DER)
before calculating OCID.

Regards,
Smyslov Valery.