1
$\begingroup$

In a situation in which A handles a message P for B to sign using ECDSA, and that event repeats itself many times, is there a way A can discover B's private key?

A can carefully choose what will be P every time, and be confident that B is always the same person using the same key to sign.

Does it change anything if P is always a string of 32 bytes that B won't hash before signing, he will just sign directly -- as it would do with a message he had hashed himself.

$\endgroup$
1
$\begingroup$

Can one extract a private key from a series of carefully constructed signed messages?

That should not happen, but has. One example is ISO/IEC 9796:1991 (description), which is the first (AFAIK) signature scheme vetted by an international standard body. It was shown (full disclosure: by me) vulnerable to recovery of the private key from the signature of two well-chosen messages, when used in one of its mode (Rabin signature, an analog of RSA with public exponent $2$). That standard and mode are still used in 2020 in a widely deployed application where changing the verifying devices would be expensive. But over three decades that has enabled no practical attack (AFAIK) of that application, because in it's usage scenario actual adversaries are heavily constrained in the messages they can obtain signed.

The question discusses the strongest kind of attack condition for a signature scheme: a chosen message attack. The failure considered is the worst kind of failure for a signature scheme: key recovery. A failure just as serious in practice is universal forgery, allowing the attacker to obtain a valid signature for any message. Lesser notions of forgery exist, in particular existential forgery, where the attacker is able to choose the message which signature is forged. In strong resistance to existential forgery, the adversary is even allowed to obtain a genuine signature of that message (and succeeds by exhibiting a different signature).

Modern signature schemes aim at strong resistance to existential forgery under chosen message attack, with a few exceptions (including ECDSA which fails on the strong, see this). They thus are resistant to the question's key recovery under chosen message attack.


The question's last paragraph considers a signature scheme where the message is a fixed bytestring that is used without hashing (that could be a modification of a signature scheme with hashing, where the adversary is allowed to use a signing device that implements the signature except for the hashing step).

Yes, the removal of the hash can change things, but the details depend on the particular signature scheme. And since we removed the hash, that's not considered a valid attack on the signature scheme with hash.

For any RSA-based signature (with odd exponent), key recovery and universal forgery are widely conjectured impossible, beside side-channel and fault attacks on implementations. Existential forgery can be possible, or not, depending on details of the scheme.

I know no way the removal of the hash would allow to recover an ECDSA private key, or even enable existential forgery. But there's a much better option! When the cost of hashing makes it impractical to hash the full message in a security device such as a Smart Card or HSM, it's possible change the usage to signing (with hash in the device) a hash of the message (computed externally).

| improve this answer | |
$\endgroup$
2
$\begingroup$

It is not possible if the signature scheme is secure, under the standard notion of "existential unforgeability under chosen message attacks". According to this definition, the adversary is given the public key and can then choose messages to be signed one after another. If it can forge any signature, then the scheme is not secure. As such, if the scheme is secure, it's not possible to form special messages that result in the key being revealed, or any other vulnerability.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, but I'm still somewhat in the dark here. Is the ECDSA scheme secure under that notion? I searched for it but wasn't sure. I saw RSA has some issues like you can recover the message from the signature -- and if you alter the signature you'll recover a different message, as if it was the one signed in the first place. Are any of these things relevant? Do they exist in ECDSA? $\endgroup$ – fiatjaf Sep 13 at 2:12
  • 1
    $\begingroup$ ECDSA is assumed to be secure under this definition. Regarding RSA, you are referring to "plain RSA" which is NOT secure! However, RSA PKCS#1 v1.5 and RSA-PSS are examples that are assumed to be secure. $\endgroup$ – Yehuda Lindell Sep 13 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.