Cryptography-Digest Digest #887, Volume #8 Mon, 11 Jan 99 23:13:06 EST
Contents:
Re: Practical OTP for secure two-person emailing (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Practical True Random Number Generator (R. Knauer)
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Practical True Random Number Generator ("Trevor Jackson, III")
Re: Practical OTP for secure two-person emailing (Scott Fluhrer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical OTP for secure two-person emailing
Date: Tue, 12 Jan 1999 02:16:12 GMT
Reply-To: [EMAIL PROTECTED]
On 12 Jan 1999 01:38:34 +0100, Anonymous <[EMAIL PROTECTED]> wrote:
>(Forgive me if someone already posted an idea like this.)
Yes, this has been suggested before.
But why stop with CDs - why not go for DVDs. 16 GB out to last a
lifetime, eh.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 02:02:56 GMT
Reply-To: [EMAIL PROTECTED]
On 11 Jan 1999 16:41:29 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>>How about specific constants like ln(c) or c^1/2, etc.? Can these be
>>show to be random like pi on a case by case basis?
>Yes. But on a case-by-case basis. It's *NOT* the case that
>all transcendental numbers are "random" in a cryptographic
>sense.
But how does one do the characterization? What are the criteria for
deciding that a given transcendental constant produces a crypto-grade
random sequence? For that matter, how do we know that pi is random?
>Because you're running on a machine with finite memory, for one
>thing....
But that does not stop one from doing expanded arithmatic. PGP does it
with its exceptionally long keys.
>It's actually fairly easy to make a PRNG-based cryptographic protocol
>provably secure, in the same sense as the proof for the one-time pad.
>Just make the seed to the PRNG as long as the message you want to
>send (and use any decent PRNG). In this case, then the PRNG *is*
>a one-time pad.
Yeah, but the seed must be random - so why not just use it instead.
>But in a real system, people aren't willing to do that. For most
>trancendental numbers and most bases, it takes time and effort to
>calculate increasingly long strings of digits. So for engineering
>reasons, it's a lot faster to calculate the first thousand digits
>than the second thousand (and so forth, progressively).
I suspect you missed out on the original intent of this thread. It was
to find ways to construct secure stream ciphers with small keys. First
the old obscure text cipher was re-proposed, but that bogged down when
no one could decide on how to remove correlation effectively. Then
digit expansion was proposed and that's when you must have joined in.
BTW, why is strong mixing (FIPS 140-1) not satisfactory to remove
correlation for purposes of crypto? Why can't one strongly mix
(nonlinearly) the LSBs from several obscurely selected antiskewed text
streams to produce a secure stream cipher? Why would such ciphers fall
victim to Bayesian Attacks?
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 00:59:56 GMT
Reply-To: [EMAIL PROTECTED]
On 11 Jan 1999 23:31:17 GMT, [EMAIL PROTECTED] (John Curtis) wrote:
>>Real random numbers are only theorical.
>Hmmm. Not sure a physicist would agree. Some types of
>radioactive decay are modelled as quantum tunnelling out
>of an energy well. This is dependent upon the Psi function
>of the particles and is not predictable in a pretty deep
>fashion.
If the decay can be modelled by a first order rate equation, then the
probability for a decay event occuring in any time interval of a given
length is independent of when that interval occurs. That is about as
random as it gets.
It is not all that difficult to characterize such a radioactive source
by measuring its decay over time, in a well equipped laboratory
anyway. A first order rate equation is a simple exponential in time,
namely exp(-kt), where k is the rate constant related to the
reciprocal of the half life.
That first order equation comes from dN/dt = -k N, where N is the
number of radioactive nuclei remaining. The fact that k is a constant
permits integration to the simple exponential above. Also, the fact
that k is a constant tells you that the probability for a decay to
occur in a given length interval is independent when that interval
occurs. That is, (k dt) is the probability for a decay in the interval
t -> t + dt, independent of t itself. That means the decay is totally
completely random.
>Chaos theory really describes macro-scale events.
Which makes such events suspect as sources of randomness. Weather
phenomena are chaotic, but not totally random - otherwise it would not
be possible to forecast the weather with computer algorithms.
>Got to be careful, though. Strange things, like microphonics
>can introduce correlations to other signals in the system.
>Much easier to demonstrate that these are eliminated in a
>discrete system, still requires careful validation.
Based on some recent discussions in another thread here, one must
design a TRNG, even one based on radioactive decay, with proper
concern for anything possible going wrong with the circuitry. The
reason is that it is impossible to characterize the randomness of the
output sequence per se, and therefore one must rely on the hardware to
function properly - or you could get a non-random output which could
screw up your OTP.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
Date: Mon, 11 Jan 1999 21:41:59 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> On Mon, 11 Jan 1999 14:10:29 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >Referring to your phrase 'Only a number produced by a TRNG can be
> >proved to be random', could you give the conrete proof algorithm??
>
> I should rephrase that statement: "At present, only a properly
> designed hardware TRNG based on a physical process known to be totally
> random can generate crypto-grade random numbers suitable for the OTP
> cryptosystem."
>
> You might try to argue that physicists do not know for certain that
> any given physical process is completely random, but then you need to
> prove that assertion because it goes against a very large body of
> evidence to the contrary.
>
> Radioactive decay for certain isotopes is known to be completely
> random based on a century of observations. If you sincerely believe
> you can prove otherwise, I would suggest ordering your tux for the
> Nobel Prize you will receive when you do it successfully.
Actually, we believe this to be true, but I can provide a thought experiment
in which it is violated. Consider a TRNG that is based on monitoring the
emission of some radioacive substance. For version 1.0 of this experiment
we'll assume the substance is fissionable and the TRNG is watching for gamma
rays.
The TRNG can be attacked. The opponent need only shine a periodic neutron
source at the mechanism to induce regular fluctuations. A sophisticated
attacker will turn off the stimulus when the engineers disassemble the
mechanism to find the error.
For version 2.0 we'll imagine a substance undergoing beta decay. This too may
be attackable. I believe there is a form of stimulated emission that could
be used to induce beta decay in the sample. "Simply" (he says) shine a
neutrino source at the mechanism in order to influence it. Vary the
intensity to induce periodicity.
Now my sub-atomic physics was never great, but it appears that there will
always be a way to mess up "perfectly random" events. Now the key question:
Do we know for a fact, or can we prove, that no *natural* phenomena can
influence our TRNG in such a manner as to induce regularities.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 01:18:17 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 23:25:07 +0000, [EMAIL PROTECTED] (Paul L.
Allen) wrote:
>No, I just know the folly of trying to explain complicated things to
>fucking idiots.
I guess than means you have just made yourself irrelevant for any
further discussions, at least with me.
Take your pompous overbearing smug attitude back the the university
where it belongs because it certainly does not belong in the real
world here.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
Date: Mon, 11 Jan 1999 21:51:08 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>,
> R. Knauer <[EMAIL PROTECTED]> wrote:
>
> >Is there a reason to believe that if I chose an arbitrary offset into
> >the digit expansion of Pi, that the sequence that is generated from
> >that offset is not one of all possible sequences of that length, and
> >that it is equiprobable with all of those other possible sequences? If
> >not, what is it about the digit expansion of Pi that causes such
> >limitations?
>
> There is, actually. There's a known closed form solution for the
> digits of pi (in base 16) that I find troublesome. But more troublesome
> than that is the fact that I rather doubt you'll use a truly
> arbitrary output.
That's interesting. I'm somewhat curious about the closed form solution, but
I'm bewildered by the base 16 clause. What has base 16 got to do with
it????????
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 02:51:03 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 21:14:18 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Another thread addressed the key generation mechanism for the Russian cipher. It
>was typists pounding on typewriter keys. This is hardly equivalent to a TRNG.
>Thus it would hardly have neen "totally secure" as you stated above.
We are sure beating this poor horse to death. The SPCA is gonna jump
us any moment now.
Back then breaking ciphers was not as easy as today, so maybe that's
why the Russians got by with poorly constructed pads until they resued
them. After all, the pads were unpredictable when not reused, so they
met the prime criterion for crypto-grade random numbers at that time.
>It probably would have need secure "enough" though without the reuse. Question
>is, was it an OTP? The key generation mechanism would disqualify it from meeting
>your definition.
Whatever. <jeez>
>Sorry, to be pedantic, but your quote was "Only a number produced by a TRNG can
>be proved to be random." I said a number cannot be proved to be random. Which
>is your opinion?
Both are correct statements, and they are not contradictory. A number
produced by a TRNG is by definition a crypto-grade random number for
purposes of the OTP system because it is one equiprobable instance of
a sequence of all possible sequences of a given finite length.
To put it in the language you develop below, knowledge of one bit
sequence is not sufficient to predict another one.
>A single number cannot be construed as random or non-random. Only the context
>allows us to decide how expected or predictable the number was when it arrived or
>was created.
Correct.
>Given a sequence of numbers, one can try to predict each from the preceeding
>sequence.
That is what the Bayesian Attack tries to accomplish.
>If the numbers are not predictable we conclude that they are
>independent.
But that conclusion is not determined formally - rather it is
determined experimentally. (see below).
>If the source of the numbers produces independent samples then we
>can presume that the numbers are unpredictable.
That is the essence of the TRNG.
>Even if some of the individual
>numbers contains patterns like all ones, or alternating digits.
Correct, although I would exclude all 1s or all 0s on the grounds that
these two sequences are pathological. Call them error codes if you
want.
>It is exactly this unpredictability that makes the OTP system secure. Note that
>reuse compromises exactly this property. When you merge (XOR) an unpredictable
>bit stream with any other bit stream, even a perfectly ordered one, the resulting
>bit stream is just as unpredictable as the original key.
Correct. Mixing total randomness with any degree of order produces
total randomness. The entropy of randomness overwhelms the entropy of
order, like a large number overwhelms a small number.
>If your keys are predictable your security suffers.
>Note the use of the term unpreditable as a substitute for "random".
That's because they are the same concept. The output of a TRNG is
unpredictable because that is how the TRNG is specified. Randomness in
crypto means unpredictability, since the latter is the prime objective
of crypto.
>> Whether that is true of other schemes, such as a highly modified text
>> cipher or the digit expansion of transcendental constants all strongly
>> mixed together, is another matter. In that latter case there might be
>> enough information leakage to give the cryptanalyst an inroad into
>> launching a successful Bayesian Attack.
>The idea that true strength is resistance to attack is well founded. But it is
>descriptive rather than prescriptive. I.e., the definition is both inverted and
>non-constructive.
You sure lost me on that one. I thougth that if an OTP cipher held up
to an experimental attack like a Bayesian Attack, then that was prima
facie evidence of its superior strength.
A point of clarification may be warranted here - one which Chaitin
makes in his papers. It is true that one cannot determine that a
number is random from formal considerations on the number itself, but
that certainly does not rule out experiments with many such numbers.
In fact since randomness and unpredictablilty are the same thing in
crypto, the ability to withstand attempts at predictability (e.g.,
breaking the cipher with a Bayesian Attack) means that one has
determined experimentally that the OTP is truly random.
Chaitin mentions Experimental Mathematics as the paradigm for proving
propositions when formal proof is not possible due to Mathematical
Indeterminancy, such as his Halting Probability and Exponential
Diophantine Equation.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 02:12:03 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 20:48:07 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>If you are wiling to work with keys that are less than perfect,
I do not recall ever saying I was, but let's assume so for the sake of
discussion. The only "imperfection" I said should not make any
practical difference was the filtering out of two particular
pathological sequences - all 1s and all 0s.
>can you
>describe the limits on the amount of imperfection that you find tolerable?
I cannot, but I am sure it can be done in terms of a Bayesian Attack.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
Date: Mon, 11 Jan 1999 22:48:40 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Practical True Random Number Generator
Jim Dunnett wrote:
> On Sun, 10 Jan 1999 15:42:13 GMT, [EMAIL PROTECTED] (R. Knauer) wrote:
>
> >Work in some New Age psychobabble to motivate these "homeless" gypsies
> >and you got a winner here.
> >
> >But I suspect that if you just tape recorded a conversation between
> >two of them, you would have all the randomness you could ever want.
>
> Politicians and pop-groups probably have just as much
> entropy.
There's a thumb rule that when the nickname for the National Socialists appears
in a thread the therad is dead. We're not there yet (and I'm superstitiously
avoiding the term), but we're on the slippery slope. Anyway, here goes:
Politicians are probably the most fruitful source of noise. It's their stock
in trade. Matter of fact, I think we're trying to remove the president 'cause
his statements contained over 200% entropy!
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Practical OTP for secure two-person emailing
Date: Tue, 12 Jan 1999 04:03:47 GMT
In article <[EMAIL PROTECTED]>,
Anonymous <[EMAIL PROTECTED]> wrote:
>Following on the thread of the "Practical TRNG," if Alice filled a 660mb
>file with a stream of true random bits, burned one CD-ROM copy for herself
>and one copy for Bob, then met Bob to give him the CD-ROM OTP, it seems
>like they could exchange years worth of personal email (textual at least)
>before needing to generate a new OTP and meet again to swap it.
That's one of the biggest problems with OTP -- Alice and Bob have to meet
(or at least have a secure channel with a huge bandwidth). Most times in
the real world, this just isn't the case.
>
>Alice starts at offset zero, Bob starts at offset halfway through the CD,
>and if Alice hits Bob's offset or Bob hits the end of the CD (or say, they
>come within 10% of their ends), then they begin to make provisions to
>create and exchange a new OTP. Each message contains an offset number to
>avoid synchronization problems.
Which makes traffic analysis even easier. Did the attacker miss a message?
He'll find out about it with the next message.
>
>Each party could send ~330mb of data before the pad would be used up.
>This is quite a decent amount of text, certainly more text than I write to
>any single person in my lifetime.
Whether that's enough depends on what they're transmitting. If they're
exchanging text messages, yes, unless one of them is sending his personal
library, it's sufficient. However, if they're exchanging programs, or gifs,
well, it can be used up a lot faster.
>
>This seems to make an OTP-based TSCS quite feasible in real life, as long
>as you make sure you never re-use any portion of the pad, and that the pad
>(and original file) are securely deleted after use. Obviously the
>strongest attack would be to recover either Alice or Bob's pad.
Another problem with CD-ROMs -- you cannot selectively destroy used parts
of them. That means, if the attacker manages to get his grubby hands on
it before the last message has been sent, he can instantly decrypt
*everything* sent by it.
>
>Protocol concerns such as Bob being assured that Alice REALLY made good
>TRNs for the OTP could be addressed by each of them burning their own OTP
>CD-ROMs and trading them, then agreeing to use XOR-ed data combining one
>byte from each CD-ROM to create one key byte.
Actually, trusting Alice and Bob is not one thing you should have to worry
about. After all, if Alice is in fact a Secret Russian Spy, she needn't
give Bob a bad CD-ROM -- she can give him a perfectly good CD-ROM, and
give the plaintext of everything Bob sends her to her Spymaster in her
monthly report. And, nothing in the protocol or the cipher can stop her.
I really don't see the real advantage of this over, say, PGP.
--
poncho
------------------------------
** 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
******************************
