Bolt11: Signature verification fails after public key recovery due to s-value malleability

[erickcestari]

Found through differential fuzzing: When decoding a bolt11 invoice the current code performs redundant signature verification after public key recovery, which fails due to ECDSA s-value malleability:

val msg = Crypto.sha256(tohash)
val nodeId = Crypto.recoverPublicKey(sig, msg, recid.toInt())
val check = Crypto.verifySignature(msg, sig, nodeId)  // This fails unnecessarily
require(check) { "invalid signature" }

Root Cause:

• recoverPublicKey accepts both high-s and low-s signatures
• verifySignature only accepts low-s signatures (normalized)
• This creates a mismatch when the signature has a high s-value

Proposed Solution:
Remove the redundant verification check since recoverPublicKey already guarantees signature validity. The additional verifySignature call provides no security benefit but introduces compatibility issues.

Invoice deserialization failed for lnbc1qqygh9qpp5s7zxqqyqqqqqqqqyqqqqcqqqqqqqqqqqqcqpjqqqqqqqqqqqqqqqdqqqqqqqqqqqqqqqqqqqqqqqcqpjqqqqqqqq2qqqqqqqqqqqqqqqqqcqpjqqqqqqqqqqqqqqqqqqqqqqqqsqqqqqdqqqqqqqqqqqqqqrqqqt42398
Module: Lnd
Result: No error
Module: LightningKmp
Result: invalid signature

This is a known issue documented in secp256k1: bitcoin-core/secp256k1#1718

[real-or-random]

I think this is also a bug in BOLT11, which simply doesn't specify whether low-s is a requirement or not.

[erickcestari]

I think this is also a bug in BOLT11, which simply doesn't specify whether low-s is a requirement or not.

You’re right. There are more issues related to non-normalized signatures. In BOLT11, if the n field (a public key) is included, applications attempt to verify the signature together with n and the hash by calling secp256k1_ecdsa_verify directly. Since the signature isn’t normalized beforehand, this leads to invoices with a non-normalized signature being always rejected when n is present.

In other words:

• For BOLT11 invoices without the n field, signatures can be non-normalized.
• For BOLT11 invoices with the n field, the signature must be normalized to pass validation.

This is the behavior from c-lightning:

/* BOLT #11:
	 *
	 * A reader...  MUST check that the `signature` is valid (see
	 * the `n` tagged field specified below). ... A reader...
	 * MUST use the `n` field to validate the signature instead of
	 * performing signature recovery.
	 */
	if (!have_n) {
		struct pubkey k;
		if (!secp256k1_ecdsa_recover(secp256k1_ctx,
					     &k.pubkey,
					     &sig,
					     (const u8 *)&hash))
			return decode_fail(b11, fail,
					   "signature recovery failed");
		node_id_from_pubkey(&b11->receiver_id, &k);
	} else {
		struct pubkey k;
		/* n parsing checked this! */
		if (!pubkey_from_node_id(&k, &b11->receiver_id))
			abort();
		if (!secp256k1_ecdsa_verify(secp256k1_ctx, &b11->sig,
					    (const u8 *)&hash,
					    &k.pubkey))
			return decode_fail(b11, fail, "invalid signature");
	}

rust-lightning:

/// Checks if the signature is valid for the included payee public key or if none exists if it's
	/// valid for the recovered signature (which should always be true?).
	pub fn check_signature(&self) -> bool {
		let included_pub_key = self.raw_invoice.payee_pub_key();

		let mut recovered_pub_key = Option::None;
		if recovered_pub_key.is_none() {
			let recovered = match self.recover_payee_pub_key() {
				Ok(pk) => pk,
				Err(_) => return false,
			};
			recovered_pub_key = Some(recovered);
		}

		let pub_key =
			included_pub_key.or(recovered_pub_key.as_ref()).expect("One is always present");

		let hash = Message::from_digest(self.hash);

		let secp_context = Secp256k1::new();
		let verification_result =
			secp_context.verify_ecdsa(&hash, &self.signature.to_standard(), pub_key);

		match verification_result {
			Ok(()) => true,
			Err(_) => false,
		}
	}

lnd:

	// If the destination pubkey was provided as a tagged field, use that
	// to verify the signature, if not do public key recovery.
	if decodedInvoice.Destination != nil {
		signature, err := sig.ToSignature()
		if err != nil {
			return nil, fmt.Errorf("unable to deserialize "+
				"signature: %v", err)
		}
		if !signature.Verify(hash, decodedInvoice.Destination) {
			return nil, fmt.Errorf("invalid invoice signature")
		}
	} else {
		headerByte := recoveryID + 27 + 4
		compactSign := append([]byte{headerByte}, sig.RawBytes()...)
		pubkey, _, err := ecdsa.RecoverCompact(compactSign, hash)
		if err != nil {
			return nil, err
		}
		decodedInvoice.Destination = pubkey
	}

[t-bast]

Fixed in #806, thanks for the report!