Cryptography-Digest Digest #48, Volume #9 Sun, 7 Feb 99 09:13:04 EST
Contents:
Re: Loony question
Re: Encryption Algorithms
Re: Simple newbie challenge -- variable length codes (line noise)
Re: Foiling 56-bit export limitations: example with 70-bit DES
([EMAIL PROTECTED])
Re: *** Where Does The Randomness Come From ?!? *** (R. Knauer)
Re: *** Where Does The Randomness Come From ?!? *** (R. Knauer)
Re: Java random (Logi Ragnarsson)
Re: Java random (Logi Ragnarsson)
Re: RNG Product Feature Poll (Herman Rubin)
Re: RNG Product Feature Poll (Herman Rubin)
Re: I hate to bring up PRNGs again... (Herman Rubin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Loony question
Date: 7 Feb 99 11:43:48 GMT
Trevor Jackson, III ([EMAIL PROTECTED]) wrote:
: AbsolutAF3 wrote:
: > >Would a particularly awful track off a CD with a lot of
: > >screeching guitars and howling monkeys be a decent source
: > >of random numbers?
: > It really depends on your use of the numbers.
: The introduction to this sentence gave me a chill of dread because I feared you
: would close with "... your taste is music."
That would clearly be wrong. However, the taste in music of potential
cryptanalysts would affect how effectively random the audio signal would
be. But one's own taste in music is irrelevant.
However, rather than make assumptions about the taste in music of
cryptanalysts, one _is_ advised to use the numbers correctly, by using
only the LSBs, hashing, and so on.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Encryption Algorithms
Date: 7 Feb 99 11:38:35 GMT
Asher Pressman ([EMAIL PROTECTED]) wrote:
: Does anyone know of any good sites where i can find encryption
: algorithms? I've been looking for a while and i just can't find
: anything...
I describe a few algorithms on my web site,
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
http://members.xoom.com/quadibloc/index.html
but there is no source code or test vectors. Also, on the links page are
links to a few other crypto pages, including one or two with lots of links
and stuff.
John Savard
------------------------------
From: [EMAIL PROTECTED] (line noise)
Subject: Re: Simple newbie challenge -- variable length codes
Date: Sun, 07 Feb 1999 04:08:56 -0800
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(DonGraft) wrote:
>I'm a total newbie here, so forgive any stupidity or naivete!
>
>Suppose you have a simple code where each letter of the
>plaintext is replaced with a string of binary 0s and 1s, but
>the number of them differs for each letter. Actually the letters
>are placed at the leaves of an arbitrary binary tree, and the code
>is determined by traversing the tree to the desired letter and
>noting the decisions at the successive nodes.
>
>How might such a code be cracked? Please remember I am
>a newbie so the more complete the answer the better.
>
>Thank you for your patience if this is a well-known thing.
>
>Respectfully,
>Don
This is compresion not encription. some of the best compresion systim use
decision trees like you discribe. Congrats you have just independantly
invented lzw/lzh compresion! But as a cypher the randon linking of letters
to leaves would be verry easy for a computer to gess.
--
----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.2
mQCPAjBLsOcAAAED/ArhyRBT+BCUswtoZjflht+IJR1OOv5FiaTJ3lRvXPDfBCAt
a32Z7T+p7PJkEEWz5rnWaUMgNS8bVM0exU9hAjT7frkZogOjZ7z0OyLQRqwuDFAx
RilC0PNvi/8KsDxVU9/pjnQxwEiEWpw1jF0L31YmXSiXKQCvUiUD/HERsCpdABEB
AAG0IUxpbmUgTm9pc2U8T3V0IE9mIFBhcGVyIEAgaWQuY29tPokAlQIFEDBtpuMl
A/xxEbAqXQEBqSgD/Ao9nLK1XflDLrWX/UazWAe2Z3WsiJBJjukSeTgTH8GPNjbq
HCaTOEpX736OmAhGEBntcqYWPe+opbj9IPfLabka+UAYin6xNuhU3vNzx10Bnv59
HnL8L3p2owc2+FY/4tlKkeLvqOo7e9SiAF9ULnlQ4KzPhypIoMqdIDWt8+Sf
=BadZ
=====END PGP PUBLIC KEY BLOCK=====
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Foiling 56-bit export limitations: example with 70-bit DES
Date: Sun, 07 Feb 1999 12:29:17 GMT
C O R R E C T I O N
My posting below mistakenly used a probability value of 1:2^112 for DES key
collision that is valid for higher-order M-DES -- instead of the value 1:2^56
for the case at hand, for 70-bit M-DES. The two described M-DES protocol
impossibilities "STOP 1" and "STOP 2" for the "wild-guess-attack" are NOT
altered by this correction. This correction however serves to avoid future
wrong references.
The CORRECTED passages are given below, where the last passage points to the
even lower key-collision probabilities for higher M-DES modes (as I will post
in the next future).
In article <79j465$4ej$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
.....
> Thus, the case where the SAME DES key but DIFFERENT unknown-keys are used
> would not happen unless so randomly choosen -- for which your probability is
> lower than 1 in 2^56. This is effectively zero, even in the Universe`s
> lifetime.
.....
>
> I guess we cleared that above now, in my reply. The point is not that the
> wild-guess-attack could not exist -- in a quaint way it does exist -- but
> that it could not happen. Perhaps, we are in agreement? BTW, the 1:2^56
> probability against that wild-guess-attack gets even lower in other modes of
> M-DES.
>
Cheers,
Ed Gerck
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Crossposted-To: sci.philosophy.meta,sci.physics,sci.physics.relativity,sci.skeptic
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: Sun, 07 Feb 1999 12:50:33 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 07 Feb 1999 03:05:38 +0000, Colin Day <[EMAIL PROTECTED]>
wrote:
>Math is a closed system? I think that Godel would dispute that (if he weren't
>dead)
You left out Turing, who is also dead. But Greg Chaitin is alive, and
he disputes that quite vigorously:
http://www.umcs.maine.edu/~chaitin/
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
Bob Knauer
"To compel a man to furnish contributions of money for the propagation
of opinions which he disbelieves is sinful and tyrannical."
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Crossposted-To: sci.philosophy.meta,sci.physics,sci.skeptic
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: Sun, 07 Feb 1999 12:53:25 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 6 Feb 1999 19:30:14 -0800, "PAC" <[EMAIL PROTECTED]> wrote:
> I didn't really want to get into this type of discussion and take away
>the tone of this thread, but what we percieve is really out there, but from
>one aspect, to know it in its entirety means to be merged 100% into an
>object and with that object. Since we are never at that situation, a
>separation still exists regardless of what percieved.
Quantum Mechanics prevents complete knowledge of an object, merged or
separate.
Bob Knauer
"To compel a man to furnish contributions of money for the propagation
of opinions which he disbelieves is sinful and tyrannical."
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (Logi Ragnarsson)
Subject: Re: Java random
Date: 7 Feb 1999 10:23:57 GMT
In <79i2ts$jp8$[EMAIL PROTECTED]> "Else" <[EMAIL PROTECTED]> writes:
>SecureRandom *is* part of the JDK. It uses SHA. I believe SHA is not export
>controlled (am I correct on this?). FYI - SecureRandom is very slow. Its
>seeding takes over 1 second.
Hash functions and signature schemes can be exported from the US, I'm
sure. SecureRandom does indeed take a long time for the initial seeding,
but it only does this for the first instance of SecureRandom that you
create. What you could do is to launch a thread at start-up which creates
a SecureRandom instance. Then creating more instances later will be much
faster.
--
Logi Ragnarsson - [EMAIL PROTECTED] - [EMAIL PROTECTED]
Mathematics and CS student at the University of Aarhus
------------------------------
From: [EMAIL PROTECTED] (Logi Ragnarsson)
Subject: Re: Java random
Date: 7 Feb 1999 10:34:50 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Paul Rubin) writes:
>In article <79i41h$lim$[EMAIL PROTECTED]>, Else <[EMAIL PROTECTED]> wrote:
>>I made an implementation similar to SecureRandom. I setup a counter which
>>just goes count++;
>>while another thread sleeps for 10 ms. 10 ms is enough for the counter to go
>>to a few thousand on an average Pentium. I think it's enough entropy for one
>>byte. The whole 16 bytes takes just 160 ms, which is way faster than
>>SecureRandom. I think it should be enough for this application.
>I'm a little skeptical of this. If the counter goes to a few thousand
>in 10 ms, what is the statistical distribution if you do that several
>thousand times? Have you looked at that? You might be getting only a
>few bits of useable entropy each time, if that much (say the count
>reaches 3403 the first time, then 3315, then 3402, etc.) If you're
>going to use this method I'd advise collecting all the output of the
>counters and hashing it before using it.
I did something similar. I measured how mlong it took for the loop to
reach 1024 and then used that period (but never less than 5ms) for a
scheme like the above, keeping the lowest byte of the counter. The output
does not compress, so it isn't completely useless. Are there better
tests?
Just to be sure I collect (by default) 128 bytes in this way, and hash
them to get the initial state of an MD5-based PRNG.
Of course, this all assumes that the scheduler isn't completely
deterministic, which it possibly might be on some platforms. Also, it
helps to make sure that the machine is doing something else while the
seeding is being done. Collecting the initial entropy in a separate
thread while the application is starting up might help a bit.
>I'm not even completely convinced that the numbers from SecureRandom
>are really that random if they're for very high security purposes.
>But I haven't looked into it that much.
--
Logi Ragnarsson - [EMAIL PROTECTED] - [EMAIL PROTECTED]
Mathematics and CS student at the University of Aarhus
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: RNG Product Feature Poll
Date: 7 Feb 1999 08:12:50 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 2 Feb 1999 10:27:58 -0500, [EMAIL PROTECTED] (Herman Rubin)
>wrote:
...................
>I am using the strong crypto definition of random, not the statistical
>definition. In fact, that is what this whole discussion is about. I
>maintain that statistical descriptions of events are inadequate to
>characterize crypto-grade randomness, which is suitable for use in the
>OTP system.
Reasonable statistical properties are more than enough for cryptography,
while the other may not be the case. Also, one can include, in the
statistical tests, those which will be needed for good cryptographic
sequences of bits.
>>If one uses an analog-threshhold detector, it can get quite
>>complicated, and not even be a renewal process. That is, the times
>>between detections may not even be independent.
>The time between detections will always be indeterminant. Saying that
>you know that the detection of a decay event cannot occur during a
>particular interval does not mean you can say that when a detection
>does occur.
>Consider 4 times:
>t1, the time when a first decay is detected;
>t2, the time when a decay first cannot be detected;
>t3, the time when a decay can first be detected;
>t4, the time when a decay is secondly detected.
>The interval during which no detection can occur is t2 -> t3.
>The detection of a second decay event at t4 is in no way determined by
>t2, t3, or t3-t2. That is, the value if t4 cannot be known even though
>it is known that it is not any time between t2 and t3.
Not being known is quite different from having no knowledge of the
deviation of the probability from what is expected. The observed
interval t4-t1 and the interval (continuing the numbering) t7-t4
are not necessarily independent, and the dependence between the
various intervals can become quite complicated.
>If the interval of non-detection could cause you to know when a
>detection CAN occur, then the decay process would not be
>indeterminant.
>Kolmogorov algorithmic complexity theory addresses this issue (see Li
>and Vitanyi, op. cit.). If you have a random process x1, followed by a
>non-random process x2, followed by a random process x3, then the
>overall process is represented by x = x1 . x2 . x3, where the dot
>operator means algorithmic concatenation.
>Here x1 is the detection of the first decay event, x2 is the
>non-detection of decay events for a specified interval, and x3 is the
>detection of a subsequent event after that interval.
Why does t2-t1 have to be non-random? In what is known as a type 2
counter, it is random. Even in type 1 counters, the non-constancy
of the circuitry will make it random. Analog processes may be non-
random for PRACTICAL purposes, but whether they are so here is by no
means clear. It may or may not be important.
>The algorithmic complexity of x, K(x), for the overall process is not
>significantly reduced by the inclusion of the non-random process x2.
>IOW, your certainty that no decay event can be detected in the
>blanking interval, t2 -> t3, does not effect the randomness
>(indeterminancy) of detection of a second detection after that
>interval.
It is quite possible that it does, in particular, if particles to be
detected have different energies.
>>I have just looked at this; the numbers should be reasonably good, but
>>not that good. One problem is that of measuring the time; this can
>>be seen to produce biases and failure of independence on the order of
>>10^{-4}. This should not be a problem for cryptography, but would be
>>for statistical use.
>I do not understand what you just said. You seem to be agreeing with
>me that statistical randomness has no impact on crypto-grade
>randomness.
>Also I do not see how the measurement technique employed in HotBits
>results in bias, much less how you managed to quantify it with a
>number such as 10^{-4}.
I did not quantify it; I gave an estimate on the best order of the
problem. How accurately can a counter measure a short interval of
time?
>Please elaborate on all these issues.
>>There is always Murphy's Law to worry about. One might barely be
>>able to test at a high enough level for cryptographic use, but
>>this would not be good enough for statistical use, where 10^10
>>to 10^15 bits are commonly used now.
>Statistical tests for TRNGs are useless. If one cannot generate
>crypto-grade random numbers algorithmically, then one cannot test
>crypto-grade randomness algorithmically, otherwise one could generate
>such numbers algorithmically by a simple filtering scheme.
This does not follow. One can use a physical device which generates
good random numbers when it is working properly. One must guard
against the device not working properly.
>A TRNG must be capable of generating all possible sequences of a given
>finite length equiprobably, therefore its output cannot be filtered in
>any way. Each of the 2^N sequences of length N must be output
>equiprobably, or the complete indeterminancy of the TRNG is destroyed,
>and proveable security cannot be achieved.
If that is your definition, there is no such thing as a TRNG. The
various sequences may be CLOSE to equiprobable, but no physical
device is going to make them EXACTLY equiprobable.
>Only by conducting a careful design audit of the TRNG itself can one
>certify that it is proveably secure. That audit includes testing the
>subsystems that make up the TRNG, not its output. Testing the output
>results in creating a bogus distribution of "good" and "bad" strings,
>which violates the specification for a TRNG, namely that it be capable
>of outputting *ALL* possible strings, not just "good" ones based on
>some statistical notion of what constitutes "good" or "bad" strings.
The components are not going to have the precise properties you
seem to want for them. They have analog aspects throughout, and
physical equipment drifts.
>If a TRNG is not capable of generating all possible strings
>equiprobably, it is not a TRNG for purposes of secure crypto.
It could do a very good job.
A good criterion would be that the probability that a bit is 1, given
all preceding bits, is small. The channel capacity for the one
trying to read the message without the key is roughly proportional to
the square of the bias, and channel capacity is only an asymptotic
rate, rarely well approximated for reasonable length messages.
For secure cryptography, there are strings which one would not want
to use. Using a string which would enable the intercepter to have
a good chance of guessing some or all of the message is something
which should be avoided for cryptographic purposes.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: RNG Product Feature Poll
Date: 7 Feb 1999 08:45:48 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On Wed, 3 Feb 1999 18:01:35 GMT, [EMAIL PROTECTED] (Peter Pearson)
>wrote:
>>In 1955, the Rand Corporation published a book entitled "A Million
>>Random Digits with 100,000 Normal Deviates," described at
>>http://www.rand.org/publications/classics/randomdigits/.
>>Today's online version doesn't mention radioactive decay, but I
>>believe I recall that that was the basis for their "random frequency
>>pulse source."
>>So, don't let overbroad patent claims scare you....
>A radioactive decay rate of 100,000 counts per second sounds a bit
>high for 1955. At that high count rate they could have been measuring
>the quench process in their detector instead of the actual radioactive
>decay events.
I believe it would have been possible in 1955; as I recall, Geiger
counters could run as fast as 10^6 counts per second. By 1970,
certainly rates of better than 10^8 were possible using scintillation
counters and photomultipliers. One could easily produce 10^7
high-quality bits per second by using the parity of the number of
counts in intervals of that length from a counter with a rate well
under 10^9. It turns out that one wants to use a quite substantial
dead time.
The problem is that one cannot do that much testing. To test for
an accuracy of 10^{-3}, one needs about 10^7 counts. This might
be good enough for cryptography, but not for simulation purposes.
My suggestion is to use 8 independent files, XOR them, and accept
the result if at least 5 pass.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: I hate to bring up PRNGs again...
Date: 7 Feb 1999 09:06:23 -0500
In article <[EMAIL PROTECTED]>,
Brett W <[EMAIL PROTECTED]> wrote:
>Hi
>Just a quick newbie question:
>Although you may have a whole tonne of things that are psuedo-random and
>not that high on entropy, could you combine several of these independant
>devices together to make stronger PRNGs?
>Probably not is my guess, but I'd like an experienced response.
This has been very seriously suggested. One of the types of PRNGs,
which have very long periods and are easy and fast, are the
ones for which words have the recurrence
x[n] = x[n-a] OP x[n-b],
where OP can be one of XOR, +, -, and others. If the larger of
a and b is a fair-sized Mersenne number, and the smaller one for
which the full period is obtained, the period is long enough for
the entire estimated future lifetime of the universe. But it was
long suspected, and finally shown, that these have subtle flaws
when used for statistical purposes; the Mersenne number used in
this was 1279; the period is more than 10^380.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
** 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
******************************
