Think about Rustls

[RossSmyth]

Compiling this crate from source is not a good experience, mainly because of OpenSSL and it's silly Perl building requiment. I would at least think about using Rustls so it is more easily portable. Looking at the source it is mainly limited to one function it seems so this may be doable, but I am no expert.

[triska]

The openssl crate is currently only needed to perform a single operation: scalar multiplication of a point on one of two elliptic curves. This is used by crypto_curve_scalar_mult/4 in Scryer Prolog's library(crypto).

It seems the rustls crate does not expose this specific operation as one of its functions. I have looked at dozens of other crates in the repository, and found none of them besides openssl that lets us securely perform this fundamental operation on elliptic curves.

Maybe someone in the Rust community can be convinced to add a crate that does it, at least for secp256k1, then we can finally get rid of this highly inconvenient dependency!

[triska]

The newly announced crrl library by @pornin may be a good candidate to resolve this issue, once support for secp256k1 is added.

[infogulch]

crrl library looks interesting.

Rust library for cryptographic research

I'm curious what crypto_curve_scalar_mult/4 is used and useful for. Is it common to use directly? Most cryptography is done via libraries and protocols that have it built-in.

[triska]

One application that comes to mind is Bitcoinolog, which uses crypto_curve_scalar_mult/4 to create Bitcoin public keys and addresses.

It is true: If you need only an encrypted network connection, you can simply use the predicates from library(tls) to negotiate it automatically, and you do not have to manually perform this operation on elliptic curves. Still, it is useful to provide this functionality, for example to enable the following use cases:

• verification and testing of cryptographic protocols
• Prolog-based implementations of further cryptographic protocols (other than TLS) that use this building block
• educational use cases, such as explaining individual steps of ECDH key exchange
• using Scryer Prolog for research and reasoning about elliptic curves
• etc.

[RossSmyth]

I do not know cryptography very well but maybe this could work
https://github.com/RustCrypto/elliptic-curves
Or something else in RustCrypto

[triska]

Thank you, well spotted! I took a look specifically at RustCrypto's k256 crate since it implements secp256k1 which is needed for Bitcoinolog.

It seems the crate almost provides the intended functionality, but again lacks elementary functionality, such as getting not only the X but also the Y coordinate of an affine point.

The operation I need is the most frequently needed and most basic operation on elliptic curves:

Given a scalar s and a point P on the elliptic curve, I need to compute s·P and obtain the coordinates X and Y of the result.

The openssl crate, for all its horrible API, at least lets us implement this elementary operation with some implementation effort. From the k256 documentation, I guess that the following few lines almost perform the intended functionality:

        let mut point = AffinePoint::from_bytes(&qbytes).unwrap();
        let s = Scalar::from_str_vartime(&scalar.to_string()).unwrap();
        let result = point.mul(s);

So we have result as an AffinePoint, and we can use the API to get the X coordinate, but not the Y coordinate.

It would be great to have an actual Rust-based cryptographic library, which uses the built-in Rust data structures to represent integers, points etc. All these redundant, badly documented, and error-prone conversions between bytes, strings and cryptic formats are extremely frustrating to use. An ideal Rust crate would provide s·P as a multiplication of a Rust integer s and a point P and result whose coordinates are easy to reason about within Rust.

[Skgland]

RustCrypto/elliptic-curves#621 appear to implement a trait/method with the missing conversion

[infogulch]

I think there are reasonable objections to exposing raw cryptographic primitives to userspace in general. Secrecy breaking operations are littered left and right. For example, an implementation using pure Rust would have no way to ensure the absence of optimizations that are conditional on the contents of the encrypted payload, exposing all users to timing-based attacks depending on arbitrary compiler optimizations that are present now or any time in the future. Thus assembly-based implementations (e.g. asm! or extern fn) are preferred. There are many such unintuitive ways to break cryptographic designs.

These concerns are not theoretical and such attacks are surprisingly simple to pull off. Cryptopals publishes a great self-learning course in the form of progressive challenges that teach you how to break many cryptographic designs that were in public use at some point in the past. What I learned working through these challenges is that designing a cryptographic system directly on top of primitives that is suitable for a specific application and is not vulnerable is shockingly subtle.

