Cryptography-Digest Digest #607, Volume #12 Mon, 4 Sep 00 05:13:01 EDT
Contents:
Re: R: R: R: R: R: R: Test on pseudorandom number generator. (Terry Ritter)
Re: RSA public exponent (Bryan Olson)
Re: Capability of memorizing passwords (Anders Thulin)
Re: I need an algorithm to determine the center of gravity for; (Anders Thulin)
Re: cryptology software ("Michal Kvasnicka")
Re: New cryption method... ("Stou Sandalski")
Re: Capability of memorizing passwords (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: R: R: R: R: R: R: Test on pseudorandom number generator.
Date: Mon, 04 Sep 2000 05:27:27 GMT
On Mon, 4 Sep 2000 01:13:58 +0200, in <8oukja$nsb$[EMAIL PROTECTED]>,
in sci.crypt "Cristiano" <[EMAIL PROTECTED]> wrote:
>> >> >For my purpose I generate many 1024 bits numbers (with BBS), I collect
>> >only
>> >> >few lsb from these numbers, I apply SHA-1 every 160 bits collected and
>I
>> >> >take only differents bit pairs (00 and 11 are discarded, while 01=0
>and
>> >> >10=1).
>> >> >If I test this sequence with a bit test (including Maurer), it's ok?
>> >>
>> >> The Maurer test article specifically disclaims use of the test on
>> >> pseudorandom sequences. And, in my experience, the test itself is
>> >> much less sensitive than runs.
>> >
>> >Do you mean that Maurer's test is good only for random sequences?
>>
>> I mean that he says in his article that the test is only for really
>> random sequences and not pseudorandom sequences. Shall we use his
>> test and then ignore what he says about its use?
>
>I have the article. An explicit disclaim to utilize Maurer's test for
>pseudorandom sequence seems not present in this article (perhaps except for
>some words at the beginning of the abstract section).
I am glad you have the article. Now, please follow on p. 410:
"The paper is not concerned with tests for pseudo-random bit
generators . . . ."
A more complete excerpt is:
". . . there do exist chaotic processes in nature, such as radioactive
decay and thermal noise in transistors, that allow the construction of
a random bit generator that is completely unpredictable for all
practical applications. It is a non-trivial task, however, to design
an electronic circuit that explores the randomness of such a process
in a way that guarantees the statistical independence and symmetrical
distribution of the generated bits. It is therefore essential in a
cryptographic application that such a device be tested intensively for
malfunction after production, and also periodically during operation.
"The paper is not concerned with tests for pseudo-random bit
generators that stretch a short (randomly selected) seed
deterministically into a long sequence of random bits, i.e., it is not
concerned with the evaluation of practical keystream generators for
stream ciphers."
Thus "the paper" (that is, Maurer's test) concerns the testing of
"really random" sources, not pseudorandom sources.
>> >I like this test because it's output is only a chi-square value (not 234
>> >p-values),
>>
>> Something sounds wrong about that: Your earlier message described a
>> test with 234 values; that is *not* 234 p-values, or at least it
>> should not be. Those values into one test produce a statistic which
>> has a p-value -- that is, one p-value -- not 234.
>>
>> The output of even something very simple like the frequency test is a
>> statistic which has one p-value, not 234 p-values.
>
>From DiehardC 1.01 documentation:
> "DiehardC will perform 15 tests, each of which will produce a p-value.
> A p-value is normalized and if your random numbers really are random,
> it should be between 0.001 and 0.999 (Bad random numbers generators
> will usually produce p-values of 0.00000 or 1.00000) After all the
> tests are performed, you'll see a summary of the 160 or p-values,
> and a KSTEST of all of them."
>
>Observing the program, the p-values are 234. After sorting these p-values a
>KS test is performed given a p-values of 234 p-values.
>You say is this wrong?
You say you like the Maurer test because its output is only a single
chi-square value. (Actually, it would be better to use p-values,
because chi-square evaluation depends upon size.) But every test or
set of tests can produce *a* single result.
On the other hand, if one actually does perform multiple tests, one
should want multiple results, instead of just an overall summary. But
of course one could get such a summary simply by combining the results
in some way.
Perhaps you think that by performing a Maurer test you have one test
which is the equivalent of performing any multiple of tests. I
disagree. In my experience, I have found "runs" to be superior, for
any particular amount of data.
Consequently, I say there is no difference -- beyond a particular
implementation -- between the amount of output from the test you like
better and the test you do not. I also say that in my experience the
Maurer test is notably insensitive for the amount of data it uses.
>> If you have had some success finding problems using the Maurer test, I
>> would like to hear about it. In my experience, it is very insensitive
>> at realistic testing sizes, and if we have much more data, the other
>> tests can use that and improve their results as well.
>
>I have these tests: frequency (monobit test), Serial (two-bit test), Poker,
>Runs, Autocorrelation, Maurer and Diehard (the latter only 1 week).
>I found Maurer's test very sensitive. When I tested URAND, autocorrelation
>test found a high chi-square at 32 (about 5) and 96 (about 4) bits distance.
>Maurer's test give a very bad chi-square (about 23) with L=8 and bad (about
>4) with L=9; with L=16 it give a chi-square of 1500 (!). The size of testing
>sequence is 1010*2^L*L bits (as in documentation).
>Normally autocorrelation test check distance up to 8-16 bits (now I check up
>to
>100 bits), without Maurer's test URAND can pass any test because the other
>test but Diehard don't detect this weak point.
First of all, it is better to use the p-values in a discussion than
raw chi-square values.
Next, I am confused. I thought you has said that once you had ceased
to use your "trick" of collecting bytes from multiple steps, URAND was
exposed as a bad generator by Diehard. If not, what did happen?
>> >and then because it is able to detect any "tampering" in the
>> >generator (like an arbitrary change of just few bits every hundreds).
>>
>> Really? What makes you think so?
>>
>> The Maurer test typically works on bytes, on which runs-up / runs-down
>> becomes useful. In my experience runs is more sensitive, so I would
>> expect it to better detect tampering. If that expectation is wrong, I
>> would like to hear about it.
>
>Only the facts!
>When I try to make a PRNG by myself, it is strongly possible that my
>generator don't
>pass some test. My first BBS generator don't pass the runs test for L=6. So
>with some "trick" I try to modify only few bits every 100-200. Now all test
>are good (not Diehard) but Maurer fail with a chi-square very high.
>So I'll toss Maurer's test only for strong valid reasons proven by facts.
The only facts I know you have do not imply what you seem to think.
Simply because Maurer continues to find a problem after your "trick"
is applied does not make it a better test, except *perhaps* with
respect to that particular trick.
There is a great deal more to understand before we can even accept
that Maurer is not confused by that trick. For example, we would like
to know whether Maurer produces the same result for various levels of
trickiness; and if not, why not? Surely taking a byte each from 4 RNG
steps must in some sense appear "more random" than not doing so.
When we look at the details of Maurer, we find that it does not do
well exploring full 32-bit values. I don't know what you are doing,
but if you are applying Maurer on bytes, while applying the other
tests on 32-bit values, the results simply are not comparable. No
wonder the "trick" of taking a byte from each step does not confuse
Maurer! If the other tests were applied on bytes, they might do as
well or better. There is a great deal more that it is necessary to
know than one apparent success.
>> >For runs test do you mean the one in the above book?
>>
>> I started implementing statistical tests and testing RNG's a decade
>> ago, way before HAC, and I have used many different references. One
>> good reference is Knuth's "The Art of Computer Programming," Vol. 2.
>> Now that I look at the test descriptions in HAC, they seem pretty
>> sparse to me, and rather obscure as well.
>>
>> I do not use the HAC statistic for runs; it seems to me that runs
>> should have a combinatoric (probably binomial) distribution, and
>> knowing that, we can collect a distribution of run-length counts, then
>> compare the sample distribution to the expectation using chi-square.
>> To me, that would seem to be much more straightforward, more likely to
>> be programmed correctly, and more useful if it finds a problem. In my
>> experience, comparing distributions in this way can pick up a
>> surprisingly wide variety of problems.
>
>What you say seems to be what is in HAC.
And where would that be, exactly?
I get better results, in general, when I can predict the expectations
for a complete discrete distribution. We can do that for frequency,
runs up / runs down, runs, and various other tests. Then all we have
to do is to compare the distributions.
Often, we will use a statistical test -- for example, chi square -- to
render an opinion on whether the sample distribution is the same as we
expect it to be, given a random source. But if we have the sample
distribution values, that is not our only option; for example, we can
simply graph the sample distribution and look at it. We don't have to
depend upon a numerical evaluation to tell us when a sample
distribution has problems. We can validate the numerical comparison
with our own eyes, and often don't need any sort of statistical
function evaluation at all.
>> >> >For my curiosity, I test such a sequence with Diehard (ok it's bad!).
>> >> >If I collect more than 4 bits at each step (x=x*x % n) Diehard fail
>big.
>> >> >If I collect less than 5 bits at each step Diehard is far good. Maurer
>is
>> >> >almost always good.
>> >> >It seems that some information is given also by Diehard. It is
>possible?
>> >>
>> >> Sure. But if your sequence fails when you test more than a few bits
>> >> of RNG internal state, your RNG's are "bad" and you need to fix them
>> >> before going on. "Good" RNG's generally pass statistical tests even
>> >> when the tests are performed properly on all of the RNG state.
>> >> (Sometimes, specific tests which correspond to RNG structure will
>> >> detect that structure and fail, and we can't do much about that.)
>> >
>> >I do only what is in literature. A BBS generator is a BBS generator!
>>
>> Perhaps. But a BB&S generator with small N is insecure.
>
>(?) Do you think that a modulus of 1024 bits it is small?
For what? As I understand things, 1024 bits is too small for the
theoretical guarantees to kick in.
>> And a BB&S
>> generator with an error in implementation is not really BB&S at all.
>> Is a BB&S generator which does not function as one might expect also a
>> BB&S generator?
>
>Sure, but its implementation is very simple!
If indeed the implementation is so simple, why do you report problems
in the sequence which it generates? Why is there a need to "de-skew"
with SHA-1? I would find it ironic indeed if BB&S produced biased
sequences.
>> >After many attempts to get a "random" sequence, I seen that in most cases
>by
>> >appling SHA-1 and de-skewing the result is far good.
>>
>> But you should not have to do that if the underlying generator is
>> working right. The need to "de-skew" should tell you that something
>> is wrong! Maybe a BB&S generator is *not* a BB&S generator! Finding
>> and resolving this sort of result is exactly why we test!
>
>The de-skew in not needed. I only found that the sequences are a little
>better by de-skewing it, that is the tests give a better result (not
>always). Probably in my final version I'll use "standard" BBS (without any
>"trick").
I can only go by what you report. If you say you needed something
beyond BB&S itself, one can only ask "Why?"
>> >For a BBS generator is provable secure to get only lg lg n least
>significant
>> >bits, but by using SHA-1 I can take more bits.
>>
>> Really? Who says?
>>
>> If you take more bits, you violate the strength theory of BB&S; if you
>> are willing to do that, why not use the whole BB&S state in SHA-1?
>
>An ashing function is said to be not invertible.
Indeed, many things are "said." But if there is an advantage to BB&S,
that advantage is the claim to have a proof of strength. I am aware
of no such proof for the hashing function. So to use a very slow RNG
specifically for its proof of strength, and then to give up that proof
for a hashing non-proof, seems rather strange.
>So if I hash some bits is
>very hard to correlate the result of hash with its input.
That already should be hard if one is using BB&S correctly.
>If the bits to hash are 2, 10 or 20 bits of a BBS output I think this is not
>a big problem.
>If I take more bit I violate the strength of BBS if somebody can examine the
>output of BBS. But if I hash its output nobody can learn about BBS.
>I don't use the whole BBS state because the result is very bad.
Really? That would be an interesting result. If BB&S generates a
poor sequence when the whole state is used (that is, when treated like
a normal statistical RNG), the main effect of the required few-bit
sampling may be to hide this situation from analysis.
I'm not sure that any defects would be exploitable after bit-sampling,
but *any* RNG can be bit-sampled, and if that does not improve
strength for the normal RNG, it should not improve strength for BB&S
either.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: RSA public exponent
Date: Mon, 04 Sep 2000 05:42:40 GMT
Paul Schlyter wrote:
> Bob Silverman wrote:
> > Mack wrote:
> > > the current recommendation is a public key length
> > > that is greater than 1/4 the length of the modulus.
> >
> > No. This is the SECOND time you have made this same wrong
> > pronouncement. It is the *private key* which must be long, and
> > NOT the public exponent.
>
> He didn't claim the private key must be short, did he?
I don't think you followed the flow. Bob Silverman is
pointing out that Mack mis-stated the current recommendation.
> Why can't both the private and the public exponents be long btw?
> Suppose I would want both the private and the public exponent
> to be of the same length as the modulus - how would I do that?
They can. The point is that given the current
best-practice on use of RSA, the sizes you are supposing
are slower for public key operations and have no known or
expected security advantages.
How would you do that? I don't understand the question.
What is stopping you?
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: Capability of memorizing passwords
Date: Mon, 4 Sep 2000 06:36:09 GMT
Mok-Kong Shen wrote:
> memorize random passwords (commonly 8 characters). I am
> very surprised to read in a magazine that the record of
> memorizing a bit sequence, given a time of 30 minutes, is
> 2745 bits! So brain's capability of processing random
> stuffs doesn't seem to be too bad after all.
The trick is to impose a structure on it that is easier
to remember. It takes some training to do well, though --
it's certainly *not* anything you impose on ordinary users.
--
Anders Thulin [EMAIL PROTECTED] 040-10 50 63
Telia Prosoft AB, Box 85, S-201 20 Malmö, Sweden
------------------------------
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: I need an algorithm to determine the center of gravity for;
Date: Mon, 4 Sep 2000 06:41:31 GMT
[EMAIL PROTECTED] wrote:
> I need an algorithm to determine the center of gravity for;
Try Gonzales-Wintz: Digital Image Processing.
--
Anders Thulin [EMAIL PROTECTED] 040-10 50 63
Telia Prosoft AB, Box 85, S-201 20 Malmö, Sweden
------------------------------
From: "Michal Kvasnicka" <[EMAIL PROTECTED]>
Subject: Re: cryptology software
Date: Mon, 4 Sep 2000 09:05:20 +0200
Have a look at the:
http://www.maths.usyd.edu.au:8000/u/magma/MagmaInfo.html
Michal
"Stou Sandalski" <tangui [EMAIL PROTECTED]> píše v diskusním příspěvku
news:HiZr5.8341$[EMAIL PROTECTED]...
> Maple is a symbolic algebra package... it might have some use in crypto...
> but thats not what it was originaly designed to do... (as far as I know)
>
> stou
>
> "Michal Kvasnicka" <[EMAIL PROTECTED]> wrote in message
> news:8onp7k$ull$[EMAIL PROTECTED]...
> > I am looking for Maple or Matlab cryptography and cryptoanalysis
software.
> >
> > Thanks in advance for any help,
> >
> > Michal
> >
> >
> > --
> > Michal Kvasnicka
> > [EMAIL PROTECTED]
> >
>
>
>
>
>
------------------------------
From: "Stou Sandalski" <tangui [EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Mon, 4 Sep 2000 01:15:05 -0700
"PROdotes" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> > You don't get it do you? This guy does not want anyone to know what the
> > algorithm is because that's what makes it "so strong". He should have
read
> > a bit more sci.crypt before posting his ridiculous attempts at crypto.
>
> Hey... "if knowledge is power then to be unknown is to be unconquered"
>
> The reason I'm not giving the whole code is that I have done just a part
> of it and think that it still has "to less" combinations.
>
> For now it's just a simple method. First. Scrambel the bytes switching
> randomly two of them using the pass. as a seed and a controler for the
> number of bytes that are swiched. Than convert the file to a "black-white
> picture" and randomly invert some of the bytes. Then the vertical lines
> are mixed up, and then tha same with the horizontal again. The result can
> then be stored as an "grayscale picture" to get some "compersion" on the
> file. so there are ((n*8)!)^2 * n^2 * 2 combinations for scrambling...
> where n is the fix(sqrt(number of bytes)) + 1.
>
> Want some more... got some remarks... want to piss me of... just say it.
HEY EVERYBODY I Got a sick assss crypto method... its unbreakable I SWEAR...
I don't really want to tell you exactly what it is, but get this... I
basicaly take some plain text and use some random transformations to
semi-randomly generate cipher text bits by using huge(!) amounts of
entropicaly large bits scrambled using a quad-trilinear G-Box, which in turn
inverts the non-inverted dirty bits, then calculating f(x) for x^n mod y log
z, and I get like 22.3 X 10 ^ -31337 combinations for scrambling the data...
the crypto is unbrakable EVEN IF YOU HAVE THE PASSWORD!!!!! if thats not
good crypto I don't know what the hell it is! Tomorow I am porting it to
compiled basic for an AS/400, since my atari is way tooo slow to do these
insane transformations... I bet you its unbreakable and crazy... don't fuck
with me people my crypto is LEEET
Stou
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Capability of memorizing passwords
Date: Mon, 04 Sep 2000 09:01:44 GMT
S. T. L. wrote:
>
> <<I suppose not everyone knows your technique. Could you
> give an example that works, i.e. automatically translates
> back to the arbitrarily given 128 bit?>>
>
> Well, um, I'd expect that a program would be able to accept
> arbitrary-length passphrases, no? Translating from 128 random bits to
> a 10-word passphrase is as simple as breaking it up into chunks of
> bits and looking up the words in a list of 8,192 words (or however
> many you have; I used 8,192 words). Doing the reverse would require
> the same list.
Wouldn't it be faster to simply hash the string for translating your
text passphrase into a 128 bit value, than looking up the words in your
list? I mean, having a passphrase generator as a seperate program seems
like a good idea, to me. Once that's done... why increase the size of
the program that uses the passphrase by including the list?
Of course, I personally think that if we're allowing arbitrary length
passphrases, and want 128 bits of entropy in that passphrase, it would
be much better to display a running count of the entropy of the
passphrase textfield, and require that it have at least 128 bits of
entropy.
This means that users can enter *any* sufficiently long string as a
passphrase, so that individual users can pick things that are most
easily memorizable to themselves. I might, for example, use "Twas
brillig and the slithy toves did gyre and gimble in the wabe", which is
something I could easily remember, since I had to memorize it in high
school for something... Admittedly, a human who knows part of it can
VERY easily guess the rest of it, but a computer couldn't, unless that
particular poem is part of it's dictionary/database. If I'm worried
about such Jabberwocky being in the cracker's database, because of how
common it is, I could just choose something more obscure, eg "In a hole
in the ground, there lived a hobbit." which is perhaps less likely to be
in a codebreaker's dictionary. Someone who knows me, and what I read
*might* be able to guess my passphrases, but a computer probably
couldn't.
--
... perfection has been reached not when there is nothing left to
add, but when there is nothing left to take away. (from RFC 1925)
------------------------------
** 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
******************************
