Subject: Re: DEADBEEF vs SHA1
From: David Shaw <[email-masked]>
To: IETF OpenPGP Working Group <[email-masked]>
Date: Mon, 21 Feb 2011 21:00:13 -0500
List-Id: <ietf-openpgp.imc.org>

On Feb 21, 2011, at 7:35 AM, Lutz Donnerhacke wrote:

> 
> * Jon Callas wrote:
>> The bottom line is that a key id in that context is a 64-bit binary key
>> into a database. That's all that it is.
> 
> And it is *not unique*. Software has to deal with multiple keys having the
> same ID. Not importing v3, because it might generate such ambigious cases,
> is not an acceptable solution. V3 keys only enforce standard compliant
> behaviour.

I definitely agree.  Unfortunately, very widely deployed code does make the assumption that all keys have a unique ID.  A better fix for this problem is to fix that code, but that is complex and will likely not happen quickly.  A blockage of V3 keys is not the ideal fix for the problem, as V4-V4 collisions are still possible.  Given how easy it is to make a V3-V4 collision, and how hard it is to make a V4-V4 one, giving an option to block V3 goes a long way to avoid (though not eliminate) the problem, and buys time for the proper fix to be developed and released.

David

To: [email-masked]
Path: not-for-mail
From: Lutz Donnerhacke <[email-masked]>
Newsgroups: iks.lists.ietf-open-pgp
Subject: Re: DEADBEEF vs SHA1
Date: Mon, 21 Feb 2011 12:35:04 +0000 (UTC)
Organization: IKS Jena, =?UTF-8?Q?Th=C3=BCringen?= Netz, Fitug
Lines: 8
NNTP-Posting-Host: belenus.iks-jena.de
NNTP-Posting-Date: Mon, 21 Feb 2011 12:35:04 +0000 (UTC)
Sender: [email-masked]

* Jon Callas wrote:
> The bottom line is that a key id in that context is a 64-bit binary key
> into a database. That's all that it is.

And it is *not unique*. Software has to deal with multiple keys having the
same ID. Not importing v3, because it might generate such ambigious cases,
is not an acceptable solution. V3 keys only enforce standard compliant
behaviour.

Subject: Re: DEADBEEF vs SHA1
From: David Shaw <[email-masked]>
Date: Fri, 18 Feb 2011 16:06:59 -0500
Cc: IETF OpenPGP Working Group <[email-masked]>
To: Jon Callas <[email-masked]>
Sender: [email-masked]

On Feb 18, 2011, at 1:29 PM, Jon Callas wrote:

> There are a number of ways to deal with this. For example, I could have a copy of PGP 2.6.3 lying around and use that to decrypt my old things. That's only a mild inconvenience. Similarly, PGP or GnuPG could keep v3 keys around *as* *software* for such archival purposes. It might even make sense from a user experience aspect to have them in historic keyrings that are not in one's face every day.

Right, a historic keyring is the sort of thing I'm envisioning, along with some sort of application knob to use it ("click here to enable V3 keys" or "--enable-v3-keys") or not ("--disable-v3-keys").

David

Subject: Re: DEADBEEF vs SHA1
From: Jon Callas <[email-masked]>
Date: Fri, 18 Feb 2011 10:29:24 -0800
To: IETF OpenPGP Working Group <[email-masked]>
Sender: [email-masked]

I think it's very important to understand the distinction between the protocol(s) we have and machines that implement the protocols. Those machines can be APIs (e.g. OpenPGP SDK, Bouncy Castly, etc.) applications (e.g. GnuPG, PGP Desktop), appliances (e.g. PGP Universal), but they are not the same thing. It's perfectly fine for an application to do some right thing that is not supported by some protocol.

For example, when I was at PGP Corporation, I used to say a lot that OpenPGP is a standard (and a protocol), but PGP is software. The PGP Software implements the OpenPGP protocol, but it also implements the S/MIME protocol, as well as SSL/TLS, X.509, SMTP, and so on. 

