Overflow in crypto_inverse_scalarmult()

[Sc00bz]

After sc25519_invert(), the scalar is modulo 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed then it is multiplied by 8 without modulo thus has a max value of 0x80000000000000000000000000000000a6f7cef517bce6b2c09318d2e7ae9f60. But the for loop ignores the highest order bit.

Simplest fix is change the for loop from https://github.com/BjoernMHaase/AuCPace/blob/7e7a63b5a20558d7e3fc162661288d18b1532bcc/c/tweetnacl.c#L1039 to for (i = 255; i >= 0; --i) {

The way I've solved this for the OPRF is not caring if the inverse scalar is a multiple of 8 because it is called on a known good point, but this is only if you are hiding crypto_inverse_scalarmult() for internal use only:

randombytes(r, 32);
crypto_elligator2(p, pwHash, 64);
crypto_inverse_scalarmult(p, r, p);
send(socket, p, 32, 0);
// server does:
// recv(socket, p, 32, 0);
// crypto_scalarmult(p, salt, p);
// send(socket, p, 32, 0);
recv(socket, p, 32, 0);
crypto_scalarmult(p, r, p);

[BjoernMHaase]

Hi Steve,

thank you for pointing this out. I have already fixed it in the repo.

I think that it is important to have the inverse scalarmult always operate on a multiple of 8. The problem is that Elligator2 does guarantee to return a point on the curve, but not necessarily on the prime-order subgroup. Between honest participants, you won't notice anything. However in your code example below, you might leak some bits of the password.

Again, the problem with your code example

|>crypto_elligator2(p, pwHash, 64); >crypto_inverse_scalarmult(p, r, p);

send(socket, p, 32, 0); |

. If you don't multiply the output of the elligator by 8 in the scalarmult you publish a point coordinate that is not guaranteed to be on the prime-order subgroup. For some passwords the point will be on the curve, for some it might not be on the curve.

This is why I have added this factor of 8.

Yours,

Björn.

P.S.: I have just googled your name. Could it possibly be that you are the person that I always have called "Steve Tobtu" in the slides and the paper? I thought so far that "Tobtu" would be the surname of this person that was active on the CFRG list  ..?

Am 09.02.2020 um 09:35 schrieb Steve Thomas:

After |sc25519_invert()|, the scalar is modulo 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed then it is multiplied by 8 without modulo thus has a max value of 0x80000000000000000000000000000000a6f7cef517bce6b2c09318d2e7ae9f60. But the for loop ignores the highest order bit.

Simplest fix is change the for loop from https://github.com/BjoernMHaase/AuCPace/blob/7e7a63b5a20558d7e3fc162661288d18b1532bcc/c/tweetnacl.c#L1039 to |for (i = 255; i >= 0; --i) {|

The way I've solved this for the OPRF is not caring if the inverse scalar is a multiple of 8 because it is called on a known good point, but this is only if you are hiding |crypto_inverse_scalarmult()| for internal use only:

|randombytes(r, 32); crypto_elligator2(p, pwHash, 64); crypto_inverse_scalarmult(p, r, p); send(socket, p, 32, 0); // server does: // recv(socket, p, 32, 0); // crypto_scalarmult(p, salt, p); // send(socket, p, 32, 0); recv(socket, p, 32, 0); crypto_scalarmult(p, r, p); |

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/BjoernMHaase/AuCPace/issues/1?email_source=notifications&email_token=ADMGYAHLRFRDRU4DRSLUPMLRB653XA5CNFSM4KSADYN2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4IMBT2KQ, or unsubscribe https://github.com/notifications/unsubscribe-auth/ADMGYABQ4IGCWICGJSXL7I3RB653XANCNFSM4KSADYNQ.

[BjoernMHaase]

Correcting myself: . For some passwords the point will be on the curve, for some it might not be on the set of prime order subgroup points on the curve.

[Sc00bz]

I was under the impression that Elligator2 multiplies by the cofactor at the end like libsodium, but I realize now that's not "Elligator2" it's "Elligator2 with the cofactor removed".

P.S.: I have just googled your name. Could it possibly be that you are the person that I always have called "Steve Tobtu" in the slides and the paper? I thought so far that "Tobtu" would be the surname of this person that was active on the CFRG list ..?

Yes, that would be me. I saw that when I was skimming through your slides but got distracted by some papers I hadn't seen. Speaking of you should not cite Muxiang Zhang's paper "Analysis of the SPEKE password-authenticated key exchange protocol" because it comes down to modifying SPEKE so you can solve DLPs. Basically if H(pw) outputs parseInt(pw) and passwords are pins then pins 000002, 000004, 000008… are exponential equivalent because they are 2**1 = 2, 2**2 = 4, 2**3 = 8, ...