Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:22
Mark Tillotson (markt@harlequin.co.uk)
Wed, 28 Oct 1998 11:47:21 GMT
Eric Rescorla <ekr@rtfm.com> wrote:
| Huh? Extending the calculation makes it perfectly clear that
| 128 bit keys are long enough for just about any foreseeable future.
| 128 bit keys are 72 bits stronger than a DES key. 72 bits is
| approx 10^21. Now, imagine an attacker with the entire GNP
| of the US (ca. $5x10^12) available to him. That means he can
| build a machine that's say 10^7 times more powerful than
| Deep Crack. Consequently, he'd be able to crack a 128 bit in
| approximately 10^14 days, or 10^11 years. I'm not worried.
One factor you haven't brought into your calculations is _probability_.
There's a small probability that a 2^56 search could find a 128 bit
key by chance, namely one in 2^72. It might just be that one's
approach to secrecy demands that a keysize is chosen that makes it
infeasible for an adversary to have a greater than 1 in N chance of
cracking a key, given your estimate for their resources. I suggest
that you might want to make N quite a large number. You haven't made
explicit allowance for it. It's fundamental to setting up a threat
model to give a value to N, rather than just saying "I'm not worried".
You appear to have taken the position that if an adversary can't
afford to search the entire keyspace, you are safe from them. Some of
us want unnecessary risks reduced to very low levels. We can reduce
them ridiculously easily and cheaply by adding key bits.
|
| Now, consider a key for fee operation. Again, we use Deep Crack
| and $100K as a baseline. Assume the machine has an operational
| lifetime of 5 years and it can crack a key every 3 days. That's
| roughly 500 keys over the lifetime of the machine, or $200/key.
| Now, the cost for an 80 bit key is 2^24 (10^7) * $200 or
| $10^9/key. That's a billion dollars.
If you look in "Minimal Key Lengths for Symmetric Ciphers to Provide
Adequate Commercial Security", Blaze, Diffie, Rivest, Schneier,
Shimomura, Thompson & Wiener, Jan 1996, they have a table of estimated
resources to crack symmetric ciphers of given keylengths, based on
economic arguments of what was feasible with technology then (about 3
years ago).
Reproducing the bottom line of this paper:
| Time and cost Length Needed
| Type of Budget Tool per key recovered for protection
| Attacker 40bits 56bits in Late 1995
|
| Intellegence Agency
|
| $300M ASIC .0002 seconds 12 seconds 75
| ($0.001) ($38)
So, they make the cost about $40, not $200, and allowing for Moore's
law, we should call that around $10 now, for cracking a 56 bit key
(ie. searching a 2^55 keyspace)
Let's say we'd like a security level which gives an adversary throwing
$1M dollars at the problem a 1-in-a-million-million chance of finding
the key. I find this to be a level that leaves me "not worried".
That means the minimum keylength should be 55 + 16.5 + 40 ~= 112 bits.
That's rather more than 80 bits. And that's for today's key cracking
hardware. Say you want to be resistant for the next 40 years, then
upgrading to 128 bits is bound to be insufficient under this threat
model. In fact 160 bits is more like it, extrapolating wildly, as one
has to do.
|
| Look, I'm all for using fairly large keys, but the sort of
| simpleminded alarmism you're engaging in gets in the way of
| understanding how strong our cryptosystems actually are.
| Please do the math before you go ranting about how weak
| or strong things are.
And furthermore it's pointless doing the maths if you don't state the
assumptions in your threat model!
Personally since we all use crypto, we should choose a threat model
that few would ever question as being too soft. That way we'd all be
happy that key sizes are large enough. In the interim treat 128 bit
as the minimum for short-term secrets.
Another quote of relevance from the aforementioned paper:
| One consequence of this uniformity of costs is that there is
| rarely any need to tailor the strength of cryptography to the
| sensitivity of the information being protected. Even if most of the
| information in a system has neither privacy implications nor monetary
| value, there is no practical or economic reason to design computer
| hardware or software to provide differing levels of encryption for
| different messages. It is simplest, most prudent, and thus
| fundamentally most economical, to employ a uniformly high level of
| encryption: the strongest encryption required for any information that
| might be stored or transmitted by a secure system.
|
__Mark
[ markt@harlequin.co.uk | http://www.harlequin.co.uk/ | +44(0)1954 785433 ]
[ personal homepage http://utter.chaos.org.uk/~markt/ | fax " " 785444 ]
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:22