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

[kaie]

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]

@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]

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

[kaie]

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

[ni4]

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]

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

[dkg]

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]

See also MR !213 and issue #143.

[kaie]

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]

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

[paulwouters]

Attached an export and export-minimal

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

[paulwouters]

(github really does not like copy pasting base64)

[paulwouters]

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]

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

[ni4]

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]

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]

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

[letoams]

No

[kaie]

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]

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'):

-----BEGIN PGP PUBLIC KEY BLOCK-----

mQENBFaJkKsBCADDSwQawRsKYqY/DuxWZjNNn39f14tDaswbpuF+PorNnt0MrepI
0yVY28NQ+5P09j75Os1jlqksK06aAVBtkJvr+T1ip85AxPUdTjD3U3zhM5/YATMi
pl2oQP0uYH+vCAyuhFSVyzGri8wPgtUZZIC3I62hu7vyTd+zDq03LxpLBzbdifET
cV2ua7GdQIEEQPheSg2JyD9uROnU7fa+JRrKbgVtXgG7/Ucf6VABDbaL27t1cSvl
aUbQGQ7SJqNBUUNYGUfIMT3+Qzy6lW4epVLtFDGyWy0yGVSPH1wCy626yRfBnusi
Aeg7MRtekXXust/Kiq6Sxph6l+jfrlI8VSA9ABEBAAG0KlBhdWwgV291dGVycyAo
b25saW5lIGtleSkgPHBhdWxAbm9oYXRzLmNhPokBNQQTAQgAHwUCVomQqwIbAwQL
CQgHBhUIAgkKCwMWAQICHgECF4AACgkQOxMtTbuuXTGhyAgAj0j0C2GTDhz3G5Xy
dVH0Zc/dyW4e0nGbbYygYnMv7MGSYOBGSQV98BumpRh0155Q/z8nSJTUIJyD+siV
LCZFYumVoHqu4+FuGifZPz7zg9LeQrNUWMCmboSVG7N3UxlYU7XSp4c3+pceSwBt
Hu/4BeKLGb7W7X9AgGTppsLMVTJ7x10qPbbNjTRtYGTqe5EN78P6rF5fLVaPIgbB
KVFiYd2eQk9tAA9kXDzLAyrvVqENjODMeUkFmMPRe8lzPiXIgflwZ0T5zvDOOH2M
CIjcVVxPkLdif4wWnPBiJnw9xQ0jKH/xrg/tqJsydJN/haiwJBk988oK0+0RTem7
mZdc37kBDQRWiZCuAQgAu3dNmyjwTd9GFvcFNYV5+UP1fvdcYUrQuhz0a6mvEmhO
5TqJ2Kugeu97pvV29aa6cCXzn4I8zCaZ3gHtEuQYtdETTaz72qhsF0nXpnMP3QH4
wsfwCL9dhm3z4yoK3Y7S8b0V+EIpXK+gKEn00HjIZEdjp9TpKSUiXpDXCs/pwmHb
NfkBw1dz2ywQ70YjOxzUCt+SAQNO19gNkZ9u0FzAAzP7YWEHIyNRCZr+l0oy2f93
QyarXjYWfgJhi/kKxn2wvzR7cpwexge9dlI9TqrjC2c4uVj6OcUV5g+2w0SY4Y7B
Ct5wD2VyRcV0UXOX/fzNnPAluhVdSLku3URgy11XPQARAQABiQEqBBgBCAAUBQJW
iZCuAhsMBQkAAAAABAsJCAcACgkQOxMtTbuuXTGTEAf9GyuPDfQiX44Nj5LmpXw0
NsAkQ3mBQb/oD5B/Ib/C62wmKOGSy0kdvRH8JUYV/HaVpyT+mOTPZw5YFAzNNbhz
Hr3FLM2DDXOFZixIP7ytGZyMSTlevzmNg6x0r5Utmdh4ui50FrGkW63thIqR8geE
wx3HZ+jPM9p++u1idgK3qg5N1b14MhsBhbW69if/dXljynX3IR7QAaXXK+xj7g3z
FI3dz+UMVAk+WHNWLUK3gKXYf+KwLgXRxFHSMgAInlewhVDV1/jNctS8JwxxWuFP
LAV+mdhI5ujMzv8uW0MCFvFIFmL9kc+hGCThEotvQg1FTWRvxZV1fEswlEP6RHrG
KA==
=TELv
-----END PGP PUBLIC KEY BLOCK-----

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]

@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]

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

[kaie]

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

[dkg]

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

[kaie]

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]

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]

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]

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]

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

[ni4]

@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]

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]

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]

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]

First thought about this as possible explanation: singpolyma/openpgp-php#120 (comment), but it doesn't seem to apply, as should place value which differs from 0x0001 in this case.

[andrewgdotcom]

@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.