Discussion:
Computing an inverse scalar for Curve25519
(too old to reply)
Alexey Ermishkin
2017-05-30 18:23:27 UTC
Permalink
Hello everyone.

I'm trying to implement sphinx password store protocol which needs an
inverse element webee.technion.ac.il/~hugo/sphinx.pdf using 25519

It's all ok with p-256 curve (PoC in Golang is here:
https://gist.github.com/Scratch-net/37ae11e589ea3d17fe104a2630306042), works
like a charm, but nothing helps for Curve25519.

I tried to
1) Remove clamping before second scalarMult
2) Inverse Endianness, convert scalar to BigInt, use the standard
ModInverse, convert back to bytes and reverse byte order once again but that
did not help

I'm obviously missing something but cannot figure out what. I'd love to get
an advice on how to achieve that using ref10 notation or similar existing
code

Thanks in advance,
Alex.
isis agora lovecruft
2017-05-30 22:18:25 UTC
Permalink
Post by Alexey Ermishkin
Hello everyone.
I'm trying to implement sphinx password store protocol which needs an
inverse element webee.technion.ac.il/~hugo/sphinx.pdf using 25519
https://gist.github.com/Scratch-net/37ae11e589ea3d17fe104a2630306042), works
like a charm, but nothing helps for Curve25519.
I tried to
1) Remove clamping before second scalarMult
2) Inverse Endianness, convert scalar to BigInt, use the standard
ModInverse, convert back to bytes and reverse byte order once again but that
did not help
I'm obviously missing something but cannot figure out what. I'd love to get
an advice on how to achieve that using ref10 notation or similar existing
code
Thanks in advance,
Alex.
Hello Alex,

Someone answered precisely this same question on SE [0] about a week ago, by
pointing out that field element inversion isn't the same as scalar inversion.
Curiously, the questioner, John Dow, is also implementing the same "password
store mechanism, called Sphinx". Maybe you two should collaborate? :)

The questioner helpfully posted a screenshot of the protocol setup
requirements of the paper, which state that the cyclic group G must be of
prime order. Unfortunately, the group of points on curve25519 is _not_ prime
order, but, instead, the cofactor (8, in this case) times the order of the
basepoint (2^252 - 27742317777372353535851937790883648493). All Edwards
curves — and curve25519 is one of this type — have cofactors. Effectively,
this means you can't implement your protocol using curve25519 (at least, not
without some modification). To say that cofactors are annoying would be
putting it mildly!

