[Cryptography] BitCoin bug reported

[Peter Gutmann]

Theodore Ts'o <tytso at mit.edu> writes:

>However, I still have a philosophical dislike of complex encoding schemes
>such as ASN.1 which allow for arbitrary optional fields and optional data
>structures, because it encourages protocol complexity.  If you have a
>protocol message with a dozen different optional fields, the combinatorics
>mean that you have at least 4096 test cases to write if you are doing black
>box testing, and that's just testing the presence or absence of the optional
>fields, ignoring tests based on the value of those fields if they are
>present.

This is the big problem with ASN.1.  It's actually a relatively simple, clean
encoding, but it's applied by... well, by the sort of people who gave us
X.509.  So you get monstrosities like:

  For example consider the use of a DN in an IssuingDistributionPoint
  extension, which begins:

  IssuingDistributionPoint ::= SEQUENCE {
    distributionPoint [0] DistributionPointName OPTIONAL,
    ...
    }

  DistributionPointName ::= CHOICE {
    fullName [0] GeneralNames,
    ...
    }

  GeneralNames ::= SEQUENCE OF GeneralName

  GeneralName ::= CHOICE {
    ...
    directoryName [4] Name,
    ...
    }

  Name ::= CHOICE {
    rdnSequence RDNSequence
    }

  RDNSequence ::= SEQUENCE OF RelativeDistinguishedName

  RelativeDistinguishedName ::= SET OF AttributeTypeAndValue

                    [It] was of a baroque monstrosity not often seen outside
                    the Maximegalon Museum of Diseased Imaginings.
                        -- Douglas Adams, "The Restaurant at the End of the
                           Universe"

  Once we reach AttributeTypeAndValue we finally get to something which
  contains actual data - everything before that point is just wrapping.

  Now consider a typical use of this extension, in which you encode the URL at
  which CA information is to be found.  This is encoded as:

  SEQUENCE { [0] { [0] { SEQUENCE { [6] "http://.." } } } }

  All this just to specify a URL!

                    It looks like they were trying to stress-test their ASN.1
                    compilers.
                        -- Roger Schlafly on stds-p1363

                    It smelled like slow death in there, malaria, nightmares.
                    This was the end of the river alright.
                        -- Captain Willard, "Apocalypse Now"

The problem isn't the encoding, it's how it's used.  Give the folks who
dreamed up the above JSON, or anything else for that matter, and they'll make
a similar mess.  So I'm not sure if the Sapir-Whorf hypothesis entirely
applies to ASN.1, it's powerful enough to give you all you need to build the
most godawful mess, and it's usually applied that way, but when used correctly
you end up with a simple, clean encoding.

>Of course, Bitcoin managed to create an overly complex encoding scheme
>without using ASN.1, which just goes to show that you can write Fortran in
>any language.  :-/

Exactly.  If you look at some of the extensions used with TLS you can
immediately see which ones were created by X.509ers because they've emulated
the sort of mess you'd usually see done in ASN.1 in TLS' ad-hoc encoding. This
makes the whole thing twice as bad, you now have an ASN.1-style mess combined
with the need to hand-code a TLS ad-hoc parser for it.

The downside with ASN.1, admittedly, is that it makes it easier than most
notations to create such a mess :-(.

Peter.