Re: Problem verifying a signed message

----- Original Message -----
From: "Colestock, Robert" <[email protected]>
To: <[email protected]>; <[email protected]>
Cc: "Pawling, John" <[email protected]>
Sent: Monday, March 18, 2002 2:30 PM
Subject: RE: Problem verifying a signed message

> After investigating our ASN.1 encoding of the signed attributes of this
> message, I believe the SFL encoding is correct.  The encoding difference
> is due to the ASN.1 DER encoding rule that states that the SEQUENCE OF
> must be numerically ordered.  The SFL ordering is correct, but in this
> case it may not be obvious why.  The DER rules indicate the the ordering
> must be made on the data, not the outer tag and length.

I believe the above understanding of DER to be incorrect, although I would
say that the DER specification is poorly worded.  Paragraph 11.6 of [X.690]
states:

"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."

I believe that "encodings of the component values" refers to the _complete_
encoding of each value, including its outermost tag and length.  It would be
illogical for it to be otherwise.  Whilst excluding the outermost tag and
length from the comparison might make sense for primitive data types
(strings, OIDs etc.) it would be bizarre for constructed values, e.g.
SETs/SEQUENCEs as used in signed attributes, because what you would then be
comparing would be two series of tagged SET/SEQUENCE members stacked
end-to-end, rather than a "whole" SET/SEQUENCE.

> Ignoring the tag and length, the 2nd and 3rd SEQUENCE items of the
SignedAttrs are as
> follows (from original message not re-encoded results):
>
> ...
> 30 18 06 09 2A 86 48 86 F7 OD 01 09 03 31 0B 06 ...
> 30 1C 06 09 2A 86 48 86 F7 OD 01 09 05 31 0F 17 ...
> 30 23 06 09 2A 86 48 86 F7 OD 01 09 04 31 16 04 ...
> ...

The above appears to be correctly DER-encoded, because the most significant
difference is in the second octet (the length of the SEQUENCE).
If you refer to example 5.4 at http://www.imc.org/draft-ietf-smime-examples,
it resembles the above.

> Our DER re-encoded results:
> ...
> 30 18 06 09 2A 86 48 86 F7 OD 01 09 03 31 0B 06 ...
> 30 23 06 09 2A 86 48 86 F7 OD 01 09 04 31 16 04 ...
> 30 1C 06 09 2A 86 48 86 F7 OD 01 09 05 31 0F 17 ...
>                                     ** <<< ORDERED VALUE >>>
> ...
> IGNORING the 23 AND 1C lengths, the ordering occurs on the "**" flagged
> values (04 AND 05).

And the above appears to be incorrect because the lengths have been ignored
and the sorting is done based on a component within the OID.

> I hope this helps.  I personally wrote this particular DER encoding
> modification in the SNACC compiler (it was originally a BER encoding
> compiler).  You may already be aware of this, but if you attempt to
> write the logic that sorts the SEQUENCE OF elements, be careful of the
> byte count of the lengths (82 01 01 for example indicates 2 bytes, 257
> value).

Here's another reason why including the outermost tag/length when sorting
makes more sense - if you have stored your SET OF in memory as an array of
fully-encoded components, perhaps as pointers into the original encoded
data, you can simply memcmp() them without having to parse the tag and
length of each to find the offset at which to start the comparison.

Also, with the outer tag/length included in the comparison, you don't
actually need to worry about padding shorter values with zero octets as
described in [X.690] section 11.6 - the fact that only definite lengths are
used in DER guarantees that a shorter value will differ from a longer one
before the end of the shorter value is reached, so memcmp() will never
reference the padding octets.

Reference:

[X.690] - INTERNATIONAL STANDARD 8825-1/ITU-T RECOMMENDATION X.690 (12/97):
Information technology - ASN.1 encoding rules: Specification of Basic
Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished
Encoding Rules (DER)

John Stark
E-mail: [email protected]
Tel: +44 (0) 1223 566732
Fax: +44 (0) 1223 566727
Mobile: +44 (0) 7968 110628