RNP claims Paul Wouter's key 7754c9b4b6b15364ca4a88183b132d4dbbae5d31 is invalid.

kaie commented 7 months ago

I fetched Paul's key from DNS (@letoams) I will attach it as a file.

Importing that key into Thunderbird fails. The key isn't revoked, function rnp_key_valid_till64 reports zero, which means "the key was never valid".

Importing into an empty keyring reports the following:

$ rnpkeys --homedir /tmp/rnpring/ --import /tmp/paul-exported.asc 
Keyring directory '/tmp/rnpring/' is empty.
Use "rnpkeys" command to generate a new key or import existing keys from the file or GnuPG keyrings.
[signature_validate() /home/user/github/rnp/src/lib/crypto/signatures.cpp:322] wrong lbits
[signature_validate() /home/user/github/rnp/src/lib/crypto/signatures.cpp:322] wrong lbits

pub   2048/RSA 3b132d4dbbae5d31 2016-01-03 [INVALID]
      7754c9b4b6b15364ca4a88183b132d4dbbae5d31
uid           Paul Wouters (online key) <paul@nohats.ca> [INVALID]
sub   2048/RSA 39d749ae2942c932 2016-01-03 [INVALID]
      3903808100efd9dd73489ad939d749ae2942c932
Import finished: 2 keys processed, 2 new public keys, 0 new secret keys, 0 updated, 0 unchanged.

@ni4 I don't understand why the key isn't accepted. Do you understand in which way this key is broken? Thanks in advance

paul-exported.txt

ni4 commented 7 months ago

@kaie That's because self-signatures on the key contains wrong lbits value (forced to 0x0001), which by RFC 4880 is - Two-octet field holding the left 16 bits of the signed hash value., The left 16 bits of the hash are included in the Signature packet to provide a quick test to reject some invalid signatures.. RNP checks this value and rejects signature, without this check key is validated properly.

kaie commented 7 months ago

Is it correct to reject this key, or is that a bug in RNP?

kaie commented 7 months ago

Paul, which software did you use to generate this key with invalid values?

ni4 commented 7 months ago

Is it correct to reject this key, or is that a bug in RNP?

It's not a bug but decision (which could be changed in case of need) as standard doesn't directly say how to behave in this case. I believe there were some discussion in openpgp mailing list regarding this case, but right now I don't get an idea how to properly search for that thread.

paulwouters commented 7 months ago

I don't remember, but it seems 99.9999% likely that I just used gnupg.

dkg commented 7 months ago

https://www.ietf.org/archive/id/draft-ietf-openpgp-crypto-refresh-13.html#name-notes-on-signatures says:

The high 16 bits (first two octets) of the hash are included in the Signature packet to provide a way to reject some invalid signatures without performing a signature verification. When verifying a v6 signature, an implementation MUST reject the signature if these octets don't match the first two octets of the computed hash.

IIRC, we argued for a while about whether we should be explicit about handling this for v4 signatures, and ultimately decided that since implementer behavior has been ambiguous and undefined for decades in v4, we were not likely to be able to fix this ambiguity in this update, but we could resolve it going forward (that is, for v6 signatures).

You can see this behavior tested in the interop test suite and see that the implementations appear to be split.

dkg commented 7 months ago

See also MR !213 and issue #143.

kaie commented 7 months ago

But why does the key contain those different bytes?

Do you think a buggy implementation produced that key?

Or do you think that the key data might have been corrupted?

I took the key from DNS. Maybe it's possible that @paulwouters made a mistake when converting the key into a key record, or I made a mistake when converting the key back from DNS into a key file?

Paul, are you able to export your key to a file and attach it? Maybe this way we could check whether the same problem happens with your original key.

ni4 commented 7 months ago

Could it be that some key server strips/changes this data as GnuPG doesn't seem to behave in this way?

paulwouters commented 7 months ago

Attached an export and export-minimal

pw-gnupg-export.txt pw-gnupg-export-minimal.txt

paulwouters commented 7 months ago

(github really does not like copy pasting base64)

paulwouters commented 7 months ago

