Cryptography-Digest Digest #134, Volume #9 Wed, 24 Feb 99 20:13:04 EST
Contents:
Re: Pentium III Hardware Random Numbers (Terry Ritter)
Re: Pentium III Hardware Random Numbers ([EMAIL PROTECTED])
Cryptographer's Calculator (Steve)
Re: Testing Algorithms ("Trevor Jackson, III")
Re: Testing Algorithms ("Trevor Jackson, III")
Re: Pentium III Hardware Random Numbers (Terry Ritter)
Re: Testing Algorithms ("Trevor Jackson, III")
Re: Block cipher in the smallest PIC (Robert Scott)
Re: Define Randomness (Terry Ritter)
Re: Pentium III Hardware Random Numbers (Terry Ritter)
Re: Define Randomness (Terry Ritter)
Re: Define Randomness (Patrick Juola)
Re: Define Randomness (Terry Ritter)
Re: Define Randomness (Alan DeKok)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Pentium III Hardware Random Numbers
Date: Wed, 24 Feb 1999 22:10:27 GMT
On Wed, 24 Feb 1999 19:32:13 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (R. Knauer) wrote:
>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.
"Completely biased?" Well, if the generator produces a *constant*
output, we will certainly have a hard time removing that "bias."
But *if* we have different-valued results, and *if* each result is
largely independent of each other result, it seems to me that even a
heavily-biased source can be processed into fewer but nevertheless
unbiased results.
The correct way to do this is to use the independence of each result
to select between state alternatives in a limited amount of internal
state. By doing many such selections, thus accumulating far more
"entropy" than is retained by the internal state, we can assure that
every possible state value has an equal probability of being selected,
which is a lack of bias.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Pentium III Hardware Random Numbers
Date: Wed, 24 Feb 1999 21:19:15 GMT
Is there some compelling reason why we should trust Intel?
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Steve)
Subject: Cryptographer's Calculator
Date: Wed, 24 Feb 1999 13:50:08 -0800
Hello,
Just to let everyone know about our new calculator
tool for cryptographers:
CypherCalc is a full-featured, programmable calculator
designed for multi-precision integer arithmetic. You
can use CypherCalc to perform "big number" math
operations such as exponentiation, modular
multiplication, and Montgomery products.
CypherCalc is a great time-saver for those who work in
the fields of Cryptography and Cryptanalysis. It is
intended for use in the design and testing of
cryptographic algorithms involving key exchanges,
modular exponentiation, modular inverses, and
Montgomery Math.
CypherCalc can save countless hours of program
development time by providing a reliable source of
known answers. You can check your algorithms against
CypherCalc's results in seconds. Also included is a
simple scripting language that allows you to automate
repetitive calculations and algorithms.
Details for CypherCalc (including screen shots) are at
www.cyphercalc.com or contact us by email at
[EMAIL PROTECTED]
We would welcome any comments or suggestions you might
have for making CypherCalc more useful to
cryptographers.
Regards,
Steve
EPS/Solutions
===========================
*** Posted from RemarQ - http://www.remarq.com - Discussions Start Here (tm) ***
------------------------------
Date: Wed, 24 Feb 1999 16:56:28 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Steven Runyeard wrote:
> >No. The guess is only as valid as the assumptions it is based upon.
> >Since you have based yours on nothing concrete, your guess is pretty
> >useless.
>
> I don't agree. Because we are brought up in an environment with a
> certain level of technology it's hard to imagine anything much
> different. Let's look back at the technology surrounding Babbage in
> the late 1800s. If anyone had suggested to him that within 100 years
> someone could build a processor about an inch square that could
> perform 2,000,000,000 instructions per second he would have sent them
> to the nearest nut house. It would have taken a massive leap of faith
> to believe it was possible. I feel that in another 100 years we would
> have made an equally 'unbelievable' leap in technology. Don't limit
> your thinking to the size of computers the size of melecules and
> atoms. What about a computer made of super strings? Maybe even
> smaller. Who knows? The point is we don't know what lies ahead of us.
> My guess is no more worthless than yours.
As we project farther into the future the "worth" of a guess approaches
zero very quickly. However, your historical analogy does not consider
one critical distinction, that being technology versus science. If we
forsee technological limits such as the resolution limit to UV
lithography, these should be ignored because we must assume new
technologies will continue to be developed. In fact, technology
projection is famously flawed for timidity rather than aggressiveness.
For a reference see Heinlein's 1950, 1965, and 1980 projections. They
were analyzed in "Expanded Universe" I think.
Scientific limits are a different issue. If we project computation
speeds based on the current model of reality we will hit limits such as
the Plank length, speed of light, and the number of particles available
in the observable universe. Projections that stay within the known
scientific limits are of a different class than those that violate those
limits.
A superstring computer is certainly conceivable with modern theory, given
some room for TBDs in the specs. But a computer that violates the speed
of light is in the same class as divine inspiration. If you assume any
rules you want then you can get any output you want. By tomorrow. These
assumption are certainly possible in that revolutions in our view of
reality do happen (relativity and quantum physics being examples).
However, postulating a scientific revolution undermines the value of the
projection of future capability.
A simple example is that controlled transmutation would solve the world
hunger problem. So what? We've come far in the last 30 years toward
solving that problem without ridiculously powerful technologies. Making
the assumption does not help in analyzing our expectation about future
capabilities because you might as well wish for it to happen tomorrow or
in 1e100 years as in 100 years.
------------------------------
Date: Wed, 24 Feb 1999 16:59:13 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>,
> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> >Steven Runyeard 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 are basing your calculations on the assumption that CPU speeds
> >> will stop increasting. So far the trend has been a doubling around
> >> every 1.5 years. I remember back in 1985 being told that my 1 MIP CPU
> >> is about as fast as we can possible get because of 'physical
> >> barriers'. Today we have CPUs that can run 2,000 times faster. Have we
> >> got to that barrier yet? No, I don't think so.
> >>
> >> This whole thing comes down to speculation. As far as you're concerned
> >> we are going to reach a ceiling in computer performance. I, on the
> >> other hand think we will not. If there is money in it Intel will find
> >> a way of making a faster CPU.
> >>
> >> It's your guess that we won't crack a 256 bit key. It's my guess that
> >> we will. Each guess is just as valid.
> >
> >No. The guess is only as valid as the assumptions it is based upon.
> >Since you have based yours on nothing concrete, your guess is pretty
> >useless. If you specify any level of technology less than divine you will
> >find limits. Those limits will control the size of a key that can be
> >broken with that technology in a reasonable amount of time.
>
> On the other hand, if you specify any length of technology less than
> divine, you run a grave risk of finding technology outstripping
> your specifications.
Agreed. technological prognostication is famous for its timidity. But I see a
difference between tech limits and scientific limits on which I commented in a
different thread. Projections based on scientific revolutions are as useful as
projections based on divine interference.
>
>
> I don't think there's a clear cut "smart" set of specifications.
>
> -kitten
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Pentium III Hardware Random Numbers
Date: Wed, 24 Feb 1999 22:10:22 GMT
On 24 Feb 1999 10:38:33 -0500, in <7b16dp$[EMAIL PROTECTED]>, in
sci.crypt [EMAIL PROTECTED] (Herman Rubin) wrote:
>[...]
>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.
Well, we can't expect to use the noise directly. Even sampling the
noise directly for bits is unlikely to be unbiased. But this does not
mean that noise values do not have substantial independence. And when
we have independence, we can mine it.
>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.
I would say that it is the responsibility of the machine, or other
post-processing, to remove that bias.
As I recall you have several times mentioned the use of bit-distance
in an unbiased bit sequence to form desired distributions. I wonder
if you could expand on that here. A tutorial reference would be
ideal, but any references or articles on this would be helpful.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Date: Wed, 24 Feb 1999 17:04:34 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Bauerda wrote:
> >On the other hand, if you specify any length of technology less than
> >divine, you run a grave risk of finding technology outstripping
> >your specifications.
>
> Then why don't we throw in another variable. What is the probablitity that a
> short, randomly generated string will make a readable and probable message? Or
> that a randomly generated message will correctly decompress using a standard
> (or specified) compression algorithm? And if an enemy has that much computing
> power, maybe they should see if they can get Asimov's psycho-history to work
> and simply predict what your message said.
Nah. Knowing the enemy was predicting one's behavior influences that behavior in
ways that produce an undecidable Godelian condition.
On the other hand, projections of e/n/o/r/m/o/u/s fantastic technological power may
influence the need for secrecy. As our economy transitions from one of scarcity to
one of abundance it may become less important to hide things. Given a civilization
capable of enumerating the integers up to 2^1000 they may not *care* who knows
what.
------------------------------
From: [EMAIL PROTECTED] (Robert Scott)
Subject: Re: Block cipher in the smallest PIC
Reply-To: see text
Date: Wed, 24 Feb 1999 23:11:10 GMT
On Wed, 24 Feb 1999 20:51:55 GMT, [EMAIL PROTECTED] (Paul Rubin) wrote:
>In article <[EMAIL PROTECTED]>, Robert Scott <see text> wrote:
>>On Wed, 24 Feb 1999 17:12:42 GMT, [EMAIL PROTECTED] (Paul Rubin) wrote:
>>>I'm skeptical of whether your cipher is as secure as DES, because
>>>of its slow rate of diffusion.
>>
>>DES is actually slower (relative the the number of rounds).
>>DES takes 5 of the 16 rounds to completely diffuse every input
>>bit to potentially every bit in the left and right 32-bit halves.
>>My cipher takes 7 rounds of the 32 total rounds for complete
>>diffusion. 7/32 < 5/16.
>
>Look what happens in your cipher if two inputs differ only
>in the 2nd-to-highest bit in some byte. I think you should
>change your F function to depend on all the bits in the byte.
Yes, I realize that those high bits won't propagate until
they get shifted into bits 0-5, but the application limits
the size of the f-table I can use. That is why I have opted
for more rounds, since time is not a factor in my application.
>>BTW, as David Wagner pointed out to me, the key expansion algorithm
>>that I proposed would be much better if I didn't use the
>>all-zeroes DES key, since that key results in a repeat in my key
>>schedule every 16 bytes, using recursive DES encryption of the
>>raw key. So assume any other fixed DES key.
>
>Yes, the all-zero and all-one DES keys are weak in this sense.
>There are some other semiweak keys as well.
>
>Better IMO would be to DES-encrypt a fixed string using your cipher
>key as the DES key, rather than encrypting your cipher key with a
>fixed DES key. That way, figuring out some bits of the F table
>doesn't give you as big a foothold toward figuring out the rest
>as your current scheme does.
Yes, I'll do that. Thanks.
Bob Scott
Ann Arbor, Michigan (email: rscott (at) wwnet (dot) net )
(My automatic return address is intentionally invalid.)
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Define Randomness
Date: Wed, 24 Feb 1999 23:05:56 GMT
On Wed, 24 Feb 1999 22:00:03 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (R. Knauer) wrote:
>[...]
>Now here's the question for you - do these anti-skewing procedures
>introduce correlations into the keystream? After all, they are
>algorithmic, which means they produce a pattern.
"Algorithmic" does not mean "produces a pattern." The result of
algorithmic filtering is knowable in principle if the input is known.
But if the input is *not* knowable, with independent values, there may
*be* no pattern from the output.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Pentium III Hardware Random Numbers
Date: Wed, 24 Feb 1999 23:06:09 GMT
On Wed, 24 Feb 1999 21:19:15 GMT, in
<7b1qca$akc$[EMAIL PROTECTED]>, in sci.crypt [EMAIL PROTECTED]
wrote:
>Is there some compelling reason why we should trust Intel?
Nope. No more than we would trust, say, Schneier.
The issue is not the source of the argument, but rather the argument
itself. There are technical objections (which have nothing to do with
conspiracies) to what we think is the Intel design.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Define Randomness
Date: Wed, 24 Feb 1999 23:05:35 GMT
On Wed, 24 Feb 1999 21:29:43 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (R. Knauer) wrote:
>On Wed, 24 Feb 1999 20:54:51 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>
>>>You need an unbiased generator for it to be crypto-grade random.
>
>>But that can be understood in misleading ways. In particular, the
>>original "generator" *can* have bias in its output, and yet *can* be
>>used for crypto, *provided* the output is "processed" to remove the
>>bias.
>
>Two comments:
>
>1) Such anti-skewing processing must be included in the overall
>specification of the TRNG for it to be a genuine TRNG, so we are back
>where we started, namely:
>
>"You need an unbiased generator for it to be crypto-grade random".
It is necessary to distinguish between the generator and the output to
be able to measure the raw generator itself. It is only by measuring
the raw generator that we can convince ourselves that it really is
such a generator.
If that means you need to modify your definition, then so be it.
>2) I have not been convinced that anti-skewing does not introduce
>correlations, which would make the output unsuitable for crypto-grade
>ciphers. After all, the anti-skewing procedure is algorithmic, so
>there is always the opportunity to introduce correlation(s).
The von Neumann method is "algorithmic." So the issue is not
algorithmic per se, but rather the particular algorithm, and the
independence of the input values.
>The von Neumann method looks innocent on the surface since the
>probability of dibits 01 and 10 are the same, namely p*(1-p). But that
>says nothing about the correlations inherent in their appearance.
The von Neumann method does nothing about longer-range correlations.
If you are willing to assume such do not exist, then you can use the
simple algorithm. But then there is "always the opportunity" for
longer-range correlations to exist unhandled.
>If
>you start throwing out bits like in the von Neumann method, who knows
>what patterns are left behind.
If they are "left behind," who cares?
>>It would not be correct, for example, to say that a crypto-grade
>>generator must *inherently* produce an unbiased output. While that
>>might be convenient, I doubt that any physical machine -- even
>>measuring the ideal flat source -- could produce a sufficiently flat
>>distribution in practice. So the output from physical generators
>>generally must be post-processed before use.
>
>I fully agree. A bias-free TRNG is an idealization, just like a
>(perfect) circle is an idealization. But that does not imply that
>algorithmic anti-skewing procedures should be used to fix a poorly
>implemented TRNG design.
What "anti-skewing" procedures would you call *not* algorithmic?
>You don't run eccentric wheels on axles that are shaped like a crank,
>just to compensate for the eccentricity.
We also cannot trust as ideal those things which are measurably not.
Surely we should do what we can to make them as ideal as possible.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Define Randomness
Date: 24 Feb 1999 14:43:53 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 24 Feb 1999 11:02:38 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>BTW, what happens to the randomness of your number generator as the
>bias approaches unity? You started out with a bias of 5:1 with a
>standard die. How random is your number generator if the die has 1,000
>sides, and you use only one of the faces of that die for the 1 bit and
>all the rest for the 0 bit?
Well, assuming you're rolling this K-sided golf ball randomly, then you'll
get a one with (expected) probability 1/K and a zero with (expected)
probability 1-1/K. Shannon's formulation for entropy applies
(it's a stationary ergodic source), and you can calculated the
entropy of the system as
(1/K * -lg(1/K)) + (K-1)*lg(1-1/K)
Elementary analysis reveals that this is everywhere positive but
goes to a limit of zero as K tends to infinity.
>In the limit as the number of sides grows unboundedly large, the bias
>approaches unity, which means that your generator puts out all zeros.
>Yet the claim is that it is still a random number generator, albeit
>not for purposes of crypto.
But for any finite number of sides, it will not output all zeros.
Trying to project properties obtained in the finite case to properties
of the limiting case is fraught with peril; in this case, I'll cheerfully
accept that the limiting case of a K-sided golf ball with only one
1 and the rest 0 isn't really a 'random number generator'.
>Li & Vitanyi make the point that any true random number must be normal
>in the Borel sense, which means that there can be no bias whatsoever.
>Of course, Borel normality is a property of infinite numbers, but we
>can handle that by applying it to the generator itself for finite
>strings.
>
>Therefore in order for a TRNG to be *capable* of outputting a normal
>number, it cannot have any bias in its implementation.
This is simulaneously both true and false, depending on how you look
at it.
My finite K-sided golf ball is *capable* of outputting a normal number;
it just does so, in the infinite case, with probability zero. Arguing
about whether something that can happen -- but only does so with
probability zero -- is something that is really capable of happening
is one of those pointless arguments better left for philosophers in
need of pointless publications.
But yes, in general, a uniform generator and only a uniform generator
will output a normal number.
Problem : Li & Vitanyi state (p. 158, p. 3) that "it is universally
agreed that a random infinite sequence must be normal." Well, bluntly,
it ain't so, guys. There's lots of random infinite sequences that
aren't normal. This paragraph counts as one that, most kindly, they
oversimplified.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Define Randomness
Date: Wed, 24 Feb 1999 23:05:42 GMT
On Wed, 24 Feb 1999 22:06:21 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (R. Knauer) wrote:
>[...]
>But, I do not trust algorithmic post processing. You will have to
>convince me that anti-skewing does not introduce unwanted correlations
>which can wreck the security of the TRNG significantly.
I would say that you have to consider whether any valid alternate
approach exists.
Can we run a TRNG without post-processing? That would be one
alternative, but I doubt it is viable.
And if not, exactly what sort of post-processing would you say is
*not* algorithmic?
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Alan DeKok)
Subject: Re: Define Randomness
Date: 24 Feb 1999 19:51:24 -0500
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>
>On 24 Feb 1999 09:49:32 -0500, in
><7b13hs$[EMAIL PROTECTED]>, in sci.crypt
>[EMAIL PROTECTED] (Alan DeKok) wrote:
>
>>[...]
>>Q: When is an algorithmic PRNG identical to a TRNG?
>>
>>A: They're identical when you are unable to distinguish the two.
>
>That's true as far as it goes. And it goes exactly as far as the
>first test which *will* distinguish the two.
Any bets as to how long it will be before anyone discovers just such
a test? :)
>When we use a PRNG we *know* that a relatively small amount of
>original uniqueness creates the sequence we see. What we *don't* know
>is whether our clever Opponents can use the sequence to define the
>hidden information, and then extrapolate the rest of the sequence.
Like physics. An ensemble of particles has a finite number of
states, and can thus be characterized and predicted.
>So if a physical RNG actually contains a large, hidden, unknown and
>presumably unknowable internal state (or even a supernatural arbitrary
>randomness), to penetrate it our Opponents will have to be not only
>much sharper than we might think, but also much sharper than we can
>imagine anyone being.
I think that's the crux of the matter. (I'm starting soon on "The
physics of Fisher Information". Deriving physics from information theory.)
There is physical information which is *unknowable*, and thus can
safely be used to generate unpredictable random numbers.
In contrast, PRNG's can have their state be *known*, and
*completely* known.
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.
------------------------------
** 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
******************************
