ECDSA signature verification fails with "Signature is invalid" due to non-minimal DER encoding of r/s #151

They say the best testers are the users, and since I'm kinda a power user and caught this error on both my phones with FairEmail using this library, I started to investigate. After a couple hours of doing it, here are my findings with claude code, a confirmed bug that can be fixed with the suggestions below.

I hope I could be of help here.

Summary

EcdsaSignatureVerifier.getSignature() (in minidns-dnssec/src/main/java/org/minidns/dnssec/algorithms/EcdsaSignatureVerifier.java) converts the raw wire-format ECDSA signature (fixed-length r || s) into ASN.1 DER before handing it to java.security.Signature.verify(). The conversion correctly adds a leading 0x00 pad byte when r[0]/s[0] has its high bit set, but it never strips a leading 0x00 byte that is already present in the raw value when that byte isn't actually required for sign disambiguation.

This produces a non-minimal (non-canonical) DER INTEGER encoding whenever a real signature's r or s happens to start with 0x00 followed by a byte whose high bit is clear. The JDK's default SunEC provider parses signatures strictly and rejects this as malformed:

java.io.IOException: Invalid encoding: redundant leading 0s
	at java.base/sun.security.util.DerValue.getBigIntegerInternal(DerValue.java:658)
	at java.base/sun.security.util.DerValue.getPositiveBigInteger(DerValue.java:639)
	at java.base/sun.security.util.ECUtil.decodeSignature(ECUtil.java:288)
	at java.base/sun.security.ec.ECDSASignature.engineVerify(ECDSASignature.java:514)
	at java.base/java.security.Signature.verify(Signature.java:777)

Verifier.verify() then throws DnssecValidationFailedException("Signature is invalid.") even though the signature is cryptographically valid — it's purely a DER re-encoding bug, not a real DNSSEC failure.

Because this depends only on the random r/s values of a given signature (roughly a 1-in-256 chance per component), it:

• affects any zone/key combination whose current RRSIG happens to hit this byte pattern, and stops affecting it once the zone re-signs with a new signature — so it can appear and disappear over time for the same domain
• is completely independent of which resolver serves the answer (reproduced against multiple unrelated DNSCrypt resolvers)
• affects any RRset type, not just DNSKEY

This is very likely the underlying cause of at least some reports like #132 ("DNSSEC failing for some users no matter what resolver they use") — that issue's proximate error is different ("No signatures were attached to answer"), but the "fails regardless of resolver, sometimes works after retry" symptom pattern is exactly what this bug produces if the RRSIG differs between an initial answer and a retried one (e.g. due to a nlnetlabs-style rolling signature or algorithm rotation).

Reproduction

Captured against the live authoritative chain for a real domain (ksol.io, algorithm 13 / ECDSAP256SHA256):

RRSIG DNSKEY 13 2 3600 20260901201037 20260818191037 14365 ksol.io. yeyRejP8zfsIfyeKMFLOsmhBoJtzqHN2iQ7cpnBfAMYARIEuG+gqJRsU5POgYahnhmrAGSLgDQCSx7hVI6oE/w==

The raw signature's s component (last 32 bytes) is 0044812e1be82a251b14e4f3a061a867866ac01922e00d0092c7b85523aa04ff — a redundant leading 0x00 (next byte 0x44 has its high bit clear, so the zero isn't needed for sign disambiguation).

Steps:

1. Fetch the DNSKEY RRset + RRSIG for ksol.io from any resolver.
2. Call Verifier.verify(dnskeyRecords, rrsig, matchingKey) — throws DnssecValidationFailedException: Signature is invalid.
3. Independently verify the exact same canonicalized RRset bytes (Verifier.combine() output) and signature with a different DNSSEC-agnostic library (confirmed here with Python's cryptography + dnspython, which does correct minimal DER encoding) — signature verifies as valid.
4. Isolate to the DER step alone: re-encode the same raw r/s bytes with minidns's current logic vs. a corrected minimal-DER encoder, and call java.security.Signature.verify() directly (no minidns code involved) against the same content/pubkey:
   • minidns's current encoding → SignatureException: Invalid encoding for signature (redundant leading 0s)
   • minimally-encoded DER → verifies true

This confirms the bug is entirely in the raw→DER conversion step, not in canonicalization, key selection, or the actual cryptographic signature.

Suggested fix

In getSignature(), instead of only ever writing the full fixed-length r/s with at most one added pad byte, strip all redundant leading 0x00 bytes first, then add back exactly one pad byte only if the remaining high-order byte has its sign bit set:

private static byte[] toMinimalUnsignedInt(byte[] v) {
    int start = 0;
    while (start < v.length - 1 && v[start] == 0 && (v[start + 1] & 0x80) == 0) {
        start++;
    }
    byte[] trimmed = Arrays.copyOfRange(v, start, v.length);
    if ((trimmed[0] & 0x80) != 0) {
        byte[] withPad = new byte[trimmed.length + 1];
        System.arraycopy(trimmed, 0, withPad, 1, trimmed.length);
        return withPad;
    }
    return trimmed;
}

...and use the resulting length in place of the current rlen/slen computation (the sequence length byte still fits in a single byte for P-256/P-384, so no other change is needed there).

Environment

• minidns git HEAD as of 2024-10-24 (46a3e8c6c1078daab02905c4cbe016286132601e), so current master is affected.
• Reproduced on desktop OpenJDK 26 (SunEC provider); originally observed on Android (minidns consumers: Cheogram/Conversations and FairEmail both surface the identical "Validation of 2 DNSKEY records failed: Signature is invalid." message from real-world logs), so this is not JDK-version-specific — it's inherent to strict DER parsers per RFC compliance (BouncyCastle would likely reject the same encoding).