Subject: AlgorithmIdentifier, SHA-1, etc.

From: Eric Rescorla <[email-masked]>
Date: Fri, 06 Apr 2007 11:30:49 -0700

I'm trying to get a handle on how one ought to encode AlgorithmIdentifier.

As people will perhaps remember, the ASN.1 is:

AlgorithmIdentifier  ::=  SEQUENCE  {
     algorithm               OBJECT IDENTIFIER,
     parameters              ANY DEFINED BY algorithm OPTIONAL  }
                                -- contains a value of the type
                                -- registered for use with the
                                -- algorithm object identifier value

Present hash functions do not take any useful parameters, leaving
us with two encoding options:

  - omit the parameter.
  - include a NULL

To make things more complicated, there are (at least) two different
contexts in which this production appears:

  - The S/MIME DigestAlgorithmIdentifier production.
  - Inside the DigestInfo of the S/MIME signature.

RFC 3370's guidance is to omit the parameter for SHA-1 and include
a NULL for MD5 (see S 2.1 and 2.2.).

However, the current PKCS#1 errata
(ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1errata.txt)
recommend that when one is encoding DigestInfo, one should
encode it as NULL:

  Exception: When formatting the DigestInfoValue in EMSA-PKCS1-V1.5 
  (see 9.2), the parameters field associated with id-sha1, id-sha256, 
  id-sha384 and id-sha512 SHALL have a value of type NULL. This is to 
  maintain compatibility with existing implementations and with the 
  numeric information values already published for EMSA-PKCS1-V1.5 
  which are also reflected in IEEE 1363a-2004[27].

My understanding from discussions in Prague is that this reflects
NIST's current guidance as well.

Technically these don't conflict, but obviously, it's undesirable to
have the encoding in the message not match that in the DigestInfo,
since doing binary comparisons is common practice here. So, what's the
right answer here?

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 06 Apr 2007 13:09:27 -0700

At Fri, 06 Apr 2007 13:02:58 -0700,
Blake Ramsdell wrote:
> Eric Rescorla wrote:
> In my case when I receive a digest AlgorithmIdentifier, I bust it open 
> and get the OID out and discard the wrapper (the outer 
> AlgorithmIdentifier). So I'm not affected by a mismatch if I do that.
> 
> But yeah, short of normalizing the values in some way, you're pretty 
> much done. That is, there's no binary comparison, and you perform an 
> equivalence check by converting both values in such a way that the same 
> answer comes out. So if you have { sha-1, NULL } and { sha-1 } you get 
> the same answer.

Yeah, my thinking is that it would be better for these to match
so that naive implementations work.

-Ekr

---

From: Blake Ramsdell <[email-masked]>
Date: Fri, 06 Apr 2007 13:02:58 -0700

Blake
-- 
Blake Ramsdell | Sendmail, Inc. | http://www.sendmail.com

---

From: Russ Housley <[email-masked]>
Date: Fri, 06 Apr 2007 16:09:19 -0400

Note that the DigestInfoValue is part of the structure that is 
"encrypted" with the RSA private key when generating a signature.  It 
is recovered by "decrypting" the signature value with the RSA public key.

An implementation should check that the expected digest algorithm was 
used.  As Eric point out, this check is easier to perform if the two 
values are encoded in exactly the same manner.

One needs to look deeper into signatures in certificates and CMS 
SignerInfo to see where these comparisons are really performed.

The certificate signature has this structure:

    Certificate  ::=  SEQUENCE  {
         tbsCertificate       TBSCertificate,
         signatureAlgorithm   AlgorithmIdentifier,
         signatureValue       BIT STRING  }

In practice, the signature algorithm tells the digest algorithm as 
well as the digital signature algorithm. The ones that are relevant 
to this question are:

    sha1WithRSAEncryption
    sha224WithRSAEncryption
    sha256WithRSAEncryption
    sha384WithRSAEncryption
    sha512WithRSAEncryption

There is no filed that explicitly carries a digest algorithm 
identifier.  So, the digest algorithm for comparison to the 
DigestInfoValue inside the signature value must be generated in some 
manner by the implementation.  I believe than many implementations 
use a simple internal table.  Adding entries to this table is part of 
the work needed to add support for additional RSA signature 
algorithms.  So, the table should contain exactly the octet string 
that will appear in DigestInfoValue, including the NULL parameter 
required by PKCS#1.

The CMS SignerInfo has this structure:

       SignerInfo ::= SEQUENCE {
         version CMSVersion,
         sid SignerIdentifier,
         digestAlgorithm DigestAlgorithmIdentifier,
         signedAttrs [0] IMPLICIT SignedAttributes OPTIONAL,
         signatureAlgorithm SignatureAlgorithmIdentifier,
         signature SignatureValue,
         unsignedAttrs [1] IMPLICIT UnsignedAttributes OPTIONAL }

Again, the signature algorithm tells the digest algorithm. The same 
set of algorithm identifiers are used here.