If you'd like to learn more about the historical problems arising from
cofactors, along with a very elegant solution to elliminate the cofactors of
Ed448 and curve25519, I would highly suggest reading Mike Hamburg's "Decaf:
Elliminating cofactors through point compression" paper [1] as well as the
archives of this list (if you haven't yet).

P.S.: This line of code [2] in your example should be using a random scalar
(in â„€/lâ„€, l=2^252 - 27742317777372353535851937790883648493) instead of taking
a random field element (in â„€/(2^255 - 19)) compressing it to bytes and
treating it as a scalar, without modular reduction. (Lines 37 and 44 are also
doing this.) Similarly, here [3] you're inverting a field element modulo the
order of the basepoint (`N` in your library, `l` here). Instead, `r` and
`rInv` should both be scalars.

Side note: That Golang elliptic curve library you're using is horrible! I
can't believe that's in the Go standard library! (Actually, I can; it's Go.)
It's exacerbating confusion between field elements and scalars with its
horrible typing, i.e. in "crypto/elliptic/p256":

func (p256Curve) ScalarMult(bigX, bigY *big.Int, scalar []byte) (x, y *big.Int) {

No wonder you're trying to compress field elements to bytes and pass them in
as scalars, its type system is practically telling you to do that! (And if
that weren't bad enough, it's expressing field elements as bigints
 this is
really slow, not to mention weird since most libraries split up these
potentially large numbers into "limbs".) I would not recommend that library.

[0]: https://crypto.stackexchange.com/a/47482
[1]: https://mikehamburg.com/papers/decaf/decaf.pdf
[2]: https://gist.github.com/Scratch-net/37ae11e589ea3d17fe104a2630306042#file-sphinx-go-L33
[3]: https://gist.github.com/Scratch-net/37ae11e589ea3d17fe104a2630306042#file-sphinx-go-L35

Best regards,
--
♥Ⓐ isis agora lovecruft
_________________________________________________________
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
Alexey Ermishkin
2017-05-30 22:31:38 UTC
Permalink
Thanks for pointing out at my mistakes and a very good explanation. I will
continue to dig deeper
Mike Hamburg
2017-05-30 22:37:15 UTC
Permalink
Is it enough to use 8*r and 8*(r^-1 mod q) for this protocol?

If not, or if you can’t prove it, you could always use my library at

https://sourceforge.net/projects/ed448goldilocks/ <https://sourceforge.net/projects/ed448goldilocks/>

It gives a prime-order quotient group of Ed448 and Curve25519, and it implements Elligator and division mod q.

— Mike
Post by Alexey Ermishkin
Thanks for pointing out at my mistakes and a very good explanation. I will
continue to dig deeper
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Max Skibinsky
2017-05-31 00:27:38 UTC
Permalink
my understanding of sphinx is that user is constructing *hash(password,
hash(password)^device_key)* in such way that user never sees *device_key* and
device never sees *hash(password). *That is achieved by sending
*hash(password)^p *with random *p *to device/server, which responds with
*hash(password)^(p*device_key) *and then user calculates
*hash(password)^(p*device_key)^1/p=**hash(password)^device_key* to get
final randomized password.

Expanding on Alexey question: which curves/libs currently support
calculations of inverse (1/p) so that it is possible to restore
*hash(password)^device_key
? *We run into this issue exactly while considering adding sphinx to our
crypto relays (which are completely on curve25519)

-
max​
vault12
​​
<https://vault12.com/>
​​
blog <http://skibinsky.com/>

*linkedin <http://bit.ly/max-li>*
Post by Mike Hamburg
Is it enough to use 8*r and 8*(r^-1 mod q) for this protocol?
If not, or if you can’t prove it, you could always use my library at
https://sourceforge.net/projects/ed448goldilocks/
It gives a prime-order quotient group of Ed448 and Curve25519, and it
implements Elligator and division mod q.
— Mike
Thanks for pointing out at my mistakes and a very good explanation. I will
continue to dig deeper
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Michael Scott
2017-05-31 08:21:37 UTC
Permalink
You might consider using Version3 of our AMCL library

https://github.com/miracl/amcl

Includes a standard API for ECDSA, which requires the inverse calculation,
so should be easy to re-use that code

It supports multiple elliptic curves (all those mentioned here), and its
simple to switch from one curve to another.

Also its available in Go if that is what you like (and C, Rust, Java,
Javascript and Swift)


Mike Scott
Post by Max Skibinsky
my understanding of sphinx is that user is constructing *hash(password,
hash(password)^device_key)* in such way that user never sees *device_key* and
device never sees *hash(password). *That is achieved by sending
*hash(password)^p *with random *p *to device/server, which responds with
*hash(password)^(p*device_key) *and then user calculates
*hash(password)^(p*device_key)^1/p=**hash(password)^device_key* to get
final randomized password.
Expanding on Alexey question: which curves/libs currently support
calculations of inverse (1/p) so that it is possible to restore *hash(password)^device_key
? *We run into this issue exactly while considering adding sphinx to our
crypto relays (which are completely on curve25519)
-
max​
vault12
​​
<https://vault12.com/>
​​
blog <http://skibinsky.com/>
*linkedin <http://bit.ly/max-li>*
Post by Mike Hamburg
Is it enough to use 8*r and 8*(r^-1 mod q) for this protocol?
If not, or if you can’t prove it, you could always use my library at
https://sourceforge.net/projects/ed448goldilocks/
It gives a prime-order quotient group of Ed448 and Curve25519, and it
implements Elligator and division mod q.
— Mike
Thanks for pointing out at my mistakes and a very good explanation. I will
continue to dig deeper
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Max Skibinsky
2017-05-31 15:13:42 UTC
Permalink
Thank you for sharing this Mike. looks like a great lib, quite a delight to
find both Swift and Rust implementation.

-
max​
vault12
​​
<https://vault12.com/>
​​
blog <http://skibinsky.com/>

*linkedin <http://bit.ly/max-li>*
Post by Michael Scott
You might consider using Version3 of our AMCL library
https://github.com/miracl/amcl
Includes a standard API for ECDSA, which requires the inverse calculation,
so should be easy to re-use that code
It supports multiple elliptic curves (all those mentioned here), and its
simple to switch from one curve to another.
Also its available in Go if that is what you like (and C, Rust, Java,
Javascript and Swift)
Mike Scott
Post by Max Skibinsky
my understanding of sphinx is that user is constructing *hash(password,
hash(password)^device_key)* in such way that user never sees *device_key* and
device never sees *hash(password). *That is achieved by sending
*hash(password)^p *with random *p *to device/server, which responds with
*hash(password)^(p*device_key) *and then user calculates
*hash(password)^(p*device_key)^1/p=**hash(password)^device_key* to get
final randomized password.
Expanding on Alexey question: which curves/libs currently support
calculations of inverse (1/p) so that it is possible to restore *hash(password)^device_key
? *We run into this issue exactly while considering adding sphinx to our
crypto relays (which are completely on curve25519)
-
max​
vault12
​​
<https://vault12.com/>
​​
blog <http://skibinsky.com/>
*linkedin <http://bit.ly/max-li>*
Post by Mike Hamburg
Is it enough to use 8*r and 8*(r^-1 mod q) for this protocol?
If not, or if you can’t prove it, you could always use my library at
https://sourceforge.net/projects/ed448goldilocks/
It gives a prime-order quotient group of Ed448 and Curve25519, and it
implements Elligator and division mod q.
— Mike
Thanks for pointing out at my mistakes and a very good explanation. I will
continue to dig deeper
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Loading...