der: support for the REAL type

[ChristopherRabotin]

Hi there,

I'm seriously considering using your library to encode lots of f64 data (cf. https://github.com/anise-toolkit , and specifically this flatbuffer example: https://github.com/anise-toolkit/specs/blob/1-draft-0-0-1/ephemeris.fbs ).

I'm brand new to ASN.1, so please excuse novice questions. According to a copy of some specs I found here, https://www.oss.com/asn1/resources/books-whitepapers-pubs/larmouth-asn1-book.pdf, section 2.4 (page 83) talks about a REAL type. The ASN.1 playground also uses that type in their default example: https://asn1.io/asn1playground/ .

However, I don't see it in the docs as one of the supported type (https://docs.rs/der/latest/der/asn1/index.html).

Is the REAL type not supported in DER encoding? Or has it not yet been implemented in this library because it isn't needed for the crypto algorithms?

Thanks

[tarcieri]

I am not familiar with a DER encoding of ASN.1 REAL.

DER encodings are intended for cryptographic applications and MUST be canonical. Canonicalizing f64 in general seems like a tricky problem.

You likely want BER instead, which this crate purposefully does not support so as to stay laser-focused on DER.

[ChristopherRabotin]

Interesting. What is the reference you're using for DER so I can make sure to adhere to that?

For those who need this, one can rebuild the floating type as per the specs using the following ASN.1 definition, which looks canonical to me, but maybe I'm missing something:

ANISE DEFINITIONS AUTOMATIC TAGS ::= 
BEGIN
  Normal ::= SEQUENCE       
  {                                                     
     mantissa INTEGER DEFAULT 0,
     realbase INTEGER DEFAULT 10,
     exponent INTEGER (-32..32) DEFAULT 0
  }

Subnormal ::= ENUMERATED {
    plus-infinity,
    neg-infinity
}   

Real ::= CHOICE {
    as_normal Normal,
    as_subnormal Subnormal
}                                                                                                 
END

The following works for the encoding of Pi:

realdata Real ::= as_normal : {
mantissa 3141592653589793,
realbase 2,
exponent 14
}

This works in the playground and is oddly slightly more efficient in the encoding of a Real than the default implementation of the playground.

[tarcieri]

DER is defined in ITU X.690

[ChristopherRabotin]

Section 11.3 specifies DER for Real values. Can we reopen this issue?

[tarcieri]

Okay, sorry I guess I missed that.

If you'd like it implemented you'll have to contribute the implementation yourself. Our use cases are all cryptography, and given that floating point support is very much outside our purview.

[ChristopherRabotin]

Hi. Could you give me some tips on how I would go about starting the implementation of that type? Thanks

[tarcieri]

You can look at the other ASN.1 type definitions here for examples: https://github.com/RustCrypto/formats/tree/master/der/src/asn1

You’ll need to implement the same set of traits as the types in those modules.

[ChristopherRabotin]

Hi there,

I've started the decoding implementation and had a design question I was hoping you could provide some guidance on.

As per the specs of the exponent encoding (below), it seems to me that the exponent can be encoded on several octets/bytes. However, the IEEE 754 standard (as implement in Rust as f64) only supports 11 bits of exponent.

Question: how would you prefer this to be designed?

1. One way would be to return an error if the exponent cannot be encoded on the 11bit allowed by IEEE-754. If that's the recommendation, do you know what's the simplest way to rebuild the bytes from the sign bit, the exponent, and the mantissa?
2. Another way would be to convert each component as an f64 and then call powf on that f64 and multiply that result with the other parts of the value. The main problem here is that der is no-std and therefore rustc does not allow me to use powf. Further, off the cuff, this seems like a waste of operations because if the exponent does not fit in the 754 format, then why even go further since, at the very best, we'll have a totally different number stored.

Looking forward to reading your advice, thanks.

[tarcieri]

One way would be to return an error if the exponent cannot be encoded on the 11bit allowed by IEEE-754. If that's the recommendation, do you know what's the simplest way to rebuild the bytes from the sign bit, the exponent, and the mantissa?

You should be able to construct a u64 with the desired bit representation and then use f64::from_bits to safely transmute it to a float.

[ChristopherRabotin]

