Cryptography-Digest Digest #906, Volume #8 Thu, 14 Jan 99 13:13:03 EST
Contents:
Re: On the Generation of Pseudo-OTP (Patrick Juola)
Re: Practical True Random Number Generator ("Tony T. Warnock")
Re: Metaphysics Of Randomness (Patrick Juola)
Re: Cayley-Purser algorithm? ([EMAIL PROTECTED])
Re: crypto machines (fungus)
Re: Practical True Random Number Generator (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: What is left to invent? (Jayant Shukla)
Re: On the utility of using Nulls (wtshaw)
hardware historic (William Butler)
Re: Wassenaar agreement (wtshaw)
Re: Metaphysics Of Randomness (R. Knauer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: On the Generation of Pseudo-OTP
Date: 14 Jan 1999 09:05:23 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On Wed, 13 Jan 1999 15:09:50 -0600, Jim Felling
><[EMAIL PROTECTED]> wrote:
>
>>> 2) what other properties besides normality would make an arbitary
>>> real useful for cryptographic purposes?
>
>>1) Easy to compute arbitrary digits
>>2) proper statistical behavior in a local (not an absolute sense) -- e.g. given
>>a number t which is normal to all bases this still does not mean that in the
>>first 2^256 digits even a single 7 (base 10) occurs - since the normality is
>>over the entire (infinite) set of digits of the number and the accessible digits
>>to us may well not be well behaved for our purposes.
>>3) Compact representation of the number.( so one can transmit the key
>>conveniently and unambiguously)
>
>>Of those #2 is the most difficult to achieve and the hardest to document
>>appropriately.( The number, since it is normal is well behaved as to randomness
>>in a global sense, but this does not mean any local set of values (however
>>large) is cryptographicly appropriate.)
>
>Can't the same things be said of a TRNG?
Well, this is part of Shannon's theory that traditionally gets
hand-waved behind a curtain when the OTP is discussed at a
novices level. For Shannon's entropy to be well-defined (and
hence for the proof of security for the OTP to go through),
the random source needs to be "ergodic", which is approximately
a statement that any sample of the random source is representative.
A good example of something that *isn't* ergodic -- for which I
am indebted to Bell, Cleary, and Witten -- is a stick of dynamite,
which undergoes a significant change in state a few seconds after
you light the fuse. No amount of sampling after that point will
let you reconstruct the original properties of the dynamite.
Language, on the other hand, is usually regarded as ergodic in a
broad sense -- the English I use today is a pretty good model for
the English I used yesterday -- although not in a narrow sense,
as the English I used at the age of 18 months or so differed
considerably.
So, yes, this is also something that needs to be said for a TRNG.
Patrick
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Practical True Random Number Generator
Date: Thu, 14 Jan 1999 08:07:44 -0700
Reply-To: [EMAIL PROTECTED]
The counts of a Geiger Counter are Poisson. Of course this means that there is a
greater probability of an even number of counts in an interval than an odd number.
Tony
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 14 Jan 1999 09:19:22 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 13 Jan 1999 15:46:01 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>R. Knauer <[EMAIL PROTECTED]> writes
>
>>>>One conclusion from these considerations is that a number that is
>>>>generated algorithmically, no matter what the algorithm might be, is
>>>>not a true random number - because such a number always has some
>>>>reason for its existence, a reason that you could possibly discover if
>>>>you worked at it long enough or hard enough. That is why only the
>>>>TRNG-based OTP cryptosystem is proveably secure - all other systems
>>>>have an underlying calculable reason behind their encryption schemes.
>
>>>>That means that almost all of classical cryptography (the OTP being
>>>>the sole exception) is not about security but is about obscurity,
>
>Douglas E.Denny. <[EMAIL PROTECTED]> writes:
>
>>>There is an inbuilt falacy in this above statement.
>>>If your proposition above about any random number generated is not a true
>>>random number, (for whatever reason) then the OTP _cannot_ be an
>>>exception as its (random) key is normally derived from an algorithm.
>
>[EMAIL PROTECTED] (Patrick Juola) wrote:
>
>>Mr. Knauer's statement is incorrect -- although not for the reason
>>given.
>
>Specifically which statement is that?
[snippety snippety snippy snip snip]
>>But, on the other hand, the reason that the OTP is provably
>>secure is *NOT* because of some mystical property involving
>>''true randomness'', but by a simple assumption of statistical
>>equiprobability and uncertainty
>
>I have been saying that all along.
>
>I have been saying that the proveable security of the OTP is not based
>on the "true randomness" of the pad per se - but the way in which the
>pad is generated, namley by a TRNG which satisfies the properties of
>equiprobability and uncertainty.
>
>>If the key is at least as uncertain as the message, then it's
>>possible to develop a provably perfect encryption method based
>>on that key.
>
>If the key is generated by a TRNG, it will possess that property.
Approximately the two paragraphs you wrote immediately above are
the incorrect ones.
The key property to focus on is not the "true" randomness, but
the degree of uncertainty. A single coin flip is, to all practical
tests, a "true" random number generator, but is unable to mask more
than a single bit of information. Similarly, if I use a set of
five coin flips to generate a "truly-random" key for a Caesar
cypher, the resulting system is still insecure as hell. The
key itself is still random, but it's carrying more than its
rated wattage, if you'll permit me an engineering metaphor.
Conversely, I can still use algorithmic methods that are not truly
random and be able to mask small messages; a good example would
be, for instance, using about 1000 characters of running (English)
text -- a classic book cypher -- using a good hashing algorithm (or
even a good compression algorithm) to distil 256 pseudorandom bits from
those thousand characters, and then using those bits as an XOR mask to
hide *no more than 256* bits* of plaintext. This can be proved secure,
subject to some handwaving about the hashing algorithm being sufficiently
(and provably) "good." Hey, such proofs exist for LZ77. Perhaps I
should consult a patent lawyer. 8-)
-kitten
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cayley-Purser algorithm?
Date: Thu, 14 Jan 1999 15:50:22 GMT
In article <[EMAIL PROTECTED]>,
William Whyte <[EMAIL PROTECTED]> wrote:
> Hi,
> > There's an article on the BBC News website talking about some new encryption
> > algorithm invented by a schoolgirl. She calls it Cayley-Purser. No algorithm
> > details were given but all sorts of claims were made about how it's going to
> > revolutionize e-mail security.
> >
> > They never bothered to mention if it's a public-key algorithm. They just said
> > it's thirty times faster than RSA (which isn't very impressive for private-key
> > algorithms).
> Yes, I do. it is a public key algorithm, and it's based on work that
> Sarah did with us in Baltimore Technologies
> The idea we were working on was to use 2x2 matrices with entries
> modulo n, n the product of 2 primes (ie an RSA number). The
> security is therefore exactly the same as the security of an RSA key with
> the same modulus.
This is "proof by assertion". The fact that the algorithm uses SL(2, Z/NZ)
where N = pq is not equivalent to proving that its security relies on
factoring N.
Let us see the algorithm and judge for ourselves. Otherwise, this is all
overblown hype.
>However, the encryption and decryption processes
> require only a small number of matrix multiplications rather than
> modular exponentiation, so both public-key operations (16 multiplications
> over the finite field) and private-key operations are as fast as a
> normal RSA private-key operation (17 multiplications). The downside
> is that both the key and the ciphertext are about eight times the
> length of the modulus,
More info please. Give the full method.
> Sarah, by the way, is level-headed enough to know that new public-key
> algorithms only made you millions if you invented them in the Seventies.
False. A secure, FAST public key method, [say O(keysize^2) rather than
O(keysize^3)] would be quite valuable.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: crypto machines
Date: Thu, 14 Jan 1999 17:10:06 +0100
ben there wrote:
>
> I need help to find old crypto machines for sale,
> or blueprints so i might try to make them myself.
> All help greatfully excepted.
I've seen a couple of them on ebay in the past.
http://www.ebay.com/
If you check there once a week or so you might find some....
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Thu, 14 Jan 1999 16:31:01 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 14 Jan 1999 08:07:44 -0700, "Tony T. Warnock"
<[EMAIL PROTECTED]> wrote:
>The counts of a Geiger Counter are Poisson.
For small count rates.
>Of course this means that there is a
>greater probability of an even number of counts in an interval than an odd number.
How does that follow? Please elaborate, with a reference if possible.
Remember that the radioactive TRNG we are discussing is designed to
measure two intervals. If one is longer than the other, a certain bit
is output. That output bit is toggled back and forth from one
measurement to the next to remove bias.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 14 Jan 1999 16:51:29 GMT
Reply-To: [EMAIL PROTECTED]
On 14 Jan 1999 09:05:23 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>A good example of something that *isn't* ergodic -- for which I
>am indebted to Bell, Cleary, and Witten -- is a stick of dynamite,
>which undergoes a significant change in state a few seconds after
>you light the fuse. No amount of sampling after that point will
>let you reconstruct the original properties of the dynamite.
>Language, on the other hand, is usually regarded as ergodic in a
>broad sense -- the English I use today is a pretty good model for
>the English I used yesterday -- although not in a narrow sense,
>as the English I used at the age of 18 months or so differed
>considerably.
Do you have some references for all of this - preferrably on the Web.
>So, yes, this is also something that needs to be said for a TRNG.
But isn't ergodicity covered by the requirement that the TRNG be
capable of outputting all possible sequences equiprobably?
When I studied ergodicity in Physics some 30 years ago, we were taught
that it means that a system can pass thru all points in phase space.
But to require that a system actually do that, even over an infinite
period of time, was considered an hypothesis for classical ensembles.
IIRC, it was required in order to justify equipartition of energy, a
necessary ingredient for the Maxwellian distribution.
For example, one microstate for a given macrostate of the air in a
room is for all the molecules to be located in one corner moving
toward that corner. But just because that is a possible microstate in
phase space does not mean that it will ever happen, even given an
infinite amount of time.
Possibilty does not require actuality, even over an infinity of time.
Some things just don't happen even though they could happen. Otherwise
we might have a much different Universe - the "best of all possible
worlds".
Similarly, even though one microstate of a TRNG is possible, say
111...1 for large N, that does not mean it must be actually be output
by the TRNG, even given an infinite amount of time.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (Jayant Shukla)
Subject: Re: What is left to invent?
Date: 14 Jan 1999 17:20:51 GMT
David A Molnar <[EMAIL PROTECTED]> writes:
>Jayant Shukla <[EMAIL PROTECTED]> wrote:
>> I personally would not consider them to be a major unconquered
>> frontier in cryptography. A public key system, that is provably
>> secure (unlike RSA or DH) would be at the top of my list.
> ^^^^^^^^^^^^^^^^^^
>are either of those proved one way or the other yet ? I thought "we"
>were getting close on DH and becoming more pessimistic on RSA.
No, either of them have not been proved to be secure or insecure.
If you break RSA by factoring p, where p is the product of two primes,
then you can break DH as well. An easy way to factor product of
primes can be expolited to solve the discrete log problem efficiently.
I would not say we are getting close on DH v/s RSA, but I would agree
that DH is much simpler and cleaner than RSA.
regards,
Jayant
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: On the utility of using Nulls
Date: Thu, 14 Jan 1999 09:14:21 -0600
In article <77kijm$mu7$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> Actual this would not add much protection if one assumes that
> the attacker has a copy of the encryption decryption program
> even if the 4 character choseen at ramdom independent of the
> key used for the encryption. its affect would be (26!)/((22!)(4!))
> number of combinations which is interms of entropy or bit
> space about 13.86 extra bits. It might be nice however if one
> could keep the method secret since its use could be harder to
> detect.
By suggesting upon casual glance that any number of other base algorithms
might be in use, a cracker would likely not look first at the one that I
have used this one with. The more choices that are available, the better
for slight increase in security for each one. As an additional layer
added, or chained, as you will, to a base algorithm, the effort in solving
the underlying cipher is directly compounded with the last one.
With a substitution key, a transposition key, and a null addition, it is
sort of a three-layer snack cake. I'll keep the null idea in mind as I
put some more things together; it is not one of those always useful
options.
--
Crypto with attitude....
------------------------------
From: [EMAIL PROTECTED] (William Butler)
Subject: hardware historic
Date: Thu, 14 Jan 1999 08:47:28 -0800
Looking for old military abd civilian encryption
machines.Please advise where I might be able to find
such things for sale.
Thank's William
*** Posted from RemarQ - http://www.remarq.com - Discussions Start Here (tm) ***
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Wassenaar agreement
Date: Thu, 14 Jan 1999 09:32:07 -0600
In article <77jie1$m9p$[EMAIL PROTECTED]>, "David Barton"
<[EMAIL PROTECTED]> wrote:
> Does any one know of any (rough) dates for the Wassenaar agreement to be
> implemented in any of the participating countries, particularly the UK?
>
How about NEVER?
--
Crypto with attitude....
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Thu, 14 Jan 1999 17:59:14 GMT
Reply-To: [EMAIL PROTECTED]
On 14 Jan 1999 09:19:22 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>>>If the key is at least as uncertain as the message, then it's
>>>possible to develop a provably perfect encryption method based
>>>on that key.
>>If the key is generated by a TRNG, it will possess that property.
>Approximately the two paragraphs you wrote immediately above are
>the incorrect ones.
But I did not write the first paragraph you refernece above. And I do
not see what is incorrect about the second one.
In the second paragraph I was not pronouncing on the security of the
systerm, just the key generated by a TRNG. I never agreed that just
because you have a secure key that you also had a secure cryptosystem.
I am not that stupid. And neither is the original poster.
The original poster did not say that you would *always* have a secure
system with a random key, only that it was possible to have one. For
example, given a key generated by a TRNG, you can have the OTP system
- which is proveably secure.
>The key property to focus on is not the "true" randomness, but
>the degree of uncertainty.
But crypto-grade randomness means just that - total uncertainty, total
unpredictability.
I don't understand what you are driving at. It seems that you are
misinterpreting what was said for pedagogical purposes. But that is
not fair, because neither the original poster nor I are that stupid.
>A single coin flip is, to all practical
>tests, a "true" random number generator, but is unable to mask more
>than a single bit of information.
That is why the specification for a TRNG focuses on the sequence, not
the individual bits. A TRNG is a physcial device capable of outputting
all possible sequences equiprobably. That says nothing about the
individual bits making up the sequence, although some things about
them can be inferred.
If you recall from the discussions a year ago, this point was debated
and that is how this consensus definition for a TRNG prevailed. We
decided that it was the generation of the sequence, not individual
bits, that was important.
>Similarly, if I use a set of
>five coin flips to generate a "truly-random" key for a Caesar
>cypher, the resulting system is still insecure as hell. The
>key itself is still random, but it's carrying more than its
>rated wattage, if you'll permit me an engineering metaphor.
I do not see how the above statements made by the original poster or
by me in any way implies that. But maybe I am missing something.
>Conversely, I can still use algorithmic methods that are not truly
>random and be able to mask small messages;
Why only small messages? What is so special about small messages? Why
can't a large message be considered the concatenation of many such
small messages?
If you say that one small message can slip under the radar but many of
them cannot, that still does not say anything about the security of
the system. I could probably slip almost any cipher under the nose of
the best team of cryptanalysta and they would not have enough to go on
to know how I constructed it. For all they know, based on "one small
cipher", I could have used the Washington to Moscow OTP system.
For example, here is a typical "small message": 10111010...
Now, from that tell me what my message is. Is it "attack at dawn" or
"attack at dusk" or "attack at noon" or "do not attack"?
>a good example would
>be, for instance, using about 1000 characters of running (English)
>text -- a classic book cypher -- using a good hashing algorithm (or
>even a good compression algorithm) to distil 256 pseudorandom bits from
>those thousand characters, and then using those bits as an XOR mask to
>hide *no more than 256* bits* of plaintext.
That method is still under debate, at least in my mind. But then you
hedged it by saying that it was only good for "one small message".
So what? I claim any cipher is good for "one small message".
>This can be proved secure,
>subject to some handwaving about the hashing algorithm being sufficiently
>(and provably) "good." Hey, such proofs exist for LZ77.
Do you have a reference for that, preferrably on the Web?
>Perhaps I should consult a patent lawyer. 8-)
Don't waste your time. Patents are notoriously easy to infringe. The
burden of proof is on you, the patent holder, to defend your patent.
That is usually more costly than it is worth if the infringement is
constructed to avoid litigation.
Unless you covered *every* possible case in your Claims, even trivial
ones, you have little defense - most especially in computer software.
The only way you can hope to keep your intellectual property intact is
to brand it and rely on that branding to protect you.
For example, if I made a trivial change to the IDEA algorithm there is
not much the patent holders of IDEA can do about it, unless I claim it
is a variant of IDEA - for marketing purposes. In that case I have
infringed in a non-trivial way. If I don't claim that it is a variant
of IDEA, it has no immediate market value.
The reason for all this apparent laxity is so people can improve on
the state of the art without being bullied by a handful of insiders
who claim that the entire field of crypto was invented by them.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
** 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
******************************
