Subject: Re: [Raven] RE: Response on crypto issue CALEA Not

From: "Steven M. Bellovin" <[email-masked]>
Date: Thu, 28 Oct 1999 13:55:20 -0400

In message <[email-masked]
s.com>, "Carter Bullard" writes:

>    It is mathematically impossible to measure the level
> of protection provided by encryption, so VPN service
> providers would probably avoid this in their SLA's.  They
> will probably state that they use a given algorithm with a
> given key length and hope the public's belief in probability
> is enough.

Last time I checked, mathematicians believed in probablity, too.  In fact, 
it's even considered to be a branch of mathematics.
> 
>    I know this is a tangent but I did want to see if
> anyone would agree or disagree with this line of thinking.
> 
>    The most interesting thing about encryption to me is
> that you cannot measure the level of protection.  Either the
> level of protection is 0, because there is none, or there
> is protection, but it is impossible to measure mathmatically.

Leaving out information-theoretic considerations -- there's a lot of
math in the crypto business these days -- one can say "the probability
that an attacker get the key is X."
> 
>    My theoretical 56-bit brute force DES cracker starts
> with 0xA3458BE7237EFA, because it has a 1's density that I
> particularly like.  Did you get that session key this time,
> or did you get the 34,546,243rd key in my list of particularly
> interesting challenge keys?  My list of challenge keys is
> the entire set of keys, and I'm going to try them all, and
> so I am going to read your message, the only question is when.
> With this line of thinking, encryption buys you some time, but
> confidentiality protection = 0.

"Some" time?  For, say, 168-bit keys, the proper unit for measuring the time 
needed for a brute-force attack is "lifetimes of the universe".
> 
>    OK, lets assume that there is protection, so lets try
> to measure it.  The thesis is that you cannot measure the strength
> of the random session that key you get without challenging it.
> Even within the set of infinitely large keys, there is a theoretic
> set of weak keys, for any algorithm.  Session key generation
> algorithms can not realize if the key they just generated is
> weak or not.  But because the expected set of weak keys is weeee
> (small) and the expected set of good keys is HUGE (large), all
> of this is hidden in the probabilities.  We should somehow
> sleep well, and change keys often.

First of all, whether or not there are weak keys depends on the cipher 
algorithm.  None of the AES finalists have any weak keys, so far as is known; 
for DES, the odds that a randomly-generated key is weak is 1/2^52 or 
thereabouts.  You're not going to hit one by accident.  And yes, the generator 
can check against a list of known weak keys -- but that's probably not worth 
doing, since the code will be poorly debugged.  Again, it just isn't going to 
happen.
> 
>    Now when you add to this mix, sets of random challenge keys
> that will be used in brute force attacks, the problem becomes
> somewhat untenable to calculate mathmatically because it is,
> dare I say, NP complete and relative.  Now that doesn't mean
> that there isn't a means to measure a probablistic notion of
> the protection, but a meaningful value is very hard to calculate,
> almost impossible.
> 
>    This is from a theoretical position.  If we take a practical
> perspective, there are even more barriers to understanding the
> strength of encryption systems like IPSec.  Session key generation
> mechanisms, which are the Achilles heel of the entire strategy,
> are just pseudo-random number generators.  They mysteriously
> generate a number and load it into a register that can't be read,
> of course for our protection.  The interesting thing is that
> there is absolutely no guarantee that the system doesn't
> generate a bad session key, or the same session key, every
> time.  Did you run a test piece of plaintext through to make sure
> you even got a session key?

Random number generation is indeed critical.  You need a good (preferably 
true-random) seed and a cryptographically-strong random number generator.
But the problem is well-known, even in the IETF -- see RFC 1750, for example.
> 
>    I believe that encryption provides no real protection.  Encryption
> may buy you some time, but its hard to calculate how much.

The real risk is our lousy host security, due to buggy code.  Gene Spafford, I 
believe, observed that using strong crypto on the Internet is like using an 
armored car to transport money between someone living on a park bench and 
someone living in a cardboard shack.  But that doesn't mean that the crypto is 
bad, merely that by itself, it can't solve all of our security problems.

		--Steve Bellovin

_______________________________________________
raven mailing list
[email-masked]
http://www.ietf.org/mailman/listinfo/raven

---

From: "chefren" <[email-masked]>
Date: Thu, 28 Oct 1999 20:25:37 +0200

> that an attacker get the key is X."

True but they cannot state what should be behind the "=" in

  X=

There is no further math here...

+++chefren

= =
Verdien 100 Euro bij aanbrengen van een nieuwe
klant voor een website: http://www.ii.nl/premie