Cryptography-Digest Digest #132, Volume #9 Wed, 24 Feb 99 15:13:03 EST
Contents:
Re: Pentium III Hardware Random Numbers (Herman Rubin)
Re: Testing Algorithms (Steven Runyeard)
Re: True Randomness (Patrick Juola)
Re: Define Randomness (Patrick Juola)
Re: Testing Algorithms ("Vegeta-the original Super Saia-jin")
Re: Testing Algorithms (R. Knauer)
Re: True Randomness (R. Knauer)
Re: Testing Algorithms (R. Knauer)
Re: Standard fileheaders for encrypted files (John Savard)
Re: Block cipher in the smallest PIC (Paul Rubin)
Re: Testing Algorithms ("Tim Woodall")
Re: Testing Algorithms (R. Knauer)
Re: Another extension to CipherSaber (Darren New)
Re: What do you all think about the new cipher devised by a 16 year old? (Jim
Gillogly)
Re: Block cipher in the smallest PIC (Medical Electronics Lab)
Re: Define Randomness (Alan DeKok)
Re: Pentium III Hardware Random Numbers (R. Knauer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Pentium III Hardware Random Numbers
Date: 24 Feb 1999 10:38:33 -0500
In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Earlier, there was a post speculating that the Pentium III might use a
>technique described in a recent Intel patent to generate random numbers,
>based on oscillator drift, which would not be good.
>I recently saw an item (was it in Wired? Computerworld?) that says that
>Intel is going to use thermal noise in the chip. This, of course, is a
>much better technique for quality randomness. And it confirms that this
>feature is to be present - until this report, I had seen nothing about
>this feature except in Usenet posts, which could be rumors.
I cannot see thermal noise as a good source for randomness. The
problem is that the physical parameters are not constant, and thus
there is a moderate amount of variation. This may be low enough
for cryptographic uses, but I would not trust it for the large
simulations in various fields, where a small amount of bias or
dependence can be important.
--
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] (Steven Runyeard)
Subject: Re: Testing Algorithms
Date: Wed, 24 Feb 1999 16:46:38 GMT
>And your basis for believing this is...?
My basis is the achievements of mankind so far. In all forms of
technology there has been a stready improvement. I can't image there
will come a time when all the scientists say "that's it, we know
everything there is to know". You base your beliefs on current
knowledge whereas I'm prepared to believe that there are far more
interesting discoveries to come.
Steve
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: True Randomness
Date: 24 Feb 1999 10:59:34 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 24 Feb 1999 08:58:37 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>
>>Um, Li and Vitanyi doesn't have everything about probability theory;
>
>Um, Li & Vitanyi's book most certainly has a considerable amount about
>probability. In fact, they assert that Kolmogorov's theory is all
>based on probability theory.
Yes... but it doesn't have *everything* about probability theory.
That's the point. It's a specialist book, but not a compendium of
All That is Known, or even All That Is Known About Probability.
Would that it were; my library would be considerably smaller, lighter,
and easy to pack.
Or, more formally, there exist facts and theorems in probability
theory that are not addressed in Li and Vitanyi's book. Proof is
immediate by inspection of the library shelves *near* Li/Vitanyi. 8-)
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Define Randomness
Date: 24 Feb 1999 11:02:38 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 24 Feb 1999 09:23:07 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>You're confusing generator skew with sequence skew again.
>
>I do not believe so, not in the context of crypto-grade random
>numbers.
>
>>The point is that a *generator* can be skewed (I prefer the term
>>'bias', but they're largely equivalent) and still be random.
>
>>As an example : suppose I have a bit-generator that works like this :
>>I roll a die ("randomly") and output a zero if the result is a six,
>>a one otherwise.
>
>>This isn't a very good generator (it's biased), but it's still
>>random. And the entropy of this generator is less than the entropy
>>of a generator consisting of a fair coin.
>
>That generator is not crypto-grade random. If you used keystreams from
>that RNG you would leak significant amounts of information.
No, but it's "random." The von Neumann/Knuth pairwise transform would
remove the bias and make it acceptable.
The point of the original poster being, of course, that a "random"
stream need not be an "unbiased random" stream.
-kitten
------------------------------
From: "Vegeta-the original Super Saia-jin" <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Date: Fri, 19 Feb 1999 01:51:57 -0500
No, in that all forms of cryptography have finite life span and no matter
how strong they can be defeated in time.
As far as speed goes, the faster the processor the faster the algorithm
As far as security goes, key length helps, but it won't make it secure, I
think that DES proves that, it's a joke, and a bad one at that.
As far as size goes with the advent of multigigabyte hard drives, and
staggering amounts of RAM . . . size in most cases isn't a factor, My
father could tell you what the ARPA had to use when the CIA would send them
the captured Soviet codes. (This is before the NSA was truly defined as a
cloak and dagger agency.)
But to quote the creator of PGP, "I will never say anything I make is
totally secure."
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Testing Algorithms
Date: Wed, 24 Feb 1999 16:54:25 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 24 Feb 1999 07:14:31 +0100, fungus
<[EMAIL PROTECTED]> wrote:
>You're saying "computers got faster before, they'll get faster again".
>This is just idle thought and handwaving. What is the basis for your
>belief?
In the early days of automobiles there was exponential growth in
certain performance and cost factors. But later those factors later
reached a plateau.
It is projected that by the year 2020, circuits will be the size of
individual atoms, which is ludicrous from a classical computing point
of view. Long before that happens, classical computer circuits will
reach their inherent plateau. Just look for the S-curve to emerge.
Bob Knauer
"Democracy is the theory that the common people know what they
want, and deserve to get it good and hard."
--H.L. Mencken
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness
Date: Wed, 24 Feb 1999 16:57:08 GMT
Reply-To: [EMAIL PROTECTED]
On 24 Feb 1999 10:55:33 -0500, [EMAIL PROTECTED] (Herman Rubin)
wrote:
>>>It is not usual to have statistical terms in a probability book, although
>>>maximum likelihood might be found there.
>>>Hidden Markov models are far too recent to be in Feller's book.
>>>And even later probability textbooks might not have this.
>>What book(s) do you recommend for these two concepts?
>Any reasonable statistics book discusses maximum likelihood, among
>other methods of inference.
>As for hidden Markov models, one is only likely to find applications.
>The idea that what is observed is a function of an unobserved Markov
>chain is simple to state, and can be quite difficult to work with.
Ok, let me ask it again. If you were teaching these two concepts in a
university course, and only these two concepts as they relate to our
discussions on randomness here, what one or two books at most would
you be using for the course?
I am looking for specific recommendations, focused on the issues at
hand.
Bob Knauer
"Democracy is the theory that the common people know what they
want, and deserve to get it good and hard."
--H.L. Mencken
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Testing Algorithms
Date: Wed, 24 Feb 1999 17:05:39 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 24 Feb 1999 16:46:38 GMT, [EMAIL PROTECTED]
(Steven Runyeard) wrote:
>My basis is the achievements of mankind so far. In all forms of
>technology there has been a stready improvement. I can't image there
>will come a time when all the scientists say "that's it, we know
>everything there is to know". You base your beliefs on current
>knowledge whereas I'm prepared to believe that there are far more
>interesting discoveries to come.
The automobile is a perfect example of a technological system that has
not advanced much at all since the early days of its invention. There
have been some performance innovations in race car technology, but
they are not exponential in nature.
The only innovations in the auto industry have been in the marketing
area, where the goal is to screw the maximum number of people into
buying the least reliable products for the greatest amounts of profit.
Only the federal govt has surpassed the auto industry in screwing
people on a routine policy basis.
Bob Knauer
"Democracy is the theory that the common people know what they
want, and deserve to get it good and hard."
--H.L. Mencken
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: talk.politics.crypto
Subject: Re: Standard fileheaders for encrypted files
Date: Wed, 24 Feb 1999 16:55:02 GMT
Kiril Kesarev <[EMAIL PROTECTED]> wrote, in part:
>Encryption
>algorithms
>generally allow any input sequences.
Yes, but Triple-DES is as hard to crack as Single-DES if one has known
plaintext at each individual level - thanks to known, but not
necessarily standardized, headers.
John Savard (teenerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Block cipher in the smallest PIC
Date: Wed, 24 Feb 1999 17:12:42 GMT
In article <[EMAIL PROTECTED]>, Robert Scott <see text> wrote:
>I have an application in remote keyless entry that,
>for economic reasons, favors the use of the smallest
>PIC processor: the 12C581. It has only 32 bytes of
>RAM and 512 words of program. Although the stakes are
>not as high as in electronic funds transfer, still I
>wanted to see if I could implement an 8-byte block
>cipher as secure as DES. I know DES has been implemented
>on larger PICs, but we just don't have the room to
>do it in this one. One thing we do have plenty of is
>time. So I have designed a 32-round cipher that can be
>implemented using only 110 instruction words (which includes
>a 64-byte key-dependent lookup table) and 9 bytes of RAM.
I'm skeptical of whether your cipher is as secure as DES, because
of its slow rate of diffusion.
Why don't you take a look at the GOST block cipher in AC2?
It's slightly more complicated than your cipher, but should
still fit in the PIC, and has been around for a while and
withstood some cryptanalysis.
If you have a little more program space available you could
try Skipjack. That's a very simple cipher but needs a 256-byte
F-table (in rom). There's a PIC implmentation available
through www.brouhaha.com/~eric.
------------------------------
From: "Tim Woodall" <No Spam [EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Date: Wed, 24 Feb 1999 17:24:30 -0000
Patrick Juola wrote in message <7b107g$q5l$[EMAIL PROTECTED]>...
>In article <[EMAIL PROTECTED]>,
>Tim Woodall <No Spam [EMAIL PROTECTED]> wrote:
>>
>>Steven Runyeard wrote in message
<[EMAIL PROTECTED]>...
>>>Someone wrote:
>>>>There's no garantee that this growth rate will continue. In fact
>>>>everything points to the opposite.
>>>
>>>No, there is no quarantee of this. There is also no quarantee that the
>>>speed of light will be a barrier.
>>
>>You really don't understand how big 2^256 is.
>>
>>Consider a computer consisting of a single water molecule.
>>Consider that this computer can test 10^9 keys per second.
>
>Why 10^9? As long as we're making silly assumptions, I'm going
>to assume that it can test 10^80 keys per second.
>
>Why is your assumption less silly than mine?
>
> -kitten
10^9 was a mistake (sorry :-). 10^18 was what I was intending, being the
time taken for light to cross a distance comparible to the size of the water
molecule. This removes the black hole problem if you want to crack the key
in one second but that was arbitrary anyway. Cracking a key in 10^18 seconds
(current age of the universe) would be more reasonable requiring a computer
of sides 10^6m or about the size of the moon.
So now we have it. The moon was created by the mice to crack a 256 bit key.
Watch out for the Vogons who ought to be near :-)
Tim.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Testing Algorithms
Date: Wed, 24 Feb 1999 17:59:53 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 24 Feb 1999 17:24:30 -0000, "Tim Woodall" <No Spam
[EMAIL PROTECTED]> wrote:
>So now we have it. The moon was created by the mice to crack a 256 bit key.
>Watch out for the Vogons who ought to be near :-)
I always thought the Moon was created to synchronize women's menstrual
periods, so primitive hunters would all know to come home at the same
time to make babies.
Bob Knauer
"Democracy is the theory that the common people know what they
want, and deserve to get it good and hard."
--H.L. Mencken
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Another extension to CipherSaber
Date: Wed, 24 Feb 1999 18:11:13 GMT
> Trying to narrow design standards for crypto to meet ever more-restrictive
> criteria results in the ultimate end of having only one crypto algorithm
> that can meet them; this is exactly what some want to happen, and to be
> sure that it is a appropriately crippled product to boot.
We're not talking about crypto algorithms here. We're talking about
ASCII armoring algorithms. I see no possible reason why you'd want
everyone inventing their own ASCII armoring algorithms just for
arbitrary divergence.
There's a good reason for lots of different crypto algorithms, but none
of those reasons apply to making binary go thru email.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"Be.... the email."
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: What do you all think about the new cipher devised by a 16 year old?
Date: Wed, 24 Feb 1999 10:42:32 -0800
fungus wrote:
> It's still a secret, until the "patents go through".
> ...
> Another mystery is that a patent is being applied for when (according
> to the press) the girl in question says she's not interested in making
> money from it. Something doesn't add up...
Specifically, she was quoted in the press as saying:
SF> My project is mainly about maths. Patenting
SF> maths doesn't help anyone to move science on.
She was also considering writing it up for Crypto '99: those papers are
generally kept under wraps as well. I'd be disappointed to hear she'd
taken advice to get it patented against her stated viewpoint above.
--
Jim Gillogly
4 Rethe S.R. 1999, 18:37
12.19.5.17.9, 10 Muluc 2 Kayab, Seventh Lord of Night
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Block cipher in the smallest PIC
Date: Wed, 24 Feb 1999 12:30:22 -0600
Robert Scott wrote:
> Here it is in pseudo-code:
>
> i = 64;
> do
> {
> B0 += ftab(i); i--;
> B4 ^= ftab(B0);
> B5 += ftab(B1);
> B6 ^= ftab(B2);
> B7 += ftab(B3);
> B4 ^= ftab(i); i--;
> B0 += ftab(B5);
> B1 ^= ftab(B6);
> B2 += ftab(B7);
> B3 ^= ftab(B4);
> Taking B7...B0 as a single 64-bit quantity,
> rotate it right one bit, with B0,lsb going to B7,msb;
> } while(i>0);
>
> where the ftab() function is table lookup modulo 64:
>
> byte ftab( byte x )
> {
> return KeyTable[ x & 63 ];
> }
>
> The KeyTable[] is the expanded key, burned in ROM in the
> transmitter. Assume the key expansion algorithm takes an
> 8-byte raw key and recursively applies DES 8 times using
> the all zeroes DES key. The resulting 64 bytes becomes the
> KeyTable[]. We don't need to do key expansion in the PIC
> since that is done when the transmitter is made. The
> receiver is "programmed" by putting the transmitter in a
> mode that causes it to dump out its 64-byte expanded key.
> Keys are changed by throwing away the old transmitter
> and programming a new one.
The function is probably good enough for what you are doing.
But you may want to look for small cycles - situations where
the bytes just flip to specific values in the internal B array.
The other thing I'd change is the use of DES. Replace that
with a hash function.
At any rate a good way to test it is to compare a lot of input
to output samples running on a PC simulator. run the outputs
thru a statistics package and see how well scrambled they are
compared to the inputs. If you see any patterns at all, just
try changing the order you do things, or add more rounds by
cycling up in "i" then back down again.
> If anyone can find a more secure algorithm that can
> be implemented using no more RAM and ROM than I used
> above, I would certainly like to hear about it.
Looks like a fun challenge :-)
Patience, persistence, truth,
Dr. mike
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
fillerfillerfillerfillerfillerfillerfillerfillerfillerfillerfiller
------------------------------
From: [EMAIL PROTECTED] (Alan DeKok)
Subject: Re: Define Randomness
Date: 24 Feb 1999 15:19:10 -0500
In article <7b14dd$qb9$[EMAIL PROTECTED]>,
Patrick Juola <[EMAIL PROTECTED]> wrote:
>In article <7b13hs$[EMAIL PROTECTED]>,
>Alan DeKok <[EMAIL PROTECTED]> wrote:
>>
>> And from Chaitin, there is no one method by which to determine the
>>difference between a PRNG and a TRNG. So *any* tests are necessarily
>>incomplete.
>
>Possibly incomplete. But the incompleteness is largely theoretical
>when you're talking about design analysis.
*necessarily* incomplete. You point this out below, where you
state:
>It's reasonable to claim that "an indistinguishable difference
>doesn't make a difference." But you can't then go on and define
>an acceptable set of methods for distinguishing.
That's what I said, in different words.
>There's a big difference between inspecting the design of a generator
>and examining only the output sequences produced by a generator.
Oh, of course. However, the set of methods/tests for distinguishing
PRNG from TRNG also includes methods of analyzing the design of
generators, so you're stuck. :)
That being said, it's a lot easier to analyze algorithms than huge
bit streams.
Alan DeKok.
--
"Thus we can conjecture that Special Relativity may ultimately be derived from
a simpler and more fundamental principle of _Conservation of Computational
Resources_." - Complexity, Entropy, and the Physics of Information, p. 315.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Pentium III Hardware Random Numbers
Date: Wed, 24 Feb 1999 19:32:13 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 24 Feb 1999 19:11:40 GMT, [EMAIL PROTECTED] (Robert Scott) wrote:
>Given a source of randomness that exhibits some bias, it is
>always possible to reduce the bias as much as you like provided
>you are willing to sacrifice speed. For example, take 100 biased
>bits and produce a single output bit depending on the parity of
>the 100-bit number.
As the bias increases, the speed decreases. You cannot anti-skew a
completely biased output.
Bob Knauer
"Democracy is the theory that the common people know what they
want, and deserve to get it good and hard."
--H.L. Mencken
------------------------------
** 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
******************************