It's with that in mind, the difference between the protocol and software is an important part of this discussion.

I agree with Ian completely that there are people who have old (v3 key) encrypted and signed data that they need to get to. Decrypting data is the most important thing. I'm sure that I have some things in old backups that maybe I'd like to decrypt some day without having to break the key they're encrypted to.

There are a number of ways to deal with this. For example, I could have a copy of PGP 2.6.3 lying around and use that to decrypt my old things. That's only a mild inconvenience. Similarly, PGP or GnuPG could keep v3 keys around *as* *software* for such archival purposes. It might even make sense from a user experience aspect to have them in historic keyrings that are not in one's face every day. Or GnuPG could handle it despite it not being any longer standard, or ....

The bottom line is that a key id in that context is a 64-bit binary key into a database. That's all that it is. Yeah, it's derived with a function, but it's just a key.

IETF RFCs are not programming manuals. They are also not requirements documents for applications. They are descriptions of how to properly interoperate, and that's all. Application designers still have to think.

	Jon

Date: Fri, 18 Feb 2011 12:36:56 -0500
From: Daniel Kahn Gillmor <[email-masked]>
To: Werner Koch <[email-masked]>
CC: David Shaw <[email-masked]>, IETF OpenPGP Working Group <[email-masked]>
Subject: Re: DEADBEEF vs SHA1
Sender: [email-masked]

This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--------------enigB023DE46FC2756A1E5F3CDC0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On 02/18/2011 03:22 AM, Werner Koch wrote:
> The part which requires more work is to change all code looking for a
> keyid to iterate over all keyids in the database until it succeeds.  We=

> do this for example for wildcard keyids.  It turned out that this is
> sometimes pretty annoying because the user is forced to enter the
> passphrases for all of his keys.  For the case you describe we won't
> have this problem but it is nevertheless a lot of work to try all
> keyids.  It would be more correct, though.

while it might be more correct to import the new keys, it introduces
dangerous ambiguity to the output of "gpg --check-sigs --with-colons",
as that command identifies certifiers by key ID.

Any tool that relies on the output of "gpg --check-sigs --with-colons"
is currently implicitly expecting only a single key per keyID in the
keyring; otherwise, the output would be ambiguous.

> Disabling v3 import and an option to enable such imports seems to be
> justified and is easy to implement.

That's good to hear, thanks!

	--dkg

--------------enigB023DE46FC2756A1E5F3CDC0
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

--------------enigB023DE46FC2756A1E5F3CDC0--

From: Werner Koch <[email-masked]>
To: David Shaw <[email-masked]>
Cc: IETF OpenPGP Working Group <[email-masked]>
Subject: Re: DEADBEEF vs SHA1
Organisation: g10 Code GmbH
OpenPGP: id=5B0358A2; url=finger:[email-masked]
Date: Fri, 18 Feb 2011 09:22:40 +0100
Sender: [email-masked]

On Thu, 17 Feb 2011 20:12, [email-masked] said:

