pkcs1v15.rs:verify too strict?

[nwalfield]

This change (I think) is causing some signatures to no longer verify. In particular, the check:

    if sig >= pub_key.n() || sig_len != pub_key.size() {
        return Err(Error::Verification);
    }

is failing for a signature in our test suite. The signature is a 2039-bit MPI generated by a 2048-bit RSA key. Thus, the signature data is 255 bytes and the key is 256 bytes. This used to work (admittedly, this was on rsa 0.3; I'm in the process of upgrading our rust crypto dependencies), and it seems to work with the other four crypto backends that we use in Sequoia without any special treatment. Manually padding the signature to the key length causes verify to correctly verify the signature.

Perhaps we've just been lucky.

Running our test suite, I see:

...
canonicalize: check!(userid "Steve Bannon <steve@breitbart.com>", ua, [V4(Signature4 { version: 4, typ: PositiveCertification, pk_algo: RSAEncryptSign, hash_algo: SHA256, hashed_area: [Subpacket { value: IssuerFingerprint(Fingerprint("E1A98F265261892482B39222F345D6C0DC83D9B1")), authenticated: false }, Subpacket { value: SignatureCreationTime(1515317542), authenticated: false }, Subpacket { value: KeyFlags(CS), authenticated: false }, Subpacket { value: KeyExpirationTime(63072000s), authenticated: false }, Subpacket { value: PreferredSymmetricAlgorithms([AES256, AES192, AES128, TripleDES]), authenticated: false }, Subpacket { value: PreferredHashAlgorithms([SHA256, SHA384, SHA512, SHA224, SHA1]), authenticated: false }, Subpacket { value: PreferredCompressionAlgorithms([Zlib, BZip2, Zip]), authenticated: false }, Subpacket { value: Features(MDC), authenticated: false }, Subpacket { value: KeyServerPreferences(no modify), authenticated: false }], unhashed_area: [Subpacket { value: Issuer(KeyID("F345D6C0DC83D9B1")), authenticated: false }], additional_issuers: [], digest_prefix: "EC6A", computed_digest: None, level: 0, mpis: RSA { s: 2039 bits: 6C69 9144 3A1F 8676 0707 1132 C9FC 6626 4644 B39E 2A08 07BF 32E8 8AA1 8FC7 5034 FD90 2BD9 A921 ACCB C337 E845 A936 8453 D1E5 4F1E 4F51 FDA4 E20F 8A55 CDEC 84B7 7C45 66EA A0C6 526B 4FFA E2DA DB73 37E3 D198 88E1 D916 288D 91FB A17F E11C BAAC 6790 067C 0A4E 9D73 FB1D 870D 552D 966D 5CD5 1B9B 33C2 8E87 9979 5D19 D0A1 FC11 2586 E9EF C88D 3C41 B4DB 6597 2C32 9B3B 74E3 09DB 0999 8181 EA53 E1F5 F600 BC8E F18A 04A0 65DC 31AC 6486 4E7C 22FE 1B26 1202 A416 A47C 516F 968E DEEF 88C6 2BE4 1AB3 A039 57D9 FB95 DCB9 1210 6B2F EF9C 8F6C 229A CCDF 8CB0 8063 EE08 15C0 CF12 3CA1 DD40 5279 44C9 FB71 12E6 E47A E321 D7F8 DD6B C533 103E 9B46 2DD2 2548 5E } })], verify_userid_binding, ...)
canonicalize: Sig EC6A, type = PositiveCertification doesn't belong to userid "Steve Bannon <steve@breitbart.com>": verification error
...

Note the 2039-bit signature and the "verification error" message. This is from the cert::test::merge unit test. You should be able to reproduce the failure as follows:

git clone https://gitlab.com/sequoia-pgp/sequoia.git
cd sequoia
git switch origin/neal/dependencies
cargo test -p sequoia-openpgp --no-default-features --features sequoia-openpgp/compression,sequoia-openpgp/allow-experimental-crypto,sequoia-openpgp/allow-variable-time-crypto,sequoia-openpgp/crypto-rust -- cert::test::merge

I apologize if this is our bug, and appreciate any support. Thanks.

[tarcieri]

Do you have any information on what produced that signature?

This check was intended to reduce malleability but if there are notable libraries producing signatures without this property we may need to relax the check for interop purposes.

[nwalfield]

Do you have any information on what produced that signature?

It was produced by Sequoia using the Nettle backend.

This check was intended to reduce malleability but if there are notable libraries producing signatures without this property we may need to relax the check for interop purposes.

Can you please explain a bit more what you are thinking.

Are you saying that these signatures are out of spec? If so, what is out of spec, the number of leading 0 bits or the lack of the leading 0 byte?

In OpenPGP, MPIs have their leading zeros stripped. Adding them back manually is not a big deal, but our other crypto backends automatically zero pad, it seems. Do you think they are doing something dangerous?

[nwalfield]

By the way, the OpenPGP interoperability test suite includes a number of test vectors that exercise this:

Improbably short RSA signatures

Explores whether implementations properly handle improbably short RSA signatures. RSA signatures are of the same size as the signing key's modulus. However, OpenPGP will strip leading zeros, so we can have "short" signatures with implementations either having to pad the signature again, or omitting RFC 3447's length check.

The signatures are over the string "Hello World :)" made using Bob's key.

[nwalfield]

In a conversation with @teythoon, he said:

09:37 <teythoon> neal: i kinda think it is not unreasonable for the rsa implementation to
                 reject the signature if it has the wrong length
09:37 <teythoon> neal: see e.g. https://datatracker.ietf.org/doc/html/rfc8017#section-9.1.2
09:38 <teythoon> then again, most implementations seem to handle it fine 
09:39 <teythoon> otoh, nettle for example is really picky about truncation of ecc points and scalars
09:41 <teythoon> i think that is because with rsa people expect that kind of truncation to happen,
              and you can scale the artifact sizes to fit your threat model, whereas modern algorithms
              produce and consume artifiacts of fixed sizes

I've changed sequoia to deal with rsa's semantics. Feel free to close.

[tarcieri]

FWIW #272 was the impetus for these changes

[tarcieri]

Closing for now. We'll see if someone else complains.

[nwalfield]

Thanks for your help.