Cryptography-Digest Digest #894, Volume #8 Tue, 12 Jan 99 19:13:04 EST
Contents:
Re: On the Generation of Pseudo-OTP (Paul L. Allen)
Re: On the Generation of Pseudo-OTP (Paul L. Allen)
Re: Practical True Random Number Generator (R. Knauer)
Re: Practical True Random Number Generator (R. Knauer)
Re: Practical True Random Number Generator (R. Knauer)
Re: On the Generation of Pseudo-OTP (Patrick Juola)
Re: Practical True Random Number Generator (Nicko van Someren)
Re: Twofish vs DES? ("TERACytE")
Encrypted WordPerfect 5.1-files (DOS) ("K&G")
Re: Random numbers in C: Some suggestions. (Mike Oliver)
Re: Random numbers in C: Some suggestions. (Mike Oliver)
Re: What is better : Blowfish, Des, Tripple-Des (Jim Gillogly)
Re: Practical True Random Number Generator (Patrick Juola)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul L. Allen)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 19:07:25 +0000
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>
[EMAIL PROTECTED] (R. Knauer) writes:
> On Mon, 11 Jan 1999 21:03:31 +0000, [EMAIL PROTECTED] (Paul L.
> Allen) wrote:
>
> >> There is something about your entropy that is not quite right here. In
> >> one of his papers, Chaitin dismisses such "low-entropy" sequences as
> >> being "non-random" for purposes of his algorithmic information theory,
> >> of which his algorithmic complexity theory is a subset. He dismisses
> >> such sequences because they are reducible.
>
> >Then his algorithmic information theory appears to have flaws.
>
> To be fair to Greg Chaitin, you should read his papers for yourself
> and not trust my evaluation. I am not trained in this field (although
> I am not a complete neophyte either), so it is entirely possible I
> misconstrued what he was saying.
Possibly. But I'm answering posts here and not his papers...
> >Any sequence you like to specify in advance is reducible and, with the
> >right input data, will result in good compression.
>
> I don't understand what you just said. Are you saying that ANY
> sequence can be compressed further to a significant extent? Small
> reductions are not of significance in algorithmic complexity theory.
Yes, any sequence can be compressed *in the right circumstances*. If
you have a sub-sequence which occurs many times in a longer sequence then
no matter what that sub-sequence is you can replace it with a compression
code that says "expand me into sub-sequence 1". That sort of trick is
at the heart of many compression schemes one way or another. If you can
identify some sub-sequence that occurs frequently you can replace it with
a compression code. The problem with truly random data is that even the
common sub-sequences are relatively rare and the compression flag you
use relatively common (so must be escaped when it appears as a sub-sequence
in the data). You can't get round it by making the compression flag
longer because although it occurs more rarely it's longer.
Chaitin's problem is that if you consider sequences in isolation you
can show compressibility whereas if the same sequence is embedded in
a much longer sequence of random data it isn't because you can't come
up with a compression scheme for the larger sequence that actually works.
> >Build a Huffman compression table for
> >ordinary English text and use it to compress the same text that's been
> >rot-13ed and you'll get something that's larger than the original. The
> >sequences Chaitin claims are reducible are only reducible in some
> >circumstances and those circumstances do not apply to TRNGs.
>
> We decided that Chaitin's algorithmic complexity theory has no direct
> immediate application to crypto (private communication). But it is
> interesting to note that he proves that random numbers cannot be
> characterized as such formally. He does that by appealing to Godel's
> Theorem, Turing's Halting Problem and his own Mathematical
> Indeterminancy Theorem.
You can't prove any randomly-generated number is random, only that it has
statistics which are closer to or further away from what you'd expect of
a truly random number. And you'd expect some randomly-generated numbers
to depart from some of those statistics some of the time. The more samples
you have, the more confident you can be that your generator is random.
> >Essentially the mistake is to take a finite sequence and apply thinking
> >that is only meaningful for infinite sequences. Like asking if "6" is
> >a random number - it's a meaningless question because you the term "random
> >number" only applies to something which is taken from a (potentially) larger
> >sequence of numbers.
>
> I am not sure I follow that. It is a tenent of both crypto and
> Chaitin's theory that one cannot characterize a number as random on a
> formal basis by looking at the number by itself.
I thought that was what I said. You can't look at a finite sequence and
decide if it's truly random or not.
> In crypto, one has to decide randomness based on the nature of the
> generator.
That's a reasonable way of doing it for hardware generators.
> In Chaitin's theory, randomness is decided if one cannot further reduce
> the number algorithmically.
I don't believe him. And that's apart from the fact that you just told
me Chaitin says you cannnot characterize a number as random on a formal
basis by looking at the number itself, which he appears to have just
done. Under the right circumstances you can compress any sequence. Under
the wrong circumstances, compressing that sequence when it is part of
a larger sequence will result in the larger sequence becoming even
larger. Chaitin's mistake is to consider sequences in isolation instead
of when they're embedded in larger random sequences.
> >This is true (except you mean "sequence" again). For very large sequences
> >and selections of sequences we can determine the probability that those
> >sequences would have the statistical properties they have by chance.
>
> It is not the statistical properties of the sequence per se, but the
> statistical properties of the generator that make a number truly
> random for crypto purposes.
But you can only determine the statistical properties of a black-box
generator by looking at the statistical properties of the sequences it
produces.
--Paul
------------------------------
From: [EMAIL PROTECTED] (Paul L. Allen)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 19:23:24 +0000
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>
[EMAIL PROTECTED] (R. Knauer) writes:
> On Mon, 11 Jan 1999 23:25:07 +0000, [EMAIL PROTECTED] (Paul L.
> Allen) wrote:
>
> >No, I just know the folly of trying to explain complicated things to
> >fucking idiots.
>
> I guess than means you have just made yourself irrelevant for any
> further discussions, at least with me.
Your trouble is you're incapable of reading and/or comprehending what
you read. I mention that some of your requirements for a hardware TRNG
are ridiculous and you take it as an ad hominem, which it wasn't, so
you cut the bits where I explain to you why your requirements were
ridiculous and you accuse me of not explaining anything to you (which makes
you a liar). Then when I show you what a *real* ad hominem looks like, so
you'll know in future and not accuse people wrongly of attacking you with an
ad hominem, you cut the bits that show you were wrong and get all huffy.
I've seen this "snip the bits that prove you were wrong then accuse the
other guy of being unable to prove you wrong" trick many times before.
It always comes from fuckwits who are unable to admit they are wrong.
> Take your pompous overbearing smug attitude back the the university
> where it belongs because it certainly does not belong in the real
> world here.
See? I told you that you were incapable of reading and/or comprehending
what you read. In my previous post I made it clear (to those with the wit
to comprehend) that I have designed safety-critical systems. I know what
I'm talking about because I've done it in the real world as well as having
the theory. So I *know* some of your claims about real TRNGs and making
them failsafe by using multiple redundancy are ridiculous.
BTW, since you appear to be hard of thinking, I'll explain something else
to you. This is Usenet. You get to post what you want. I get to post
what I want. So you can post all the crap you want and I can respond
to each of your posts telling you why they're full of shit. You cannot
stop me posting saying when your posts are full of shit any more than
I can stop you posting crap. However much you dislike my responding to
your posts, that won't make me go away. In fact the only way you can
stop me pointing out when your posts are full of shit is to stop posting
crap.
--Paul
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 21:04:57 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 12 Jan 1999 20:27:56 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>> You are introducing symmetry into the measurements, and now the
>> direction of time does not matter - so systematic errors such as the
>> decay of the radioactive source over time are cancelled and cannot
>> cause bias in the bitstream.
>Sorry, being not a physicist, I find it difficult to understand
>the 'direction of time'. Isn't it that time is uni-directional?
>Or could you refer to literature on perhaps the reversal of the
>direction of time? Thanks in advance.
I did not mean anything mysterious or esoteric about that term, just
that you have cancelled out the effects of systematic timing errors by
reversing the sense measurement in time.
IOW, the "direction of time" is "reversed" only in a calculational
sense, to eliminate bias. Actually what you do is keep the time the
same but reverse the outputs, but that has the same effect.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 21:21:41 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 12 Jan 1999 20:42:30 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Sorry to say that after having read in another thead many occurences
>of the term 'Bayesian Attack' I still have yet no concrete idea of
>an implementation of such an attack. I mean I am still ignorant of
>literatures that enable me to try to lauch such an attack on
>a given cipher.
That makes two of us. You might want to read the post from Patrick
Juola today.
I also asked him to give us some introductory text book references. I
looked on amazon.com and there are several books available but they
are incredibly expensive. Of course, there is always the library.
In the meantime you can might want to chase links in AltaVista with
keyword "bayesian". Let us know if you find anything interesting.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 21:07:38 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 12 Jan 1999 20:38:10 +0100, [EMAIL PROTECTED] wrote:
>BTW: Most physical processes are independent of time,
Certainly at the quantum level.
>only entropy in a closed system is always growing.
>Is our world based on the movement towards chaos?
The Universe is moving towards more information capacity.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: On the Generation of Pseudo-OTP
Date: 12 Jan 1999 14:47:58 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 12 Jan 1999 10:16:03 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>But, as my half-assed remembrance tells me, the proof is actually
>>expressed in terms like "pi is 'normal' to every base", where
>>'normal' means that every (finite) digit stream appears *somewhere*
>>in the decimal expansion of pi.
>
>The Web page: ftp://www.cc.u-tokyo.ac.jp/README.our_latest_record
>gives some of interesting digits sequences:
>
>0123456789 : from 17,387,594,880-th of pi
>0123456789 : from 26,852,899,245-th of pi
>0123456789 : from 30,243,957,439-th of pi
>0123456789 : from 34,549,153,953-th of pi
>0123456789 : from 41,952,536,161-th of pi
>0123456789 : from 43,289,964,000-th of pi
>
>9876543210 : from 21,981,157,633-th of pi
>9876543210 : from 29,832,636,867-th of pi
>9876543210 : from 39,232,573,648-th of pi
>9876543210 : from 42,140,457,481-th of pi
>9876543210 : from 43,065,796,214-th of pi
>09876543210 : from 42,321,758,803-th of pi
>
>That shows you at a glance the futility of trying to characterize
>individual sequences as random.
>
>>This is necessary, but not sufficient, for producing a cryptologically
>>random stream.... for example, the stream
>>0.123456789101112131415161718192021...
>>is also 'normal' to base 10, but is pretty pathetic as an OTP.
>
>Is it? After all, it is one of the possible, equiprobable sequences
>that a TRNG can generate.
Yup. But the probability of your generator creating that particular
infinite stream is, literally, zero.
>
>>But PGP doesn't use numbers longer than the memory of the PC it's running
>>on. 2048 bits are actually pretty small when you're dealing with
>>expansions of trancendental numbers.
>
>Is that true if you are talking about digit expansions?
Yup. The pi generation method is very unusual in that it *doesn't*
require hugely increasing memory with each successive digit.
Most methods require that you store and manipulate huge structures
to calculate each successive digit, and rather quickly, your
machine starts gasping for breath.
>>Because the Bayesian attack will work by seed counting as well as on
>>an individual bit basis. As a practical attack, enumerating all 128-bit
>>seeds is probably not reasonable. But that also requires that you be
>>able to, on demand, generate up to 2^128 bits of the trancendental
>>stream of interest. Smaller than that, and you run the risk that
>>someone will simply enumerate the seeds and look for patterns in them.
>
>How about doing it this way: I take a 128-bit offset into the digit
>expansion of the transcendental constant and begin the digit expansion
>one digit at a time until I get a sequence of length sufficient for my
>current needs. In such manner, I do not have to calculate the first
>2^128 digits.
Um.... This is exactly what you can't do in most cases. With the
exception of the base-16 pi calculations, you usually need to calculate
the first i digits in order to then compute the i+1st.
You can see the difficulties there. The same page you reference
with all the digits of pi also gives the running time -- approximately
twenty-five hours to calculate 2^36 digits. This means that you'd
only need about, um, 2^92 days to calculate your 2^128-bit offset.
Or we could have something about as secure as DES and only take 2^30
days.
Better bring a good book.
-kitten
------------------------------
From: Nicko van Someren <[EMAIL PROTECTED]>
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 23:19:49 +0000
This is a multi-part message in MIME format.
==============32FDA6CC8D656D8A224F61F4
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
KloroX wrote:
> On Mon, 11 Jan 1999 16:48:45 -0500, Nicko van Someren
> <[EMAIL PROTECTED]> wrote:
>
> [snip]
> >It should be noted, for the sake of the pathologically pedantic, that
> >if you use a radioactive source with a finite half-life then the
> >radioactivity
> >of the source is decreasing over time and this gives you some bias.
> [snip]
>
> A simple fix comes to mind. If we write your original loop as
> (disregarding the case of t1 = t2 for simplicity)
>
> while(true)
> {
> get(t1, t2); // get the intervals t1 and t2 between detected
> fissions
> if(t1 > t2)
> output(0);
> else
> output(1);
> }
>
> then we could modify the loop to invert the rule at every reading:
>
> while(true)
> {
> get(t1, t2);
> if(t1 > t2)
> output(0);
> else
> output(1);
> get(t1, t2);
> if(t1 < t2)
> output(0);
> else
> output(1);
> }
This removes the most obvious bias but it does not get you back up
to a full 1 bit of entropy per output bit. The first bit is more likely
to be a zero and the second is more likely to be a one.
Nicko
==============32FDA6CC8D656D8A224F61F4
Content-Type: text/x-vcard; charset=us-ascii;
name="nicko.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Nicko van Someren
Content-Disposition: attachment;
filename="nicko.vcf"
begin:vcard
n:van Someren;Nicko
x-mozilla-html:FALSE
org:nCipher Corporation Ltd.<br><img
src="http://www.ncipher.com/images/masters/ncipher100.jpg">
version:2.1
email;internet:[EMAIL PROTECTED]
title:Chief Technology Officer
tel;fax:+44 1223 723601
tel;work:+44 1223 723600
adr;quoted-printable:;;Jupiter House=0D=0AStation Road;Cambridge;;CB1 2JD;England
x-mozilla-cpt:;0
fn:Nicko van Someren
end:vcard
==============32FDA6CC8D656D8A224F61F4==
------------------------------
From: "TERACytE" <[EMAIL PROTECTED]>
Subject: Re: Twofish vs DES?
Date: Tue, 12 Jan 1999 16:30:32 -0700
All I was looking for was a relevant discussion about the pluses & minuses
of each. I used the term "better" (whatever that means) to entice
responses. Looks like that part worked. It's a good idea to seek out
other perspectives, when you have your own personal opinion on something
that interests you.
My opinion? Both are good quality encryption engines. I've studied and
coded both DES & BlowFish (the TwoFish predecessor), so I know I've got good
experience in the area.
DES is a tried and true algorithm. It's been around for a while & has been
poked 'n prodded by the best. However, it is for these reasons that various
institutions are seeking to replace it. It does not fulfill all the needs
of new (or developing) technologies. TwoFish seeks to be the next
replacement for the encryption standard. It is simply designed to continue
where DES leaves off.
In terms of "better", neither is better.
Brad Aisa <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>[EMAIL PROTECTED] wrote:
>
>> > >NEITHER
>> > >if you want something more modern than these weak
>> > >old ciphers
>>
>> Joe the question was a B. S. troll in the first
>> place how could anyone take it as a real question.
>
>Oh, for christ's sake, the question was perfectly legitimate -- someone
>was asking about the relative merits of two modern asymmetric
>cryptographic algorthims. This is exactly the place to ask such a
>question. Troll? Sheesh.
>
>--
>Brad Aisa
>[EMAIL PROTECTED] -- PGP 5.0 public key available at:
>http://keys.pgp.com:11371/pks/lookup?op=get&search=0x6F053CE9
>
>"Laissez faire."
------------------------------
From: "K&G" <[EMAIL PROTECTED]>
Subject: Encrypted WordPerfect 5.1-files (DOS)
Date: Wed, 13 Jan 1999 00:46:58 +0100
Hi there,
I'd like to know if someone who could help me to decrypt
some (DOS) WordPerfect 5.1-files that are mine (I can
prove that) but I've lost the password.
Thanx,
Guy Cornet
[EMAIL PROTECTED]
------------------------------
From: Mike Oliver <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math,sci.math.num-analysis,sci.physics
Subject: Re: Random numbers in C: Some suggestions.
Date: Tue, 12 Jan 1999 15:54:10 -0800
Reply-To: [EMAIL PROTECTED]
George Marsaglia wrote:
> [...] and experience has shown that
> lagged Fibonacci generators using xor provide
> unsatisfactory 'randomness' unless the lags are
> very long, and even for those with very long lags,
> (and even for those using + or - rather than xor),
Could you give us a pointer to information about
why these RNGs are unsatisfactory and what sort
of test they tend to fail?
--
Disclaimer: I could be wrong -- but I'm not. (Eagles, "Victim of Love")
Finger for PGP public key, or visit http://www.math.ucla.edu/~oliver.
1500 bits, fingerprint AE AE 4F F8 EA EA A6 FB E9 36 5F 9E EA D0 F8 B9
------------------------------
From: Mike Oliver <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math,sci.math.num-analysis,sci.physics
Subject: Re: Random numbers in C: Some suggestions.
Date: Tue, 12 Jan 1999 15:54:33 -0800
Reply-To: [EMAIL PROTECTED]
George Marsaglia wrote:
> [...] and experience has shown that
> lagged Fibonacci generators using xor provide
> unsatisfactory 'randomness' unless the lags are
> very long, and even for those with very long lags,
> (and even for those using + or - rather than xor),
Could you please give us a pointer to information about
why these RNGs are unsatisfactory and what sort
of test they tend to fail?
Posted and mailed.
--
Disclaimer: I could be wrong -- but I'm not. (Eagles, "Victim of Love")
Finger for PGP public key, or visit http://www.math.ucla.edu/~oliver.
1500 bits, fingerprint AE AE 4F F8 EA EA A6 FB E9 36 5F 9E EA D0 F8 B9
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: What is better : Blowfish, Des, Tripple-Des
Date: Tue, 12 Jan 1999 16:00:31 -0800
Reply-To: [EMAIL PROTECTED]
nRg wrote:
> What is better and safer ?
>
> a blowfish encryption with 448bits
> a DES encryption with 56bits
> a Triple DES Encyrption with 112bits
Blowfish and 3DES are almost certainly safer than DES; there's no
effective difference in the key length (i.e. both are "long enough").
DES is no longer secure enough for many applications, but is safer than
sending plaintext. "Better" depends on the application: Blowfish is
faster, 3DES is an easier drop-in replacement for DES, and DES should
soon be exportable from countries that want to be able to read your
transactions.
> Are there any new technologies ? Please give me a URL to download them
Yes, many. For the AES candidates to replace DES, see (for example)
Brian Gladman's collection at http://www.seven77.demon.co.uk/aes.htm .
For many real-world applications you'll be well served by using a
canned package with strong crypto such as PGP, or rolling your own
with tested techniques like CipherSaber ( http://ciphersaber.gurus.com ).
--
Jim Gillogly
Sterday, 21 Afteryule S.R. 1999, 23:46
12.19.5.15.6, 6 Cimi 19 Kankin, Ninth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Practical True Random Number Generator
Date: 12 Jan 1999 15:24:15 -0500
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>R. Knauer wrote:
>>
>
>> Unless the ciphers created from the pads can withstand a Bayesian
>> Attack, the random number generator you propose is not verified to be
>> crypto-grade secure.
>
>Sorry to say that after having read in another thead many occurences
>of the term 'Bayesian Attack' I still have yet no concrete idea of
>an implementation of such an attack. I mean I am still ignorant of
>literatures that enable me to try to lauch such an attack on
>a given cipher.
Quoting from
http://fi-www.arc.nasa.gov/ic/projects/bayes-group/group/html/bayes-theorem-long.html
>Bayes' theorem gives the rule for updating belief in a Hypothesis H
>(i.e. the probability of H) given additional evidence E, and background
>information (context) I:
>
> p(H|E,I) = p(H|I)*p(E|H,I)/p(E|I) [Bayes Rule]
>
>The left-hand term, p(H|E,I), is called the posterior probability, and
>t gives the probability of the hypothesis H after considering the effect
>of evidence E in context I. The p(H|I) term is just the prior probability
>of H given I alone; that is, the belief in H before the evidence E is
>considered. The term p(E|H,I) is called the likelihood, and it gives the
>probability of the evidence assuming the hypothesis H and background
>information I is true. The last term, 1/p(E|I), is independent of H, and
>can be regarded as a normalizing or scaling constant. The information I
>is a conjunction of (at least) all of the other statements relevant to
>determining p(H|I) and p(E|I).
In practical terms, it means that you can reason from the observed
event (the evidence E) to the cause in a probabilistic fashion -- if
you observe E, then the most likely hypothesis H is one that maximizes
the probability of the hypothesis itself, together with the probability
that the hypothesis would produce the effect.
Stripped of (some of) the mathematical mumbo-jumbo, it means that
we can reason about the probability of a particular input text being
the plaintext based on the probability that a given stream was generated
by our generators.
-kitten
------------------------------
** 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
******************************
