Cryptography-Digest Digest #709, Volume #9 Sat, 12 Jun 99 19:13:04 EDT
Contents:
Re: Slide Attack on Scott19u.zip (SCOTT19U.ZIP_GUY)
Re: RSA example with small numbers (Jim Gillogly)
Re: RSA example with small numbers (Gergo Barany)
Re: RSA msg length... (James Pate Williams, Jr.)
Re: RSA example with small numbers (James Pate Williams, Jr.)
Re: Cracking DES ([EMAIL PROTECTED])
Re: Cracking DES (Boris Kazak)
Re: RSA example with small numbers (James Pate Williams, Jr.)
Re: Slide Attack on Scott19u.zip (David Wagner)
Re: RSA example with small numbers ([EMAIL PROTECTED])
Re: Cracking DES (David Wagner)
Re: Slide Attack on Scott19u.zip ([EMAIL PROTECTED])
How to read postscript files (David Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Slide Attack on Scott19u.zip
Date: Sat, 12 Jun 1999 22:38:17 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim
Redburn) wrote:
>On Sat, 12 Jun 1999 20:33:23 GMT, [EMAIL PROTECTED]
>(SCOTT19U.ZIP_GUY) wrote:
>
>
>> Actually it is rather well documented. It complies and runs on a PC what
>>more to you want?
>>
>
>How do I compile it on my Linux PC - an Intel Pentium using gcc 2.8.1?
>
>The compiler complains that it can't find keys.h or pc.h, neither of
>which are included in the scott19u.zip file.
THe guy in germany was able to comple in visual C with out any problem.
(At least he had no problems with scott16u)
drop pc.h and key.h and change the access() to what every your system use
also change make more room for the arrays rt ft bt as I described in past
posts. This should allow you to compile. Put I don't have your system so
I can't tell exactly what is needed.
>
>-Tim.
>
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: RSA example with small numbers
Date: Sat, 12 Jun 1999 14:28:52 -0700
Gergo Barany wrote:
> I selected two primes, p=23 and q=37 (I could use any primes, but they
> shouldn't be a lot bigger or smaller, I felt). Their product n=851,
> (p-1)(q-1)=792. Then, I had the RSA Algorithm Javascript Page
> [http://www.orst.edu/dept/honors/makmur/] generate my keys, d=317 and
> e=5 ...
>
> I chose the number 10 as my plaintext and encrypted it:
> C=M^e mod n=10^5 mod 851=433
>
> Then I took the cyphertext 433 and decrypted it:
> M=C^d mod n=433^{317} mod 851=499
"bc" says (433^317) % 851 = 10.
Looks to me like you're OK -- check that last step again.
--
Jim Gillogly
Hevensday, 22 Forelithe S.R. 1999, 21:26
12.19.6.4.17, 1 Caban 5 Zotz, Seventh Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Gergo Barany)
Subject: Re: RSA example with small numbers
Date: 12 Jun 1999 21:39:46 GMT
In article <7jue4p$gao$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
>> I chose the number 10 as my plaintext and encrypted it:
>> C=M^e mod n=10^5 mod 851=433
>>
>> Then I took the cyphertext 433 and decrypted it:
>> M=C^d mod n=433^{317} mod 851=499
>
>You did something wrong because
>
>433**317 (mod 851) = 10 in the win98 calc.
Ok, thanks. Apparently, the Win98 calculator works better than my TI-85
when it comes to 835-digit numbers. Thanks also to the other poster for
the link to his FreeLIP package. Looks like I'll have to use my PC for
calculations, then.
Gergo
--
Bureaucrats cut red tape -- lengthwise.
GU d- s:+ a--- C++>$ UL+++ P>++ L+++ E>++ W+ N++ o? K- w--- !O !M !V
PS+ PE+ Y+ PGP+ t* 5+ X- R>+ tv++ b+>+++ DI+ D+ G>++ e* h! !r !y+
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: RSA msg length...
Date: Sat, 12 Jun 1999 21:47:29 GMT
On Sat, 12 Jun 1999 14:43:39 -0400, "Particle" <[EMAIL PROTECTED]>
wrote:
>how big can a msg (block) be?
Think of an example with artificially small parameters:
p = 3 and q = 5, n = p * q = 15 = 1111 (in binary). The largest
message is m = 14 = 1110. This has bit length 4 which is the bit
length of the modulus. Out of curiosity, why is a binary space-
partitioning tree interested in cryptography, usually BSP trees
are prevalent in computer graphics?
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: RSA example with small numbers
Date: Sat, 12 Jun 1999 21:56:31 GMT
On 12 Jun 1999 21:39:46 GMT, [EMAIL PROTECTED] (Gergo Barany)
wrote:
> Thanks also to the other poster for
>the link to his FreeLIP package. Looks like I'll have to use my PC for
>calculations, then.
A correction is in order, Arjen K. Lenstra of the special and general
number field sieve fame (a well-known factoring algorithm) wrote
FreeLIP which is portable to PCs under Microsoft's Visual C/C++ and
Borland's C/C++ 5.0. (Currently, these are the only two C/C++
compilers on this author's PC.)
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cracking DES
Date: Sat, 12 Jun 1999 21:16:33 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>(...)
> Note that algorithmic weaknesses scale linearly. I.e. if you double
the
> number of algorithms you double the amout of work for an adversary
> (Ritter and others have suggested that this may not be true, for this
> topic it is true.)
>
> Key weakness does not scale linearly. If you double the key size
(which
> is the usual technique for 3DES) you do much more than double the
> adversary's workload. "Just running it three times" does not increase
> the security by a factor of three. It increses it by a factor of
2^56.
> So if you buy a super-duper one minute DES cracker, you need 2^56
> minutes to crack 3DES with it.
There is a big difference between combining ciphers in parallel or in
series. If you combine them in series then security grows much faster
than linearly. Resistance against most known attacks grows
exponentially if you add rounds to a cipher. If you combine different
ciphers it is possible that an attack will not work at all. For
example, if you like DES but need a larger key then your are probably
better off combining different algorithms, say DES-IDEA-DES rather then
simply 3DES.
Using different ciphers in parallel, i.e. choosing one cipher for
encrypting some messages and another to encrypt other messages, doesn't
seem to be a good idea as Bryan Olson has exhaustively explained. It is
rather odd though that this is precisely what the government does: I
understand they use many different ciphers. Wouldn't it be better to
use only one? Well, maybe these different ciphers are optimized for
different operational environments or, maybe, in this way it is easier
to keep them secret.
If it were possible to produce a *huge* number of cryptanalytically
unrelated ciphers, then the attacker could not study them all, choose
the weakest and attack it recovering part of the information.
A similar idea is to use a huge number of permutations and choose one
depending on the key. In a previous post I described "heavy DES", a
slowish cipher that encrypts 64 bit blocks with a 140 bit secret key by
executing 10 DES encryptions in series. First define and publish 16K
random DES keys. Observe that you need 14 bits to index one DES key.
Next, take the secret key, divide it into 10 indexes and encrypt the
plaintext by sequentially chaining the 10 indexed DES functions. DES is
not a group, therefore each instance of the 140 bits long key results
in a different permutation.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Cracking DES
Date: Sat, 12 Jun 1999 15:25:52 -0400
Reply-To: [EMAIL PROTECTED]
Terry Ritter wrote:
> (********)
>
> Anybody can handwave that only 5% of the traffic is essentially as
> good as 100%, but that does not make it true. In special cases it may
> be true. For the most part, I doubt it is. To imply that it is true
> is to some extent implying that everyone else (!!!) in the world
> operates in a haze, repeating everything they say 20 times.
=============
Depends who digests the traffic. It is no big secret that if your
adversary is a professional in the field, he knows a lot of the
background information. Then even 0.1% of the traffic might be enough
for such a person not only to fill the gaps in the intended secret
stuff, but sometimes even to ignite his imagination and figure out the
possible uses of this secret stuff which its very creators could not
anticipate. Russian intelligence and industrial espionage worked just
this way - they did not need even 5% of the traffic, a couple of
seemingly innocent words would be enogh to build the remaining bridges.
Obviously, we are speaking here about highly educated professionals.
If, on the other hands, you are dealing with a bureaucrat, who
cannot tell a cone from a sine, logarithm from algorithm and manometer
from potentiometer, then even 20 times repeating may not be enough.
Best wishes BNK
>
> ---
> Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: RSA example with small numbers
Date: Sat, 12 Jun 1999 22:12:59 GMT
On Sat, 12 Jun 1999 21:56:31 GMT, [EMAIL PROTECTED] (James Pate
Williams, Jr.) wrote:
>On 12 Jun 1999 21:39:46 GMT, [EMAIL PROTECTED] (Gergo Barany)
>wrote:
>
>> Thanks also to the other poster for
>>the link to his FreeLIP package. Looks like I'll have to use my PC for
>>calculations, then.
>
>A correction is in order, Arjen K. Lenstra of the special and general
>number field sieve fame (a well-known factoring algorithm) wrote
>FreeLIP which is portable to PCs under Microsoft's Visual C/C++ and
>Borland's C/C++ 5.0. (Currently, these are the only two C/C++
>compilers on this author's PC.)
>
Actually I do have gcc on my machine which is used by Xspin,
but I have not tried compiling FreeLIP using this compiler.
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Slide Attack on Scott19u.zip
Date: 12 Jun 1999 15:20:42 -0700
In article <7jue3a$2ci0$[EMAIL PROTECTED]>,
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
> Just what do you mean bypass the fact the first and last round
> are different. DO you mean your attacking a reduced version
> of Scott19u. I think that reduced version attack was kind of what
> Paul Onions did a long time ago?
I'm not suggesting to attack a reduced version.
I'm referring to the earlier comment that the same S-box entry
will not be used in the first and last round, since in all likelihood
the 19-bit input to the S-box will be different.
This fact was claimed to make slide attacks impossible.
I was suggesting that this fact might not be so bad (for the attacker)
as it seems; that you can still make slide attacks work, even though
different S-box entries are used.
> >
> >The primary equation is C[i] = S{(P[i] + P[i+1]) xor C[i-1]},
>
> Actually in your notation it is C[i]=S{(C[i-1] xor P[i]) + P[i+1]
> where if the first 19 bits of Pass call P[0] then C[-1] is the last
> nineteen bits used in the file. The min file length is 64 bits.
Oops, serves me right for not looking it up. Anyhow my point below it
is still valid (I think), you just have to change the equations slightly.
> THe complete file is rotated 9 bits up so the the top 9 bits of C[0] go to
> bottom of the file. Also there is a first and last round the Paul function
> that is different from the 23 rounds that are represented by the
> equations above. When one gets to the end of file it borrows for the top
> of file rest of C[0] and C[1] so that the most C[m] is such that parts of the
> last P[n] and P[n+1] could be using parts od C[0] and C[1] The Paul function
> named after Paul Onions is very short and you can see the code to see
> how that interacts with things.
Ok, I have to admit you lost me here. Sorry.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA example with small numbers
Date: Sat, 12 Jun 1999 23:14:38 +0059
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Gergo Barany <[EMAIL PROTECTED]> wrote:
> I selected two primes, p=23 and q=37 (I could use any primes, but they
> shouldn't be a lot bigger or smaller, I felt). Their product n=851,
> (p-1)(q-1)=792. Then, I had the RSA Algorithm Javascript Page
> [http://www.orst.edu/dept/honors/makmur/] generate my keys, d=317 and
> e=5 (I would have done that myself, but neither AC nor the Cryptography
> FAQ (question 6.5) gave me enough details on that).
e can be chosen freely so long as e is coprime (relatively prime) to
(p-1)(q-1). AC says that commonly-used values are 3, 17, and 65537.
You must then find d such that d*e mod (p-1)(q-1) = 1. This is done by
a method similar to Euclid's algorithm for finding the greatest common
divisor of two numbers - when doing the computation for RSA, the
numbers in question are e and (p-1)(q-1). In your example
792 = (5 * 158) + 2 (in effect, find 792/5 while keep the remainder)
5 = (2 * 2) + 1
It will sometimes take more than two steps of this sort to get back to
a remainder of 1. (If e and (p-1)(q-1) were not coprime, then we would
never get a remainder of 1, since this procedure gives the greatest
common divisor of the two numbers as the last non-zero remainder.)
Working backwards from this, see that
1 = 5 - (2 * 2)
2 = 792 - (5 * 158)
so now substituting in
1 = 5 - (2 * (792 - (5 * 158)))
= 5 - (2 * 792) + 5 * (2 * 158)
= 5 * (1 + (2 * 158)) - (2 * 792)
= 5 * 317 - (2 * 792)
hence 5 * 317 mod 792 = 1.
[snip]
> I chose the number 10 as my plaintext and encrypted it:
> C=M^e mod n=10^5 mod 851=433
> Then I took the cyphertext 433 and decrypted it:
> M=C^d mod n=433^{317} mod 851=499
> Now, as you can see, my original plaintext is not the same as the result
> of D(E(M)).
It's nothing more serious than an arithmetical slip: your method seems
fine. I don't know how you managed to calculate 433^317 mod 851 using
your calculator, since 433^317 is around 10^836, but I've just tried
it out using dc, and it claims that the remainder is 10 - the same as
your original plaintext.
dc is a calculator which is found on Unix systems as standard. It
stores numbers to arbitrary precision, so it can cope properly with
the huge numbers required here. If you have access to a Unix system,
it may well be worth a look.
Best wishes,
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBN2LbywfhhuwOgxFAEQIaXgCePTIhQs2pHbkQLEImw+fUZscaRgkAoKPA
JHkZIdJeHngRVGyUY0NSRgOH
=ZpjM
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Cracking DES
Date: 12 Jun 1999 15:13:34 -0700
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> For example, what percentage of all books fall into such a category?
> What percentage of all crypto message traffic fall into such a
> category?
I don't know. Let's suppose 0.1% of the messages are books like
Biham and Shamir, just for the sake of argument. (For all I know, the
NSA has entire warehouses full of wonderful books like that one, but
let's assume for the sake of this debate that they're sent relatively
rarely.) I hope that's a small enough proportion to satisfy you.
Let's run with this scenario. The cryptanalyst breaks 5% of the contents
of each message. For 99.9% of the messages, he doesn't get a Biham and
Shamir book, so most days he goes home unhappy. But occasionally that
Biham and Shamir book will go through, and then it's an incredibly huge
secret that got divulged, a secret interesting enough to keep him busy
for years.
The point is, when the cost of compromise is so large, even failure rates
like 5% or 0.1% start to look utterly unacceptable.
By the way, I should mention that the military scenario may actually be
a little unfair to your position, because in military scenarios the cost
of failure can be dramatically large, whereas in many commercial settings
it's not clear that this is the case.
So you might be able to make a more persuasive case in the commercial
setting than in a military setting. What do you think?
> And if 5% of the traffic can expose everything, why is it that anyone
> ever bothers to send the other 95%?
Oh, come on, I think this question is disingenous.
I'm saying that _with a lot of work_ (say, several man-years from a very
good researcher), you can recover most of the other 95% from just the 5%
you managed to read, at least in some important cases.
But when I read a book, I don't want to spend years trying to re-discover
all the author's neat ideas from 5% of his writings. Therefore, to save
time, he spells out all his ideas for me nice and clearly, and I read them.
The author may spend several years formulating all his ideas clearly, but
then the point of good writing is that he goes through this process once,
and the readers don't ever have to repeat that process again.
That's why you bother to send the whole book -- because it makes the
reader's life easier.
> I asked for a citation to the literature where somebody has made such
> a statement, identified their assumptions, explained their reasoning,
> and backed it up with evidence.
And if you don't find anything in the literature to support my position,
will you then conclude that I must be wrong? I think there's a flaw in
this reasoning.
To be honest, I don't think the academic literature has really studied
these types of questions, so I think it's unrealistic to expect any
definitive results in either direction from the literature. (But feel
free to prove me wrong with some examples; I'd be interested to hear of
any citations with evidence one way or another.)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Slide Attack on Scott19u.zip
Date: Sat, 12 Jun 1999 21:59:47 GMT
In article <7juehu$2ci0$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> If they write the dam paper in HTML or ascii I would read it.
> the ghost view is 3megs unexpanded way to large for n my harddrive.
> Is it to much to ask for a HTML or C version of this.
That's ironic considering you boast a cipher that requires 1.18MB
keys... :)
Get GSVIEW and ADOBE, if you want to read real papers you will most
likely need it (note that blowfish is a txt only paper...)
> Maybe yes or maybe not at this this isn't as pompous as your first
boast.
Maybe he is human? He probably shouldn't boast figures unless he can
substantiate them, but I trust him because well he knows more then me.
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: How to read postscript files
Date: 12 Jun 1999 15:35:11 -0700
Go to <http://wheel.compose.cs.cmu.edu:8001/cgi-bin/browse/objweb>.
Type in the URL of the postscript file you want to read in the lower
dialog box. Click the submit button. Wait a long time. Click on
the link to ``step through sequence elements''. Enjoy!
This should let you view any postscript file from a normal web browser,
without needing to install ghostview.
------------------------------
** 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
******************************
