Cryptography-Digest Digest #548, Volume #9 Fri, 14 May 99 00:13:03 EDT
Contents:
Re: Fast random number generator -- Need C code for simulation
([EMAIL PROTECTED])
Re: Fast random number generator -- Need C code for simulation ([EMAIL PROTECTED])
Re: Fast random number generator -- Need C code for simulation ([EMAIL PROTECTED])
Re: PGP 6.0/6.2 for Macintosh ([EMAIL PROTECTED])
Re: On Contextual Strength (Bryan Olson)
Re: Fast random number generator -- Need C code for simulation (Mike McCarty)
Re: Random permutation ([EMAIL PROTECTED])
Re: TwoDeck solution (but it ain't pretty) (Boris Kazak)
Toy Round Function ([EMAIL PROTECTED])
Re: Hello I am paper, please read me. ([EMAIL PROTECTED])
Re: TwoDeck solution (but it ain't pretty) ([EMAIL PROTECTED])
Re: Lemming and Lemur (D. J. Bernstein)
Re: Fast random number generator -- Need C code for simulation (John Savard)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Fast random number generator -- Need C code for simulation
Date: Thu, 13 May 1999 23:16:14 GMT
Try a GFSR?
Like so
if (GFSR & 1) {
GFSR = (GFSR ^ 0x80000057) >> 1
return 1;
} else {
GFSR >>= 1;
return 0;
}
It returns one bit, but is reasonably fast. This is off the top of my
head from AC, so you may want to check first. It will make 2**32 - 1
bits or about 2**27 random 32 bit numbers. (134217728)
Tom
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
Date: Thu, 13 May 1999 20:20:52 -0400
From: [EMAIL PROTECTED]
Subject: Re: Fast random number generator -- Need C code for simulation
Terry Ritter wrote:
>
> On Thu, 13 May 1999 14:09:44 -0700, in
> <[EMAIL PROTECTED]>, in sci.crypt
> [EMAIL PROTECTED] (catfish) wrote:
>
> >I've been following this interesting thread and wonder if there's some
> >fast C code for a long-period RNG.
>
> Maybe you can use something from:
>
> http://www.io.com/~ritter/NEWS4/HARDRAND.HTM
>
Terry,
Your distallation of that thread is quite well done. I did not realize
how intense it was until I reviewed your organization of the material.
Well done and thank you.
During my review I was struck by a comment from Juola that really hits
hard. We should make it the koan of sci.crypt:
I can't prove "randomness", only the apparent absence of LOTS of
randomness.
- Patrick Juola, 28 Jan 1999 11:23:20 -0500
------------------------------
Date: Thu, 13 May 1999 20:32:38 -0400
From: [EMAIL PROTECTED]
Subject: Re: Fast random number generator -- Need C code for simulation
Terry Ritter wrote:
>
> On Thu, 13 May 1999 23:16:14 GMT, in <7hfmft$2gq$[EMAIL PROTECTED]>, in
> sci.crypt [EMAIL PROTECTED] wrote:
>
> >Try a GFSR?
> >
> >Like so
> >
> >if (GFSR & 1) {
> > GFSR = (GFSR ^ 0x80000057) >> 1
> > return 1;
> >} else {
> > GFSR >>= 1;
> > return 0;
> >}
> >
> >It returns one bit, but is reasonably fast. This is off the top of my
> >head from AC, so you may want to check first. It will make 2**32 - 1
> >bits or about 2**27 random 32 bit numbers. (134217728)
>
> That is an LFSR, and the bit-level implementation will be relatively
> slow.
>
> A GFSR is the use of a separate LFSR for each bit of the result. This
> produces better "randomness," and makes use of the ability to do fast
> word-wide exclusive-OR's. Another advantage is the ability to use
> vastly larger amounts of state.
A particular implementation called R250 is available in source code.
But all such paralel LFSR exhibit perfect correlation between the bits
of each word of outout, so you get a period of 2^words instead of
2^bits.
>
> A generalization of that idea is the Additive RNG from Knuth which I
> have used widely. This is still a very structured RNG and so must be
> "nonlinearized." Combining the result from several RNG's is popular,
> as is combining really-random results with an RNG.
>
> For statistical use, I think several tested very large generators are
> available on the web. Try my randomness links:
>
> http://www.io.com/~ritter/NETLINKS.HTM#RandomPseudo
>
> ---
> Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
n
------------------------------
Date: Thu, 13 May 1999 20:48:39 -0400
From: [EMAIL PROTECTED]
Subject: Re: PGP 6.0/6.2 for Macintosh
Ask this question in alt.security.PGP
Lee Kanner wrote:
>
> Apologies if this is off-topic; this is the closest newsgroup I can find.
>
> PGP 6.0 seems to have the property that its menu bar icon vanishes when I
> launch any Internet application, e.g. Eudora, Netscape, or NewWatcher.
> PGP 5.0 and 5.5 did not do this. I called the company's technical support
> about this and they professed not to even be aware of the behavior. But
> they told me that I did not have the latest, that the latest was 6.2. I
> went back to the download site (Norway) and the link was labeled 6.2, the
> .sit file called itself 6.2, but when expanded, it became version 6.0,
> dated August, 1998.
>
> This vanishing of the menu item is a nuisance, because encrypted e-mail
> that does not use the plug-ins cannot be conveniently decrypted in situ; I
> have to copy it to a document belonging to a non-Internet application
> before I can decrypt it. I suppose I could try putting an alias to PGP
> Tools in the Apple Menu.
>
> Does anyone know whether version 6.2 solves this problem and how to get 6.2?
>
> Herb
>
> --
> Herb and/or Lee Kanner
> For e-mail reply, remove "NO-SPAM"
>
> [EMAIL PROTECTED]
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: On Contextual Strength
Date: Thu, 13 May 1999 17:42:19 -0700
Terry Ritter wrote:
> Bryan Olson
> >Terry Ritter wrote:
> >> Indeed: Since we do not know x, we cannot assume we know that value.
> >> The implication of this is that we cannot trust any cipher.
> >
> >So your "contextual strength" is bankrupt.
>
> Sorry.
>
> >We not only can't
> >prove it, but if it's false the evidence to show it's false
> >need not exist.
>
> What?
Carefully explained below.
> >It lacks both mathematical proof and scientific
> >testability.
>
> That seems to be a projection of the faults of your idea of strength,
> which also has no mathematical proof, and also cannot be tested with
> respect to secret opponents, and they are the only ones we care about.
> Strength values from cryptanalysis which does not show a practical
> break are irrelevant to real cipher use.
My idea of strength is independent of secret opponents. Recall
what my notion is:
> > >To me, a strong cipher is one for which there is no tractable
> > >break.
I want to reject ciphers if there exists a tractable break,
without regard to whether an adversary may know or discover that
break.
> >If, on the other hand, we consider a cipher strong
> >if and only if it has no tractable break, at least the hypothesis
> >is falsifiable and we're playing the same rules as our adversary
> >in looking for the evidence that would do so.
>
> You mean we can assume a cipher has some strength unless someone can
> prove otherwise?
No. I mean what I wrote.
> This arrogant misuse of logic is at the root of many
> problems in cryptography and cryptanalysis, because it seems to be the
> way science is normally done. But in cryptography, it would have us
> believe that only work in the published academic literature counts,
> when in fact what really counts is what our opponents can do. Just
> because the academics have some level of skill does not mean our data
> are secure to that level of strength. Any strength value which does
> not take our opponents into account is irrelevant to actual use.
Try and follow: my notion of strength allows valid scientific
hypothesis that a cipher is strong; the hypothesis is falsifiable.
If the cipher is not strong then there necessarily exists evidence
that proves it is not strong.
If a cipher is strong under the idea I proposed, then _no_
adversary can break it since a break does not exist.
> Demanding that our opponents publish their attacks before we will
> consider our ciphers weak is simply insane.
Which makes "contextual strength" unscientific. If we define
a cipher as strong if our adversaries can't break them, then the
only evidence that could refute the hypothesis that a cipher is
strong must come from our adversaries.
> If the opponents break
> the cipher and keep quiet, we will use that cipher again and again and
> again, and all that time all the academics will claim the cipher must
> be strong because nobody has proven otherwise. That is not science,
> that is arrogant ignorance.
So we must reject a model that defines strength in terms of the
abilities of our adversaries.
> Cryptanalysis delivers only an upper bound to strength. We do not
> know "the" strength, and I argue that there is no one strength, but
> instead of range of strengths depending upon what is known by each
> opposing group.
And thus:
> >Your proposal, unlike the conventional method, is unscientific.
> >You can't prove contextual strength, and without the help of
> >your adversary you can't get the evidence that would disprove it.
>
> And you have neither proof nor evidence for the real strength of your
> system either. You just have a value which is the current delusion
> for strength from cryptanalysis.
How many times do we have to repeat the same thing? Neither
notion supports proof of strength. The notion I propose is
scientifically defensible, yours is not.
> >No one that I've seen has disagreed that we lack mathematical
> >proof of computational security. No one disagrees that we can't
> >rigorously quantify the security of our systems. Prove the
> >security of your proposal and you'll have a point.
>
> I think I'll wait until you prove your alternative first.
Yes, you can hide your head in the sand. Neither alternative allows
formal proof of strength. Over and over, people have shown that the
conventional practices have decisive advantages over you alternatives,
and then you point out that their method lacks mathematical proof.
Yes we understand, conventional methods are tied with yours in that
one way; that's why we consider other criteria.
A couple years ago there was an interesting April Fools post: it
said a Russian mathematician had proven factoring to be tractable,
but that the proof was non-constructive. That is, it didn't show
how to factor efficiently, only that an efficient algorithm exists.
Under the absolute notion of cipher strength that I propose, such
a proof would imply that RSA is weak. Under an adversary-relative
concept, it would imply nothing about the security of RSA.
--Bryan
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Subject: Re: Fast random number generator -- Need C code for simulation
Date: 13 May 1999 23:56:32 GMT
In article <[EMAIL PROTECTED]>,
catfish <[EMAIL PROTECTED]> wrote:
)
)I've been following this interesting thread and wonder if there's some
)fast C code for a long-period RNG.
)
)I'm doing a simulation model where many millions of random numbers are
)used. These are now generated by the (Microsoft) C rand() function. The
)nature of the simulation is that the sequence of numbers should be
)random, ie, not repeated, because what happened earlier influences the
)current state of the model. The rand() function returns an integer
)between 0 and 0x7fff (32767). I think rand() is a 16-bit function, and
)suspect that I get many repetitions during a run. If so, I may be running
)the same simulation again and again in one run without realizing it.
This is likely the case.
A simple way to make a very long period rng is to use shuffling. Store
50 or so on the first call. Then on each succeeding calls, use the
previously returned random number mod the size of the stored array to
pick the next one to return. Fill that cell with a newly gen'd rng.
Mike
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel <- They make me say that.
------------------------------
Date: Thu, 13 May 1999 20:39:53 -0400
From: [EMAIL PROTECTED]
Subject: Re: Random permutation
Bryan Olson wrote:
>
> [EMAIL PROTECTED] wrote:
> >
> > Bryan Olson wrote:
> > This algorithm is quite similar to the single-bit routine suggested by
> > hrubin. So many of the comments in that thread apply here.
>
> Quite right. Myself, Dr. Rubin and Mr. Shen discussed that routine
> in a thread a few months ago. I posted the algorithm mostly to
> remind Mr. Shen of the technique.
>
> Alas, there's a flaw in my procedure. We wouldn't want to generate
> a number from 0..15 if endRange is 16!/8 or more. We'd want to use
> the first bits and save the others.
>
> > While the utilization of the fundamental source of random numbers looks
> > to be minimized the overall algorithm suffers horribly as N increases.
> > While the time scales as you described the space requirements scale
> > exponentially on N.
>
> That's not true. The space to store N! is about N lg N bits.
Damn. You are right. I screwed up.
Shouldn't try to think and type at the same time! :-)
> Since the request seemed to imply an explicitly listed permutation,
> Theta(N lg N) space is the best possible.
>
> > Since the original post was aimed at efficiently selecting from the
> > range 0..N-1 in order to implement a classic in-place shuffle, it is
> > appropriate to consider avoiding multi-precision operations.
>
> The question had a fixed N, namely 16. Below is the routine in
> Python, using the library random number generator to produce single
> bits. On my old Pentium-Pro 180, it handles 16! in the blink of an
> eye, 256! in well under a second, and 1024! in about four seconds.
>
> So I agree that it uses a lot of computation, but for many cases of
> interest it's entirely practical.
It seems our tastes differ. Since this is an issue of preference rather
than correctness I cannot really criticize.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: TwoDeck solution (but it ain't pretty)
Date: Thu, 13 May 1999 19:17:51 -0400
Reply-To: [EMAIL PROTECTED]
tomstdenis wrote:
>
> How do you know where I go to school?
>
> Tom
> --
> ---Share what you know. Learn what you don't.---
This is not a question which an aspiring cryptographer should ask
after posting his phone number...
Best wishes BNK
------------------------------
From: [EMAIL PROTECTED]
Subject: Toy Round Function
Date: Fri, 14 May 1999 02:05:21 GMT
This is a simple round function I was playing with. It uses a 10x32 S-
Box and a 32-bit P-box. I used multiplication as the primary source of
diffusion and addition as permutations... Check it out
A and B are 32 bits
+ addition (mod 2**32)
^ addition (mod 2)
>> binary shift right
for r = 0 to rounds
A = A + (((B ^ P[2r]) * S[B >> 22]) ^ P[2r + 1])
(A,B) = (B,A)
next r
Where the first permutation is multiplied by a S box entry. The top 10
bits of B are used as they are the most sensitive to the
multiplication. The lower ~5 bits are weaker, but are used in
subsequent rounds. The double permutation is to hide statistical
dependacies, but probably is more dependant on the multiplication.
Also the last perm. is used to help cover up the bottom bits of the
mult.
The diffusion is lagged by one cycle... Can this be improved? Also it
uses addition, could this use xor and still remain non-commutitive (non
isomorphic)?
This most likely can be broken, so what I would like is pointers, so I
could teach myself (with help... so not by myself) how to start
diff/linear analysis.
Thanks for your time,
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hello I am paper, please read me.
Date: Fri, 14 May 1999 01:52:21 GMT
<snip>
I have read the papers, and have AC. I have a lot of printed material
too. I generally read anything I can find. I stay away from public-
key because it's a little more then me right now. I understand them,
just can't do any better.
About TwoDeck, the security lies within not being able to find the
output of A in B(A(x)), if you don't know A you can't find B.
At anyrate for any N outputs there are N! solutions, and you can't find
the right one until you have log2(N!) blocks (about 1600 blocks when
N=256). There is a considerable amount of work required to find the
one solution that will work.
Am I missing something? Everyone one says it's easy, but I don't see
how. I really want to know.
Given y = B(A(x)), how do you deduce A or B from it?
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: TwoDeck solution (but it ain't pretty)
Date: Fri, 14 May 1999 03:28:20 GMT
> This is not a question which an aspiring cryptographer should ask
> after posting his phone number...
Why not? They have to know where to send the money :)
Just kidding!!!!
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: Lemming and Lemur
Date: 14 May 1999 03:21:07 GMT
David Wagner <[EMAIL PROTECTED]> wrote:
> (Dan Bernstein has apparently done some early, unpublished work on
> slide attacks, under the name of ``teleportation attacks.'')
No, no, I didn't think about these attacks at all before I saw your 1995
S-1 posting. My only contribution is the name ``teleportation attack.''
I seem to recall coming up with the name in 1997; I like it better than
``slide attack.''
---Dan
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Fast random number generator -- Need C code for simulation
Date: Fri, 14 May 1999 04:09:03 GMT
[EMAIL PROTECTED] (catfish) wrote, in part:
>I'm doing a simulation model where many millions of random numbers are
>used. These are now generated by the (Microsoft) C rand() function.
It is indeed highly likely that you are getting a single sequence with
the 32768 numbers from 0 to 32767 in a scrambled order - and a
scrambled order with certain correlations.
>I use
> r = rand() % N; // remainder after division
You should use r = rand() << B
where B is a number of bits, as that is much faster.
Which is equivalent to rand() / N2 ... where N*N2 = 32768.
rand() % N is *very* bad, since the last 8 bits of rand() have period
256, the last 9 bits of rand() have period 512, etc..
Except you shouldn't use rand(), of course, as noted previously. Even
if you use a better random number generator, << B and not % N must be
used.
Numerical Methods in C discusses this topic at length, giving examples
of several types of generator.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
** 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
******************************