Using hash-slinger's openpgpkey command to --create the DNS OPENPGPKEY record, and the output of the openpgpkey --fetch command.

pw-openpgpkey-create.txt pw-openpgpkey-fetch.txt

dkg commented 7 months ago

Every one of the samples that @paulwouters posted has the two digest prefix octets set to 0x0001

ni4 commented 7 months ago

Given that I didn't see any GnuPG-generated keys with such behaviour (and slight difference in default options, like absence of BZip2 compression) I guess this key was generated by some other implementation, but I cannot insist on it. Anyway, the thing is not to find out who's guilty but how to resolve this case correctly :)

It would be easy to update RNP to ignore this check, but should we actually do that?

kaie commented 7 months ago

I don't have an opinion yet what RNP should do. Could we try to gather some more evidence?

I don't recall any other report from users who claimed they haven't been able to import their keys.

Would it make sense to ask on a gnupg developer's mailing list, whether they are aware if any past version of GnuPG may have had a bug that produced this kind of key?

kaie commented 7 months ago

Apparently open-keychain once had a bug to produce that incorrect data. Paul, could you have been using that to generate the key? https://github.com/open-keychain/open-keychain/issues/2688 https://github.com/open-keychain/open-keychain/pull/2695

letoams commented 7 months ago

No

kaie commented 7 months ago

I've looked at a collection of about 1000 public keys, and in 5 of them I see a signature with 0x0001 lbits. None of the signatures is for a binding signature, they are all in user ID certifications (web of trust).

dkg commented 7 months ago

I've just noted that some future sop update-key command might want to identify and correct this kind of flaw in any certificate it finds, over at https://gitlab.com/dkg/openpgp-stateless-cli/-/issues/29.

@ni4 i agree with your underlying question. The specification suggests that what RNP is currently doing is the right thing for v6 signatures. I wouldn't want you to remove the check completely, as that would make it non-compliant for v6 signatures.

Arguably, this hash prefix field is not a great thing. But if we're going to have it, implementations should populate it correctly, and should indeed produce an error for the signature if it's wrong (otherwise we end up in a situation like this one, where we have different perspectives from different implementations).

One reason given for keeping this field at all is that it makes it easy and relatively cheap for implementations to normalize certificates by sort signatures in certificates where the OpenPGP certifications, self-sigs, and binding signatures have been reordered, before the asymmetric part of the verification process has happened. But (a) i'm not sure how many implementations actually do this, (b) if the field isn't correctly populated, this kind of operation isn't possible anyway, and normalizing implementations would need to fall back to the expensive asymmetric operations anyway, and (c) i'm not sure whether this marginal use case is worth the hassle.

Here is a copy of Paul's certificate with the pair of hash prefix octets corrected (done by hand with PGPy via cert.userids[0]._signatures[0]._signature.hash2 = bytearray(b'\xa1\xc8') and cert.subkeys['3903808100EFD9DD73489AD939D749AE2942C932']._signatures[0]._signature.hash2 = bytearray(b'\x93\x10'):

and here is the corrected DANE record (exported via gpg --export-options export-dane --armor --export 7754c9b4b6b15364ca4a88183b132d4dbbae5d31):

