Is password-based AES encryption secure at all?

Question

For a few years I have put all my passwords in a text file and encrypted that file with a password using a software solution (Axcrypt) which uses AES-128. The password is not really strong, but I thought AES encryption would make it strong somehow.

But it always bothered me how this can be secure and now that I have read a little about encryption it seems to me that this actually has nothing to do with AES encryption. Because when using a password instead of directly providing the key, the AES encryption becomes completely irrelevant. It doesn't matter anymore how many billion years it takes to crack AES because the only thing that now needs to be cracked is my password. The attacker finds my file, downloads Axcrypt, and bruteforce/dictionary attacks it until it's cracked. The attacker won't need to bruteforce my file with 128bit keys, he bruteforces it with passwords.

So I have two questions:

1. Am I right? Is it completely pointless to use passwords to AES encrypt files?

2. Axcrypt website recommends using a 22-characters-long password to achieve 128 bit security. Will a 22 character password be as secure as a randomly generated key? How?

(I know the actual key is derived from the password with an algorithm. I just can't understand how a password can be secure. The very existence of a password means the attacker will no longer have to deal with AES and keys, only with passwords)

Answer 1

You are correct in that the best strategy for an adversary would be to guess the password, as opposed to cryptanalysis of AES plaintext/ciphertexts. However, this does not make encryption pointless - password based key derivation is a challenge unto itself, separate from encryption, but one that does have practical solutions.

We can strengthen this weak link by making it require a large amount of time to derive the key from the password. If an adversary can only test a handful of passwords per second, then the probability that they will be able to crack a given password drops dramatically.

Granted, this is not a perfect solution - You might need to derive your key on a slow, old computer, while your adversary might have access to a distributed network armed with GPUs and FPGAs. So there is a balance to be had between how long it takes you to derive your key (which must be quick enough) and how long it takes an adversary to guess passwords (which must be slow enough).

Typically a duration of 1 second per derivation attempt is considered appropriate. However, the actual time duration required to compute a hash does not remain constant, even if you iterate the function a constant number of times. This is due to the way computing power scales with time - the iteration count you use to secure your password today may not protect you nearly as well in a few years.

As to whether or not a 22 character password is equivalent in strength to an 128 bit key, this is not a question that can be answered with a simple "yes" or "no" - for example, if your 22 character password is 1010101...10, then no, it absolutely does not have nearly as much entropy as a uniformly random 128 bit value. If your 22 character password consists of 3-4 english words with spacing, it does not have nearly as much entropy as a 128 bit random value.

Answer 2

Am I right? Is it completely pointless to use passwords to AES encrypt files?

No, certainly it isn't completely pointless to use password to AES encrypt files. However, problem lies within details.

The attacker won't need to bruteforce my file with 128bit keys, he bruteforces it with passwords.

This is true, 128bit key is often far bigger than what password entropy is. This is why good encryption schemes don't use password directly (which we usually frown upon, as AES security is only ever checked assuming key has entropy spread trough whole key). Instead, we use Password Key Derivation Functions (PKDF), which are designed to make bruteforcing password harder (because they are slow), and spread entropy into whole key. This gives us some more predicted complexity (since PKDF is slow), but isn't excuse for weak password.

Axcrypt website recommends using a 22-characters-long password to achieve 128 bit security. Will a 22 character password be as secure as a randomly generated key? How?

How long it will take to bruteforce password isn't dependent on it's length, but on it's complexity (entropy). For more details I'd recommend looking under term "password entropy". Example here.

The very existence of a password means the attacker will no longer have to deal with AES and keys, only with passwords

This isn't exactly true. To check if password is correct you need to use PKDF (which takes time), then try to decrypt database to check if key you got is correct. So by no means you magically avoid AES, but there is nothing that stops you from guessing password forever (after all we want you to get files if you have correct password).

As a side note: When you decrypt textfile and put it on decrypted disk, it is unencrypted, and will often remain there after you remove it. This is (one of reasons) why you should use dedicated password manager. And of course you should use good password.

Answer 3

The short answer is, it depends on how you choose your passwords, and on how the software derives the encryption key from the password.

As you've correctly noted, AES is almost never the weakest link in your encryption system. So far, nobody's found (or, at least, published) any way to break AES itself significantly faster than by trying all the possible AES keys by brute force. Doing that for an AES-128 key is far beyond the means of mankind; brute forcing an AES-256 key, at least using conventional computing technology*, should be well beyond the means of any civilization limited to a single star system.

On the other hand, guessing a password can be much easier than that. Exactly how much easier depends on how you choose your password. If your password happens to be, say, 123456, password, qwerty, letmein, abc123 or anything else found on some list of most common passwords, it basically takes no time at all. Even if you, say, pick an obscure word and mix it with some numbers and punctuation, there are password cracking tools like John the Ripper that can very quickly try all combinations like that.

On the other hand, it's not actually hard to come up with a password (or, more properly, a passphrase) that is as hard to guess as a random AES key. For example, a 10 word random Diceware passphrase has a little over 129 bits of entropy, making it about twice as hard to brute force as an AES-128 key.

Sure, a random 10 word passphrase takes a bit of effort to memorize, but not as much as you might think. Here's one I just generated (using /dev/urandom and a Perl script, since I don't happen to have actual dice around): paso stew glans statue north max admix gloat frau betsy. I bet if you really wanted, you could memorize that.**

