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

From: "Carter Bullard" <[email-masked]>
Date: Thu, 28 Oct 1999 07:48:06 -0700

Hey Paul,
   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.

   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.

   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.

   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.

   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?

   I believe that encryption provides no real protection.  Encryption
may buy you some time, but its hard to calculate how much.
   
Carter

> -----Original Message-----
> From: Paul Ferguson [mailto:[email-masked]]
> Sent: Thursday, October 28, 1999 7:09 AM
> To: Bullard, Carter [NYPAR:DS46-I:EXCH]
> Cc: [email-masked]
> Subject: Re: [Raven] Response on crypto issue
> 
> 
> At 07:33 AM 10/27/1999 -0700, Carter Bullard wrote:
> 
> >   So, now to make a quantum jump, in anticipation of the
> >inevitable interaction of IP technology with LE, when designing
> >VPN technology for the ISP, should we consider supporting the
> >ability to selectively turn this stuff off, if these types of
> >orders are common?  This isn't a CALEA issue, but it is a
> >CALEA class issue.  I can see supporting the negotiation of
> >the NULL algorithm as defined in RFC 2410, as a technical
> >solution for supporting this type of "feature", but there is
> >no requirement of VPN equipment manufacturers to implement
> >RFC 2410.  Would this be a bad idea?  I don't really know.
> 
> This makes one wonder -- what happnes if the service provider
> is contractually bound to their customer(s) to provide a "secure"
> VPN service? Aren't there related legal entanglements here?
> 
> Just curious,
> 
> - paul (I don't even play a lawyer on TV)
> 
>

---

From: "chefren" <[email-masked]>
Date: Thu, 28 Oct 1999 19:23:44 +0200

On 28 Oct 99, at 7:48, Carter Bullard wrote:

>    I believe that encryption provides no real protection.  Encryption may
> buy you some time, but its hard to calculate how much.

Although I agree with what you wrote I believe it's not a 
part of this discussion...

+++chefren

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

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

---

From: Greg Broiles <[email-masked]>
Date: Thu, 28 Oct 1999 12:13:22 -0700

> anyone would agree or disagree with this line of thinking.

While I think "mathematically impossible" is too strong, I agree that
it's difficult to gather information about the security of a system, and
thereby to compare one system against another.

If it's hard to measure security, it's hard to measure expected losses,
because we don't know how likely they are, even if we know what the
value of the loss will be if it occurs. (But that's a hard problem,
too.)

In light of those difficulties, I expect that service providers (and
their insurance companies) will avoid writing guarantees about security,
but will instead promise to use "commercially reasonable" methods, or
otherwise use contract terms which allow the specifics to change without
changing the contract. 

> is protection, but it is impossible to measure mathmatically.

I think this is oversimplified - reducing the security of a system to a
binary value is like saying that some (unspecified) team will win the
World Series. Sure, that's true, but how will that information help us
make decisions?

I submit it would be more useful to make finer-grained predictions
about security, where the probability of being secure depends on the
identity (or class) of attacker, and the timing of the attack. 

For example, I can distinguish between a one-bit key (which offers only
the tiniest resistance, even to attackers without computers), a 40-bit
key (which is still strong against noncomputerized attacks, and provides
limited security against attackers with meager computer resources), a
56-bit key (which is within the reach of a nonprofit organization, but
beyond the reach of the average individual), and a 128-bit key, which is
likely secure against any brute-force attacks for another 10 years at
least - but it might (with a vanishingly small chance) fall to a
brute-force attack within minutes, if the attacker is spectacularly
lucky. Using your methodology, there's no distinction between the 1-bit
key and the 128-bit key. 

As you point out, those predictions about security won't be perfect, but
it's very unusual that a person or an organization is blessed with
perfect information about the future prior to making decisions and
plans. I don't think the lack of perfection is fatal.

> may buy you some time, but its hard to calculate how much.

I wish you'd share your reasoning with the folks at the FBI, the BXA and
the Wassenaar Secretariat - perhaps we'd be rid of all this export
hassle, and the current discussion, too. If encryption isn't useful,
surely the government's got no reason to regulate it, nor will they need
help breaking the security of something that provides no real
protection. Right? 

--
Greg Broiles
[email-masked]

---

From: "chefren" <[email-masked]>
Date: Thu, 28 Oct 1999 21:52:24 +0200

On 28 Oct 99, at 12:13, Greg Broiles wrote:

> If it's hard to measure security

No, it's =impossible= to measure security.

But as long as this list keeps open we do can write about 
ins and outs of an IETF tapping standard that would support 
auditing and keeps the dumptcp spooks out of the courts.

+++chefren

= =

---

From: Sandy Harris <[email-masked]>
Date: Thu, 28 Oct 1999 18:57:59 +0000

> Carter Bullard wrote:

> of protection provided by encryption,

This strikes me as bafflegab of the worst sort.

It is mathematically trivial, at least in the case of block ciphers,
to state the level of security they are designed to deliver, which is
the level they will deliver if both design and implementation are
unflawed. It is stated as the number of bits in the key.

Of course it is hard to verify either the design or the implementation.
There are, however, a few tools around that help. Lots of research
literature on cryptography and lots more on software engineering. Quite
a bit of practical experience and oral tradition too, especially in
groups like the IETF.

[snip]

> that you cannot measure the level of protection.

Nonsense. You can clearly put an upper bound on it, the resource cost
for brute force search. For a block cipher, this is determined by
key size.

If the algorithm has no major flaws (equivalently, if brute force
is the best available attack) you have a lower bound equal to the
upper bound, so you have an exact measure of strength.

Of course it is hard to know if brute force is the best available
attack, let alone the best possible. All you can do is to use public
well-analyzed algorithms; verify that multiple respectable crypto
types have looked at them without finding flaws.

If the algorithm has major flaws unknown to you but known to the
attacker, you're up the creek. Of course, you can always use two
or more algorithms in combination. Set up your IPSEC and PGP to
use different ciphers; your email is secure if either cipher is.

> Either the
>    My theoretical 56-bit brute force DES cracker ...

Yes, for DES with its 56-bit key space. But unless you can come
up with a bteer attack than trying all keys, any sensible key
length defeats you completely.

The EFF's $200,000 machine broke DES in ~57 hours. Assume an
attacker with more budget, better technology, whatever, can
break a 64-bit cipher in 1 second. 2^16 times harder, a few
100 thousand times faster.

Try the same hardware against a 96-bit key. 32 bits more key,
so 2^32 times as much search required. Just over a century.

If the attacker is still using brute force, a 128-bit key
is effectively unbreakable. 2^32 centuries, 400 billion
years. Even if our estimates of his speed are off by a
factor of a million, we are safe.

I can live with the notion of you reading my message, as long
as the sun burns out first.

Of course, if you have an attack better than brute force,
then the analysis above fails. I guess I'll just have to use
the best cipher I can find, with a 256-bit key, and hope for
the best.
 
> of the random session that key you get without challenging it.

What are you trying to say here?

> set of weak keys, for any algorithm.

No. There are plenty of algorithms with no known weak keys.

> ....  If we take a practical
> are just pseudo-random number generators.

Not in any competent implementation.

> ... 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.

Nor is there any guarantee a spreadsheet won't give 2+2=-347.975,
or that my next local call through one of your Nortel switches
won't connect me to Australia.

That's why we have a discipline called software engineering.

---

From: "chefren" <[email-masked]>
Date: Fri, 29 Oct 1999 02:52:50 +0200

On 28 Oct 99, at 18:57, Sandy Harris wrote:

..

> the best cipher I can find, with a 256-bit key, and hope for

After at least 2^6 times writing "if" it comes out: He just 
=hopes= for the best. Words of a crypto-believer.

There is more fun here

..

..

> No. There are plenty of algorithms with no known weak keys.

(Forgets to give in there might be people who do know 
weaknesses, forgets that those people probably have good 
reasons not to tell the world, for example keeping NSA 
budged as low as possible.)  

..

> Not in any competent implementation.

(Forgets to define "competent", forgets to admit he cannot 
prove competence.)

> Nor is there any guarantee a spreadsheet won't give 2+2=-347.975,

Yes there is a guarantee for that. You can simply state 
that: If the machine keeps running as designed the answer 
will be 4. This if isn't unreasonably at all compared to 
the if's of crypto-church. (I don't enter those crypto 
churches that much but, if I remember well, the omni 
present crypto-devil was called "bad random number 
generator" in most of them?)  

> won't connect me to Australia.

Beh. What has "your Nortel" to do with this! Yuck!

> That's why we have a discipline called software engineering.

Yes and one side it is known to most of us that software 
easily leads to complexity far far beyond the oversight of 
any sole human being. It's on the other side also known to 
most of us that engineers are the guys who always come up 
with unexpected new ideas to solve problems faster and 
better than expected.

If you =think= you can reason something will cost at least 
2^x years to crack there are guy's who =know= it will be 
2^(x-y). And the Y-people have cracked about any key in 
history faster than crypto believers expected.

Hm. How do we get more idea's for a better IETF internet 
tap standard?

+++chefren

= =