including the entire fingerprint of the issuer in an OpenPGP certification

including the entire fingerprint of the issuer in an OpenPGP certification

[Daniel Kahn Gillmor]

[-- Attachment #1: Type: text/plain, Size: 3191 bytes --]

Hi OpenPGP folks (and Cc'ed notmuch developers/users)--

Some recent discussion about verifying OpenPGP signatures for the
notmuch mail user agent got me thinking about different ways one might
interpret a negative result from a signature made over a message.

Most OpenPGP signatures i've seen use the (unhashed) issuer subpacket to
refer to the low 64 bits of the fingerprint of the issuer's key (the
issuer's "key ID"):

 https://tools.ietf.org/html/rfc4880#section-5.2.3.5

Given that we can't assume that key IDs are unique with any high degree
of confidence, this creates some ambiguity between these states:

 A) "you don't have the key that made this signature"

 B) "this signature is bad"

a user-friendly MUA that thinks it is in state A might do something
sensible like offer to do a keyserver lookup (if it is online), while
simply reporting "signature error" if it thinks it is in state B.

But a devious attacker could potentially create a colliding Key ID (i
believe collisions of the low 64 bits of SHA1 are within reach today,
i'd love to be corrected if this is not the case) and cause the
user-friendly MUA to assume it is in state B when it is actually in
state A.  The attacker doesn't even need access to the message or
signature in question to do this.  They'd only need to have been able to
supply a key to the user at some time in the past.  (e.g. push a new
subkey to the keyservers which a user pulls during a keyring refresh)

One way around this ambiguity would be to include the issuer's entire
fingerprint instead of just the low 64 bits, which would make the
certainty of state A vs. state B much clearer.

Would there be any objection to a new subpacket type for OpenPGPv4 that
would include the remaining 96 bits of the issuer's fingerprint?  (the
"high 96" proposal)

Alternately, what about a new subpacket type that simply includes the
entire 160 bits of the issuer's fingerprint?   (the "full fingerprint"
proposal)

A third proposal would be a new subpacket type that simply includes the
entire public key of the issuer (the "full pubkey" proposal).

I lean toward "high 96", since using it in conjunction with the issuer
subpacket retains backward compatibility with existing tools (which know
how to interpret the issuer subpacket) while introducing the smallest
amount of additional data per signature.

Given that the size of a signature from a 2048-bit RSA key is 256 bytes
already, adding an additional 12 bytes (plus a few bytes of subpacket
overhead) per signature doesn't seem particularly excessive.

I'm also assuming that the typical use of this subpacket would be in the
unhashed section of a signature packet, since it is an advisory field
and not intended to address attacks against an adversary capable of
tampering directly with the data in the signature itself.

I will write code to implement this using an experimental subpacket ID,
but i'd like to know if anyone has any caveats, concerns, or preferences
between the proposals i've outlined above (or entirely different
proposals that would address the underlying concern).

Any thoughts?

Regards,

	--dkg


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 900 bytes --]

Re: including the entire fingerprint of the issuer in an OpenPGP certification

[Jon Callas]

On the one hand, my only disagreement with you is to suggest that your proposal be tied into using SHA256 for a fingerprint. If you're going to expand the keyid to a fingerprint, why not get a better fingerprint?

On the other hand, this has never been a problem. It's harder than you think, because you have to generate a new key each time, which takes a while on RSA. 

Nonetheless, I think it's a good idea. I'd just go all the way to a better fingerprint.

	Jon


On Jan 17, 2011, at 5:47 PM, Daniel Kahn Gillmor wrote:

