[Discuss] KeePassX

[kentborg at borg.org (Kent Borg)]

On 08/13/2013 04:30 PM, Daniel Barrett wrote:
> In the absence of the 4096-bit private half of my key, how hard is it
> to decrypt the session key by brute force and thereby decrypt file
> Foo? Do the time arguments from this KeePass discussion apply?

There are three approaches they can take, sorted from fuzzy to known:

1) They can try to break your public key into a private key and then get 
the session key directly.

2) They can try to break the symmetric encryption directly by exploiting 
some weakness in the encryption algorithm that somehow offers an efficiency.

3) They can try to bruteforce the key for the symmetric encryption.

#1.  I think yesterday someone posted a pointer to a PDF that said that 
a 4096 public key is equivalent to a 118-bit symmetrical key. This is an 
estimate, and expect the estimate to fall over time. Public key 
cryptography depends on mathematical problems that are easy to run one 
direction and very much harder to run the other way (multiplication vs. 
prime factoring, in the case of RSA).  There are major risks here.  
Obviously, a breakthrough in factoring is feared.  A breakthrough in 
quantum computing is also touted as being a risk, but as with most 
things quantum, I don't pretend to really understand that.

#2.  DES is known to have weaknesses beyond its short keysize. During 
its development the NSA quietly made changes that made it more robust, 
in a way that was not publicly understood until years later.  AES or 
CAST or whatever, might also have a weakness.  A symmetric cypher is 
really just mixing and mashing your data in a predictable but 
complicated way.  If someone can better understand the "complicated" 
part, there could be a hole that makes it easier to decypt a message.

#3.  This is the most concrete one to understand, and the hardest for 
the NSA to accomplish.  If this is the best the NSA can do, you can do 
the math on the number of possibilities.  You can imagine a parallel 
computer to speed it up.  You can compare large key sizes with the size 
and age of the universe and conclude they are safe. Bruteforcing 
128-bits is impossible.  Bruteforcing 256-bits is 128-bits times as 
impossible.


A related #4 is when there is a passphrase used to generate a 
symmetrical key.  If your passphrase has predictable aspects the search 
space can start common passwords, common phrases in our language, 
initial letters for those phrases, dictionary words, common 
misspellings, and then start doing permutations on on those. The search 
quickly becomes truly enormous, but still far smaller than just 
searching every combination, and even if you are forced to try every 
key, might as well start with common ones and hope to get lucky.  In the 
case of encrypting a file with a public key (and actually a randomly 
chosen symmetric key) there is no passphrase. But, your copy of your 
private key needs to be protected.  It will be likely be encrypted with 
a symmetric key, derived from a passphrase that you chose.  Make that 
passphrase good.  And don't let the other guy get a copy of your private 
key at all.

Finally, #5, is finding the weakest link.  From one end of the 
communication to the other, the encryption might be great, but something 
else goes wrong.  Maybe the "randomly" chosen key wasn't very random.  
Maybe the encryption was just done wrong by someone who didn't 
understand.  Maybe there is a simple bug in the implementation.  Maybe 
there is spyware in your computer.  Maybe there is a hidden camera 
mounted over your keyboard.  Maybe a sysadmin got a National Security 
Letter.  The whole system needs to be secure, it can be attacked at any 
point.

But all that is classic spy-vs-spy.

The new world is the NSA wants everything, and they need to be efficient 
about it to get everything, so anything the interferes with the 
efficiency hurts their efforts.  Maybe there is a weakness in AES.  
Okay, make them spend a lot of computrons exploiting that and your 
message becomes exempt from their "everything" approach.

They can handle an limited number of exemptions.


-kb