Cryptography-Digest Digest #430, Volume #9 Tue, 20 Apr 99 19:13:04 EDT
Contents:
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: Anybody has a working copy of DIEHARD ? ("Kevin G. Rhoads")
Re: Generalized TEA paper ([EMAIL PROTECTED])
Re: NSA not so bad after all? (was Re: RC6 new key standard from AES conference?)
(David Hamilton)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Terry Ritter)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Terry Ritter)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Terry Ritter)
How long for export application? (Dale Mosby)
Re: AES Competition (Paul Koning)
Re: dumb question on releasing source code (Paul Koning)
encrypted and AUTHENTICATED tunnels (Phil Howard)
Re: How long for export application? (Phil Howard)
Re: AES R1 comments/papers available & my views (Bauerda)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 20 Apr 1999 21:04:15 GMT
Reply-To: [EMAIL PROTECTED]
On 20 Apr 1999 13:56:41 -0500, [EMAIL PROTECTED] (Herman
Rubin) wrote:
>>On Mon, 19 Apr 1999 22:00:55 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
>>wrote:
>>>If I buy a bit-stream generator that has been advertised as generating
>>>a "truly random" (uniform equiprobable) bit stream, and the acceptance
>>>test shows the likelihood of its meeting its advertised specification
>>>is less than 1 in 1,000,000, I am justified in rejecting it and finding
>>>another vendor.
>This method of making decisions is an aspect of the typical misuse
>of statistics. No test can find the likelihood of it meeting the
>advertised random behavior without having a prior distribution of
>the various states of nature.
I believe you are correct in saying that. It would seem that quantum
randomness is the consequence of all of nature being involved in some
way in every process that results in a measurement. Since it is
impossible to know that state of nature without disturbing it, it is
therefore impossible to determine the behavior of individual quantum
measurements. That indeterminance we call true randomness because
there is no possible way ever to determine the outcome of the quantum
process.
>What one can test is the probability
>that a result in a given class would occur by chance if the precise
>hypothesis is true.
>But a precise null hypothesis is essentially always false, and
>also the type of probability statement made is not what one should
>be considering.
One of the requirements for a TRNG (used in crypto) is that it must
not be biased in any way. Therefore the null hypothesis is:
H0: p = 1/2.
H1: p <> 1/2.
I see no reason why comprehensive experimental tests cannot be
constructed to test that hypothesis to within an arbitrarily small
error. For example, those tests would certainly look not only at 1-bit
bias, but at 2-bit bias, 3-bit bias, etc. They would look at very
large multiple samples and compare/contrast them to one another.
>>And you could not be faulted. Just realize that you did that to be on
>>the safe side, not because you made a reasonably correct
>>determination. The TRNG could have been a perfectly good device.
>If you take this position, NOTHING can be decided by looking
>at the data.
I certainly did not mean to imply that. I assumed that the original
poster was referring to his beloved simplistic small sample
statistical tests (like those found in Triola), and not a rigorous
program of experimental testing.
I merely agreed that simplistic small sample statistical tests can be
useful as diagnostic indicators. That is not the same as saying that
they are valid in terms of substantiating the rejection of the null
hypothesis to within an arbitrarily small error.
The poster has a reason to suspect the TRNG is broken based on his
prejudices, and therefore temporarily reject it if he sees fit. We do
that all the time without realizing it. The fact that such rejection
is not based on a reasonably certain determination is another matter.
How he acts on that decision to reject the TRNG is something that was
not discussed, and is probably why you commented as you did. I would
assume that there was some kind of further involvement with the TRNG
maker. If the TRGN was designed carefully, the maker could have then
run internal tests on the subsystems to prove out the device. The
actual decision to buy the TRNG would then be based on those internal
tests and an audit of the design.
BTW, notice that he could easily be fooled by a fake TRNG that did
satisfy his beloved statistical tests. That is a far greater danger
than inadvertantly rejecting a good TRNG. That's why I have called
such simplistic tests Snake Oil Tests.
They are just as useless as deciding that a woman would make a good
wife just because she is good looking.
>The device could be a generator with 99% 1's, and
>it still could produce any given sequence.
That is exactly what I have been saying all along - to the apparent
consternation of some posters here.
But one thing I have agreed with them is that simplistic small sample
statistical tests can be useful as diagnostic warnings. I would be
very prejudiced against a TRNG that put out a sequence with such high
1-bit bias as 99% 1s. For example, it could have a malfunctioning
output stage.
I would, however, not conclude that it was not good enough of a TRNG
for my purposes on that basis alone - any more than I would conclude
that a generator which did pass those simplistic statistical tests was
a good TRNG.
>One always observes a finite sequence. Probability can deal with
>infinite sequences, but probabilities are not known. Only data
>is known.
And those data, if there are enough, can be used to determine if they
are strong enough to reject the hypothesis that p = 1/2 to within an
arbitrarily small error.
>"Ensemble" is a term coined by physicists who have the not uncommon
>difficulty with accepting probability as primitive.
"Ensemble" is also used by mathematicians. It was used in many places
in Feller's book, and also in Li & Vitanyi. For example, consider this
direct quote from Feller:
+++++
"Thus, contrary to widespread belief, the time average for any
individual game has nothing to do with the ensemble average at any
given moment."
--Feller, p. 152.
+++++
Or perhaps Feller is a closet physicist. :-)
>If it is a physical process, it is random.
If it is a quantum physics process, it is random. Classical chaotic
processes are not truly random in the strictest sense of the term.
Even a fair coin toss is not truly random, although it might be close
enough to be useful in some applications.
Only quantum processes can be truly random.
>It does not have the ideal properties; the question is, is it close enough.
Yes. One of the required properties for a TRNG for crypto is that it
exhibit very little bit-group bias. The extent to which a given TRNG
does have a slight bias is the extent to which the ciphers it creates
leak information to the cryptanalyst - and that depends crucially on
message traffic volume.
It would be good protocol to dismantle a TRNG and reassemble it
periodically to destroy any charafteristics that could leak
information - for example, removing and reinstalling the radioisotope
in a radioactive TRNG. Perhaps changing detectors would be advisable
too.
For shot noise TRNGs, replacing the diode would be advisable. If the
TRNG was a fair coin toss, changing coins periodically would be
advised. Even strongly mixing of the outputs of several different
TRNGs in different ways would help. Have one strong mixing scheme one
day, another another day.
IOW, you want to randomize the sources of randomness.
>This takes
>a large enough data set to make a reasonable determination, and
>the problem is much more difficult than statistics texts admit.
That is *exactly* what I have been saying for the past several months.
I still cannot figure out why so many people here are having such a
difficult time understanding that, especially in light of the
overwhelming evidence.
>The question is when to act as if something is true, when one knows
>it is not.
That is where the "arbitrarily small error" comes into play. For
example, if I test a TRNG experimentally and decide that it has a
probability p = 0.50 +- 0.05, is that good enough for purposes of
crypto? Since those are the odds at roulette and since Las Vegas gets
by quite handsomely with them, I would be suspect in using a TRNG with
that much bias.
If on the other hand, I determined that the TRNG had p = 0.5013 +-
0.0002, I might be inclined to use it.
Bob Knauer
If you think health care is expensive now, wait until it's FREE!
------------------------------
From: "Kevin G. Rhoads" <[EMAIL PROTECTED]>
Subject: Re: Anybody has a working copy of DIEHARD ?
Date: Tue, 20 Apr 1999 11:24:07 -0700
DIEHARD is available from a variety of sources, not just
Prof. Marsaglia's site. I believe you can find it on Simtel. It
is also on the Numerical Recipes CD Rom.
If all else fails, e-mail me, I have two versions of the source,
an older Fortran and the newer an F2C transliterated C, as well
as Prof. Marsaglia's FPS1 build to a DOS extended EXE and
some DVF builds I made to Win32 Console mode.
Of course, you can use the F2C transliteration with just about
any C compiler as well.
--
Kevin G. Rhoads, Ph.D. (Linearity is a convenient fiction.)
[EMAIL PROTECTED]
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Generalized TEA paper
Date: Tue, 20 Apr 1999 20:59:53 GMT
<snip>
To be silly and reply to my own message... why not...
Anyways, I re-uploaded the file, because it was an older copy (whoops!).
Right now the more up-to-date copy is available as posted.
Does anyone have any PS tools?
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (David Hamilton)
Subject: Re: NSA not so bad after all? (was Re: RC6 new key standard from AES
conference?)
Date: Tue, 20 Apr 1999 18:43:56 GMT
=====BEGIN PGP SIGNED MESSAGE=====
"Steven Alexander" <[EMAIL PROTECTED]> wrote:
>The NSA is very much ahead of the rest of the world in terms of
>cryptographic and computer technology. They were researching crypto long
>before the rest of the world.
(snip)
Wasn't the USA President Nixon once asked 'What did you know and when did you
know it?'? So, it might be a bit risky to state the above as absolute truths.
For example, I doubt whether it is public knowledge what the Chinese,
Indians, Japanese, Russians etc (put in your own favourite nationality) know
about cryptography and when they knew it. And then there's always the lone
genius or talented mathematician or excellent cryptographer who doesn't work
for the USA NSA. And then there's always Andrew Wiles.
So, maybe the USA NSA is ahead (rather than 'very much ahead') of the rest of
the world, but perhaps it isn't.
David Hamilton. Only I give the right to read what I write and PGP allows me
to make that choice. Use PGP now.
I have revoked 2048 bit RSA key ID 0x40F703B9. Please do not use. Do use:-
2048bit rsa ID=0xFA412179 Fp=08DE A9CB D8D8 B282 FA14 58F6 69CE D32D
4096bit dh ID=0xA07AEA5E Fp=28BA 9E4C CA47 09C3 7B8A CE14 36F3 3560 A07A EA5E
Both keys dated 1998/04/08 with sole UserID=<[EMAIL PROTECTED]>
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
Comment: Signed with 2048 bit RSA key
iQEVAwUBNxzKOso1RmX6QSF5AQFIQQf/Tpk05Tbnd4x1nSXdIKiJjIc71fOXndMh
9kvjbbcSSyh/LyMWjpu/Fitwl4tYq/lOL9QOwHd1zMaVHyklpNcZUUCSHN4awaiR
mF0mXT1dU9IJok9HfjVtB2QLFMdqIU128bGB1/iTZIsIbYuQ3GYI4+mxLC7Gp//P
EJGFYVj0Uil0HEvfa3+xfGII4/H0tt2S2DnMvbhFDIs2FRIgGM5MvPCH6QqWTkKk
y1ldy5muB5MGfAtSZmo21d2roBAx66xUu1+XxegMAqI6cM9AWL5MlNTmqwoxF/Pb
9nGfPt/1NT3Dc1HBluGCxP2oYNAdmWUGatzml2k6q4ZJkxEKDPv+rQ==
=6Wpc
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Tue, 20 Apr 1999 22:03:33 GMT
On 18 Apr 99 02:05:37 GMT, in <[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] () wrote:
>Terry Ritter ([EMAIL PROTECTED]) wrote:
>: As I see it, the real opportunity for
>: cryptanalysis is as part of a dynamic and interactive cipher design
>: process, as opposed to final certification.
>
>Two comments are warranted here.
>
>- Since cryptanalysis represents the "hard" part of the work in designing
>a cipher, this is why cipher designers should themselves know something
>about cryptanalysis;
I agree.
>- And I think you can see why this design process actually _increases_ the
>probability of a design which is strong against known attacks, but weak
>against a future attack someone might discover.
You lost me on that one.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Tue, 20 Apr 1999 22:03:47 GMT
On 18 Apr 99 01:55:36 GMT, in <[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] () wrote:
>Terry Ritter ([EMAIL PROTECTED]) wrote:
>
>: On 16 Apr 1999 17:21:22 -0400, in <7f89ki$gng$[EMAIL PROTECTED]>,
>: in sci.crypt [EMAIL PROTECTED] (Patrick Juola) wrote:
>
>: >[...]
>: >So you're suggesting that a cypher that has withstood years of
>: >intensive analysis by professionals is *NO* better than a cypher
>: >that has not been analyzed at all?
>
>: It is not provably better. And not provably better admits the
>: possibility of contradiction. So we do not know. Which means that
>: interpreting years of intensive analysis as strength is nothing more
>: than DELUSION. Cryptanalysis of any length whatsoever provides no
>: rational scientific indication of strength.
>
>Yes and no.
>
>Your point is valid, however, what do we do if there is no way to obtain a
>lower bound on the strength of a cipher? I fear this is quite possible:
I agree.
>proving a cipher is strong against attacks we can't even imagine seems to
>me to be equivalent to solving the halting problem.
We have the testimony of 50 years of mathematical cryptography which
has not achieved the Holy Grail. I just think reality is trying to
tell us something.
>Then it does make sense to look at the upper bound, because it's one of
>the few indications we have.
No. Completely false. I see no reason why the upper bound should
have any correlation at all to the lower bound.
In any security audit, we have to consider the worst case attacks, not
just the ones we expect, and not just the ones we tried.
>But it also makes sense - and here, I think,
>we come closer to agreement - not to put too much faith in that upper
>bound, and to add constructs of different types, and constructs that seem
>like any mathematical tools to analyze them which would be useful for
>cryptanalysts are *far* in advance of the state of current knowledge.
I'm not sure I understand this fully.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Tue, 20 Apr 1999 22:03:24 GMT
On 18 Apr 99 01:49:42 GMT, in <[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] () wrote:
>Terry Ritter ([EMAIL PROTECTED]) wrote:
>: This is seriously disturbing: The issue is not who makes a thing, but
>: instead what the thing actually is. Deliberately judging a design in
>: the context of who made it is actually anti-scientific, and should be
>: widely denounced as the superstition it is.
>
>That's true *if* judging a cipher that way is used as a substitute for
>actual analytical study of the cipher itself by a competent individual.
>Where the services of an expert are not available, or there is
>insufficient time to fully evaluate all candidate ciphers for an
>application, choosing a cipher from a respected source is not
>"superstition", and it is the kind of choice people make all the time:
>i.e., when shopping for a new computer.
Is shopping for a cipher like shopping for a new computer? Yes, I
think so, but this situation is not a technical discussion between
people of expertise but, rather, ordinary users who really have no
choice but to rely upon promotion and rumor.
When experts themselves cannot fully characterize the strength of a
system specifically designed to produce strength, we know we are in
trouble. It's just that this is the way it's always been, and most of
us forgot what it means. It does not mean that we must rely upon the
same promotion and rumor as ordinary users.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Dale Mosby <[EMAIL PROTECTED]>
Subject: How long for export application?
Date: Tue, 20 Apr 1999 15:01:54 -0700
Does anyone have a recent data point for the time required
to get a classification request run though the system? (A question
for USA readers of course.)
Feb 2nd an application for "Classification Request" went to the
Bureau of Export Administration. It has been with the NSA since
February 26th. As of April 12 BXA can't tell me anything other
than "it's with NSA". All I'm trying to do is get approval to change
a 40 bit DES algorithm to 56 bit DES. This has to be the most
straightforward request that could be submitted. Has anyone
run something through recently? I'd love to know what sort
of turn-around time people have experienced.
Thanks, Dale [EMAIL PROTECTED]
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: AES Competition
Date: Tue, 20 Apr 1999 14:08:45 -0400
"A [Temporary] Dog" wrote:
>
> On Sat, 17 Apr 1999 22:13:05 +0100, "Michael Scott" <[EMAIL PROTECTED]>
> wrote:
> >
> >I must say Rijndael is looking good, given that its completely patent free,
> >scales nicely to various architectures, and can also be used as a one-way
> >hash. Its only problem seems to be its awful name.
> >
> How do you pronounce that anyway? I've been (mentally) calling it
> "Rinj N Dall" (three syllables, like Toys R Us).
Awful name? I think it's a fine name. (I suppose it helps
to be Dutch... :-) )
It's two syllables. The first one requires a sound not found in
most languages. For a reasonable approximation, try "rhine-dahl".
paul
--
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Xedia Corporation, 119 Russell Street, Littleton, MA 01460, USA
! phone: +1 978 952 6000 ext 115, fax: +1 978 952 6090
! email: [EMAIL PROTECTED]
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "Be wary of strong drink. It can make you shoot at tax collectors
! -- and miss!"
! -- Robert A. Heinlein, "The Notebooks of Lazarus Long"
! in "Time Enough for Love"
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: dumb question on releasing source code
Date: Tue, 20 Apr 1999 14:17:04 -0400
Chris Cavitt wrote:
>
> I'm a college student at a US University, and I have several small crypto
> programs(GoldWasser-Micalli, Blum-Goldwasser, etc) which use keys ranging
> from 8 to 16bits. Is it legal under US law for me to post the source code to
> these programs on my web page given the small key sizes, or is that illegal?
By the letter it would probably be illegal. It's a little hard to
imagine people coming after you for it but stranger things have
happened,
better safe than sorry.
> I thought I remembered a professor saying it was legal to post anything with
> keys <56bits,
That is quite wrong. The correct statement is that 56 bit key
cryptosystems
are easier to export to a larger set of destinations, but they are most
definitely still subject to restrictions.
paul
--
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Xedia Corporation, 119 Russell Street, Littleton, MA 01460, USA
! phone: +1 978 952 6000 ext 115, fax: +1 978 952 6090
! email: [EMAIL PROTECTED]
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "Be wary of strong drink. It can make you shoot at tax collectors
! -- and miss!"
! -- Robert A. Heinlein, "The Notebooks of Lazarus Long"
! in "Time Enough for Love"
------------------------------
From: [EMAIL PROTECTED] (Phil Howard)
Subject: encrypted and AUTHENTICATED tunnels
Date: Tue, 20 Apr 1999 22:38:10 GMT
Is there any free and unencumbered software that implements encrypted
and AUTHENTICATED tunnels? This would require an unshared authentication
key pair in each direction. Otherwise, a cracker with the tunnel code
and the opportunity to hijack the routing of one end of a VPN, could get
into a VPN easily and penetrate all those insecure applications that
assume they are running on a secured LAN.
Unfortunately, it is rather pointless for me to try to implement such a
thing myself, given the country I live in.
* strong encryption
* strong unshared authentication
* no patent encumberances
* GPL or similar licensing
--
Phil Howard KA9WGN
[EMAIL PROTECTED] [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Phil Howard)
Subject: Re: How long for export application?
Date: Tue, 20 Apr 1999 22:49:01 GMT
On Tue, 20 Apr 1999 15:01:54 -0700 Dale Mosby ([EMAIL PROTECTED]) wrote:
| Does anyone have a recent data point for the time required
| to get a classification request run though the system? (A question
| for USA readers of course.)
|
| Feb 2nd an application for "Classification Request" went to the
| Bureau of Export Administration. It has been with the NSA since
| February 26th. As of April 12 BXA can't tell me anything other
| than "it's with NSA". All I'm trying to do is get approval to change
| a 40 bit DES algorithm to 56 bit DES. This has to be the most
| straightforward request that could be submitted. Has anyone
| run something through recently? I'd love to know what sort
| of turn-around time people have experienced.
I guess is that the way the bureaucracy works there, is that no one
person has the authority to actually approve anything. But everyone
there does think that someone else might have that authority. So
any paperwork simply flows around (possibly at random) long enough
to the point that someone simply decides that if it hasn't been
tossed out by the time he's gotten it several times, then someone
must be approving it, and he stamps it and finally sends it back out
of the agency.
Either that, or they're still waiting for your 3rd grade teacher to
return the form asking about your private life.
--
Phil Howard KA9WGN
[EMAIL PROTECTED] [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Bauerda)
Subject: Re: AES R1 comments/papers available & my views
Date: 20 Apr 1999 23:01:00 GMT
>It would appear that TwoFish, Rijndael, Serpent, RC6 & possibly MARS
>are generally perceived to be good candidates.
This basicly aggrees with the ranking from the informal poll, Rijndael, RC6,
Twofish, Mars, and Serpent. The only one which I am surprised at here is
Serpent. While it does have some interesting ideas behind it, the design
seemed to conservative (not just doubling the rounds, but also the s-boxes) and
slow ( even with half the rounds, it is still slower than some of the other
algorithms).
>
>Generally, I thought it was nice that the emphasis was moved slightly
>away from performance.
It may be that because I am relativly new to cryptography (and relatively
young), I do not have as much respect for the passage of time as some people
have. I was introduced to the "good" algorithms (IDEA, Blowfish, DES) before
I saw the list of all of the ones that had been broken. Yes, the AES
candidates are new, but I look at how fast attacks were found on Deal, Magenta,
Loki, Frog, and some of the key schedules, and I don't think that lots of time
is needed. Performance is something which is here and now and which can be
tested more absolutely.
Having said that, I would like to add my vote for Rijndael. It is fast on a
variety of platforms, it is based on a cipher (Square) which has not been
broken (or even harmed, that I know of), and because the number of rounds
changes with the key size, one can get extra security while still staying
inside the defined standard.
David Bauer
------------------------------
** 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
******************************