That said, I haven't studied this implementation in depth so I'm not comfortable commenting on it directly.

Besides RustCrypto/elliptic-curves#621 : p256: Allow converting affine points to coordinates and back mentioned by Skgland, there is also a related discussion: zkcrypto/group: Add traits and APIs for dealing with curve coordinates #30.

[triska]

Well, to use these cryptographic APIs, I have to perform a very basic operation: Translate an integer I have available in Rust to one of the formats that these crates require. This basic operation will always be needed, no matter how obscure and hard it is for application programmers.

I have now tried, and failed, to perform this basic operation, and did not succeed. What I currently have for crypto_curve_scalar_mult in system_calls.rs is:

    pub(crate) fn crypto_curve_scalar_mult(&mut self) {
        let curve = cell_as_atom!(self.machine_st.registers[1]);

        match curve {
            atom!("secp256k1") => { }
            _ => {
                unreachable!()
            }
        };

        let stub_gen = || functor_stub(atom!("crypto_curve_scalar_mult"), 5);

        let sbytes = self.machine_st.integers_to_bytevec(self.machine_st.registers[2], stub_gen);
        let s = Scalar::from_repr(sbytes).unwrap();

        let qbytes = self.machine_st.integers_to_bytevec(self.machine_st.registers[3], stub_gen);

        let mut q = AffinePoint::from_bytes(&qbytes).unwrap();
        let result = q.mul(s);

        let enc = result.to_encoded_point(false);
        let x = enc.x().unwrap();
        let y = enc.y().unwrap();

        let sx = {
            let buffer = String::from_iter(x.as_ref().iter().map(|b| *b as char));

            if buffer.len() == 0 {
                empty_list_as_cell!()
            } else {
                atom_as_cstr_cell!(self.machine_st.atom_tbl.build_with(&buffer))
            }
        };

        let sy = {
            let buffer = String::from_iter(y.as_ref().iter().map(|b| *b as char));

            if buffer.len() == 0 {
                empty_list_as_cell!()
            } else {
                atom_as_cstr_cell!(self.machine_st.atom_tbl.build_with(&buffer))
            }
        };

        unify!(self.machine_st, self.machine_st.registers[4], sx);
        unify!(self.machine_st, self.machine_st.registers[5], sy);
    }

This fails to compile with 2 errors:

error[E0599]: no function or associated item named `from_repr` found for struct `k256::Scalar` in the current scope
    --> src/machine/system_calls.rs:6128:25
     |
6128 |         let s = Scalar::from_repr(sbytes).unwrap();
     |                         ^^^^^^^^^ function or associated item not found in `k256::Scalar`

and also:

6132 |         let mut q = AffinePoint::from_bytes(&qbytes).unwrap();
     |                                  ^^^^^^^^^^ function or associated item not found in `AffinePoint`

I do not know why these occur. I see from_repr in the source code of the crate. I think I saw from_bytes somewhere in one of the documentations.

My impression of this crate is that essential functionality is either not available or not sufficiently documented at the moment: Essential functions are either not available, or require translations between several cryptic formats.

I hope someone is interested to help in this area. The overall functionality that is required here is pretty basic: Multiply a point on the curve by an integer, and get the result to Prolog.

[tarcieri]

It seems the crate almost provides the intended functionality, but again lacks elementary functionality, such as getting not only the X but also the Y coordinate of an affine point.

The decision not to expose the y-coordinate is very much deliberate, as y-coordinate access is implicated in the most common attack against elliptic curve libraries: invalid curve attacks.

There is some ongoing discussion here as to how to safely expose raw coordinate access: zkcrypto/group#30

In the meantime, as a workaround you can obtain an uncompressed SEC1-encoded point and access its y-coordinate if you pass false as the compress argument to https://docs.rs/k256/latest/k256/struct.AffinePoint.html#method.to_encoded_point

[triska]

Thank you a lot! Quoting from https://safecurves.cr.yp.to/twist.html regarding invalid curve attacks:

An ECC implementor can stop an invalid-curve attack by checking whether the input point Q satisfies the correct curve equation; this does not take much time, and it guarantees that Q is on the original curve.

Such a check seems to be a much more reliable safety measure than not exposing the Y coordinate, which, it turns out, can be obtained after all in another way.

