In 2017, cryptography researchers from Kudelski Security demonstrated practical fault attacks against EdDSA (specifically Ed25519; RFC 8032).

Their techniques are also applicable to Deterministic ECDSA (RFC 6979), and potentially work against any deterministic Signature scheme (n.b. the Fiat-Shamir or Schnorr distinction isn’t meaningful in this context).

Although that might seem alarming, fault attacks aren’t especially useful for software applications running on general-purpose computers. They’re mostly in the threat models for smartcards and embedded devices.

A recent paper discusses a technique called “hedged” signatures, which I’ve mentioned in A Furry’s Guide to Digital Signature Algorithms.

What is a Hedged Signature?

Let’s just consult the formal definition given by Aranha, et al. in the paper I linked above!

Okay, if you’re not a cryptographer, this is probably clear as mud.

Let’s try a different approach (one that most software engineers will find more intuitive). We’ll start with non-hedged signatures, and then tweak them to become hedged.

Libsodium: Non-Hedged Signatures

Libsodium’s crypto_sign_detached() (which implements Ed25519) accepts two arguments:

1. The message being signed.
2. The secret key held by the signer.

Libsodium’s congruents crypto_sign_verify_detached() accepts three arguments:

1. The detached signature.
2. The message.
3. The public key (corresponds to the secret key from the other function).

Since libsodium uses Ed25519 under-the-hood, the signature algorithm is deterministic: If you sign the same Message with the same secret key, it will always produce the same signature.

Don’t believe me? Try it yourself: https://3v4l.org/lKrJb

Dhole Crypto: Hedged Signatures

Last year when I wrote Dhole Cryptography (in PHP and JavaScript), I decided to implement what would later come to be called “hedged signatures” by cryptographers.

Instead of just signing a message, Dhole Crypto first generates a 256-bit per-message nonce and then signs the nonce and the message together. Then, it appends the nonce to the generated signature (and encodes this as one binary-safe string).

That is to say, the major hack is to change a procedure from this:

function sign(string $message, string $secretKey): string {
  $signature = sodium_crypto_sign_detached(
    $message,
    $secretKey
  );
  return base64_encode($signature);
}

…into a procedure that looks like this:

function hsign(string $message, string $secretKey): string {
  $nonce = random_bytes(32);
  $signature = sodium_crypto_sign_detached(
    $nonce . $message,
    $secretKey
  );
  return base64_encode($signature . $nonce);
}

If you pay careful attention to the placement of the nonce in this updated procedure, you’ll notice that it’s backwards compatible with the original libsodium API for Ed25519: crypto_sign() and crypto_sign_open().

Of course, these details are totally abstracted away from the user. Instead, the API looks like this (PHP):

getPublicKey();

// Signing a message
$message = "I certify that you have paid your $350 awoo fine";
$sig = Asymmetric::sign($message, $secret);

// Verifying a message and signature
if (!Asymmetric::verify($message, $public, $sig)) {
    die('AWOO FINE UNPAID');
}

For JavaScript developers, this may be more intuitive to read:

const { 
    Asymmetric, 
    AsymmetricSecretKey
} = require('dhole-crypto');

(async function () {
    let wolfSecret = await AsymmetricSecretKey.generate();
    let wolfPublic = wolfSecret.getPublicKey();
    
    let message = "Your $350 awoo fine has been paid UwU";
    
    let signature = await Asymmetric.sign(message, wolfSecret);
    if (!await Asymmetric.verify(message, wolfPublic, signature)) {
        console.log("Invalid signature. Awoo not authorized.");
    }
})();

Do Hedged Signatures Protect Against Fault Attacks?

Sort of. It really depends on the kind of fault attack the attacker uses.

See Section 5 of the paper for a detailed break-down of the provable security of hedged signatures against XEdDSA (a variant of EdDSA used by the Signal protocol; the EdDSA variants specified in RFC 8032 were not studied in that paper).

However, the exploit explored by Kudelski using simple voltage glitches to break EdDSA in an Arduino device does become significantly more difficult with hedged signatures versus classical EdDSA.

Additionally, if you combine the existing techniques for mitigating fault attacks in embedded software with a protocol that uses hedged signatures, you may push the cost of a successful fault attack to become economically impractical for attackers.

However, it’s demonstrable that Hedged Signatures are at least as secure as Deterministic Signatures:

Even if your hedging suffers from a catastrophic randomness failure and generates the same nonce twice, the actual nonce used within Ed25519 will be derived from the SHA-512 hash of this value, the message, and a secret key.

Consequently, the only way for the internal nonce to repeat is for the message to be the same–which is the same scenario as a Deterministic Signature, which doesn’t let attackers steal your secret key.

What Does This All Mean?

Hedged signatures are at least as safe as Deterministic Signatures, and in some scenarios, offer a greater degree of protection than Deterministic Signatures.

Additionally, it’s very easy to convert a Deterministic Signature scheme into a Hedged Signature Scheme: Just add additional randomness that gets signed as part of the message, then append this randomness to the signature (so the signature can be successfully verified later).

Or, if you’re using a programming language that I publish open source software in, you can just use Dhole Cryptography and not worry about these details.

(Header art by Kyume.)