ed25519 signature verification low order check isn't strong enough

[Rexicon226]

Our current ed25519 implementation tries to avoid an expensive inversion in the verify function by just subtracting the expected signature R and the computed R point and rejecting a low-order result. This fails to catch invalid signatures for a few cases, one of which is shown below,

Zig:

const std = @import("std");
const Ed25519 = std.crypto.sign.Ed25519;

pub fn main() !void {
    const pubkey: Ed25519.PublicKey = .{ .bytes = .{ 134, 231, 47, 92, 42, 114, 21, 21, 16, 89, 170, 21, 28, 14, 230, 248, 226, 21, 93, 48, 20, 2, 243, 93, 116, 152, 240, 120, 98, 154, 143, 121 } };
    const signature: Ed25519.Signature = .fromBytes(.{ 250, 157, 222, 39, 79, 72, 32, 239, 177, 154, 137, 15, 139, 162, 216, 121, 23, 16, 164, 48, 60, 238, 244, 174, 223, 157, 221, 196, 232, 26, 31, 17, 112, 26, 89, 139, 154, 2, 174, 96, 80, 93, 208, 194, 147, 138, 26, 12, 45, 111, 253, 70, 118, 207, 180, 145, 37, 177, 158, 156, 179, 88, 218, 6 });
    const message = [_]u8{ 101, 100, 50, 53, 53, 49, 57, 118, 101, 99, 116, 111, 114, 115, 32, 51 };

    try signature.verify(&message, pubkey);
}

Passes.

Rust:

use ed25519_dalek::{Signature, SigningKey};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let pubkey_bytes = [134, 231, 47, 92, 42, 114, 21, 21, 16, 89, 170, 21, 28, 14, 230, 248, 226, 21, 93, 48, 20, 2, 243, 93, 116, 152, 240, 120, 98, 154, 143, 121];
    let publickey = SigningKey::from_bytes(&pubkey_bytes);

    let signature_bytes = [250, 157, 222, 39, 79, 72, 32, 239, 177, 154, 137, 15, 139, 162, 216, 121, 23, 16, 164, 48, 60, 238, 244, 174, 223, 157, 221, 196, 232, 26, 31, 17, 112, 26, 89, 139, 154, 2, 174, 96, 80, 93, 208, 194, 147, 138, 26, 12, 45, 111, 253, 70, 118, 207, 180, 145, 37, 177, 158, 156, 179, 88, 218, 6];
    let signature = Signature::from_bytes(&signature_bytes);

    let message_bytes = [101, 100, 50, 53, 53, 49, 57, 118, 101, 99, 116, 111, 114, 115, 32, 51];
    publickey.verify(&message_bytes, &signature)?;

    Ok(())
}

Fails.

The edd25519-dalek library takes the cost of the inversion in their verification function by compressing and then equating the compressed forms. They do the equating in constant time, although we don't care about that for our usecases.
https://github.com/dalek-cryptography/ed25519-dalek/blob/02001d8c3422fb0314b541fdb09d04760f7ab4ba/src/verifying.rs#L268
https://github.com/dalek-cryptography/ed25519-dalek/blob/02001d8c3422fb0314b541fdb09d04760f7ab4ba/src/verifying.rs#L247

cc @jedisct1

[jedisct1]

We should only check that 8(S·B)−8R−8(h·A) = 0 .

With your example, the actual cause seems to be a sign issue.

We get:

A =  86e72f5c2a7215151059aa151c0ee6f8e2155d301402f35d7498f078629a8ff9
h = 30ebd9a24cd524abe1b11640e14f6805b6c9648141de26c2d8d384a666fe7f0c

With Zig:

A.h = 3d3d079f7a2321d6314430a8096653b329ff8514f101c44f46dadcc3f0c8c11e

With libsodium:

A.h = 3d3d079f7a2321d6314430a8096653b329ff8514f101c44f46dadcc3f0c8c19e

(same, but negative)

[Rexicon226]

I assume you mean we should check R = [s]B - [k]A (0 = s[B] - [k]A - R) right? We don't need to clear the cofactor for unbatched afaik.

[Rexicon226]

The reason I ask is that there's an important difference. Dishonest signers could create a signature with a non-zero torsion component, and the batch version equation (the one that multiplies by 8 and ends up only checking the prime-order subgroup) would still succeed.

[jedisct1]

Cofactored verification for all cases. See https://eprint.iacr.org/2020/1244.pdf for justification.

rejectUnexpectedSubgroup() can be explicitly called if really needed.

But with correct sign for A.H, the equation doesn't validate.

[Rexicon226]

Got it, thanks for clarifying. So the current course of action looks like:

1. Use cofactored verification for the unbatched one as well
2. Fix whatever this sign bug is. Seems that mul is wrong in this case, but I haven't looked deeply into it, doing so now.

Right?

[jedisct1]

The sign issue appears to have been a false alarm.

The cofactored equation seems to hold. I might have missed something, but I don’t see a bug.

Although the paper shows that this is not necessary, we could still add functions with stricter checks, matching the traditional libsodium behavior, that Rust library, and other implementations for compatibility.

[Rexicon226]

What level of strictness are you thinking? verify_strict like ed25519-dalek? Do we use the cofactorless verification? Could you maybe lay out a bit more info on what you are looking for exactly?

[jedisct1]

Cofactored verification is now the recommended approach, so the existing functions should remain unchanged.

We can, however, add functions for cofactorless verification.