$ORIGIN _openpgpkey.nohats.ca.
; 7754C9B4B6B15364CA4A88183B132D4DBBAE5D31
; Paul Wouters (online key) <paul@nohats.ca>
0357513deb903a056e74a7e475247fc1ffe31d8be4c1d4a31f58dd47 TYPE61 \# 1247 (
    99010d04568990ab010800c34b041ac11b0a62a63f0eec5666334d9f7f5fd78b
    436acc1ba6e17e3e8acd9edd0cadea48d32558dbc350fb93f4f63ef93acd6396
    a92c2b4e9a01506d909bebf93d62a7ce40c4f51d4e30f7537ce1339fd8013322
    a65da840fd2e607faf080cae845495cb31ab8bcc0f82d5196480b723ada1bbbb
    f24ddfb30ead372f1a4b0736dd89f113715dae6bb19d40810440f85e4a0d89c8
    3f6e44e9d4edf6be251aca6e056d5e01bbfd471fe950010db68bdbbb75712be5
    6946d0190ed226a3415143581947c8313dfe433cba956e1ea552ed1431b25b2d
    3219548f1f5c02cbadbac917c19eeb2201e83b311b5e9175eeb2dfca8aae92c6
    987a97e8dfae523c55203d0011010001b42a5061756c20576f75746572732028
    6f6e6c696e65206b657929203c7061756c406e6f686174732e63613e89014c04
    130108001f0502568990ab021b03040b09080706150802090a0b03160102021e
    01021780002109103b132d4dbbae5d311621047754c9b4b6b15364ca4a88183b
    132d4dbbae5d31000108008f48f40b61930e1cf71b95f27551f465cfddc96e1e
    d2719b6d8ca062732fecc19260e04649057df01ba6a51874d79e50ff3f274894
    d4209c83fac8952c264562e995a07aaee3e16e1a27d93f3ef383d2de42b35458
    c0a66e84951bb37753195853b5d2a78737fa971e4b006d1eeff805e28b19bed6
    ed7f408064e9a6c2cc55327bc75d2a3db6cd8d346d6064ea7b910defc3faac5e
    5f2d568f2206c129516261dd9e424f6d000f645c3ccb032aef56a10d8ce0cc79
    490598c3d17bc9733e25c881f9706744f9cef0ce387d8c0888dc555c4f90b762
    7f8c169cf062267c3dc50d23287ff1ae0feda89b3274937f85a8b024193df3ca
    0ad3ed114de9bb99975cdfb9010d04568990ae010800bb774d9b28f04ddf4616
    f705358579f943f57ef75c614ad0ba1cf46ba9af12684ee53a89d8aba07aef7b
    a6f576f5a6ba7025f39f823ccc2699de01ed12e418b5d1134dacfbdaa86c1749
    d7a6730fdd01f8c2c7f008bf5d866df3e32a0add8ed2f1bd15f842295cafa028
    49f4d078c8644763a7d4e92925225e90d70acfe9c261db35f901c35773db2c10
    ef46233b1cd40adf9201034ed7d80d919f6ed05cc00333fb616107232351099a
    fe974a32d9ff774326ab5e36167e02618bf90ac67db0bf347b729c1ec607bd76
    523d4eaae30b6738b958fa39c515e60fb6c34498e18ec10ade700f657245c574
    517397fdfccd9cf025ba155d48b92edd4460cb5d573d00110100018901410418
    010800140502568990ae021b0c050900000000040b090807002109103b132d4d
    bbae5d311621047754c9b4b6b15364ca4a88183b132d4dbbae5d31000107fd1b
    2b8f0df4225f8e0d8f92e6a57c3436c02443798141bfe80f907f21bfc2eb6c26
    28e192cb491dbd11fc254615fc7695a724fe98e4cf670e58140ccd35b8731ebd
    c52ccd830d7385662c483fbcad199c8c49395ebf398d83ac74af952d99d878ba
    2e7416b1a45baded848a91f20784c31dc767e8cf33da7efaed627602b7aa0e4d
    d5bd78321b0185b5baf627ff757963ca75f7211ed001a5d72bec63ee0df3148d
    ddcfe50c54093e5873562d42b780a5d87fe2b02e05d1c451d23200089e57b085
    50d5d7f8cd72d4bc270c715ae14f2c057e99d848e6e8ccceff2e5b430216f148
    1662fd91cfa11824e1128b6f420d454d646fc595757c4b309443fa447ac628
    )

dkg commented 7 months ago

@kaie wrote:

I've looked at a collection of about 1000 public keys, and in 5 of them I see a signature with 0x0001 lbits. None of the signatures is for a binding signature, they are all in user ID certifications (web of trust).

Thanks for doing this research, Kai. By random chance we'd expect 1 in 65336 OpenPGP signatures to have the two left-most octets of hash match 0x0001. @andrewgdotcom maybe you can do a more thorough review of certifications in the hockeypuck network? It would be good to know whether there are any patterns to which specific keys are issuing such a certification; maybe that would let us find someone who is actively using the non-conformant tool.

