Subject: Possible ambiguities in encoding of signatures, encrypted keys

From: [email-masked] (Peter Gutmann)
Date: Mon, 12 Apr 1999 16:07:01 (NZST)

Currently both RFC 2459 and CMS refer to RFC 2313/2437 for the encoding of RSA
signatures/encrypted data (RFC 2459, 7.2.1; CMS, 12.3.2.1 and 12.2.2 - what I'm
about to describe applies to other algorithms as well, but I'll stick with RSA
to keep it simple).  These RFC's make the assumption that the encoded value
will be of the same length as the modulus, zero-padding the value if required
(RFC 2437, 7.2.1 and 8.1.1), however when this padding is used the encoded
value doesn't follow the DER any more.  Although neither RFC 2459 or CMS
require this, the former does imply it when it says (Section 4) "the
certificate is encoded with the ASN.1 distinguished encoding rules (DER)".
Because the signature will be zero-padded a small portion of the time as per
RFC 2313/2437, it's not a DER-encoded value.  In addition I would suspect that
most implementations don't perform the zero-padding (although it's hard to
check because it occurs only about once every 256 times), so they wouldn't
comply with RFC 2313/2437.
 
The zero-padding requirement isn't something which is right or wrong one way or
the other, not padding means you get DER-compliant encodings, but padding is
necessary to allow one-pass encoding of CMS data (unless you use the indefinite
encoding all the way down) since the signature at the end of an arbitrary
amount of data could suddenly shrink by one (or more) bytes, requiring
everything to be re-encoded from the start.
 
To clear up this problem, I'd recommend the following:
 
Change the text in RFC 2459, section 4, to read:
 
  "the tbsCertificate is encoded with the ASN.1 distinguished encoding rules
   (DER)"
 
and add the following text wherever a reference to RFC 2313/2437 is made (I've
listed the section numbers above):
 
  Although RFC 2313/2437 requires that the encoded values be zero-padded to
  match the size of the modulus, this padding doesn't comply with the ASN.1
  distinguished encoding rules (DER) which allow at most one leading zero byte,
  and only if the MSB of the value is set.  Some implementations may choose to
  pad the value as per the RFC's, others may choose to follow the DER.  Both of
  these encoding forms are acceptable, and implementations should be able to
  process both zero-padded and non-padded values.
 
If necessary I guess RFC 2459 could be a bit more strict (always require DER),
but CMS should allow both forms since, as I've outlined above, requiring DER
would make one-pass encoding impossible.
 
Peter.

---

From: William Whyte <[email-masked]>
Date: Mon, 12 Apr 1999 10:20:54 +0100

Hi Peter,

> value doesn't follow the DER any more.

I'm not sure this is right. The signature is an octet string or a
bit string, not an integer, and it's perfectly legal to have an
OCTET STRING or BIT STRING with leading null bytes. RFC 2313 says:

8.4 Integer-to-octet-string conversion

   The integer encrypted data y shall be converted to an octet string ED
   of length k, the encrypted data. 

and it's the octet string that's encoded.

Cheers,

William

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 13 Apr 1999 00:11:34 (NZST)

>I'm not sure this is right. The signature is an octet string or a bit string,
>not an integer, and it's perfectly legal to have an OCTET STRING or BIT STRING
>with leading null bytes.
 
Ah, of course!  This only leaves the signatures which have internal structure
(eg DSA, a SEQUENCE containing two INTEGER's), and they have their own rules
which don't clash with RFC 2459/CMS.
 
(Didn't PKIX at one point include a requirement for DH values, encoded as bit
 strings, to be shifted up so the MSB was the first nonzero bit in the string,
 thankfully this vanished soon after it appeared because it would've been a
 right pain to implement)
 
Is anyone aware of any implementations which break if the signature/encrypted
data value isn't padded out as required?  You'd probably have to go out of your
way to write code which does this, I'm wondering whether any code does actually
complain if the data isn't exactly the right size.  The reason I'm asking is
that I've always encoded things in the minimum number of bytes (as if it was a
DER INTEGER) rather than padding with zeroes which so far hasn't caused any
problems.
 
Peter.