eddsa/eddsa.go usability + misc. notes

[sarkortrantor]

multiple things:

1) usability: for my use case (which is not that exotic) I would like to sign messages using an existing edwards25519.Curve keypair. this is not possible with current implementation (I'm aware of the one key one purpose moto but the option should be left to the user since this is the exact purpose of kyber if I'm not mistaken) => not usable I need to reinvent the eddsa sign in my code

2) detail: IMHO the returned signature should not be a []byte but a tuple (kyber.Point, kyber.Scalar). the choice to marshall it or not and how should be left to the user. (same in verify, accept tuple instead of []byte, and avoid the now unnecessary unmarshall call)

3) consistency + DRY: use curve.NewKey() instead of rewriting it here in the form of hashSeed in fact solving 3) solves 1) too since NewKey implements the key.Generator interface and we can now use key.NewKeyPair()

[jeffallen]

I've noticed some of the same things recently when using eddsa. I have marked this as future work which would be a good size to be done by an assistant.

[nikkolasg]

A few things I remember from the time we worked on that. I don't have time right now to re-dig into it so please bear with me, there might be invalid stuff... :

• The main problem with EdDSA is that the key creation is not really compatible with the edwards25519 key creation. With EdDSA, you do Hash + Bit shift and then you split the result in two: first 32 bytes goes to being a Scalar, and the second 32 bytes are kept to sign the thing. Using basically edwards25519.NewKey just creates you a random scalar modulo'd with the bit shift. I'm not sure there's a clean way to use NewKeyPair for that.

• If you are in posession of a edwards25519 key pair, you can use schnorr signatures (kyber has a package for it) and it is normally verifiable by any edddsa implementation (there should be integration test for that somewhere).

• Regarding signatures as a tuple of slice of bytes... I guess we step into theological opinions. EdDSA is a package that must implement a very specific completely defined signature algorithm. It is made to produce EdDSA signature and verify EdDSA signature. Letting people play with the output of a signature scheme is generally not a good idea. That's also why all completely defined specific signature algorithm returns a slice of bytes too. Also, IIRC most packages in the sign/ directory returns a slice of bytes as a signature, so I would suggest to continue being consistent on that front.

[sarkortrantor]

If I'm not mistaken,

• in edwards25519 curve every 256 bits string is a valid scalar,
• a secret is a scalar whose bits has been twiddled such as to prevent small subgroup attacks.
• a EdDSA private key k is a 256 bits string chosen uniformly at random (=> hence any scalar => hence any secret => hence a private key returned by NewKeyPair())
• a EdDSA public key is defined to be the point A = sB where s=H0..255(k) where H in our example is sha512 (Ed25519)

what I think is the source of the misunderstanding is that A != kB,