kaie commented 7 months ago

Thanks Daniel, this allowed me to import Paul's key and send him encrypted email.

kaie commented 7 months ago

In my sample set of 1000 keys I have ~ 187000 sigs

dkg commented 7 months ago

you have a mean of 187 signatures on each certificate‽ that seems quite high to me.

kaie commented 7 months ago

yes. I once ran a script to fetch signer keys, for the signatures found in the keys of my contacts. This might have been before the keyserver spam incident, so I probably have some spam signatures in there.

kaie commented 7 months ago

Note I participated in Fosdem keysigning events twice. If a key has multiple user IDs, and many party people have signed all user IDs, this also can quickly result in a bigger number of signatures.

andrewgdotcom commented 7 months ago

In my sample set of 1000 keys I have ~ 187000 sigs

In a set of 187000 randomly generated sigs one would expect to see ~3 sigs with any given hash prefix. So the reported 5 instances of a 0x0001 hash prefix is slightly high, but comsistent with a random distribution given the small sample size.

andrewgdotcom commented 7 months ago

A quick and dirty audit on a sample subset of the last pre-flooding SKS dump (not so many spammy keys) shows that digest prefixes of 0x1 are an order of magnitude more prevalent than any other prefix.

andrewg@whippet:~/swarm/keydump$ for i in sks-dump-*12.pgp; do sq packet dump < $i 2>/dev/null |grep -I "Digest prefix: 000F"|wc -l; done
2
0
0
3
0
andrewg@whippet:~/swarm/keydump$ for i in sks-dump-*12.pgp; do sq packet dump < $i 2>/dev/null |grep -I "Digest prefix: 0000"|wc -l; done
0
0
0
1
0
andrewg@whippet:~/swarm/keydump$ for i in sks-dump-*12.pgp; do sq packet dump < $i 2>/dev/null |grep -I "Digest prefix: 0001"|wc -l; done
12
5
9
11
9
andrewg@whippet:~/swarm/keydump$

andrewgdotcom commented 7 months ago

And from eyeballing a selection, it would appear that the offending sigs started appearing in August 2015.

ni4 commented 7 months ago

@ni4 i agree with your underlying question. The specification suggests that what RNP is currently doing is the right thing for v6 signatures. I wouldn't want you to remove the check completely, as that would make it non-compliant for v6 signatures.

This should not be a problem as yet we do not insist on v6 compatibility and support, just have some chunks of code which were needed for Thunderbird-PQC. Given that crypto-rerfresh is still seem to be updated, as well as draft-wussler, that would not be an issue for a while.

As for me it is better to allow user to use such key(s) (probably in configurable way) instead of taking him in trouble.

letoams commented 7 months ago

On Thu, 15 Feb 2024, Nickolay Olshevsky wrote:

Given that crypto-rerfresh is still seem to be updated

It is in the RFC Editor queue, so there shouldn't be any changes other then editorial/readability.

andrewgdotcom commented 7 months ago

The offending digest prefixes appear in signatures using both SHA1 and SHA256, so this issue cannot be related to the openkeychain one linked above (which was caused by an unsafe reuse/reinit of a hash algo and therefore would not emit 0x0001 in all cases).

andrewgdotcom commented 7 months ago

The vast majority of the offending digests that I see in the SKS dataset are in default-config keys, i.e. ones that have one userid with one selfsig and one encryption subkey with one selfsig only. In such cases both selfsigs have the broken digest.

ni4 commented 7 months ago

First thought about this as possible explanation: https://github.com/singpolyma/openpgp-php/issues/120#issuecomment-1012034968, but it doesn't seem to apply, as should place value which differs from 0x0001 in this case.

andrewgdotcom commented 7 months ago

@ni4 Yes, the openpgp-php issue used the first two octets of the signed data instead of the unsigned digest - but that wouldn't produce this behaviour.

rnpgp / rnp

RNP claims Paul Wouter's key 7754c9b4b6b15364ca4a88183b132d4dbbae5d31 is invalid. #2191