Uses preprocessed private keys, incompatible with other Ed25519 implementations

[lukaslihotzki]

There are two different meanings of Ed25519 private key:

1. 64 bytes derived from a 32 byte seed with SHA-512. I'll call this preprocessed private key.
2. Just the 32 byte seed. I'll call this private key seed. Obviously, the preprocessed private key can't be transformed back into the private key seed.

libolm stores preprocessed private keys in the Account and OutboundGroupSession pickles, which can be used in the bundled ed25519 library. However, other Ed25519 implementations (OpenSSL) do not support preprocessed private keys, so they are incompatible with existing pickled objects. RFC 8032 specifies the private key of Ed25519 is the private key seed, so you can't blame these implementations. If private key seeds were stored in the pickles instead, all Ed25519 implementations would be compatible.

I think that this issue is currently internal to Matrix clients, so clients can just store private key seeds internally if they need that. At least, that seems to work for me. This would change with the Dehydrated Devices MSC, because this MSC requires clients to store pickled accounts on the server, so they would have to agree on a common format.

I would like to integrate the OpenSSL implementation of Ed25519 into libolm eventually, so I propose these changes:

1. Allow to store either preprocessed private keys or private key seeds in _olm_ed25519_private_key. Add a flag to _olm_ed25519_private_key to distinguish them. This would require a pickle format update.
2. Store private key seeds in _olm_ed25519_private_key for newly created keys. In Account and OutboundGroupSession, the private key seeds are new random data, so storing it directly does not reveal previously secret data.

Would that be acceptable?

[richvdh]

@uhoreg any thoughts on this?

[uhoreg]

Yes, I think this sounds sensible. Alternatively, we could store both the seed and the preprocessed private key in _olm_ed25519_private_key, and have a flag that indicates whether the seed is actually set. I'm not sure if we care more about the performance benefit of pre-computing the SHA-512 hash, or if we care more about wasting extra bytes for each key. Though I suspect that either way is fine.

Obviously, if you have an account/outbound group session that only has the preprocessed private key, then you won't be able to retrieve the seed, so you wouldn't be able to use OpenSSL with such accounts/outbound group sessions. For outbound group sessions, this isn't a huge deal as you can just create a brand new one.

Unfortunately, I don't currently have time to work on this, but if you want to do so, I'd be happy to merge it in.

[richvdh]

It's not particularly pertinent here, but for completeness, it turns out that there is another possible definition of "private key".

Some ed25519 implementations use "private keys" which are actually 64-byte strings consisting of the 32-byte seed followed by the 32-byte public key.

This is true of implementations based on the SUPERCOP reference implementations, which include libsodium, and the various language-specific wrappers of it such as python's libnacl and perl's Crypt::NaCl::Sodium. See implementation.