Later in the document, we find:

A protocol designer can help protect against this attack by specifying point compression.

This again seems to be a much better choice: Specify point compression in the protocol. I do not regard this a a good argument for obscuring such basic functionality as obtaining (not even: specifying) the coordinates of a point.

[tarcieri]

We of course check that any inputs satisfy the curve equation. The issue is less our implementation, which uses modern complete addition formulas, and rather other legacy implementations which don't. And in fact, if you can solve the curve equation, you don't need the full y-coordinate and can solve for it instead: that's how point decompression works, which is a strategic approach to eliminating invalid curves as a bugclass.

Just a general note: the SafeCurves site is very much out-of-date and does not represent the state-of-the-art, especially when it comes to prime order curves. There have been several developments in the past decade which that site does not mention or adequately provide context for.

Anyway, this is one of the biggest hot-button issues in all of our crates. There is a tradeoff between providing misuse-resistant APIs and "power user APIs" which we are trying to walk delicately. There's already been ample discussion about it I suggest you familiarize yourself with.

Please see this issue and leave any relevant comments there: zkcrypto/group#30

To quote that issue:

dealing in coordinates directly is almost always incorrect for cryptographic protocols, so we didn't expose them

[triska]

We currently already have this functionality, so I am not particularly interested in ample discussion about how to obtain the coordinate of a point.

If a crate appears that readily provides this elementary operation, I will immediately use it, so that we can get rid of the current dependency on OpenSSL.

[tarcieri]

The OpenSSL example appears to be using the SEC1 encoding. As I already noted, that's fully supported by k256 via the FromEncodedPoint and ToEncodedPoint traits.

Passing compress: false to to_encoded_point will additionally serialize the y-coordinate.

The default encoding is compressed (which omits the full y-coordinate), as the secp256k1 ecosystem uses compressed points almost exclusively.

[triska]

I have published what I have so far in the rust-crypto branch:

https://github.com/triska/scryer-prolog/tree/rust-crypto

In particular, the following commit attempts to use k256 instead of OpenSSL:

triska@98f1efd

I get the mentioned compilation errors. I have looked at the diagrams in zkcrypto/group#30 (comment), and I have looked at the source of the crate, and I am at a loss on how to perform this basic operation: Given a Prolog integer and a point on the elliptic curve (specified in affine coordinates, using Prolog integers), obtain the X and Y coordinates of the scalar multiplication. That's all I want to do. I tried to look up the SEC1 encoding in the 144 page document which I assume contains the specification: https://www.secg.org/sec1-v2.pdf.

Prolog and Rust interact with this internal predicate: https://github.com/triska/scryer-prolog/blob/98f1efd214860cec1a964cf5950b4415e2c7dcd6/src/lib/crypto.pl#L767

Please note that not all use cases of elliptic curves are cryptographic: Someone may want to perform the scalar multiplication and look at the resulting point for reasons that are completely unrelated to cryptography.

I would dearly appreciate help from other contributors to make this work. Thank you a lot!

[tarcieri]

Scalar::from_repr is documented here: https://docs.rs/k256/latest/k256/struct.Scalar.html#trait-impls

You need to import the PrimeField trait in order to use it, as the documentation describes.

For AffinePoint, as I mentioned earlier you'll need to use the FromEncodedPoint and ToEncodedPoint traits, which work with the SEC1 encoding (which is the standard point encoding used with practically all prime order elliptic curves). Again, make sure to pass compressed: false to to_encoded_point in order to ensure the y-coordinate is present.

The EncodedPoint::coordinates method can be used to obtain the coordinates.

[triska]

I tried to import this trait in triska@766ffa6, and now the entire compilation crashes:

$ cargo build --release
   Compiling scryer-prolog v0.9.0 (/Users/triska/scryer-prolog)
error: failed to run custom build command for `scryer-prolog v0.9.0 (/Users/triska/scryer-prolog)`

Caused by:
  process didn't exit successfully: `/Users/triska/scryer-prolog/target/release/build/scryer-prolog-4c9b496aa1684afc/build-script-main` (exit status: 101)
  --- stdout
  rustfmt 1.4.38-stable (e092d0b6 2022-07-16)

  --- stderr
  thread 'main' panicked at 'parse error: expected `,` in file "src/machine/system_calls.rs"', build/static_string_indexing.rs:124:17
  note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
