Cryptography-Digest Digest #787, Volume #9 Sun, 27 Jun 99 15:13:02 EDT
Contents:
The One-Time Pad Paradox
Re: Tough crypt question: how to break AT&T's monopoly??? ([EMAIL PROTECTED])
Re: one time pad ([EMAIL PROTECTED])
Re: Kryptos article ("Douglas A. Gwyn")
Re: one time pad ([EMAIL PROTECTED])
Re: Converting arbitrary bit sequences into plain English texts (wtshaw)
Re: one time pad ([EMAIL PROTECTED])
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: Kryptos article (wtshaw)
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: A few questions on RSA (Gilad Maayan)
Re: The One-Time Pad Paradox (S.T.L.)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Subject: The One-Time Pad Paradox
Date: 27 Jun 99 15:39:19 GMT
The One-Time Pad is the one theoretically perfect cipher. Provided it is
applied in strict accordance with the theoretical conditions.
One must use a key that is truly and genuinely random.
Now, there is a small, but finite, probability that the random key will
happen to be 000000...
If one uses such a key, one is sending one's message in plaintext.
If one refuses to use such a key, one is causing one's key to be
nonrandom, hence one is spoiling the perfection of the one-time-pad.
This qualifies as a genuine paradox, and as such may well be fruitful,
just as paradoxes in mathematics and physics have occasionally led to new
paradigms.
One way to resolve the "next step" after this paradox: let us suppose
one's key *does* look random, but applying the key to the message creates
what _appears_ to be the plaintext of a message saying (in different
words) essentially the same thing as the message you want to keep
secret...
is the following: before applying the OTP, encrypt one's message with a
probabilistic encryption method. If this happens, repeat the probabilistic
encryption, and use the same OTP again, _then_ send the result.
Since the pad is random, the only "information" is that the _ciphertext_
is random-looking, and one already has the full ciphertext.
However, that *does* introduce a subliminal channel...
(I call this Comfort-Zone Encryption.)
The desired situation to avoid this paradox is this: you have N plaintext
messages, you have N keys, and you have N ciphertext messages. But no one
of the N keys is "zero", and *none* of the N ciphertext messages could be
mistaken (by someone who doesn't realize a one-time-pad is being used) for
any plaintext - or could be thought to be more closely associated with one
plaintext message than another.
Stating the condition helps to see what is necessary. A step (but an
incomplete one) would be to take an alphabetic text, and by means of a
random key encipher it to a ciphertext consisting of 26 funny-looking
symbols instead of the 26 letters, which occasionally can have meaning
associated with them.
Surely there is, in mathematics, some class of equi-spaced binary strings
applicable to this kind of thing...
John Savard
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Tough crypt question: how to break AT&T's monopoly???
Date: Sun, 27 Jun 1999 16:05:56 GMT
<snip>
With the PKZIP skeme you don't need much chosen /known plaintext
though. The only things it may be good for is highly compressed files
such as MP3 or JPG. In which case why are you zipping them?
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Sun, 27 Jun 1999 01:27:51 -0400
From: [EMAIL PROTECTED]
Subject: Re: one time pad
AllanW wrote:
>
> [EMAIL PROTECTED] (S.T.L.) wrote:
> > This thread is disgusting. Most involving OTPs get ugly, but
> > *so* many kooks posting here have the wrong ideas.
>
> Gosh, S.T.L., it's a good thing you're here to help us
> distinguish the kooks from, say, the insufferable
> egotistical asshole bastards.
>
> > I'll just state it plainly:
> >
> > If you have a perfect random number generator
>
> Is there such a thing? If so, how do you know?
>
> > that is operating correctly, then ALL you need to do is
> > take its output, send it to the recipient securely, and
>
> How?
>
> Doesn't the existance of a secure channel imply that no
> encryption is needed?
No. This issue may belong in the FAQ. The secure channel may have
timing characteristics that make it unacceptable for real-time
communication, but acceptable for keypad communication. Condsider a
ship. At dock you can very easily transfer arbitrary amounts of pad
quite cheaply, and with almost total security. At sea, however, you
have no secure channel. I.e., it is intermittent, but the channel
capacity is unreasonably high.
If your ship is an SSBN and you want to send "DEFCON I", the OTP might
be useful.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Kryptos article
Date: Sat, 26 Jun 1999 03:49:50 GMT
Jim Gillogly wrote:
> Reflecting on this, I realized it's utter garbage. The pool would
> swap up and down, not right and left. Never mind.
Um, Jim, mirrors don't reverse in any particular direction.
Martin Gardner had a discussion of this in one of his books:
Why is your image in a flat mirror reversed left-to-right,
not top-to-bottom? (Think about it; it can produce one of
those moments of "enlightenment".)
------------------------------
Date: Sun, 27 Jun 1999 01:28:50 -0400
From: [EMAIL PROTECTED]
Subject: Re: one time pad
John Myre wrote:
>
> AllanW wrote:
> >
> > [EMAIL PROTECTED] (S.T.L.) wrote:
> <snip>
> > > Now, IF you suspect that your true-RNG is going flaky on
> > > you (operating incorrectly), take it out of service, have
> > > it output a quadrillion bits
> >
> > Different countries have different names for names of numbers
> > larger than 1 million. For instance, in England the words
> > Billion, Trillion and Quadrillion represent much larger values
> > than they do in the United States.
> <snip>
>
> I think he made a mistake, and meant "bazillion".
Well, let's be precise. I believe the proper term is "billions and
billions".
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Sun, 27 Jun 1999 11:52:23 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> This reminds me of some work I did on readability analysis. Most
> ratings use grade levels. Here we're talking negative numbers.
> Negative readability is an interesting idea.
As I remember, generally, readability had to do with using personal
words. For those who want to make something appear more natural instead,
don't leave them out, and salt in some proper nouns as well.
Surely a person in a particular field would be quick to pick up on misuse
of jargon, but any else might easily fall prey to the expert syndrome.
You could do invent your own brand of reality reassigning well understood
words to obscure meanings, claiming only those that are clear enough in
the subject could actually understand it, and deny any others could
criticize content on what it should or should not be.
--
It's always possible that a politician is acting out of principles.
--Michael Kinsley of Slate.com
------------------------------
Date: Sun, 27 Jun 1999 01:54:55 -0400
From: [EMAIL PROTECTED]
Subject: Re: one time pad
William Tanksley wrote:
> There is NO single stream of data coming out of an alleged RNG which would
> prove to me that it wasn't an RNG.
Well I have this special RNG that meets these criteria. It's quite
cheap. It is also sold under the name "zero ohm resistor", but for
today only, I'll make a special offer of $10.00 each.
------------------------------
Date: Sun, 27 Jun 1999 02:00:40 -0400
From: [EMAIL PROTECTED]
Subject: Re: DES-NULL attack
> 64-bits is generally secure. Just because the number of bits is close
> to that of DES does not mean the key space is the same.
Yes it does. The size of the key space is _defined_ to be 2^keybits,
sometimes modified by subtracting a few known-weak keys.
If you have the same number of key bits you have the same keyspace. If
you have "close to" the number of key bits you have "close to" the same
keyspace. "Close to" in an exponential space.
------------------------------
Date: Sun, 27 Jun 1999 02:08:23 -0400
From: [EMAIL PROTECTED]
Subject: Re: DES-NULL attack
fungus wrote:
>
> [EMAIL PROTECTED] wrote:
> >
> > In article <7l204q$mci$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (Thomas Pornin) wrote:
> > > As usual: if some agency has so much power and is after me, the
> > > possibility that they could recover a DES key in a few days with a
> > > hardware worth dozens millions of dollars is the least of my concerns.
> > > They could kidnap me for much less.
> > >
> > > Anyway, the limit if generally considered to be about 80 bits.
> >
> > By whom? If a 64-bit key is not safe an 80-bit key is probably not
> > safe. If we are to follow the skeptism.
> >
>
> Skipjack was 80 bits. The NSA are the experts in what can and what
> can't be cracked by people in the near future.
>
> ;-)
Are they? They are supposed to be. That's what they're paid for.
That's what we all assume. But, how do you _know_. How can you test
the capabilities of the organization? Even if you were a senator on the
oversight committee, with theoretical access to everything they are
supposed to be doing, how do you measure this expertise?
I don't think it can be done.
>
> > 64-bits is generally secure. Just because the number of bits is close
> > to that of DES does not mean the key space is the same.
> >
>
> Nope. It's 256 times bigger. Even the famous EFF machine would take
> a couple of years to find a 64 bit key.
>
> --
> <\___/>
> / O O \
> \_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Kryptos article
Date: Sun, 27 Jun 1999 11:55:31 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> Maybe it because your right hand looks like your left hand and your head
> doesn't look like your feet?
>
> They just mirror stuff, that's all, just like shadows in some ways.
>
According to Alice, mirrors can be best used by walking through them, but
everytime I try, the guy on the other side seems not to like the idea
'cause he hits back.
--
It's always possible that a politician is acting out of principles.
--Michael Kinsley of Slate.com
------------------------------
Date: Sun, 27 Jun 1999 02:01:34 -0400
From: [EMAIL PROTECTED]
Subject: Re: DES-NULL attack
fungus wrote:
>
> Thomas Pornin wrote:
> >
> > (*) Many people, included some considered as smart and competent in the
> > domain of micro-electronics, predict that Moore's law will cease to be
> > valid in at most 5 years. However, such predictions have been done for
> > the last 10 years at least
>
> Yeah, but the "past predictions" were based on technical difficulties,
> the new predicions are based on physical laws.
>
> > therefore it is safer to assume that this exponential augmentation
> > of computing power might just go on for the next 30 years.
>
> More like 15-20...
>
> ...even so, that means a Pentium XIV with a clock speed in the
> hundreds of gigahertz range. I can't wait for the games!
How will you tell the games from real life?
------------------------------
From: [EMAIL PROTECTED] (Gilad Maayan)
Subject: Re: A few questions on RSA
Date: Sun, 27 Jun 1999 17:02:57 GMT
Thanks a lot for your reply - you really did help me out. But of
course, I still have a few (actually, more than a few) comments and
questions.
>I'm going to assume that RTS is another name for RSA based on
>earlier posts.
My apologies to everyone who read this thread - I wrote that message
in a hurry, at around 6am, and after getting very little sleep, and
for some stupid reason substituted RSA for RTS without noticing. The
reference, is, of course, to RSA.
>he has
>
>M = plaintext Message
>length of M
>C = M^e mod n (e, n unknown)
>
>and needs d.
Actually, no. He needs e. Does this change anything?
>I think that obtaining d is still difficult even with knowledge
>of e and n. This seems to imply that you are correct and d is
>hard to obtain in this case.
Aha, but is it hard to obtain, or impossible to obtain? My thinking is
that without at least one of the factors, or the modulus there is no
possible way to extrapolate e. Think about it - what could you
possibly use for an attack?
> I don't see any way to obtain e given a _single_ C .
> On the other hand, given many C perhaps a way is possible.
> (I need to think about it).
It should be mentioned that in my particular system, you only get one
C to work with.
> It will probably depend on
> whether you use padding or not.
Are we talking about adding a bunch of zeroes or random characters to
the end of the 20 bits? If so, I'm not using padding. The 20 bit
plaintext will be encrypted as-is. How does this effect security?
>>...you could test the entire keyspace to find a key that works,
>> but you would have no way in hell of knowing
>> which key was actually used.
>I like this way of thinking about it, since it recognizes
>each e as defining a different random permutation.
>I don't see any easy way to get e off the top of my head.
Exactly. The thing is, if you have a 20 bit plaintext and a
corresponding 20 bit cyphertext, you would have 2^80 keys that 'fit'.
All of them would turn our plaintext into the known cyphertext, and so
there is no possible way to distinguish which one is 'right' - which
one was used in the original encoding.
But another question arises here - from someone else's post I learned
that a 20 bit plaintext would yield a 1024-bit cyphertext when
encrypted with a 1024-bit key. Is this true? If not, is there any way
to make RSA 'symmetrical' - in other words, to use a 1024-bit key on a
20 bit plaintext, and get 20 bits back?
>From the secret key, you can compute the public key in poly time
>by finding its inverse mod n . Sorry.
>This would work, except that e and d are defined to be
>inverses of each other. Inverses are reasonable to compute. :-\
Wait, so why is it that you can't compute the secret key from the
public key? If they're inverses of each other, it stands to reason
that it would work the other way around. And, of course, it doesn't,
since public keys are freely published.
>You're thinking that because the output -- the DES keys -- isn't
>accessible to a cryptanalyst it will be harder to figure out
>what the functions are ?
>I'm trying to construct a pathological example in which the functions
>are linear congruential generators. Given direct access to the
>output of such generators, one can derive values for a
>generator which "coincides" with the generator in question --
>in the sense that they produce the same outputs. So if we
>had direct access to your DES keys, we could pretty easily
>get the LCGs , even if you weren't giving away the seed.
I'll give you an even easier pathological scenario. The function is
just your ordinary, 10-step affair that scrambles the order of binary
digits and such. Naturally, if you had a couple hundred, or even a
couple dozen "outputs" of this limited function - similar
DES-encrypted messages which it generated - and applied some smart
cryptographic techniques, you would be able to extrapolate the next
output. I concede this. But what I'm saying is that assuming you only
have one or two outputs to work with, you wouldn't be able to figure
out the function by determining a logical series. You would have to
break Triple-DES to find out what the key is, and find the function in
reverse. This is, essentially, my contention - I'd like to know if I'm
right.
And one more thing - excuse my ignorance, but as you might have
guessed I'm new to this field - what exactly is an LCG?
>Anyway, this pathological example makes me think that
>it may be possible to show that *any* attack on
>this system automatically implies an ability to
>predict the functions. So if the functions are
>perfectly pseudo-random, then the scheme is
>secure.
Are you telling me that any successful attack renders the functions
obsolete? If so, I completely agree. The question is, would it be at
all practical to break it even once?
>I'm not quite sure about your keyseed in such a
>setting, though. Maybe we could treat the
>functions as random oracles and let the keyseed
>be the index i?
sure, you could. But I intend to encrypt the keyseed using RSA - it'll
work better like this for several reasons rooted in my specific
aplication.
> why not just use the functions _directly_ to encrypt, instead of
>going through 3DES ?
Well, as I said, I'm not claiming they are completely random. If they
were, I would probably be able to use them instead of DES, and also
put DES out of business. However, I doubt any function I come up with
will be that effective. My working assumption is that even with a
relatively small number of outputs, it will be possible to extrapolate
a series, and so I'm betting on the analyser having only one output to
work with.
I hope you'll forgive me for going to so much detail.
By the way, in case anyone is interested, this is more than a purely
academic inquiry. I'm designing a commercial encryption-related
product, and am trying to devise a secure system that would fit the
product and accommodate it's limitations.
Many thanks,
Gilad Maayan
------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: The One-Time Pad Paradox
Date: 27 Jun 1999 19:13:18 GMT
I don't consider this a paradox.
<<The One-Time Pad is the one theoretically perfect cipher. Provided it is
applied in strict accordance with the theoretical conditions.>>
Right on.
<<One must use a key that is truly and genuinely random.>>
Absolutely.
<<Now, there is a small, but finite, probability that the random key will
happen to be 000000...>>
Right you are.
<<If one uses such a key, one is sending one's message in plaintext.>>
Yep. The Adversary doesn't know that it is the correct plaintext, however, and
because he knows neither the key nor the correct plaintext he cannot decide
whether the encrypted message he sees is identical to the correct plaintext or
says something completely different.
<<If one refuses to use such a key, one is causing one's key to be
nonrandom, hence one is spoiling the perfection of the one-time-pad.>>
Absolutely!
<<This qualifies as a genuine paradox, and as such may well be fruitful,
just as paradoxes in mathematics and physics have occasionally led to new
paradigms.>>
I don't consider it a paradox. Interesting, but not really.
<<One way to resolve the "next step" after this paradox: let us suppose
one's key *does* look random, but applying the key to the message creates
what _appears_ to be the plaintext of a message saying (in different
words) essentially the same thing as the message you want to keep
secret...>>
Could be. The rest of your message I'm not quoting because A) I don't
understand it, and B) It can't help.
You seem to be forgetting (so it seems to be) another possibility: One's key
could look random, but applying the key to the message creates what _appears_
to be the plaintext of a message saying a completely different thing as the
message you want to keep secret. The probability of getting any one specific
message of this type is, of course, exactly the same as the "null key case".
When the adversary sees your ciphertext, he CANNOT decide whether this last
possibility, your "similar message possibility", or the "null key" possibility
has occurred. (The number of "completely different plaintexts" is much greater
than the single "null key" and probably larger than the number of "similar
plaintexts"). If the Adversary tries to guess that you are sending plaintext in
the clear, it still doesn't help him because for all he knows, he is being
fooled by a similar plaintext.
Moral of this story: You were absolutely correct that munging a one-time-pad
spoils its perfection. "Null keys" or "similar plaintext producing keys" don't
change that, and in my eyes aren't a paradox because of the existence of
"completely different plaintexts".
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Great SRian
Conspiracy, the Triple-Sigma Club, and the Union of Quantum Mechanics
Avid watcher of "World's Most Terrifying Causality Violations", "World's
Scariest Warp Accidents", and "When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #3: Thou Shalt Conserve Baryon Number.
------------------------------
** 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
******************************
