Double Public Key Signing Function Oracle Attack on Ed25519

The standard specification of Ed25519 message signing involves providing the algorithm with a message and private key.

The function will use the private key to compute the public key and sign the message. Some libraries provide a variant of the message signing function that also takes the pre-computed public key as an input parameter.

Libraries that allow arbitrary public keys as inputs without checking if the input public key corresponds to the input private key are vulnerable to the following attack.

By using several public keys and messages, a malicious user with access to the signing mechanism may build up insights into the private key parameters resulting in access to the private key.

This shortcoming means that an attacker could use the signing function as an Oracle, perform crypto-analysis and ultimately get at secrets. For example, an attacker who can’t access the private key but can access the signing mechanism through an API call could use several public keys and messages to gradually build up insights into private key parameters.