Ed25519 private keys only have 251 bits of effective entropy.
The following code should probably not be performing clamping! Clamping is performed on the lower 256 bits of the result of SHA512 in the EdDSA scheme, which is the resulting private key. The seed for EdDSA should just be a random 256bit number! GPG/libgcrypt will perform this clamping during EdDSA on the seed itself. See this link for evidence of libgcrypt performing clamping on a SHA512 result.
The code being affected by this in sequioia can be found here. What happens now is due to clamping in the function below, keys generated by Sequioia will only have an effective range of 2^251
, which means only 2^251
possible outputs from SHA512 for EdDSA to use.
Solutions:
- Sequoia could just not call
ed25519::private_key
when generating keys. - This function could just return 32 random bytes (makes the most sense here I think).
pub fn private_key<R>(rng: &mut R) -> Box<[u8]>
where
R: Random,
{
let mut ret = vec![0u8; ED25519_KEY_SIZE].into_boxed_slice();
// Curve25519 Paper, Sec. 3:
// A user can, for example, generate 32 uniform random bytes, clear bits 0, 1, 2 of the first
// byte, clear bit 7 of the last byte, and set bit 6 of the last byte.
rng.random(&mut ret[..]);
ret[0] &= 0b1111_1000;
ret[ED25519_KEY_SIZE - 1] &= !0b1000_0000;
ret[ED25519_KEY_SIZE - 1] |= 0b0100_0000;
ret
}
The above should just be:
pub fn private_key<R>(rng: &mut R) -> Box<[u8]>
where
R: Random,
{
let mut ret = vec![0u8; ED25519_KEY_SIZE].into_boxed_slice();
rng.random(&mut ret[..]);
ret
}
Or alternatively (and probably more correct):
// Pseudocode
pub fn private_key<R>(seed: &[u8]) -> Box<[u8]>
where
R: Random,
{
let mut ret = vec![0u8; ED25519_KEY_SIZE * 2].into_boxed_slice();
sha512(&mut ret, seed);
let secret = &ret[33..];
secret[0] &= 0b1111_1000;
secret[ED25519_KEY_SIZE - 1] &= !0b1000_0000;
secret[ED25519_KEY_SIZE - 1] |= 0b0100_0000;
ret
}
Edited by Reisen