make: *** [all] Error 101

Maybe the import was not done correctly?

[str4d]

I am very concerned by these lines of the predicate:
https://github.com/triska/scryer-prolog/blob/98f1efd214860cec1a964cf5950b4415e2c7dcd6/src/lib/crypto.pl#L763-L766

It appears that what is going on here is:

• The base point is provided as point(X, Y).
• The predicate manually encodes these into an undocumented uncompressed hex encoding.
• The hex-encoded uncompressed base point is passed through to the underlying crypto_curve_scalar_mult helper.
• The predicate expects that helper to return coordinates for the resulting point.

It seems to me like this has a problematic abstraction mismatch. The underlying crypto_curve_scalar_mult helper should consume and return points in a uniform manner. If the base point is passed over in (some kind of) uncompressed form, then the resulting point should be returned the same way. That leaves the predicate responsible for handling all of the logic for encoding and decoding between how the helper method represents points, and how the library(crypto) represents them with the term point(X, Y) (I don't know enough about Prolog to know if this term is opaque or if it exposes the coordinates; the latter seems like a very error-prone API as it allows for invalid points to be constructed).

[str4d]

Maybe the import was not done correctly?

@triska you've imported the trait correctly. This seems more like a bug in build/static_string_indexing.rs, especially given that the line it is erroring on does indeed have a , in it.

[triska]

@str4d: Our goal in this issue is to replace the way this is currently done with a method that does not depend on OpenSSL, and ideally also uses a much better API.

All crates currently under discussion in this issue suffer from this dramatic abstraction mismatch: As a Rust programmer, I would like to use Rust integers to represent integers. Yet, I am forced to use completely different encodings by these crates.

I prefer to write any necessary conversions to the greatest possible extent in Prolog, because I want to keep as much as possible of the implementation in Prolog.

[triska]

Regarding the point representation: In library(crypto), the Prolog term point(X,Y) represents an affine point. You can construct such terms by simply writing them down, and you can freely inspect them.

Scalar multiplication only works for points that are on the curve, library(crypto) checks for this: https://github.com/triska/scryer-prolog/blob/98f1efd214860cec1a964cf5950b4415e2c7dcd6/src/lib/crypto.pl#L761

[str4d]

All crates currently under discussion in this issue suffer from this dramatic abstraction mismatch: As a Rust programmer, I would like to use Rust integers to represent integers. Yet, I am forced to use completely different encodings by these crates.

Then you will be left wanting. There are no Rust integers that can represent cryptographically-relevant fields, as Rust does not have native big integer support like e.g. Python (or I presume Prolog), and the largest native integer size is a u128 which is too small to represent the 255- or 256-bit fields used by these curves.

The point encodings provided by the Rust crates in question are developed for the specific use case of safe production usage in cryptographic protocols; it is therefore natural and expected that they will bake in security precautions that a library solely interested in "reasons unrelated to cryptography" (as you put it) may not require.

I prefer to write any necessary conversions to the greatest possible extent in Prolog, because I want to keep as much as possible of the implementation in Prolog.

Then indeed, there is no need for the Rust code to deal directly in coordinates at all, as you say you want the conversions to be implemented in Prolog. @tarcieri has already specified above how you should go about this. To re-iterate:

• Take the base point in point(X, Y) form.
• Encode it in whichever point encoding format you want to use to communicate with Rust (e.g. the SEC1 uncompressed point encoding format).
• Pass this to a helper method that consumes and produces the encoding format you chose above, performing the scalar mul in between.
• Parse the result from whichever point encoding format you chose above to obtain the result's coordinates.
• Return the result in point(RX, RY) form.

[triska]

Scryer Prolog uses the num crate for big integers, so there will always be this mismatch.

If someone is interested in writing these conversion functions, please do, thank you a lot.

[triska]

I have filed #1600 to eliminate the extremely inconvenient OpenSSL dependency of library(crypto), using the newly available crrl crate by @pornin. I hope this finally resolves this issue once and for all.

[triska]

This change is now available in master and the newly released version 0.9.1, and I think that resolves this issue?