full-disclosure - Re: OT: help generating gpg key with prescribed 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>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Thu, 22 Sep 2011 12:30:30 +0300
From: Georgi Guninski <guninski@...inski.com>
To: Valdis.Kletnieks@...edu
Cc: full-disclosure@...ts.grok.org.uk
Subject: Re: OT: help generating gpg key with prescribed
 key ID

On Wed, Sep 21, 2011 at 01:08:59PM -0400, Valdis.Kletnieks@...edu wrote:
> On Wed, 21 Sep 2011 16:21:24 +0300, Georgi Guninski said:
> > for a fishing expedition i need to generate a gpg key with prescribed key ID.
> > 
> > is there a relatively easy way to do this?
> 
> It's intentionally difficult.  It *is* possible to generate a key to match a given key ID,
> or even match a given key fingerprint - however, the resulting key will have odd values
> for key length (for instance, it may be a 25-bit DSA key or 1,343,342 bit RSA or other
> wild stuff).  
> 
> http://www.pgp.net/pgpnet/pgp-faq/pgp-faq-keys.html#key-public-key-forgery
> 
> The tricky part will be getting the person to accept that the key is from who it
> purports to be - this will probably involve some social engineering, especially if
> the target already *has* a trusted key from the person you're trying to forge.

thanks Valdis, very useful references!

just in case this question show up in searches:

in gpg 1.4.10 it is easy to generate RSA keys with prescribed key ID of arbitrary length >= 320.
if the packet version is set to 3, the key ID is just the RSA n \mod 2^64.

the algorithm is:
set the lowest 64 bits to the desired ID.
generate random high bits until you fully factor $n$ using trial division or EC.
number theory is on your side.
a disadvantage is that the key will be weak, but almost sure this can be fixed with more advanced theory.

-- 
joro

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