Subject: RE: X.509 Extensions Enhancements

From: "Tom Gindin" <[email-masked]>
Date: Wed, 27 Jun 2001 22:51:40 -0400

Carlin:

     Your argument would be more convincing if it weren't for note 2 to
section 11.2.2 of X.690 (I'm using the '94 version), which strictly limits
the length of an encoding with no 1 bits ("If a bitstring value has no 1
bits then an encoder shall encode the value with a length of 1 and an
initial octet set to 0"), without consideration of the number of bits in
the named bit list.  The stuff you quoted from X.680 is applicable to BER
(the original one of the encodings, after all) rather than DER.

          Tom Gindin

"Carlin Covey" <[email-masked]>@mail.imc.org on 06/27/2001 09:20:36 PM

Sent by:  [email-masked]

To:   "David A. Cooper" <[email-masked]>, <[email-masked]>
cc:
Subject:  RE: X.509 Extensions Enhancements

David,

Perhaps I'm still a bit jet-lagged from my vacation, but I don't follow
your logic.  How does the text that
says the "...rules are free to add (or remove) ..."  lead to your
conclusion that the only rational DER is
to delete all trailing zeros?

Despite my not being able to follow your logic, I don't dispute the fact
that all trailing zeros should be deleted.
However,  I do maintain that the wording is ambiguous concerning whether
these trailing zeros begin within or
after the NamedBitList.  That is, "values that are being encoded" could
refer to NamedBitList's rather than to
bits within a NamedBitList.

Regards,

Carlin

____________________________

-  Carlin Covey
   Cylink Corporation

     -----Original Message-----
     From: [email-masked]
     [mailto:[email-masked]]On Behalf Of David A. Cooper
     Sent: Wednesday, June 13, 2001 6:44 AM
     To: [email-masked]
     Subject: RE: X.509 Extensions Enhancements

     Hoyt,

     I could not find anything in X.509 that specifies how to encode named
     bit lists. However, as Bodo Möller pointed out, X.680 treats bit
     strings differently when it includes a named bit list. The text that
     Bodo quoted is also in section 19.7 of the 1994 edition of X.680:

             When a "NamedBitList" is used in defining a bitstring type
     ASN.1 encoding rules
             are free to add (or remove) arbitrarily many trailing 0 bits
     to (or from) values that are
             being encoded or decoded. Application designers should
     therefore ensure that different
             semantics are not associated with such values which differ
     only in the number of trailing 0 bits.

     So, while it seems that X.509 does not specify how to encode bit
     strings that use a "NamedBitList", I believe that the above text
     allows for only one rational distinguished encoding rule: remove all
     trailing 0 bits. Since this is the rule specified by X.690 for DER
     encoding ("Where [a "NamedBitList" is used in defining a bitstring
     type], the bitstring shall have all trailing 0 bits removed before it
     is encoded."), I believe it is appropriate for X.509 to adopt this
     rule. Since the PKIX certificate and CRL profile simply specifies the
     use of the DER encoding rules, there would be no need to make any
     changes in PKIX.

     Carlin Covey suggests that the number of used/unused bits in a named
     bit list could be used to convey extra information:

             The newly added bits have three values: true, false, and
     omitted. Omitted indicates that
             the CA has no opinion about the value of these flags (probably
     because the certificate
             was issued or the CA software was written prior to these bits
     being defined).

     But as the quotes above show, this is not only inconsistent with DER
     but also with any "legal" encoding rules for named bit lists.

     Dave

     At 12:39 AM 6/13/01 -0700, Hoyt L. Kesterson II wrote:
                   Paragraph 11.2.2 of X.690 states that, for named bit
               strings (paragra[h 19.7 of X.680) all trailing zero bits
               must be removed before encoding.  Paragraph 11.2.1, which
               refers to bit strings of either kind, speaks of unused bits
               in the final octet being zero.  I believe the specific case
               for named bit strings trumps the general case.

               Charlie Gardiner

          from clause x in 509

          In order to enable the validation of SIGNED and SIGNATURE types
          in a distributed environment, a distinguished encoding is
          required. A distinguished encoding of a SIGNED or SIGNATURE data
          value shall be obtained by applying the Basic Encoding Rules
          defined in ITU-T Rec. X.690 (1997) | ISO/IEC 8825 :1998, with the
          following restrictions: In order to enable the validation of
          SIGNED and SIGNATURE types in a distributed environment, a
          distinguished encoding is required. A distinguished encoding of a
          SIGNED or SIGNATURE data value shall be obtained by applying the
          Basic Encoding Rules defined in ITU-T Rec. X.690 (1997) | ISO/IEC
          8825 :1998, with the following restrictions:

          in the list of restrictions is

          In order to enable the validation of SIGNED and SIGNATURE types
          in a distributed environment, a distinguished encoding is
          required. A distinguished encoding of a SIGNED or SIGNATURE data
          value shall be obtained by applying the Basic Encoding Rules
          defined in ITU-T Rec. X.690 (1997) | ISO/IEC 8825 :1998, with the
          following restrictions:

          509 says to encode according to the rules in 509. the x.680 DER
          rules were written later than those in x.509. in the case of bit
          string, the rules are different. the rules in x.680 do not permit
          extensibility in a bit string. the rules in 509 do.

             hoyt

---

From: Phil Griffin <[email-masked]>
Date: Thu, 28 Jun 2001 09:11:22 -0400

Tom,

You nailed it perfectly. Allowing trailing zero bits
does not lead to a "distinguished" encoding. Arbitrary
numbers of trailing zero bits is a BER feature, as it 
allows a sender more than one way to encode the same 
value.

Whether or not a given bit appears in a named bit list
is not a consideration. There is no indication whatsoever
in a BER/DER encoding that a bit has a name or not in
some ASN.1 type definition. 

And ASN.1 does not require that all bits that are 'used'
have a name. ASN.1 allows you to create bit string types
such as 

   Bits ::= BIT STRING { skipSomeBits (2) }

which leaves the leading bits 'used' but not 'named'. 

Though these leading bits are 'unassigned bits' with no
name, they must be present in a BER/DER encoding that 
carries the named bit 'skipSomeBits'. So it is not 
possible for leading bits to participate in some sort
of three value logic - such notions do not generalize
well.

And there is no loss of extensibility using DER (X.690).
Unconstrained bit strings such as 'Bits' are inherently
extensible. There is no size limit imposed by this ASN.1
type definition, no matter how many bits are named or
not.

Named bits in a type definition do carry semantics for 
human readers. So, they have a role in the XER encoding
rules and the new ASN.1/XML value notation. 

With the type definition 

   WorkDays ::= BIT STRING {
      monday    (1), 
      tuesday   (2),
      wednesday (3),
      thursday  (4),
      friday    (5)
   } 

a user might specify a value of WorkDays as

   <WorkDays> 0101 </WorkDays>

or, using the named bits, as

   <WorkDays> <monday/> <wednesday/> </WorkDays>

Looking at the text in X.680 will not tell you how to
encode a distinguished value. The text in X.680 must be
general enough to support, not just BER and DER, but all
possible encoding rules. This includes new ones such as
the XER rules written long after the words in X.680. 

It is X.690 that defines DER by restricting the rules
for BER. Though it may be a difficult read, X.690 is not
ambiguous on how to encode a bit string in one and only
one way. But some may find it easier to digest one of
the books at http://www.nokalva.com/asn1/booksintro.html.

Phil

---

From: "Carlin Covey" <[email-masked]>
Date: Thu, 28 Jun 2001 08:24:03 -0700

Tom, you raise a good point.  I had overlooked that note.
That certainly presents a counter example to my interpretation.

But I'm still a bit puzzled.  Is there no significance to
the fact that this text appears in a section entitled "Unused bits"?

Regards,

Carlin

-  Carlin Covey
   Cylink Corporation

-----Original Message-----
From: Tom Gindin [mailto:[email-masked]]
Sent: Wednesday, June 27, 2001 7:52 PM
To: Carlin Covey
Cc: David A. Cooper; [email-masked]
Subject: RE: X.509 Extensions Enhancements

     Carlin:

          Tom Gindin

David,

Regards,

Carlin

-  Carlin Covey
   Cylink Corporation

     -----Original Message-----
     From: [email-masked]
     [mailto:[email-masked]]On Behalf Of David A. Cooper
     Sent: Wednesday, June 13, 2001 6:44 AM
     To: [email-masked]
     Subject: RE: X.509 Extensions Enhancements

     Hoyt,

     Dave

               Charlie Gardiner

          from clause x in 509

             hoyt

---

From: "Carlin Covey" <[email-masked]>
Date: Thu, 28 Jun 2001 08:52:15 -0700

Phil, I concede Tom's point (see my previous email).

And I agree that allowing an arbitrary number of trailing
zero bits is not a DER feature.  However my interpretation
did not involve allowing an arbitrary number.  It involved
encoding exactly the number of bits in the NamedBitList,
regardless of the value of the individual bits.

Yes, I agree that it is not possible for unused bits
to participate in the three-valued logic unless these
bits are at the trailing end of the NamedBitList.  But
the trailing end of the NamedBitList is where newly-defined
Boolean flags are added.

I also agree that the bit string can be extended even using
the "delete all trailing zeros" interpretation.  The issue
is in the application's interpretation of newly added bits.
An application that has been written after some additional
bits were defined in a new version of the standard may encounter
a DER-encoded NamedBitList that was created before these
additional bits were defined.  Under the "delete all trailing
zeros" interpretation, the application cannot determine whether
the issuer of the NamedBitList intended these additional bits
to be 0, or whether the issuer was ignorant of the definition
of these additional bits.  This is the extensibility issue.
The only way out of it with the "delete all trailing zeros"
interpretation is to ensure that the 0 value is a safe default
for all newly defined bits.  This would work OK, unless the
bits must be set in combination with other bits.

I do agree with you that X.690 is a hard read, but I disagree
that it is unambiguous.  Reading the interpretations that appear
in other books may indeed be helpful, but it introduces another
layer of interpretation between the reader and the actual standard.

Regards,

Carlin

-  Carlin Covey
   Cylink Corporation

-----Original Message-----
From: Phil Griffin [mailto:[email-masked]]
Sent: Thursday, June 28, 2001 6:11 AM
To: Tom Gindin
Cc: Carlin Covey; David A. Cooper; [email-masked]
Subject: Re: X.509 Extensions Enhancements

Tom,

With the type definition

Phil

---

From: Phil Griffin <[email-masked]>
Date: Thu, 28 Jun 2001 15:01:59 -0400

> Phil, I concede Tom's point (see my previous email).

Carlin, your previous mail was delayed and only 
arrived at my machine after a subsequent post by
Tom in reply to your post.

> the trailing end of the NamedBitList is where newly-defined

This is currently true for X.509 and the PKIX profile, but
it is not true in general. The example type definition of
"Bits" I provided intended to make this clear. It is not
uncommon to see protocols step over or reserve bits, then
add names for them in later versions.

But perhaps another example would help. Consider in the
time stamp protocol the borrowed type definition used in
ISO WD 18014:

PKIFailureInfo ::= BIT STRING {
   badAlg               (0),
   badRequest           (2),
   badDataFormat        (5),  
   timeNotAvailable    (14),  
   unacceptedPolicy    (15),  
   unacceptedExtension (16),  
   addInfoNotAvailable (17),  
   systemFailure       (25)   
}

Clearly, names for bits 1, 3, 4, etc. that are not
trailing bits could be added to this definition in
a later version of the standard.

> of these additional bits.  This is the extensibility issue.

Creating such a dependence in an ASN.1 application is 
warned against in the ASN.1 standards. Even if BER is 
used there is no way that automatic ASN.1 tools can 
enforce such behavior. A sender can always omit or add
trailing bits in a correct encoding. 

Nothing in a BER encoding relates to named bits. The only
way to tell if the sender obeyed such a protocol would be
to look at the ASN.1 specification the sender used.

> layer of interpretation between the reader and the actual standard.

The more eyes reading the standards the better. There
is of course a formal defect and amendment mechanism 
in place. But any suggested improvements to the text 
or examples in the standards would be well received.

These can be sent to one of the ASN.1 discussion lists,
privately to one of the rapporteurs (Olivier DUBUISSON
<[email-masked]>, John Larmouth 
<[email-masked]>), or directly to the 
ASN.1 standards editor (Paul Thorpe <[email-masked]>).

Now is a perfect time as the group is doing a four year
review to roll all of the defects and amendments made in
the recent past into the base documents. The 2002 review
will take place in Paris the weeks of November 5-16.

Phil Griffin