Occasional invalid RSA signature under repeated signing (gpg 2.3.7 / libgcrypt 1.10.1)

[Diggory Blake]

Hi all — I hit an odd signing failure and did enough digging that I
thought it was worth writing up in case it's useful. Happy to be told
this is already known, or that I'm barking up the wrong tree.

## What happened

I signed a git commit with `git commit --amend --no-edit` (which calls
`gpg -bsau <KEY>` under the hood), and later noticed `git verify-commit`
reports it as `BAD signature`. The key is the right one, and every
other commit I've signed around that time verifies fine — only this one
is broken.

When I dug into it, `gpg --debug 4 --verify` shows the signature is
well-formed but `s^e mod n` doesn't match the PKCS#1 v1.5-padded
expected value. Re-signing the same bytes with the same gpg immediately
after produces a good signature, so it was a one-off. If it were just
that I'd have shrugged and moved on, but the shape of `cmp` turned out
to be pretty specific.

## Environment

- Windows 10 Pro 22H2
- gpg (GnuPG) 2.3.7 (the standalone installer from gnupg.org, not the
  one bundled with Git for Windows)
- libgcrypt 1.10.1
- RSA-4096 key, SHA-256 signatures
- No custom `gpg-agent.conf`, defaults throughout

## The signature that failed

Comparing what gpg computed the expected padded value should be against
what it got from `s^e mod n`:

```
data:  01ff…ff003031300d0609608648016503040201050004200c8d58d745…ad3409
 (expected)
cmp :  a0ed2c0ca3a3401628b3eb3436885a1992b551c589176ef0adddfccea17aef24
       ad6e76df617bf9e4e5a6ecf455feb0cb939030402b9e986e37b2243431070c7e
       f86a1b3e1ee98da51d8250bd215274d98ec3ec329930b65880c2b4c3f7db8559
       … (matches n bytewise for ~480 bytes with byte 1 offset by −2) …
       <32-byte tail varies per failure>
```

The public modulus starts:

```
n:     a0ef2c0ca3a3401628b3eb3436885a1992b551c589176ef0adddfccea17aef24
       ad6e76df617bf9e4e5a6ecf455feb0cb939030402b9e986e37b2243431070c7e
       …
```

Byte 1 of `cmp` is `0xed`, byte 1 of `n` is `0xef`, so `cmp` looks like
`n − 2^4081` in the high half. Middle 460+ bytes match `n` exactly.
Only the last 32 bytes differ from a straight copy of `n`.

I checked (with an independent BigInt reimplementation) that this is
the actual `s^e mod n`, not just something libgcrypt's debug printer
was showing me — same result.

## Reproducer

I wondered how rare this actually was, so I wrote a small stress
harness — a Node script that loops `gpg -bsau <KEY>` on a fixed 1305-byte
payload and verifies each signature. Rough hit rates:

- Sequential (1 sign at a time): **1 BADSIG in 500**
- 5-way concurrent: **1 BADSIG in ~100–200**

So concurrency isn't necessary — it just makes it faster to reproduce.

I collected two more BADSIGs this way. Both have the same shape as the
original: the first 480 bytes of `s^e mod n` are byte-for-byte identical
to the original failure (`a0ed2c0ca3a3401628b3eb…`), and only the
trailing 32 bytes vary. Three independent failures agreeing to that
extent doesn't look like random memory noise; it looks like a specific
intermediate value is leaking through.

## Fault-attack safety

Before sharing failing signatures I checked they don't enable a
Bellcore-style CRT fault attack. For each failure:

```
gcd(|s^e mod n − PKCS1_pad(hash)|, n) = 1
```

so the corruption affects both CRT branches (mod p *and* mod q)
coherently, not one branch only. The private key isn't recoverable
from these signatures.

That's also an interesting data point about the mechanism, I think —
it's not a fault in one exponentiation but something that survives
CRT recombination.

## Things I ruled out

- **Race condition** — sequential reproduces at 1/500
- **git → object corruption** — base64 CRC-24 verifies over the sig
  packet; git writes exactly what gpg returned
- **Wrong payload / encoding** — the LEFT16 field in the sig packet
  matches the SHA-256 prefix of the exact bytes git presents to gpg,
  and I brute-forced ~thousands of nearby payload variants (CRLF, BOM,
  encoding header, timestamp sweeps, every tree hash in the repo) —
  none verify
- **Wrong key** — issuer fingerprint is correct
- **Transient bad state** — re-signing the same bytes moments later
  succeeds

## Where I got to on the mechanism

I read some of `libgcrypt-1.10.1/mpi/mpi-pow.c`, `mpi/mpiutil.c`, and
`cipher/rsa.c`, but I didn't manage to pin down the specific line.
The candidates I noticed (may be wrong):

- `_gcry_mpi_powm`'s W==1 branch skips the `MPN_ZERO(rp, rsize)` the
  W>1 branch does (though I'm not sure W==1 is even reached for
  RSA-4096 sign)
- `_gcry_mpi_alloc_limb_space` doesn't zero the buffer except in the
  `nlimbs==0` case
- `secret_core_crt`'s output MPI might reuse limbs from a previous
  operation whose contents happened to be shaped like `n`

The fact that `s^e mod n` is *deterministic* across failures except for
32 bytes at the tail suggests something in the blinding intermediate
path, since the blinding factor `r` is the only fresh input per sign.
libgcrypt 1.11 rewrote the modexp as `_gcry_mpih_powm_lli` which might
already have addressed this class of bug — I haven't tested that yet.

## Attachments

Files in this gist:
https://gist.github.com/Diggsey/ac9232486c7347f60dc77970521ec0bd

- `bad.payload.bin` — the exact 1305-byte payload
- `bad_original.asc`, `bad_concurrent.asc`, `bad_sequential.asc` — three
  failing signatures (one from the original git commit, two from the
  stress reproducer)
- `stress.js` — the reproducer (~90 lines of Node)
- `decode-sigs.js` — the independent BigInt verifier that also does the
  Bellcore-safety `gcd` check

Thanks for taking a look, and apologies if this turns out to already
be fixed in a version I haven't tested.