BUG. Defective RIST255_MULT and RIST255_MULBASE implementations.

[dta90d]

Hello!

I think I've stumbled upon a bug in implementation of Ristretto scalar multiplication.

For some reason the n parameter (Scalar) is being preprocessed like that:

ton/crypto/vm/tonops.cpp

Line 830 in eed3153

auto n = stack.pop_int() % get_ristretto256_l();

ton/crypto/vm/tonops.cpp

Line 860 in eed3153

auto n = stack.pop_int() % get_ristretto256_l();

Value of get_ristretto256_l() (l onwards) is 2^252 + 27742317777372353535851937790883648493 so that means that if the Scalar passed is less than l it goes directly in n (n == scalar_passed) and thus we get correct results, but if Scalar is equal or greater than l we end up with some small value in n and thus get wrong final results.

Here's a real-life example of what we should get (tested via curve25519_dalek, code below) and what we get in reality from TVM.

Let's take some point on a curve X and Scalar n that is greater than l where:

X = 0xf245308737c2a888ba56448c8cdbce9d063b57b147e063ce36c580194ef31a63
n = 0xd32fcc5ae91ba05704da9df434f22fd4c2c373fdd8294bbb58bf27292aeec00a

The results we should get are (B being RISTRETTO_BASEPOINT):

X * n = 0x5e727d972b11f6490b0b1ba8147775bceb1a2cb523b381fa22d5a5c0e97d4744 // MUL
B * n = 0x9a30709d72de12d67f7af1cd8695ff16214d2d4600ae5f478873d2e7ed0ece73 // MULBASE

But when processed through TVM we get different results:

PUSHINT 109581956733909874354130828266673789621712875798453783900027869828650322041443 // X
PUSHINT 95522463270312866099681725115318615928183786721526257398762142880656593436682 // n
RIST255_MUL // => 86949080096112004834615039891007688035110909213144700491546856921768921685808 == 0xc03b6f72e4205f5da1a7b1f8028c04927fe3558d6186050889c85a4c01085f30

PUSHINT 95522463270312866099681725115318615928183786721526257398762142880656593436682 // n
RIST255_MULBASE // => 19216342509223456543606312405417350433746860378776904565137185386174840323083 == 0x2a7c107e4a0e1fbf425fda5a46e95f8fd60e4b365120a3e8a49497f19d443c0b

So as we saw the resulting numbers are not correct.
Please fix this if it's indeed a bug cause it may pose real threat for some applications' security and working capacity.

Additionally, I attach a snippet of code for Rust script to quickly plug it in and test this issue yourself.

use curve25519_dalek::{Scalar, RistrettoPoint};
use curve25519_dalek::ristretto::{CompressedRistretto};

fn main() {
    let X: RistrettoPoint = CompressedRistretto::from_slice(hex::decode("f245308737c2a888ba56448c8cdbce9d063b57b147e063ce36c580194ef31a63").unwrap().as_slice()).unwrap().decompress().unwrap();
    let n: Scalar = Scalar::from_canonical_bytes(hex::decode("d32fcc5ae91ba05704da9df434f22fd4c2c373fdd8294bbb58bf27292aeec00a").unwrap().try_into().unwrap()).unwrap();
    let R: RistrettoPoint = X * n;
    let R2: RistrettoPoint = RistrettoPoint::mul_base(&n);
    println!("{}", format!("{}", ::hex::encode(R.compress().to_bytes().as_ref())));
    println!("{}", format!("{}", ::hex::encode(R2.compress().to_bytes().as_ref())));
}

Looking forward for your reply.
Thanks!

[EmelyanenkoK]

Thank you! We will check.

[dta90d]

@EmelyanenkoK Do you have an estimate when to expect the response?

[EmelyanenkoK]

TVM expects scalar in non-canonical form. You can compare results with the following rust code (from_canonical_bytes -> from_bytes_mod_order):

use curve25519_dalek::{Scalar, RistrettoPoint};
use curve25519_dalek::ristretto::{CompressedRistretto};

