Cryptography-Digest Digest #633, Volume #12 Thu, 7 Sep 00 19:13:01 EDT
Contents:
Re: R: R: R: R: R: R: R: R: Test on pseudorandom number generator. (Terry Ritter)
Re: RSA patent expiration party still on for the 20th (Bill Unruh)
Re: Free Upgrade PGP Personal Privacy 6.5.8 - how? (-)
Re: Free Upgrade PGP Personal Privacy 6.5.8 - how? (-)
Re: For those working on the next RSA factoring challenge... (Jerry Coffin)
Re: Ciphertext Randomness/Statistical Tests (Amory Liken)
Singhs Cipher Challenge ("Mike")
Re: Carnivore article in October CACM _Inside_Risks (Roger Schlafly)
Re: Carnivore article in October CACM _Inside_Risks (Paul Rubin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: R: R: R: R: R: R: R: R: Test on pseudorandom number generator.
Date: Thu, 07 Sep 2000 21:31:43 GMT
On Thu, 7 Sep 2000 19:33:17 +0200, in <8p8i47$hjf$[EMAIL PROTECTED]>,
in sci.crypt "Cristiano" <[EMAIL PROTECTED]> wrote:
I doubt these remarks are doing any good, and also that anyone else
possibly can have any interest in them. Since this has gotten to be
decidedly not fun, and since I am not being paid for tolerating not
fun, it is time for me to stop.
>[...]
>I have 234 p-values each time (so the expected value for each class is
>234/11=21,27).
>For each class I count how many times "p-values found" are below or above
>21,27.
>
>Diehard test performed 100 times for MT19937:
>
>p-values below / above 21,27
>0,05 44 56
>0,15 38 62
>0,25 36 64
>0,35 32 68
>0,45 35 65
>0,55 34 66
>0,65 34 66
>0,75 27 73
>0,85 39 61
>0,95 14 86
>1,05 100 0
>
>Do you mean this? If so, must I discard p-values=0 or =1?
First, I would find it not useful to collect the values from different
tests in this way. If we do that, even if one test does indicate a
problem, that result will be hidden by tests which do not find a
problem. We need to look at each test separately.
And the issue is not about discarding p-values. The issue is that low
or high p-value counts may indicate that a test has found problems.
So then we run other trials with different data to see if those
results are repeatable. If not, we go on to something else.
>> However, an overall p-value mean comparable to the original is not
>> reported.
>
>What is the meaning of "comparable to the original"?
My reason for suggesting 100x as many tests was to get about 10x more
accuracy in the mean. What I would like to see is a "mean of the 50
means," or "the mean of all tests." I would like to see that value
snapping closer to 0.50 the more tests are performed.
>> >If a good generator must give a uniform distribution of p-values,
>reporting
>> >these p-values in a graphical form we must see a triangle.
>>
>> We can report p-values as counts in equal-spaced intervals, as above.
>> Then we "must" see a flat line, as above. There is no magic in a
>> cumulative distribution.
>
>No.
Yes.
>If I sort all p-values (like Diehard in KS test) and then I report these
>p-values in a graphical form, we must see a triangle, or rather, a line from
>(0,0) to (11699,1) (a triangle with the axis).
>
>y ^
> |
> | * (11699,1)
> | *
> | *
> | *
> |*-------------------------->
> 0,0 x
>
For looking at the data, that's probably even better than comparing
bin counts. But as far as I know, there is nothing particularly magic
about that line. It is just one way to see problems in the flat
p-value distribution.
The p-value distribution is "flat" in the sense that any particular
p-value should be equally likely to be anywhere in the range of x
values (i.e., 0..1). So any particular subset of that range should
collect about the same number of p-values as any other subset of the
same size.
Your evaluation function appears to be the sum of the squares of the
individual differences of sorted p-values from either a best-fit or
0..1 line. I guess the main problem with that is understanding what
differences in that line mean in a numerical statistical sense. We
expect that any measured set of p-values will be non-ideal, so if we
are going to use the line concept, we need to have some sort of way to
evaluate the distribution of line results. The usual answer is to use
a K-S test. That is what it does.
>[...]
>The KS test is included in DiehardC (is a stand alone test, I hope its
>developper has tested it).
>The KS test is a problem also for me. This is the reason for which I try to
>use other methods (like the interpolation). It seems to work fine: when a
>test fail big (like URAND) the error of the straight line is about 6-8, when
>a test result is good, the error is only .03-.06. In this way the difference
>between the ideal distribution and the real distribution is more
>understandable.
I can only say that I am unaware of a statistical investigation of the
numerical line technique for p-value evaluation, beyond K-S itself.
If such exists, I would like to hear about it.
>> >> I assume the K-S result is a p-value,...
>> >
>> >Yes; from DiehardC documentation: "After all the tests are performed,
>you'll
>> >see a summary of the 160 or p-values [?], and a KSTEST of all of them."
>(I
>> >think there is a mistake because the p-values are 234).
I would apply K-S across the multiple trials of each particular test,
not all the different tests. So if Diehard works some other way, and
I were to use it, I would change it, or manually excerpt the results
and perform a separate K-S computations. But from a casual look at
one of the tests, it seems like K-S *is* used on individual tests.
Perhaps a final level of K-S is used on those results.
>[...]
>> >[...]
>> >Now I'll be more precise. URAND pass very well frequency (p= .95489),
>>
>> Actually, that's high enough to wonder about. A value that high
>> should occur about 1 time in 20: Are we just that lucky?
>
>All p-values given by "my" tests (I wrote all tests but Diehard) are the
>integral of the chi-square curve (with a given d.o.f.) from X² to infinite.
>In other words it represent the terminal (right) part of the area of the
>curve (I think this is not the same as in Diehard). This is called
>significance level.
>Only Autocorrelation and Maurer's test follow (approximately) a normal two
>tailed distribution.
It appears that we are not communicating.
The existence of a p-value of .95+ is something which had better occur
only 1 time in 20 on "good" data, or we are not using the same concept
of p-value. Exactly the same issue occurs if we consider the a "q"
value, typically 1 - p, or .05-; that too should occur only 1 time in
20. No matter what you call it, the problem is that the value should
be somewhat rare. Yet we have it.
Since the value .95 did in fact occur, it is reasonable to ask whether
additional trials also have a high value. If so, we may have found a
problem. This is exactly the sort of indication we may get from a
test which has found a problem, so we need to check it out.
>> >Serial
>> >(p= .78908), Poker (p= .39018) and Runs (p= .91267); fail Autocorrelation
>> >for distance =32 (p=0)
>>
>> That seems like a pretty clear result, but does it make sense? I
>> don't know. I would not be surprised to see a RNG fail this test, but
>> from my remote location, I see no reason why we would have such strong
>> correlation at this particular distance (and no shorter).
>
>Do you think is not useful to see autocorrelation up to 200-300 bit?
I think autocorrelation is a great test, and would take it as far as I
could afford to go, at least thousands of bits.
>For example I'm testing a Tausworth generator (s[i]=s[i-250]^s[i-147]) it
>seems very good! But if it is not seeded very well it always fail
>autocorrelation at 21 bits and around at 194.
Why? Do you have some theoretical reason to believe that correlation
should occur at this distance? If not, why do you blame the
generator?
I could believe correlation at 250, 147, or even 103. Otherwise,
something may be wrong, and I will have to learn something new. I
would not trust some number which says the generator is bad without
understanding why.
>I think that a continual bad autocorrelation at the same bit distance (even
>100-200 bits) may be useful to find some weakness of a generator or in the
>seeding too.
It may be equally effective in finding implementation and test-fixture
errors.
>[...]
>For example, for better understand the meaning of KS, by using kstest() in
>DiehardC I had filled a vector of 100 double ("real" in DiehardC) with
>number
>from 0 to i/99 (0<=i<=99).
>KS result is .113585762310732. What is the meaning?
If we assume the K-S result is a p-value, the meaning *should* be that
such a regular sequence is improbable (occurring about 1 time in 10).
But I would expect the data as described to be much *more* improbable
than that. I thus suspect that something about this is not working as
one might expect.
>
>> >I'm not a mathematician, I'm a programmer.
>> >What it is important for me is to have tools to help me in my job. Now my
>> >job is to find a PRNG and a cryptographically secure PRNG.
>> >So, if Maurer can help me (even only in some case) to find weakness why
>not
>> >use it?
>>
>> Using or not using the Maurer test is not the issue. But when Maurer
>> picks up something the others do not, my first thought is that
>> something is strange about the test environment.
>
>If a bits sequence fail a test for bits sequence I think that the sequence
>is bad, not the test!
You think wrong. Tests have requirements, which if not met, remove
meaning from the results. And test implementations can be wrong, and
so must also be tested.
>I use the test to check the sequence not the sequence to check the test.
>When URAND (32 bits generator) failed autocorrelation test at 32 bits and 96
>bits (32*3 bits), I said "well, URAND is bad" not "well, autocorrelation
>test is bad".
Say to yourself: "Something about my test set-up may be bad."
>In most cases Maurer's test seems to give similar results to Diehard but
>much more readable and understandable (at least for me).
>Your rage against Maurer's test seems a little bit "suspect".
It is your acceptance of Maurer's test under these conditions which is
more than 'a little bit "suspect."' The obvious indications are that
something is wrong in the test system. Yet you continue to ignore
those indications apparently because you like the results from that
test. That is "suspect."
I have shown chapter and verse where he specifically disclaims his own
test for pseudorandom use, yet you ignore his words. HAC specifically
mentions that Maurer's test needs a lot of data compared to other
tests; you apparently think that is fine. And I have never seen
Maurer's test find problems my other tests have missed.
Any time Maurer's test finds something other tests do not, the
universe is telling you something: It is time to re-check the code.
>Maurer's test seems a little "strange" when I test the whole state of a BBS
>generator (see BBS generator below).
>
>> >> >[...]
>> >> >What you say seems to be what is in HAC.
>> >>
>> >> And where would that be, exactly?
>> >
>> >Page 182:
>> >"(iv) Runs test
>> >The purpose of the runs test is to determine whether the number of runs
>(of
>> >either zeros or
>> >ones; see Definition 5.26) of various lengths in the sequence s is as
>> >expected for a random
>> >sequence.".
>>
>> First of all, the runs test described in HAC only works on bits, not
>> larger values. In contrast, Knuth II, section 3.3.2 describes the Run
>> test (runs up / runs down) which is valid for large integers and
>> reals. I have addressed the distribution for small integers. The
>> Diehard implementation is in fact runs up / runs down, based on 32-bit
>> integers, and not the HAC definition.
>>
>> Restricting runs to bits only is a serious loss. Many RNG's produce
>> integer values, not individual bits, so analyzing the values as bit
>> sequences may not have much meaning.
>
>I have seen runs test in DiehardC. It count the runs up / runs down from 1
>to 5 and those of length greater than or equal to 6 (like in FIPS PUB
>140-2).
>Its implementation seems a little "strange":
>
> for 2 times do:
> for 10 times do:
> take 10000 32 bits numbers and count runs;
> from these count, compute 1 KS for 10 up and 1 KS for 10 down;
>
>So at the end of runs test we have 4 p-values.
>It is not better compute 1 p-values for up and 1 for down from the whole
>file of 32 bits numbers?
If you feel like any test is improperly implemented in Diehard, one
way to address the problem is to do your own implementation from the
original reference, then compare the results.
>Anyway I have runs test for bits and number of 32 bits.
>Do you think may be useful to extend Diehard runs? And for blocks of x bits
>(not only 32)?
>In this case how can I do to calculate the significance level?
There are various ways; I usually take the easy way: We know the
probability of any particular run length, assuming "good" data, so for
data of a given length we can expect a certain run count for each
length. We can evaluate these by chi-square, and I would arrange to
have at least 10 in each bin. What this does is compare the expected
distribution to the experimental distribution, and deliver a p-value
representing the probability of obtaining such results with "good"
data. That is basically what we get from any test. But Diehard
appears to have a more complex evaluation.
>[...]
>In fact runs test (as in HAC) seems to give results almost useless.
>On the other hand, I don't have any comparison on the utility of runs test
>of Diehard.
If the RNG produces bits only, then testing bits makes sense. We can
expect to make finding RNG problems more difficult when we "block" or
"decimate" values before testing.
>[...]
>If the security of BBS is even more strong than factoring n, a 1024 bits
>modulus is very good in most cases!
Where is your reference for that?
>From the recent discussion on sci.crypt, it appears that BB&S is in
fact *less* strong than factoring N unless we use much larger values
of N than 1024.
>[...]
>I don't think that if I de-skew any sequence and the result is good, I must
>worry about that.
Then all of this testing must be useless for you: All you have to do
is to encrypt each value from each generator and you will have a good
sequence, independent of whether or not each RNG is good. So why
bother testing the RNG's?
>The BBS give a far good sequence (may be good or sometimes bad), de-skewing
>it I get a far good sequence (not always), where is the problem?
The problem is that a correctly implemented and correctly tested BB&S
sequence should gain *nothing* from "de-skewing." But since your
tests show that something *is* gained, the obvious implication is that
you do not have a correctly implemented and tested BB&S generator.
And that means either that your faith in your implementation of BB&S
is misplaced, or that your faith in your testing is misplaced.
>You persist to say that my test have troubles or BBS is bad implemented, but
>I've never read that if I apply to a BBS generator a SHA-1 and then unbias I
>*must* get a bad sequence.
You persist in misunderstanding the issue. You fail to recognize the
warning signs of an improper implementation. Quit talking about how
that can't possibly happen to you, and find and fix the problem.
>> >To obtain the sequence to test I collect each bit of x in a buffer (the
>> >sequence). When I have collected all bits of x, I recompute (x*x)%n and
>> >continue the collection.
>>
>> That is wrong: You should be doing the modular reduction before
>> collecting data. Many or most RNG's require modular reduction, and
>> that should always be fully completed before data are taken.
>
>If my intent is to test a bits generator with tests for bits sequence, to
>use the whole state as a bits sequence is not wrong because I only use the
>bits really presents in the state. In other words, if I use a PRNG with a
>modulus equal to 0x12345678 (29 bits) and I take its state as a 29 bits
>number it's wrong because many bits will never be present in the state. So
>if its state is 0x123 this number need a modular reduction.
>On the other hand, if I use the same generator as a bits generator, the
>state of 0x123 must be taken as is because the bits that I take are:
>100100011 and these are all "valid" bits.
How do you *know* those bits are valid? Have you shown that they have
the same value before and after modular reduction? Do you have a
proof? If not, what do you imagine that are you talking about?
If you are going to make another BB&S step, you will have to perform
the modular reduction anyway. So no added computation is involved,
except perhaps on the last step. So why would you insist that doing
it wrong is just as good as doing it right?
The only reason to use slow BB&S is to get a theoretical basis for
strength. But the only way that can possibly work is if the
implementation is exactly that which is expected, not some other thing
which is not the same. Your results do not come from BB&S but from
something else which you nevertheless *call* BB&S.
>[...]
>I don't want to use a BBS like a number generator. I need it only for bits
>generation, so I test the generator as a bit generator with tests for bits
>(those in HAC).
>Do you remeber:
>"For my curiosity, I test such a sequence [from a BBS generator] with
>Diehard (ok it's bad!).
>[...]
>It seems that some information is given also by Diehard."
>(using a number test with bits sequence may be useful, at least in some
>cases).
There really is no point in discussing details of tests on a generator
which clearly is not implemented correctly.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RSA patent expiration party still on for the 20th
Date: 7 Sep 2000 21:36:51 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (S. T. L.) writes:
>/*You would only be able to use RSA after Sept 20 on stuff that
>was not developed befor that date either. You would have violated the
>patent if you had used ( developed) before that date.*/
>What if you wrote something before Sept. 6 (or 20), but never gave it to anyone
>else but yourself? Would that prevent one from releasing it publicly after
>Sept. 6 (or 20)?
We are getting into the wild blue yonder here. It depends on why you wrote it. If you
could argue that it was for "research" purposes, then I believe that the patent law by
precedent allows such use. (After all patents are published precisely to allow others
to
improve on them). However if it was for commercial or non-commercial use ofthe patent,
then they could take you to court. They would have to prove that you so made use of it
befor that date. Thus writing dates on the code from befor Sept x, in the released
commercial code would be strong evidence that you did use it. Of course one would then
have to assess damages, and they presumably would be small. Would MIT actually go after
you for such a violation? The answer to that question I leave as an exercise for the
reader.
------------------------------
From: - <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Free Upgrade PGP Personal Privacy 6.5.8 - how?
Date: Thu, 07 Sep 2000 17:11:49 -0500
On Thu, 07 Sep 2000 12:04:35 GMT, [EMAIL PROTECTED] wrote:
>In article <jjtherrien-8DF129.01245107092000@news>,
>
>[snipped]
>
>> ______________
>>
>> NAI announced present owners could get a free upgrade to PGP Personal
>> Privacy 6.5.8, however we would have to get it from McAfee. Well,
>what
>> I expected from previous experience happened.
>>
>> I submitted my request to <[EMAIL PROTECTED]>, and McAfee
>replied
>> that I can get a free download [PGPfreeware] from "www.pgpi.org" --
>the
>> usual nonsense!!!
>>
>> I have repeated the request, explaining to them the difference
>between
>> the two (to the people I bought it from!!?!&?%) -- with a copy to
>NAI. I
>> have not as yet received a reply to my second request.
>>
>> *** Has any one been able to get the free copy we are owed to upgrade
>to
>
>I'm curious as to why you would think you are "owed" something. While
>some minor software upgrades are generally provided at no charge, seems
>to me that's at the good will of the publisher....not because someone
>is owed something...
Assholes like you should get kicked in the balls twice a day until they
learn some manners and stop being argumentative jaggoffs.
>
>
>
>> PGP Personal Privacy 6.5.8? If so please tell us how? Details
>please.
>>
>> *** Are others trying to or about to try to get the free upgrade? We
>> should perhaps all get together on this, and try to solve this
>problem
>> once and for all.
>>
>> I am really fed up with the bureaucratic run-around and confusion
>inside
>> NAI and McAfee on this. NAI should solve the problem with McAfee
>before
>> telling us to get it from there, and provide us with the name of
>someone
>> in McAfee who understands the problem and their telephone number
>(email
>> address, fax number, or whatever).
>>
>> It is not up to the paying customers to solve their internal
>problems -
>> and they obviously do have serious ones. The onus to provide
>upgrades
>> (especially for correcting serious errors like this one) lies
>normally
>> with the developer (NAI), rather than a reseller (McAfee). The
>> developer should at least verify that the upgrade is indeed available.
>>
>> If they had the good sense of issuing registration numbers for retail
>> commercial software (as other developers do, including shareware
>> authors), we would not have this type of problem.
>>
>> As every shareware author does, they could just post the upgrade on
>the
>> Web, and only those with a valid registration number would be able to
>> use those downloads without paying.
>>
>> Or simply ask people for their registration number when they try to
>> download. Problem solved.
>>
>> Cheers,
>>
>> Jacques
>>
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: - <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Free Upgrade PGP Personal Privacy 6.5.8 - how?
Date: Thu, 07 Sep 2000 17:17:42 -0500
On Thu, 07 Sep 2000 09:15:21 GMT, [EMAIL PROTECTED] wrote:
>one short phrase:
>
>ftp://zedz.net
>
Is the "retail version" on that page (10435KB) gratis, or should one
download the "Personal Privacy" file (8695KB)?
It's too big of a download at 28.8 to download the wrong one.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: For those working on the next RSA factoring challenge...
Date: Thu, 7 Sep 2000 16:22:31 -0600
In article <8p4suq$och$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Hi,
>
> I have been reading this post and i've had problem following. Could
> anyone describe memory bandwidth for me and how it affects peformance
> and the like? You can be a bit technical if needed but not too much as i
> don't have an electronics background, only software development.
Memory bandwidth is simply how fast you can read/write data from/to
memory. It becomes critical in the case of NFS because the NFS works
with a HUGE amount of data -- far to much to fit into a cache
(assuming you're factoring a number big enough to justify using the
NFS in the fist place). The NFS doesn't use this data in a nice,
predictable pattern such as reading serially through memory. The NFS
does not do a lot of work with a small amount of data before moving
on to work with other data.
Typical SDRAM is considerably slower on the first access to a page of
memory than on subsequent pages. The non-serial order of access in
the NFS means that MOST accesses will be "first" accesses in a page,
so nearly every access suffers the penalty. The fact that only a
small amount of work is done on each piece of data before moving on
to work with other data prevents the on-board cache from providing
much benefit either.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (Amory Liken)
Subject: Re: Ciphertext Randomness/Statistical Tests
Date: Thu, 07 Sep 2000 22:27:25 GMT
John Myre <[EMAIL PROTECTED]> wrote:
>Quite so. Indeed, the only counterexamples so far are to
>add data which carries no plaintext information at all.
How about "ascii armor"? Any PGP encrypted message posted here on Usenet
can certainly be compressed.
--
"Amory Liken" is actually 1678 904523 <[EMAIL PROTECTED]>.
01234 56789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
Reply-To: "Mike" <.>
From: "Mike" <[EMAIL PROTECTED]>
Subject: Singhs Cipher Challenge
Date: Thu, 7 Sep 2000 18:36:59 -0400
Does anyone know if the egroup http://www.egroups.com/group/CipherChallenge
is still active?
I joined it about 5 weeks ago, but the moderators still haven't approved me.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,alt.security,talk.politics.crypto
Subject: Re: Carnivore article in October CACM _Inside_Risks
Date: Thu, 07 Sep 2000 15:40:19 -0700
Larry Kilgallen wrote:
> Existing devices do this, using an RSA digital signature. ...
> ... What it has is that chip, which is sufficient
> if we are content with it not being duplicated (it can be moved, but
> not duplicated).
Yes, there are things like smart cards that will do RSA signatures,
and attempt to keep the private key from being accessed and copied.
However, nearly all of these will yield the private key to a
sophisticated attacker who looks at side channels. The copy-proof
signing device is just not a commercial reality yet.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Crossposted-To: comp.security.misc,alt.security,talk.politics.crypto
Subject: Re: Carnivore article in October CACM _Inside_Risks
Date: 7 Sep 2000 23:00:19 GMT
Roger Schlafly <[EMAIL PROTECTED]> wrote:
>Yes, there are things like smart cards that will do RSA signatures,
>and attempt to keep the private key from being accessed and copied.
>However, nearly all of these will yield the private key to a
>sophisticated attacker who looks at side channels.
That appears to be true of smart cards, but certainly not of more
sophisticated modules. Crypto modules these days can be made immune
to any type of passive attack (i.e. any attack that doesn't involve
physical tampering). If you have to drill holes in a device to access
internal signals, that's no longer a side channel.
>The copy-proof signing device is just not a commercial reality yet.
Probably true, but copying can be made awfully difficult.
------------------------------
** 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
******************************