In each case, the digestAlgorithm must contain the digest algorithm 
identifier that is implicitly named by the signature algorithm, and 
the DigestInfoValue must contain the same digest algorithm identifier.

As Eric has already explained, the parameter in DigestInfoValue must 
be NULL, but we are "forgiving" in the processing of the parameter 
for digestAlgorithm.  The parameter can be NULL or absent.

In order to use the same signature validation routines for CMS and 
certificates, I believe that most implementations use the same 
internal table as discussed above for the DigestInfoValue 
comparison.  Then, in addition, the digest algorithm identifier is 
compared to the digestAlgorithm field in SignerInfo.  The signature 
value must contain exactly the expected digest algorithm identifier 
with a NULL parameter.

So, the only comparison that is not an exact match is the comparison 
from the internal table entry to the digestAlgorithm field.  I 
suggest that the object identifiers must match, but one can ignore 
the parameters, after making sure they are either absent or 
NULL.  That is, do not let the parameters carry some inappropriate value.

Russ

---

From: [email-masked] (Peter Gutmann)
Date: Sat, 07 Apr 2007 19:01:26 +1200

Eric Rescorla <[email-masked]> writes:

>So, what's the right answer here?

Read the OID and hash value, toss the rest.  Doing anything else is just
asking for trouble.

(There's really no question here: There are two ways to do this, knowing in
 advance what you'll encounter in the field isn't possible, so the only
 workable solution is to not compare the encoded value, or if you must,
 compare two pre-encoded alternatives for each possible hash algorithm.  This
 still breaks though if someone gets the encoding slightly wrong... comparing
 a pre-built value is just asking for trouble).

>My understanding from discussions in Prague is that this reflects NIST's
>current guidance as well.

This would put them in conflict with ISO, who (the last time I checked) say
the parameter should be omitted.  In any case though it doesn't really matter
which side wants to hold their breath the longest, if you read the OID and
hash and work with that you can't go wrong.

Peter.

---

From: Dr Stephen Henson <[email-masked]>
Date: Sat, 07 Apr 2007 12:39:07 +0100

Russ Housley wrote:
> "encrypted" with the RSA private key when generating a signature.  It is
> recovered by "decrypting" the signature value with the RSA public key.
> 

Note that care should be taken when handling the DigestInfo structure
recovered from an RSA signature.

As well as the original Bleichenbacher signature forgery attack (caused
by ignoring trailing garbage after DigestInfo) there is a variant which
inserts garbage in the middle of the recovered structure. Allowing
arbitrary parameter values in the DigestAlgorithmIdentifier (for example
large OCTET STRINGs) is one way to do this. Unlike the original attack
this variant produces a "valid" DigestInfo structure.

As a result in the specific case of the recovered DigestInfo from an RSA
signature OpenSSL now only tolerates a NULL or absent parameter field.
This is OK for all existing digests.

It is more liberal about DigestInfo structures in other contexts.

Steve.

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 07 Apr 2007 07:30:42 -0700

At Sat, 07 Apr 2007 19:01:26 +1200,
>  a pre-built value is just asking for trouble).

Totally agree.

My question was more what we ought to recommend.

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 07 Apr 2007 07:30:03 -0700

At Sat, 07 Apr 2007 12:39:07 +0100,
> It is more liberal about DigestInfo structures in other contexts.

Steven,

As I recall OpenSSL puts the NULL in the digestAlgorithm encoding
as well. Am I right about that? 

Thanks,
-Ekr

---

From: Dr Stephen Henson <[email-masked]>
Date: Sat, 07 Apr 2007 18:07:06 +0100

> as well. Am I right about that? 

Yes. It places the NULL in the DigestAlgortihmIdentifier for RSA
signatures DigestInfo according to PKCS#1.

It also includes it in other DigestAlgorithmIdentifier structures too.

As I recall (I'd have to check some ancient email archives) the NULL was
needed to pass an old S/MIME v2 compliance test some years back.

Steve.

---

From: Russ Housley <[email-masked]>
Date: Sat, 07 Apr 2007 18:49:14 -0400

Thanks for pointing this out.  I did say that you needed to make sure 
it was a valid parameter encoding, but I should have included this 
important additional information.  Thanks.

Russ

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 09 Apr 2007 14:11:04 +0200

>  a pre-built value is just asking for trouble).

That approach, to not validate the parameters field, is what led to
the variant of Bleichenbacher's attack in several TLS implementations.
I'm strongly opposed to permit this in conforming implementations.

Even if we restrict it to either absent parameters or NULL parameters,
that would enable a side-channel: you can "leak" one bit of
information by deciding which of NULL or absent you use.  It is not
clear to me how important that threat is.  There are other ways to
leak information in the TLS protocol (packet ordering, random values,
etc).  However, there may be some value in not expanding the ways to
leak information further.

I could live with MUST generate NULL parameters fields on encoding,
and MUST accept both NULL and absent fields on decoding.

/Simon