Cryptography-Digest Digest #775, Volume #9 Fri, 25 Jun 99 15:13:03 EDT
Contents:
Re: one time pad (Jim Gillogly)
Re: LOKI 89,91; Safer K-64, K-128 (JPeschel)
Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day (Lincoln Yeoh)
Re: one time pad (Patrick Juola)
Re: one time pad (Patrick Juola)
Re: one time pad (Jim Gillogly)
Re: one time pad ("Harvey Rook")
Re: one time pad (Terry Ritter)
Re: one time pad (AllanW)
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: one time pad (AllanW)
Re: Kryptos article (Lincoln Yeoh)
----------------------------------------------------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 11:25:18 -0700
Mickey McInnis wrote:
>
> In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
> |> However, several one-time pad systems have in fact been broken by
> |> cryptanalysis. One that has achieved some measure of fame can be
> |> found under "VENONA" on the NSA Web site.
>
> If I recall correctly, the "VENOMA" example wasn't a one-time-pad that
> was broken. It was a two-time-pad (or a multiple-time-pad). Due to
> errors, the same pad was reused. The sender meant to use a
> one-time-pad, but they didn't.
VENONA was indeed intended to be a one-time pad system. That's the
nature of actual implementations: they typically do not match the
theoretical specifications. Much VENONA traffic did use one-time
pads, so far as we can tell, and will consequently never be broken.
R. H. Morris gave more examples of failures of fielded systems
intended as one-time pad systems at a recent Crypto meeting.
Virtually everybody, presumably including Doug, agrees that OTPs
if used correctly would be theoretically unbreakable. However,
actual fielded systems are typically another story.
--
Jim Gillogly
2 Afterlithe S.R. 1999, 18:17
12.19.6.5.10, 1 Oc 18 Zotz, Second Lord of Night
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: LOKI 89,91; Safer K-64, K-128
Date: 25 Jun 1999 18:17:09 GMT
> [EMAIL PROTECTED] writes:
>To the "Algorithms and Attacks" page of my web site I have recently
>added the above ciphers and attacks.
And TEA, too
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
Date: Fri, 25 Jun 1999 18:35:41 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 25 Jun 1999 00:43:53 GMT, [EMAIL PROTECTED]
(John Savard) wrote:
>then, not only _should_ we omit using true random generator output
>that is all zeroes, or that corresponds to some simple, regular
>sequence that the cryptanalyst would, as it were, accidentally solve,
Given a totally random generator running for an eternity, eventually you
may get Shakespeare. But it's still random.
But if you're still concerned just compress the plaintext. So even if the
OTP has a long string of zeroes somewhere they aren't going to extract it
as easily.
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: one time pad
Date: 25 Jun 1999 14:39:32 -0400
In article <7l0all$8jm$[EMAIL PROTECTED]>,
Greg Ofiesh <[EMAIL PROTECTED]> wrote:
>
>> The probability of a long stream of zero's is
>> so vanishingly small, that
>> worrying about it is counter productive.
>
>If it is vanishingly small, then at some point you do not expect to see
>it in nature. For example, what are the odds that all photons in the
>universe come together and cancel each other out in a moment of time?
>So slim that you do not expect to ever see it happen.
>
>Therefore I ask, what do you do if your RNG produces an event that is
>too unlikely to occur in nature?
If you generate 100 bytes with your RNG, the resulting output is
``too unlikely to occur in nature.'' Therefore you have no output
at all.
>Why not filter the output with: "I want only those events that
>meet a threshold of probability.
Because in a properly functioning generator, *all* outputs meet, or
fail to meet, exactly the same threshhold of probability.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: one time pad
Date: 25 Jun 1999 14:37:06 -0400
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
>>John Savard wrote:
>
>>> But in real life, our RBG might generate all zeroes because of a
>>> short circuit, ...
>
>>Yes, that was the idea of the FIPS-140 tests, which weren't allowed to
>>monitor the "internals" of the key generator but only the key stream.
>
>>However, you're switching context. The fellow was claiming that
>>patterns should be eliminated from the output of a *correctly
>>functioning* random bit generator to improve security, and *that*
>>idea is completely wrong.
>
>I'll agree it's:
>
>- theoretically unsound, and
>
>- completely wrong to remove _short_ patterns
>
>but while I am not ready to advocate the practice, I think an issue is
>being raised that can't be completely dismissed.
Well, what sort of evidence would you regard as being sufficient
to justify a dismissal?
I'm glad we agree that it's theoretically unsound -- on what basis
to you propose to distinguish "long" sequences where such removal
is justified from "short" ones where it isnt?
-kitten
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 11:16:25 -0700
Greg Ofiesh wrote:
> Therefore I ask, what do you do if your RNG produces an event that is
> too unlikely to occur in nature? Assume the RNG is broken and replace
> it? Why not filter the output with: "I want only those events that
> meet a threshold of probability. Anything lower than this given
> threshold is demonstrative of an inperfect RNG because the event shows
> a bias toward a probability that is too slim to occur in nature."
>
> What say you?
I say the same thing we've been saying all along. If you filter
the output, you lose the absolute provable security of the OTP.
Several people have given you examples of how information
loss occurs. Again: suppose you've decided you will drop
all runs of 8 or more 0-bits. The cryptanalyst expects you to
send one of two messages (example mapped to A-Z for convenience
of exposition):
ATTACKATTHREEOCLOCK or
WITHDRAWIMMEDIATELY She intercepts your encrypted message:
DNQBGEGZUPAYWOVCMTP She concludes you sent the second message.
How did she do this?
The true one-time pad does not leak this information.
In a practical situation this requirement is in tension with the
requirement that you verify your RNG is working. Typically
you would want to monitor your RNG output to see whether the patterns
it's producing exceed your credibility threshold. If they do, you
would presumably want to take the RNG off-line and fix it before
putting it back into service and creating more pad with it.
If you find the RNG was working correctly after all, though, you
must then shove that a priori incredible stretch of bits back
into the pad, or you would have committed the same fault as if
you'd been filtering: the cryptanalyst can assume these strings
will never occur, and design her attacks accordingly.
All things considered, I'd rather be in 3DES.
--
Jim Gillogly
2 Afterlithe S.R. 1999, 17:34
12.19.6.5.10, 1 Oc 18 Zotz, Second Lord of Night
------------------------------
From: "Harvey Rook" <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 11:31:50 -0700
Greg Ofiesh <[EMAIL PROTECTED]> wrote in message
news:7l0all$8jm$[EMAIL PROTECTED]...
>
> > The probability of a long stream of zero's is
> > so vanishingly small, that
> > worrying about it is counter productive.
>
> If it is vanishingly small, then at some point you do not expect to see
> it in nature. For example, what are the odds that all photons in the
> universe come together and cancel each other out in a moment of time?
> So slim that you do not expect to ever see it happen.
>
> Therefore I ask, what do you do if your RNG produces an event that is
> too unlikely to occur in nature? Assume the RNG is broken and replace
> it? Why not filter the output with: "I want only those events that
> meet a threshold of probability. Anything lower than this given
> threshold is demonstrative of an inperfect RNG because the event shows
> a bias toward a probability that is too slim to occur in nature."
>
> What say you?
When you generate a stream of random numbers (I'll assume a binary
stream for simplicity) then all streams have equal probability.
For example, the stream 0000 will occur with probability 1/16, as
will the stream 0110, or 1110. Even though the second streams look
more random, they will occur with the same frequency as the all
0's stream.
If your RNG shows a bias toward a probability that is to slim to occur in
nature, then get rid of it. Don't filter it. Applying a process to a biased
stream
of numbers, risks making the stream more biased, even if you can't see the
bias,
all it takes is for someone better at math, to look your process, and
discover it's
weaknesses.
Harv.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 18:37:17 GMT
On Fri, 25 Jun 1999 15:46:20 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (John Savard) wrote:
>[EMAIL PROTECTED] (Terry Ritter) wrote, in part:
>
>>The issue here is whether even minor forms of predictability are
>>mathematically prohibited, or even wildly impossible given what we
>>know about the real system. I think not: these are reasonable
>>concerns. There is no process in place, no tool we have, no test we
>>can make which can eliminate the possibility of weakness in a pad.
>>And the possibility of weakness destroys any claim to absolute
>>strength.
>
>I see that I have misunderstood your argument. I thought you were
>claiming that a physical random-number generator might accidentally
>produce a keystream matching one that could be generated by a
>cryptanalyzable PRNG, and I pointed out that that risk doesn't
>actually reduce ambiguity.
>
>Instead, you are suggesting that a physical RNG - say, for example, a
>rotating cage with numbered balls in it - might still be predictable
>by means of some advanced mathematics.
Not necessarily "advanced," perhaps just arduous. Perhaps it just
takes the audacious thought that any such analysis would be
worthwhile. If we do not look for weakness, we surely will not find
it.
>Well, it is true that the OTP model makes simplifying assumptions
>about the real world. The "proof" that the OTP is secure depends on
>the truth of those assumptions. The specific example of a "true" RNG I
>gave _might_ be subject to such an attack, but I think no one would
>really be worried about that particular risk. Independent dice throws,
>though, or the output of an RNG making use of a quantum-mechanical
>process, can be considered quite safe.
*Anything* can be *considered* safe. The issue is whether or not
something actually *is* safe. If we have no proof of "safety," we are
inherently accepting the *possibility* of danger. And without data,
we have no grounds on which to assess the *probability* of that
danger. Statements like "<x> can be considered quite safe" are just
wishes and hopes more modestly dressed for public display. But when
wishes and hopes are enough, we don't need cryptography at all. I
claim we would do well to check even "obviously random" physical
generators to see if anything funny is going on. And even that does
not give us peace of mind.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 17:56:34 GMT
In article <7kttrb$dp7$[EMAIL PROTECTED]>,
Greg Ofiesh <[EMAIL PROTECTED]> wrote:
> > I disagree. If, for example, 0x00 appears 20 times
> > in a row, then the plaintext for those 20 characters
> > will show up in the ciphertext. The problem is that
> > the attacker has NO way of guessing that this is
> > really the correct plaintext. Without knowing
> > up-front that there's a 20-byte run of zeros in
> > the key, he has no more reason to guess the
> > plaintext is showing through unchanged than any other
> > run of 20 characters.
>
> Given the message and the cipher stream, one can derive the
> pad segment between them. Examining the pad segment, one
> would immediately realize that the odds of 20 0's are
> astronomical. The plain text as well is an equally
> astronomical candidate (all candidates have same
> astronomical odds of being correct). But when you have
> one astronomical event coincide with another, that cannot
> be coincidence. Thus patterns to the naked eye must be
> avoided in the pad.
>
> What say you?
Okay, I think I have an answer that will satisfy everyone.
Mr. Ofiesh, you concede that the odds against generating a pad
of 20 0-bytes is "astronomical," but then you worry that if
this ever did happen, 20 bytes of plaintext would be visible,
right?
First, try to see the problem from the attacker's point of
view. Take a very large plaintext document and "encrypt" it
by XOR-ing it with random bytes. Now load the result into
a text editor and look for patterns. You *will* see some
apparently meaningful data in there. For instance, the
odds are approximately 2^24 times the length of your document
that you will see the letters "CIA" in order somewhere in
the output; your mileage may vary, but there's almost
certainly going to be a few apparently-meaningful strings in
large random output. For our CIA example, there are two
possible ways to explain why the letters appear in the
encrypted text:
* First, the plaintext might have actually referred to
the CIA, and the pad might have happened to hit on
the astronomical odds, by generating three 0-bytes
at exactly the wrong moment.
The odds against this are astronomical.
* Second, the plaintext might not have any reference
to the CIA, or at least no reference at that particular
postion. But the pad happened to come up with exactly
the right values to make the encrypted output use the
phrase anyway.
The odds against this are also astronomical. However,
one or the other of these must be true, because the
output clearly does have these three letters.
Be the attacker for a moment, with no knowledge of the
original plaintext document. Which of these possibilities
is correct? You have no way of knowing. You could base
your answer on probabilities; there are about 96^3 more
ways for the second option to be true than for the first
one, given the assumption that the original plaintext was
100% printable ASCII. Or you could assume that the pad had
a pattern for exactly three bytes. (But which pattern? If
the pad was 0x0A, 0x0B, 0x0D then the plaintext was "IBM".)
...Having said all of this, I happen to know that you are
still not convinced. (What I just said was a variation on
what many people have already said, and most of them are
much smarter than I am. If they didn't convince you, then
neither did I.) So, we need a way to counter your fears
about patterns giving away the plaintext, without
compromising the OTP algorithm by eliminating some
possible random patterns.
The solution is simply to use TWO pads instead of one. If
the message is N bytes long, generate two N-byte pads.
Classic OTP works by either adding the pad to the plaintext
modulo 256, or else by XORing the pad to the plaintext.
Since our modified OTP has two pads, we have a third choice:
do both of these things. So we XOR with pad1, and then we
add pad2.
Purists will note that the end result is exactly as secure
as before, no more and no less, except for the logistical
problem (we must now transfer twice as much information
securely, two pads instead of one).
Mr. Ofiesh, on the other hand, need no longer fear the
results of patterns in the pad. Because now, for plaintext
to show through in the encrypted text, we have to have TWO
astronomically-impossible events happening at once; for
instance, both pads generate 20 0-bytes in exactly the
same position. As you stated before,
> ... when you have
> one astronomical event coincide with another, that cannot
> be coincidence.
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES-NULL attack
Date: Fri, 25 Jun 1999 18:47:00 GMT
Hello Tom,
Oh! You are on duty today.
You should get a more salary.
The case is out of your confidence
Tchao.
Alex
In article <7l03cg$59u$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <7l029h$4q6$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Suppose we use DES encryption algorithm.
> >
> > Let a plain text block contains only bits with NULL value.
> >
> > Then correspondent cipher block is well-defined function
> > of the encryption key, which can be recovered.
>
> That is not true. It's a function of the plaintext register, key and
> sboxes. You forget that the key and sboxes will not always produce
> degenerative output and their is a feedback (the other unmodified half
> in each round).
>
> For NULL it's just as hard as for '12345678'. By your argument though
> the all one plaintext would reveal the complement of the key.
>
> That's not true. If it were this would apply to many other ciphers
> (Blowfish, CAST, Kafre, etc...)
>
> Tom
> --
> PGP key is at:
> 'http://mypage.goplay.com/tomstdenis/key.pgp'.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
>
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 18:37:17 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote:
> Were it possible to tell whether sequence s + '0' was more
> random than s + '1', we could produce the one sequence which
> was most random. But everybody would know that sequence so
> it would be useless for cryptography.
Heh heh, I like that. It's kind of like, "Give me a list of
all well-known patterns, and then find the one that is least
well-known!" The answer depends on the quality of the first
list.
> The whole point of crypto random is the hope that it is
> not possible to know what the sequence will be.
Right.
Common RNG tests wouldn't be of any use, if they didn't
check for known problems that make the next character in
a sequence too easy to guess.
For instance, we use frequency graphs to prove that each
possible output byte is generated approximately the
correct number of times. If we found that the byte value
'0' was output only half as often as the odds predict it
should be, we would call that a weakness because an
attacker would rarely guess 0.
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: Kryptos article
Date: Fri, 25 Jun 1999 18:20:10 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 24 Jun 1999 22:38:15 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>Jim Gillogly wrote:
>> In addition, I've just been told that some of the letters on the
>> sculpture are in italics.
>
>Hm, you'd think I would have noticed something like that.
>
>Now that we know where the real "message breaks" are,
>I wonder if there is any indication of them on the sculpture,
>such as a slightly wider inter-letter spacing or whatever.
http://www.odci.gov/cia/information/tour/krypt.html
Is that a hole on the lower right? And is that where we're supposed to dig
or look inside?
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
** 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
******************************
