Cryptography-Digest Digest #233, Volume #10 Tue, 14 Sep 99 15:13:03 EDT
Contents:
Re: Ritter's paper (Medical Electronics Lab)
Re: pseudo random number in a embedded software (Medical Electronics Lab)
Re: 40-bit ssl (John Pliam)
Re: Mathematical models and encryption (Medical Electronics Lab)
Re: Stream cipher from a hash function (Doug Stell)
Re: RC4 or IBAA or ISAAC to generate large random numbers (fungus)
Re: Neal Stephenson's Cryptonomicon: Crypto Cop-Out (Tom Knight)
Re: Sources of randomness (Scott Nelson)
Re: RC4-40 Cracking ("Richard Parker")
Re: Can you believe this?? (John)
Re: RSA Algorithm (Peter Pearson)
Re: primes in dh (David P Jablon)
Re: Performance benchmarks (Medical Electronics Lab)
Re: RSA Algorithm (Doug Stell)
----------------------------------------------------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Ritter's paper
Date: Tue, 14 Sep 1999 12:44:59 -0500
Terry Ritter wrote:
> There is a copy of the article .PDF on my pages. It is first in the
> list in the Technical Articles section on my top page. The exact link
> is:
>
> http://www.io.com/~ritter/ARTS/R8INTW1.PDF
Thanks!
Patience, persistence, truth,
Dr. mike
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: pseudo random number in a embedded software
Date: Tue, 14 Sep 1999 12:31:36 -0500
jerome wrote:
>
> i'm trying to do a pseudo random number generator in a embedded
> software. the only external event is the network (link point to
> point and/or broadcast such as ethernet).
>
> any hints or pointers explaining how to do that ? i know rfc1750
> and knuth(Vol2).
Check out Yarrow on Bruce's site:
http://www.counterpane.com
Patience, persistence, truth,
Dr. mike
------------------------------
From: John Pliam <[EMAIL PROTECTED]>
Subject: Re: 40-bit ssl
Date: Tue, 14 Sep 1999 16:09:00 +0000
Fiji wrote:
> I know that it is weak but the questions is what is the
> fastest that it has been cracked? Searching on the web I find
> instances of it being broken in about a week but that was back
> in 95. What is the fastest that it could be brute forced with
> todays computing power...i.e. linux clusters, etc.
I believe that the only conservative yet reasonable way to answer
such a question is to use the most recent record-breaking brute
force performance. To my knowledge that number is still the
245 billion keys/sec of the DES Challenge III:
http://www.eff.org/descracker/
At that rate, against 40 bits, you get:
worst case: 5 sec
avg. case: 2.5 sec
Now, is dedicated hardware and a global effort a realistic
threat model? Probably not for a few credit card numbers.
The point is IMHO, that 40-bit encryption should no longer be
considered something which forces your adversary to conduct
an attack off-line. Rather, it is best to consider 40-bit SSL
vulnerable to *real-time* attacks by *amateurs*. Forget
about governments...
John
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Mathematical models and encryption
Date: Tue, 14 Sep 1999 12:55:06 -0500
Tom Pedersen wrote:
>
> How would you characterize a mathematical model in the field of cryoptology?
Define what you mean by "mathematical model". I usually think it
means a specific set of equations in a specific order connected
by conditionals.
> Can you in fact speak of models and cryptology at the same time?
Using the above definition, yes.
> For instance is RSA-encryption a model for sending a message from a
> transmitter to a reciever or is it only a method/algorithm?
If the message is a key then it's certainly an algorithm. The
algorithm is also a model isn't it?
> If there _are_ models - then where is the line between a model and a simple
> method?
Depends on how you want to think about things. Models are usually
used to compare real world things to imagination. If the model
fails it's much cheaper than if a bridge fails. You can model your
security system, and usually crypto is a subsection of that, to see
if there are any holes in your real world application. The "model"
of the crypto is usually perfect, it's going to be run on a computer
in any case. The model of the security won't be perfect, you can't
second guess what social engineering will accomplish with a brand
new employee.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: Stream cipher from a hash function
Date: Tue, 14 Sep 1999 17:51:13 GMT
On Fri, 10 Sep 1999 19:18:10 -0400, [EMAIL PROTECTED] wrote:
>Ok, lets assume that crypto is 100% export restricted, and only lies
>within the US (heh, a BIG assumption).
If export is your concern, building an encryption algorithm out of a
hash function would render it export controlled, since the intent is
to hide the data content.
> Hash functions, on the other
>hand, are not export restricted. Is it possible to turn a hash function
>into a stream cipher?
Sure, but they are rather inefficient.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: RC4 or IBAA or ISAAC to generate large random numbers
Date: Tue, 14 Sep 1999 18:10:33 +0200
Gaston Gloesener wrote:
>
> The named random number generators (RC4, IBAA, ISAAC are beased on an
> array of 32-bit (m) values and each run returns another array of the
> same size than the first giving a set of random numbers (r).
>
Huh?
RC4 certainly isn't 32-bit, and I don't think ISAAC is either.
> What is the correct way to generate larger random numbers (>64 bits):
>
Using 8-bit RC4, generate eight bytes and combine them into
a 64 bit (or larger) number.
> Two Methods can be done:
>
> 1. Handle large integers inside the algorithm, for example through a
> C++ class of huge binaries.
Doesn't make sense.
> 2. Compute a set of results (r-array) and use consecutive 32-bit values
> to fill-up the resulting random number. Thus the first result of a 128
> bit random-number will be (r[0]<<96)|(r[1]<<64)|(r[2]<<32)|r[3],
> combining the first 4 32-values to one 128-bit value. This would be the
> way I would suggest,
Except that the outputs are only 8 bits, this is the way to
do it.
> but is the result really satisfying all criteria
> of random numbers, especially the gussian-distribution ?
RC4 has a slight bias. The probability of two consecutive
outputs being equal isn't 1/256, it's slightly less. This
isn't a weakness from a cryptographic point of view but
in a random number generator it might not be acceptable.
You don't say what your application is. If you want random
numbers which pass statistical tests for randomness then
you should be using something designed for this purpose,
not a cryptographic algorithm.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Tom Knight <[EMAIL PROTECTED]>
Crossposted-To: rec.arts.sf.written,alt.cyberpunk
Subject: Re: Neal Stephenson's Cryptonomicon: Crypto Cop-Out
Date: Tue, 14 Sep 1999 18:24:16 +0100
Ian wrote:
> Matt Ruff / Lisa Gold <[EMAIL PROTECTED]> wrote:
>
> >I think you are making a mistake in assuming that Stephenson necessarily
> >agrees with the beliefs and arguments of his protagonists. In fact, he's
> >stated publicly that it's an artist's job *not* to take political
> >stands, because they interfere with the craft of telling a good story.
>
> Yet he IS an advocate of various "crypto-anarchy" sorts of idea, as you can
> read in bunches of his stuff. The general thrust of his books DOES seem to
> be the sort of future he advocates.
Yes, Stephenson is an advocate of that kind of thing, and yes, that kind of
thing does turn up a lot in his books. I'd still say that he never seems to be
trying to influence opinions. None of the characters in his books can be seen
as heroic mouthpieces.
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Sources of randomness
Reply-To: [EMAIL PROTECTED]
Date: Tue, 14 Sep 1999 16:50:56 GMT
On 14 Sep 1999 09:52:52 +0100, Paul Crowley
<[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] writes:
>> We wouldn't want to filter out the non-randomness, so
>> much as condense down the randomness. A good method
>> is to XOR the low entropy source bit stream into the
>> feedback of a large linear feedback shift register
>> (with taps corresponding to a primitive polynomial,
>> as usual). The nice fact about the technique is that
>> as long as the source stream is independent of the
>> register state, the register never loses entropy.
>
>Even better would be to PUSH all of the random data into Panama, which
>keeps a 1kbyte-wide shift register as part of its state, as well as a
>big non-linear mixer. Then you can PULL all the words you like out
>of it. See http://www.esat.kuleuven.ac.be/~rijmen/daemen.html
The Panama link at that site was broken for me.
As far as the results go, it doesn't make a whit of difference
whether randomness is distilled by excluding the non-random bits,
or by hashing the low order bits, or the generally preferred method
of "hash everything you can get." CRC, SHA, MD5, Panama - they all
produce no more entropy than is fed into them, and if fed enough,
they all produce their set maximum amount and discard the overage.
But CRC, a.k.a Linear Feedback Shift Register, is usually much
smaller and faster than a cryptographically secure hash. If
the object is to distill random bits from a biased source,
it seems a better choice to me.
Even if you wanted to protect the source bits, if
for instance you were going to use them as a session key
which might be compromised, then it's still better to
collect them with a LFSR and hash them only once, rather
than hashing multiple times during the collection.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: RC4-40 Cracking
Date: Tue, 14 Sep 1999 17:34:45 GMT
"Dafydd Richards" <[EMAIL PROTECTED]> wrote:
> Please could somebody post/email rough estimates for the following please
> :-
>
> 1) How much time would a machine on a $30,000 budget take to crack RC4-40.
>
> 2) How much would it cost to construct a machine to crack RC4-40 in say half
> an hour.
A group of cryptographers addressed that issue a few years ago.
Consider taking a look at their paper:
M. Blaze, W. Diffie, R. Rivest, B. Schneier, T. Shimomura, E.
Thompson, and M. Weiner. Minimal Key Lengths for Symmetric Ciphers
to Provide Adequate Commercial Security , January 1996
<http://www.counterpane.com/keylength.html>
Here is a quote from a relevant portion of the paper:
"The recent successful brute-force attack by two French graduate
students on Netscape's 40- bit RC4 algorithm demonstrates the
dangers of such short keys. These students at the Ecole
Polytechnique in Paris used `idle time' on the school's computers,
incurring no cost to themselves or their school. Even with these
limited resources, they were able to recover the 40-bit key in a few
days.
There is no need to have the resources of an institution of
higher education at hand, however. Anyone with a modicum of computer
expertise and a few hundred dollars would be able to attack 40-bit
encryption much faster. An FPGA chip - costing approximately $400
mounted on a card - would on average recover a 40-bit key in five
hours. Assuming the FPGA lasts three years and is used continuously
to find keys, the average cost per key is eight cents.
A more determined commercial predator, prepared to spend $10,000
for a set-up with 25 ORCA chips, can find 40-bit keys in an average
of 12 minutes, at the same average eight cent cost. Spending more
money to buy more chips reduces the time accordingly: $300,000
results in a solution in an average of 24 seconds; $10,000,000
results in an average solution in 0.7 seconds."
I should note, however, that I recall that at the time the paper was
released some commented that they felt that these estimates overly
estimated the rate at which an programmable logic chips could test RC4
keys.
-Richard
------------------------------
From: John <[EMAIL PROTECTED]>
Subject: Re: Can you believe this??
Date: Tue, 14 Sep 1999 11:22:49 -0700
What's the joke? Some people don't subscribe to the "pure"
science of cryptography as much as others. It is very hard
to make money and be into the pure science at the same time.
Not many can do it. The source or publication would be
the easiest method a cryptographer had to crack a system.
What is the obligation? As a scientist, you are supposed
to share information. It is unethical not to. In business,
especially computers/tech...The whole idea is to have
something that nobody can "get there hands on."
http://www.aasp.net/~speechfb
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Peter Pearson <[EMAIL PROTECTED]>
Subject: Re: RSA Algorithm
Date: Tue, 14 Sep 1999 09:34:52 -0700
Gary Partis wrote:
> We have implemented a sub-set of RSA (the EXP bit) in Z80 and even after
> extensive optimisation (and dedicated hardware to handle big numbers), it
> is still slow.... :-(
>
> In the standard algorithm, the MULMOD (C=A * Z MOD P) code is called
> extensively, and this code it's self is highly iterative (128 times for a
> 128bit key) per call, and it is called a few hundred times per encryption
> and decryption.
>
> Does any one know of an algorithm which overcomes this performance issue,
> or if there is a set of 128bit keys/modulus which minimises the need to
> call the MULMOD code from the EXP code?
A 128-bit modulus is not secure, since 128-bit composite
numbers can be easily factored.
Using a public exponent of 3, 17,or 65537 reduces the number
of modular multiplies needed to perform an encryption. Decryption
will always require a number of multiplies on the order of
1.5 times the bit length of the modulus.
What sorts of speeds are you expecting, and what speeds are you
seeing? It's a fact of life that RSA is slow; that's why it's
generally used to exchange keys for faster ciphers. Maybe it's
your expectations that are out of line.
- Peter
------------------------------
From: [EMAIL PROTECTED] (David P Jablon)
Subject: Re: primes in dh
Date: Tue, 14 Sep 1999 16:38:55 GMT
For the DH modulus, you can use any *randomly chosen* large prime
p where q = (p-1)/2 is also prime. For the "generator",
any small number > 1 will work just fine.
The process for finding a random or pseudo-random generator as
described below may be useful for authenticated forms of DH,
but a fixed generator, like g=4, is good enough for vanilla DH.
You'll also want to prevent small subgroup confinement.
See <www.IntegritySciences.com/ssc.html> for detail.
======================================================
David P. Jablon
Integrity Sciences, Inc.
[EMAIL PROTECTED]
<http://www.IntegritySciences.com>
In article <[EMAIL PROTECTED]>,
Bob Deblier <[EMAIL PROTECTED]> wrote:
>Tom St Denis wrote:
>
>> I decided instead of using DH for just key gen I will use it for pk instead.
>> What happens is you make a key pair (x, g^x mod p) and give out the second.
>> Whenever I want to talk to someone I take their public key and compute the
>> normal g^xy mod p, since they have my public key ... etc... simple stuff.
>>
>> However to stop any people that are bent on thinking that they can easily be
>> broken, can i get a somewhat large prime (say 1536 or 2048 bits?) please?
>> Just to keep annoying people from saying 'hey 1024 is too small although it
>> will never be broken, and it's probably easier just to break into the
>> computer and steal the key out of memory .... etc"
>
>Here's a (probable) 2048 safe prime. Both this number and (number - 1) / 2 are
>probable primes, which simplifies the finding of a generator.
>
>b478a3fa33b1eac4ac8838ff8118999aacd9ea174143f0a9e06b68004836c63598897ae0e8738764659b3902926258df809a5453b50d57438a3c765b1ea9e64089606376fd6da94a43686d8e3fe574eb5b77d55d1b84a9de2dd96042938036837082f753f42296696a808e5df937a48c3b5ffe5c509752227b14c17f612d9950370337d62dcad7031071a3710b5ed7c59e061eb6540a8b108318f0334a6bd6780da6ebdc4988b658a42d8a57548019811f41af62aa463562c3cdd3db018a91fb956d6663ddea34c427935177611d3eaa883f1665eb036e3423dbfea9bafe81513dde34f3056d6014b081404ca205ba2858434d55b91764a2703e46578f9e254f
>
>In case you don't have the algorithm for finding a generator (hope I remember
>my math correctly)
>
>Assuming you have a P where P = 2Q+1, and both P and Q are prime (like the one
>above)
>
>Step 1: Choose a random G with 1 < G < P-1
>Step 2: If G^2 mod P equals 1 goto Step 1
>Step 3: if G^Q mod P equals 1 goto Step 1
>
>This is a simplification of a more general algorithm:
>
>Assuming you have a prime P and the factorization of (P-1) = N =
>p1^e1*p2^e2*...*pk^ek then:
>
>Step 1: Choose a random G with 1 < G < P-1
>Step 2: For i from 1 to k do the following:
>Step 2.1: Compute b = G^(N/pi) mod P
>Step 2.2: if b = 1 then goto Step 1
>
>For more information, there's the excellent Handbook of Applied Cryptography by
>Alfred J. Menezes.
>
>Good luck
>
>Bob Deblier
>
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Performance benchmarks
Date: Tue, 14 Sep 1999 12:38:43 -0500
Jim Goodman wrote:
>
> Hello,
>
> I was wondering if anyone knew of a collection of performance
> numbers on the web (or in papers) for various companies' public
> key implementations (rather than having to surf each of their web
> pages myself). I'm interested in all forms (IF, DL, and ECC).
> I'd really appreciate it if someone could give me a pointer.
I don't you'll find any thing like that.
I would like to compare various invocations of
my code just to see what the differences are on
a single processor. There are a great many
variables to account for, and different algorithms
can take advantage of some processor abilities,
ram accessability, and so on.
With just ECC, I want to make sure that I compare
things equally. That means I need to find curves
with the same number of points in each of the
different fields I want to test. This is a hard
problem, but I'm closing in on it.
If you start comparing things between different
types of math, life gets more fuzzy. The
"equivelent" level of security isn't well defined.
You still have all the parameter choices to deal
with of processor/ram/etc. and some of the tests
will do better on some processors and worse on
others.
So if you pick a processor configuration, then
perform a bunch of tests with specific code,
you can determine what's good for a specific
application. If you change anything, start over!
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: RSA Algorithm
Date: Tue, 14 Sep 1999 17:46:27 GMT
On Tue, 14 Sep 1999 09:34:52 -0700, Peter Pearson
<[EMAIL PROTECTED]> wrote:
>Gary Partis wrote:
>> We have implemented a sub-set of RSA (the EXP bit) in Z80 and even after
>> extensive optimisation (and dedicated hardware to handle big numbers), it
>> is still slow.... :-(
Does the dedicated hardware perform the mod N reduction efficiently or
does it just assist with the multiplications?
>> In the standard algorithm, the MULMOD (C=A * Z MOD P) code is called
>> extensively, and this code it's self is highly iterative (128 times for a
>> 128bit key) per call, and it is called a few hundred times per encryption
>> and decryption.
As stated by others, 128-bit RSA keys are quite insecure and nearly
useless. The 512-bit challenge was recently cracked and one should
certainly use something larger than this. The absolute minimum today
is probably 768 or 1024 bits. The processing burden will increase by
something on the order of the 4'th power of the length.
>> Does any one know of an algorithm which overcomes this performance issue,
>> or if there is a set of 128bit keys/modulus which minimises the need to
>> call the MULMOD code from the EXP code?
If the hardware does not do the mod N efficiently, there are some
software options that will help substantially. These options are
almost essential for implementation on a small processor.
The private key, but not the public key, computation can take
advantage of the Chinese Remainder Theorem (CRT). This performs two
computations with numbers half the size of the key, resulting in a 4X
performance improvement.
Montgomery Multiplication will eliminate the divisions associated with
the mod N function. Division is replaced by two multiplies and one
right-shift. Since Montgomery Multiplication requires GCD(N, R) = 1
and R to be a power of 2, it must work with an odd modulus, It will
not be usable for the public key calculation with and even N. It will
be usable with the prime moduli of the CRT.
There are a number of other optimizations in the literature that may
also be helpful. Chapter 14 of the HAC discusses them nicely.
>Using a public exponent of 3, 17,or 65537 reduces the number
>of modular multiplies needed to perform an encryption. Decryption
>will always require a number of multiplies on the order of
>1.5 times the length of the modulus.
As the above reply indicates, the number of multliplicatons is on the
order of the size of the exponent, plus the number of ONE-bits in the
exponent. The small public exponents mentioned give you the least
number of ONE-bits. The private exponent is roughly the size of the
modulus and 50% ONEs.
doug
------------------------------
** 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
******************************
