Banc of America Article
Steven M. Bellovin
smb at research.att.com
Sun Jan 26 15:53:34 UTC 2003
In message <Pine.LNX.4.44.0301260529320.29298-100000 at www.everquick.net>, "E.B.
Dreger" writes:
>
>AR> Date: Sun, 26 Jan 2003 00:22:02 -0500 (Eastern Standard Time)
>AR> From: Alex Rubenstein
>
>
>AR> Agreed. And, even if it is super encrypted, who cares? Enough
>AR> CPU and time will take care of that.
>
>Articles about "1000 years to crack using brute force" are a bit
>disconcerting if someone has access to 10,000x compromised hosts.
>While we're on the subject: root certificates, anybody?
>
>Each worm seems to prove the availability of CPU and time.
This is practical against, say, DES, with its 56-bit keys. In fact,
it's been done; see http://www.virusbtn.com/resources/viruses/indepth/opaserv.xml
for an example. But the fact that DES is insecure has been known for
years; it doesn't take a worm to underscore that point. Let's look at
AES or 3DES instead.
Suppose there are 1,000,000,000 infected hosts. Let's further assume
that each one can check a single key in .1 nanoseconds. (That's a gross
exageration, I might add, for a general-purpose machine -- and we're
not talking about 1,000,000,000 NSA code-crackers being infected.)
AES uses 128-bit keys; there are therefore 340282366920938463463374607431768211456
possibilities. Call it 3*10^38. Divide that by 10^9 hosts, and 10^10
tries per second per host. That gives us 3*10^19 tries per second.
There are ~10^5 seconds/day, and 3*10^2 seconds/year, meaning that it
would take 10^12 years for this scenario.
3DES? Well, 3DES may be using 112-bit keys, so we can cut the time by
2^16. Call that 10^5 -- so we'll only have to wait 10^7 years for a
single result....
Yes, with enough CPU and enough time, it's possible to crack modern
ciphers by brute force. But "enough" is quite a large number.
--Steve Bellovin, http://www.research.att.com/~smb (me)
http://www.wilyhacker.com (2nd edition of "Firewalls" book)
More information about the NANOG
mailing list