Cryptography-Digest Digest #64, Volume #9 Wed, 10 Feb 99 11:13:03 EST
Contents:
RSA Cryptography Today FAQ (1/1) ([EMAIL PROTECTED])
Re: RNG Product Feature Poll (Herman Rubin)
Re: What is left to invent? (Mok-Kong Shen)
Re: Questions about pseudoprimes, testing primes (mathematical) ("Benjamin Johnston")
Re: simple challenge protocol (Cameron)
Re: On a Method of Session Key Generation (revised) (R. Knauer)
Re: What is left to invent? (R. Knauer)
Re: What is left to invent? (R. Knauer)
Re: hardRandNumbGen (R. Knauer)
Pentium III serial number - Why should webs be free? ("Scott Berg")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Crossposted-To:
talk.politics.crypto,alt.security.ripem,sci.answers,talk.answers,alt.answers,news.answers
Subject: RSA Cryptography Today FAQ (1/1)
Date: 10 Feb 1999 13:38:20 GMT
Reply-To: [EMAIL PROTECTED]
Archive-name: cryptography-faq/rsa/part1
Last-modified: 1997/05/21
An old version of the RSA Labs' publication "Answers to Frequently Asked
Questions about Today's Cryptography" used to be posted here until May
1997. These postings were not sponsored or updated by RSA Labs, and
for some time we were unable to stop them. While we hope the information
in our FAQ is useful, the version that was being posted here was quite
outdated. The latest version of the FAQ is more complete and up-to-date.
Unfortunately, our FAQ is no longer available in ASCII due to its
mathematical content. Please visit our website at
http://www.rsa.com/rsalabs/ to view the new version of the FAQ with your
browser or download it in the Adobe Acrobat (.pdf) format.
RSA Labs FAQ Editor
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: RNG Product Feature Poll
Date: 10 Feb 1999 08:52:54 -0500
In article <[EMAIL PROTECTED]>,
Michael Sierchio <[EMAIL PROTECTED]> wrote:
>Herman Rubin wrote:
>> Physical processes are random, but do they have distributions which
>> have the desired probabilities? Random does not imply independent or
>> equidistributed. It is those last which must be tested for, or just
>> assumed that the equipment is guaranteed to be of the needed quality.
>For cryptographic purposes, "collecting entropy" from physical
>processes also requires relying on a "local effect" -- the
>assumption is that someone else can't take the same measurements.
>The techniques for removing skew/bias are sufficient for turning
>most entropy sources into one that passes the statistical tests,
>and the ones required by FIPS 140-1. I take your comment to mean
>that some measurable "random" processes aren't stochastic(?). It's
>still the chaotic zone that counts, even if it is bounded.
For cryptographic purposes, the problem is to keep the interceptor
from getting too much information about the message. For cryptographic
purposes, independent bits with probability .501, or even .51, of
being 1 will be very hard to crack. For statistical simulations,
this might not be the case; 30 years ago, I ran one with about
25,000 bits going into each observation.
Stochastic and random, at least in mathematical use, are essentially
synonymous. The techniques you describe will lessen the effects of
SOME types of bias, but at the expense of increasing others. The
big problem with random sources can be dependence, rather than bias;
this is the problem with pseudo-random sources.
>Anyway, I find something strange about the demand for a "provably"
>true random number generator. I'll settle for a "probably" TRNG.
If by TRNG, you mean one in which all sequences have the same
probability, you will not get it. What you will have to settle
for is one which is "probably" "close" to that.
--
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: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: Wed, 10 Feb 1999 13:50:53 +0100
R. Knauer wrote:
>
> What if I generated a pad by flipping a perfectly symmetric coin - one
> machined to high precision with the same amount of scant markings on
> each face to indicate 1 or 0? Wouldn't the sequence I generated with
> that coin be proveably random?
Tell any mechanical engineer or workman of your project and he'll
laugh at you or simply walk away.
M. K. Shen
------------------------------
From: "Benjamin Johnston" <[EMAIL PROTECTED]>
Subject: Re: Questions about pseudoprimes, testing primes (mathematical)
Date: Wed, 10 Feb 1999 23:45:41 +1100
Thanks for you help, I'm not quite sure about one answer though.
>> 3. If I am using the above test, to find verify primes with very high
>> certainty, how many m should I try, and are there any rules for choosing
an
>> m that is most effective at proving that a number is not prime.
>
>There are composite numbs, like 561, you can not filter out by this test.
Let me rephrase my question,
If I am testing a number, n, to see if it is a prime,
If 2^(n-1) mod n !=1
then the number is not prime (!= meaning not equal)
If 2^(n-1) mod n = 1
then the number may be prime, so I test again using a different base,
ie, 3^(n-1) mod n =1.
Using the number 561 above, it passes base 2, but fails base 3, so it is
therefore composite.
Doing some personal tests, it appears there are about 20 pseudoprimes base 2
between 0 and 20000. I would assume that there would be quite a few
pseudoprimes base both 2 and 3, but for each test I add (ie checking base 4,
5, 6 ...) there would be lesser and lesser chance of a composite being
mistaken for a prime.
How many tests need to be carried out before you can say that the certainty
that a number is prime is so high, that you may as well assume the number to
be prime.
Or alternatively, is this test so unsuitable for finding primes that it
would never be used in cryptographic products (this probably isn't the most
efficient method for finding and testing primes, but if the user is patient
enough could it be carried out with reasonable certainty within reasonable
time (less than a couple of hours)) for large primes.
Thanks again,
Benjamin Johnston
[EMAIL PROTECTED]
------------------------------
From: Cameron <[EMAIL PROTECTED]>
Subject: Re: simple challenge protocol
Date: Thu, 11 Feb 1999 01:30:22 +1100
Paul LeMahieu wrote:
> Hi,
>
> I'm writing some client-server code, and I'd like a simple
> method for the server to verify that the command came from
> a client having the correct password.
>
> My requirements:
>
> 1) no clear-text passwords sent over the network
> 2) server only executes command if it was sent
> by a client with the correct password
> 3) Model: hackers can look at the network, block packets,
> send packets, spoof machine identities, etc.
>
> I have a feeling the algorithm I'm about to describe is
> very well known. It seems simple and safe, but I want to make sure
> there's nothing obvious I'm missing.
>
> Assumptions:
>
> Both client and server know a password (secret key k),
> and a good one-way hash f(k,data). Everything but k
> is known by potential hackers.
>
> Protocol:
>
> 1) Client sends command c to server.
> 2) Server creates challenge r (random number) and sends it to the
> client
> 3) Client responds with f(k,c+r)
> 4) Server compares the f(k,c+r) returned by the client with
> a locally computed one. If they're the same, the server
> executes the command c.
>
> Is this as secure as it seems to me? I see only one shortcoming: the
> server
> must store the clear-text password somewhere (storing a one-way
> encrypted version
> won't do).
>
> I welcome any comments on this protocol, as well as comments on the
> faith
> I've placed in "a good one-way hash".
>
> Thanks,
>
> Paul LeMahieu
> [EMAIL PROTECTED]
In esseence the protocol is secure but it does have a few failings.
It is like most protocols vulnerable to a man-in-the-middle attack. The
only way around this would be to introduce a trusted third-party to
verify both the server and the client to each other.
Also it would be wiser to remove the command from the first step or
from the third and fourth steps. The reason for this being that if c is
sent as plaintext with the protocol and later used as part of the hash
function it introduces an element of insecurity to the hash function as
any one listening in on the protocol will know both c and r there by
reducing the difficulty in breaking the hash function severly. In
practice at the moment this may not seem like a serious enough point but
it you can never be to careful.
The server does not have to store the plain-text password, it can in
fact store a one-way has of the password so long as the same one-way
hash is used by the client. Put simply when the client uses the
password k in the hash function in step 3 before including it with c and
r it first passes it through another hash function, preferably not the
same one used in the protocol for communications between the client and
the server, and then includes it in the final hash sent to the server.
This means that the server need only store the hash of the password and
not the plain-text version.
Cameron
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On a Method of Session Key Generation (revised)
Date: Wed, 10 Feb 1999 14:22:24 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 10 Feb 1999 08:32:33 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>>This is a discussion about what constitutes crypto-grade randomness,
>>including proveable security. As long as ciphers can be shown to be
>>unbreakable, I will accept them as crypto-grade, even if a small but
>>inconsequential amount of information leaks from the ciphers.
>I take the "shown to be unbreakable" phrase to mean some "proof" of
>strength. The issue is indeed about PROVEN security.
>
>Over 50 years of mathematical cryptography has yet to produce any such
>proof. Systems which even get close to such claims (e.g., BB&S, RSA,
>DH) still get a great deal of jaundiced scrutiny. If we limit
>cryptography to only provably-secure ciphers, we will not be sending
>many messages: There are no such ciphers.
Then let people acknowledge that. False claims of security based on
handwaving arguments about statistical tests have no place in
cryptogoraphy.
>And with all this work and *no* examples of ultimate success, one
>might be tempted to think that there is some inherent reason.
>Personally, I suspect that a provably secure cipher simply cannot
>exist.
The OTP is proveably secure.
>>Either the cipher is unbreakable or it is not. If it is not, then it
>>is hardly worthy of further consideration.
>A practical OTP is breakable if the "pad" can be found to be
>sufficiently non-random. And since we are unable to test that no such
>fault exists, we also cannot PROVE that a practical TRNG is
>unbreakable. Just like other ciphers.
But you can test that such fault exists, and you can prove that a TRNG
is unbreakable to within an arbitrary level of precision, one that is
so small that the amount of information leaked is negligible.
Using that TRNG, my original statement above holds true.
Bob Knauer
"It is not a matter of what is true that counts, but a matter of
what is perceived to be true."
--Henry Kissinger
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: What is left to invent?
Date: Wed, 10 Feb 1999 14:58:01 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 10 Feb 1999 08:31:56 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>When I say "source" here, I mean a practical machine producing real
>results. In this context, the quality of randomness in abstract
>"radioactive decay" is essentially metaphysical: perfect True
>Randomness may be in there somewhere, but if we cannot also tap it
>perfectly, it may as well not be.
True Randomness is indeed in there, based on Quantum Mechanics. And we
can tap it well enough to make OTP ciphers that are practically secure
to an arbirtary level of security.
>Yet as soon as I said "there *is* *no* PROVABLY random source," you
>could hardly wait to disagree. The issue is *indeed* about PROOF.
Yes, but there are two kinds of proof: theoretical and experimental.
You are focusing solely on theoretical proof, and I am including
experimental proof. But statistical tests on the final output of a
TRNG do not constitute sufficient experimental proof, so I am
rejecting them for that reason.
Since lack of bit-group bias is necessary for a properly functioning
TRNG, I will accept statistical testing for bit-group bias as a
necessary condition. If a TRNG consistently outputs strings that show
an unacceptable level of bit-group bias, that TRNG needs to be tested
further, including a full audit of its design and complete diagnostics
of its subsystems. But just because a RNG passes bit-group bias tests
does not mean it is a TRNG. PRNGs can be made to pass bit-group bias
tests, and they cannot be TRNGs by definition.
>When we implement a TRNG machine, the randomness we get can be very
>good, and surely "random enough" for security in practice.
As long as you can demonstrate that by doing an audit on the TRNG,
including diagnostics on its subsystems, then it is proveable secure
to a certain experimental level. To apprecitate that, you must
consider experimental proof as a valid form of proof.
>But it
>will NEVER be PROVABLY secure. If the goal of all this TRNG stuff is
>to have "the one PROVABLY secure cipher," that is a goal which can
>never be met.
You are focusing solely on theoretical proof, and leaving out
experimental proof. If you do decide to include experimental proof,
just be sure not to include statistical tests on the final output,
because they are invalid as experimental proof to any level of
security.
In the first place you do not certify the proper operation of
experimental equipment by only studying its output statistically
(because such a procedure is "begging the question"), and in the
second place passing statistical tests are at best a necessary
condition but cetrainly not a sufficient condition for certifying a
TRNG.
The best that can come from using statistical tests on the final
output is that the RNG you are testing MIGHT be a TRNG. But then it
might also be a PRNG, so where does that leave you?
Assuming that a RNG passed your statistical tests, you can now
determine if it is a TRNG to within a specified level of precision by
auditing the design and testing the subsystems, even using certain
statistical tests where appropriate on those subsystems.
One of the things that has clouded this discussion is that the
proponents of statistical testing have for the most part avoided
telling us exactly what statisitcal tests they are defending. Only
tests for bit-group bias have been mentioned, and then only in
passing.
That forces those of us who do not accept statistical testing of the
final output as a sufficient condition for certification of a TRNG,
even to a specified level of security, to question the whole
methodology. I would welcome seeing a battery of statistical tests on
the final output being proposed as sufficient to certify a TRNG ot a
specified level of security, since then I see if they can be used to
solve Godel-Turing-Chaitin indeterminancy problem.
The algorithmic information (complexity) theory of Greg Chaitin,
called AIT, has its type of randomness which is simplier in many ways
to crypto-grade randomness. If you can find an algorithm which
simplifies the production of a number, then the number is not AIT
random. Given that, it is a fundamental tenet of AIT that you cannot
decide on the randomness of a number algorithmically, only that it is
not random. That fact is tied up intimately with the Godel-Turing
indeterminancy problem. Cf. Chaitin, op. cit.
Now, crypto-grade randomness is not the same as AIT randomness - in
fact it is more "demanding". That's because every string is
crypto-random, even the simple ones. Therefore there can be no
algorithmic methodology to decide if a number is crypto-random. The
only thing you can do is to certify that the RNG itself is
crypto-random by proving theoretically and experimentally that it
meets the specifications for a TRNG. That cannot be done solely by
testing its output statistically.
Bob Knauer
"It is not a matter of what is true that counts, but a matter of
what is perceived to be true."
--Henry Kissinger
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: What is left to invent?
Date: Wed, 10 Feb 1999 14:58:34 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 10 Feb 1999 13:50:53 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>> What if I generated a pad by flipping a perfectly symmetric coin - one
>> machined to high precision with the same amount of scant markings on
>> each face to indicate 1 or 0? Wouldn't the sequence I generated with
>> that coin be proveably random?
>Tell any mechanical engineer or workman of your project and he'll
>laugh at you or simply walk away.
Prove that.
Bob Knauer
"It is not a matter of what is true that counts, but a matter of
what is perceived to be true."
--Henry Kissinger
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: hardRandNumbGen
Date: Wed, 10 Feb 1999 15:00:04 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 10 Feb 1999 00:05:49 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Any tests you would use to prove QM indeterminate can be used t prove a non QM
>RNG indeterminate. naturally, these would be statistical tests.
Apparently you never mastered Quantum Mechanics, or you would not be
making such a ludicrous statement as you did above.
Bob Knauer
"It is not a matter of what is true that counts, but a matter of
what is perceived to be true."
--Henry Kissinger
------------------------------
From: "Scott Berg" <[EMAIL PROTECTED]>
Crossposted-To: comp.sys.intel
Subject: Pentium III serial number - Why should webs be free?
Date: Wed, 10 Feb 1999 09:03:02 -0600
Gee, a company (Microsoft or anyone else) spends a fortune learning about a
topic and putting it on the web, then they expect people to PAY for it? And
lock out those who can't prove that they HAD? The nerve of them all!
Why, I regularly go to the gas station and fill up my car's tank without
paying for it, go to the supermarket and fill up my cart without paying for
it, use the telephone without paying for it, ... Why should it be any
different to fill up my hard drive without paying for it?
Sarcasm aside, the web is changing from a government subsidized (read: YOUR
tax money) experiment into a business. You pay for other goods and services
like those listed above. Why should web content be different? Now, I agree
that bug fixes should be free since they shouldn't have been there in the
first place, but handing them out only to those who bought the original
package instead of pirating it seems only fair. I even agree that the net
can be compared to highways, where taxes pay for the "basics" but private
trucking companies make money by charging you for hauling stuff on it.
But remember:
Ain't no such thing as a free lunch!
Nogami wrote in message <[EMAIL PROTECTED]>...
>On Mon, 8 Feb 1999 20:17:44 +0000, Anthony Naggs
><[EMAIL PROTECTED]> wrote:
>
>>>> What I AM concerned about is websites (and software authors) that just
>>>> block all access unless you enable it, thus forcing your hand.
>>
>Ever tried getting on Microsoft's online support pages with cookies
>disabled? It totally locks you out. No cookies = no entry.
>
>That's why I'm afraid of this Intel serial number idea...
>
>N.
------------------------------
** 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
******************************