> import the other one without explicitly deleting the first.  When
> trying to import the second key, GPG fails with "key 689E2211 doesn't
> match our copy".  PGP silently ignores the new key.  Not allowing a
> new key to replace an old one does make some sense (after all, how

Actual this message is here due to my laziness.  A proper implementation
would fallen back to insert that key as a new key.  That would be easy.

The part which requires more work is to change all code looking for a
keyid to iterate over all keyids in the database until it succeeds.  We
do this for example for wildcard keyids.  It turned out that this is
sometimes pretty annoying because the user is forced to enter the
passphrases for all of his keys.  For the case you describe we won't
have this problem but it is nevertheless a lot of work to try all
keyids.  It would be more correct, though.

Disabling v3 import and an option to enable such imports seems to be
justified and is easy to implement.

Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

Subject: Re: DEADBEEF vs SHA1
From: David Shaw <[email-masked]>
Date: Thu, 17 Feb 2011 23:42:52 -0500
To: IETF OpenPGP Working Group <[email-masked]>
Sender: [email-masked]

I think I wasn't as clear as I should have been, so let me try and clarify my thoughts a bit more.  There are two issues here:

I started looking at this in the context of the signing key collision issue that Daniel Gillmor had posted about.  He was concerned about the chance of a SHA-1 V4-to-V4 64-bit collision, and I pointed out there is also a risk of a V3-to-V4 collision, which is vastly easier to accomplish.  Now, Daniel's proposed fix handles both cases, so that would seem to be the end of it.  We've already discussed his fix, and so here's just another reason why it's a useful idea.  So, done.  No problem.  That's the standards part of the message.

However, wearing my implementation hat, we do have a different problem now.  In trying out the V3-to-V4 collision against current implementations in the field, it turns out to be a denial of service attack, as at least the implementations that I tried (PGP 9 and GPG 1.4) can't cope very well with two different keys with the same 64-bit key ID.  The "fingerprint in each signature" is intended to disambiguate between two different keys with the same key ID in order to find the real signer.  However, we don't even get to that point, as we can't import two different keys with the same key ID in the first place (the RFC even warns about this specifically).

The end result is that if someone makes this sort of collision, they can upload them to keyservers (perhaps ironically, SKS can handle multiple keys with the same 64-bit key ID just fine), thus "poisoning" certain keys.  Once a key is poisoned, requesting it from the keyserver will return both the good and bad keys in a (so far as I can tell) nondeterministic order, so anyone fetching that key risks importing the bad one, causing signature verifications from the real key to fail, blocking encryption to the real key, and generally making a nuisance.

My proposed fix for this is not an OpenPGP standard issue, as I'm not proposing removing V3 support from the standard.  Rather, I'm just taking advantage of the fact that many OpenPGP developers read this list to raise awareness of the issue, and point out that adding a knob to enable or disable V3 (as allowed for in the standard) is a fairly simple way to avoid this problem.

David

Subject: Re: DEADBEEF vs SHA1
From: David Shaw <[email-masked]>
Date: Thu, 17 Feb 2011 21:43:07 -0500
Cc: IETF OpenPGP Working Group <[email-masked]>
To: Ian G <[email-masked]>
Sender: [email-masked]

On Feb 17, 2011, at 6:56 PM, Ian G wrote:

> 
> On 18/02/11 6:12 AM, David Shaw wrote:
> ...
>> In terms of the issue that originally started this thread, the proposal to include and compare the complete fingerprint resolves this attack as well (slightly better in this case, in fact, since a V3 fingerprint can't even accidentally collide with a V4 one).
> ...
>> That said, however, (and switching over to implementation thoughts here) given how easy it is to make a V3 DEADBEEF key that collides with a real V4 key, I wonder if it would also be useful for implementations to simply refuse (or at least give the option to refuse) to import any V3 keys.  That might not have been feasible 10 years ago, but nowadays, I suspect most people would not even notice.  Standards-wise, that is fine as 4880 does not require V3 (discourages it, in fact: MUST NOT create, and only MAY accept).
> 
> Two thoughts.  One is that we're not only dealing with code, we're also dealing with data:
> 
>  * People have stored files encrypted to V3 keys (this is to conflate storage security with transport security, but that was common thinking in PGP world).
>  * typically, people have expected things like digital signatures masquerading as human signatures to survive a long time.
>  * some standards require 30 years of technology lifetime.

So those (few, I suspect) people who actually need V3 capability can switch it back on again.  This isn't really a standards question, as 4880 doesn't mandate V3 support.  Any implementation that wants to add a knob to turn it on or off is free to do that.

In the meantime, we cut off a extremely easy denial of service attack.

David

Date: Fri, 18 Feb 2011 01:31:50 +0100
From: "Daniel A. Nagy" <[email-masked]>
Organization: ePoint Systems Ltd.
To: Ian G <[email-masked]>
CC: David Shaw <[email-masked]>, IETF OpenPGP Working Group <[email-masked]>
Subject: Re: DEADBEEF vs SHA1
Sender: [email-masked]

This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--------------enig7A69917390DBBC8CB3943136
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

On 02/18/2011 12:56 AM, Ian G wrote:
>   * typically, people have expected things like digital signatures
> masquerading as human signatures to survive a long time.
>   * some standards require 30 years of technology lifetime.

Actually, these two can be addressed while still doing away with V3 key
format. Since V3 signatures can be generated by V4 keys and the keyID in
V3 signatures is not part of the hashed material, one can re-package the
V3 key in V4 format and change the keyID part in the signature, while
still keeping the whole thing valid, without access to the private key.

The only thing missing would be the self-signature of the key, but that
is a minor compromise in the face of things like keyserver poisoning.

IMHO, of course.

--=20
Daniel A. Nagy
ePoint Systems Ltd.

--------------enig7A69917390DBBC8CB3943136
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

--------------enig7A69917390DBBC8CB3943136--

Date: Thu, 17 Feb 2011 19:23:31 -0500
To: [email-masked]
Subject: Re: DEADBEEF vs SHA1
From: [email-masked]
Sender: [email-masked]

On Thu, 17 Feb 2011 14:12:20 -0500 David Shaw 
<[email-masked]> wrote:

>The problem is that the issuer subpacket doesn't 
>differentiate between V3 and V4, so it's possible to make a 
>DEADBEEF V3 key and use it to do a version rollback / denial of 
>service attack against a V4 key.

....

>In terms of the issue that originally started this thread, the 
>proposal to include and compare the complete fingerprint resolves 
>this attack as well (slightly better in this case, in fact, since 
>a V3 fingerprint can't even accidentally collide with a V4 one).

.....

>I wonder if it would also be useful for 
>implementations to simply refuse (or at least give the option to 
>refuse) to import any V3 keys. 

But if there is an effective solution that offers inclusion, and 
doesn't require any additional work,  (and probably needs to be 
implemented anyway independent of v3 keys), then why choose a path  
of exclusion of V3 keys?

(Even if only for Ian's point, that there are lots of v3 encrypted 
and signed material out there, that should be accessable.)

When Senderek described the ADK flaw, people could have argued 
similarly to exclude V4 keys, (but wisely chose to keep subkey 
capability and simple just fixed the ADK problem).

vedaal

Date: Fri, 18 Feb 2011 10:56:25 +1100
From: Ian G <[email-masked]>
To: David Shaw <[email-masked]>
CC: IETF OpenPGP Working Group <[email-masked]>
Subject: Re: DEADBEEF vs SHA1
Sender: [email-masked]

On 18/02/11 6:12 AM, David Shaw wrote:
...
> In terms of the issue that originally started this thread, the proposal to include and compare the complete fingerprint resolves this attack as well (slightly better in this case, in fact, since a V3 fingerprint can't even accidentally collide with a V4 one).
...
> That said, however, (and switching over to implementation thoughts here) given how easy it is to make a V3 DEADBEEF key that collides with a real V4 key, I wonder if it would also be useful for implementations to simply refuse (or at least give the option to refuse) to import any V3 keys.  That might not have been feasible 10 years ago, but nowadays, I suspect most people would not even notice.  Standards-wise, that is fine as 4880 does not require V3 (discourages it, in fact: MUST NOT create, and only MAY accept).

Two thoughts.  One is that we're not only dealing with code, we're also 
dealing with data:

   * People have stored files encrypted to V3 keys (this is to conflate 
storage security with transport security, but that was common thinking 
in PGP world).
   * typically, people have expected things like digital signatures 
masquerading as human signatures to survive a long time.
   * some standards require 30 years of technology lifetime.

Secondly, isn't the argument more about ditching the Key ID approach? 
If we set up the new way to use only full fingerprints, then any 
imported V3 keys can be indexed on that basis.

iang

PS: I agree with the "must not generate V3 keys" part.  Is it possible 
to widen that with "must not sign or export or encrypt using V3 keys." 
And possibly offer an upgrade mode  "implementations may re-package V3 
keys in V5 format."  Dunno, just whiteboarding here...

Date: Thu, 17 Feb 2011 15:08:05 -0500
From: Daniel Kahn Gillmor <[email-masked]>
Reply-To: IETF OpenPGP Working Group <[email-masked]>
To: IETF OpenPGP Working Group <[email-masked]>
Subject: Re: DEADBEEF vs SHA1
Sender: [email-masked]

This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--------------enigA597F855B6E5B26FE30070B4
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On 02/17/2011 02:12 PM, David Shaw wrote:
> I wonder if it would also be useful for implementations to
> simply refuse (or at least give the option to refuse) to
> import any V3 keys.

I think this seems like a reasonable step to take.  As a user, given the
option between:

 a) losing communication with v3 users

 b) allowing anyone to lock me out of communications with v4 users

i would prefer (a).

	--dkg

--------------enigA597F855B6E5B26FE30070B4
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

--------------enigA597F855B6E5B26FE30070B4--

From: David Shaw <[email-masked]>
Subject: DEADBEEF vs SHA1
Date: Thu, 17 Feb 2011 14:12:20 -0500
To: IETF OpenPGP Working Group <[email-masked]>
Sender: [email-masked]

Hi everyone,

I was thinking about Daniel Gillmor's proposal to include the complete fingerprint in signatures, and specifically this:

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

It occurred to me that it doesn't actually matter whether a 64-bit SHA-1 collision is feasible today or not.  There is a much easier collision that makes this attack trivial without going up against SHA-1 at all.

OpenPGP uses the 64-bit key ID to find the right key to verify a signature (via the issuer subpacket).  However that key ID doesn't have to be the lower 64 bits of the fingerprint like it is in V4.  In V3, it was the lower 64 bits of the modulus, which is trivial to set to whatever the attacker likes (i.e. the DEADBEEF key problem).  The problem is that the issuer subpacket doesn't differentiate between V3 and V4, so it's possible to make a DEADBEEF V3 key and use it to do a version rollback / denial of service attack against a V4 key.

For example, Alice's key (either V3 or V4) has a key ID of E435AEDF689E2211.  Mallory makes a V3 key, matches the key ID E435AEDF689E2211, and distributes it ahead of Alice.  Now any signatures that Alice issues will result in a "bad signature" error, since they will be verified against the wrong key.

To test, I made both Alice's and Mallory's key and tested with both PGP (9.10) and GPG (1.4 from git).  Basically, the attack works as expected.  Not surprisingly, once one key is imported, you can't import the other one without explicitly deleting the first.  When trying to import the second key, GPG fails with "key 689E2211 doesn't match our copy".  PGP silently ignores the new key.  Not allowing a new key to replace an old one does make some sense (after all, how would the implementation know which is "real" and which is "fake"?), but I can see this being a frustration.  Of course, this is a double-edged sword, since if Alice beats Mallory into the keyring, Mallory is locked out.

In terms of the issue that originally started this thread, the proposal to include and compare the complete fingerprint resolves this attack as well (slightly better in this case, in fact, since a V3 fingerprint can't even accidentally collide with a V4 one).

That said, however, (and switching over to implementation thoughts here) given how easy it is to make a V3 DEADBEEF key that collides with a real V4 key, I wonder if it would also be useful for implementations to simply refuse (or at least give the option to refuse) to import any V3 keys.  That might not have been feasible 10 years ago, but nowadays, I suspect most people would not even notice.  Standards-wise, that is fine as 4880 does not require V3 (discourages it, in fact: MUST NOT create, and only MAY accept).

I've pasted the test keys below if anyone wants to play with them.

David

p.s. the PKESK packet doesn't differentiate between V3 and V4 either but the attack is less obvious there - the victim would have to encrypt to the wrong key, and we at least theoretically have the means to discourage this via the web of trust.  It would still be an annoyance, though.

Alice:

Mallory: