full-disclosure - PGP CPU time wasta (never refer to pgp key using 32bit key-id)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Date: Tue, 11 May 2010 00:13:39 +0000
From: halfdog <me@...fdog.net>
To: full-disclosure@...ts.grok.org.uk
Subject: PGP CPU time wasta (never refer to pgp key using
	32bit key-id)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

When I created a new pgp key lately, I wanted to have something personal and
easy to remember in the fingerprint, or more precisely the lower 32 bits
(KeyID). The demo code at
http://www.halfdog.net/Projects/PgpKeyTools/KeyGenDSA.java allows to search for
pgp keys with nice KeyID patterns. The program uses data from a given private
key template and varies it. Most of the variation occurs in the "creation time -
secs since 1970" field, so that computation is fast enough (gives ~5 hits/day
for every target KeyId with 1024bit DSA on moderate hardware).

At first I wanted to target 0xdeadbeef of course (because it is that famous),
but when I prepared to upload key, I found out that someone else has already
done that years ago, but it seems that no one has attempted it since then. I do
not know which method was used back than, but since difficulty of public key
fingerprint optimization depends on public key block version, it might have been
harder or easier back then (apart from the CPU speed issues).

To honor the creator of these keys, I refrained from searching for deadbeef
KeyIDs and targeted words in the opposite direction.

Searching the keyservers, I found that many good KeyIDs are still free, e.g.
words/phrases "a bad deed", "defaced" and many regular patterns (41414141, 0)

The KeyID 0x0 might be interesting, because at least one server had a problem
searching for such a key:

Invalid_argument("String.sub")

Since the KeyID is only a part of the total fingerprint, this program does not
lessen pgp security as such. When e.g. gpg is checking signatures, the whole
fingerprint is used. But it might be a very bad idea to refer to/compare
essential keys using only the 32bit KeyID and textual information from the
self-signature of a key.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAkvooBIACgkQxFmThv7tq+7pOwCfaLQd6iw3fDTsYpdEymSiHBmp
odEAn0g3s6unTHTRZmJs94HOCWVGT5RW
=Is7G
-----END PGP SIGNATURE-----

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/