Cryptography-Digest Digest #102, Volume #9 Thu, 18 Feb 99 14:13:04 EST
Contents:
Re: random number generator??? (R. Knauer)
Re: encryption debate (R. Knauer)
Re: Randomness of coin flips (R. Knauer)
Re: Randomness of coin flips (R. Knauer)
Re: More Security for Single-DES? (John Savard)
Re: True Randomness (Coen Visser)
Re: Randomness of coin flips (R. Knauer)
Re: Algorithm help (fungus)
Re: Randomness of coin flips ("Tony T. Warnock")
Re: Randomness of coin flips (Mark Carroll)
Re: True Randomness (Eric Norman)
Re: Decoding messages from ETI. (Medical Electronics Lab)
Re: Randomness of coin flips ("Tony T. Warnock")
Re: random number generator??? ("Sam Simpson")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: random number generator???
Date: Thu, 18 Feb 1999 14:13:46 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 18 Feb 1999 13:03:18 -0000, "Sam Simpson"
<[EMAIL PROTECTED]> wrote:
>You'll note that I refer to the numbers as "real random"... Basically
>there is no *proof* that the numbers are indeed random.
There can't be an algorithmic proof, otherwise the numbers would not
be truly random.
True random numbers defy any kind of algorithmic characterization,
including pseudo-random statistical tests.
>Take a user defined number of "user events" (which can be either key
>presses or mouse moves). An event includes the high resolution timer
>details, system clock details, the actual data from the event (x,y pos
>or key).
Why not just use text instead? It may not be as entropic as mouse
wiggles, but it is a helluva lot easier to obtain, and you can spend
the time you saved hashing the livin' bejeezuz out of it instead. All
you need to make sure is that it contains some entropy to begin with,
since you cannot distill pseudo-randomness if there is not present to
begin with.
I suggest using text from the Congressional Record, since there is
unlikely to a more entropic source of text available than the
ramblings of politicians. Choose the deliberations on the Clipper Chip
for sheer poetic justice. :-)
>I tend to be inclusive with the data hashed (e.g. rather than worrying
>about removing the least sig bits of the timer I just use all of the
>data).
It would seem that it would take more hashing if you left in all the
bits. Patrick Juola (IIRC) commented on this the other day, so if he
is tuned into this thread, perhaps he (or anyone else) could comment
on that.
>All of the events are run through a user selectable hash function
>(currently SHA-1, RIPEMD or Haval).
SHA-1 was invented by the govt. Do you really trust it? If you trust
the govt for anything, I have a helluva deal on a bridge in New Yawk.
Terry Ritter is a proponent of the CRC. I recommend reading his web
pages to see why, e.g.:
http://www.io.com/~ritter/NEWS2/CRCRAND.HTM
and others (use keyword 'CRC' for Search).
>This procedure is repeated until the desired number of bytes have been
>outputted.
I presume you have some way to quantify what is meant by "desired
number" in terms of the input.
>My empirical tests (with Diehard etc) show _very_ reasonable results,
>even for very low numbers of events per hash.
Those tests are pseudo-random tests, and therefore are not definitive
for purposes of proveably secure crypto. The digit expansion for pi
passes such tests, but is hardly a source of crypto-grade randomness -
once the attacker learns that it is the source of the keystream.
[NB: That statement may not completely true if one takes large offsets
into the digit expansion of pi, making exhaustive search for the
offset impossible.]
>Of course, this is in no way a "proof" of the strength (is a proof even
>possible?), but I used the term "real random" to differentiate from a
>deterministic RNG or stream cipher.
I believe what you mean is "crypto-grade randomness", in terms of the
practical impossibility of a cryptanalytic attack with known
technology. Now all you have to do is show that your scheme is
proveably secure, either theoretically or experimentally.
I have suggested one experimental method to test a keystream, but
never seem to attract any comments one way or the other. The method
consists in using the trial keystream to create test ciphers from
intelligible messages and subjecting them to the best analytical
attacks possible. Presumably those attacks will permit
characterization of the security of the keystream.
>Certainly I'd appreciate any comments you or anyone else has.....
This topic always manages to draw a lot of comments.
>>Hey, where is Ol' Sternlight these days?
>I think he is now accessing comp.security.pgp.discuss from a "home for
>the infirm".
>Drop in to c.s.p.d and view his jihad of the month :-)
No thanks. There are enough lunatics on sci.crypt for one lifetime.
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: encryption debate
Date: Thu, 18 Feb 1999 16:32:02 GMT
Reply-To: [EMAIL PROTECTED]
On 18 Feb 1999 15:45:37 GMT, [EMAIL PROTECTED] (Andrew Haley)
wrote:
>1. This is off topic in sci.crypt.
Not really. Govt infringement of personal privacy is every bit part of
crytpo. DUH!
But then we here in Texas can't really expect a marxist from England
to understand the concept of personal liberty, especially when you all
sat idly by and let your Fascist Rulers confiscate all your guns.
What a bunch of effeminate wimps. <jeez>
>2. Godwin's law- you lose, for the NNth time.
The hell with Godwin and his stupid "law". I will comment as I please.
Anyway you need to look up the term "Fascism" in the dictionary to see
that it has a general meaning distinct from the Nazi era. Here, I will
do it for you:
>From Websters Online, http://www.m-w.com/netdict.htm:
+++++
fascism: a political philosophy, movement, or regime that exalts
nation and often race above the individual and that stands for a
centralized autocratic government headed by a dictatorial leader,
severe economic and social regimentation, and forcible suppression of
opposition 2 : a tendency toward or actual exercise of strong
autocratic or dictatorial control.
+++++
The operative meaning of Fascism as I use it is: "a centralized
autocratic government headed by a dictatorial leader, severe economic
and social regimentation, and forcible suppression of opposition."
>3. Have you any idea how silly you sound?
Sci.crypt has a large population of libertarians, and my rhetoric is
about as libertarian as it gets. The fact that it causes you such
concern shows all of us that you oppose personal liberty.
>"The Fascist Beast in
>Harlot Washington," indeed. This is the sort of phrase that a nutcase
>writing letters to the editor in green ink uses, except that now (of
>course) nutcases use Usenet instead.
You should know, since you are the expert in nutcases writing letters
to the editor in green ink. I have never met anyone like that, and
certainly am not that kind of person myself.
>In your latest visit to sci.crypt I've been really impressed by the
>way that you've managed mostly to post about cryptography. However,
>it seems that happy situation has come to an end, and you are back to
>using sci groups to spread your ludicrous political views.
I would expect that from a marxist living in England. Go kiss St.
Tonie's slimy arse as he delivers you all to the Hun.
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Randomness of coin flips
Date: Thu, 18 Feb 1999 16:35:42 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 18 Feb 1999 08:11:48 -0700, "Tony T. Warnock"
<[EMAIL PROTECTED]> wrote:
>quincunx (qv.)
qv.?
I have not seen any prior reference. In fact a dejanews search came up
empty.
What on God's Green Earth (tm) is a "quincunx"?
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Randomness of coin flips
Date: Thu, 18 Feb 1999 14:34:00 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 18 Feb 1999 08:06:02 -0500, [EMAIL PROTECTED]
wrote:
>>If coin flips were truly independent of one another, what would you
>>expect to happen that is any different from what you observed?
>I remember reading an interesting paper years ago on coin flips. IIRC if a
>series of coin flips become biased one way or the other (ie: more heads
>than tails) the more skewed the series became the less likely it was to
>return to a 50-50 series and was more likely to become more biased.
There are many comments about random sequences in Li & Vitanyi's book
on Kolmogorov Complexity regarding Bernoulli processes such as coin
tosses. It is not at all surprising that during any particular finite
length run one observes skewing that does not satisfy pseudo-random
statistical tests. But that does not make the number any less random
(unpredictable).
The problem with deterministic tests for pseudo-randomness, such as
statistical tests for bias, is that they cannot give results that are
*certain*, but only results that are probabilistic - and that causes
them to be circularly defined. See p. 50ff in the book cited above:
"But we cannot assert a *certainty* about a particular number n of
throws, such as 'the proportion of heads will be p +/- eps for large
enough n (with eps depending on n)'. We can at best say 'the
proportion will lie between p +/- eps with at least such and such
probability (depending on eps and n0) whenever n > n0'. But now we
have defined probability in an obviously circular fashion."
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: More Security for Single-DES?
Date: Thu, 18 Feb 1999 16:30:55 GMT
"Peter K. Boucher" <[EMAIL PROTECTED]> wrote, in part:
>Somewhere along the route from your original suggestion, past the PRNG,
>and arriving at 256-bit RC4, I suspect the line of unexportable multiple
>encryption has been passed.
Even my suggestion would not be exportable, since it does make the key
longer. I was thinking about clock cycles, not the export laws.
John Savard
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (Coen Visser)
Subject: Re: True Randomness
Date: 18 Feb 1999 15:13:26 GMT
[EMAIL PROTECTED] writes:
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>>>>> You have read Li & Vitanyi's book, haven't you?
>>>>No,
>>> Then it is highly recommended that you do.
>>Why? Do they say anything new?
The book gives an very thorough overview on theory of Kolmogorov complexity,
randomness, incompressibility et cetera from the perspective of theoretical
computer science. Furthermore the book contains a nice introduction on
the basic principles needed to understand the main text. It's a wanna have.
>Read it and find out, especially the sections on randomness and
>induction/inference.
>The authors point out the absurdity of trying to characterize
>randomness using statistical tests. It seems that there is a bit of
>circularity contained in that scheme. Another absurdity comes from the
>realization that statistical tests measure certain kinds of
>regularity, and by definition randomness is that which has no
>regularity.
Hmm, they also talk about Martin-Lof tests for randomness. I don't know
your definition of a statistical test but a Martin-Lof test could be
regarded as one (I think). Not that it would be practicle, because you
need a lot of different tests to say something about the randomness of
an object.
Regards,
Coen Visser
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Randomness of coin flips
Date: Thu, 18 Feb 1999 15:20:03 GMT
Reply-To: [EMAIL PROTECTED]
On 18 Feb 1999 08:56:23 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>Well, *IF* -- and I'm cheerfully hypothesizing in blissful ignorance
>here -- *IF* Ms. So's coin flipping technique tends to put an even
>number of flips on the coin, then she will observe that the bigrams
>HH and/or TT tend to dominate over HT and TH. This means that
>she'll see longer than expected runs.
I fail to see how the regularity of having the "expected" amount of
bias present is a measure of true randomness. It may be a measure of
pseudo-randomness, but that is not appropriate to secure crypto.
It cannot even be said with certainty that those "expectations", which
come from pseudo-random tests for example, will even occur in the
limit of infinite length. There is every real possibility that a
random number will oscillate between one state of bias to the other
(offsetting) state of bias back and forth forever, still maintaining
its normality in the infinite limit. Li & Vitanyi have a writeup on
this phenomenon - it's called "complexity oscillations".
>Similarly, if her technique tends to put an odd number of flips on
>the coin, she'll see more HT and TH bigrams, which means she'll see
>shorter than expected runs.
So what? Again, you are using the term "expected", which is a
probabilistic concept. Probability only applies to pseudo-randomness,
not true randomness. (See Kolmogorov quote below).
>Either of these could be confirmed or disconfirmed quantitatively
>with a quarter, an elementary stats textbook, and a bit of -- or a
>lot of -- patience.
Pseudo-random tests have no bearing on true randomness, no matter how
well-versed you are or how patient you are. They are based on a
circular definition of probability as it applies to true randomness.
Here is Kolmogorov's own comments on this matter (p. 52, Li & Vitanyi,
op. cit.):
"In everyday language we call random those phenomena where we cannot
find a regularity allowing us to predict precisely their results.
Generally speaking, there is no ground to believe that random
phenomena should possess any definite probability. Therefore, we
should distinguish between randomness proper (as absence of any
regularity) and stochastic randomness (which is the subject of
probability thoery). There emerges the problem of finding reasons for
the applicability of the mathematical theory of probability to the
real world."
The goal of secure crypto is to prevent a crypanalyst from being able
to determine (predict) your messages from the ciphers. That requires
true randomness, otherwise the attacker *could* succeed in breaking
your system (however "unexpected"), in which case you do not have a
secure cryptosystem. Therefore, true randomness of the unpredictable
variety must be distinguished from pseudo-randomness of the stochastic
variety if you are to have any measure of certainty that your ciphers
are secure.
It is one thing to say that you know for *certain* that an attacker
has a 1% chance of breaking your system, and another thing altogether
to say that you know only with an "expected" probability that an
attacker has a 1% chance of breaking your system - whatever that
latter statement means.
Such circular thinking reminds me of using obscurity as a means of
creating security. As long as the attacker doesn't know your obscure
method, your ciphers are presumably secure - but once he does know
your method then all bets are off. The same is true of an attacker who
slips past the "expected" probability of pseudo-randomness, by
discovering some regularity which he can exploit for purposes of
predictability.
The digit expansion of pi passes all statistical tests for
pseudo-randomness, yet it is one of the most highly predictable
numbers in mathematics.
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Algorithm help
Date: Thu, 18 Feb 1999 09:33:48 +0100
Swartz wrote:
>
> I was just wondering if anyone had any info on how to make a algorithm
> that was based on time (you had to decrypt it during a certian time).
> If anyone has any info, I would appreciate it.
>
How do you find out the current "time"? If you ask the computer, you
might get a wrong answer (people can set the clock to whatever they
want to).
The only way I can think of doing this would be via the Internet.
You would need a decryption server which you can trust to provide
the correct time.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Randomness of coin flips
Date: Thu, 18 Feb 1999 08:11:48 -0700
Reply-To: [EMAIL PROTECTED]
For coin flips to appear "random" (rather than practical) the coin must be
flipped high enough that the initial configuration is washed out. Check the
protocols on craps at Las Vegas. The dice are bounced at least twice, at
least once higher than some line drawn on the sides of the table. Coins
could be flipped a minimum hight and required to bounce at least twice, on
at least two surfaces. The same principles apply in the construction of a
quincunx (qv.)
Tony
------------------------------
From: [EMAIL PROTECTED] (Mark Carroll)
Subject: Re: Randomness of coin flips
Date: 18 Feb 1999 17:26:07 +0000 (GMT)
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
(snip)
>What on God's Green Earth (tm) is a "quincunx"?
http://WWW-KSL-SVC.stanford.edu:5915/WEBSTER/ is your friend: "an
arrangement of five things with one at each corner and one in the
middle of a square or rectangle"
-- Mark
------------------------------
From: Eric Norman <[EMAIL PROTECTED]>
Subject: Re: True Randomness
Date: Thu, 18 Feb 1999 11:30:11 -0600
Tony T. Warnock wrote:
> > > So they can tell the left handers from the right handers eh?
>
> A sinister development dexterously achieved.
This is a gauche attempt at wordplay.
--
Eric Norman
"Congress shall make no law restricting the size of integers
that may be multiplied together, or the number of times that
an integer may be multiplied by itself, or the modulus by
which an integer may be reduced".
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Decoding messages from ETI.
Date: Thu, 18 Feb 1999 12:25:35 -0600
WhiteHat wrote:
>
> Greetings,
>
> I am searching for various methods of decoding/understanding a message
> received from an extra terrestrial intelligence (if/when we receive such a
> message). It is presumed that the ETI wants us to read the message. Thus,
> the task of understanding the message is the task of learning the "language"
> used to compose it (i.e. break the code of the language).
>
> I am looking for ways of "decoding" such a message. Any suggestions and/or
> links would be greatly appreciated.
Probably a better place to look would be under linguistics.
You might also get a lot of clues from archiology, they've had to
decode several languages where the symbols were unknown initially.
The basic task is finding patterns. Since math is a pretty basic
element of all "civilizations" the signal pattern may have some
kind of leading edge that describes a number or sequence of numbers.
Astronomy is also pretty basic, there may be a sequence that
describes the rotation of the galaxy or the positions of several
quasars which can be seen from any point in the galaxy.
If they send us a poem tho, I think it'll be pretty hard.
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Randomness of coin flips
Date: Thu, 18 Feb 1999 11:36:42 -0700
Reply-To: [EMAIL PROTECTED]
http://www.does.org/masterli/models.html
These guys seem to have models for sale.
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: random number generator???
Date: Thu, 18 Feb 1999 17:24:46 -0000
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
R. Knauer wrote in message <[EMAIL PROTECTED]>...
>On Thu, 18 Feb 1999 13:03:18 -0000, "Sam Simpson"
><[EMAIL PROTECTED]> wrote:
>
>>You'll note that I refer to the numbers as "real random"... Basically
>>there is no *proof* that the numbers are indeed random.
>
>There can't be an algorithmic proof, otherwise the numbers would not
>be truly random.
>
>True random numbers defy any kind of algorithmic characterization,
>including pseudo-random statistical tests.
Indeed.
>
>>Take a user defined number of "user events" (which can be either key
>>presses or mouse moves). An event includes the high resolution timer
>>details, system clock details, the actual data from the event (x,y pos
>>or key).
>
>Why not just use text instead? It may not be as entropic as mouse
>wiggles, but it is a helluva lot easier to obtain, and you can spend
>the time you saved hashing the livin' bejeezuz out of it instead.
I concieve this component will be used for creating random data for use
with session keys, IVs, asymmetric keys etc.
I strongly disagree that just munging text is as good as both text input
and mouse wiggles (but I can't prove it <g>).
>All
>you need to make sure is that it contains some entropy to begin with,
>since you cannot distill pseudo-randomness if there is not present to
>begin with.
Quite.
<SNIP>
>>I tend to be inclusive with the data hashed (e.g. rather than worrying
>>about removing the least sig bits of the timer I just use all of the
>>data).
>
>It would seem that it would take more hashing if you left in all the
>bits. Patrick Juola (IIRC) commented on this the other day, so if he
>is tuned into this thread, perhaps he (or anyone else) could comment
>on that.
I'd rather be conservative (with respect of "entropy bits") rather than
chuck them away needlessly.
Besides, for the intended platform, CPU cycles are cheap.
>>All of the events are run through a user selectable hash function
>>(currently SHA-1, RIPEMD or Haval).
>
>SHA-1 was invented by the govt. Do you really trust it? If you trust
>the govt for anything, I have a helluva deal on a bridge in New Yawk.
I couldn't possible comment. People far more adequately equipped have
looked at SHA-1 and found no weaknesses.
Still, people can choose to use RIPEMD or Haval if they strongly object
to SHA-1.
>Terry Ritter is a proponent of the CRC. I recommend reading his web
>pages to see why, e.g.:
>
>http://www.io.com/~ritter/NEWS2/CRCRAND.HTM
>
Yes, I've read a lot of Mr Ritters stuff.
>and others (use keyword 'CRC' for Search).
>
>>This procedure is repeated until the desired number of bytes have been
>>outputted.
>
>I presume you have some way to quantify what is meant by "desired
>number" in terms of the input.
At creation time, application developers specify the "Events per hash" &
"Bytes required".
>>My empirical tests (with Diehard etc) show _very_ reasonable results,
>>even for very low numbers of events per hash.
>
>Those tests are pseudo-random tests, and therefore are not definitive
>for purposes of proveably secure crypto. The digit expansion for pi
>passes such tests, but is hardly a source of crypto-grade randomness -
>once the attacker learns that it is the source of the keystream.
Indeed. I've done my homework and read Knuth, HAC etc on this topic....
>>Of course, this is in no way a "proof" of the strength (is a proof
even
>>possible?), but I used the term "real random" to differentiate from a
>>deterministic RNG or stream cipher.
>
>I believe what you mean is "crypto-grade randomness", in terms of the
>practical impossibility of a cryptanalytic attack with known
>technology.
Yes, that sounds like a suitable phrase.
<SNIP>
>>>Hey, where is Ol' Sternlight these days?
>
>>I think he is now accessing comp.security.pgp.discuss from a "home for
>>the infirm".
>
>>Drop in to c.s.p.d and view his jihad of the month :-)
>
>No thanks. There are enough lunatics on sci.crypt for one lifetime.
:-)
Cheers,
- --
Sam Simpson
Comms Analyst
http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because he's
kill filed. See http://www.openpgp.net/FUD for why!
=====BEGIN PGP SIGNATURE=====
Version: PGP 6.0.2
iQA/AwUBNsxM0+0ty8FDP9tPEQI/AwCgtFxfdAEIR11pKbZNikThJ/HbiXgAnRM+
Usj1fEbASGACBdAgGw/pBqtb
=E5e4
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
