Proof of possession. x25519 + ed25519

Question

There are Client and Server.

Client have previously send public keys for x25519 and ed25519 to the server. And now need to prove that it has private keys for them.

I have found similar solutions in description of ssh protocol by Digital Ocean: https://www.digitalocean.com/community/tutorials/understanding-the-ssh-encryption-and-connection-process#authenticating-the-user's-access-to-the-server

And in SSH Authentication Protocol RFC: https://www.rfc-editor.org/rfc/rfc4252#section-7

General scheme:

1. Server generates some 'nonce'. Encrypts it with x25519 public key of the client and sends to the client.
2. Client decrypts the 'nonce' with corresponding x25519 private key. Signs it with ed25519 private key and sends original data with the signature attached.
3. Server checks that the data equals to the one was send in (1). And checks signature. Proof-of-Possession is done.

I have two questions:

1. Is this scheme correct ? What should I review/read to make it correct ?
2. In the article from Digital Ocean you can find that client doesn't send raw data back to server but gets md5 of it and sends only md5. Why so ? What's the point of that operation ? Should I do the same ?

Answer 1

1. Is this scheme correct ? What should I review/read to make it correct ?

One obvious issue is that the client is willing to decrypt arbitrary ciphertexts with its private key. Hence, if it uses the private key for any other purpose, well, it's insecure.

2. In the article from Digital Ocean you can find that client doesn't send raw data back to server but gets md5 of it and sends only md5. Why so ?

Well, that's to prevent someone from using the client as a decryption Oracle; they still could use it as a "decrypt-and-MD5" Oracle, but that's not nearly as bad.

Personally, I would make three changes:

• Replace MD5 with a modern hash (for example, SHA-256) - while MD5 is probably perfectly safe in this use, it has shown enough weaknesses that steering clear is probably the wiser option.

• I'd replace the deterministic hash with a randomized one. That is, I'd have the client pick a random string "r", and return the pair $r, SHA256( r || decryption )$. That way, the client can't be used as a "decrypt-and-SHA256" oracle either.

• On decryption failure, I'd make sure I'd pick a random decryption, and return the pair $r, SHA256( r || random )$ - there's no reason to give people a "is this a valid ciphertext" Oracle.

Actually, personally I'd probably replace this entire thing with a Schnorr proof of knowledge, but I rather assumed you didn't want to wholesale replace everything...