Cryptography-Digest Digest #547, Volume #10 Thu, 11 Nov 99 17:13:03 EST
Contents:
Re: Compression: A ? for David Scott (Tim Tyler)
Re: S/MIME plug-in for Eudora? Strong Encryption ([EMAIL PROTECTED])
Re: The DVD Hack: What Next? (Lincoln Yeoh)
Re: Lenstra on key sizes (Medical Electronics Lab)
Re: Encryption Placement (Paul Koning)
Re: Compression: A ? for David Scott ("Douglas A. Gwyn")
Re: RC4 in Kremlin US version 2.21 can be cracked !! (Tom St Denis)
Re: Ultimate Crypto Protection? (Tom St Denis)
Re: Compression: A ? for David Scott (Tim Tyler)
Re: Proposal: Inexpensive Method of "True Random Data" Generation (Mike McCarty)
Re: Lenstra on key sizes (Bill McGonigle)
Re: Ultimate Crypto Protection? (HJS)
Re: What sort of noise should encrypted stuff look like? (Bill Unruh)
Re: What's gpg? <PHILOSOPHY 101>
Re: What's gpg? <PHILOSOPHY 101>
Re: S/MIME plug-in for Eudora? Strong Encryption (Doug McIntyre)
Re: Build your own one-on-one compressor (Mok-Kong Shen)
Re: For all lions --- (Mok-Kong Shen)
Re: Build your own one-on-one compressor (Mok-Kong Shen)
Re: Proposal: Inexpensive Method of "True Random Data" Generation (Mike McCarty)
real random number generator idea -- any criticisms? ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression: A ? for David Scott
Reply-To: [EMAIL PROTECTED]
Date: Thu, 11 Nov 1999 17:59:54 GMT
Tom <[EMAIL PROTECTED]> wrote:
: On Tue, 9 Nov 1999 23:19:02 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
:>Tom <[EMAIL PROTECTED]> wrote:
:>: (SCOTT19U.ZIP_GUY) wrote:
:>:>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
:>:> I think your actaully Tommy St Dennis since you don't seem to understand
:>:>what is goin on. And seem not to actaully read the posts.
:>:
:>: It's not a question of understanding, it's a question of believing any
:>: of it.
:>
:>Hopefully, reason - rather than faith - will prove sufficient.
: I'd hope so, but that doesn't seem to be the case.
;-(
:>:> Again if you don't use o-o-o compression you open your self up
:>:>to cipher only attacks. Do you understand this point before we go
:>:>into other areas to explore.
:>:
:>: The only cipher only attack that has been presented is a reduction in
:>: the set of possible output files from standard compression, which is a
:>: factor of the compression being non-perfect, not of it being non
:>: o-o-o, and of irreversibility, and this also isn't a function of it's
:>: being non o-o-o.
:>
:>"irreversible" and "non-o-o-o" are pretty much synonyms...?
:
: The o-o-o example is given as E(D(x)) = x, and D(E(y)) = y for any y
: or x, which is symmetrical. By reversible, I mean y=D(x) for any x,
: meaning that any x decompresses to something.
D(x) = x/2 (if x is even)
D(x) = 0 (if x is odd)
...is reversible by your definition of reversible.
However, AFAICS, *nobody* else would call this "reversible".
If something's reversible, you cen reverse it
No information is lost running in either direction.
Your definition doesn't appear to correspond with common usage.
:>: Again, this o-o-o concept is not generally accepted, nor has it been
:>: proven to be true.
:>
:>What exactly is your problem with it? It demonstrably prevents scertain types
:>of security leak.
:>
: Only argument has been against brute force, and that doesn't hold up.
This is because you've not been paying attention. The main point is
to eliminate clues that aid cryptanalysis. The argument does /not/ depend
on the possibility of a brute-force attack.
: I have no "problem" with it, except that it's being presented as fact
: when it doesn't appear to be at all.
:>: If you were to claim that a compressor where y=Decompress(x), where x
:>: can be any file, I'd agree it could be of some advantage. That's true
:>: for o-o-o, but o-o-o isn't required.
:>
:>The property you mention is inadequate (or at least sub-optimal) from a
:>security POV.
:
: Why not? [...]
It's trivial to create such a compressor. A wrapper around LZW compression
that suppresses errors and spits out the null file when it finds one would
qualify :-(
This has nothing to do with eliminating clues that aid cryptanalysis - and
completely misses the point ;-/
:>o-o-o compression offers better protection than this.
: Why?
Because (for one thing) the decomp(X) = some Y for any X says nothing about
whether the analyst can use Comp(Decomp(X)) = X to detect invalid compressed
files.
The decomp(X) = some Y for any X property alone barely offers any protection at all.
I'm getting tired answering the same questions over and over again.
We need a one-on-one compression FAQ. Until this is available, see
http://www.alife.co.uk/securecompress/ for a basic introduction to
one-on-one compression.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
I'm pink, therefore I spam.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: S/MIME plug-in for Eudora? Strong Encryption
Date: 11 Nov 1999 18:10:43 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(SkinD) wrote:
> They used to sell it but they are now
> only interested in selling multiple-site licences for a minimum of 20
> users. The helpful person at their sales dept said he'd like to sell
> it but his employers are no longer even interested in individual
> users.
It is probably illegal for them to refuse to supply (unless there were
some express limitations in the Shareware agreement). They made an offer
that you have accepted. If you get the details from someone I suggest
you send a cheque to the company.
Michael
Michael Strelitz
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: The DVD Hack: What Next?
Date: Thu, 11 Nov 1999 18:16:21 GMT
Reply-To: [EMAIL PROTECTED]
On 9 Nov 99 11:42:34 GMT, [EMAIL PROTECTED] () wrote:
>That isn't really accurate: the mistake of leaving the master key
>unencrypted made the hack easier, but since the DVD player software had to
>_use_ the master key anyways, if the mistake had not been made, the
>Norwegian programmers would just have had to work for a few days longer.
Assuming it's exportable it's probably 40 bit crypto. And so it's probably
crackable in a week or two with a single high end PC.
Cheerio,
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Lenstra on key sizes
Date: Thu, 11 Nov 1999 12:52:53 -0600
Mok-Kong Shen wrote:
> That sort of continual contest is 'actually' taking place, though
> you can't expect any official institution to formally do that.
> In fact, the development of sciences is the result of continual
> contests. Despite opinions in the opposite direction, I think
> that crypto is among those fields that are favoured in the sense
> that any individual can attempt to take part in the current
> research. (Compare with, say, some branches of physics where
> one needs giant financial resources like those at CERN or other
> laboratories.) Time and again I hear opinions that competitions
> in certain sectors are not fair. One couldn't exclude that in
> principle. But the real world is imperfect and hence does
> not provide fairness as necessity (cf. the social competition
> between the rich and the poor). That's life. So doing work
> instead of continuously complaining seems to be a better strategy
> under the given circumstances.
Actually, there's a lot of physics that could be done in a
basement with limited resources. But crypto only takes a
nice computer and a lot of time with pencil and paper, so it
is much easier to do research. In either case, you have to
learn a lot of math, and that too takes a lot of time.
But it is kind of cool that any individual can advance the
state of the art by thinking hard, and they don't have to be
tied into any huge laboratory.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Encryption Placement
Date: Thu, 11 Nov 1999 13:39:43 -0500
"Lassi Hippel�inen" wrote:
>
> The difference is in trading management, performance, and security.
>
> The higher the encryption is placed, the more efficient it can be made.
> It can even use application-dependent tricks, e.g. encrypt only
> essential information. Security is also better, because encrypted
> information doesn't appear outside the application instance.
>
> Lower layer encryption is far easier to manage and much more scalable.
> It is transparent to the users, and doesn't burden their hosts with the
> calculations. And security is also better, because the users can't leak
> the keys. They don't even have them.
>
> If there were a single correct configuration, it would be in general use
> by now...
That's absolutely true!
My answer would be "it depends on what the threats are".
If you don't trust anyone outside your own system, application layer
crypto is a good choice. Network layer encryption implemented in your
own system would also serve (IPSec for example). Datalink crypto would
not.
If you're worried about traffic analysis, application crypto
is NOT a good choice, but the other two are. Datalink crypto is
best in that case, but network layer crypto can come pretty close
especially if used in tunnel mode.
The efficiency argument (encrypt only what really matters) isn't
all that convincing: if you have a really severe performance
requirement, throwing hardware crypto accelerators at the
problem is a much easier solution.
paul
> Benjamin Valenti wrote:
> >
> > I am aware that there are three OSI layers where encryption is
> > implemented: application, network, and data-link layers. What are the
> > differences between each? What are the reason for choosing one over
> > another? What are the advantages and disadvantages to using one or the
> > other? If there is a source online, I haven't found it and could use
> > some help. Please help me or at least point me in the right direction.
> > Thank you!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Compression: A ? for David Scott
Date: Thu, 11 Nov 1999 19:10:16 GMT
Tim Tyler wrote:
> Methinks you underestimate your opponents ;-/
Methinks you didn't understand what I said.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RC4 in Kremlin US version 2.21 can be cracked !!
Date: Thu, 11 Nov 1999 19:11:25 GMT
In article <80eshl$68i$[EMAIL PROTECTED]>,
"Alexander PUKALL" <[EMAIL PROTECTED]> wrote:
> RC4 with CBC encryption mode not selected ( RC4 is not a block
cipher ) is
> like a VIGENERE cipher, even RC4-128 bits or more
First off I doubt you know what a Vinegere cipher actually is. Here is
the pseudo-code
for i = 0 to n
Ci = Pi xor K[i mod k_len]
next i
It's not secure at all and most importantly nothing like RC4. Stop
spamming this group!
RC4 is a secure random number generator, a Vinegere cipher is not a RNG
at all...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Ultimate Crypto Protection?
Date: Thu, 11 Nov 1999 19:19:26 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (BigJim44) wrote:
> I'm just a rookie at this. It would appear that if I encipher a
message using
> one of the better crypto programs out there and then take that
enciphered
> message and encipher it a second time using an entirely different
program (one
> that employs a different algorithm) I would have a system that would
be very
> difficult to crack. It would envolve a lot of work though.
But the thing is one encipherment is probably hard to tackle anyways.
Why overdo it?
> I have a friend who tells me that the Russian military used double
enciphered
> OTP all through the cold war and that NSA, with all it's expertise
and computer
> hardware never had much success breaking it.
Your friend is a liar. There is no such thing as a 'double-otp'. For
any two OTP's another OTP can exist which is the composite of the two.
For example for C = P xor K1 xor K2 there exist a K3 which is equal to
K1 xor K2 ...
>
> Is double encipherment really all that effective?
Not really. Depends on what you are trying to depict as usefull.
Currently most implementations of crypto (S/MIME, PGP, heck even my
peekboo :) ) do not get attacked from a math or algorithm standpoint.
[i.e solving my peekboo public key, or brute forcing a 160 bit message
key are not realistic means of attack]. They normally get attacked at
the user level. Bad passwords, user mistakes, etc... can compromise
the security much easier...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression: A ? for David Scott
Reply-To: [EMAIL PROTECTED]
Date: Thu, 11 Nov 1999 19:36:33 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: The idea is that a brute-force attack must test each
: putative recovered compressed plaintext for validity,
: and a non-o-o-o compression scheme would facilitate
: this in two possible ways: (1) some garbage would
: fail to decompress; (2) other garbage would decompress
: to something that fails statistical tests for plaintext.
That's *ONE* idea.
Somehow, that the cryptanalyst might use information systematically added to
the file to mount an attack, based on these regularities, and *not*
involving brute force doesn't seem to have got a mention, though :-(
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
--- Please refill tagline dispenser ---
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: 11 Nov 1999 19:44:48 GMT
In article <[EMAIL PROTECTED]>, Coen Visser <[EMAIL PROTECTED]> wrote:
)Patrick Juola wrote:
)
)> >If you want to define it that way. But this leads to a useless
)> >definition -> A TRNG produces strings that are "unpredictable"
)> >(we can not use the word random anymore, it is reserved for
)> >the generators and not the strings). So we have no other means to
)> >qualify the strings other than to say that they are produced by
)> >a TRNG and therefore are "unpredictable". But we have no means to
)> >qualify the TRNG (is it really truely random?) because we can not
)> >talk about the degree of randomness of the strings it produces
)> >(that was not allowed).
)
)> That's because talking about the individual strings is meaningless
)> in a statistical sense. Given a string, you can't tell anything about
)
)I agree that the bickering about randomness of strings of size 1
)is a waste of time or at best purely academic. But there is a *lot*
)of (statistical) information in a random string of size ~ 2E1024 whether
)you look at it as a single string or as 2E512 strings of size 2E512.
The length of the string is irrelevant. If you had 2e512 strings, then
you could draw conclusions. But from one string, of whatever length, one
cannot draw a conclusion.
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.
------------------------------
From: [EMAIL PROTECTED] (Bill McGonigle)
Subject: Re: Lenstra on key sizes
Date: Thu, 11 Nov 1999 14:17:52 -0500
In article <80d67o$jju$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote:
> And have contests they
> can't do becasue of inherint weaknesses in there short keyed methods.
I'm not familiar with your product, but a long key does not make a secure
product. A longer key can make a more secure product.
-Bill
=====
[EMAIL PROTECTED] / FAX: (419) 710-9745
Dartmouth-Hitchcock Medical Center Clinical Computing
------------------------------
From: [EMAIL PROTECTED] (HJS)
Subject: Re: Ultimate Crypto Protection?
Date: Thu, 11 Nov 1999 19:50:59 GMT
Reply-To: HJS
On 11 Nov 1999 17:06:23 GMT, [EMAIL PROTECTED] (BigJim44) wrote:
>I have a friend who tells me that the Russian military used double enciphered
>OTP all through the cold war and that NSA, with all it's expertise and computer
>hardware never had much success breaking it.
If it was genuine one-time-pad properly used and administered, then no amount
of expertise, however intelligently applied, and no amount of computer hardware
would or could ever have broken it!
An OTP hardly needs superencipherment - it's totally secure the first time,
doing it again is a waste of time and could even, in some circumstances
weaken the system.
--
HJS +
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: What sort of noise should encrypted stuff look like?
Date: 11 Nov 1999 19:52:25 GMT
In <80asd8$3vk$[EMAIL PROTECTED]> Tom St Denis <[EMAIL PROTECTED]> writes:
>What is pink noise?
>Technically encrypted data should not resemble anything, mechanically
>though we can think of it as white noise [although white noise is not
>actually white, so why do they call it white noise?].
White noise is white because each spectral component has an equal power
(on average) just as white light does. Pink noise has a spectrum which
is bigger at low frequencies than at high. If one did this for the light
spectrum from a light bulb, the resulting colour of the light would be
pink.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: What's gpg? <PHILOSOPHY 101>
Date: 11 Nov 99 19:45:17 GMT
Douglas A. Gwyn ([EMAIL PROTECTED]) wrote:
: John Savard wrote:
: > >Jerry Coffin <[EMAIL PROTECTED]> wrote ...
: > >> .... It
: > >> just happens that DES (for example) has been studied by a lot of
: > >> really smart people for an awful long time, and nobody's found an easy
: > >> attack on it, so it's generally assumed that none is likely to exist.
: > This is sound, to an extent; it's simply Bayesian statistics.
: No, it's not sound at all! This is not a "statistical" issue;
: cracking attempts aren't randomly drawn from some population.
: There are many historical counterexamples; practically every new
: crytposystem has been believed uncrackable after many "experts"
: tried and failed to crack it, but in the end they (nearly) all
: turned out to be crackable.
Now, this is interesting. I can't argue with your history, but I have
tended to think that the microchip revolution has given the defense quite
an unprecedented advantage over the offence in the area of cryptography
these days.
Each cracking attempt indeed is based on the experience gained from the
previous failures; I think there is a shaky kind of validity for saying
that "this cipher hasn't been cracked after five years of study, so, on
the average, it should have another five years before it is cracked". That
is all the confidence - which isn't much - Bayesian statistics can give.
Not every statistician accepts the validity of Bayesian statistics
precisely because it attempts to deal with the case when things _aren't_
neatly drawn from a population.
In any case, those who haven't listened to Terry Ritter may now listen to
you, and ponder what it means if nearly all the ciphers we think of as
secure today might turn out to be crackable.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: What's gpg? <PHILOSOPHY 101>
Date: 11 Nov 99 19:46:30 GMT
Dennis Ritchie ([EMAIL PROTECTED]) wrote:
: Well, the independence of AC and GCH, and the forcing method,
: are Cohen's most memorable contributions that I know of, but
: he neglected to mention the waking-up business in his 1966 monograph
My faulty memory of a recent thread in sci.math; another poster responded
with the correct story.
John Savard
------------------------------
Crossposted-To:
comp.security.misc,comp.security.pgp.tech,alt.security.pgp,comp.mail.eudora.ms-windows
Subject: Re: S/MIME plug-in for Eudora? Strong Encryption
From: [EMAIL PROTECTED] (Doug McIntyre)
Date: Thu, 11 Nov 1999 20:02:12 GMT
[EMAIL PROTECTED] (Lincoln Yeoh) writes:
>On Thu, 11 Nov 1999 12:49:36 +0000, SkinD <[EMAIL PROTECTED]> wrote:
>>>Why not just use PGP?
>>
>>Because, to my knowledge, millions of internet users are already using
>>email programs which are able automatically to use S/MIME without the
>>need even to install a program or plug-in. I'm thinking of Netscape
>>Communicator. S/MIME would enable people to use encryption or signing
>>with me without them even particularly thinking about what they are
>>doing.
>That is not true. AFAIK those millions of internet users must get a cert
>from a CA first to use S/MIME. e.g. thawte, verisign, etc.
>Try it yourself. And those free certs tend to expire after 60 days or so.
>When that happens you have to explain to your "morons" why they have to
>update their cert and how.
Thawte gives away free certificates for personal use. They expire on a
yearly basis, just like buying a certificate would.
>>I like, and use, PGP but frankly can't ever see more than 0.001% of
>>internet users ever installing it or even understanding it once they
>>have done so. S/MIME can be used by morons.
>So far I haven't bothered to encrypt messages to morons.
>PGP is far more flexible than S/MIME. You can even encrypt/sign faxes if
>you wish ;).
There's no reason PGP would be able to do anything that S/MIME
couldn't. Its the same concept, and the same execution.
--
Doug McIntyre [EMAIL PROTECTED]
Network Engineer/Tech Support/Jack of All Trades of Vector Internet
Due to circumstances beyond your control, you are master of your fate
and captain of your soul.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Build your own one-on-one compressor
Date: Thu, 11 Nov 1999 20:35:23 +0100
Mok-Kong Shen wrote:
>
> This same counter-argument was raised, when long time ago in this
> thread I mentioned the numerical encoding using a publically
> accepted dictionary. My humble opinion about that issue is: (1)
'this thread' should read 'this group'. Sorry.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: alt.politics.org.nsa,alt.math,alt.security
Subject: Re: For all lions ---
Date: Thu, 11 Nov 1999 20:32:41 +0100
Markku J. Saarelainen wrote:
>
> Some of most popular encryption applications have backdoors and their
> development projects have been supported and influenced by certain
> specific intelligence-interest groups. In the future's electronic
> commerce environment these encryption methods and technologies shall
> become even more important for any corporation anywhere around the world
> and it is highly recommended to avoid using any of the most popular
> and/or free encryption applications for any business and commercial
> purposes."
I am afraid it is not very clear what you are proposing for use in
'applications for business and commercial purposes'. On superficial
reading at least, one could deduce that anything (1) non-popular
and (2) very costly would qualify in your opinion. (PGP is free.
Do you think that it is bad because it is free?) So I believe you
should elaborate your points more concretely to enable better
comprehension of your article by the general readers.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Build your own one-on-one compressor
Date: Thu, 11 Nov 1999 20:32:21 +0100
Tim Tyler wrote:
>
>
> Will the 65536 words in your dictionary contain all the words I used?
This same counter-argument was raised, when long time ago in this
thread I mentioned the numerical encoding using a publically
accepted dictionary. My humble opinion about that issue is: (1)
One has to be a very learned man to write ordinary texts that
contains plenty of words outside a dictionary of that size. (Note
the Chinese telegraphic code has only 10000 words and the Unicode
of Chinese words uses 2 bytes -- I don't know exactly but I doubt
that there exist many contemporary Chinese words not in the Unicode,
for otherwise Unicode would have largely failed its design goal).
(2) If words outside the dictionary are rare, then the effect on
compression of these is negligible (one uses a verbatim copying
method for these words). (3) such a dictionary/system is intended
for the common people (normal communications). For scientists
in special disciplines, e.g. chemists, special dictionaries can be
constructed according to the same principle.
> I think the scheme you are proposing can compress English texts. I doubt it
> will be as good as methods allowing variable-length symbols, and schemes like
> arithmetic coding which allow symbols which are not an integral number of bits
> in length.
Of course, without some extensive experiments neither your doubt
nor my claim can be ascertained.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: 11 Nov 1999 19:54:58 GMT
In article <[EMAIL PROTECTED]>, Coen Visser <[EMAIL PROTECTED]> wrote:
[snip]
)No, that is just a matter of how you define things. Defining
)incompressible
)strings as random is extremely handy. You can use it as a great
)mathematical
)tool. It is also a very intuitive notion. How can you use the randomness
)of
)the source as a mathematical tool? I haven't seen a mathematically solid
)definition of a random source in this discussion yet.
No individual string can be random. A string is or is not compressible,
and is compressible to some degree or less, is not an absolute
statement. It depends on the universe of strings from which it is
drawn. If a process generates one of two strings, each of which is 10
billion elements long, but only one of those two, then each of those 10
billion element strings is compressible to a single bit. OTOH, if the
universe of output is all possible strings of 10 billion elements, and
if individual elements occur equiprobably, then not any of the strings
is compressible.
You seem to be trying to decompose a single event, i.e. the generation
of a string, into multiple events, i.e. the generation of each string
element (or equivalently, generation of strings of length one element
each), and then use the randomness or non-randomness of the latter
events considered as a stochastic process as a means for determining
the randomness of the single event of generation of the entire string.
The single event is not so decomposable. The two stochastic processes
(generation of single long strings vs. generation of single element
strings) do not have a 1-1 correspondence, as you seem to believe. Both
random and non-random processes for generation of single long strings
can map to random processes at the individual element level.
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.
------------------------------
From: [EMAIL PROTECTED]
Subject: real random number generator idea -- any criticisms?
Date: Thu, 11 Nov 1999 20:21:27 GMT
I have an idea for a random number generator on Windows NT/9x machines.
The idea is an adaptation of a rng mentioned in Schneier's Applied
Cryptography, Sec 17.14 in the subsection. "Using the Computer's Clock"
Make an initial call to ::GetTickCount(). Keep calling the function
repeatedly until the value changes, incrementing a counter each time.
Take the LSB of the counter and use that as a bit of randomness. The
resolution of the win32 function ::GetTickCount is about 10ms for NT,
55ms for 95.
Thus, the method grabs randomness from the process scheduler.
I considered the possibility that the attacker may be able to control
what else is running on the machine. In order to counteract the case
where the attacker might be able to starve the process to influence the
number of calls, I also XOR the bit with the LSB from the high-
frequency performance counter, i.e. ::QueryPerformanceCounter().
On my machine (running NT 4.0), I can produce a KB of data in around 80
seconds. This rate has more to do with the OS than the HW.
(.001 s/ms * 10 ms/bit * 8 bits/byte * 1024 bytes/KB = 81.92 s/KB)
So an initialization vector of 8 bytes would take less than 1/10th of a
second to generate.
Empirical evidence shows this method does not have any bias. I
analyzed the outcome of this method by comparing the autocorrelation
function outputs with those of some true random (hardware) sources.
The results looked comparable.
I am in the process of trying to gen. enough data (10MB) to run the
diehard analysis program against it (
http://stat.fsu.edu/~geo/diehard.html ).
This will help determine how statistically random the data is, but I
wanted to get some criticism and opinions on whether this method can be
cracked by intimate knowledge of the scheduler. Please no attacks that
would involve rewriting the kernel. I realize that if the attacker can
precisely control the scheduling of the process, then the method could
be compromised.
source code:
BYTE GetRandomByte()
{
BYTE output = 0;
for (int i=0;i<8;++i) {
BYTE randomBit = 0;
DWORD counter =0;
DWORD initialTick = ::GetTickCount();
// See how high we can count before GetTickCount changes.
while (initialTick == ::GetTickCount() )
++counter;
randomBit ^= counter & 1;
// let's also get an LSB from the
// high-resolution timer.
// This should help to protect us from thread starvation problems
LARGE_INTEGER perfCount;
::QueryPerformanceCounter(&perfCount);
randomBit ^= perfCount.LowPart & 1;
output <<= 1;// shift everything a bit
output |= randomBit;// set the LSB
}
return output;
}
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
