here are some benchmarks comparing the current shared secret calculation with X25519: gist.github.com/tevador/50160d160d2…52ae02eb3d17024#gistcomment-4258297

tevador: awesome thank you :) do these have the precondition that input scalars are < 2^252?

mx25519_invkey will return a failure if the inverted key is >= 2^252

scalar multiplication works with any private key < 2^256

^ One thing to note is that the private key should not be reduced. You should simply generate random 32 bytes and that becomes the private key. The algorithm clamps the key internally.

tevador: Doesn't that create notable levels of bias?

If this is still the Ed25519 scalar field, clamping removes torsion. It won't create < modulus. If you're reducing to be < bias, that's even more biased than Monero's current scalar generation algorithm (which koe thankfully moved to wide reduction in Seraphis).

Monero's scalar gen is biased ?

*just because you're no longer reducing with 3 wide bits, which you're now clamping out.

l = 2^252 + 27742317777372353535851937790883648493, so the bias is ~2^-126

moneromooo: Yes. It's a 32-byte reduction.

Patch plz ? :D

The IETF hash to curve spec, which does provide a formula for the needed bits to be sufficiently without bias, I believe recommends a 48-byte reduction for 32-byte fields.

check RFC 7748, clamping is the recommended procedure for generating X25519 private keys

And then the community as a whole frequently does 64-byte reduction.

Ooh, I remmeber seeing 64 byte gen for a 32 byte value in some place...

> To control bias, hash_to_field instead uses random integers whose... (full message at libera.ems.host/_matrix/media/r0/do…092952852e54a0193288cdf537120ef8b94)

This is from the IETF document on hash to field, which is what I'm primarily referring to tbc.

yes, 48-byte reduction is to have a ~2^-128 bias with any 256-bit prime number. But the order of the Curve25519 group is so close to 2^252 that you get that for free without reduction.

random32_unbiased only reduces if the random bits is < a multiple of the modulo though, that ought not bias ?

Unbiased generation is needed for things like Schnorr signatures, where even a slight bias will eventually leak the private key. None of this applies to DH.

So I do know Ed25519 is beneficial in this regards, though no, I probably don't know as much as you ;)

tevador: is there a workaround if I want to guarantee the inversion is no-fail

?

I just wanted to raise it as a concern of mine. While the x25519 spec does line up, the EdDSA spec does use wide reduction. I question why it does so if the bias should be equivalent.

moneromooo: If this is using rejection sampling, it's not biased. If it's > modulus and it reduces, it is biased.

tevador: Thank you for the clarification here.

... I mean, it'd still leak the DH secret.

*to be clear, there's the discussion it already has insufficient bias and I don't mean to dismiss it.

Though I do want to note that while we're not discussing leaking the private key, we are discussing leaking the ECDH secret. That is sufficient to break amount privacy.

UkoeHB: I don't think we need to care about that. The chance of failure is ~2^-124. It won't happen in practice unless you generate a key specifically to fail.

So while the comment may be it has insufficient bias, I'm not sure we can ignore this because its DH, not a signature.

mx25519_scalar_inv() doesn't look like it has any failure modes

mx25519_scalar_inv is not an API function.

It's internal.

<moneromooo> "random32_unbiased only reduces..." <- words.filippo.io/dispatches/wide-reduction notes it as handling an edge case. Not as a valid bias removal

oh I see thanks

It's the final footnote. I just didn't want to post the entire paragraph ;)

UkoeHB: Mind if I get your thoughts/sign off on X25519 bias? I won't run around endlessly about this, and won't claim to be versed enough to have a true opinion. Just wanted to ensure it was discussed and considered.

And tevador definitely seems to have to, and I appreciate their work :D I just want to ensure its verified :p Which is not something I feel confident to myself :(

I'm still looking at this

Sure 👍️

Ask Dr. Bernstein. I'm 100% sure it's secure since he implemented it this way.

And tevador, truly not trying to state there is an issue or dismiss your explanation. Thanks for providing it :)

It's secure as long as the scanning key is only ever used for DH.

Which it is in the current specs AFAIK.

tevador: I think this comment github.com/tevador/mx25519/blob/837…c373ff32681154c1/src/mx25519.c#L107 should be 8*k0*8*k1...

although it's kind of misleading since there is no mul8

No, it's correct actually. All the keys are implicitly multiples of 8 due to the clamping procedure. invkey calculates basically 8/(8*key[0]*key[1]...)

mul8 is there on line 108

oh you start with 8 ok

fun fact, if you pass num_keys == 0, it will give you an identity key: c87be1164f29370883d6e6e89bed9c3e00000000000000000000000000000030

shouldn't identity be 000000...001? is it represented different from ed25519 points?

1 would be an invalid key since all private keys must be multiples of 8 by convention

so it returns something like 8*(1/8)

hmm ok

if you reduce is mod l, you'll get 1

it*

the bit shift at the end is also a mul8, are you not counting that on semantic grounds?

that's the final mul8 that cancels the 1/8 in the inversion

it's 8*(1/(8*key[0]*key[1]...))

the result is a private key you can plug into mx25519_scmul and it will work as an inverse

oh duh

ok to make it no-fail I would need to do this:

1. manually compute inversions with monero crypto scalar ops

2. if the inversion is >= 2^252, then do `mx25519_scmul()` three times with `((x << 3) - 2^255) * P + 2^254 * P + 2^254*P`

However there is no point addition available, so that's impossible. Basically it's impossible to make this API no-fail

is a 2^-124 failure rate something we need to care about?

I think it's enough just to reject the seed

It's possible to make it no-fail at the cost of making each scalar multiplication slower. We would need one more ladder iteration to cover 256 key bits. But this would be highly non-standard for Curve 25519.

I agree to require a reroll when your find-received key or address index extension are >= 2^252, the problem for me is removing the no-fail guarantee when dealing with inversions (which the generate-address secret holder can't do anything about when generating addresses).

All I want to change is being able to use invalid inversions somehow

if `mx25519_invkey()` fails, then there is a back-up solution

which I can do if point addition is available

point addition is not possible only with the x-coordinate

But the failure can be worked around quite easily: if invkey(k0, k1) fails, simly call invkey(k0) and then invkey(k1). This will require 2 scalarmults instead of one but the chance of that is so low that it doesn't matter in practice.

no, it is the failure of the final result that concerns me

the probability of failure may be very low, but I have a hard time getting behind removing the no-fail guarantee when it isn't necessary

the problem is this limits the range of input scalars: github.com/tevador/mx25519/blob/837…154c1/src/portable/scalarmult.c#L28, if we could remove this line and let the bit shift be up to the caller (or provide two api points for strict vs non-strict multiplications... that would work

cause then you could do 8*(x * P) if x >= 2^252

I'm waiting to hear tomorrow if it's broken or genius, after the last one took just a few hours lol

It was accepted to crypto 2022 👀 so should be reviewed

I believe Halo 2, which has far smaller proof sizes and I name as reference partially due to how it's a top contender and partially as it'll be the most known reference, would take 100s for the same amount of gates they did at just 3s afaict. The cost is 500x larger proofs :/ Still insane to see