Cryptography-Digest Digest #388, Volume #9 Wed, 14 Apr 99 10:13:05 EDT
Contents:
Re: True Randomness & The Law Of Large Numbers (Terry Ritter)
Hex representation of constants available (Dave Shapiro)
Re: Adequacy of FIPS-140 (wtshaw)
Re: Adequacy of FIPS-140 (wtshaw)
Re: Adequacy of FIPS-140 (wtshaw)
Re: SNAKE#6 is oil as well, SNAKE#7 hisses into life (Thomas Wu)
AES Round 1 deadline: 15th April 1999 (David Crick)
Re: PGP=NSA (Conjecture with Arguments) (Gurripato (x=nospam))
Re: discreate logarithm problem ([EMAIL PROTECTED])
Re: SNAKE#6 is oil as well, SNAKE#7 hisses into life (Peter Gunn)
Re: Adequacy of FIPS-140 (R. Knauer)
Re: Adequacy of FIPS-140 (R. Knauer)
Re: PGP 6 is JUNK ("Tony Champion")
Re: PGP, The Big Lie (Theorem with Incomplete Proof) (Thomas W. Kellar)
Re: Adequacy of FIPS-140 (R. Knauer)
Re: Adequacy of FIPS-140 (R. Knauer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Wed, 14 Apr 1999 06:39:15 GMT
On Wed, 14 Apr 1999 00:07:27 -0500, in
<7f17so$cj9$[EMAIL PROTECTED]>, in sci.crypt "Franzen"
<[EMAIL PROTECTED]> wrote:
>[...]
>My chi-square table predicts 98% of the times I flip one million fair
>coins I will get 500,007 to 501,284 (and its inverse, 498,716 to
>499,993) heads.
I'm not happy with using a chi-square table to approximate a binomial
distribution. We could do better with the normal distribution, but
then we would have to convert to standard form, which would confuse
me. Being a simple man, I prefer to use the binomial directly, even
if that must inevitably be harder. And it looks to me like we get:
* less than (or equal to) 498712 about 0.5 percent of the time, and
* more than 501,288 about 0.5 percent of the time.
So we get between 498,712 and 501,288 about 99 percent of the time.
>If you have a better estimator, this is the time to pull it out.
You might try:
http://www.io.com/~ritter/JAVASCRP/BINOMPOI.HTM#Binomial
This is a JavaScript page that computes binomial probabilities and
handles these large values easily, although it rounds the result to 4
decimals. It will not solve the problem directly, but it does provide
enough information to solve it, in particular the c.d.f.
with p = 0.5, n = 1000000,
for k = 498712, the c.d.f. = 0.0050
for k = 501288, the c.d.f. = 0.9950
(c.d.f. = cumulative distribution function; the probability of getting
k or less successes)
>[...]
>I spoke with my mathematican daughter yesterday. Her short answer is
>you people who think 500,000 is the single most expected outcome from
>one million fair flips have little knowledge of simple applied
>probability.
Knowledge or not, daughters or not, and like it or not, the single
most probable outcome *is* 500,000 nevertheless. The probability of
getting that particular value is of course very low (0.0008 or so).
As you say, getting this exact value would be unexpected and
improbable. But the value 500000 is what we call "the expectation."
It also is the most-probable value.
Even that low 0.0008 probability will decrease in either direction as
we move away from 500,000. For example, the probability of getting
exactly 500,200 is down to 0.0007, and the same can be said of
499,800, so getting these values is even more unexpected and more
improbable than getting 500,000. The distribution is symmetric and
values even more distant from 500,000 become even more unexpected and
improbable.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Dave Shapiro <[EMAIL PROTECTED]>
Subject: Hex representation of constants available
Date: Wed, 14 Apr 1999 00:14:58 -0600
Boris Kazak recently sent me some common constants, as hexadecimal
strings, calculated to 16,384 places. These constants include e, e^2,
sqrt(e), ln(2), ln(3), ln(5), sin(1), cos(1), sqrt(2), sqrt(3), and
sqrt(5). He also sent me pi to 65,536 hex places, which he got from a
German site. This stuff is available at
http://www.csd.net/~daves/constants
Dave
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Adequacy of FIPS-140
Date: Wed, 14 Apr 1999 01:33:44 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Terry Ritter) wrote:
>
> This endless, hopeless search for PROOF of absolute security has got
> to stop. There is no such proof in realized systems, including OTP's.
> I suspect there can be no such proof.
>
We must continually find what we can tolerate; it is real life to have to
work with a lower level than the ideal whether in matters of randomness,
or politicians. It is also important to figure out when something is just
not acceptable for our purposes.
--
Too much of a good thing can be much worse than none.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Adequacy of FIPS-140
Date: Wed, 14 Apr 1999 01:27:04 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> I hope you are right, because now one can use Internet-based text
> streams for keys. You index the text source based on some widely known
> pointer like the last digits of world market closes, and hash that
> stream to get a proveably secure key.
>
The key concept is not to pretend that you get more randomness from
distilling text than you reasonably can. Clearly it is between one and
three bits per letter, given a meaningful passage. Therefore, given a
certain sized key, and a desired level of randomness for that key, you
should be able to figure a window of much text you should start with.
--
Too much of a good thing can be much worse than none.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Adequacy of FIPS-140
Date: Wed, 14 Apr 1999 01:39:26 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> On Wed, 14 Apr 1999 00:04:50 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>
> >>For example, based on your statement above, it appears that you
> >>don't believe that a quantum computer programmed to calculate a true
> >>random number is proveably secure?
>
> >>Please explain why you think that..
>
> >No.
>
> Then we must conclude that your comments in that regard are not
> "expert".
>
> At least you are honest about the limits of your understanding, which
> is something more than we can say about the other "experts" around
> here.
>
I take it that he understands the law of diminishing returns, something
very basic to expert analysis.
--
Too much of a good thing can be much worse than none.
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: SNAKE#6 is oil as well, SNAKE#7 hisses into life
Date: 14 Apr 1999 00:25:30 -0700
Peter Gunn <[EMAIL PROTECTED]> writes:
>
> I am starting to come to the conclusion though that I am naturally
> skilled at producing vast quantities of snake oil, without intending
> to do so. There is probably several different thesis in this just
> awaiting documentation by a brave psychologist ;-)
>
> Funnily enough, SNAKE#5 failed to accurately document my intentions...
> which was something like the following snake oil... only small problem
> I can see is that the c1 & C2 values which were intended to show
> proof of possesion of P actually do no such thing... here it is anyway...
> SNAKE#6...
>
> 1) A->B: y1=(g^x1)%p, U, z1=(g^H(P,x1))%p
> 2) B: z2=(g^H(P,x2))%p, key=H((y1^x2)%p)
> 3) B->A: y2=(g^x2)%p, z2, c2=(z1^H(P,x2))%p
> 4) A->B: c1=(z2^H(P,x1))%p
> 5) A: key=H((y2^x1)%p)
>
> What happens is...
>
> 1) Client sends to Server his DH public value y1,
> his user identifier U, and z1=(g^H(P,x1))%p
> 2) Server looks up user list using U to find password P,
> to work out z2=(g^H(P,x2))%p, disconnecting client if
> U is not found.
> 3) Otherwise, he returns his DH Public value along
> with z2, and works out the DH secret value.
> 4) Client works out c1=(z2^H(P,x1))%p, and disconnects if
> c1 != c2.
> 5) Otherwise Client sends c1 to Server, which disconnects
> if c1 != c2.
There's an even easier attack against this one:
Malicious A (step 1) sends out z1=g (instead of z1=g^H(P,x1)).
B now computes c2=z1^H(P,x2)=g^H(P,x2). B also sends back
z2=g^H(P,x2).
Malicious A (step 4) echoes z2 back to B in place of c1.
Guess what: c1==z2==c2==g^H(P,x2); the server is spoofed.
> --------------------------------------------------------------
>
> But wait, there is more... SNAKE#7
>
> Ok, Im still on trying to authenticate the Server and Client
> by proving to one another that they both know the user's
> password P... without spilling the beans to this Ted guy
> who is always snooping in on peoples conversations (what is
> the relationship between Ted & Alice anyway? sounds to me like
> somethings going on there :-)
>
> So, how am I going to prove possesion of P...
>
> Ideas...
>
> #1 => Encrypt DH public values (but thats just EKE)
> #2 => exchange H(P,x)... x would need to include DH public
> in order to verify its origin... and some other
> info (salt?) to stop it being broken because of
> short P. H(P,key) is no use since MITM knows key,
> but what about (g^H(P,key))%p?? This doesnt look
> easily reversed when key is known...
> SNAKE#7 here we go...
If I'm reading this correctly, you're now assuming that both sides
share some value (known as 'key') which is cryptographically strong,
and not subject to brute force attacks. If this is the case, you
can get authentication/key exchange with much simpler protocols,
without even using PK, let alone a strong password protocol.
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
Date: Wed, 14 Apr 1999 10:30:31 +0100
From: David Crick <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: AES Round 1 deadline: 15th April 1999
Hi,
Just a reminder (as if one's needed) that the deadline for comments
on Round 1 of AES is 15th April 1999.
David.
--
+---------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] http://members.tripod.com/~vidcad/ |
| Damon Hill WC '96 Tribute: http://www.geocities.com/MotorCity/4236/ |
| Brundle Quotes Page: http://members.tripod.com/~vidcad/martin_b.htm |
| PGP Public Keys: (2048-bit RSA) 0x22D5C7A9 (4096 DH/DSS) 0x87C46DE1 |
+---------------------------------------------------------------------+
------------------------------
From: [EMAIL PROTECTED] (Gurripato (x=nospam))
Subject: Re: PGP=NSA (Conjecture with Arguments)
Date: Wed, 14 Apr 1999 07:38:37 GMT
On Tue, 13 Apr 1999 19:10:27 -0700, "Charles Booher"
<[EMAIL PROTECTED]> wrote:
>It is called the Booher Conjecture.
>
>PGP=NSA
Conclusion: Phil Zimmerman killed Martin Luther King. Finally
somebody had the courage to tell!
>Since I am the author of the Conjecture I decided in and arrogant fit of
>pique to name it after myself.
>
>
>Why is Phil Zimmerman so totally disinterested in computer programming and
>the mathematics of encryption? He has not written a line of code in the
>last 5 years at least. He has not done a lick of intellectual work in the
>last five years except kiss for money at the NSA.
So what? IIRC, Phil himself said he was no professional
criptographer. He decided to put crypto in a computer program and
give it to the masses, and that�s just what he did. Is he to continue
doing so for the rest of his life? It�s like saying John Glenn is
disinterested in space because he didn�t go to space for the last 30
years. Oh, well, he did last year; well, maybe he is under the
Chinese payroll.
>The current savagely weakened travesty that is calling itself PGP has
>exactly
>
>1000 *1000*1000 =
>
>1,000,000,000
>
>possible key sets.
>
>The dumb asses are using the a custom random number generator with a seed of
>1 Billion possibilities. That is the randomization stuff you type when you
>are typing. It may even be less than that.
Care about some pointers, urls, webpages...?
>Possible Secure Office key pairs than can be generated in less that three
>days on your typical computer (333MHz Pentium).
>
>My symetrical Key is much Bigger as well.
>
>SecureOffice = 2^168
>374144419156711147060143317175368453031918731001856
>
>While PGP=2^128
>340282366920938463463374607431768211456
>
>Testing One Billion Keys a Second takes
>
>SecureOffice = 1.63*10^34 Years
>PGP=1.48*10^22
>
>My numbers are better, way better.
Boy, how relieved I am! Just 10^22 years is not enough for my
security needs.
>My interface is better, way better.
And your marketing is yet to improve.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: discreate logarithm problem
Date: Wed, 14 Apr 1999 11:24:45 GMT
> > If gcd(g, n) = 1 yes. Also g^x = 1 (mod P)
> >
>
> Where did P come from?? What makes you assert g^x = 1 mod P?
I meant to put a 'n', and that is how I read it for a generator. I have seen
this in numerous places.
> > Hard. You have to try all the possible combinations that would make y.
>
> Where did you get this piece of mis- information?
Because if 'g' and 'n' form a good generator then the output can be anything
(almost) between 0 and 'n - 1', if the generator is bad (and you know it) then
you can eliminate some choices.
> > Easier. Since you eliminate alot of possibilities. Given gcd(g, n) = 1,
each
> > output (y) is equal probable (meaning find x is hard).
>
> Your second sentence here is gibberish. Where does probability enter?
Well because many outputs would not have solutions, and thus a probability of
0....
Oh well, I should have proofed my email. Why not start a flame war over it.
(I am really not in the mood, considering all)
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Peter Gunn <[EMAIL PROTECTED]>
Subject: Re: SNAKE#6 is oil as well, SNAKE#7 hisses into life
Date: Wed, 14 Apr 1999 11:54:18 +0100
Thomas Wu wrote:
> Peter Gunn <[EMAIL PROTECTED]> writes:
> >
> > I am starting to come to the conclusion though that I am naturally
> > skilled at producing vast quantities of snake oil, without intending
> > to do so. There is probably several different thesis in this just
> > awaiting documentation by a brave psychologist ;-)
> >
> > Funnily enough, SNAKE#5 failed to accurately document my intentions...
> > which was something like the following snake oil... only small problem
> > I can see is that the c1 & C2 values which were intended to show
> > proof of possesion of P actually do no such thing... here it is anyway...
> > SNAKE#6...
> >
> > 1) A->B: y1=(g^x1)%p, U, z1=(g^H(P,x1))%p
> > 2) B: z2=(g^H(P,x2))%p, key=H((y1^x2)%p)
> > 3) B->A: y2=(g^x2)%p, z2, c2=(z1^H(P,x2))%p
> > 4) A->B: c1=(z2^H(P,x1))%p
> > 5) A: key=H((y2^x1)%p)
> >
> > What happens is...
> >
> > 1) Client sends to Server his DH public value y1,
> > his user identifier U, and z1=(g^H(P,x1))%p
> > 2) Server looks up user list using U to find password P,
> > to work out z2=(g^H(P,x2))%p, disconnecting client if
> > U is not found.
> > 3) Otherwise, he returns his DH Public value along
> > with z2, and works out the DH secret value.
> > 4) Client works out c1=(z2^H(P,x1))%p, and disconnects if
> > c1 != c2.
> > 5) Otherwise Client sends c1 to Server, which disconnects
> > if c1 != c2.
>
> There's an even easier attack against this one:
>
> Malicious A (step 1) sends out z1=g (instead of z1=g^H(P,x1)).
> B now computes c2=z1^H(P,x2)=g^H(P,x2). B also sends back
> z2=g^H(P,x2).
>
> Malicious A (step 4) echoes z2 back to B in place of c1.
> Guess what: c1==z2==c2==g^H(P,x2); the server is spoofed.
>
> > --------------------------------------------------------------
> >
> > But wait, there is more... SNAKE#7
> >
> > Ok, Im still on trying to authenticate the Server and Client
> > by proving to one another that they both know the user's
> > password P... without spilling the beans to this Ted guy
> > who is always snooping in on peoples conversations (what is
> > the relationship between Ted & Alice anyway? sounds to me like
> > somethings going on there :-)
> >
> > So, how am I going to prove possesion of P...
> >
> > Ideas...
> >
> > #1 => Encrypt DH public values (but thats just EKE)
> > #2 => exchange H(P,x)... x would need to include DH public
> > in order to verify its origin... and some other
> > info (salt?) to stop it being broken because of
> > short P. H(P,key) is no use since MITM knows key,
> > but what about (g^H(P,key))%p?? This doesnt look
> > easily reversed when key is known...
> > SNAKE#7 here we go...
>
> If I'm reading this correctly, you're now assuming that both sides
> share some value (known as 'key') which is cryptographically strong,
> and not subject to brute force attacks. If this is the case, you
> can get authentication/key exchange with much simpler protocols,
> without even using PK, let alone a strong password protocol.
Nope, key is just a hash of the DH private value... which the MITM
will know if he's using his own DH public value.
(g^H(P,key))%p
== (g^H(P,H((y2^x1)%p)))%p /** client A ... creates y1, knows x1 **/
== (g^H(P,H((y1^x2)%p)))%p /** server B... creates y2, knows x2 **/
BTW Steps 3) & 4)in SNAKE#7 had a typo and should have read...
3) A: key=H((y2^x1)%p)
4) B: key=H((y1^x2)%p)
but I guess you already spotted that one :-)
The idea is that A & B prove they have both the password P and the
same DH private value by exchanging some value which is calculated
from P & key, but that cant be 'reversed' to find P when key is known.
So the real question is ... how easy is it to get a value for P from the
result of (g^H(P,K))%p where g, K, and p are all constants??
Say P is in the range [0..n], then, P for known H(P,K) with known
K can be obtained in n guesses (or n/2 on average), but obtaining
P for known (g^H(P,K))%p with known g, p, and K would seem to
require n*D guesses where D is the number of guesses required
to find H(P,K) (I guess this is the Discrete Logarithm Problem??)
Of course, the MITM can dictionary attack (g^H(P,K))%p
when g, K, and p are known.... hmmm...
More food for thought...
ttfn,
PG.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Adequacy of FIPS-140
Date: Wed, 14 Apr 1999 13:22:41 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 14 Apr 1999 01:39:26 -0600, [EMAIL PROTECTED] (wtshaw) wrote:
>I take it that he understands the law of diminishing returns, something
>very basic to expert analysis.
Quantum computation is not a matter of any dimishing returns - it is a
fundamentally different way to go about computation.
And it provides for the calcualtion of true random numbers, not just
"nearly" random numbers.
Bob Knauer
"I read a funny story about how the Republicans freed the slaves. The
Republicans are the ones who created slavery by law in the 1600's.
Abraham Lincoln freed the slaves and he was not a Republican."
- Marion Barry, Mayor of Washington DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Adequacy of FIPS-140
Date: Wed, 14 Apr 1999 13:24:09 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 14 Apr 1999 01:51:27 GMT, [EMAIL PROTECTED] wrote:
>> [...] to get a proveably secure key.
>"Proveably secure"? Hm. Does this result come before or after the proof
>there are no purple unicorns?
What are purple unicorns?
Do you know what a quantum computer is? Believe me, it has nothing to
do with your purple unicorns.
Bob Knauer
"I read a funny story about how the Republicans freed the slaves. The
Republicans are the ones who created slavery by law in the 1600's.
Abraham Lincoln freed the slaves and he was not a Republican."
- Marion Barry, Mayor of Washington DC
------------------------------
From: "Tony Champion" <[EMAIL PROTECTED]>
Subject: Re: PGP 6 is JUNK
Date: Wed, 14 Apr 1999 12:28:13 GMT
Maybe you can fill me in on a couple of missing parts to your claims.
1. How to you compare a custom algorithm to a algorithm that just uses a
couple of existing algorithms?
2. If someone is in jepordy of being watched by Big Brother, and they are
encrypting sensitive information with PGP, then they deserve to go to jail
on the count of insanity.
3. Give the man a break.... I don't see your algorithm causing NSA to get
a little nervous...
I am not saying that your algorithm is not more secure than PGP. It might
very well be.... First, publish a detail description of your algorithm, and
let it be confirmed. And I also have no doubt that your GUI is better, but
PGP is not popular for it's GUI.... My last bit of advise is to work on
your marketing strategy a little better... If you want to sell your product,
focus on your product not someone else's.... All of your headings have PGP
not SecureOffice....
Tony
------------------------------
From: [EMAIL PROTECTED] (Thomas W. Kellar)
Subject: Re: PGP, The Big Lie (Theorem with Incomplete Proof)
Date: 14 Apr 1999 13:30:37 GMT
Charles Booher ([EMAIL PROTECTED]) wrote:
: Tell your story to the Grand Jury, I did and I feel so much better for it.
Since you bring it it, I can ask: What is the status
of that situation. I have not heard lately.
Thomas
--
Freelance System Programming. http://www.fsp.com
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Adequacy of FIPS-140
Date: Wed, 14 Apr 1999 13:26:52 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 14 Apr 1999 01:27:04 -0600, [EMAIL PROTECTED] (wtshaw) wrote:
>The key concept is not to pretend that you get more randomness from
>distilling text than you reasonably can. Clearly it is between one and
>three bits per letter, given a meaningful passage. Therefore, given a
>certain sized key, and a desired level of randomness for that key, you
>should be able to figure a window of much text you should start with.
Are you saying that if I want 8 bits of entropy per character, I
cannot simply hash approx. 3 times as much text as key size? How about
hashing 6 times as much text as key size? 12 times, 24 times, 100
times. Text is cheap and so is computer time.
Bob Knauer
"I read a funny story about how the Republicans freed the slaves. The
Republicans are the ones who created slavery by law in the 1600's.
Abraham Lincoln freed the slaves and he was not a Republican."
- Marion Barry, Mayor of Washington DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Adequacy of FIPS-140
Date: Wed, 14 Apr 1999 13:28:50 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 14 Apr 1999 01:33:44 -0600, [EMAIL PROTECTED] (wtshaw) wrote:
>We must continually find what we can tolerate; it is real life to have to
>work with a lower level than the ideal whether in matters of randomness,
>or politicians. It is also important to figure out when something is just
>not acceptable for our purposes.
It is also important to recognize a fundamental breakthru, like
quantum computation.
Quantum computation holds out the prospect of generating true random
numbers - not very good approximations to true random numbers, but
actual 100% true random numbers.
Bob Knauer
"I read a funny story about how the Republicans freed the slaves. The
Republicans are the ones who created slavery by law in the 1600's.
Abraham Lincoln freed the slaves and he was not a Republican."
- Marion Barry, Mayor of Washington DC
------------------------------
** 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
******************************
