Cryptography-Digest Digest #304, Volume #13 Mon, 11 Dec 00 01:13:00 EST
Contents:
Re: [Question] Generation of random keys (Simon Johnson)
Re: Array shuffling ("Scott Fluhrer")
Re: [Question] Generation of random keys - LONG - algorithms, randomness (David
Schwartz)
Re: Array shuffling ("Scott Fluhrer")
Re: [Question] Generation of random keys - LONG - algorithms, randomness and
unpredictability (Bryan Olson)
Re: [Question] Generation of random keys - LONG - algorithms, randomness (David
Schwartz)
__(FYI) Funding Support at the Hong Kong Science Park (kctang)
Re: What's better CAST in PGP or Blowfish 128bit? (Ray Dillinger)
Re: keysize for equivalent security for symmetric and asymmetric keys (Lee Winter)
----------------------------------------------------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: [Question] Generation of random keys
Date: Sun, 10 Dec 2000 20:57:53 GMT
In article <8vbfut$e31$[EMAIL PROTECTED]>,
Alan Rouse <[EMAIL PROTECTED]> wrote:
> The hard part is knowing how much entropy you have collected.
Perhaps
> you want to create a 160-bit key, so you need 160 bits of entropy.
How
> can you be certain that you have that much? Tough question.
>
> Yes you can be "very conservative" and collect 2x, or 10x, or 100x as
> much entropy-containing data as you think you need. But you still
> don't KNOW how much you have. Perhaps the entire sample is completely
> determined by a relatively small number of controlling factors. This
> is a difficult problem that cannot be solved by software. It requires
> careful study on a case-by-case basis. And even then you won't KNOW.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
The real problem is not wether or not you can collect the maximum
entropy. The problem is wether the cryptanalysis can exploit it if it
isn't. If a coin has a bias of +-1 x 10^-36 and we generate 128-bits
from it, for a key, the security of the system will be unnoticably
degraded.
If your really parinoid, we can create a near perfect entropy
collection, by flipping a load of coins in parrell then XORing the
flips. Any bias in the resultant output will degrade expodentially as
the number of coins increases.
Or, you could just use the radioactive decays of Plutonium to generate
your keys? In which case, you will get perfect entropy collection,
provided you collect bits at high resolution.
Yours,
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Date: Sun, 10 Dec 2000 14:00:44 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Having recently looked at the sci.crypt FAQ, I noticed that the array
> shuffling algorithm requires that you use a modran function.
>
> for( n = ARRLTH-1; n > 0 ; n-- ) swap( &arr[modran( n+1 )], &arr[n] );
>
> Considering that, with an arbitrary parameter, each call to modran takes
> a nondeterministic amount of time to complete, and further is generally
> not the most efficient use of random bits, I took it upon myself to
> write my own array shuffler, which uses random bits in the most
> efficient way possible.
Actually, if you're looking to use the random bits as efficiently as
possible, it's actually rather simple: use your random bit stream to select
an integer between 0 and N!-1, and use that integer to select the
permutation. Using a maximally efficient modran function, this takes an
expected log2(N!)+O(1) random bits. Your algorithm uses strictly more than
this algorithm for N>2.
>
> I submit it here for your review and comment on. Although this
> algorithm also takes a nondeterministic amount of time to complete, it
> should use N*log(N) bits on average, and the nondeterministic part is
> where you can see it, in the do/while loop, not hidden in random number
> function. This shuffler should not be biased if randbit() is not
> biased.
Comments:
- This algorithm looks like a randomized quicksort (minus the pivot
element), while the classical algorithm can be viewed as a randomized
selection sort (with optimizations).
- This does appear to be unbiased, in the sense that it produces all
permutations with probability 1/N!, if all randbit() outputs are unbiased
and independent. I think I see an outline of a proof -- have you proved it
yourself?
- Are you sure that your algorithm uses fewer expected random bits than the
classical algorithm? At N=3, the classical algorithm uses an expected 3 2/3
random bits, while your algorithm uses an expected 5 bits. For N=4, the
expected number of random bits are 5 2/3 for classical, and 8 2/7 for yours.
In addition, as I referenced earlier, a maximally efficient modran function
(which can be efficiently computed) can make an unbiased selection of N
items using an expected log2(N)+O(1) random bits -- have you looked at the
classical algorithm using that?
- Have you analyzed the expected number of random bits your algorithm uses?
You may want to look at a formal analysis of quicksort (e.g. in Knuth) --
the lack of a pivot element will change the analysis somewhat, but I'd
expect it to remain similar.
- One distinction is that your algorithm uses a destination buffer, while
the classical algorithm is in-place. For some applications, this may be
importent.
- Have you heard of the obscure technique known as "indenting"? Makes your
code much easier to read.
>
> int int_shuffle_array( unsigned int * arr, unsigned int * buf, int len )
> {
> int lt, rt, bits = 0;
> if( len == 1 ) {
> buf[0] = arr[0];
> return 0;
> }
> if( len == 2 ) {
> if( randbit() ) {
> buf[1] = arr[0];
> buf[0] = arr[1];
> } else {
> buf[0] = arr[0];
> buf[1] = arr[1];
> }
> return 1;
> }
> do { int i;
> unsigned int * bufl = buf, * bufr = buf + len;
> for( i = 0; bufl != bufr; ++i )
> if( randbit() )
> *bufl++ = arr[i];
> else
> *--bufr = arr[i];
> lt = bufl - buf;
> rt = len - lt;
> bits += len;
> } while( lt==0 || rt==0 );
> if( lt>0 ) bits += int_shuffle_array( buf , arr , lt );
> if( rt>0 ) bits += int_shuffle_array( buf+lt, arr+lt, rt );
BTW: you don't need the "if (lt>0)" test in the above two lines
> return bits;
> }
>
> Curiously, using (rand() & 1) as randbit() averages much above than
> N*log(N) for any N greater than 2.
Your rand() may be poor in the low bits. It's a common failing with rand()
implementations.
--
poncho
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: [Question] Generation of random keys - LONG - algorithms, randomness
Date: Sun, 10 Dec 2000 14:25:10 -0800
"John A. Malley" wrote:
> 1) An algorithm cannot produce randomness.
I'll produce a simple counterexample. First, I'll take a fairly
standard definition of randomness: a stream of numbers in some base is
random if all numbers are equally probable and each output is
uncorrelated with respect to any previous numbers.
Now I'll start with something that's not random, an input stream that
is unpredictable but both highly correlated and non-uniform. Say it's in
base 10, but only one in ten thousand digits is a '3' and there's a 95%
change that each digit is identical to the previous digit. Suppose it's
produced by a process such as radioactive decay.
Now I construct an algorithm where we take 50,000 digits from the input
stream, do a SHA1 hash on them, and output the results of the SHA1 as a
stream. Note that this means we produce 160 bits of output for every
50,000 digits of input.
The output of this process is, by the fairly standard definition above,
random. But the input is not. If the algorithm didn't produce the
randomness, where did it come from?
DS
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Date: Sun, 10 Dec 2000 14:43:56 -0800
Paul Crowley <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Benjamin Goldberg wrote:
> >
> > Having recently looked at the sci.crypt FAQ, I noticed that the array
> > shuffling algorithm requires that you use a modran function.
> >
> > for( n = ARRLTH-1; n > 0 ; n-- ) swap( &arr[modran( n+1 )], &arr[n] );
> >
> > Considering that, with an arbitrary parameter, each call to modran takes
> > a nondeterministic amount of time to complete, and further is generally
> > not the most efficient use of random bits, I took it upon myself to
> > write my own array shuffler, which uses random bits in the most
> > efficient way possible.
>
> Pseudocode would be better than C for explaining this, but it looks like
> you're doing a quicksort and replacing the comparator with a random bit
> lookup. Schneier recommends this method in the first edition of Applied
> Cryptography. However, it's biased. In fact, *any* shuffling method
> which uses a bounded number of bits has to be biased.
However, it is technically unbounded -- if all of the elements end up going
to one partition, the algorithm tries again. For example, if you replace
randbit() with something that always returns 0 (or always return 1), the
algorithm will never terminate[1].
> The bound on the number of bits that your generator uses is n(n-1)/2 -
> ie worst case, every element is "compared" to every other. However,
> usually it'll use on the order of lg(n) bits. The bias is in favour of
> the shuffles that use the fewest bits - can you see why?
Actually, it's not quite quicksort, in that he doesn't have the pivot
element, so and we really doesn't "compare" elements together -- he sends
elements to one of the two partitions independently. And, I went through
the calculations, and verified that it is unbiased in the N=3 case.
[1] Note: this is *not* a criticism of the algorithm -- as Paul mentioned,
for N>=3, any unbiased shuffling algorithm based on random bits will never
terminate on some sequence of random bits.
--
poncho
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: [Question] Generation of random keys - LONG - algorithms, randomness and
unpredictability
Date: Mon, 11 Dec 2000 00:00:20 GMT
David Schwartz wrote:
>
> "John A. Malley" wrote:
>
> > 1) An algorithm cannot produce randomness.
>
> I'll produce a simple counterexample. First, I'll take a fairly
> standard definition of randomness: a stream of numbers in some base is
> random if all numbers are equally probable and each output is
> uncorrelated with respect to any previous numbers.
Nonsense. To produce a counterexample, you have to use
the definition of the term that was used in the assertion.
Malley stated that he'd use "randomness" to mean more than
one outcome has non-zero probability.
Incidentally, a fairly common definition of random number
generator has each output equally probably and independent
of all previous outputs. I'm not sure where you got
"uncorrelated", which is a weaker condition than independent.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: [Question] Generation of random keys - LONG - algorithms, randomness
Date: Sun, 10 Dec 2000 16:31:55 -0800
Bryan Olson wrote:
>
> David Schwartz wrote:
> >
> > "John A. Malley" wrote:
> >
> > > 1) An algorithm cannot produce randomness.
> >
> > I'll produce a simple counterexample. First, I'll take a fairly
> > standard definition of randomness: a stream of numbers in some base is
> > random if all numbers are equally probable and each output is
> > uncorrelated with respect to any previous numbers.
>
> Nonsense. To produce a counterexample, you have to use
> the definition of the term that was used in the assertion.
Err, what? So if someone argues that snow is black, I have to check to
see whether if by "snow" they might have meant coal?
> Malley stated that he'd use "randomness" to mean more than
> one outcome has non-zero probability.
This is the weakest definition of "randomness" I've ever seen. It also
has an ambiguity problem, because probability has to be computed with
respect to some set of knowledge.
> Incidentally, a fairly common definition of random number
> generator has each output equally probably and independent
> of all previous outputs. I'm not sure where you got
> "uncorrelated", which is a weaker condition than independent.
If you make the definition even more restrictive, it simply strengthens
my point.
DS
------------------------------
From: kctang <[EMAIL PROTECTED]>
Subject: __(FYI) Funding Support at the Hong Kong Science Park
Date: Mon, 11 Dec 2000 11:19:04 +0800
==============EC976C4C1E487B5544123E77
Content-Type: text/plain; charset=big5
Content-Transfer-Encoding: 7bit
Funding Support at Hong Kong
============================
http://www.info.gov.hk/itc/eng/funding/itf.shtml
http://www.info.gov.hk/itc/eng/funding/arf.shtml
http://www.info.gov.hk/itc/eng/funding/pag.shtml
in http://www.info.gov.hk/itc/eng/about/mission_and_values.shtml
http://www.info.gov.hk/id/ewww/aboutus/function/technology/fund/industrial.htm
http://www.info.gov.hk/id/ewww/aboutus/function/development/index_service_fund.htm
in http://www.info.gov.hk/id/ewww
Hong Kong Science Park
======================
http://www.hksciencepark.com/hksp/tenants/Tenant-listindex.html
http://www.hksciencepark.com/hksp/RelatedSite/index.html
in http://www.hksciencepark.com/
Communicated by kctang
PS. Don't waste time anymore!
==============EC976C4C1E487B5544123E77
Content-Type: text/html; charset=big5
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<tt></tt>
<br><tt>Funding Support at Hong Kong</tt>
<br><tt>----------------------------</tt><tt></tt>
<p><tt><A
HREF="http://www.info.gov.hk/itc/eng/funding/itf.shtml">http://www.info.gov.hk/itc/eng/funding/itf.shtml</A></tt>
<br><tt><A
HREF="http://www.info.gov.hk/itc/eng/funding/arf.shtml">http://www.info.gov.hk/itc/eng/funding/arf.shtml</A></tt>
<br><tt><A
HREF="http://www.info.gov.hk/itc/eng/funding/pag.shtml">http://www.info.gov.hk/itc/eng/funding/pag.shtml</A></tt>
<br><tt>in <A
HREF="http://www.info.gov.hk/itc/eng/about/mission_and_values.shtml">http://www.info.gov.hk/itc/eng/about/mission_and_values.shtml</A></tt><tt></tt>
<p><tt><A
HREF="http://www.info.gov.hk/id/ewww/aboutus/function/technology/fund/industrial.htm">http://www.info.gov.hk/id/ewww/aboutus/function/technology/fund/industrial.htm</A></tt>
<br><tt><A
HREF="http://www.info.gov.hk/id/ewww/aboutus/function/development/index_service_fund.htm">http://www.info.gov.hk/id/ewww/aboutus/function/development/index_service_fund.htm</A></tt>
<br><tt>in <A
HREF="http://www.info.gov.hk/id/ewww">http://www.info.gov.hk/id/ewww</A></tt>
<br><tt></tt> <tt></tt>
<p><tt>Hong Kong Science Park</tt>
<br><tt>----------------------</tt><tt></tt>
<p><tt> <A
HREF="http://www.hksciencepark.com/hksp/tenants/Tenant-listindex.html">http://www.hksciencepark.com/hksp/tenants/Tenant-listindex.html</A></tt>
<br><tt> <A
HREF="http://www.hksciencepark.com/hksp/RelatedSite/index.html">http://www.hksciencepark.com/hksp/RelatedSite/index.html</A></tt>
<br><tt>in <A
HREF="http://www.hksciencepark.com/">http://www.hksciencepark.com/</A></tt>
<br><tt></tt>
<br><tt></tt>
<br><tt></tt> <tt></tt>
<p><tt>Communicated by kctang</tt><tt></tt>
<p><tt>PS. Don't waste time anymore!</tt></html>
==============EC976C4C1E487B5544123E77==
------------------------------
From: Ray Dillinger <[EMAIL PROTECTED]>
Subject: Re: What's better CAST in PGP or Blowfish 128bit?
Date: Mon, 11 Dec 2000 04:33:52 GMT
Noname <[EMAIL PROTECTED]> wrote:
: Yes, I need to learn and therefore I'm here:o)). Is it a problem? I cannot
: know everything:o)). I am coder and I need to include encryption into my
: product.
: And that's all. So for me is crypting only algorithm with input and output.
Well, that's not quite true, depending on the degree of security
you want. In order to implement crypto that can't be bypassed,
you have to get down'n'dirty with the hardware when you're doing
your implementation. It's not just input and output. You can
implement a good encryption function perfectly in terms of input
and output, and people will still hack into your customers' secret
files.
For example, if you store your key in a local variable while you're
computing ciphertext, and you let the system reclaim that memory
when the routine exits, you are leaving a copy of the key lying
around. A hacker will run another program to allocate the next
frame buffer, the system will probably hand it the memory you just
let go of, and guess what -- that other program can use it to
"guess" your key.
Dynamically allocated and stack allocated variables -- be SURE
to overwrite them before deallocating them. This even goes all
the way out to the math routines, etc, that you've got in the
standard libraries and never think about.
Hmm, what else? Oh yeah, something else you probably don't normally
think about. When the system runs low on physical memory, it swaps
processes to disk. Including their local variables. Including the
key if you've got it stored in a local variable. And yes, someone
who seriously wants to hack your program *will* come in with a
utility that takes snapshots of the swap space and uses that to
make password guesses...
Anything that could contain a key or plaintext, needs to be
"volatile" so that the system can't swap it to disk.
Hmm, what else? Oh, another thing you don't normally think about.
If you're using a GUI front end, and you're displaying your keys
or your plaintext, then your window classes have copies of it. So
you've got to go in there and make sure *they* are also declaring
things volatile, overwriting local variables before exit, etc.
These are the major ways that systems can have good crypto algorithms
and still get nailed in the real world. There are others. The point
is that a good cipher and a correct implementation does not make a
secure product -- at least not by themselves. If you want to do it
right, you have to have a good cipher and an implementation that is
both correct and utterly paranoid about leaving traces anywhere
on the system.
If you are interested in the kind of gaffes made by major software
manufacturers, go to www.counterpane.com and read the crypto-gram
newsletter archives. Search for the word "doghouse" or "dog-house"
in each of a dozen different crypto-gram newsletters. You'll find
interesting things.
Now, if after that crash course in how to not do it, you still feel
that you can write good cryptographic code without dedicating a chunk
of your life to it, be my guest and good luck. But don't think in
terms of inputs and outputs -- think in terms of sheer paranoia and
how an attacker might come after the key or plaintext.
Bear
------------------------------
Date: Mon, 11 Dec 2000 00:42:05 -0500
From: Lee Winter <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
John Myre wrote:
> "Trevor L. Jackson, III" wrote:
> <snip>
> > The human body produces about one watt per pound. The Sun produces less than
> > this. Since the Sun has a density below unity (it would float) it also produces
> > less energy per unit volume.
>
> Joke, right?
No. The issue isn't energy density, but power density. The energy density of the sun
is pretty high (the permeation time is about 10K years). The power density of the sun
is less than that of human flesh. The numbers are: 4e12g/sec in a volume of 5e26
cubic meters, or ~1e-14 g/sec.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