In practice, even a shorter passphrase should be sufficient for most purposes. A 6 word Diceware passphrase has about 77.5 bits of entropy, and while brute forcing it might be within the reach of, say, the NSA if they really wanted to, your secrets would have to be absolutely vital to national security for it to be worth the effort. Some random hacker who's just after your credit card number or your Steam account has nowhere near such resources available.

Besides, as I mentioned earlier, there are ways for crypto software to slow down brute force password cracking attempts, by using a deliberately slow key-derivation function to convert the password into an encryption key. This is known as key stretching, and any decent cryptosystem that uses passwords should implement it.

Since you specifically mentioned AxCrypt in your question, I took a quick look at their site to see how they claim to process passwords. Under "Technical Details", there's a link to this PDF, which says:

Password derivation algorithm
The password is UTF-­8 encoded without BOM. It is then passed to a PBKDF2­-HMAC-SHA512 key derivation function. 64 bytes of output are produced and then reduced to the target key size. The salt is 32 bytes, and the iterations are set to a fixed value of 1000.

So it seems they're using PBKDF2 with an iteration count of 1000, which is... better than nothing, at least. The 1000 iterations basically slow down brute force password guessing attacks by a factor of 1000, compared to just directly hashing the password with SHA-512. So if, say, an attacker could crack your password in one second without the iteration (which is likely, if it happens to be one of the 1,000,000 most common ones or some simple variation of those), then with the iteration they'd have to spend almost 20 minutes to break it. Or, to look at it another way, slowing down a brute force attack by a factor of 1000 is about equivalent to adding one extra word to a Diceware passphrase.

That said, good modern crypto software would make the iteration count adjustable, and (for desktop use) default to at least 1,000,000,000 or so. That's almost equivalent to adding three words to a Diceware passphrase, or slowing a one-second attack down to 30 years. It's also about the number of hash iterations that a typical modern CPU should run in a little under a second.

If the software is really well designed, it may also use a memory-hard key derivation function that is designed not only to be slow, but also to consume a lot of memory, making it hard to implement on massively parallel password cracking hardware. But such functions have only really become popular in the last couple of years.

With a well chosen password, possibly helped by a good key-stretching KDF, it is in fact possible to ensure that your password won't be the weakest link in your cryptosystem, either. Of course, in practice, that doesn't mean that the system will be unbreakable; it just means that something else will be the weakest link, instead.

---

^{*) One potentially valid reason to prefer AES-256 over AES-128 is post-quantum security. If efficient general purpose quantum computers ever become available, Grover's algorithm could be used to search an $n$-element key space in $O(\sqrt n)$ time. That could potentially put breaking AES-128 within reach, but AES-256 should still remain at least as secure against such quantum attacks as AES-128 is against non-quantum brute force attacks.}

^{**) General memorization tips (not just for passwords!): 1) don't think of the words in the passphrase as just words, think about what they remind you of; 2) don't try to memorize each word separately, but try to associate a mental image with each pair or triplet of consecutive words, so that each word will remind you of the next one; 3) use whatever mnemonics you can come up with — the weirder or more embarrassing they are, the better they work; 4) once you think you've got the whole phrase down, wait 15 minutes and try to recall it again; keep a note in case you forget. Then wait an hour and see if you can still remember it; then a day; then another day; and so on, until it's firmly lodged in your long-term memory.}

Answer 4

Am I right? Is it completely pointless to use passwords to AES encrypt files?

I'd say you're looking at it backwards. A better question would be: "Is it completely pointless to use AES to encrypt password-protected files?" And then the answer is a clear no, because AES is a widely available, well-proven algorithm, which gives us confidence that that part isn't going to be weak.

This latter bit relates to what security people call the weak-link property: a security system is only as secure as its weakest link. Reformulating the above, the point of using strong algorithms to protect data isn't that they're sufficient to guarantee security in practice—it's that they allow us to be confident that if the system fails it will be somewhere else, so we can concentrate our defensive efforts there.

---

Password-based security has precisely the weaknesses that you fear. Its virtue is that that it's easy to use. The goal of security isn't to recommend that users deploy maximally secure solutions—it's to balance security and usability in such a way that users will actually receive adequate safety in practice. How password-based encryption plays out in this broader perspective is of course a difficult question.