Re: Binary Encoding for Crypto-conditions

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
<https://play.google.com/store/apps/details?id=org.thoughtcrime.securesms&hl=en>:
+1650-862-5992
Public Key
<https://raw.github.com/zmanian/pub_keys/master/gpg/%3Czaki@manian.org%3E.public.gpg-key>

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

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