Subject: RE: Best practice for data encoding?

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 06 Jun 2006 15:00:11 -0400

On Tuesday, June 06, 2006 11:55:15 AM -0700 "Hallam-Baker, Phillip" 
<[email-masked]> wrote:

>
>> From: Jeffrey Hutzelman [mailto:[email-masked]]
>
>> To be pedantic, ASN.1 is what its name says it is - a notation.
>> The properties you go on to describe are those of BER; other
>> encodings have other properties.  For example, DER adds
>> constraints such that there are no longer multiple ways to
>> encode the same thing.  Besides simplifying implementations,
>
> Hate to bust your bubble here but DER encoding is vastly more complex
> than any other encoding. It is certainly not simpler than the BER
> encoding.

It's a subset, in fact.  All DER is valid BER.

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

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Tue, 6 Jun 2006 11:55:15 -0700

> encode the same thing.  Besides simplifying implementations, 

Hate to bust your bubble here but DER encoding is vastly more complex than any other encoding. It is certainly not simpler than the BER encoding.

The reason for this is that in DER encoding each chunck of data is encoded using the definite length encoding in which each data structure is preceded by a length descriptor. In addition to being much more troublesome to decode than a simple end of structure market such as ), }, or </> it is considerably more complex to code because the length descriptor is itself a variable length integer.

The upshot of this is that it is impossible to write a LR(1) encoder for DER encoding. In order to encode the structure you have to recursively size each substructure before the first byte of the enclosing structure can be emitted.

> this also makes it possible to compare cryptographic hashes 
> of DER-encoded data; X.509 and Kerberos both take advantage 
> of this property. 

I am not aware of any X.509 system that relies on this property. If there is such a system they certainly are not making use of the ability to reduce a DER encoded structure to X.500 data and reassemble it. Almost none of the PKIX applications have done this properly until recently.

X.509 certs are exchanged as opaque binary blobs by all rational applications. 

> > Then there are MACRO definitions, VALUE specifications, and an even 
> > more complex definition of extension capabilities. In 
> short, ASN.1 is 
> > vastly more complex that the average TLV encoding. The 
> higher rate of 
> > errors is thus not entirely surprising.
> 
> There certainly is a rich set of features (read: complexity) 
> in both the
> ASN.1 syntax and its commonly-used encodings.  However, I 
> don't think that's the real source of the problem.  There 
> seem to be a lot of ad-hoc
> ASN.1 decoders out there that people have written as part of 
> some other protocol, instead of using an off-the-shelf 
> compiler/encoder/decoder; 

That's because most of the off the shelf compiler/encoders have historically been trash.

Where do you think all the bungled DER implementations came from?

> I also suspect that a number of the problems found have 
> nothing to do with decoding ASN.1 specifically, and would 
> have come up had other approaches been used.  For example, 
> several of the problems cited earlier were buffer overflows 
> found in code written well before the true impact of that 
> problem was well understood.  

Before the 1960s? I very much doubt it.

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 6 Jun 2006 23:08:05 +0200

On Jun 06 2006, at 20:55 , Hallam-Baker, Phillip wrote:

>> There

Of course, the interesting question is: why is that so?

Needless complexity makes it hard to build such a tool, so a great  
one becomes less likely to be written.
Needless complexity has the interesting effect of turning off the  
more brilliant implementers, so implementations are more likely to be  
written by second-rate coders.
Also, needless complexity means that the resulting tool will be  
heavyweight, even more so as the complexity sucks off energy that  
could have been put into streamlining the implementation;  
implementers are going to consider this in their make-or-take  
decisions and prefer to roll their own (and create bugs).

That's one set of reasons.
The other reason is that with some kinds of formal standardization,  
there is an interesting non-technical effect:
People suddenly think they can make money off the standard (itself,  
as opposed to off the market created by the standard, which is the  
economic purpose of all standardization).
In the implementation space, this leads to a fragmentation of efforts  
-- instead of one focused open-source implementation, there are  
likely to be multiple "commercial" ones.
The more insidious effect is that suddenly, there is an incentive to  
add even more needless complexity to create barriers of entry to the  
implementation market.
(Or, at least, to create enough complexity to secure a thriving  
consulting market for the people doing the standardization -- a kind  
of trapdoor function.)

Example directly pertinent to this discussion:
It has been claimed that ASN.1 PER was created to ensure the health  
of a company trying to dominate the ASN.1 implementation market.
The company appears to have been quite successful for a while.
(They also pretty much single-handedly killed dependent standards  
like H.323 in the process, not the least because their dominating  
implementation actually was flawed as well.)

Of course, many of us are seeing this effect all the time in all  
kinds of standards development, including the IETF.
It has to be actively, consciously fought every day, or it will  
dominate.
Look up Mancur Olson's "The Rise and Decline of Nations" and Carlo  
Cipolla's excellent summary "Basic Laws of Human Stupidity" (we are  
talking about type "B2" or "Bs" here) for some pertinent political/ 
economic theory.

Gruesse, Carsten