[107426] in Cypherpunks
Re: PGP Fingerprint
daemon@ATHENA.MIT.EDU (Paul Holman)
Wed Jan 13 20:02:18 1999
Date: Wed, 13 Jan 1999 15:36:32 -0900
From: Paul Holman <pablos@fortnocs.com>
To: cypherpunks@toad.com
Reply-To: Paul Holman <pablos@fortnocs.com>
This is a cryptographically signed message in MIME format.
--------------ms5D4BF1713F91497ECCE50024
Content-Type: multipart/mixed;
boundary="------------A27EB0DF0D297C89DDCCE1B1"
This is a multi-part message in MIME format.
--------------A27EB0DF0D297C89DDCCE1B1
Content-Type: text/plain; charset=us-ascii; x-mac-type="54455854"; x-mac-creator="4D4F5353"
Content-Transfer-Encoding: 7bit
mgraffam@idsi.net wrote:
> Hmm.
> Generating a key with the same fingerprint as another amounts to
finding
> two messages that hash to the same value. A collision. I would not
use
> the term "relatively trivial" to describe such an operation.. unless
> there is something I am missing?
On the surface, this would appear to be the case, but there happens to
be something you're missing. I'll quote
from the comp.security.pgp FAQ:
<QUOTE>
4.10 Can a public key be forged?
There are four components in a public key, each of which has its own
weaknesses. The four components are
user IDs, key IDs, signatures and the key fingerprint.
The user ID
It is quite easy to create a fake user ID. If a user ID on a key is
changed, and the key is then added to another
keyring, the changed user ID will be seen as a new user ID and so it
gets added to the ones already present.
This implies that an unsigned user ID should never be trusted. Question
6.3 discusses this in more detail.
The key ID
It is possible to create a key with a chosen key ID. Paul Leyland
<pcl@sable.ox.ac.uk> explains:
A PGP key ID is just the bottom 64 bits of the public modulus
(but only the bottom 32 bits
are displayed with pgp -kv). It is easy to select two primes
which when multiplied together
have a specific set of low-order bits.
This makes it possible to create a fake key with the same key ID as an
existing one. The fingerprint will still
be
different, though.
By the way, this attack is sometimes referred to as a DEADBEEF attack.
This term originates from an
example
key with key ID 0xDEADBEEF which was created to demonstrate that this
was possible.
Signatures
There are currently no methods to create a fake signature for a user ID
on someone's key. To create a
signature
for a user ID, you need the signatory's secret key. A signature actually
signs a hash of the user ID it applies
to,
so you can't copy a signature from one user ID to another or modify a
signed user ID without invalidating
the
signature.
The key fingerprint
Yes, it is possible to create a public key with the same fingerprint as
an existing one, thanks to a design
misfeature in PGP. The fake key will not be of the same length, so it
should be easy to detect. Usually such
keys have odd key lengths.
Paul Leyland provided the following technical explanation:
Inside a PGP key, the public modulus and encryption exponent are
each represented as the
size of the quantity in bits, followed by the bits of the
quantity itself. The key fingerprint,
displayed by pgp -kvc, is the MD5 hash of the bits, but NOT of
the lengths. By transferring
low-order bits from the modulus to the high-order portion of the
exponent and altering the two
lengths accordingly, it is possible to create a new key with
exactly the same fingerprint.
4.11 How do I detect a forged key?
As explained in question 4.10, each component of the public key can be
faked. It is, however, not possible to
create a fake key for which all the components match.
For this reason, you should always verify that key ID, fingerprint, and
key size correspond when you are
about
to use someone's key. And when you sign a user ID, make sure it is
signed by the key's owner!
Similarly, if you want to provide information about your key, include
key ID, fingerprint and key size.
</QUOTE>
--
Paul Holman 907.562.7660
Special Agent fax 907.562.3687
Fort Nocs pablos@fortnocs.com
www.fortnocs.com PGP KeyID: 0x3F5AB569
--------------A27EB0DF0D297C89DDCCE1B1
Content-Type: text/x-vcard; charset=us-ascii;
name="pablos.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Paul Holman
Content-Disposition: attachment;
filename="pablos.vcf"
begin:vcard
n:Holman;Paul
tel;cell:907.250.1757
tel;fax:907.562.3687
tel;home:907.349.1938
tel;work:907.562.7660
x-mozilla-html:TRUE
url:http://www.fortnocs.com
org:Fort Nocs
version:2.1
email;internet:pablos@fortnocs.com
title:Special Agent
note:PGP KeyID: 0x3F5AB569
adr;quoted-printable:;;3601 C Street=0D=0ASuite 1400;Anchorage;Alaska;99503;USA
x-mozilla-cpt:;1
fn:Paul Holman
end:vcard
--------------A27EB0DF0D297C89DDCCE1B1--
--------------ms5D4BF1713F91497ECCE50024
Content-Type: application/x-pkcs7-signature; name="smime.p7s"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="smime.p7s"
Content-Description: S/MIME Cryptographic Signature
MIIIcwYJKoZIhvcNAQcCoIIIZDCCCGACAQExCzAJBgUrDgMCGgUAMAsGCSqGSIb3DQEHAaCC
BiAwggLfMIICSKADAgECAgJFFTANBgkqhkiG9w0BAQQFADCBuTELMAkGA1UEBhMCWkExFTAT
BgNVBAgTDFdlc3Rlcm4gQ2FwZTEUMBIGA1UEBxMLRHVyYmFudmlsbGUxGjAYBgNVBAoTEVRo
YXd0ZSBDb25zdWx0aW5nMSkwJwYDVQQLEyBUaGF3dGUgUEYgUlNBIElLIDE5OTguOS4xNiAx
Nzo1NTE2MDQGA1UEAxMtVGhhd3RlIFBlcnNvbmFsIEZyZWVtYWlsIFJTQSBJc3N1ZXIgMTk5
OC45LjE2MB4XDTk4MTAyNjE2MzIxNFoXDTk5MTAyNjE2MzIxNFowWjEPMA0GA1UEBBMGSG9s
bWFuMQ0wCwYDVQQqEwRQYXVsMRQwEgYDVQQDEwtQYXVsIEhvbG1hbjEiMCAGCSqGSIb3DQEJ
ARYTcGFibG9zQGZvcnRub2NzLmNvbTCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEA0z2O
1Zwiij67thFmoJUVbqbRtXdksNJyZ1NiaZzYjY6VeD6yv+7QNMSbat1svJIaoCRVUjjB775A
UjOJMXNLp1pFZG1FNpiokggQw+UTQZpnb10tM5g8j+sRYhbw8neshkCBOOHZpn5NviYLcC8K
CQKmk04xwKId1njKCXvVHbcCAwEAAaNUMFIwEQYJYIZIAYb4QgEBBAQDAgWgMA4GA1UdDwEB
/wQEAwIFoDAMBgNVHRMBAf8EAjAAMB8GA1UdIwQYMBaAFP4+YJxrjA+w2DPGysYeWLBxOLXg
MA0GCSqGSIb3DQEBBAUAA4GBAFED8asL/AsNC/wbHF/ODvddHFezMDy03MGFe+KIhiqB+eTW
R+CjkfJrYkyjVWYY/YIjMExNU2V1IRlN08wv92swp8f0p8w3fOTn/9v2YyJjO68SNLgyU2Rn
/kzRJ/Epe6CdKjbG7h+GMWBMmj0zrJIXdRV8q0bY0zKBjrHWUq78MIIDOTCCAqKgAwIBAgIB
CjANBgkqhkiG9w0BAQQFADCB0TELMAkGA1UEBhMCWkExFTATBgNVBAgTDFdlc3Rlcm4gQ2Fw
ZTESMBAGA1UEBxMJQ2FwZSBUb3duMRowGAYDVQQKExFUaGF3dGUgQ29uc3VsdGluZzEoMCYG
A1UECxMfQ2VydGlmaWNhdGlvbiBTZXJ2aWNlcyBEaXZpc2lvbjEkMCIGA1UEAxMbVGhhd3Rl
IFBlcnNvbmFsIEZyZWVtYWlsIENBMSswKQYJKoZIhvcNAQkBFhxwZXJzb25hbC1mcmVlbWFp
bEB0aGF3dGUuY29tMB4XDTk4MDkxNjE3NTUzNFoXDTAwMDkxNTE3NTUzNFowgbkxCzAJBgNV
BAYTAlpBMRUwEwYDVQQIEwxXZXN0ZXJuIENhcGUxFDASBgNVBAcTC0R1cmJhbnZpbGxlMRow
GAYDVQQKExFUaGF3dGUgQ29uc3VsdGluZzEpMCcGA1UECxMgVGhhd3RlIFBGIFJTQSBJSyAx
OTk4LjkuMTYgMTc6NTUxNjA0BgNVBAMTLVRoYXd0ZSBQZXJzb25hbCBGcmVlbWFpbCBSU0Eg
SXNzdWVyIDE5OTguOS4xNjCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEAxKXl1NTQXwgC
7gchfSS/q2uOHusgBwIVhGuP0JMkHxud7miyuSxP6ZNnFxAXHqH5Q0EjuTCqdpe78+f9gcC1
MYv2plAmVPKVKOsZpB6XHrDiuJvBBJoy0DwJbE/kNU/wdr8AEwNPRQhg8/y00JABihLJnLp/
UuoqkzU2PDzkNS8CAwEAAaM3MDUwEgYDVR0TAQH/BAgwBgEB/wIBADAfBgNVHSMEGDAWgBRy
ScJzNMZV9At2coF+d/SH58ayDjANBgkqhkiG9w0BAQQFAAOBgQAsx4IfAUM+B4/uaVypZIL4
wJatkyvLm1DXQJqBwrqmdp08lUDcVcHhVYJ5qwopptUM4VcoPo/5u9XfDZNYqlsti48z5N1Y
FTV2chUpvUL0WpILd1+dJ9uaLU4bggaO0o1Wu5Xe2wxlBd6VngLdUxe+vvxrwxoiehQrYb3C
n156WjGCAhswggIXAgEBMIHAMIG5MQswCQYDVQQGEwJaQTEVMBMGA1UECBMMV2VzdGVybiBD
YXBlMRQwEgYDVQQHEwtEdXJiYW52aWxsZTEaMBgGA1UEChMRVGhhd3RlIENvbnN1bHRpbmcx
KTAnBgNVBAsTIFRoYXd0ZSBQRiBSU0EgSUsgMTk5OC45LjE2IDE3OjU1MTYwNAYDVQQDEy1U
aGF3dGUgUGVyc29uYWwgRnJlZW1haWwgUlNBIElzc3VlciAxOTk4LjkuMTYCAkUVMAkGBSsO
AwIaBQCggbEwGAYJKoZIhvcNAQkDMQsGCSqGSIb3DQEHATAcBgkqhkiG9w0BCQUxDxcNOTkw
MTE0MDAzNjMyWjAjBgkqhkiG9w0BCQQxFgQUP3AR6ZsxrtoEZ3D4rLQi0gZBI9YwUgYJKoZI
hvcNAQkPMUUwQzAKBggqhkiG9w0DBzAOBggqhkiG9w0DAgICAIAwBwYFKw4DAgcwDQYIKoZI
hvcNAwICAUAwDQYIKoZIhvcNAwICASgwDQYJKoZIhvcNAQEBBQAEgYDG0sy8RoLtSl1sOwcm
0gDhfKYNTx52j3DGZTs3DJEkQXFtxmEpa3+mVL5VS2B37h/dsYxdvPJmNU1K9HhtNu71JTf3
ecg4sWNH6BdTo556mb6qgOo5gAfsr+GE0xL5Ux4revTIIuBPDEy7ydzVUugnBOLFXueuZZF6
lffxDkTt8w==
--------------ms5D4BF1713F91497ECCE50024--