fn main() {
    let X: RistrettoPoint = CompressedRistretto::from_slice(hex::decode("f245308737c2a888ba56448c8cdbce9d063b57b147e063ce36c580194ef31a63").unwrap().as_slice()).unwrap().decompress().unwrap();
    let n: Scalar = Scalar::from_bytes_mod_order(hex::decode("d32fcc5ae91ba05704da9df434f22fd4c2c373fdd8294bbb58bf27292aeec00a").unwrap().try_into().unwrap());

    let R: RistrettoPoint = X * n;
    let R2: RistrettoPoint = RistrettoPoint::mul_base(&n);
    println!("{}", format!("{}", ::hex::encode(R.compress().to_bytes().as_ref())));
    println!("{}", format!("{}", ::hex::encode(R2.compress().to_bytes().as_ref())));
}

Seems like canonical and non-canonical forms can be calculated from each other but it requires non-trivial tinkering with higher bits.

[dta90d]

Hello, please don't close the issue, I had no time to work on it and come up with the answer.

[dta90d]

@EmelyanenkoK

Hello! I had time recently to explore the topic, so here are the results of my research.

First of all, I'm not a mathematician or Rust/C++ dev, I just happen to implement an algorithm for smart contract from the official specification that has test vectors and results of calculations of each step and I can't do it, because the values coming from the TVM's RIST255_MULT and RIST255_MULBASE functions just do not match the verified test values from the specification. So it's safe to assume there is something wrong with the implementation.

Secondly, I've tried out your code with from_bytes_mod_order method that can receive unreduced scalar and reduces it automatically. It outputs exactly the same results as my original code, meaning that reducing (or converting from non-canonical to canonical scalar format) should output the original value when the reduced scalar is being passed (and that's not happening for TVM according to your reply).

Thirdly, it is obvious from the curve25519_dalek::scalar docs that scalar that is being passed to the MUL and MULBASE functions MUST be canonical and that also means that converting already canonical scalar to canonical format should take no effects on value:

    /// Check whether this `Scalar` is the canonical representative mod \\(\ell\\). This is not
    /// public because any `Scalar` that is publicly observed is reduced, by scalar invariant #2.
    fn is_canonical(&self) -> Choice {
        self.ct_eq(&self.reduce())
    }

https://github.com/dalek-cryptography/curve25519-dalek/blob/43a16f03d4c635a8836c23ac07244c116ea3aab8/curve25519-dalek/src/scalar.rs#L1134

So that means that functions inside TVM should work the same way, which is not the case.

Also I've tried out libsodium library that TVM uses and it gives the exact same results as dalek and specification give, I can provide the code if you need more proof.

Looking forward for your reply.
Thanks!

[EmelyanenkoK]

Secondly, I've tried out your code with from_bytes_mod_order method that can receive unreduced scalar and reduces it automatically. It outputs exactly the same results as my original code

Let's start with that

What your

use curve25519_dalek::{Scalar, RistrettoPoint};
use curve25519_dalek::ristretto::{CompressedRistretto};

fn main() {
    let X: RistrettoPoint = CompressedRistretto::from_slice(hex::decode("f245308737c2a888ba56448c8cdbce9d063b57b147e063ce36c580194ef31a63").unwrap().as_slice()).unwrap().decompress().unwrap();
    let n: Scalar = Scalar::from_canonical_bytes(hex::decode("d32fcc5ae91ba05704da9df434f22fd4c2c373fdd8294bbb58bf27292aeec00a").unwrap().try_into().unwrap()).unwrap();
    let R: RistrettoPoint = X * n;
    let R2: RistrettoPoint = RistrettoPoint::mul_base(&n);
    println!("{}", format!("{}", ::hex::encode(R.compress().to_bytes().as_ref())));
    println!("{}", format!("{}", ::hex::encode(R2.compress().to_bytes().as_ref())));
}

and "ours"

use curve25519_dalek::{Scalar, RistrettoPoint};
use curve25519_dalek::ristretto::{CompressedRistretto};