hence if I have a curve KeyPair I should be able to sign messages using my private key but I need to be aware that for the other party to be able to verify my signature I need to publish a different public key, namely A. EDIT: or to be more precise if I have a scalar I should be able to sign using it as a EdDSA private key ! (and to my current understanding we don't need to do any bit masking on EdDSA private keys since they are fed into the hash function in order to derive the public key) https://tools.ietf.org/html/rfc8032

without going into "is this a good idea" I'd say that the sign and verify should be functions that accept keys, as we can see in other libraries

[nikkolasg]

in edwards25519 curve every 256 bits string is a valid scalar,

Yes but not in our implementation because we automatically modulo scalar, so it has a reduced range in kyber. Also there's two part in a EdDSA private key => the "real" private key scalar, and the deterministic randomness "r" , both are derived from a common seed. Implementations differs into what they consider a private key: either the seed or the two parts.

EDIT: or to be more precise if I have a scalar I should be able to sign using it as a EdDSA private key ! (and to my current understanding we don't need to do any bit masking on EdDSA private keys since they are fed into the hash function in order to derive the public key)

It's supposed to be the other way around, you take random slice of bytes, hash it do the bit twiddling and then create the private scalar out of the first 32 bytes.

[sarkortrantor]

and I forgot to add that masking the output of the hash makes the implementation not conform with the RFC or the description of the signature scheme in the original paper

[sarkortrantor]

in edwards25519 curve every 256 bits string is a valid scalar, Yes but not in our implementation because we automatically modulo scalar, so it has a reduced range in kyber.

ok but then any scalar obtained by using SetBytes(256 bits string) is still a valid scalar, and can be represented using a 256 bit string => it is a valid EdDSA private key EDIT: ok we need to map a scalar to a 256 bit string => ok we cannot use a scalar as an EdDSA private key as is, understand your point now

[sarkortrantor]

in edwards25519 curve every 256 bits string is a valid scalar,

Yes but not in our implementation because we automatically modulo scalar, so it has a reduced range in kyber. Also there's two part in a EdDSA private key => the "real" private key scalar, and the deterministic randomness "r" , both are derived from a common seed. Implementations differs into what they consider a private key: either the seed or the two parts.

EDIT: or to be more precise if I have a scalar I should be able to sign using it as a EdDSA private key ! (and to my current understanding we don't need to do any bit masking on EdDSA private keys since they are fed into the hash function in order to derive the public key)

It's supposed to be the other way around, you take random slice of bytes, hash it do the bit twiddling and then create the private scalar out of the first 32 bytes.

sorry for the bad writing by scalar I meant the string representation (your slice of bytes), I've confused both, but still to my understanding there is no need to do the bit twiddling on the resulting hash

woops : (from RFC) The private key is 32 octets (256 bits, corresponding to b) of cryptographically secure random data. See [RFC4086] for a discussion about randomness.

The 32-byte public key is generated by the following steps.

1. Hash the 32-byte private key using SHA-512, storing the digest in a 64-octet large buffer, denoted h. Only the lower 32 bytes are used for generating the public key.

2. Prune the buffer: The lowest three bits of the first octet are cleared, the highest bit of the last octet is cleared, and the second highest bit of the last octet is set.

3. Interpret the buffer as the little-endian integer, forming a secret scalar s. Perform a fixed-base scalar multiplication [s]B.

4. The public key A is the encoding of the point [s]B. First, encode the y-coordinate (in the range 0 <= y < p) as a little- endian string of 32 octets. The most significant bit of the final octet is always zero. To form the encoding of the point [s]B, copy the least significant bit of the x coordinate to the most significant bit of the final octet. The result is the public key.

[sarkortrantor]

so to conclude let's forget about the "I should be able to use my curve private key to sign" and keep only the remark "I should be able to specify which key to use" where key is a 256 bits string

[nikkolasg]

"I should be able to specify which key to use" where key is a 256 bits string

But how ? To me, the problem is that the given private key can be considered either as:

• the seed to feed into the hash function, that can generate the two scalars afterwards. But in that case, since the given key is a Scalar, that means it is already modulo'd. Having a modulo'd input instead of a completely uniform one may or may not be a security issue but we should be cautious about it (having a biased input often is a security problem). Moreover, the corresponding public of the given private key input will not be able to verify signatures issued in this way.
• the private key to sign directly: but in that case we miss the second 32 bytes output of the hash function, so we can't sign using EdDSA.

[sarkortrantor]

I don't have enough background on this to pronounce myself, I just read the definition of "EdDSA private key" in the RFC, and wikipedia, hence with respect to these sources of informations to me there is not much interpretation, the private key is defined as the 256 bits random seed. (but again I have 0 idea if this is how other people or implementations have interpreted it in practice).

regarding your concern about Scalar already modulo'd, the whole discussion led me to think that it is indeed a bad idea (a key is a 256 bits seed, not a Scalar, if someone want to map deterministically a Scalar to a 256 bits representation for using it as a EdDSA private key, fine, up to him, but we should't accept a Scalar)

[K1li4nL]

Hello, first thank you for efforts in discussing this issue, since it was opened time has passed and this function has been added to ed25519: https://github.com/dedis/kyber/blob/b172e02f7ce590f74d69baef55d5172273d1d1b7/group/edwards25519/curve.go#L65

The key and seed can then be passed to eddsa using: https://github.com/dedis/kyber/blob/b172e02f7ce590f74d69baef55d5172273d1d1b7/sign/eddsa/eddsa.go#L74