Issue with _random_scalar()

[Sc00bz]

This basically removes 3 bits from the key space vs just 1 bit with standard clamping. It's best to think of it as 8*((r/8)*G) and (r/8) has a max value of 2**252 - 1 (with standard clamping) which is less than ℓ. Now that you have P = (r/8)*G doing 8*P is a one-to-one function (assuming G is of order ℓ).

---

There is a theoretical attack on this and with standard clamping, if you can solve DLPs. From the server's first message (B = b*G + N) you can make guesses against it because the random scalar is in a specific range. Start with solving the DLPs b'*G = B for each B. Make a password guess and generate N'. Solve the DLP n'*G = N' and if any b'-n' are in an invalid range the password is wrong.

To prevent this attack, you should call crypto_scalarmult_ed25519_base_noclamp() and _random_scalar() should be:

static void
_random_scalar(unsigned char n[32])
{
    do {
        randombytes_buf(n, 32);
        n[0] &= 248;
        n[31] &= 127;
    } while (sodium_is_zero(n, 32));
}

This way each message from the server can only eliminate 1 in about 2**127.6 (1 / (1 - (2**252 - 1) / (2**252 + 27742317777372353535851937790883648493))) passwords guessed. If you get about 2**63.6 messages you'd only be able to eliminate 1 in about 2**64 passwords guessed. Ideally you'd want _random_scalar() to have a range of [1, ℓ) (then times 8), but the smaller range will still make the theoretical attack infeasible.

[jedisct1]

Hi, and thanks for your feedback!

_noclamp() variants were not available until libsodium 1.0.17 that was only released last week. Avoiding standard clamping was not possible before

That version also introduces crypto_core_ed25519_scalar_random() to pick a random scalar in [1, ℓ), btw.

I'm still planning to implement salt blinding, which makes libsodium 1.0.17+ mandatory; so that will be a good time to also switch to scalar_random()+_noclamp(), that have been specifically introduced for this.