Mailing List Archive: GnuPG: devel

Using second keyring may be misleading?

Index | Next | Previous | View Threaded

guninski at guninski

Jun 14, 2012, 7:10 AM

Post #1 of 15 (381 views)
Permalink

Using second keyring may be misleading?

I was investigating ubuntu's apt-key key management.

Noticed that collision in the keyids lead to strange results.

The first command claims ubuntu signed my key (false) and the second
shows the key is selfsigned.

Attached is a keyring and here is the output:

$rm -rf /home/joro2/.gnupg/ ; gpg --import /usr/share/keyrings/ubuntu-master-keyring.gpg ; gpg --check-sigs --keyring /tmp/sec3
gpg: imported: 1 (RSA: 1)
gpg: no ultimately trusted keys found
/home/joro2/.gnupg/pubring.gpg
------------------------------
pub 4096R/3F272F5B 2007-11-09
uid Ubuntu Archive Master Signing Key <ftpmaster [at] ubuntu>
sig!3 3F272F5B 2007-11-09 Ubuntu Archive Master Signing Key <ftpmaster [at] ubuntu>

/tmp/sec3
---------
pub 1024R/B1C08810 2012-06-14
uid kkkkkkk5 <k@k>
sig!3 B1C08810 2012-06-14 [User ID not found]
sig! 3F272F5B 2012-06-14 Ubuntu Archive Master Signing Key <ftpmaster [at] ubuntu>
sig! 3F272F5B 2012-06-14 Ubuntu Archive Master Signing Key <ftpmaster [at] ubuntu>
sub 1024R/0354AE88 2012-06-14
sig! B1C08810 2012-06-14 [User ID not found]
sub 2179R/3F272F5B 2012-06-14
sig! B1C08810 2012-06-14 [User ID not found]

1 signature not checked due to a missing key

$rm -rf /home/joro2/.gnupg/ ; gpg --import /usr/share/keyrings/ubuntu-master-keyring.gpg ; gpg --no-default-keyring --check-sigs --keyring /tmp/sec3

gpg: Total number processed: 1
gpg: imported: 1 (RSA: 1)
gpg: no ultimately trusted keys found
/tmp/sec3
---------
pub 1024R/B1C08810 2012-06-14
uid kkkkkkk5 <k@k>
sig!3 B1C08810 2012-06-14 kkkkkkk5 <k@k>
sig! 3F272F5B 2012-06-14 kkkkkkk5 <k@k>
sig! 3F272F5B 2012-06-14 kkkkkkk5 <k@k>
sub 1024R/0354AE88 2012-06-14
sig! B1C08810 2012-06-14 kkkkkkk5 <k@k>
sub 2179R/3F272F5B 2012-06-14
sig! B1C08810 2012-06-14 kkkkkkk5 <k@k>

ubuntu's key importing is close to this, if interested check the bash
file "apt-key".

Attachments:

sec3 (1.99 KB)

wk at gnupg

Jun 15, 2012, 5:04 AM

Post #2 of 15 (373 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Thu, 14 Jun 2012 16:10, guninski [at] guninski said:

> Noticed that collision in the keyids lead to strange results.
>
> The first command claims ubuntu signed my key (false) and the second
> shows the key is selfsigned.

That is one of the reasons of my remarks that the use several keyrings
is not worth the trouble. Use one keyring and import the keys you need.

Shalom-Salam,

Werner

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

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

guninski at guninski

Jun 15, 2012, 5:30 AM

Post #3 of 15 (370 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Fri, Jun 15, 2012 at 02:04:44PM +0200, Werner Koch wrote:
> That is one of the reasons of my remarks that the use several keyrings
> is not worth the trouble. Use one keyring and import the keys you need.
>
>

This is ubuntu's problem I don't care much about, but they need to
verify the keys are signed.

The k@k contains a subkey colliding with ubuntu's key 3F272F5B.

The order of importing the keys seems important and in one case a
self signature is reported as other user, in the other case a selfisg
is reported as bad signature from wrong user.

I suppose if the colliding key is first it makes the other key unusable.

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

dkg at fifthhorseman

Jun 21, 2012, 8:57 PM

Post #4 of 15 (358 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On 06/15/2012 08:30 AM, Georgi Guninski wrote:
> This is ubuntu's problem I don't care much about, but they need to
> verify the keys are signed.
>
> The k@k contains a subkey colliding with ubuntu's key 3F272F5B.

colliding at how many trailing bits? what happens if you use
"--keyid-format long"?

--dkg

Attachments:

signature.asc (1.01 KB)

