Cryptography-Digest Digest #49, Volume #9 Sun, 7 Feb 99 12:13:05 EST
Contents:
Re: RNG Product Feature Poll (R. Knauer)
Re: RNG Product Feature Poll (Herman Rubin)
Re: What is left to invent? (R. Knauer)
Re: Loony question (Scott Fluhrer)
Re: Rolling code generators (Philip Koopman)
Re: Encryption Algorithms (Mr. Tines)
Re: hardRandNumbGen (R. Knauer)
Re: *** Where Does The Randomness Come From ?!? *** ("PAC")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: RNG Product Feature Poll
Date: Sun, 07 Feb 1999 14:11:50 GMT
Reply-To: [EMAIL PROTECTED]
On 7 Feb 1999 08:12:50 -0500, [EMAIL PROTECTED] (Herman Rubin)
wrote:
>Reasonable statistical properties are more than enough for cryptography,
You will have to prove that assertion - I cannot take it on your word
alone. In particular, I would have to see how indeterminancy comes
from "reasonable statistical properties".
>while the other may not be the case.
What "other"?
> Also, one can include, in the
>statistical tests, those which will be needed for good cryptographic
>sequences of bits.
Again, I need to see a proof of that. In particular, I need to see how
you identify "those [properties] which will be needed for good
cryptographic sequences of bits", namely the crucial property of
indeterminancy.
>>IOW, your certainty that no decay event can be detected in the
>>blanking interval, t2 -> t3, does not effect the randomness
>>(indeterminancy) of detection of a second detection after that
>>interval.
>It is quite possible that it does, in particular, if particles to be
>detected have different energies.
Because the particles we are talking about here arise from a decay
process, they must of necessity have different energies. In order for
the excited state from which they decay to have a finite half life, it
must of necessity have an indeterminancy in its energy also. Only the
grounfd state, with its infinite half life, has no inteterminancy in
its energy, at least none from the Uncertainty Principle.
The half life of a radioactive isotope is a measure of indeterminancy
in time of when it will decay, and the spectral half width of the
energy spectrum is a measure of indeterminancy in energy of what
energy it will have when it decays.
>I did not quantify it; I gave an estimate on the best order of the
>problem. How accurately can a counter measure a short interval of
>time?
Pretty damn accurately.
>If that is your definition, there is no such thing as a TRNG. The
>various sequences may be CLOSE to equiprobable, but no physical
>device is going to make them EXACTLY equiprobable.
I never said that they must be equiprobable in actuality, only that
the TRNG be capable in principle. As long as the actual sequneces that
are produced do not leak any information about possible imperfections
in the TRNG, then the OTP ciphers are proveably secure.
Am example will suffice. Let's say I generate many strings and use
them for OTP encryptions. And you attack my ciphers using probablistic
methods. Even if you are able to detect a small imperfection in my
ciphers, you will never know for sure whether that is just a
statistical anomoly, or a real effect. Yes, you will be able to put
confidence limits on it, but you will never be able to gain a
sufficient level of certainty as long as my TRNG is not too screwed
up.
Put in those terms, would you be willing to risk a global nuclear war
just because your statistical attacks on my ciphers uncovered the
*possibility* of a weakness in my TRNG? Of course not - you will want
more samples to make sure. So you get more samples, and your tests
indicate a little more confidence in your hypothesis. But you are
still not certain. So are you now gonna nuke the world, or collect
even more data?
Where does all this end - or put in different terms, when does this
Turing Machine ever halt?
>>If a TRNG is not capable of generating all possible strings
>>equiprobably, it is not a TRNG for purposes of secure crypto.
>It could do a very good job.
Not if it can be shown that it is not capable.
There is an important distinction in probability theory between that
which is possible and that which actually happens. Statistics can only
address that which actually happens, and can not address that which
could possibly happen. As soon as your statistical tests seemingly
uncover some anomoly, it can go away if you test more data. Your
statistical tests only produce confidence of probability one in the
limit of an infinte number. Statistical tests on finite numbers only
give confidence of probabilty less than one.
How much data would you need to certify that the data you have fails
to meet the criteria for crytographic security? 10^12 bits to get 1
part per million certainty? That's a lot of bits.
>A good criterion would be that the probability that a bit is 1, given
>all preceding bits, is small. The channel capacity for the one
>trying to read the message without the key is roughly proportional to
>the square of the bias, and channel capacity is only an asymptotic
>rate, rarely well approximated for reasonable length messages.
Everything in statistics is "rarely well approximated for reasonable
length numbers".
>For secure cryptography, there are strings which one would not want
>to use.
Not if you are using the only proveably secure cryptosystem, the OTP.
You cannot filter out ANY strings without destroying the proveable
security.
>Using a string which would enable the intercepter to have
>a good chance of guessing some or all of the message is something
>which should be avoided for cryptographic purposes.
I suspect you do not fully understand why the OTP crytosystem is
proveably secure, otherwise you would not be making that statement.
There are no such things as "good" and "bad" strings per se in the OTP
system. The presence of any string does not give the cryptanalyst any
"good chance of guessing...", since any and all possible strings are
equiprobable. That makes them indeterminancy, and therefore the
attacker cannot make any guesses that will work. Even if he guesses at
a key that decrypts to a completely intelligible message, there is no
reason to accept it as the intended message. All possible intelligible
messages are contained in the cipher.
Bob Knauer
"To compel a man to furnish contributions of money for the propagation
of opinions which he disbelieves is sinful and tyrannical."
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: RNG Product Feature Poll
Date: 7 Feb 1999 08:34:51 -0500
In article <[EMAIL PROTECTED]>,
Peter Pearson <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>>On Mon, 01 Feb 1999 08:05:08 -0600, in
>><[EMAIL PROTECTED]>, in sci.crypt
>>[EMAIL PROTECTED] (Dan S. Camper) wrote:
>>>[...]
>>>The data is generated a byte (8 bits) at a time. A particle detection
>>>interrupts the incrementing of a 16-bit register, running in the
>>>background. The high and low 8 bits of that register are XOR'd together
>>>to produce the output byte. The register is not reset between
>>>detections. I don't remember offhand if the register is seeded at zero
>>>when power is first applied or not. The device has been tuned so that the
>>>16-bit register cycles once (on average) between detections.
>>Having long thought this would be a good idea, I always assumed it was
>>common knowledge from the 60's. So it is with some irony and sorrow
>>that I propose claim 1 on page 23 of US Patent 5,627,775 granted 1997
>>May 6:
>>"We claim:
>> 1. A circuit for generating a nonreproducible, nonperiodic
>>sequence of values, comprising:
>> a noise source;
>> means for generating timing signals from the noise source;
>> an independent free-running multistate digital circuit having a
>> predetermined distribution of states; and
>> buffering means for storing states of the digital circuit at
>> random times in accordance with the timing signals."
>In 1955, the Rand Corporation published a book entitled "A Million
>Random Digits with 100,000 Normal Deviates," described at
>http://www.rand.org/publications/classics/randomdigits/.
>Today's online version doesn't mention radioactive decay, but I
>believe I recall that that was the basis for their "random frequency
>pulse source."
>So, don't let overbroad patent claims scare you....
The Rand numbers come from thermal noise. However, there are quite
a few papers and reports using radioactive decay. There is a rather
large Argonne file, with a corresponding report, going back quite a
few years, using radioactive decay; it uses the parity of the number
of counts in fixed intervals, which would be better than the method
suggested above.
I do not know if the use of the number of counts of the digital
process for a fixed number of noise events is published, but I
believe that using the time is, and analog time needs to be
digitized. Using the number of events in a fixed time is certainly
in papers and reports.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: What is left to invent?
Date: Sun, 07 Feb 1999 14:24:10 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 4 Feb 1999 06:32:18 +0000, Toby Kelsey
<[EMAIL PROTECTED]> wrote:
>>If you're referring, instead, to some sort of _accidental_ bias
>>towards intelligible plaintext, not concerning oneself with that is an
>>acceptable simplification in practice, to be avoided when - and if - a
>>cipher system is encountered where such a bias exists, and there is a
>>way to say something useful about it.
>I was considering a designed-in bias. It seems to me that if such a
>system was practicable the extra security would be worth the effort.
>The problem is designing a text compression method which understands
>enough of the structure, grammar and vocabulary of intelligible text to
>give close to optimal compression. It would therefore probably have to
>be language-specific, if not domain-specific. Even if it has an
>extensive vocabulary list it is distinct from a code since the
>compression method (part of the algorithm, not the key) could be
>publicly known.
>I would be interested to know if this approach has been tried.
I have a problem with using compression in the OTP cryptosystem.
Without compression, every possible intelligible message can be
decrypted from a given cipher equiprobably if you do not know the key.
Is that the case when compression is used, and the cryptanalyst knows
that you are using compression on the message before doing the OTP
encryption? IOW, does the use of compression destroy the proveable
security of the OTP system because it prevents all intelligible
messages from being in the ciphertext?
Does compression create a bias *away* from all possible intelligible
messages being decrypted?
Bob Knauer
"To compel a man to furnish contributions of money for the propagation
of opinions which he disbelieves is sinful and tyrannical."
--Thomas Jefferson
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Loony question
Date: Sun, 07 Feb 1999 14:41:51 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] () wrote:
>
>However, rather than make assumptions about the taste in music of
>cryptanalysts, one _is_ advised to use the numbers correctly, by using
>only the LSBs, hashing, and so on.
Actually, that brings up a question I always had -- if you are doing
hashing, why use only the LSBs?
For example, suppose your hash function is SHA1, and you are hashing
together 200 words [1] of data from the CD, why should you strip off
the LSBs, and present only the 200 LSBs to the hash function? Why
not present all 200N bits of data (where N is the word size) to the
hash function? After all, the full data has at least as much entropy
as the LSBs.
I realize that hashing all the data will be slower, however, I thought
that we were talking about the security of the system, not its
performance
[1] Or whatever units of data come off an audio CD -- I'm rather
ignorant about the mechanics of CDs
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Philip Koopman)
Subject: Re: Rolling code generators
Date: Sun, 07 Feb 1999 15:08:27 GMT
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] (Robert Scott) wrote:
>Can someone point me to a source for an academic treatment of
>rolling code generators?
I don't know of a good treatment that has been published.
There are some newer systems that are quite sophisticated. United
Technologies (a design I helped create) uses a multi-level non-linear
PRNG that is very secure given cost and operational constraints. You
can get the patent documenting the design from my home page.
Microchip sells a design they say is very secure, but the guts are a
secret so it fails the "snake oil" test.
I don't know of designs beyond these that are secure enough to be
interesting.
Phil Koopman -- [EMAIL PROTECTED] -- http://www.ece.cmu.edu/~koopman
------------------------------
From: Mr. Tines <[EMAIL PROTECTED]>
Subject: Re: Encryption Algorithms
Date: 06 Feb 1999 23:52 +0000
###
On Sun, 07 Feb 1999 01:05:15 +0200, in <[EMAIL PROTECTED]>
Asher Pressman <[EMAIL PROTECTED]> wrote.....
> Does anyone know of any good sites where i can find encryption
> algorithms? I've been looking for a while and i just can't find
> anything...
I've scavenged a lot of freely redistributable source, and
have 'C' and Java implementations of a whole bunch of standard
block cypher algorithms
http://www.windsong.demon.co.uk/ctclib2_1.zip has 'C'
source in the ctcalg/ folder; and
http://www.windsong.demon.co.uk/crypt.zip has Java source
in the uk.co.demon.windsong.crypt.cea package
Then there are the usual suspects like
ftp.replay.com/pub/crypto
ftp.hut.fi/pub
-- PGPfingerprint: BC01 5527 B493 7C9B 3C54 D1B7 248C 08BC --
_______ {pegwit v8 public key =581cbf05be9899262ab4bb6a08470}
/_ __(_)__ ___ ___ {69c10bcfbca894a5bf8d208d001b829d4d0}
/ / / / _ \/ -_|_-< www.geocities.com/SiliconValley/1394
/_/ /_/_//_/\[EMAIL PROTECTED] PGP key on page
### end pegwit v8 signed text
08672d006ee693d1ebbdea6ed7ccc8be0c2aa57af7f05dff865bd110c32c
d65c3d1bfb86c3fd45ab8926bfba10fa9e5556ae9a315d3977d9ffd2156e
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Sun, 07 Feb 1999 16:29:35 GMT
Reply-To: [EMAIL PROTECTED]
On 7 Feb 1999 09:35:58 -0500, [EMAIL PROTECTED] (Herman Rubin)
wrote:
>So a 10 megabyte file could be easily tested in such a way
>that one could be fairly sure that the deviation from randomness
>was at most 1%, and have good chance of acceptance if it was .1%.
I am still having a problem relating this "deviation from randomness"
you are testing for and the indeterminancy inherent in a TRNG. You are
claiming that a property for infinite numbers applies to finite
numbers, albeit with less than probability one.
The thing that really bothers me is that "good chance" part in your
statement above. If your tests are probabilistic with only a "good
chance" of being correct, then how can they be relied on?
For each test you require a RNG to pass, the builder of the RNG can
fake the numbers to pass your tests. Or do you know of a set of tests
that can *with absolute certainty* distinguish a faked RNG from a
TRNG?
Let me expand on that. It all starts when you come to me and tell me
you want a TRNG that will pass your tests. I ask to see your tests so
I can test my design for myself before turning the system over to you.
Also, I want to see if the tests are reasonable, so I do not waste my
time playing amateur games with twit tests.
But unbeknownst to you I am really a purveyor of Snake Oil Generators
(SOGs). I take your tests and program an algorithm to generate numbers
that will pass your tests, and put that algorithm in a black box so
you cannot see it. Even if I dude the black box up with lots of bells
ans whistles, I embed the algorithm in the silicon away from your
watchful eye. I tell you that the algorithm is used to "diagnose" the
SOG so it behaves as certified all the time.
[NB: This is very much like the standard proof of Turing's halting
problem.]
Later you come back and complain that the SOG won't pass additional
tests that raise your level of confidence, and I point out that you
got everything you wanted and paid for. But, since you are a nice
gullible customer, I will enhance your SOG for an additional fee, so
it will pass your new improved tests. The same scenario obtains until
I finally bilk you out of all your money.
You made the most fundamental mistake when you assumed that
statistical testing could certify a TRNG to within any arbitrary level
of precision. You cannot use deterministic algoritmic tests to certify
if numbers are being generated by an indeterministic process. You can
only use such tests to certify that the process is not deterministic.
Therefore you can not certify that you have a TRNG or a SOG. But that
determination is crucial to producing ciphers that are proveably
secure.
Bob Knauer
"To compel a man to furnish contributions of money for the propagation
of opinions which he disbelieves is sinful and tyrannical."
--Thomas Jefferson
------------------------------
From: "PAC" <[EMAIL PROTECTED]>
Crossposted-To: sci.philosophy.meta,sci.physics,sci.skeptic
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: Sun, 7 Feb 1999 08:33:05 -0800
R. Knauer wrote in message <[EMAIL PROTECTED]>...
>On Sat, 6 Feb 1999 19:30:14 -0800, "PAC" <[EMAIL PROTECTED]> wrote:
>
>> I didn't really want to get into this type of discussion and take away
>>the tone of this thread, but what we percieve is really out there, but
from
>>one aspect, to know it in its entirety means to be merged 100% into an
>>object and with that object. Since we are never at that situation, a
>>separation still exists regardless of what percieved.
>
>Quantum Mechanics prevents complete knowledge of an object, merged or
>separate.
True, QM could be the basis for the above statement of separation, or
vice-versa.
Phil C.
------------------------------
** 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
******************************
