Cryptography-Digest Digest #980, Volume #8 Wed, 27 Jan 99 14:13:03 EST
Contents:
Re: Foiling 56-bit export limitations: example with 70-bit DES (Mok-Kong Shen)
Re: hardRandNumbGen (R. Knauer)
Re: Pentium III... (Bruce Barnett)
Re: hardRandNumbGen (Mok-Kong Shen)
Re: hardRandNumbGen ("Trevor Jackson, III")
Re: hardRandNumbGen (Patrick Juola)
Re: hardRandNumbGen (Patrick Juola)
Re: hardRandNumbGen (Mok-Kong Shen)
Re: hardRandNumbGen (Mok-Kong Shen)
Re: hardRandNumbGen (Mok-Kong Shen)
Re: Random numbers from a sound card? (R. Knauer)
Re: hardRandNumbGen (R. Knauer)
Re: hardRandNumbGen (Mok-Kong Shen)
Re: Who will win in AES contest ?? (DJohn37050)
Re: hardRandNumbGen (Mok-Kong Shen)
Re: hardRandNumbGen (Patrick Juola)
Re: Java speed vs 'C' (was Re: New Twofish Source Code Available) (Fabrice Noilhan)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Foiling 56-bit export limitations: example with 70-bit DES
Date: Wed, 27 Jan 1999 16:36:40 +0100
Patrick Juola wrote:
>
> Interesting idea. On the other hand, all it really seems to do
> is to slow down Alice's ability to communicate to exactly the
> same degree that it slows down Mike's ability to read her communications.
> So the work factor -- i.e. the ratio between Alice's time to decrypt
> and Mike's -- is unchanged.
Through slowing down both the legitimate communication partners
AND the analyst are affected. But if the analyst has to do much
more work than the legitimate partners, say, by a factor 2^55,
then that slowdown could push the workload of the analyst to
a level beyond his computing capability, while the legitimate
partners only have to tolerate some moderate amount of delays. This
is my proposed new paradigm 'Security through Inefficiency'. I employed
it in the EX-versions of my WEAK-series of algorithms in response to
the Wassenaar regulations.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 16:45:09 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 27 Jan 1999 16:52:30 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Where is the proof of 'if the generation process is hardware then
>it is crypto-grade, otherwise it is not'??
There is no proof of the first part, since PRNGs can be implemented in
H/W, like shift register PRNGs.
The proof of the second part comes from an analysis of what makes a
PRNG behave the way it does. It is based on an algorithm, which means
that its output is deterministic, and that means that there could be
vulnerability in using it. For example, if it did not output all
possible sequences of a given finite length equiprobably but started
repeating the sequneces, then it fails the definition for a TRNG.
If a PRNG only puts out a few sequences most of the time, then it is
obviously worthless. That takes care of the equiprobable part of the
TRNG specification.
Assuming that the outputs of the PRNG are equiprobable, if the PRNG is
seeded with a number of length K that is smaller than the output
needed to encrypt the message of length N, then it can only generate
as many sequences as the seed will allow, which is not the same as all
possible sequences.
If K<N, then only 2^K possible plaintexts are contained in the
ciphertext, instead of 2^N. That makes the cryptanalyst's job a lot
easier, especially when the message is longer than the unicity
distance. In that case, there is only 1 plaintext that is
intelligible. When the cryptanalyst finds it, he knows with certainty
that it is the intended message. That is not the case when using a pad
that is generated from a TRNG, where the full 2^N outputs possible.
Bob Knauer
"No Freeman shall ever be debarred the use of arms. The strongest
reason for the people to retain the right to keep and bear arms is,
as a last resort, to protect themselves against tyranny in government."
--Thomas Jefferson
------------------------------
From: Bruce Barnett <[EMAIL PROTECTED]>
Subject: Re: Pentium III...
Date: 27 Jan 1999 09:58:11 -0500
[EMAIL PROTECTED] writes:
> I can think of cases where having a machine serial number would be somewhat
> handy. I'm not sure I would build it into the processor though.
And what do you do with a 2,4,8 or 64-CPU server?
It's the big servers that need it.
Dynamic roll-over should be interesting...
--
Bruce <barnett at crd. ge. com> (speaking as myself, and not a GE employee)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 18:20:22 +0100
Patrick Juola wrote:
>
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >Patrick Juola wrote:
> >>
> >
> >> More accurately : one can't claim hardware sequences are always to
> >> be preferred to software sequences *on the basis of a statistical
> >> analysis of a finite set of output sequences.*
> >
> >The issue is: Are there other sound scientific basis to claim the
> >said preference.
>
> And the answer is : yes, if your goal is to provide unbounded
> degrees of security for messages of unbounded length.
I would be happy with a weaker goal, i.e. for messages of a
certain finite length. Could you provide the requested sound
scientific basis? Note that I am going to use the sequences
in practical applications. So any claimed degree of security
has be shown with a practical algorithm. I am also prepared to
weaken the goal further to 'bounded degree of security' if you
can give a precise definition of 'degree of security' that is
satisfactory for the practice.
M. K. Shen
------------------------------
Date: Wed, 27 Jan 1999 12:10:17 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>,
> R. Knauer <[EMAIL PROTECTED]> wrote:
> >On 27 Jan 1999 08:37:36 -0500, [EMAIL PROTECTED] (Patrick Juola)
> >wrote:
> >
> >>You *can't* evaluate a random number generator based only on the
> >>statistical properties of the stream it produces.
> >
> >I fully agree for finite sequences, but as I mention in the thread
> >entitled "Metaphysics of Randomness", statistical tests presumably do
> >apply to infinite sequences. But then, an infinite sequence contains
> >all the details about the generation process, so that makes sense.
>
> Umm.... this is a very limited use of the word "test." I will, of
> course, be delighted to apply any test you choose to any sequence
> you choose, finite or note. But I charge by the hour, and it would,
> of course, be improper of me to give you any results until after I've
> examined the entire sequence.
>
> Still want me to test that infinite sequence for you?
>
> >On an earlier occasion I asked if the Bayesian attack could be used to
> >characterize crypto-grade random numbers. If I gave you a large number
> >of ciphers of substantial length based on some unknown key generation
> >procedure, you tried the Bayesian attack on them and they "leaked" no
> >significant amount of information, then you would probably conclude
> >that the pads were most likely generated by a TRNG, even if I had used
> >some other method like a well-hashed stream cipher.
>
> Probably. By the time you get up to the upper reaches of what we
> can do with PRNGs, the information leak over reasonably-sizes
> samples is pretty infinitesimal. Having only reasonably-sized
> amounts of funding, computing power, and patience at my disposal,
> there's a limit to what can be detected -- and if I get something
> that's indistinguishable from random by this test, then I'm probably
> willing to pass it as a "good" RNG.
>
> On the other hand, there's definitely a possiblity of error there,
> which is why I wouldn't be likely to make any such statement without
> asking to see how you generated the key sequence(s). An example
> of something you could "sneak under the radar" would be a very large
> LFSR. There are well-known tests of linear complexity that give the
> minimum size of an LFSR to generate a given sequence. A "truly random"
> sequence will (with probability 1) yield a complexity curve looking
> something like this :
>
> _/
> _/
> _/
> _/
> _/
> _/
> /
>
> A LFSR-generated sequence will have a complexity curve something like
> this :
>
> ____________________________________
> _/
> _/
> _/
> _/
> /
>
> where it levels off after you hit the generator size.
>
> The question, however, is
>
> a) did you give me enough data to find where the sequence levels off?
> b) did I run a test powerful enough and long enough to find that point?
>
> The first is a mathematical property of the sequence. The second is
> a question of my time, expertise, and a bit of luck.
>
> The problem is that the Bayesian attack only works if I know -- or
> can guess -- the type of bias likely to be in your generator. In
> most cases this isn't a problem; many biases are blatantly obvious
> or result from common mistakes. The more sophisticated you are at
> hiding your biases, the less likely I am to guess the sort of bias
> or to lose patience/funding before I complete the necessary tests.
> (Of course, if I have an infinite amount of time/money, I can
> make an infinite number of guesses and will probably guess right
> on at least one of them.)
>
> On the other hand, if I can get a copy of your code, I can just read
> the code and determine your biases. But you can't rely on keeping
> your code secret....
>
> > Then I went on to
> >ask if such a "Bayesian Test" for vulnerability could be used to
> >produce confidence limits on the security of subsequent ciphers
> >produced by that encryption method.
>
> In theory, given a large enough number of computers, without
> question. But we're running into serious funding difficulties here.
>
> >But why should applying the Bayesian Test to presumably random numbers
> >be any different? (I think I know why - one is a statistical test, the
> >other is a probability survey.)
>
> More a question about finite vs. infinite data. Bayes' Theorem lets you
> refine hypotheses about biases that you've already made. Conventional
> statistics just let you test for the presence or absence of a visible
> bias. As any statistician will tell you, you can't prove the absence
> of an effect by statistical means. You can just prove that it
> didn't show up in your experiment and therefore was less than the
> sensitivity of your test.
>
> Of course, with infinite data, you can develop "tests," in the loosest
> possible sense, of infinite sensitivity. But this isn't helpful.
To boil all this verbiage down, analysis of the generation process is more
efficient than analysis of the generator output. One reason for the
improved efficiency is that understanding the generation process provides
hints of the potential defects worth testing. Another reason is that the
description of the generation process is logarithmicaly smaller than the
description of the generated output.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 27 Jan 1999 10:30:16 -0500
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>Patrick Juola wrote:
>>
>
>> The fact that you're repeatedly asking the same dumb question does,
>> however, suggest that you're not really interested in the answer.
>
>The origninal purpose is evidently: Since there can't be an good
>answer, one can't claim hardware sequences are always to be preferred
>to software sequences.
Your claim above is untrue. I can prove that there can't be a good
s/w sequence running on a deterministic machine. But I can't do that
merely by inspecting any finite sample of outputs -- I have to look
at the generators to do it. Of course, any bad PRNG can be implemented
either in h/w or s/w, so just because something is in h/w doesn't make
it good.
More accurately : one can't claim hardware sequences are always to
be preferred to software sequences *on the basis of a statistical
analysis of a finite set of output sequences.*
But this is unsurprising. I can't tell you the gas mileage by looking
at the color of the paint, either.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 27 Jan 1999 12:05:41 -0500
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>R. Knauer wrote:
>>
>
>> What he fails to appreciate is that there is a fundamental difference
>> between a TRNG and a PRNG. That is because he fails to realize that a
>> crypto-grade random number is characterized by the generation process,
>> not the number itself.
>
>Where is the proof of 'if the generation process is hardware then
>it is crypto-grade, otherwise it is not'??
There isn't such a proof. There *is* a proof that if the generation
process is purely software running on a deterministic routine, then
the randomness of the resulting pad is bounded by the randomness
of the starting conditions.
And there's a similar proof that bounded randomness cannot provide
perfect secrecy to a message of unbounded length.
-kitten
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 15:30:05 +0100
Trevor Jackson, III wrote:
>
> The fundamental reason is that, for security purposes, we have to assume that our
> opponent can do anything we can do. We can re-run the software and obtain the
> identical output. We cannot re-run the hardware and get the same output. Thus the
> hardware is superior.
>
> The deceptive provision in your question is the fact that the sources are hidden.
> This amounts to security via obscurity. Obscurity fails catastrophicaly when it is
> breached. A bad thing because the opponent can steal a copy of the software and
> get every output we will every get. He cannot steal a copy of the machine and get
> identical outputs to ours.
If you produce some sequence with a sufficiently good algorithm with
a sufficiently long key and later forget that key, even you wouldn't
be able to reproduce the sequence. As to stealing I suppose it is
irrelevant in the present context. (If you have a one-time pad and
that got stolen (copied), then what?)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 18:29:34 +0100
Patrick Juola wrote:
>
> >Where is the proof of 'if the generation process is hardware then
> >it is crypto-grade, otherwise it is not'??
>
> There isn't such a proof. There *is* a proof that if the generation
> process is purely software running on a deterministic routine, then
> the randomness of the resulting pad is bounded by the randomness
> of the starting conditions.
>
> And there's a similar proof that bounded randomness cannot provide
> perfect secrecy to a message of unbounded length.
Entirely true. It is for the same reason that none of the known
(implementable) ciphers can offer absolute security. But that
cetainly doesn't imply that any hardware generator can offer
absolute security. One should also note that even 'crypto-grade'
is itself a fuzzy term.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 16:48:46 +0100
Patrick Juola wrote:
>
> More accurately : one can't claim hardware sequences are always to
> be preferred to software sequences *on the basis of a statistical
> analysis of a finite set of output sequences.*
The issue is: Are there other sound scientific basis to claim the
said preference.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random numbers from a sound card?
Date: Wed, 27 Jan 1999 17:36:54 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 27 Jan 1999 17:46:44 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>> "It all depends on what the meaning of the word 'is' is."
>That way clearly stated in my previous post, quoted below:
> But to say there IS (in the sense of EXISTS) something
> perfect can be misleading.
>A word can have a multitude of meanings. I was prudent enough
>to put the parentheses above to make sure that there could be
>no misunderstanding. I regret that my attempt was appraently
>not successful.
You must be a mathematician.
As Greg Chaitin says in his latest book. "The Unknowable", physicists
have a sense of humor (BTW, I am a physicist), but mathematicians do
not have a sense of humor.
Which is not completely true because Chaitin is a mathematician and he
has a sense of humor.
Whatever.
Bob Knauer
"No Freeman shall ever be debarred the use of arms. The strongest
reason for the people to retain the right to keep and bear arms is,
as a last resort, to protect themselves against tyranny in government."
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 17:39:15 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 27 Jan 1999 17:55:15 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>It is important to know what the specifications ARE. Certainly
>things like the dimensions of the apparatus don't have too much
>bearing in the present context. Now what are the specifications that
>ensures a crypto-grade TRNG? These specifications must contain
>certain numerical values in terms of certain units. Then one can
>test the actual product to see whether the specifications are
>fulfilled. As long as one can't define 'crypto-grade' in terms
>of certain units precisely, there is NO way to write up such
>specifications as you proposed.
Check out the Hotbits radioactive decay TRNG:
http://www.fourmilab.ch/hotbits/
Bob Knauer
"No Freeman shall ever be debarred the use of arms. The strongest
reason for the people to retain the right to keep and bear arms is,
as a last resort, to protect themselves against tyranny in government."
--Thomas Jefferson
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 16:52:30 +0100
R. Knauer wrote:
>
> What he fails to appreciate is that there is a fundamental difference
> between a TRNG and a PRNG. That is because he fails to realize that a
> crypto-grade random number is characterized by the generation process,
> not the number itself.
Where is the proof of 'if the generation process is hardware then
it is crypto-grade, otherwise it is not'??
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Who will win in AES contest ??
Date: 27 Jan 1999 16:10:52 GMT
Rich,
Gee, shucks, aw thanks.
I think all submissions tothe 2nd AES conference will be publicly available
from NIST's AES website even if not accepted for presentation at the
conference.
Don Johnson
Don Johnson
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 16:59:03 +0100
R. Knauer wrote:
>
> By analyzing the design. With correct design one can make a TRNG
> random to within an arbitrarily high level of precision.
>
> If the TRNG is certified to produce crypto-grade random numbers to a
> level of precision that ensures that it would take an impossible
> amount of work to make it vulnerable, then that is "perfect" in a
> practical sense.
>
> If the ball bearings in your car's wheels are spherical enough so that
> they do not tear up the bearing races, that is "perfect" enough in a
> practical sense.
>
> Being obsessed over the fact that there is no such thing as a Perfect
> TRNG or a Perfect Sphere in the real world is a waste of time at the
> practical level. There are more important considerations that affect
> security - like having someone steal your pad.
If you make a metal sphere, there is a common definition of precision.
What is the 'precision' you are referring to about your TRNG design?
You have to define that 'precision' in scientific terms, in particular
establish a 'unit' and provide a precise method to measure that
'precision' in that unit. Before that, you have nothing.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 27 Jan 1999 12:01:50 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On Wed, 27 Jan 1999 15:38:29 +0100, Mok-Kong Shen
><[EMAIL PROTECTED]> wrote:
>
>>Secondly, your equiprobability is not at all sufficient.
>
>I never said it was. I said that the TRNG must be *CAPABLE* of:
>
>1) Outputting all possible sequences of a given finite length; and
>
>2) Outputting each of them equiprobably.
>
>>If the said given finite length is 2, is a physical device outputting
>>0001101100011011..... a TRNG?????
>
>Sure, why not - if you group the number above in 2-bit sequences:
>
>00 01 10 11 00 01 10 11
>
>Pad1: 00
>Pad2: 01
>Pad3:10
>....
>Pad8: 11
Minor quantification error :
Mr. Knauer's criterion should not be interpreted as:
There exists a length such that all possible sequences of that
length are outputted equiprobably,
but as :
For all (finite) lengths, all possible sequences of that length are
outputted equiprobable.
So if that's really the output of your generator, it's *NOT* a TRNG
as it's a single 8-bit sequence repeated with probability 1.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Fabrice Noilhan)
Subject: Re: Java speed vs 'C' (was Re: New Twofish Source Code Available)
Date: 27 Jan 1999 16:40:08 GMT
According to Bruce Barnett <[EMAIL PROTECTED]>:
> Someone who is familiar with C and ASM can do similar changes in the C
> code to improve the ASM code that is generated.
OK, but as far as I know, the best implementation of DFC in asm is made
by a C compiler (DEC's cc). Of course, you *can* do it yourself but it
takes much more time, it is painful and you save only a few cycles. Is
it worth doing it?
> My suggesting is to
> Write it in C
> Optimize it in ASM by hand-tuning the instructions.
> Re-write the C to generate code as similar to the ASM as
> possible.
> Compare the two versions.
OK, that's what I usually do!
> As for Java - I guess someone has to be very familiar with the
> performance of the virtual machine, including the cost of each virtual
> instruction, etc.
It seems that it is platform-dependent so it is very difficult to tune
(JIT compilation doesn't help to do that!).
One good thing would be to write into JVM asm (a.k.a. bytecode) at once.
This is not hard, and it saves a lot of pain (but it is now readable).
Once again, if you know on what platform the java code will go, you can
switch to native asm!
Fabrice
------------------------------
** 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
******************************