guninski at guninski

Jun 21, 2012, 11:32 PM

Post #5 of 15 (355 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Thu, Jun 21, 2012 at 11:57:47PM -0400, Daniel Kahn Gillmor wrote:
> On 06/15/2012 08:30 AM, Georgi Guninski wrote:
> > This is ubuntu's problem I don't care much about, but they need to
> > verify the keys are signed.
> >
> > The k@k contains a subkey colliding with ubuntu's key 3F272F5B.
>
> colliding at how many trailing bits? what happens if you use
> "--keyid-format long"?
>
> --dkg
>

Sorry but I don't have time to waste on this.

The colliding keyring is in this thread and ubuntu's master key
is available in the distribution and on keyservers.

The attack succeeded (ubuntu used --with-colons).

For me |--keyid-format long| shows complete collision of 64 bits,
same for |--with-colons|, as per design of the collision.

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

dshaw at jabberwocky

Jun 22, 2012, 5:24 AM

Post #6 of 15 (356 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Jun 21, 2012, at 11:57 PM, Daniel Kahn Gillmor wrote:

> On 06/15/2012 08:30 AM, Georgi Guninski wrote:
>> This is ubuntu's problem I don't care much about, but they need to
>> verify the keys are signed.
>>
>> The k@k contains a subkey colliding with ubuntu's key 3F272F5B.
>
> colliding at how many trailing bits? what happens if you use
> "--keyid-format long"?

It collides in all 64 bits. It's a v3 subkey on a v4 key, so presumably uses the standard DEADBEEF trick.

David

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

guninski at guninski

Jun 22, 2012, 7:40 AM

Post #7 of 15 (356 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Fri, Jun 22, 2012 at 08:24:39AM -0400, David Shaw wrote:
>
> It collides in all 64 bits. It's a v3 subkey on a v4 key, so presumably uses the standard DEADBEEF trick.
>

is this trick documented somewhere?

probably i rediscovered it.

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

dshaw at jabberwocky

Jun 22, 2012, 8:23 AM

Post #8 of 15 (357 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Jun 22, 2012, at 10:40 AM, Georgi Guninski wrote:

> On Fri, Jun 22, 2012 at 08:24:39AM -0400, David Shaw wrote:
>>
>> It collides in all 64 bits. It's a v3 subkey on a v4 key, so presumably uses the standard DEADBEEF trick.
>>
>
> is this trick documented somewhere?
>
> probably i rediscovered it.

A few people pointed it out in the mid-1990s (that long ago!) but I think it was first proposed by Paul Leyland at Oxford.

Here's an old posting about it: http://groups.google.com/group/sci.crypt/browse_thread/thread/25248ce8d6dfc1e4/e5372a1bd972dc07

It was one of the many things that prompted the V4 key format. It doesn't break the web of trust, but can confuse people (and implementations) as to which key is which.

David

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

guninski at guninski

Jun 22, 2012, 9:12 AM

Post #9 of 15 (357 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Fri, Jun 22, 2012 at 11:23:20AM -0400, David Shaw wrote:
> A few people pointed it out in the mid-1990s (that long ago!) but I think it was first proposed by Paul Leyland at Oxford.
>
> Here's an old posting about it: http://groups.google.com/group/sci.crypt/browse_thread/thread/25248ce8d6dfc1e4/e5372a1bd972dc07
>
> It was one of the many things that prompted the V4 key format. It doesn't break the web of trust, but can confuse people (and implementations) as to which key is which.
>

So it still confuses implementations? :)

I am doing something similar - fixed the lowest 64 bits of p,q
and generated random high bits until 2 primes are found.

Even (or maybe divisible by 4) v4 keyids would need more
patching or using something other than gpg for key generation.

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

dshaw at jabberwocky

Jun 22, 2012, 11:06 AM

Post #10 of 15 (356 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Jun 22, 2012, at 12:12 PM, Georgi Guninski wrote:

> On Fri, Jun 22, 2012 at 11:23:20AM -0400, David Shaw wrote:
>> A few people pointed it out in the mid-1990s (that long ago!) but I think it was first proposed by Paul Leyland at Oxford.
>>
>> Here's an old posting about it: http://groups.google.com/group/sci.crypt/browse_thread/thread/25248ce8d6dfc1e4/e5372a1bd972dc07
>>
>> It was one of the many things that prompted the V4 key format. It doesn't break the web of trust, but can confuse people (and implementations) as to which key is which.
>>
>
> So it still confuses implementations? :)

Alas :)

