[Fwd: Backdoor in RSA Discovered]
Adam Young
gr...@netcom.com wrote:
>This is not news.
>It was suggested over a year ago that the classified s-box
>design of DES might well have a secret decomposition --
>known to the NSA -- that would permit relatively trivial
>message recovery for arbitrary DES encrypted messages.
Yes, this is news. I'll explain why in a minute.
DES was designed at IBM, by IBM employees.
>That this is possible under virtually *any* cryptosystem is
>not at all surprising.
In fact it is surprising. Refer to the work of Matt Blaze at
last years crypto. He has shown that with respect to ciphers
like DES, the existence of such backdoors is unlikely.
The fact that the RSA key generation processes can be modified
to contain a backdoor is indeed news. It is a very nontrivial
attack on the way public keys are generated. The attack
utilizes RSA itself and a subliminal channel first mentioned by
Desmedt. It effectively generates keys that display the public
key ciphertext of one of the prime factors of n in the upper order
bits of n itself (n=pq). Hence, n is a number that displays one of
its own prime factors (the ciphertext of p that is).
If you take the time to read the paper, I assure you grady, that
you will find the attack to be novel.
adam
Dept. of Computer Science
Columbia University
William Unruh
In <gradyDs...@netcom.com> gr...@netcom.com (Grady Ward) writes:
>This is not news.
Sorry, but I think it IS news. This is not the standard kind of "message
leaking" by subversion of the algorithm. It assumes a completely safe
and uncrackable algorithm. It is a technique by which one can design the
key generation of
RSA, ElGamel, etc so that only to someone in the know the public key can
also be decrypted to give the private key as well, but there is no
examination of either the public key or the private key which would show
that this is possible. In fact even if you generated thousands of
public/private key pairs, you could not tell that the key generation
mechanism was subverted. Furthermore, even if someone told you it had
been and told you how it was done, you could still not use that
information to read any message unless you had the correct key.
This is not some weakness in the techhnique or
the algorithm. It is a way of using the public key itself to carry the private
key message.
Note that in the case of Viacrypt, one can simply use the key generator
of PGP to generate the key, and the attack would be foiled. It is
however a reason to distrust any secret key-generation mechanism,
whether in hardware or in software. Key generation should be done only
by software whose source code you have and which you know has not been
tampered with.
--
Bill Unruh
un...@physics.ubc.ca
Jerry Leichter
Grady Ward wrote: ...
> Consider DES with the padding of the last few bits to make a full 64
> bit block. Obviously the content of these padding bits -- thrown
> away by DES decryptor not privy to the channel -- can contain
> all kinds of useful information about the message or the key. You
> of course could even encrypt these bits using a key only the privy
> DES encryptor and decryptor had.
I have no idea what this is supposed to mean.
When you use a block cipher, you pad the *cleartext* of the final block, not the
*ciphertext*. It's impossible to pad the ciphertext: The output of the block
cipher is a full block, with all bits significant, even if the input was "short"
(and padded, say, with 0's).
Hiding information in the *cleartext* padding wouldn't accomplish anything: If
the attacker can read the cleartext of the final block, he already knows the key -
so what are you going to leak to him?
In any case, if you use CBC mode - as you probably should - there is no reason not
to pad with zeroes, ones, copies of your mother's name - whatever. Any choice has
precisely no security implications, but any choice that the receiver can check for
validity provides just a bit more protection against attack.
Clever techniques for encoding the length of the actual datastream without
requiring any overhead - thus essentially eliminating simple padding - also have
the property that there's little or no "free play" in the representation.
Now, if you *really* want to leak information in this context, I suppose a better
place is in the IV for CBC setup, or even earlier in whatever random number
generation is used for key setup. (In good protocols, the former is tied closely
to the latter, so one might as well just look at the latter.) Yes, random number
generation has been, and will likely continue to be, a weak spot in many
implementations of cryptosystems. However, it's not a particularly fruitful place
to insert the particular kind of attack under discussion, since there isn't, or
need not be, any coupling between the pieces of the code or hardware that generate
the random numbers and the pieces that know the keys. Yes, if you're given a pure
black box, you can't check this. But if you are allowed to specify your own
random numbers, you should be able to check that what the black box sends was
really calculated from the random numbers you gave it. (This assumes you have a
spec for the correct operation of the black box. If you don't have that, of
course, all bets are off.)
The attack here is very different. It occurs at key-generation time, and hides
the information in the public keys. No method has been proposed for generating
DES keys in a way that hides information within them, short of choosing them from
a restricted space of possible values. In fact, it isn't even clear what that
kind of attack would *mean*. This is an attack against *public* key systems,
where it's the public information that is compromised to reveal the private
information. In a private-key system, there *is* no public information within
which to hide anything. (Or, more accurately, the public information is the
session key messages and the encrypted datastream, and because of their nature
they aren't vulnerable to the same kind of attack.)
-- Jerry
Dave Barr
In article <4ogilo$q...@nntp.ucs.ubc.ca>,
William Unruh <un...@physics.ubc.ca> wrote:
>In <gradyDs...@netcom.com> gr...@netcom.com (Grady Ward) writes:
>>This is not news.
>
>Sorry, but I think it IS news. This is not the standard kind of "message
>leaking" by subversion of the algorithm. It assumes a completely safe
>and uncrackable algorithm.
No, it assumes subversion of the algorithm, or at least the mechanism
or assumptions by which the algorithm is used.
We already knew that any encryption system is susceptable to tampering,
and that through any number of methods security can be either weakened
or eliminated. (Like subvert the random number generator so there's
less keyspace) This is just a clever twist on a known problem.
I think Adam Young should be ashamed of himself for posting this
with the subject "Backdoor in RSA Discovered". It shows a lack
of professionalism to resort to the sorts of self-aggrandizement
that you see on the covers of those magazines on the check-out
line in the grocery store. He's found no "backdoor" in RSA or
any other algorithm for that matter. The only thing he's found
is a clever method to PUT a backdoor in an encryption system
like RSA such that it is hard to detect and such that the private
key can be diviluged to the attacker only.
Sure, it's clever. It may be even news. However not nearly to the degree
if indeed a "Backdoor in RSA" was "Discovered".
--Dave
William Unruh
>No, it assumes subversion of the algorithm, or at least the mechanism
>or assumptions by which the algorithm is used.
Again, I disagree. The algorrithm is assumed to be completely safe. It
is the public key which the user generates which is unsafe. An it is not
unsafe in any detectable way. Ie, you can do any test you desire with
the algorithm, knowing both the public and private keys. You can do any
test you desire on both the public and private keys themselves, and
create as many as you desire, and peform all the randomness tests you
desire. The claim is that even if you know exactly how the process is
implimented, you will still be unable to tell whether your keys are
comprimised. This is not tamper through obscurity. The claim seems to be
that this is tampering which obeys all of the test that one expects a
cryptosystem to obey.
>We already knew that any encryption system is susceptable to tampering,
>and that through any number of methods security can be either weakened
>or eliminated. (Like subvert the random number generator so there's
>less keyspace) This is just a clever twist on a known problem.
Yes, just as there are many ways of implimenting crypto. We now have
certain characteristics which we demand of a good crypto system- ie it
must be impervious to detection of the message even if the full crypto
system technique is known. Similarly this paper introduces a new concept
in tampering. Even if the user knows exactly how the tampering is to be
done, and he has "unlimited" instances of the system, he will be unable
to determine whether or mot that tampering has taken place. This
presents to me at least a brand new idea in tampering, just as post WW2
introduced a new concept of encryption (even though encryption had been
known for 2000 years).("What's so great about DES, RSA, etc. We've known
about encryption for 2000 years by now").
>I think Adam Young should be ashamed of himself for posting this
>with the subject "Backdoor in RSA Discovered". It shows a lack
>of professionalism to resort to the sorts of self-aggrandizement
>that you see on the covers of those magazines on the check-out
>line in the grocery store. He's found no "backdoor" in RSA or
>any other algorithm for that matter. The only thing he's found
>is a clever method to PUT a backdoor in an encryption system
>like RSA such that it is hard to detect and such that the private
>key can be diviluged to the attacker only.
>Sure, it's clever. It may be even news. However not nearly to the degree
>if indeed a "Backdoor in RSA" was "Discovered".
>--Dave
--
Bill Unruh
un...@physics.ubc.ca
Eric Backus
William Unruh (un...@physics.ubc.ca) wrote:
> ba...@math.psu.edu (Dave Barr) writes:
>
> >No, it assumes subversion of the algorithm, or at least the mechanism
> >or assumptions by which the algorithm is used.
>
> Again, I disagree. The algorrithm is assumed to be completely safe. It
> is the public key which the user generates which is unsafe. An it is not
> unsafe in any detectable way. Ie, you can do any test you desire with
> the algorithm, knowing both the public and private keys. You can do any
> test you desire on both the public and private keys themselves, and
> create as many as you desire, and peform all the randomness tests you
> desire. The claim is that even if you know exactly how the process is
> implimented, you will still be unable to tell whether your keys are
> comprimised. This is not tamper through obscurity. The claim seems to be
> that this is tampering which obeys all of the test that one expects a
> cryptosystem to obey.
I disagree (or rather, I agree with Dave Barr). This tampering is
detectable by examining the source code which was used to generate the
keys in the first place, just as other tampering would be detectable
in this way.
It is interesting that this tampering can be done in a way
undetectable except by examining the source, but the source is no less
tainted, and the encryption no less compromised, than if the source
was modified in a myriad of other ways.
--
Eric Backus <er...@lsid.hp.com>
http://labejb.lsid.hp.com/
(206) 335-2495
p.s. You do compile your own PGP executable from a signed copy of the
source, obtained from a widely-publicized location, don't you?
William Unruh
>I disagree (or rather, I agree with Dave Barr). This tampering is
>detectable by examining the source code which was used to generate the
>keys in the first place, just as other tampering would be detectable
>in this way.
We are descending into semantics here. I agree with you tht the key
generation code is comprimised. However, the algorithm is not
comprimised. (ie the crypto algoritm, not the key generation algorithm)
The other novel issue is that it is ONLY by examining the key generation
algorithm that you can discover that it is comprimised. There is no way
by looking only at the output of the generator, even knowing what it
could have done, that you can tell whether it has been comprimised.
>It is interesting that this tampering can be done in a way
>undetectable except by examining the source, but the source is no less
>tainted, and the encryption no less compromised, than if the source
>was modified in a myriad of other ways.
Other ways are detectable if you know or suspect that the tampering has
taken place, just by looking at the output.
>p.s. You do compile your own PGP executable from a signed copy of the
>source, obtained from a widely-publicized location, don't you?
PGP yes. Not if I use Viacrypt. Not if I use Netscape. Not if I use any of RSA Inc
products, not if I use smartcards, ..... This is an attack where only
publically available source code can guard against the attack. It is a
case where software is much more secure than hardware (which turns the
traditional attitude on its head).
--
Bill Unruh
un...@physics.ubc.ca
Robert I. Eachus
> This is an attack where only publically available source code can
> guard against the attack. It is a case where software is much more
> secure than hardware (which turns the traditional attitude on its
> head).
Don't bury this at the end of a message, shout it from the
rooftops! It says that any of the proposed key escrow schemes are and
must be fatally flawed. Now go re-read Ken Thompson's Turing Award
Lecture, "Reflections on Trusting Trust." If you want secure crypto
that you can trust, not only does the source code need to be public,
but you need algorithms for encryption that can either be easily
related to the object code, or which can be "proven" without using
complex tools. (Key generation is critical, encryption is harder to
compromise, and decryption code can be arbitrarily complex, since it
can't leak information.)
In RSA/PGP, the potential weakness is in the selection of the two
prime factors. If the algorithm for doing this given "random" input
is easily understood and verified by hand, the system for generating
public keys is relatively safe. If there is no clear relationship
between the input and the primes selected, you have to verify the
object or machine code--all of it.
My solution, for now, has been to write my own code for generating
and testing prime pairs, and use those keys with PGP or RSA. Even if
the toolkit software is completely trustworthy, I do run more "weak
key" tests than RSA or PGP. It makes the key generation process a
little more painful, but I sleep better at night. (Disclaimer: I have
no horrible secrets to hide, but the government has a lot of
accounting and personnel information they want to hide in transit.)
--
Robert I. Eachus
with Standard_Disclaimer;
use Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...
Marc Thibault
gr...@netcom.com (Grady Ward) writes:
> Agreed. That is why I have never trusted Viacrypt's implementation of what
> we have known as PGP. I have never seem an offer of a source license among
> their prospecti.
Depending on how easily this trojan can be implemented, it
creates a problem with any systems that generate keys on the
users' behalf. Lotus Notes comes to mind.
The bottom line is that you can't trust any system that won't
accept externally generated keys. As in the case of PGP, the
specifications for a trustworthy system's key data should be
public, and the system should accept any key(s) that satisfy
the specification, regardless of source.
Cheers,
Marc
---
This is not a secure channel; Assume nothing.
Marc Thibault Information Systems Architect
http://www.synapse.net/~mthibault
Key fingerprint = 76 21 A3 B2 41 77 BC E8 C9 1C 74 02 80 48 A0 1A
Reality is a point of view
+---- gr...@netcom.com wrote (Wed, 29 May 1996 13:48:55 GMT):
| This is why verifying the source (and by implication, verifying the
| compiler and even the machine instructions regressively) is crucial to
| bag these kinds of attacks.
+----
Signed algorithms in books would be nice too.
--
Gary Johnson "There's no union called the AFL-CIA is there?"
gjoh...@season.com <a href="http://www.efm.org">Walk The Talk</a>
CAMPAIGN '96: Juck 'em if they can't fake a toke.
Peter Simons
ba...@math.psu.edu (Dave Barr) writes:
> I think Adam Young should be ashamed of himself for posting this
> with the subject "Backdoor in RSA Discovered". [...] The only thing
> he's found is a clever method to PUT a backdoor in an encryption
> system like RSA [...]
I fully agree here.
One might even argue that he does not even put a backdoor into RSA but
into key generation, which is not part of RSA itself. And modifying
source code or hardware to weaken the keyspace is not a very new idea
in fact. This attack is known for years, that's why every PGP archive
comes with full source code and is signed by the developers.
I admit that his attack is _very_ smart. But the subject of the
article was kind of well... in Germany we say "sich selbst auf die
Schulter klopfen". :-)
-peter
William Unruh
>ba...@math.psu.edu (Dave Barr) writes:
> > I think Adam Young should be ashamed of himself for posting this
> > with the subject "Backdoor in RSA Discovered". [...] The only thing
> > he's found is a clever method to PUT a backdoor in an encryption
> > system like RSA [...]
>I fully agree here.
So does he. Lay off him already. You are so busy getting wroth that fail
to see what it is that he actually has done.
>One might even argue that he does not even put a backdoor into RSA but
>into key generation, which is not part of RSA itself. And modifying
Precisely.
>source code or hardware to weaken the keyspace is not a very new idea
>in fact. This attack is known for years, that's why every PGP archive
No, neither is encryption a new idea. Thus all of people like Rivest,
etc should stop posting all these ancient ideas like public key crypto
etc. His particular attack has NOT been known for years. It is an attack
specifically aimed at public key crypto and is completely unobservable
unless you have the code for inspection. I'm afraid that I do think it
is new, from my observation of the crypto scene the last few years. You
are like someone who has just watched a horse run the kentuckey derby in
30sec, and then spend your time objecting that the owner put shoe polish
on a white blaze to make it look like an all black horse.
>comes with full source code and is signed by the developers.
But no commercial crypto comes with source code.
--
Bill Unruh
un...@physics.ubc.ca
Peter Simons
un...@physics.ubc.ca (William Unruh) writes:
> So does he. Lay off him already. You are so busy getting wroth that fail
> to see what it is that he actually has done.
Are we a bit bitter today, William?
I appreciate what Mr. Young has done. I have never criticized his
paper and everybody is really happy that he brought this attack to
public attention.
What I, and others, criticized was the subject line: "backdoor in RSA
discovered". You say, paraphrased, that this subject line is not
relevant. I am sure, though, that we all will see this subject line
over and over again in various groups, irc chats, mailing lists,
newspapers and radio reports. :-(
Jeff Makey
-----BEGIN PGP SIGNED MESSAGE-----
In article <4on8o4$s...@nntp.ucs.ubc.ca>,
William Unruh <un...@physics.ubc.ca> wrote:
>no commercial crypto comes with source code.
Someday, perhaps some vendors will sell just their PGP signature (or
futuristic equivalent) on public domain crypto source code.
Essentially, their customers would be paying only for the vendor's
assurance that the software meets stated requirements.
:: Jeff Makey
je...@sdsc.edu
Department of Tautological Pleonasms and Superfluous Redundancies Department
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBMa+lpXgk+FUjFWbdAQG3gQQAlX/YZyDyF0iRzuVK6vKXAY+sKJT8dqa1
1CYTDIQlPgj+hFZbVwxRGex0kpA0JsHRANJWv1ljegIvIKJacGO/W7MuXBT6+SNN
vjDY6pJ7BssIlssU2F6gs5pa54Wzx5wJp86UaAtRRWWQ4TdD+rTeCvn4nRzz9fOo
oYOsz23Ti0E=
=Va58
-----END PGP SIGNATURE-----
Jo Schueth
In article <4oj66r$a...@nntp.ucs.ubc.ca>
un...@physics.ubc.ca (William Unruh) writes:
>Again, I disagree. The algorrithm is assumed to be completely safe. It
>is the public key which the user generates which is unsafe. An it is not
>unsafe in any detectable way. Ie, you can do any test you desire with
>the algorithm, knowing both the public and private keys. You can do any
>test you desire on both the public and private keys themselves, and
>create as many as you desire, and peform all the randomness tests you
>desire. The claim is that even if you know exactly how the process is
>implimented, you will still be unable to tell whether your keys are
>comprimised.
are polynomyally indistinguishable [...] to everyone (including
those who have access to the code of C') except the attacker".
For the "PAP"-implementation given in the paper, this is not true.
In their notation, a quantity called p''' is computed deterministically
from p, using the attacker's public key E. This p''' is then accomodated
in the subliminal channel.
The user's secret key certainly is part of the output of C and C'.
Knowing the factorization n=pq and the code of C', you can compute
p''' from p. Then look for p''' in the upper bits of n.
It is easy to modify C' to thwart this type of counter-attack:
Generate a random number r and construct p deterministically
from a strong hash H(r). Encode E(r) in the subliminal channel,
where E is the attacker's private key.
There is still another problem: If RSA with a k-bit modulus N is
used for E, you have E(r) < N < 2^k. This allows a statistical test,
even after the keyed randomization G with key K+j that is suggested
in the paper. Here, K is fixed and j is small. If you have a large
number of public keys, compute for each of them the inverse of G
for j between 0 and 99, say. So you get 100 possible values for
p'' = E(r) for each public key. Some are immediately ruled out
because they are larger than N. If the keys were generated by C'
instead of C, the fraction of numbers that are smaller than N is
slightly increased: for a wrong guess of j, G^-1(U) is pseudorandom,
but for a right guess G^-1(U) < N is guaranteed.
My conclusion is that the claim cited above does not hold for the
implementation presented in the paper. Some refinement is needed.
Jo
Gary Howland
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 <bi...@whitehouse.gov>
-----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 <j...@aol.com>
-----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*", "ce859f121d419ace45f2a56fafe5ef84ba6144f41901efceb8a889726845dd
a09c002c7bdf42fd73ca652862ca59be9eee540fccc3041b5ca2205d925633");
#
# 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 <j...@aol.com>';
$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*", "ce859f121d419ace45f2a56fafe5ef84ba6144f41901efceb8a889726845dd
a09c002c7bdf42fd73ca652862ca59be9eee540fccc3041b5ca2205d925633");
my $md = restore MPI pack("H*", "0c25fa4c5c12eafd132c6415a0ef68713823d6e12ea5c2cfecbe9eac607c94
75d1b60c2a3aef89438692326d70d88080317b0cd04432d5a0230de572e819");
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 <ga...@systemics.com>
Key fingerprint = 0C FB 60 61 4D 3B 24 7D 1C 89 1D BE 1F EE 09 06
William Unruh
In <17799C46C...@ibm.rhrz.uni-bonn.de> UNQ...@ibm.rhrz.uni-bonn.de (Jo Schueth) writes:
>
>In their paper, they claim indeed that "the output of C and C'
>are polynomyally indistinguishable [...] to everyone (including
>those who have access to the code of C') except the attacker".
>For the "PAP"-implementation given in the paper, this is not true.
Finally, some serious discussion! Thank you.
..........
>My conclusion is that the claim cited above does not hold for the
>implementation presented in the paper. Some refinement is needed.
>
>Jo
--
Bill Unruh
un...@physics.ubc.ca
schl...@bbs.cruzio.com
In article <4ol4f8$j...@nntp.ucs.ubc.ca>, un...@physics.ubc.ca (William Unruh) writes:
>
> Other ways are detectable if you know or suspect that the tampering has
> taken place, just by looking at the output.
Sure, but only if you also know the tampering algorithm.
There are plenty of tampering algorithms known for ruining
RSA key generation. If someone has slipped one of these
into your PGP sources, you are in trouble. So what's the big deal?
Roger
William Unruh
In <DsBEC...@cruzio.com> schl...@bbs.cruzio.com writes:
>There are plenty of tampering algorithms known for ruining
>RSA key generation. If someone has slipped one of these
>into your PGP sources, you are in trouble. So what's the big deal?
You seeem to be of the impression that PGP is the be all and end all of
cryptography. It is not. The dominant crypto in the world is in the
commercial sector- from Netscape, Mastercard, Visa, etc to Banks. In all
of these cases no source code is supplied. If someone slips in a
tampering algorithm, it is serious. (Do you really want to discover that
your bank account has been wiped out?) In general the tampering can be
discovered from theooutput of the system. This ensures tht the tampering
will not take place- it is too dangerous. If however the tampering
cannot be discovered, even if you know of the possibility and the way it
could be done, then the temptation is there to carry it out. (Mind you
with banks, almost anything would probably not be discovered).
It is the converse of good crypto. Crypto has been known for 2000 years.
HOwever good crypto is such that even if you know exactly how the crypto
is being carried out, you still cannot decode the message. Making
insecure algorithms or tampering withthem has also been known for a long
time. Good tampering is such that even if it is known how the tampering
is to occur, it cannot be detected from the output of and input to
the system alone, you have to examine the code. That concept of "secure
tampering" lets call it, is I think new.
--
Bill Unruh
un...@physics.ubc.ca
schl...@bbs.cruzio.com
In article <sFLRoD...@tanda.on.ca>, ma...@tanda.on.ca (Marc Thibault) writes:
> Depending on how easily this trojan can be implemented, it
> creates a problem with any systems that generate keys on the
> users' behalf. Lotus Notes comes to mind.
>
> The bottom line is that you can't trust any system that won't
> accept externally generated keys. As in the case of PGP, the
> specifications for a trustworthy system's key data should be
> public, and the system should accept any key(s) that satisfy
> the specification, regardless of source.
Note that this is a particular weakness of RSA. RSA is much more
susceptible to this sort of attack than other public key systems.
Roger
William Unruh
In <DsE0x...@cruzio.com> schl...@bbs.cruzio.com writes:
>Note that this is a particular weakness of RSA. RSA is much more
>susceptible to this sort of attack than other public key systems.
Young et al describe similar attacks against ElBamal and Diffie Helman
as well.
--
Bill Unruh
un...@physics.ubc.ca
Gary Howland
Jo Schueth wrote:
>
> In article <4oj66r$a...@nntp.ucs.ubc.ca>
> un...@physics.ubc.ca (William Unruh) writes:
>
> >Again, I disagree. The algorrithm is assumed to be completely safe. It
> >is the public key which the user generates which is unsafe. An it is not
> >unsafe in any detectable way. Ie, you can do any test you desire with
> >the algorithm, knowing both the public and private keys. You can do any
> >test you desire on both the public and private keys themselves, and
> >create as many as you desire, and peform all the randomness tests you
> >desire. The claim is that even if you know exactly how the process is
> >implimented, you will still be unable to tell whether your keys are
> >comprimised.
>
> are polynomyally indistinguishable [...] to everyone (including
> those who have access to the code of C') except the attacker".
> For the "PAP"-implementation given in the paper, this is not true.
>
> from p, using the attacker's public key E. This p''' is then accomodated
> in the subliminal channel.
>
> The user's secret key certainly is part of the output of C and C'.
> Knowing the factorization n=pq and the code of C', you can compute
> p''' from p. Then look for p''' in the upper bits of n.
Exactly - well pointed out.
> It is easy to modify C' to thwart this type of counter-attack:
> Generate a random number r and construct p deterministically
> from a strong hash H(r). Encode E(r) in the subliminal channel,
> where E is the attacker's private key.
^^^^^^^
Assuming you mean the attackers public key, then this is a nice
modification. I think it is worth pointing out that encryption
with E would suffice as a hash algorithm, ie. construct p from
E(r) and store E(f(r)) in N (where f() is a trivial function,
such as invert or increment). The benefit of this is that a hash
function is not required in the code, or more importantly, in the
hardware, should the NSA every go for a "stealth clipper".
> There is still another problem: If RSA with a k-bit modulus N is
> used for E, you have E(r) < N < 2^k. This allows a statistical test,
> even after the keyed randomization G with key K+j that is suggested
> in the paper. Here, K is fixed and j is small. If you have a large
> number of public keys, compute for each of them the inverse of G
> for j between 0 and 99, say. So you get 100 possible values for
> p'' = E(r) for each public key. Some are immediately ruled out
> because they are larger than N. If the keys were generated by C'
> instead of C, the fraction of numbers that are smaller than N is
> slightly increased: for a wrong guess of j, G^-1(U) is pseudorandom,
> but for a right guess G^-1(U) < N is guaranteed.
Yes, but it is trivial for the N component of E to start with a few
dozen 1s, making this test impractical.
> My conclusion is that the claim cited above does not hold for the
> implementation presented in the paper. Some refinement is needed.
Quite, but a few lessons can still be learnt. One is that we cannot
trust key generators (hardware or software), without examining
every single component. In many cases this will not be possible
due to the complexity of the task (Note - the object code should
be examined, not the source - verifying the source only verifies the
competence of the authors). Another reason is that the key
generation may be in hardware (RSA in hardware is just around the
corner - imagine if the NSA had a say in the design of the key
generator!).
I can see two possible solutions to this threat - one is the obvious
one of using your own code (eg. PGP) to generate keys. The other
is to insist that the software/hardware generate "vanity" keys,
where the user can specify the upper bits of N, thus leaving no
room for an encrypted factor.
Jo Schueth
In article <31B2DB26...@systemics.com>
Gary Howland <ga...@systemics.com> writes:
>
>Jo Schueth wrote:
>> [...]
>> where E is the attacker's private key.
> ^^^^^^^
>Assuming you mean the attackers public key, then this is a nice
>I can see two possible solutions to this threat - one is the obvious
>one of using your own code (eg. PGP) to generate keys. The other
>is to insist that the software/hardware generate "vanity" keys,
>where the user can specify the upper bits of N, thus leaving no
>room for an encrypted factor.
there is not enough space for a public-key encrypted factor.
It would make the type of attack suggested by Young et al
impossible.
However, it does not close the subliminal channel entirely.
The generator could append a short message to the bits that
were specified by the user. So there is still room left for
the more standard attacks that need less bits.
Maybe it would help if the user was allowed to specify many
bits of n, but at arbitrary positions of his choice, i.e.
if he could supply a mask like 10*0**10*0**1101**001, where
the generator may only fill in the positions marked '*'.
But I haven't thought this through.
Jo
Robert I. Eachus
> I can see two possible solutions to this threat - one is the
> obvious one of using your own code (eg. PGP) to generate keys.
Yes, don't use hardware generated keys even if you use hardware
encryption, and don't use software generated keys unless you have
faith in the software implementation. But note a more subtle scam.
Your public key could be fine, but the IDEA key could be generated as
f(R) where R is say an xor down to 32-bits or 40-bits of the random
input. You would have to search pretty hard to find a reused key, but
someone who knows f(x) can brute force messages easily.
> The other is to insist that the software/hardware generate
> "vanity" keys, where the user can specify the upper bits of N,
> thus leaving no room for an encrypted factor.
I love it, and I'll even make a recommendation for PGP 3.0. The
first few dozen bits should be ones, then a "vanity plate" for the
user consisting of his name, phone number and e-mail address, or any
other string the user wants to put there. If we specify the first 32
bits to be ones, that leaves room for a 60 character string in a
1024-bit key. Keyrings can display this data for keys from 3.0 or
subsequent releases.
One way to close a covert channel, it seems, is to use it for real
information.
schl...@bbs.cruzio.com
While you are at it, don't forget to demand the source code
to Intel's chips. A bug in the circuit layout could ruin security.
Roger
Jo Schueth
Following up un my own stupid article...
In article <1779B10CEE...@ibm.rhrz.uni-bonn.de>
I wrote:
>
>In article <31B2DB26...@systemics.com>
>Gary Howland <ga...@systemics.com> writes:
>
>>I can see two possible solutions to this threat - one is the obvious
>>is to insist that the software/hardware generate "vanity" keys,
>>where the user can specify the upper bits of N, thus leaving no
>>room for an encrypted factor.
>
>there is not enough space for a public-key encrypted factor.
>It would make the type of attack suggested by Young et al
>impossible.
>
>However, it does not close the subliminal channel entirely.
>The generator could append a short message to the bits that
>were specified by the user. So there is still room left for
>the more standard attacks that need less bits.
meant that the user may specify the upper half of n, not just
some of the upper bits. Appending some more bits could then
make the key generation very inefficient, since there would
not be enough bits left to choose one factor arbitrarily.
If all 2k bits of n are fixed, finding two k-bit primes p and q
so that pq matches the given bitstring means factoring the 2k-bit
number. So there might be some law like "finding k-bit primes
p and q so that n=pq matches a given (k+l)-bit string is as hard
as factoring a 2l-bit number". And one does not just want to find
some solution, but one where the l bits can be used as a subliminal
channel that gives information on p or q.
So, vanity keys would probably add some reasonable amount of
security.
>But I haven't thought this through.
Jo
William Unruh
> One way to close a covert channel, it seems, is to use it for real
>information.
It is of course not clear that if we specify the top bits of N that this
does not make recovery of p and q much easier (essentially there are
only N/2 random bits in p and q instead of N)
--
Bill Unruh
un...@physics.ubc.ca
Oliver Hertel
Mina-san, konnichi-wa!
_Gary_ schrieb bzw. zitierte zu _[Fwd: Backdoor in RSA Discovered]_:
> Quite, but a few lessons can still be learnt. One is that we
> cannot trust key generators (hardware or software), without
> examining [...]
Did ever someone check the pgp sources for such, er, mistakes? ;)
Dewa, sayonara!
Oliver
--
Ciao, Oliver
Homepage: http://www.th-darmstadt.de/~st001183/
"Golden Key" Campaign: http://www.privacy.org/ipc/
Robert I. Eachus
> It is of course not clear that if we specify the top bits of N
> that this does not make recovery of p and q much easier
> (essentially there are only N/2 random bits in p and q instead of
> N)
There are two issues here. One is whether a "known plaintext"
attack is possible where forcing the some of the bits of N causes loss
of security. (This is very different from the attack that caused this
discussion where the Trojan Horse gets to choose all the bits.) I
don't think that such an attack would be successful unless it set all
but a few bits of N. Leaving half the bits random seems overkill
here.
But to address the parenthetical remark, how much "randomness" is
there in p and q. (The quotes are because p and q are determined
almost completely by N. In the expected case there is one bit of
randomness--is the larger factor p or q?) If we ignore factoring the
randomness in p and q is limited to the number of bits in the smaller
of the two (plus the one bit above). So if you really want to worry
this issue, set only N/2-1 bits of N. In practice I don't think that
setting even N/2+k bits would be harmful for small k. The best known
method for cracking would still be factoring, and the time required
would not be affected by any of this.
Well...thinking about it a bit more, don't use this technique to
set N close to 2^i or 2^i-2^j. (That is you want to avoid having N
consist of a long run of ones followed by a long run of zeros, with a
few "random" bits at the end.) In other words have at least a few
upper half bits be one, and a few upper half bits be zeros. There are
specialized factoring methods for numbers of this form. At present I
don't think they are significantly faster than general purpose
factoring algorithms, but it is better to be safe than sorry.
Paul Elliott
-----BEGIN PGP SIGNED MESSAGE-----
There is an even more obvious way to hack a program like
PGP to make it vulnerable.
Simply, alter the program to choose its keys from a searchable
subset of the nominal keyspace. The subset could be pseudo
random enough so it would be difficult to detect it by testing,
only by examining the source code.
This could be done with the RSA keys or with the IDEA keys
chosen.
The resulting program would interoerate with regular PGP
any yet be vulnerable. It could only be detected by examining
the source code.
- --
Paul Elliott Telephone: 1-713-781-4543
Paul.E...@hrnowl.lonestar.org Address: 3987 South Gessner #224
Houston Texas 77063
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: cp850
iQCVAgUBMbZrW/BUQYbUhJh5AQGDBgP/YZmcyG6V0i5Ixwd3RUNUOfjO74Iy0PRS
ExuQIn/sokt/8EVDZ2aSuSMnY964oqqE5HKVsXymmPWyAY6Dm98nHkX3ZnYsWuoz
SO/i94E+JljpTT12W+inlJ5TpWJKX/HclGi0nujxDRz8Vo+9UPmY6J5M0EZavx4v
VdZ2oBtIV7w=
=HhTM
-----END PGP SIGNATURE-----
Ed Falk
In article <834031...@hrnowl.lonestar.org>,
Paul Elliott <paul.e...@hrnowl.lonestar.org> wrote:
>
>There is an even more obvious way to hack a program like
>PGP to make it vulnerable.
>
>Simply, alter the program to choose its keys from a searchable
>subset of the nominal keyspace. The subset could be pseudo
>random enough so it would be difficult to detect it by testing,
>only by examining the source code.
Yeah, I was thinking along the same lines. How would this
be detectable without source access?
So what's all the hoopla about someone discovering Yet Another
way to insert a trojan in PGP?
--
-ed falk, sun microsystems -- fa...@sun.com
"What are politicians going to tell people when the
Constitution is gone and we still have a drug problem?"
-- William Simpson, A.C.L.U.
Boudewijn W. Ch. Visser
fa...@peregrine.eng.sun.com (Ed Falk) writes:
>In article <834031...@hrnowl.lonestar.org>,
>Paul Elliott <paul.e...@hrnowl.lonestar.org> wrote:
>>
>>There is an even more obvious way to hack a program like
>>PGP to make it vulnerable.
>>
>>Simply, alter the program to choose its keys from a searchable
>>subset of the nominal keyspace. The subset could be pseudo
>>random enough so it would be difficult to detect it by testing,
>>only by examining the source code.
>Yeah, I was thinking along the same lines. How would this
>be detectable without source access?
>So what's all the hoopla about someone discovering Yet Another
>way to insert a trojan in PGP?
The interesting thing about Mr. Young's trojan is that it is
of no use to anybody but the person who put it there.
Whereas with most trojans,everybody who knows how they work
can profit from them.
Boudewijn
--
+-------------------------------------------------------------------+
|Boudewijn Visser |E-mail:vis...@ph.tn.tudelft.nl |finger for |
|Dep. of Applied Physics,Delft University of Technology |PGP-key |
+-- my own opinions etc --------------------------------------------+
Bodo Moeller
UNQ...@ibm.rhrz.uni-bonn.de (Jo Schueth) writes:
>In their paper, they claim indeed that "the output of C and C'
>are polynomyally indistinguishable [...] to everyone (including
>those who have access to the code of C') except the attacker".
>For the "PAP"-implementation given in the paper, this is not true.
[...]
>It is easy to modify C' to thwart this type of counter-attack:
[...]
>There is still another problem: If RSA with a k-bit modulus N is
>used for E, you have E(r) < N < 2^k. This allows a statistical test,
[...]
This problem can be solved, using an idea by Adam Back.
Our problem is: We have a number E that appears to be a uniformly
chosen random integer with 0 <= E < N (only the attacker or someone
who has watched the execution of program C' knows that it is not
really random). But we need a number F that appears to be a uniformly
chosen random integer with 0 <= F < M, where M is some other known
value. (M should not be smaller than N, at least not much smaller.)
So we choose a random real number x with 0 <= x < 1 (rectangular
distribution). (We will not have to transmit x.) Then we compute
E + x and get a result E' that seems to be a random number
(rectangular distribution) in the interval [0, N). Then we compute
(E' * M) / N and throw away the fraction of the quotient (which is in
the interval [0, M)), obtaining our integer F.
In practice, we'd of course take a fraction x with (say) 64 bits and
use fixed-point arithmetic (that can be simulated by integer
arithmetic) for the following computations: We multiply E by 2^64
(i.e., shift left) and set the 64 lowest bits to random values. Then
we multiply by M, divide by N (throwing away the remainder) and shift
right by 64 bits to obtain F.
When the attacker sees F, he can compute the possible values for E.
If M > N, he has to try at most two different values; if M < N, there
might be more possibilites, so M should not be more than a few bits
smaller than N.
Gary Howland
Paul Elliott wrote:
> There is an even more obvious way to hack a program like
> PGP to make it vulnerable.
>
> Simply, alter the program to choose its keys from a searchable
> subset of the nominal keyspace. The subset could be pseudo
> random enough so it would be difficult to detect it by testing,
> only by examining the source code.
By using this method you allow everyone (who has reversed engineered
the key generator) to obtain key information. Using the other
method, only the bad guy can obtain the private keys.
Michael Emery
In article <slrn4qt1pj....@dream.season.com>, Reality is a
point of view <gjoh...@dream.season.com> writes
> +---- gr...@netcom.com wrote (Wed, 29 May 1996 13:48:55 GMT):
> | This is why verifying the source (and by implication, verifying the
> | compiler and even the machine instructions regressively) is crucial to
> | bag these kinds of attacks.
> +----
>
that is to have database of digital signatures on at least one machine
that [ probably ] has not been compromised. It would not need to be very
big but it would make iit much more difficult to modofy a programme
without it being noticed.
--
Michael Emery