[Discuss] KeePassX

[richard.pieri at gmail.com (Richard Pieri)]

Kent Borg wrote:
> I'll accept your math, and it makes my point. You describe a facility
> that can only brute-force a couple hundred 80-bit keys a year.  Which
> means brute-forcing 80-bit keys is not something routine and cheap for
> the NSA, not when they think they need a plaintext copy of *everything*.

Go back to PRISM. How did the NSA get all that traffic data? They asked 
for it, and the big providers handed it over. It stands to reason that 
the NSA has obtained SSL certificates from public CAs the same way. If 
so then the vast bulk of Internet traffic is already decrypted by the 
time it ends up on the NSA's storage servers. But even if this is not 
the case, SSL and TLS are vulnerable to chosen plain-text attacks (CRIME 
and BREACH). The protocols are vulnerable regardless of the keys or 
ciphers you use.

This covers, what, 95% of the encrypted traffic on the Internet? Yes, 
there is a cost to running CRIME and BREACH attacks but it is a tiny 
cost compared to exhaustive search/brute force.

Now, my noodling is based on some assumptions. One is that the NSA 
doesn't know about any weaknesses at all and therefore must brute force 
every key that isn't in the ~95% of automagically decrypted traffic. 
Another is that they're using off the shelf GPUs. I doubt that either of 
these is the case.

Take a look at the current state of the art in Bitcoin mining. The 
fastest Bitcoin mining GPU manages 1.2 GH/s (billion hashes per second) 
at a cost of around $1000. Most lesser GPUs get around 0.3 GH/s. A 
Butterfly mining box with a cost of $1250 performs 25 GH/s, an 
improvement of 20 times that of the best GPU, and pushing 100 times the 
performance of lesser GPUs. ASICs offer a massive performance 
improvement for roughly the same cost.

A 100 times performance improvement over my GPU noodling reduces the 
32-hour crack time to just 19 minutes. If there is a weakness in the 
cipher that reduces analysis time by another order of magnitude? Your 
80-bit key will be cracked in less than 115 seconds.

This is based on the assumption that the NSA can do no better than the 
state of the art in Bitcoin mining. I figure they can do better than 
that so a 500 times performance improvement over the GPU solution may be 
a more realistic figure. If so then your 80-bit key can be cracked in 
~24 seconds. If the NSA has ASIC boxes that are 1000 times faster than 
my GPU noodling? 11.5 seconds.

More realistically, the NSA won't bother with brute forcing every key 
that they haven't gotten by asking. They'll use more sophisticated 
analysis, so maybe 3-5 seconds to break an 80-bit key? Maybe less? 
Depends on the cipher.

Let's follow along with John's mailing list example: 20,000 messages 
going through BLU per day. Let's assume that every one of them is 
encrypted with an 80-bit key unique to each recipient. And let's use the 
24 second figure just for the example. That's 5.5 days to handle one 
day's worth mail. Seems like a lot. But -- and this is important -- once 
a given recipient's key is cracked it remains cracked forever. New mail 
to that recipient does not need to be cracked, just decrypted with 
whatever keys are associated with the recipient. The 5.5 days cost is a 
one-time cost of doing business. A crack attempt won't have to be 
performed for any given recipient until that recipient's "master" key is 
changed.

This is the biggest problem with the "encrypt everything to keep the NSA 
out" argument. If a key is compromised then anything encrypted with it 
might as well be clear-text as far as the compromising party is concerned.

-- 
Rich P.