Unfortunately, it's pretty inherent in the design. The issuer subpacket that contains the key ID for a signature only has the 64-bit key ID. We'd need a new issuer subpacket that contained the whole fingerprint.

> I am doing something similar - fixed the lowest 64 bits of p,q
> and generated random high bits until 2 primes are found.
>
> Even (or maybe divisible by 4) v4 keyids would need more
> patching or using something other than gpg for key generation.

Yes, that's what I'm doing, with a similar limitation around even numbered key IDs.

David

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

guninski at guninski

Jun 23, 2012, 6:23 AM

Post #11 of 15 (357 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Fri, Jun 22, 2012 at 02:06:56PM -0400, David Shaw wrote:
> > Even (or maybe divisible by 4) v4 keyids would need more
> > patching or using something other than gpg for key generation.
>
> Yes, that's what I'm doing, with a similar limitation around even numbered key IDs.
>
> David

Hm, with even numbered keyids do you have problems when exponentiating
even naturals? Euler's theorems needs $a$ and $n$ to be coprime in
a^phi(n) = 1 mod n ?

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

nicholas.cole at gmail

Jun 24, 2012, 12:42 AM

Post #12 of 15 (354 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

>>>
>>
>> So it still confuses implementations? :)
>
> Alas :)
>
> Unfortunately, it's pretty inherent in the design. �The issuer subpacket that contains the key ID for a signature only has the 64-bit key ID. �We'd need a new issuer subpacket that contained the whole fingerprint.

1. I've never really understood why the full fingerprint *wasn't*
used for this sort of thing. The key ID probably ought to be kept as
much as possible as a human-only convenience. Is there no way to
imagine the standard changing? (I guess this would need a new key
format version, and possibly a new signature format?)

2. At least internally, could gpg get round the problem by indexing
keys by fingerprint, and by checking the validity of the signature as
well as just the key-id in the case of possible ambiguities (or at
least spotting the ambiguity and printing a warning?)

3. I know this is a particular problem with version 3 key ids. How
much stronger are version 4?

Best wishes,

Nicholas

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

dkg at fifthhorseman

Jun 24, 2012, 1:00 PM

Post #13 of 15 (355 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On 06/24/2012 03:42 AM, Nicholas Cole wrote:
>>>>
>>>
>>> So it still confuses implementations? :)
>>
>> Alas :)
>>
>> Unfortunately, it's pretty inherent in the design. The issuer subpacket that contains the key ID for a signature only has the 64-bit key ID. We'd need a new issuer subpacket that contained the whole fingerprint.
>
> 1. I've never really understood why the full fingerprint *wasn't*
> used for this sort of thing. The key ID probably ought to be kept as
> much as possible as a human-only convenience. Is there no way to
> imagine the standard changing? (I guess this would need a new key
> format version, and possibly a new signature format?)

There was a discussion about how this could be accomplished on the
IETF's OpenPGP WG list about this, starting here:

http://www.imc.org/ietf-openpgp/mail-archive/msg09915.html

One interesting outcome was the proposal (which i have failed to
implement) of using an OpenPGP "notation" subpacket with a well-defined
name, and a value of the full fingerprint of the issuer. Compatible
signing applications could insert this subpacket in addition to the
"issuer" subpacket, and compatible verifying applications could use it
to disambiguate between colliding keyids.

--dkg

[0] https://tools.ietf.org/html/rfc4880#section-5.2.3.16

Attachments:

signature.asc (1.01 KB)

wk at gnupg

Jun 25, 2012, 12:06 AM

Post #14 of 15 (355 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Sun, 24 Jun 2012 22:00, dkg [at] fifthhorseman said:

> One interesting outcome was the proposal (which i have failed to
> implement) of using an OpenPGP "notation" subpacket with a well-defined

Time to read that discussion again.

Salam-Shalom,

Werner

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

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

guninski at guninski

Jul 25, 2012, 6:33 AM

Post #15 of 15 (280 views)
Permalink

Re: Using second keyring may be misleading? [In reply to]

On Sun, Jun 24, 2012 at 08:42:07AM +0100, Nicholas Cole wrote:
> 3. I know this is a particular problem with version 3 key ids. How
> much stronger are version 4?
>

For a v.4 64 bit keyid collision the most naiive attack will need
about 2^64 calls to SHA1.

Currently a GPU costing about $500 will break it in about 220 years.
So 220 GPUs will break it in a about year.

Total budget (electricity, etc) might be in the range of $200K - $300K -
someone familiar with hash cracking told me so.

Might be wrong though.

_______________________________________________
Gnupg-devel mailing list
Gnupg-devel [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads