Cryptography-Digest Digest #964, Volume #8 Tue, 26 Jan 99 00:13:03 EST
Contents:
Re: All 8 modes, was Re: 3DES in EDE mode versus EEE mode
([EMAIL PROTECTED])
Re: Who will win in AES contest ?? (Bruce Schneier)
Re: Who will win in AES contest ?? (DJohn37050)
Re: Metaphysics Of Randomness ("Trevor Jackson, III")
Re: Who will win in AES contest ?? (Bruce Schneier)
Re: [req]:Cryptanalysis tool - word pattern table (Patrick Juola)
Re: Random numbers from a sound card? ("Trevor Jackson, III")
Re: Metaphysics Of Randomness ("Trevor Jackson, III")
Re: Non exe/com crypto prog (Michael Paul Johnson)
Re: Sanity check on authentication protocol (Edward Keyes)
Re: The Performance of Meet-in-the-Middle (David Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: All 8 modes, was Re: 3DES in EDE mode versus EEE mode
Date: Tue, 26 Jan 1999 01:07:37 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> >
>
> > Ok, will. See also my posting here on Jan 5/99, RE "On leaving the 56-bit
key
> > length limitation" -- which also discusses some options in this line of
> > reasoning, to increase the attacker's undecidability mulitiplied by the
> > key-space while the intended recipient has 2^56 less options ;-)
>
> See an earlier thread in this group initiated by me: 'On Living with
> the 56-bit Key Length Restriction'. A revised version of the original
> post is available at
>
> http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper17
>
;-) I read that --- hence the play on words in my title "On leaving the..."
indicating a different slant. But, your paper is useful IMO also in the
aspect that it calls attention to the fact we need to cope with the issues --
not just lament ;-)
Cheers,
Ed Gerck>
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Who will win in AES contest ??
Date: Mon, 25 Jan 1999 23:30:23 GMT
On Fri, 22 Jan 1999 10:32:03 -0000, "Sam Simpson"
<[EMAIL PROTECTED]> wrote:
>
>Robert Harley wrote in message ...
>>
>>[EMAIL PROTECTED] (Piotr Kulinski) writes:
>>> What do you think who will win in AES contest ???
>>> My type is Twofish....
>>
>>Why do you think it would be Twofish? Because Bruce Schneier wrote a
>>very popular book? Twofish is quite a complex, non-obvious cypher.
>
>I thought TwoFish looked quite good from a conceptual point of view.
>
>I was surprised how much emphasis Bruce et al put on speed in respect of
>TwoFish. If you look at his comments before AES:
>
>"This is serious business. Any algorithm proposed in 1997 won't be approved
>until at least 2000. It will be a standard for 20-30 years, in legacy
>systems for at least another ten, securing data that might need to be
>secured for another 20. This means we are trying to estimate security in
>the year 2060. I can�t estimate security ten years from now, let alone 60.
>The only wise option is to be very conservative."
>
>(1997/04/15 posting to sci.crypt)
>
>One would expect an ultra-conservative cipher, right?
I thought Twofish was ultra conservative.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Who will win in AES contest ??
Date: 26 Jan 1999 01:46:02 GMT
I have submitted a paper for consideration at the 2nd AES conference.
Don Johnson
------------------------------
Date: Mon, 25 Jan 1999 22:23:18 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>,
> >> What is the actual likelihood of a readable text string
> >> being output from an OTP? Most of the encrypted files
> >> I've looked at contained very few readable strings of
> >> even two characters. I would think that a readable
> >> string output would be more likely to be the result of
> >> an accidental transmission of plaintext or a zero key
> >> than it would be the result of a readable string
> >> encrypting to another readable string.
> >
> >To answer this precisely you need to provide a definition of "a readable
> >text string". In terms of letters and spaces in ASCII the odds would be
> >(65/265)^N where N is the length of the string of text. Of course this
> >formula treats upper and lower case as similar so it includes WiErD
> >STRingS liKE thiS One.
> >
> >> >(n.b. -- if the message I receive reads "attacd at
> >> nown", and you use
> >> >a stronger filter of never allowing six successive
> >> zeros, then I can
> >> >still unbutton your message. The reason being the pad
> >> necessary to
> >> >produce "attack at noon" would be an illegal pad --
> >> and hence you're
> >> >still attacking at dawn).
> >>
> >> Is this an indication of a "fatal flaw" in the OTP?
> >> From what I've read in this newsgroup, it appears that
> >> much of an analyst's work is discovering how plaintext
> >> is leaked into the ciphertext. With the OTP, any byte
> >> of zero in the key leaks a plaintext character, and
> >> that would seem to make analysis possible. Or, as
> >> described here, maybe easy. On the other hand, if I
> >> knew that the only two possible messages were "attack
> >> at noon" and "attack at dawn", I wouldn't bother
> >> worrying about which the message specified. I'd already
> >> know enough to prepare for an attack.
>
> This isn't an indication of a fatal flaw in the OTP. The reason is,
> bluntly, that the amount of "leakage" produced by a zero character
> in the bad -- or even a zero bit in the pad -- is *exactly* balanced
> by the amount of "false leakage" where something it put into the
> pad. So if you see an 'E' in the cyphertext, you have no way of knowing
> whether or not this is a leaked 'E' or a spurious 'E' created by
> something else XORing to E.
>
> And, in fact, if this "leakage" *weren't* there, then you would KNOW
> every time you saw an 'E' that the plaintext letter COULDN'T be an 'E',
> which would be a significant weakness..
>
> >> >>
> >> >>> As to whether or not the loss of entropy is
> >> significant to make a
> >> >>> practical difference -- that depends on the degree
> >> of filtering.
> >> >>> What you do really buy by doing the filtering? Not
> >> much --- and
> >> >>> every time the filter triggers introduces a
> >> weakness.
> >> >>
> >> >>Among other things, a crypto system needs to inhibit
> >> the identity operation on
> >> >>plaintext. I.e., the idea of a crypto system that
> >> includes the possibility that
> >> >>ciphertext == plaintext has a flaw. Mathematically,
> >> the system including the
> >> >>possibility is infinitesimally "stronger" due to the
> >> larger search space, but
> >> >>that's not the unit of measure for crypto strength.
> >>
> >> See what I mean? Both paragraphs above make sense and
> >> sound right. There are (simplistically) only four
> >> possibilities:
> >> The first is wrong and the second is right.
> >> The first is right and the second is wrong.
> >> Both are right.
> >> Both are wrong.
> >> However, if both are right, then both are also wrong,
> >> if they actually contradict each other.
> >>
> >> Maybe they don't contradict each other and both are
> >> right.
> >
> >I think the latter is true. The discussion above involves two
> >conclusions: 1. any filtration reduces strength by some amount; and 2.
> >Filtering out pathological patterns is not harmful to the security of
> >an OTP.
>
> Unfortunately, no. I gave the example earlier where a filtered OTP didn't
> produce any security. More generally, if c is the (received) cyphertext,
> and p is a potential plaintext, but p^c is KNOWN to be something that
> would be filtered, then you can exclude p as being a potential plaintext.
> This contradicts the requirements of perfect security.
>
> >> I mean, theoretically, a TRNG could start up generating
> >> a 2^1000 bit sequence of zeros, and that be a
> >> legitimate output. I don't think that would be very
> >> useful.
>
> But the odds of this happening are, literally, one in 2^1000 if
> the generator works. So for every time this happens, you'd get
> millions or billions of false English-appearing cyphertext messages.
> So a cryptographer would be misled millions of times more often if
> he treated an English cyphertext message at face value.
>
> >> My use or lack
> >> of it has no effect on the output. Every bit will
> >> continue to be generated completely independently of
> >> every preceding bit. Does my lack of use of output
> >> (between messages) constitute an unintentional form of
> >> filtering?
> >
> >In theory yes. An attacker knowing your intention to avoid using "bad"
> >patterns does not have to consider those keys. Thus his job is easier.
> >However, the amount of reduction in the work he has to do is
> >infinitesimal.
>
> Absolutely. Intelligent filtering will not introduce other than
> a purely theoretical and highly improbable break. A statistician
> friend of mine likes to talk about "clinical significance" -- this
> is a classic example of something with no clinical significance.
> On the other hand, if you're going to be playing around with the OTP
> *because of its perfect secrecy properties*, there's no room for
> judgements about "clinical significance."
>
Did you miss the thread in which I quantized the strength reduction (degree of
imperfection) or did you ignore it? In point of fact the loss of perfection
is correctable with a trivial extension of the ciphertext.
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Who will win in AES contest ??
Date: Mon, 25 Jan 1999 23:34:50 GMT
Reading this thread, it is clear that a lot of you have thought about
AES and the various candidates, and have opinions on which algorithms
you think should be selected.
I strongly urge all of you to send comments to NIST. NIST needs
comments from the community, not just from government agencies and not
just from cryptographers. We're all going to be stuck with AES
(whatever it is) for a long time, and we need to make sure NIST picks
an algorithm we like.
Anyone can submit comments. Comments can be on paper or in email.
Instructions are at the NIST AES website:
http://www.nist.gov/aes
AES is our standard. Get involved. Please.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: [req]:Cryptanalysis tool - word pattern table
Date: 25 Jan 1999 14:11:44 -0500
In article <[EMAIL PROTECTED]>,
Darren New <[EMAIL PROTECTED]> wrote:
>> > > It would list, for example, a pattern such as "ABACD" and then every
>> > > word in the English lang which fit that pattern (for the above example:
>> > > "every" fits).
>> > > Does anyone know where such a table can be obtained?
>
>It sounds like it would be very, very simple to write a program to do
>this if you could find a dictionary of English words. It sounds like a
>10-line BASIC program to me, followed by "sort -u". The hard part would
>be to get an adequate dictionary.
The MOBY list. Grady Ward used to distribute it; I think it's now
available from the LDC. More words than you could possibly want.
More generally, corpus-based linguistics is a cottage industry
nowadays. There are probably dozens of decent corpora out there.
And, for those of you who are more interested in the product than
the procedure, write me a check and I'll be happy to roll you one.
-kitten
------------------------------
Date: Mon, 25 Jan 1999 22:07:05 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random numbers from a sound card?
Paul Rubin wrote:
> In article <[EMAIL PROTECTED]>,
> David Ross <[EMAIL PROTECTED]> wrote:
> > Has anyone had success using a sound card (like a Sound Blaster) to
> >generate streams of random numbers?
>
> Yes, see http://www.lila.com/nautilus/index.html and download the
> source from one of the sites mentioned there.
At 99-01-25 22:05 EST this link returned File Not Found.
>
>
> > What sort of audio source would you suspect would be the best to use
> >in generating random numbers?
>
> We ask the user to blow into the microphone to make noise, IIRC.
>
> > How would you test the 'quality' of the generated random number
> >stream?
>
> We just test the total amount of energy in the audio to make sure
> the mic isn't dead. We expect that the raw audio will have lots
> of correlation, so we run it through a hash function or block cipher;
> I don't remember the details.
------------------------------
Date: Mon, 25 Jan 1999 22:18:10 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>,
> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> >Patrick Juola wrote:
> >
> >> In article <[EMAIL PROTECTED]>,
> >> Dorina Lanza <[EMAIL PROTECTED]> wrote:
> >> >R. Knauer wrote:
> >> >
> >> >> On Thu, 21 Jan 1999 13:26:52 -0500, Dorina Lanza <[EMAIL PROTECTED]>
> >> >> wrote:
> >> >>
> >> >> >I think it's worse than this. The statement that the output of a filtered
> >> >> >random source is non-random is false. If, for crypto purposes, we exclude
> >> >> >pathological values such as zero from a TRNG we still have an equiprobable
> >> >> >selection from a pool of possible values. The fact that the pool is slightly
> >> >> >smaller does not reduce the randomness because the selection process is the
> >> >> >same. The entropy would be slightly less, but not the independence of the
> >> >> >samples.
> >> >>
> >> >> >This idea of post-processing contaminating the source is fallacious.
> >> >>
> >> >> What you have just said is completely incorrect for crypto-grade
> >> >> random numbers.
> >> >>
> >> >> If you do what you have just proposed, you will be vulnerable to a
> >> >> Bayesian Attack.
> >> >
> >> >No. The filtered key stream is not biased. Every entry in the pool is equally
> >> >probable. The fact that the poll contains 2^N - 2 entries instead of 2^N entries
> >> >does not create a vulnerability.
> >> >
> >> >Please indicate otherwise if you are able.
> >>
> >> The filtered keystream, treated as a set of all possible 2^N strings, is
> >> biased. Since the possible plaintext is one of that set, you need to
> >> do the stats over the entire set -- not only over the set of potential
> >> keys.
> >
> >You are using the term "biased" in a manner with which I am not familiar. Bit bias
> >would indicate a difference in the incidence of ones and zero.
>
> Which is why I used the term 'bias' instead of the more specific 'bit bias.'
> Bias is fairly easy to define -- non-equiprobability of all samples.
> Bias comes in a lot of different forms....
>
> >> Reductio ad absurdam -- instead of throwing out only 2 keys, throw out
> >> K. If K == 2^N - 1, you have no security whatsoever. Please define
> >> the maximum K at which you have "perfect security" and provide reasons
> >> for your answer.
> >>
> >> -kitten
> >>
> >> (Hint : the minimum such K is zero.)
> >
> >OK. First, I think we agree that "perfect security" means maximum attacker effort
>per
> >bit.
>
> No, Shannon gave a very clear definition of "perfect security" that
> doesn't mention maximum attacker effort at all. A cryptosystem is perfectly
> secure if it isn't possible for an attacker to determine anything about
> the message (other than its length).
>
> The rest of the message flushed as being based on this fallacious definition.
OK, I interpret that as a surrender. YOu have declined to respond and provided a
specious
excuse. Your choice.
------------------------------
Date: Mon, 25 Jan 1999 21:32:57 -0700
From: Michael Paul Johnson <[EMAIL PROTECTED]>
Subject: Re: Non exe/com crypto prog
Eli Gamal wrote:
> I need some the expertise of the group. At work we have a new network
> up an running and my boss and all of my superiors have access to
> everything in my file space and every message I send and receive. I am
...
> deleted). I would like to have some way to encrypt my files for storage
> to deter my fellow employees. The files I would be encrypting are
> .doc's (Microsoft Word). It doesn't have to be cryptographically secure
> though that would be better. I ma looking for privacy not protection
> from the NSA. The problem is the server restricts the running of .exe
> and .com files. Are there any encryption programs out there that are
> not .exe's? Maybe some kind of Microsoft Word Marco or an add-on for
> Word?
I can think of at least 3 options:
1. Buy your own computer and internet service, and keep all your
sensitive files on it at home.
2. Use Microsoft Word's built-in password protection (breakable easily
enough, but not everyone knows how).
3. Run your an encryption program on your workstation and not on the
server.
------------------------------
From: [EMAIL PROTECTED] (Edward Keyes)
Subject: Re: Sanity check on authentication protocol
Date: Mon, 25 Jan 1999 23:19:47 -0500
In article <78hrtl$hqr$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> Depends how the shared-secret is generated. If it is derived from
> a user-chosen password then it could be very bad indeed. Simply
> because an offline dictionary attack could use this known plaintext
> to verify guesses at the password (and we all know how bad most
> passwords are). Bit interleaving won't help - the R_A will still
> be identifiable.
>
> The only way I know of to make a key-exchange strong using a pre-arranged
> (weak) shared-secret is with something like DH-EKE. The strength comes
> from the fact that all message plaintext is uniformly random before
> encryption is applied, and no plaintext is used twice, so there is nothing
> to verify a password guess against. Unfortunately this uses DH so is no
> good for your "computationally challenged" platform :-)
>
> It's an interesting problem though...
Well, if my worst fear is a dictionary attack, then I'll be quite happy.
Then I just have to make sure my keys are decent.
At this point, I'm more concerned about making sure that there is no
easy attack against the protocol. As was pointed out by another
commenter, I do open myself up to a variant of a chosen-plaintext
attack by allowing the client to choose R_A initially. I don't know
exactly what possibilities that opens up, but it doesn't make me
feel totally warm and fuzzy...
Thanks, everyone. I think this needs some tweaking.
+------------ Edward Keyes, [EMAIL PROTECTED] -------------+
|................ http://web.mit.edu/eakeyes/www/ ................|
|.... DaggerWare: "small, sharp, and with a heck of a point!" ....|
+- "A little inaccuracy saves a world of explanation." C.E.Ayres -+
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: The Performance of Meet-in-the-Middle
Date: 25 Jan 1999 21:03:49 -0800
In article <78im00$865$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> In article <78gkfo$3si$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (David Wagner) wrote:
> >
> > I don't think I believe the argument.
> ^^^^^^^^^^^^
> Which argument? I think I am making 2 distinct points:
>
> I. It is tempting to conclude from the standard descriptions of the
> meet-in-the-middle (MITM) attack, that it always has time complexity
> strictly bounded by O(2^(k+1)), regardless of how the plaintexts or
> the ciphers are modeled. But that is not true in a variety of
> different circumstances.
>
> II. It is *very* tempting to conclude that MITM is always better than
> exhaustive search O(2^(2k)), regardless of the *specific* choice of
> cipher or plaintexts. I give a counterexample to that conclusion as
> well.
I *think* my post shows that (II) is wrong, and that (I) is "almost" wrong.
By "almost" wrong, I mean that as far as I can tell the MITM attack has
time complexity bounded by O(k * 2^k), which is only logarithmically slower
(logarithmic in O(2^k)) than the naive estimate O(2^k).
If I'm right, a log-factor is close enough that I'd say the "conventional
wisdom" about the complexity of MITM attacks is roughly right.
> You seem to be summarily dismissing the proof of the statement II. To do
> that, you really must either work within the context of its premises or
> find a flaw in its logic. I stand by the proof, [...]
I must apologize profusely. I didn't really understand your proof; the
notation (or maybe the group theory) lost me. I'm sorry. I'd be happy
to try to take a look at the proof, if you feel generous enough to be
willing to "translate" it down to some simpler explanation of the construction,
but the current exposition is over my head. :-(
If I had to take a stab at it, I'd say that my post attempts to dispute
the premises of the proof. Namely, you insist that a good MITM attack
must be able to find The One True Key. My post suggests that this requirement
is too strong. In particular, if an adversary can find another key which
is "almost"-equivalent to The One True Key, then I claim that the attack
should be considered successful.
If you accept my premises, then I believe my post shows that MITM attack
has worst-case time complexity O(k * 2^k), for any cipher.
(But of course I haven't checked this against the counterexample cipher
you constructed. Maybe you should try it...)
I could well be confused; it's easy for me to make mistakes when I try to
do theory. If I am, I hope you'll point out where I went wrong.
------------------------------
** 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
******************************