How do you understand section 8.5.8? The ISO 6093 NR3 format seems to me like a string representation of a floating point value (cf. page 7 of this PDF). I would be immensely surprised if that's what ASN.1 had in mind for a base 10 encoding given how optimized the base 2 encoding is. Further, from section 2.4 of this PDF, the general idea of ASN.1 real encoding is to encode the value on three integers {x, y, z} such that value = x * (y^z), where y is either 2 or 10 in DER.

Thanks for your help

[tarcieri]

There's some discussion of the BER encoding here:

https://stackoverflow.com/questions/4975005/how-should-i-interpret-the-asn-1-ber-standard-for-reals

It indeed does appear to be a string encoding. That's not too far off from the encoding of types like UTCTime and GeneralizedTime.

It appears that 1.0 is encoded as:

[0x09, 0x08, 0x03, '+', '1', '.', '0', 'e', '+', '0']

[ChristopherRabotin]

Two questions:

1. For the decimal decoding, is it OK if the NR3 decoding is only supported if the std feature is enabled?
2. To actually encode the value, I understand I need to implement the encode_value function and provide the byte slice. Should this include the tag as well? How would you recommend I set the sign and exponent length data as those also go in the first byte of the encoding?

Thanks

[tarcieri]

Re 1) I suppose it's OK although I'm not sure how or why you'd need std? How does it help writing a decoder?

Re 2) EncodeValue operates on the value portion of a TLV record. You don't need the tag or length: it will automatically be computed by the blanket impl of Encode.

[ChristopherRabotin]

1. Yes, with std I can directly call from_utf8 and mystr.parse::<f64>() instead of writing a parser of the bytes to str and converting that to a double.
2. Okay, thanks. With a bit of luck I'll have a basic implementation done soon then.

[tarcieri]

str::from_utf8 is available in core: https://doc.rust-lang.org/beta/core/str/fn.from_utf8.html

There's already a no_std-friendly wrapper type which can be used for decoding/encoding strings as well:

https://github.com/RustCrypto/formats/blob/master/der/src/str_slice.rs

[ChristopherRabotin]

Just open the merge request #346 . I tried to squash my commits but it seems like that failed, sorry.

As mentioned in the description, I'd like a hand to make sure I interpret section 11.3.1 correctly.

From what I understand, the implementation should ensure that the mantissa is chosen such that it is zero (not just an even number) or and odd number by shifting the mantissa values to the right (dividing by two) and increasing the exponent by that same number. But how does that make sense? The exponent value is directly tied to the mantissa, and, unless I'm mistaken, there truly is only one way to arrange the bit in an IEEE-754 to make a given value. In fact, a quick demo in the playground seems to show that as well.

What am I misunderstanding in this section (below for reference)?

Thanks for your continued help.

Edit

I might have understood the idea: if the mantissa is neither zero nor is odd, then shift the mantissa by 1 and store that shift, not in the exponent, but in the scaling factor from section 8.5.7. This scaling factor can then be used to correctly recreate the floating point values (using the same tests as in the current proposed code change). Section 11.3.1 says that the scaling factor should never be stored in the mantissa itself, but I don't see anything with respect to storing it in the scaling factor field.

The diff is simply the following:

diff --git a/der/src/asn1/real.rs b/der/src/asn1/real.rs
index 7baa57f..a7f16ed 100644
--- a/der/src/asn1/real.rs
+++ b/der/src/asn1/real.rs
@@ -118,7 +118,14 @@ impl EncodeValue for f64 {
                 first_byte |= 0b0100_0000;
             }
 
-            let (_sign, exponent, mantissa) = integer_decode_f64(*self);
+            let (_sign, exponent, mut mantissa) = integer_decode_f64(*self);
+            // Check that the mantissa is either zero or odd
+            if mantissa % 2 == 0 && mantissa != 0 {
+                // Shift by one, store that as scaling factor
+                mantissa >>= 1;
+                first_byte |= 0b0000_0100;
+                assert!((mantissa % 2 == 0 && mantissa != 0) || (mantissa % 2 == 1));
+            }
             // Encode the exponent as two's complement on 16 bits
             let exponent_bytes = (exponent as i16).to_be_bytes();
             // If the exponent is encoded only on two bytes, add that info

That said, I don't quite understand the benefit of this method: it still requires just as much room to store the double as before.

Specs

[ChristopherRabotin]

@tarcieri hi Tony, I was wondering if there was anything I could do to help review and merge this work? It seems like the ASN1CC compiler might support the Real type, but I don't know if it's a BER, DER, or some other norm that's used there.