Cryptography-Digest Digest #981, Volume #8 Wed, 27 Jan 99 15:13:03 EST
Contents:
Re: Random numbers from a sound card? ("Tony T. Warnock")
Re: hardRandNumbGen (Mok-Kong Shen)
RC4 question ("Hai Huang")
Re: hardRandNumbGen (R. Knauer)
Re: Random numbers from a sound card? ([EMAIL PROTECTED])
Re: Foiling 56-bit export limitations: example with 70-bit DES ("Peter K. Boucher")
Re: Metaphysics Of Randomness (Medical Electronics Lab)
long keys from short ones ("Scott A. Berg")
Re: hardRandNumbGen (Patrick Juola)
Re: hardRandNumbGen (Patrick Juola)
Re: hardRandNumbGen (R. Knauer)
Re: hardRandNumbGen (Patrick Juola)
Re: Random numbers from a sound card? ([EMAIL PROTECTED])
Re: hardRandNumbGen (Mok-Kong Shen)
----------------------------------------------------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Random numbers from a sound card?
Date: Wed, 27 Jan 1999 12:06:35 -0700
Reply-To: [EMAIL PROTECTED]
Medical Electronics Lab wrote:
> Mok-Kong Shen wrote:
> > I am not against having something ideal and perfect as a standard
> > for approximation (to be strived at in practice) or for pedagogical
> > purpose. But to say there IS (in the sence of EXISTS) something
> > perfect can be misleading.
>
> Kind of depends on how you define "perfect". Perfect for what and
> measured in what way? We can certainly build a TRNG which is
> perfect in any measureable sense.
>
> > To 'just look' is certainly not ensuring (compare watching a
> > magician pulling rabits out of his hat). We have to ascertain
> > how 'random' the sequence we get really is. And that's one of
> > the real and big problem for the practice.
>
> Which is what makes this whole discussion so much fun. DIEHARD
> and Diaphony and autocorrelation all measure "random" in a slightly
> different way. If the output of a TRNG appears random to all those
> tests, we can say it "looks" random. It is "perfect" as far
> as we can measure. Isn't that good enough?
>
> Patience, persistence, truth,
> Dr. mike
It's not clear what is wanted here. In limit (infinitely long sequences)
both the complexity based and the frequency (statistical) based
definitions of random are equivalent (per Martin Lof). For finite
sequences (actually for computable sequences, IMHO) these are not
necessarily equivalent. It is easy to produce sequences that satisfy the
strong law of large numbers. Champernowne's sequence comes to mind:
01,1011,100101110111,.... It is not very complex computationally. It does
have the proper frequency of everything, that is, each k bit sequence has
limiting frequence 1/2^k. Unfortunately I do not know of any easily
constructed sequence that satisfy the law of the iterated logarithm. I do
not even know how to test for this. It would be a requirement for a
"statistically random" sequence.
It's possible that one can only list a set of criteria and check if your
sequence satisfy them. Again, most of these criteria are not computable
but "almost all" sequences satisfy them
Tony
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 19:19:57 +0100
R. Knauer wrote:
>
> On Wed, 27 Jan 1999 18:01:00 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >Please note I don't claim PRNGs are good. I simply doubt that
> >hardward generators are good because I have no tools to determine
> >that they are good, except by using statistical tools.
>
> You must be skilled at designing a TRNG. Statistical tools are
> worthless.
How do you measure or test the skill of a person designing a TRNG?
Using some tests of the psychologists?? More precisely, how do
you show through a test of skill that the resulting TRNG designed
by that person has a certain 'crypto-grade', even if you could define
that 'crypto-grade' scientifically precisely which I guess you can't.
Are you excluding that a skilled person could ever make mistakes??
M. K. Shen
------------------------------
From: "Hai Huang" <[EMAIL PROTECTED]>
Subject: RC4 question
Date: Wed, 27 Jan 1999 13:05:07 -0600
I am a newbie in encryption. I downloaded a source code for rc4 encryption,
and compiled it under Borland c++5.0.
I run the program by type in "rc4 4432411432 <sample.txt >sample1.txt", and
the program give me a new file called sample1.txt which contains the
encrypted information. But how do i decrypt sample1.txt back? I tried to
type in "rc4 4432411432 <sample1.txt >sample2.txt", and sample2.txt contains
only a fraction of the original data in sample.txt. I don't know what is
wrong with it. Can anyone tell me what i did wrong? Thanks in advance.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 18:13:20 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 27 Jan 1999 18:29:34 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>> 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.
You STILL haven't got it.
The OTP cryptosystem is proveably secure.
Why are you struggling with that?
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]
Subject: Re: Random numbers from a sound card?
Date: Wed, 27 Jan 1999 18:09:54 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Ross) wrote:
> Lets say I'm digitizing a sine wave of constant frequency &
> amplitude. If it has a 1 Volt peak amplitude and if I digitize at a
> constant rate, won't 1/2 of my samples yield a value of either >+.707
> Volt or < -.707 Volt? Seems like a built-in bias toward higher
> numbers...
The threshold of your detector, which decides whether a voltage
is to be called a 0 or a 1 (for this clock period), will determine your
0:1 bias. (In addition to your raw waveform's properties!)
This threshold will interact with DC biases in your waveform.
And both will drift, and differ between parts.
You will not ever get perfect 0:1 ratios
---for instance, amplifiers may switch from 0->1 faster than 1->0
(even for CMOS) so you must plan for it. Happily, combining
multiple bits (e.g., parity ) brings the ratio near
1:1 exponentially fast. Again, RFC 1750 is the bible.
Shannon is the Prophet.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Date: Wed, 27 Jan 1999 11:02:42 -0700
From: "Peter K. Boucher" <[EMAIL PROTECTED]>
Subject: Re: Foiling 56-bit export limitations: example with 70-bit DES
[EMAIL PROTECTED] wrote:
[snippety snip]
> Consider a hypothetical M-DES Standard (hereafter, M-DES) which would specify
> a total of 2M pre-defined and publicly known 64-bit different blocks of data,
> for various choices of M = 0, 1, ... Now, when Bob wants to send a message to
> Alice, he needs to negotiate a M-DES cipher with Alice, which includes a
> 56-bit secret-key [Note-1] and a publicly defined value for M, say M = 14.
> The value of M is chosen by Bob according to his security needs [Note-2], and
> accepted (or not) by Alice. To use M-DES, Bob would privately choose one
> 64-bit "key" at will (from the public list of 2^14 "keys") and then
> repeatedly use this choice to XOR-encode one by one each of all 64-bit DES
> ciphertext blocks which are calculated with the 56-bit secret-key he shares
> with Alice -- without disclosing his choice (i.e., anyone else would ignore
> the choice). Thus, Bob's choice is an "unknown key" to anyone else, including
> Alice -- providing open ignorance.
A well-known stream-cipher with variable-size keys might work as well
(or better, for flexibility's sake) for your notion of M-DES. For
example, generate M bits randomly, use these as, hypothetically
speaking, an RC4 key. You pre-encrypt the entire message with the
stream cipher, then encrypt with DES. Your recipient (and any
attackers) must brute-force the M-bit stream-cipher key.
One problem with this approach is that you must include known-plaintext
in your protocol, if your recipient wants to be sure he has correctly
guessed the M-bit "whitener."
Peter
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Wed, 27 Jan 1999 12:46:21 -0600
R. Knauer wrote:
>
> It just occured to me after finishing Chaitin's new book, "The
> Unknowable", that perhaps one reason people insist on using
> statistical tests to characterize numbers as random - which we know is
> incorrect for purposes of crypto - is that one can presumably
> characterize certain numbers by such means, but only if they are
> infinite in length.
>
> One might be tempted to say that if a very large number is
> characterized as random by statistical methods, then it is "almost"
> perfectly random. But as I understand it, that is a error in
> judgement. If the numbers you are using are finite, then the only way
> you can decide if they are random for purposes of cryto is to
> characterize the generator that produced them.
I'm confused. How else other than statistics can I tell if a
TRNG is working? The stats certainly tell me when it's *not*
working!
You need to know several things to be reasonably confident that
bits are random. 1) the circutry and equipment are what you
designed, 2) everything is shielded from outside influence and
3) the stats say "it still looks random".
A user of a piece of equipment can inspect 2, but they only
have statistics to tell them if the RNG is actually working.
Chances are they don't have logic analyzers and o'scopes to
check the RNG themselves (1). As a user, stats are all you
have, so I don't see how it's an "error in judgement" to use
that to determine if your RNG is still working.
The truely paranoid should have an o'scope tho! :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Scott A. Berg" <[EMAIL PROTECTED]>
Subject: long keys from short ones
Date: Wed, 27 Jan 1999 13:56:58 -0600
Pardon my naivete, but:
Suppose you had a really good generator of short random numbers, e.g.
digitize Brownian motion into 32 bits. Could you just concatenate (string
together) several of these to end up with a really long, truly random
sequence (OTP)?
While I want to say "Yes, of course", I know that a complex process can
sometimes generate a sequence that is non-obvious but still not random. My
favorite example is in Knuth volume I where he has this long example of
jumping to a randomly chosen subroutine that generates a random number, but
ends up with a terrible generator.
Scott
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 27 Jan 1999 14:29:25 -0500
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>R. Knauer wrote:
>>
>> On Wed, 27 Jan 1999 18:01:00 +0100, Mok-Kong Shen
>> <[EMAIL PROTECTED]> wrote:
>>
>> >Please note I don't claim PRNGs are good. I simply doubt that
>> >hardward generators are good because I have no tools to determine
>> >that they are good, except by using statistical tools.
>>
>> You must be skilled at designing a TRNG. Statistical tools are
>> worthless.
>
>How do you measure or test the skill of a person designing a TRNG?
The same way you test the skill of the architect who designed your
building.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 27 Jan 1999 14:32:25 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On Wed, 27 Jan 1999 12:13:29 -0500, "Trevor Jackson, III"
><[EMAIL PROTECTED]> wrote:
>
>>R. Knauer wrote:
>
>>> On 27 Jan 1999 10:21:56 -0500, [EMAIL PROTECTED] (Patrick Juola)
>>> wrote:
>
>>> >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....
>
>>> I can rely on keeping it just as secret as I keep my keys. If my code
>>> has been compromised, so have my keys.
>
>>Hardly. One can change keys arbitrarily. Once cannot change code so often
>>(here code == algorithm not .EXE).
>
>How about making your algorithm (code) part of the key? That way you
>could change algorithms as often as you change keys.
The larger the key, the more difficulty you have in changing/exchanging
it.
If you're going to exchange 10,000 bytes of code, why don't you use
the same mechanism to exchange a 10,000 byte RSA key or something like
that, which gives you much more bang/buck?
-kitten
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 18:28:35 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 27 Jan 1999 12:10:17 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>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.
Algorithmic analysis of the generated output itself is completely
worthless if that output is finite in length. If the number 111...1 is
generated by a TRNG, then it is a perfectly valid crypto-grade random
number, just like all the other 2^N-1 numbers of the same length.
Since all of these 2^N sequences of length N are random numbers, what
analysis of them is going to tell you that they are or are not random?
If you apply your analysis to each of the 2^N numbers, then you must
get the same result for each one since they are generated by a TRNG,
otherwise your analysis is fatally flawed.
If your analysis does give the same result for each number, what value
is it in determining randomness or non-randomness? If it correctly
gives the same result for each number, there is no discrimination
being performed. In fact, the analysis needs to say: "I cannot decide
if that number is random or not", for each number, or it is wrong.
If you could prove algorithmically that a given finite sequence is
truly random, then you could also solve both the Godel incompleteness
problem and the Turing halting problem - which are related.
See Chaitin (op. cit.) for the details why.
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] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 27 Jan 1999 14:27:50 -0500
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>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?
Sure. If the key is "as random as" the message, then Shannon's
proof of secrecy goes through. In particular, if your messages
are bounded by a given length N, then if you can get N bits of
randomness, from whatever source, hardware or software, then
you can achieve perfect secrecy.
How you get them is, of course, your problem. The difficulty is
in *proving* that a given sequence of N bits is contains N bits
of randomness (or more formally that a given generator produces
exactly random bits). But it's fairly easy to gather *MORE* than
N bits -- as much more as you feel confident that it is unlikely
to be more less than N bits of randomness in the resulting sample.
Furthermore, I note that "sound scientific basis" doesn't necessarily
rely on a formal, mathematical proof. We use the acceleration of
gravity g = 9.8 m/sec on the basis of experiment rather than any
first-principle analysis. Similar experiments show that, for instance,
English text contains just over one bit of randomness per character.
If you need a thousand bits of randomness, get a thousand characters
of English text from a secure source, distill them appropriately with
a trusted hashing function. Better yet, get 1500 characters to allow
for sloppy engineering -- you'd never run a wire at its rated wattage,
would you? Take the resulting 1000 bit string, XOR it with the plaintext,
and voila. A scientifically sound method of securing 1000 bit secrets.
>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.
Well, the usual definition is "work factor" -- the ratio of work
necessary to read a message without the key vs. with the key.
Again, "sound scientific basis" does not necessarily rely on proof;
if you are willing to accept (as many scientists do) that RSA is
as secure as factoring, then the work factor to crack an RSA code
can be made as large as you like by raising the modulus appropriately.
If you don't believe that RSA is as secure as factoring.... well, there
are other methods out there with various conjectures about their
difficulty of solution. If you don't believe *any* conjectures, you're
arguably in the same camp as people who don't really believe that
the force of gravity is constant just because it's always been constant
so far....
-kitten
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Random numbers from a sound card?
Date: Wed, 27 Jan 1999 18:18:17 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Ross) wrote:
> Nathan Kennedy wrote:
>
> > > What sort of audio source would you suspect would be the best to use
> > > in generating random numbers?
> >
> > I tune a cheap AM radio to a loud static channel, and wire that into the
> > mic port.
FM has better hiss. I leave it to RF folks to explain why. Probably
because FM listens to wider chunks of the aether than AM. Or because
of the design of FM receivers amplifying component-noise more?
> Have tried something very similar to that. I am attempting to
> create a rotortable of all 256 byte values placed in 'random' order,
> but the (8 bit) SoundBlaster seems reluctant to produce a 0xC0 byte.
> I infer this because in over 80% of the rotortables I create, 0xC0 is
> the last table entry.
>
> I'd guess that the 'consumer-grade' A->D & D->A converters used
> in common sound cards are susceptible to all sorts of troubles like
> this, i.e. missing codes and/or monotonicity problems.
>
> David Ross [EMAIL PROTECTED]
Yes. You have to assume everything is imperfect. Your raw source
is biassed, your whole amplification/detection (ie, digitization) chain
has got holes in it (in either time or frequency domains), and
you're in a fun digital-switching environment for extra bonus
problems.
This is why measurement is so much better than handwaving.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 19:36:17 +0100
R. Knauer wrote:
>
>
> You STILL haven't got it.
>
> The OTP cryptosystem is proveably secure.
>
> Why are you struggling with that?
I never refuse to acknowledge 'The OTP cryptosystem is proveably
secure'. Only as I said repeatedly that that fact is USELESS for
the practice, i.e. useless for the user of a crypto application,
because he can't get a perfect OTP to give him the 'provable
security'. Neither will he, excepting a mentally illed, demand
absolute security. But he has a right to demand that the security
offered by a system be demonstrated. Simply saying that a hardware
generator offers high security is NO convincing argument for him.
He has to have some supporting scientific data. Now for a random
number sequence I don't know any way to provide such data excepting
through statistical tests. And by the discussions till now you
also don't know a way. So it is my opinion that using statistical
tests at least gives him something concrete for him to form a more
or less objective opinion, even though we should tell him that the
tests are questionable for this and that reason. This is anyway
better than leaving him with nothing to form a (subjective) opinion
of the encryption scheme he is using. Have I expressed my arguments
clearly?
M. K. Shen
------------------------------
** 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
******************************
