W3C home > Mailing lists > Public > public-interledger@w3.org > March 2016

Re: Binary Encoding for Crypto-conditions

From: <zaki@manian.org>
Date: Wed, 30 Mar 2016 11:45:01 -0700
Message-ID: <CAJQ8TmDrsuWru7+5rtsSExQOrLogGTdpaGn6nMzt3P8dNFwMFA@mail.gmail.com>
To: Melvin Carvalho <melvincarvalho@gmail.com>
Cc: Stefan Thomas <stefan@ripple.com>, Interledger Community Group <public-interledger@w3.org>
I'm surprised how much I like ASN.1 OER.

Our basic goals should be

- Implementers should be able to use existing parser implementations as
much as possible
- The protocol designer to should minimize the risk to implementers in
non-memory safe languages of out of bounds buffer accesses and overflows. I
believe this one of the design goals with protocol buffers. Looks like it
was also a goal of ASN.1 OER

Things we probably couldn't consider goals

- Constant time parsing and evaluation

I think ASN.1 OER is the closest to the design goals of what we've
considered since proper ProtoBufs were never on the table.

Text Secure
Public Key

On Tue, Mar 29, 2016 at 11:54 PM, Melvin Carvalho <melvincarvalho@gmail.com>

> On 30 March 2016 at 04:36, Stefan Thomas <stefan@ripple.com> wrote:
>> Currently, our spec for cryptoconditions uses a totally custom binary
>> format inspired by protocol buffers.
>> Before we went any further, I wanted to stop and consider whether there
>> is a better format that we can use. So with this email I want to share my
>> research and recommendation.
>> TL;DR We can get most of the awesomeness of ASN.1 without any of the suck
>> of DER, by using ASN.1 with OER, which incidentally is very similar to our
>> current custom format. (For instance, the encoding for 0-127 byte long
>> VARBYTES is identical.)
> Perhaps consider?
> https://www.w3.org/Submission/2011/SUBM-HDT-20110330/
> I've not personally used it, so cant vouch for it, but looks promising.
>> First off, what type of binary format are we looking for?
>> It should be:
>> - Canonical (one correct way to encode things)
>> - Reasonably simple to implement
>> - Unlikely to cause bugs
>> - Well defined with good documentation
>> - Compact
>> - Fast to encode/decode
>> - Standard
>> What formats are out there?
>> - ASN.1 BER/DER (X.690) - This is what most crypto uses today. However,
>> to quote Tony, it is "almost universally reviled among implementers." It's
>> relatively inefficient size-wise. Probably my biggest gripe with it is that
>> it doesn't support unsigned integers, which is just annoying and a common
>> source for bugs. [1]
>> - ASN.1 PER (X.691) - Super-densely packed encoding. Used for mobile
>> communications etc.
>> - ASN.1 OER (X.696) - One of the newest ASN.1 Encoding Rules. Optimized
>> for very fast encoding/decoding, simplicity and small size (not as small as
>> PER, but smaller than BER/DER.)
>> - ASN.1 ECN (X.692) - Basically: Use ASN.1, but define your own encoding
>> rules or change existing ones in any way you like.
>> - RLP - Used by Ethereum. Not a standard, but very minimal.
>> - XDR (RFC 4506) - Similar idea as ASN.1, but there aren't as good of
>> tools available. For instance, I couldn't find a generic web-based XDR
>> encoder/decoder playground.
>> Notable mentions:
>> - Macaroons is working on a custom format, but it seems very specific to
>> their use case. [3]
>> After looking at these options, I noticed that ASN.1 sticks out as being
>> very widely adopted in industry. It is used in many crypto standards
>> including PKCS and X.509, but it also powers network protocols like SNMP,
>> LDAP and H.323, cellphone networks (from GPRS all the way up to LTE) and
>> even aerospace telecommunication networks.
>> I noticed that there are lots of tools available for ASN.1 - I downloaded
>> a free Eclipse-based ASN.1 editor [4] which would validate my syntax
>> definitions in real time and color them nicely. Then I could take my syntax
>> definition and paste it into the ASN playground [5] which would instantly
>> encode examples in DER, PER, XER and OER so I could see what they look
>> like. It is awesome to have that sort of tooling available both for this
>> spec and for future extensions.
>> If you're interested to learn more about ASN.1, I can highly recommend
>> these slides: [8]
>> The ability to autodetect inconsistencies in the spec and to generate
>> examples without relying on the reference implementation you're trying to
>> test has been incredibly helpful for me. And using a standardized protocol
>> makes sense because then we can keep our spec purely about
>> crypto-conditions instead of having to define some new binary format as
>> well. Because of these reason, ASN.1 seems like the way to go, but which
>> encoding should we use?
>> PER is too complicated and we don't need that level of packing. We do
>> want it to be a canonical encoding, so that leaves DER, CANONICAL-OER or
>> something custom with an ECN description.
>> DER has the advantage that there are implementations for a lot of
>> languages. But it is relatively complicated and inefficient.
>> OER is very fast to encode/decode [6] and easy to implement. [7] There
>> aren't as many existing implementations, but because it's so simple and so
>> close to our previous format - which we were already writing parsers for -
>> we don't really lose anything. Also, there is very little I'd want to
>> change about OER, so I think we should just use it as is, without any
>> ECN-type customizations.
>> So based on my research, I would recommend ASN.1 with OER as the binary
>> format for crypto-conditions.
>> I'm happy to start working on a pull request to update the spec and code,
>> but please let me know if you have any other information regarding binary
>> encoding that I missed.
>> Big thanks to Tony Arcieri for comments on DER and pointing out the
>> Macaroons effort and Jehan Tremback for pointing out the RLP format.
>> [1]
>> http://stackoverflow.com/questions/12860226/oddity-when-encoding-large-integers-using-asn-1
>> [2] https://github.com/ethereum/wiki/wiki/RLP
>> [3] https://github.com/rescrv/libmacaroons/blob/master/doc/format.txt
>> [4] http://www.asnlab.org/asndt/overview
>> [5] http://asn1-playground.oss.com/
>> [6]
>> https://www.researchgate.net/publication/275249582_Performance_Analysis_of_Existing_16092_Encodings_v_ASN1
>> [7]
>> http://www.oss.com/asn1/resources/books-whitepapers-pubs/Overview%20of%20OER.pdf
>> [8]
>> http://www.ieee802.org/802_tutorials/2010-11/Alessandro%20Triglia%20-%20ASN.1%20Tutorial%20Dallas%20-%2020101108T1701.pptx
Received on Wednesday, 30 March 2016 18:45:52 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 30 March 2016 18:45:52 UTC