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

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

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

tevador
scalar multiplication works with any private key < 2^256

tevador
^ 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.

kayabanerve[m]
tevador: Doesn't that create notable levels of bias?

kayabanerve[m]
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).

moneromooo
Monero's scalar gen is biased ?

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

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

kayabanerve[m]
moneromooo: Yes. It's a 32byte reduction.

moneromooo
Patch plz ? :D

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

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

kayabanerve[m]
And then the community as a whole frequently does 64byte reduction.

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

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

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

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

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

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

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

UkoeHB
tevador: is there a workaround if I want to guarantee the inversion is nofail

UkoeHB
?

kayabanerve[m]
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.

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

kayabanerve[m]
tevador: Thank you for the clarification here.

kayabanerve[m]
... I mean, it'd still leak the DH secret.

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

kayabanerve[m]
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.

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

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

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

tevador
mx25519_scalar_inv is not an API function.

tevador
It's internal.

tevador

kayabanerve[m]
<moneromooo> "random32_unbiased only reduces..." <
words.filippo.io/dispatches/widereduction notes it as handling an edge case. Not as a valid bias removal

UkoeHB
oh I see thanks

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

kayabanerve[m]
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.

kayabanerve[m]
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 :(

UkoeHB
I'm still looking at this

kayabanerve[m]
Sure 👍️

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

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

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

tevador
Which it is in the current specs AFAIK.

UkoeHB

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

tevador
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]...)

tevador
mul8 is there on line 108

UkoeHB
oh you start with 8 ok

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

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

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

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

UkoeHB
hmm ok

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

tevador
it*

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

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

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

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

UkoeHB
oh duh

UkoeHB
ok to make it nofail I would need to do this:

UkoeHB
1. manually compute inversions with monero crypto scalar ops

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

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

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

tevador
I think it's enough just to reject the seed

tevador
It's possible to make it nofail 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 nonstandard for Curve 25519.

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

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

UkoeHB
if `mx25519_invkey()` fails, then there is a backup solution

UkoeHB
which I can do if point addition is available

tevador
point addition is not possible only with the xcoordinate

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

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

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

UkoeHB
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 nonstrict multiplications... that would work

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

kayabanerve[m]

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

kayabanerve[m]
It was accepted to crypto 2022 👀 so should be reviewed

kayabanerve[m]
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