Subject: [pkix] RFC3852/RFC5652 CMS DER Set-of encoding in SignedAttributes

From: Jacob Dilles <[email-masked]>
Date: Mon, 21 Apr 2014 20:58:55 -0400

We are doing in-depth conformance validation of RFC3369/5652 CMS objects
with SignedData (Section 5) content type.

One of the things we check is sort-order on Set-Of types, as in

|    SignedAttributes ::= SET SIZE (1..MAX) OF Attribute

which must be DER encoded per Section 2 pg. 3 of the RFC. As specified
by the reference [DER], X.509-88 sec 8.7 (p14):

|   e) the components of a Set-of type shall be encoded in ascending
|      order of their octet value;

Per the terminology of X.209 BER, this is unambiguous in excluding
length from the comparison (not 'tag' nor 'length', only 'value');
however the point was clarified later in X.690-0207 (p19):

|   11.6 The encodings of the component values of a set-of value shall
|        appear in ascending order, the encodings being compared as
|        octet strings with the shorter components being padded at their
|        trailing end with 0-octets.
|
    
|        NOTE  The padding octets are for comparison purposes only
|        and do not appear in the encodings.

Which is similar (component 'values' .. 'ascending order'), but goes on
to specifically require that length be excluded from comparison
(otherwise, a trailing-zero padding scheme is unnecessary,
lexicographical sorting of the definite-length encoding of types
with the same tag will always result in shortest-length-first order).

We have noticed a discrepancy between this specification and many CMS
objects, both found in the wild and produced in testing several popular
cryptographic libraries.

Three common SignedAttributes are ContentType (11.1), MessageDigest
(11.2), and SigningTime (11.3); IDENTIFIED BY 1.2.840.113549.1.9.3, .4,
and .5 respectively (from PKCS9). Per [DER], given the
following input:

    a. ContentType:   2.23.136.1.1.1

    b. MessageDigest:
d21c11ee67e200fd452b587cc3bc5cb4b0ab7a92c16389fce96c7a79aa714ebc

    c. SigningTime:   070131203016Z

We should encode the Set-of Attributes ordered by their encoded value,
which first differs at the 11th octet:

    1. ContentType   (<30 15> 06092A864886F70d0109[03]..)

    2. MessageDigest (<30 2F> 06092A864886F70d0109[04]..)

    3. SigningTime   (<30 1C> 06092A864886F70d0109[05]..)

But we find that as encoded, they are ordered as:

    1. ContentType   (<30 [15]> ..)

    2. SigningTime   (<30 [1C]> ..)

    3. MessageDigest (<30 [2F]> ..)

i.e. sorting the Set-of component types by their DER encoding, including
tag and length (15 < 28 < 47). Despite being in violation of the
specification(s), this is simpler from an implementation perspective and
seems to have become a de facto standard.

My question is: For the purpose of determining if an object conforms to
the RFC3852 and/or RFC5652 CMS profile, should we consider the second
SignedAttributes Set-of encoding method compliant?

Thanks,

Jacob Dilles

---

From: "Manger, James" <[email-masked]>
Date: Tue, 22 Apr 2014 12:19:21 +1000

Jacob,

The tag & length are not excluded when sorting a SET OF elements. You are misreading the specs.

The 1988 text might have been a bit unclear by saying "the components .. octet value". The 2002 text is crystal clear: "encodings" are compared. An encoding includes tag-length-value. It makes no sense to exclude tag & length as then sorting would not be unique when the values of two components were empty (or identical). The talk of padding just makes sure that when comparing encodings of different lengths their first bytes are aligned, not their last bytes.

--
James Manger

-----Original Message-----
From: pkix [mailto:[email-masked]] On Behalf Of Jacob Dilles
Sent: Tuesday, 22 April 2014 10:59 AM
To: [email-masked]
Subject: [pkix] RFC3852/RFC5652 CMS DER Set-of encoding in SignedAttributes

    

    

    b. MessageDigest:

Thanks,

Jacob Dilles

_______________________________________________
pkix mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/pkix

---

From: Jacob Dilles <[email-masked]>
Date: Tue, 22 Apr 2014 00:41:43 -0400

Thanks James,

Maybe I'm being dense, but (comments inline):

On 4/21/14 10:19 PM, "Manger, James" <[email-masked]>
wrote:

>The 1988 text might have been a bit unclear by saying "the components ..
>octet value". The 2002 text is crystal clear: "encodings" are compared.
>An encoding includes tag-length-value. It makes no sense to exclude tag &
>length as then sorting would not be unique when the values of two
>components were empty (or identical).

Set-of type is defined to have all components of the same type, so the
tags will always be the same, and two component types with empty or
identical values have exactly one encoding, no sorting required. For
example:

A ::= INTEGER 1

B ::= INTEGER 1

S1 ::= SET OF INTEGER {A B}

S2 ::= SET OF INTEGER {B A}

S1 and S2 are indistinguishable {1 1} and thus have a unique encoding (31
04 02 01 02 01). This is true for any length (including empty) and any
number of repeated values - I'm not sure what the relevance is here.

> The talk of padding just makes sure that when comparing encodings of
>different lengths their first bytes are aligned, not their last bytes.

Why would you need padding when comparing DER tag-length-value encodings
that have different lengths?

* For comparison between two components encoded with short-form length
(0-127 octets), clearly the comparison will end at the (only) length
octet, no padding required.

* For comparison between a short-form and long-form lengths, the
comparison will end with the first length octet, as 1xxxxxxx > 0xxxxxxx.
No padding required.

* For comparison between two long-form lengths that require a different
number of extend-octets, the comparison will end with the first octet
since it includes the number of length-extend octets (e.g. TT [82] xx xx
Vs. TT [83] xx xx xx). No padding required.

* For comparison between two long-form lengths that require the same
number of length-extend octets, the comparison will end at the differing
length-extend octet, of which there are the same quantity. No padding
required. 

Perhaps you have a counterexample?

If the authors had intended lengths to be included in the comparison, it
would be worded "shall appear in ascending order, shorter components
first, with values of equal length being compared as octet strings" which
would be computationally cheaper; yet they went out of their way to
specify the zero-padding algorithm. The only way this algorithm gets used
is if you ignore the length of the encoded Set-of element
tag-length-value.  

Jacob Dilles

PS Sorting by zero-padded *value* encoding makes sense because, for
example, a SET OF OBJECT IDENTIFIER (or AlgorithmIdentifier, or Attribute,
etc.) will sort by arc.

---

From: Jacob Dilles <[email-masked]>
Date: Tue, 22 Apr 2014 01:19:05 -0400

Sorry, SET OF INTEGER {1 1} is 31 06 02 01 01 02 01 01. Bit rusty on the
hand-encoding :)

---

From: "Manger, James" <[email-masked]>
Date: Tue, 22 Apr 2014 16:15:29 +1000

> tags will always be the same,

No. The type can be a CHOICE, in which case the tags can vary.

For instance,
  Labels ::= SET OF DirectoryString
where DirectoryString is a CHOICE of 5 string types (TeletexString, PrintableString, UTF8String etc).

So here (in hex) is a DER-encoding of a SET OF DirectoryString that consists of a UTF8String with value "a" and a PrintableString with value "a".

31 06
   0C 01 61
   13 01 61

--
James Manger

---

From: Jacob Dilles <[email-masked]>
Date: Tue, 22 Apr 2014 09:58:02 -0400

Perfect. I had a feeling I was missing something. Thanks!

Jacob Dilles

On 4/22/14 2:15 AM, "Manger, James" <[email-masked]>
wrote:

>So here (in hex) is a DER-encoding of a SET OF DirectoryString that
>consists of a UTF8String with value "a" and a PrintableString with value
>"a".
>
>31 06
>   0C 01 61
>   13 01 61
>
>--
>James Manger