> * PGP Signed by an unknown key
> 
> Hi OpenPGP folks (and Cc'ed notmuch developers/users)--
> 
> Some recent discussion about verifying OpenPGP signatures for the
> notmuch mail user agent got me thinking about different ways one might
> interpret a negative result from a signature made over a message.
> 
> Most OpenPGP signatures i've seen use the (unhashed) issuer subpacket to
> refer to the low 64 bits of the fingerprint of the issuer's key (the
> issuer's "key ID"):
> 
> https://tools.ietf.org/html/rfc4880#section-5.2.3.5
> 
> Given that we can't assume that key IDs are unique with any high degree
> of confidence, this creates some ambiguity between these states:
> 
> A) "you don't have the key that made this signature"
> 
> B) "this signature is bad"
> 
> a user-friendly MUA that thinks it is in state A might do something
> sensible like offer to do a keyserver lookup (if it is online), while
> simply reporting "signature error" if it thinks it is in state B.
> 
> But a devious attacker could potentially create a colliding Key ID (i
> believe collisions of the low 64 bits of SHA1 are within reach today,
> i'd love to be corrected if this is not the case) and cause the
> user-friendly MUA to assume it is in state B when it is actually in
> state A.  The attacker doesn't even need access to the message or
> signature in question to do this.  They'd only need to have been able to
> supply a key to the user at some time in the past.  (e.g. push a new
> subkey to the keyservers which a user pulls during a keyring refresh)
> 
> One way around this ambiguity would be to include the issuer's entire
> fingerprint instead of just the low 64 bits, which would make the
> certainty of state A vs. state B much clearer.
> 
> Would there be any objection to a new subpacket type for OpenPGPv4 that
> would include the remaining 96 bits of the issuer's fingerprint?  (the
> "high 96" proposal)
> 
> Alternately, what about a new subpacket type that simply includes the
> entire 160 bits of the issuer's fingerprint?   (the "full fingerprint"
> proposal)
> 
> A third proposal would be a new subpacket type that simply includes the
> entire public key of the issuer (the "full pubkey" proposal).
> 
> I lean toward "high 96", since using it in conjunction with the issuer
> subpacket retains backward compatibility with existing tools (which know
> how to interpret the issuer subpacket) while introducing the smallest
> amount of additional data per signature.
> 
> Given that the size of a signature from a 2048-bit RSA key is 256 bytes
> already, adding an additional 12 bytes (plus a few bytes of subpacket
> overhead) per signature doesn't seem particularly excessive.
> 
> I'm also assuming that the typical use of this subpacket would be in the
> unhashed section of a signature packet, since it is an advisory field
> and not intended to address attacks against an adversary capable of
> tampering directly with the data in the signature itself.
> 
> I will write code to implement this using an experimental subpacket ID,
> but i'd like to know if anyone has any caveats, concerns, or preferences
> between the proposals i've outlined above (or entirely different
> proposals that would address the underlying concern).
> 
> Any thoughts?
> 
> Regards,
> 
> 	--dkg
> 
> 
> * Unknown Key
> * 0xD21739E9

Re: including the entire fingerprint of the issuer in an OpenPGP certification

[Peter Gutmann]

Jon Callas <jon@callas.org> writes:

>On the other hand, this has never been a problem. It's harder than you think, 
>because you have to generate a new key each time, which takes a while on RSA.

Only if you want a secure key. For SSH fuzzy fingerprinting the limiting 
factor is the hashing, not the rate at which you can crank out keys, as long 
as you don't mind that the keys aren't very secure. OK, they're not secure at 
all, but that doesn't matter since you're going for spoofing, not a secure 
signature forgery.

Peter.

Re: including the entire fingerprint of the issuer in an OpenPGP certification

[David Shaw]

On Jan 17, 2011, at 8:47 PM, Daniel Kahn Gillmor wrote:

> Would there be any objection to a new subpacket type for OpenPGPv4 that
> would include the remaining 96 bits of the issuer's fingerprint?  (the
> "high 96" proposal)
> 
> Alternately, what about a new subpacket type that simply includes the
> entire 160 bits of the issuer's fingerprint?   (the "full fingerprint"
> proposal)

I like this idea.  I would do it as "full fingerprint" myself.  The difference in storage between 160 bits and 96 bits is all of 8 bytes.  I think the simplicity of being able to say the whole fingerprint is in there is worth a measly 8 bytes.

Do we necessarily need a new subpacket type for this?  It could pretty easily be a notation.

David

Re: including the entire fingerprint of the issuer in an OpenPGP certification

[Daniel A. Nagy]

[-- Attachment #1: Type: text/plain, Size: 1726 bytes --]

On 01/18/2011 02:47 AM, Daniel Kahn Gillmor wrote:
> i believe collisions of the low 64 bits of SHA1 are within reach today,
> i'd love to be corrected if this is not the case

I'd suggest using the entire fingerprint as a reference and leaving the
creation date out of the fingerprint calculation for v5 for the
following reasons:

Yes, generating two keys with identical long key ID's is feasible (and
not even particularly expensive on 64-bit machines with dozens of
gigabytes of RAM), but generating a new key with the same 64-bit key ID
as an existing key is on the very far end of the realm of feasibility.
Given the dubious gains from success, I would rule out this attack as
impractical.

Another problem with fingerprints and key IDs is that they are generated
over the key and the creation date, meaning that the same key can have
different key ID's. Since the signature subpacket with the reference is
not part of the hashed data, one can change both the key ID and the
reference and keep the signature valid. Again, I don't know what the
practical value of such an attack might be, but just like in the first
case, it creates an odd situation potentially undermining the trust in
the security of the system. When arguing in front of a non-expert judge,
such quirks erode the claims of rock-solid evidence very badly.

The key ID itself (especially the long one) is not a bad idea, however.
It is a nice compromise in the middle of Zooko's triangle (almost
memorable, almost globally unique and almost secure). In order to make
it more useful, I'd suggest using 20-digit decimal identifiers (like
credit card numbers) instead of 16-digit hexadecimal ones.

Regards,

-- 
Daniel


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Re: including the entire fingerprint of the issuer in an OpenPGP certification

[Peter Gutmann]

"Daniel A. Nagy" <nagydani@epointsystem.org> writes:

>generating a new key with the same 64-bit key ID as an existing key is on the
>very far end of the realm of feasibility.

That should be:

  generating a *secure* new key with the same 64-bit key ID as an existing key
  is on the very far end of the realm of feasibility.

If you don't mind that your key's weak then it's not that much more work than
just finding a 64-bit collision.

Peter.