Cryptography-Digest Digest #785, Volume #9 Sun, 27 Jun 99 02:13:04 EDT
Contents:
Re: A few questions on RSA (Gilad Maayan)
Re: determining number of attempts required (S.T.L.)
Re: Moores Law (a bit off topic) (david avery)
Re: A few questions on RSA (S.T.L.)
Re: DES-NULL attack (wtshaw)
Re: A few questions on RSA (David A Molnar)
Re: determining number of attempts required (JPeschel)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Gilad Maayan)
Subject: Re: A few questions on RSA
Date: Sun, 27 Jun 1999 03:54:26 GMT
Take the following encryption scenario:
A 20 bit cyphertext is encrypted into a 20 bit cyphertext using a 1024
bit RTS pubic key. The public exponent is only about 100 bits long;
the secret exponent would be around 900 (if I'm not mistaken). Anyhow,
we're talking about a drastically small public key, and a
correspondingly large secret key.
I'm assuming, in the above scenario, that all of the following are
true. Please note that I'm making a somewhat unconventional use of RTS
- I know moduluses are usually kept in the public domain, etc.
1. An attacker knowing neither the modulus nor the public key, but
knowing the exact length of the plaintext, would not be able to
extrapolate the key from the cyphertext.
2. Let's assume the attacker knows the plaintext but not the modulus
or the public key. The key space is indeed small in this case - only
2^20 - but this only means that each 20-bit combination would have an
enormous amount of 'possible' 512/1024 keys (keys that, when used on
the plaintext, would encrypt it as the known cyphertext). Therefore,
you could test the entire keyspace (only about 1.05 million keys) to
find a key that works, but you would have no way in hell of knowing
which key was actually used.
3. Let's assume the attacker knows the plaintext, the cyphertext, the
modulus, and the secret key (not the public key). For the reasons
stated above, even though the effective key space is only 2^20, he
would have to actually break 1024-bit RTS to know the key that was
used in encryption - simply testing each one of the million-odd
possible combinations would not yield the key.
Furthermore, in our specific scenario, it would make no difference to
an attacker that the public exponent was unusually small - 1024 RTS
would be just as hard to break.
I'd like to hear your comments on this.
Also, I have another question, which appeared in the original message
but wasn't answered to my satistfaction:
Let's say you encrypt a message with triple DES, using two keys
extrapolated from a key-seed by a function. You send the cyphered
message together with the key-seed, without encrypting the key-seed in
any way. If the functions are unknown to an attacker (forget the
key-management issues), would it be able to extrapolate them from the
key-seed and cyphertext?
Many thanks,
Gilad Maayan
------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: determining number of attempts required
Date: 27 Jun 1999 04:42:01 GMT
<<The password picked (by me, if you must know) was designed specifically
to resist attacks :)>>
I see several scenarios, increasingly interesting. I'd like to know which (if
any!) are the case, actually.
1) You've encoded something important and have forgotten the exact key.
However, certain details you stated about how fast you can try keys makes me
think that the files are on some other computer, which you can't access.
2) You've given someone else guidelines to create a password (very, very
unusual guidelines), and are now trying to crack it. Unlikely.
3) You picked a password to encode information, but have forgotten its exact
contents AND are no longer allowed actual access to the encrypted data. This is
the most interesting one.
I'm getting really curious as to what you're trying to crack open! :-D
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Great SRian
Conspiracy, the Triple-Sigma Club, and the Union of Quantum Mechanics
Avid watcher of "World's Most Terrifying Causality Violations", "World's
Scariest Warp Accidents", and "When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #2: Thou Shalt Conserve Mass/Energy In Closed Systems.
------------------------------
From: [EMAIL PROTECTED] (david avery)
Subject: Re: Moores Law (a bit off topic)
Date: 27 Jun 1999 04:47:02 GMT
In message <7l3lm6$95g$[EMAIL PROTECTED]> - [EMAIL PROTECTED] writes:
:>
:>In article <[EMAIL PROTECTED]>,
:> Horst Ossifrage <[EMAIL PROTECTED]> wrote:
:>> Gorden Moore, former Chairman of the Board of Intel Corporation
:>> once said that the trend was that microprocessor performance
:>> doubled every 18 months. He did not say it is a law. There is not much
:>> more than that to research for you. You can just find the date
:>> he said it, and where he was quoted. It was an observation of his,
:>> not a calculation based on fundamental causes. The causes of this
:>> doubling of performance has been discussed in the IEEE Journal of
:>> Solid State Circuits and in the Digest of Technical Papers of
:>> the "International Solid State Circuits Conference" (ISSCC).
:>> IEEE stand for the Institute of Electrical and Electronics
:>> Engineers. See www.ieee.org
:>
:>Thanks for the summation. That was quick!
:>
actually I believe Moore said the number of transisters you could put
on a chip doubled every 18 mo. The performance increase is because of
the density and transister count increase.
Dave Avery
[EMAIL PROTECTED]
United Airlines Simulator Support
------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: A few questions on RSA
Date: 27 Jun 1999 04:26:54 GMT
<<A 20 bit cyphertext is encrypted into a 20 bit cyphertext using a 1024
bit RTS pubic key. The public exponent is only about 100 bits long;
the secret exponent would be around 900 (if I'm not mistaken). Anyhow,
we're talking about a drastically small public key, and a
correspondingly large secret key.>>
Um, okay. From what I know, the public exponent can be extraordinarily small,
just 30 or so bits, without affecting the security of the encryption. However,
I see a few problems. What is RTS? Why do you say you're encrypting a 20 bit
cyphertext (I think you mean plaintext first). Please make sure you spell
"public" right - a single letter dropped, like you did, and... *chuckle*. And
the output of an encryption using RSA is usually the length of the public key
(1024 bits in your example), from what I know. It does *not* preserve the size
of the message.
<<I'm assuming, in the above scenario, that all of the following are
true. Please note that I'm making a somewhat unconventional use of RTS>>
What is RTS?
<<I know moduluses are usually kept in the public domain, etc.>>
Okay.
<<1. An attacker knowing neither the modulus nor the public key, but
knowing the exact length of the plaintext, would not be able to
extrapolate the key from the cyphertext. >>
If the plaintext is 20 bits and the attacker knows that, and you're not using
padding, you are screwed. My calculator can perform a 2^20 attack in reasonable
time, I believe. Why you insist on 20 bits, I don't know. But we're assuming
#1, so okay. Just remember that this scenario is hard to get in real life.
<<2. Let's assume the attacker knows the plaintext but not the modulus
or the public key. The key space is indeed small in this case - only
2^20 - but this only means that each 20-bit combination would have an
enormous amount of 'possible' 512/1024 keys (keys that, when used on
the plaintext, would encrypt it as the known cyphertext). Therefore,
you could test the entire keyspace (only about 1.05 million keys) to
find a key that works, but you would have no way in hell of knowing
which key was actually used.>>
This is odd. I don't believe that #2 is possible at all, but it is very unclear
what you want...
<<3. Let's assume the attacker knows the plaintext, the cyphertext, the
modulus, and the secret key (not the public key). For the reasons
stated above, even though the effective key space is only 2^20, he
would have to actually break 1024-bit RTS to know the key that was
used in encryption - simply testing each one of the million-odd
possible combinations would not yield the key.>>
If the secret key is public and the public key is secret, why not... never
mind. What is RTS? And why does a brute-force attack not work? This is highly
confusing.
<<Furthermore, in our specific scenario, it would make no difference to
an attacker that the public exponent was unusually small - 1024 RTS
would be just as hard to break. >>
What is RTS?
<<but wasn't answered to my satistfaction:>>
Perhaps you could explain what was unsatisfactory? I'd like to help you, but
your scenario (I'm assuming that you are trying to solve a real problem that
you have, because this scenario is so specifically odd) is very strange and not
explained well.
<<would it be able to extrapolate them from the
key-seed and cyphertext?>>
The cyphertext is UNknown? Eh? And before, I thought you were concerned with
the Adversary discovering your key-seed changing function...
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Great SRian
Conspiracy, the Triple-Sigma Club, and the Union of Quantum Mechanics
Avid watcher of "World's Most Terrifying Causality Violations", "World's
Scariest Warp Accidents", and "When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #2: Thou Shalt Conserve Mass/Energy In Closed Systems.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: DES-NULL attack
Date: Sat, 26 Jun 1999 23:54:06 -0600
In article <7l2ku4$5c9$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Thomas Pornin) wrote:
>
> Therefore:
> 56-bit -> 125000$
> 64-bit -> 32000000$
> 80-bit -> 2097152000000$
>
You seem not to understand the difference between design-setup and
production. John said that the chip needed a little more work to be as
efficient as it could be, so there would be some addition work of the
first type. Beyond that, once you have the design, the individual chip
cost comes down in a big hurry with increased quantity.
--
It's always possible that a politician is acting out of principles.
--Michael Kinsley of Slate.com
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: A few questions on RSA
Date: 27 Jun 1999 05:24:57 GMT
Gilad Maayan <[EMAIL PROTECTED]> wrote:
> Take the following encryption scenario:
> A 20 bit cyphertext is encrypted into a 20 bit cyphertext using a 1024
> bit RTS pubic key. The public exponent is only about 100 bits long;
> the secret exponent would be around 900 (if I'm not mistaken). Anyhow,
> we're talking about a drastically small public key, and a
> correspondingly large secret key.
OK, you are trading fast encryptions for slow signing and
decryption. So far so good. There are attacks for small public
keys, but there small = "e = 3".
I'm going to assume that RTS is another name for RSA based on
earlier posts.i
> 1. An attacker knowing neither the modulus nor the public key, but
> knowing the exact length of the plaintext, would not be able to
> extrapolate the key from the cyphertext.
So he has
M = plaintext Message
length of M
C = M^e mod n (e, n unknown)
and needs d.
I think that obtaining d is still difficult even with knowledge
of e and n. This seems to imply that you are correct and d is
hard to obtain in this case.
STL brings up the question of guessing the plaintext and then
comparing it to the ciphertext. As he points out, in the normal
RSA scenario where e is known, this only takes 2^20 encryptions.
In this case, the adversary doesn't know e, so this guessing
doesn't work -- a guessed plaintext can't be encrypted and
compared with the ciphertext.
Oh, I'm sorry, I just realised that you meant "public key"
when you wrote "key", for exactly that reason. Whoops.
I don't see any way to obtain e given a _single_ C .
On the other hand, given many C perhaps a way is possible.
(I need to think about it). It will probably depend on
whether you use padding or not.
Which brings up another point - is 20 < 1024 enough of a
difference to solve the DL problem over the integers
and be correct in some fraction of the cases ? Well,
since you will be computing a 20 bit number
raised to the power of a 100 bit number, it seems
that you'd generally get a 2000 bit number so the
answer is NO. (what about a 2048 bit modulus )
> 2. Let's assume the attacker knows the plaintext but not the modulus
> or the public key. The key space is indeed small in this case - only
> 2^20 - but this only means that each 20-bit combination would have an
> enormous amount of 'possible' 512/1024 keys (keys that, when used on
> the plaintext, would encrypt it as the known cyphertext). Therefore,
> you could test the entire keyspace (only about 1.05 million keys) to
> find a key that works, but you would have no way in hell of knowing
> which key was actually used.
i
I like this way of thinking about it, since it recognizes
each e as defining a different random permutation.
I don't see any easy way to get e off the top of my head.
> 3. Let's assume the attacker knows the plaintext, the cyphertext, the
> modulus, and the secret key (not the public key). For the reasons
>From the secret key, you can compute the public key in poly time
by finding its inverse mod n . Sorry.
> stated above, even though the effective key space is only 2^20, he
> would have to actually break 1024-bit RTS to know the key that was
> used in encryption - simply testing each one of the million-odd
> possible combinations would not yield the key.
This would work, except that e and d are defined to be
inverses of each other. Inverses are reasonable to compute. :-\
> Furthermore, in our specific scenario, it would make no difference to
> an attacker that the public exponent was unusually small - 1024 RTS
> would be just as hard to break.
> I'd like to hear your comments on this.
> Also, I have another question, which appeared in the original message
> but wasn't answered to my satistfaction:
> Let's say you encrypt a message with triple DES, using two keys
> extrapolated from a key-seed by a function. You send the cyphered
> message together with the key-seed, without encrypting the key-seed in
> any way. If the functions are unknown to an attacker (forget the
> key-management issues), would it be able to extrapolate them from the
> key-seed and cyphertext?
You're thinking that because the output -- the DES keys -- isn't
accessible to a cryptanalyst it will be harder to figure out
what the functions are ?
I'm trying to construct a pathological example in which the functions
are linear congruential generators. Given direct access to the
output of such generators, one can derive values for a
generator which "coincides" with the generator in question --
in the sense that they produce the same outputs. So if we
had direct access to your DES keys, we could pretty easily
get the LCGs , even if you weren't giving away the seed.
As it is, you will now need to look at what the intervening
DES algorithm does when given a sequence produced by an LCG.
My suspicion (and it's only a suspicion!) is that you
will be able to eventually recover the functions if they
are LCGs, but that the analysis and process will be
a royal pain.
This kind of analysis has already been done for the
Digital Signature Standard -- which fuels my suspicion
that it is the case here. It's in Daniele Micciancio's
paper on "Pseudo-Random Number Generation : The DSS
Case" at theory.lcs.mit.edu/~miccianc/papers.html
Anyway, this pathological example makes me think that
it may be possible to show that *any* attack on
this system automatically implies an ability to
predict the functions. So if the functions are
perfectly pseudo-random, then the scheme is
secure.
I'm not quite sure about your keyseed in such a
setting, though. Maybe we could treat the
functions as random oracles and let the keyseed
be the index i?
The problem in that case is that if the functions
really are that unpredictable, why not just
use them _directly_ to encrypt, instead of
going through 3DES ? I have to look up
the reference, but I think it's Dwork and Naor
that have a system which uses a pair of
pseudo-random functions to create a
"provably secure" cryptosystem.
The next step at this point would
probably be to pull out Applied Crypto
and start working through DES
encryptions, but I will leave
that for later.
Thanks,
-David Molnar
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: determining number of attempts required
Date: 27 Jun 1999 05:56:49 GMT
> [EMAIL PROTECTED] (Keith A Monahan)writes, and I'm paraphrasing a little
here:
>I'm trying to crack a Blowfish (256-bit) password.
>It consists of lower case letters, the symbol set consisting of
>8 choices(I know the choices), and one space.
>
>This puts my total character set to 35. Not too, too bad in comparison to
>255 possibilities like normal ASCII.
>
>There are no repetitous characters in the password except one case.
>One of two possible characters is repeated one time. Those characters are
>known.
>
>The password is between 8 and 14 characters in length. If length
>drastically affects the answer, I believe it to be close to 12 characters.
>
>I have to write a program which tries all those possibilities, so I also,
etc...
>
>The bad news is I can only try about 1500-2000 attempts per hour because
>of the limitations of my input device. I cannot attack the cyphertext
>directly, as I don't believe there are any attacks better than bruteforce.
>Algorithm is 256-bit Blowfish. Some plaintext is known and my attempts/sec
>could be increased drastically if there was already a custom Blowfish
>brute-force attacker(none that I know of).
>
Keith, as far as I know there aren't any Blowfish crackers on the net, with one
exception. Markus Hahn wrote a program to recover Blowfish 97 passwords.
It's to demonstrate the danger of using weak passwords. (On the other
hand, if you find or write a fast Blowfish cracker, send it to me and I'll add
it to
my collection)
If you're going to try a dictionary attack you're going to have to do a
helluva lot better than 2,000 attempts per hour. My Russian friend Pavel
Semjanov has some code called PCL that may help you.
What program created encrypted the file? If you have access to that program
there may be a more efficient way of breaking the system.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
