Cryptography-Digest Digest #285, Volume #9 Thu, 25 Mar 99 15:13:02 EST
Contents:
Crypto & Security papers web site ("Jim Press")
Re: compare RSA and D-Hellman ("Harv")
Re: Live from the Second AES Conference (John Savard)
RNG quality in browsers? (Mika Niemi)
Re: RSA key distribution ("Roger Schlafly")
Re: Message Digest ("karl malbrain")
Random post received from [EMAIL PROTECTED] ("karl malbrain")
Re: Random Walk (R. Knauer)
Re: Random Walk (karl malbrain)
----------------------------------------------------------------------------
From: "Jim Press" <[EMAIL PROTECTED]>
Crossposted-To: alt.security
Subject: Crypto & Security papers web site
Date: Thu, 25 Mar 1999 18:22:41 GMT
Various papers that I've had published at one time or another are available
at:
http://home.freeuk.net/jpress/papers.html (non-frames)
or by navigating via frames at:
http://home.freeuk.net/jpress/frames.html
The previous bad links problem has been fixed.
Enjoy
------------------------------
From: "Harv" <[EMAIL PROTECTED]>
Subject: Re: compare RSA and D-Hellman
Date: Thu, 25 Mar 1999 10:34:03 -0800
A and g can be static and public; in fact, If A and g are static and public,
then you can evolve DH into the ElGamal public key system.
For the best setup, g shouldn't really be a small random number. g should be
a generator of A. g is a generator if and only if the only X that satisfies
g^X = 1 mod A is X=A-1. For example 3 is a generator of 7, but 2 is not.
However, if A is a randomly picked prime, then it can be difficult to tell
if g is a generator. You need to know the factorization of A-1. If you know
the factors of A-1 then g is a generator if g^x=1 mod A and g^b!=1 mod A for
any b that divides A-1.
So, you best bet is to pick a large prime p, and test if 2*p+1 is also
prime. If this is the case then set A=2*p+1, and start the hunt for a
generator.
Harv
[EMAIL PROTECTED]
Remove the Some to send email.
<[EMAIL PROTECTED]> wrote in message
news:7dd7q3$6ln$[EMAIL PROTECTED]...
> so let me see if I understand:
>
> A -> large prime number
> x,y -> large private numbers (not prime)
> g -> small random number?
>
> Is that right? Can 'a' be static?
>
> Tom
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Live from the Second AES Conference
Date: Thu, 25 Mar 1999 19:02:56 GMT
William Hugh Murray <[EMAIL PROTECTED]> wrote, in part:
>Of course, the value of super-encryption, even 3DES, assumes that
>encryption is the weak link in one's security. Since that is almost
>never the case, why bother? I ask this as a serious question. It seems
>to me that the entire AES effort spends incredible amounts of treasure
>on the easy part of the security problem.
>What am I missing?
You are fundamentally correct.
However,
- when there is a weakness in most parts of computer security, they can
only be exploited by certain people, who may need physical proximity, or
who may need to take a risk of getting caught. Weaknesses in ciphers can be
exploited by passive eavesdroppers halfway around the world.
- improvements in the speed and cost of computers mean that DES _is_ too
weak. Yes, encryption is only the easy and obvious tip of the security
iceberg. (Did somebody else say this before? I wouldn't want to plagiarize
Bruce.) But that's not a reason for making a certain minimal effort to make
it adequate before going on to the "real" problems. And, no offence, but
the AES effort can be described as "minimal" - in terms of the expenditures
made by the U.S. Government, the rewards offered to participants, and so
on. When the U.S. Government is *serious* about wanting a new cryptosystem,
it goes to the NSA.
So, in conclusion, I'd say that the AES effort is spending no more effort
than necessary on what is the easy part of the security problem, but still
a part that needed a little work at the moment.
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: Mika Niemi <[EMAIL PROTECTED]>
Crossposted-To: comp.infosystems.www.browsers.misc
Subject: RNG quality in browsers?
Date: Thu, 25 Mar 1999 12:55:52 -0600
Can anyone tell me about the quality of (pseudo) random number
generators
that popular browsers such as Netscape use for generating encryption
keys?
Is the key generation part of BSAFE, or is it done by the rest of the
program?
It would be wasteful to use 128-bit algorithms if the RNG generating the
keys has only a 32-bit seed or something stupid like that.
PGP used to have a method for generating random seeds from the timing of
users keystrokes. Putting something like this in a browser would be
more
convincing to me than some animated lock -icon (Well, maybe now this can
be done if Netscape has become open source).
Mika Niemi
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: RSA key distribution
Date: Thu, 25 Mar 1999 10:19:07 -0800
DJohn37050 wrote in message <[EMAIL PROTECTED]>...
>As Bob said, the bankers chose to exclude the possibility of certain
classes of
>attacks, at a small cost, rather then allow a very small chance that they
would
>work.
This is a completely useless thing to be doing as long as there are
other attacks which are much more likely to succeed.
To see why, consider the attack on DES in which the attacker just guesses
the key "12345678". The attack very rarely works, but is deadly when it
does. Someone can avoid the attack by adopting a DES key generation
procedure that never generates "12345678". But is any security gained
by such a procedure? No. It is always possible (however unlikely) that
someone will guess the key. The best protection is to choose keys
uniformly randomly, and not to try attacks which are of no practical
significance anyway.
> This was a conservative choice that they should be allowed to make.
It is not just a banking standard. It is an ANSI standard, and soon to
become
a US govt standard. There is a proposed FIPS that rubber-stamps the
ANSI standard.
It is reasonable to say that the bankers should be able to generate their
own keys using criteria that they believe to maximize security. However,
the standard does not allow this. Everyone must use bobs's procedure
even though most experts (including bobs?) disavow it as misguided.
------------------------------
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: Message Digest
Date: Thu, 25 Mar 1999 11:16:10 -0800
<[EMAIL PROTECTED]> wrote in message
news:7dati5$59d$[EMAIL PROTECTED]...
> Question:
>
> Given a 256 bit message, and a 128 bit digest, are there 2^128 256 bit
> messages that will make the same message digest?
>
> Tom
The point of the MESSAGE DIGEST function using 128 bits is that there has
not been 2^128 messages produced by people so far!!
So, practically, the answer to your question is EXPECT a value of 1 digested
value for 1 message. Karl M
------------------------------
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Random post received from [EMAIL PROTECTED]
Date: Thu, 25 Mar 1999 11:08:08 -0800
From: John Curtis <[EMAIL PROTECTED]>
> Date: Tue, 23 Mar 1999 17:34:39 -0500 (EST)
> To: [EMAIL PROTECTED]
> Subject: Re: Random Walk
> Dear Mr. Malbrain,
> Keep up the good work. Your efforts on sci.crypt are
> appreciated.
> regards,
> jcurtis
Thanks for the <<backing>> John, but you've already come-out in favor of
dumping this topic OFF THE NEWSGROUP with your sci.crypt.random
suggestions?!?
What gives??? Karl M
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Thu, 25 Mar 1999 19:46:43 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 25 Mar 1999 09:43:01 -0700, Shawn Willden <[EMAIL PROTECTED]>
wrote:
>>I have never proposed using the random walk as a model for
>>crypto-grade random number generation.
>So the random walk bit is a red herring?
Nope. I have not made any comment about the applicability or
inapplicability of the random walk for purposes of generating
crypto-grade random numbers. I leave that to you to decide.
All I have stated thus far is that a true random number generator
(TRNG) for purposes of crypto-grade randomness is a process that is
capable of generating all possible finite sequences equiprobably,
namely in an independent and equidistributed manner.
>Someone who has thought a little about the properties of random walks in
>particular would not be deceived by their intuition. The behavior of a random
>walk is quite sensible when you remember that it has infinite memory. On the
>other hand, someone who is applying intuition about memoryless processes (such
>as a UBP) to a random walk will be deceived in much the same way that someone
>applying their intuition about the carrying capacity of a truck to a sports car
>will be decieved. It should not be surprising that a random, impromptu survey
>of statisticians reveals a limited understanding of random walks. Outside of
>the financial industry, the random walk is not a common model, and that's a
>relatively new concept even in the financial industry.
Apparently the notion of true randomness is not commonly understood by
people in the crypto industry, judging from the rather large amount of
snake oil out there regarding the effectiveness of statistical tests.
>Processes with memory are unsuitable for random number generation.
Is that your opinion, or can you prove it? If you can prove it, I
would like to see the proof, since that will give me another insight
into the nature of true randomness.
For example, it is known (believed with great certainty) that quantum
mechanical phenomena like radioactive decay are truly random. Based on
what you are saying, those phenomena cannot be the result of any
process that has memory. Yet the unitary process that underlies
quantum phenomena seems to have a lot of memory. Therefore there
appears to be an example where your dictum is not obeyed.
The unitary evolution of the wave vector is governed by the
Schroedinger equation and is completely deterministic. At each instant
the state of the system is known with complete certainty based on the
wave vector, which is known to tell you everything about the system.
Yet the moment at which a particular radioisotope will decay is not
known at all - it is a truly random event that is the result of second
order perturbation theory applied to the nucleus and the vacuum. The
spontaneous emission of radioactive decay is the result of vacuum
fluctuations affecting the excited nuclear state.
So there is a memory component at work in QM, yet QM processes are
truly random.
>> The uniform one-dimensional random walk is the same as the uniform
>> Bernoulli process in terms of how the bits of the sequence are
>> generated.
>Nonsense. The output of random walk looks nothing whatsoever like the output
>of a UBP. A UBP can be used as the underlying random process on which one
>builds a random walk, but the outputs of the two processes are radically
>different. With this sort of construction, you must think of the random walk
>as a sort of post processing on the underlying process.
Please re-read my statement above and tell me how it says anything
that is different from what you just said. The operative part of the
statement above is "in terms of how the bits of the sequence are
generated" - and you are saying the same thing as I said, namely, that
the random walk relies on the UBP for generation of the paths.
>First, you're mixing things up. The uniform Bernoulli process is a model and
>models are not suitable for generating anything.
I find that a very curious comment. It seems to be saying that one
cannot use the equation for a perfect circle to program a numerically
controlled milling machine for making wheels. IOW, you seem to be
saying that the model of the perfect circle is not suitable for making
round wheels.
>If the question is: Why is
>the UBP not suitable as a model for a TRNG? then my answer is: I don't know.
Then my question remains unanswered.
>Certainly a non-uniform Bernoulli process seems like an excellent model, since
>it is then not necessary that p==q.
But a non-uniform Bernoulli process results in sequences that are not
crypto-grade. IOW, the process is no longer equidistributed. If p > q,
then the process will generate more sequences with a greater number of
1s versus 0s, and fewer sequences with the opposite property. In the
case that p >> q, most sequences will be highly biased with 1s
compared to 0s. That makes a very poor keystream for crypto.
>> I am not offering any arguments. I am merely quoting what I read in
>> books.
>Maybe I should post some passages from "Watership Down"?
If they are relevant, go ahead. I once referred to Edgar Allen Poe's
"Gold Bug" because he used a simple cipher in the story.
>Come on, you must be
>trying to accomplish something with your quotes.
If you really want to know what I am trying to accomplish, it is to
entice people to read those books and comment on what they think is
the truth being exposed in them.
My underlying motive for being here is to learn more about the concept
of true randomness as it applies to an area that demands true
randomness in the extreme case of proveable security.
Why I am interested in true randomness has to do with the following
comment:
+++++
"If you want to build a robust universe, one that will never go wrong,
then you dosn't want to build it like a clock, for the smallest bit of
grit will cause it to go awry. However, if things at the base are
utterly random, nothing can make them more disordered. Complete
randomness at the heart of things is the most stable situation
imaginable - a divinely clever way to build a universe."
-- Heinz Pagels
+++++
IOW, my ultimate motive is acquire metaphysical understanding of the
nature of reality.
Since there are no decent metaphysics forums on Usenet, I have to
settle for the next best thing, which is crypto. Anyway, crypto has
the interesting property of being about unknown things, and that is a
metamathematical property that I believe is tied in with quantum
indeterminancy.
>Generally quotations are used
>to provide support in the form of expert opinion for arguments the poster is
>making. I assume this is what you are doing, but I'm not seeing what your
>argument is, or, more precisely, I see some arguments from you and some quotes
>that you posted, but there is no obvious connection between the two.
I am not trying to carry the burden of proof of my position all by
myself. I ask the reader to seek out the truth for himself, and I
suggest some places to begin the search.
>I'm asking you to make that connection clear.
That is a fair request. Stay tuned and maybe the connection will be
made clear one day, assuming that there is a connection to begin with.
For now, it is the task at hand to set the groundwork - and that
usually begins by sweeping old junk out of the place. Otherwise you
never get anywhere - each time you try to cut the Hydra's head off it
grows another one.
Thus far there has been a general unwillingness on the part of the
participants to explore even the possibility that what I am claiming
is true. All I have seen is dogmatic posturing reminescent of the
catholic church when it had to deal with Galileo's claims that the Sun
is at the center of the planetary system, and not the Earth. It took
centuries for the Vatican to recant that incident (which the Pope
finally did do last year). Needless to say, such dogmatism can be a
bit stifling.
We can proceed to the truth only after people decide that it is worth
the effort to pursue it. Otherwise people will cuddle up with their
pet dogmas and never let go.
>Yes, randomness is a very subtle and complex concept, and, if I am interpreting
>your use of the term "characterize" correctly,
I use it in its ordinary dictionary sense, namely (from Websters
Online):
"to describe the character or quality of <characterizes him as
ambitious> 2 : to be a characteristic of : DISTINGUISH <an era
characterized by greed>"
>you are correct that it is
>impossible to define statistical tests that will verify that a sequence is
>random.
I think you mean to say: " it is impossible to define statistical
tests that will verify that a sequence is generated by a random
process." Only the most naive person believes that you can decide
randomness of a given sequence.
The debate now is whether statistical tests can be used to
characterize non-random processes. That is, if a process fails
statistical tests for pseudorandomness, does that mean for certain
that the process is not truly random?
Is pseudorandomness a necessary (but not sufficient) condition for
true randomness?
If you draw balls from an urn filled with a very large number of balls
of white and black color, can you validly conclude from a sample of
all white balls, that there are only white balls in the urn? I think
not. You have to proceed to examine all of them, and that entails an
infinite number of samples.
Put in reverse fashion, just because you only spot one unicorn in a
large herd of horses does not mean that unicorns do not exist based on
the fact that in the limit of a large number of horses, the
probability for unicorns becomes vanishingly small. Herds are finite
entities of discrete components, and the properties of infinitely
large herds do not rule out the existence of unicorns if you spot one
in a large herd.
>Obviously. One cannot use statistical tests to detect randomness.
You know that, and I know that, and several other readers of sci.crypt
know that. But if you were a regular here, you would be appalled at
the number of people who do not know that.
But that is not the issue I am raising now. The position I am taking
in this debate is as stated above, namely that one cannot use
statistical tests to detect non-true-randomness.
>The expansion of pi might make a perfectly good PRNG, other than it's so much
>slower than other, equally good methods. However, what does this have to do
>with cryptography?
Beats me. Probably as much as your comment has to do with
cryptography.
>No I would not. I would consider them to uniformly distributed and free of
>detectable bias. I might consider them to be unpredictable, but I would have
>to believe that they may be predictable by someone who knows more than I do.
Some people would conclude that just because the digit expansion of pi
passes statistical tests for pseudorandomness, that the process is
therefore truly random. We know that to be incorrect.
Other people might conclude that just because the output of a TRNG did
not pass statistical tests for pseudorandomness, that the TRNG is
therefore not truly random.
I concede that if a TRNG does not pass pseudorandom tests, that there
is a certain (calculable) *possibility* that it is not truly random,
but I also maintain that one must decide that on the basis of an
analysis other than statistical testing of the output per se.
That is why I am willing to accept statistical testing as a diagnostic
aid, but no more than that - except in the infinite limit.
>Statistical tests do not and, as you pointed out, cannot characterize
>randomness.
Nor can they characterize non-randomness with absolute certainty.
>Statistical tests do precisely what they're designed to do, which
>is compute the probability that a particular finite string is produced by a
>random variable that is distributed according to a particular model.
And that probability is only an estimate of the possibility that the
variable is truly random - or non-random. Possibility does not mean
certainty for finite sized samples. Only in an infinitely large sample
can one determine for certain the randomness or non-randomness of a
process based on statisitcal measure. That is what the law of large
numbers is trying to tell you - that you must go to the infinite limit
to get certainty, otherwise all you can have is a calculable level of
possibility.
>(Assuming OTP encryption, you forgot to say).
I have grown weary of making statements that call out every little
assumption. The assumptions here are previously stated so many times
that it becomes a drag to repeat all of them all of the time.
>Let me see if I can say this clearly:
>If I have a coin that is weighted on one side, such that P(H) = .3 and P(T) =
>.7 (as determined by experimental trial and statistical analysis of the
>results, with sufficient trials to establish the required confidence level),
>and I flip the coin and use it to generate bits, is the resulting stream
>random? Yes, it is.
It is not crypto-grade random. Crypto-grade randomness demands
equidistribution, and the process you just described is not
equidistributed.
>It is heavily biased, but it is in fact random. Is it a
>good RNG for cryptographic purposes? No. The biases disqualify it.
So? What conclusion are you trying to draw?
>If I have a computer and an algorithm that generates a stream of bits with P(0)
>= .5 and P(1) = .5 (always, as shown by a set of powerful statistical tests on
>the results of a large number of trials), is this stream random? No, it is
>not. Is it a good RNG for cryptographic purposes? Probably not. An attacker
>may be able to discover the algorithm and predict the stream.
That's because the PRNG is not an independent process, namely the PRNG
is deterministic. The digit expansion of pi is an example of a PRNG
that is (supposedly) unbiased. BTW, when we say unbiased we mean Borel
normal, namely there is no bias in any of the bit groups, which
includes 1-bit groups, 2-bit groups, etc.
Many naive statistical tests only look for 1-bit bias, which means
that don't even measure pseudorandomness correctly.
>If I have a noise-based RNG based on radioactive decay, well-shielded to
>prevent an attacker from monitoring the output, and I have not performed any
>statistical tests to look for, is this stream random? Yes, it is.
Only if you have done a design audit, preferable one that is peer
reviewed or is copied from a peer-reviewed design, and you have
conducted experiments to verify the performance of all subsystems
using accepted methods of testing.
> Is it a
>good RNG for cryptographic purposes? Possibly not. An attacker may be able to
>detect significant biases in the output (possibly due to a feedback loop or
>other bug).
If the RNG meets the specification for a TRNG, then it is suitable for
a proveable secure cryptosystem such as the OTP. You will have to do a
design audit and run experimental tests on each subsystem to determine
if the device is a TRNG or not.
>If I do apply thorough statistical tests to my well-shielded,
>radioisotope-based RNG and I discover that, with very high confidence, the
>resulting bit streams fit a uniform distribution and evidence no memory,
Just out of curiosity, how do you propose to do that? Can you call out
the battery of statistical tests and all the test conditions that you
would use.
>and I
>then cease testing and put the RNG into production, is this stream random?
>Yes, it is.
It is only because it meets the specification for a TRNG, and that is
something you cannot determine from statistical testing alone?
>Is it a good RNG for cryptographic purposes? Maybe. I might not
>notice if it breaks and begins producing outputs that would fail my tests, and
>an attacker might.
That is why you must run diagnostics to make sure it is not
malfunctioning.
>If I have my shielded, tested TRNG and while continuously monitoring the output
>I notice a string of 100 consecutive zeros, is this stream random? No, it is
>not.
Why not?
I agree that such an occurance has a large *possibility* of being the
result of a malfunction, but it is not certain that it is the result
of a malfunction.
If you stopped the TRNG and checked it out, and found out that it was
not malfunctioning, would you use those 100 zeros as part of the
keystream - or would you discard them because you are prejudiced
against long runs?
Where in the specification of a TRNG does it mention anything about
long runs of one bit or the other being prohibited?
>I don't care how carefully you designed and tested it, your TRNG is
>broken. Is it a good RNG for cryptographic purposes? No.
If it is funtioning properly and it puts out 100 zeros, then those 100
zeros are crypto-grade random, because the cryptanalyst has no reason
to believe that the key is made up of those zeros.
A run of 100 zeros is just as likely as any other sequence of 100
bits, therefore the cryptanalyst has no reason to believe that it is
something special. The appearance of a run of 100 zeros does not mean
that the TRNG is broken.
Bob Knauer
"The important thing is to stop lying to yourself. A man who lies
to himself, and believes his own lies, becomes unable to recognize
the truth, and he ends up losing respect for himself as well as for
others. When he has no respect for anyone, he yields to his impulses,
indulges in the lowest forms of pleasure, and behaves in the end like
an animal, in satisfying his vices."
--Dostoevsky (The Brothers Karamazov)
------------------------------
From: karl malbrain <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Thu, 25 Mar 1999 19:58:09 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I conclude with my oft-cited example of the unicorn. Just because you
> spot only one unicorn in a large herd of horses, you cannot conclude
> that unicorns do not exist just since, in the limit of large numbers
> of horses, the probability of a unicorn in the herd is zero.
Well, you run AGROUND here in the field of HISTORICAL MATERIALISM. There
never has been a limit on numbers of HORSES. Hence, your probability for
UNICORNS never reaches ZERO at all!!! I would suggest you just give-it-up on
the SUBJECTIVE IDEALISM of METAPHYSICS, and join the BOLSHEVIKS in a field
near you, now!!
Karl M
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