fn main() {
    let X: RistrettoPoint = CompressedRistretto::from_slice(hex::decode("f245308737c2a888ba56448c8cdbce9d063b57b147e063ce36c580194ef31a63").unwrap().as_slice()).unwrap().decompress().unwrap();
    let n: Scalar = Scalar::from_bytes_mod_order(hex::decode("d32fcc5ae91ba05704da9df434f22fd4c2c373fdd8294bbb58bf27292aeec00a").unwrap().try_into().unwrap());

    let R: RistrettoPoint = X * n;
    let R2: RistrettoPoint = RistrettoPoint::mul_base(&n);
    println!("{}", format!("{}", ::hex::encode(R.compress().to_bytes().as_ref())));
    println!("{}", format!("{}", ::hex::encode(R2.compress().to_bytes().as_ref())));
}

snippets output on your side?

[dta90d]

@EmelyanenkoK

Here's output of "my" snippet:

5e727d972b11f6490b0b1ba8147775bceb1a2cb523b381fa22d5a5c0e97d4744
9a30709d72de12d67f7af1cd8695ff16214d2d4600ae5f478873d2e7ed0ece73

Here's output of "your" snippet:

5e727d972b11f6490b0b1ba8147775bceb1a2cb523b381fa22d5a5c0e97d4744
9a30709d72de12d67f7af1cd8695ff16214d2d4600ae5f478873d2e7ed0ece73

[dta90d]

@EmelyanenkoK Here's full code that you can verify.

use curve25519_dalek::{Scalar, RistrettoPoint};
use curve25519_dalek::ristretto::{CompressedRistretto};

fn main1() {
    let X: RistrettoPoint = CompressedRistretto::from_slice(hex::decode("f245308737c2a888ba56448c8cdbce9d063b57b147e063ce36c580194ef31a63").unwrap().as_slice()).unwrap().decompress().unwrap();
    let n: Scalar = Scalar::from_canonical_bytes(hex::decode("d32fcc5ae91ba05704da9df434f22fd4c2c373fdd8294bbb58bf27292aeec00a").unwrap().try_into().unwrap()).unwrap();
    let R: RistrettoPoint = X * n;
    let R2: RistrettoPoint = RistrettoPoint::mul_base(&n);
    println!("{}", format!("{}", ::hex::encode(R.compress().to_bytes().as_ref())));
    println!("{}", format!("{}", ::hex::encode(R2.compress().to_bytes().as_ref())));
}


fn main2() {
    let X: RistrettoPoint = CompressedRistretto::from_slice(hex::decode("f245308737c2a888ba56448c8cdbce9d063b57b147e063ce36c580194ef31a63").unwrap().as_slice()).unwrap().decompress().unwrap();
    let n: Scalar = Scalar::from_bytes_mod_order(hex::decode("d32fcc5ae91ba05704da9df434f22fd4c2c373fdd8294bbb58bf27292aeec00a").unwrap().try_into().unwrap());

    let R: RistrettoPoint = X * n;
    let R2: RistrettoPoint = RistrettoPoint::mul_base(&n);
    println!("{}", format!("{}", ::hex::encode(R.compress().to_bytes().as_ref())));
    println!("{}", format!("{}", ::hex::encode(R2.compress().to_bytes().as_ref())));
}

fn main() {
    println!("Main 1:");
    main1();
    println!("\nMain 2:");
    main2();
}

Output:

Main 1:
5e727d972b11f6490b0b1ba8147775bceb1a2cb523b381fa22d5a5c0e97d4744
9a30709d72de12d67f7af1cd8695ff16214d2d4600ae5f478873d2e7ed0ece73

Main 2:
5e727d972b11f6490b0b1ba8147775bceb1a2cb523b381fa22d5a5c0e97d4744
9a30709d72de12d67f7af1cd8695ff16214d2d4600ae5f478873d2e7ed0ece73

[dta90d]

@EmelyanenkoK Hey, in case you wondering I've figured out proper reducing of the scalar using libsodium library and I can send you code with examples as proof that my theory is right. It works differently compared with dalek rust lib. You cannot pass 32 byte value in there, you have to explicitly pass 64 byte value into reduce function (crypto_core_ristretto255_scalar_reduce), otherwise the output will be not correct, even though there will be an output. It is slightly stated in the docs, but there is no warning or anything.

Note that s is much larger than r (64 bytes vs 32 bytes). Bits of s can be left to 0, but the interval s is sampled from should be at least 317 bits to ensure almost uniformity of r over L.

@ me if you need code with examples as proof and I will send it to you.