AES256 with 128 bit key

Question

A popular zero-knowledge file sharing site uses a 128-bit master key for encryption.

However, they claim to be using AES256. When questioned, they explained the master key is widened using PBKDF2 and random salt to 256-bits.

Can this technically still be called AES256? Is this method of widening from 128 bits to 256 an acceptable practice?

EDIT: I have no more detailed information on their process.

Answer 1

AES-256 is a specific algorithm, and it's the same algorithm whether you use the key 3e9e98e31ba18d8d18283aceb3c6e17016b729e1363afc5bea8bf7df295b03e9 every time, or derive a key with PBKDF2 from some password, or choose the key by flipping a coin 256 times.

So this is not a contradiction. But that doesn't mean their system isn't full of red flags!

1. They're abusing the technical term ‘zero-knowledge’ from the cryptography literature, which suggests that their marketing department is better-funded than their cryptography department.
2. It's hard to imagine why they use a 128-bit master key and then expand it with PBKDF2. If the 128-bit master key is actually a passphrase, then there is no reason to limit it to a 128-bit space; if it's chosen uniformly at random, it's hard to imagine that they can't afford the additional storage for a 256-bit key—especially if they're also storing a salt!—and there's no reason to use something expensive like PBKDF2 instead of (say) HKDF.
3. They're hiding their design, which suggests they are so embarrassed by it they don't want anyone to see how bad it is because it might hurt their business. (But they will likely rationalize this to themselves by pretending that other businesses would copy their bad design, which would be foolish because there are obviously better public designs available, or that adversaries won't be able to figure it out, which would be foolish because designs are much harder to conceal than keys as Kerckhoffs' observed over a century ago.)

Answer 2

It's important to understand the differences between AES128 and AES256. It's more than just AES taking a key of twice the size. The algorithm itself is different, though only slightly. AES fundamentally consists of a number of rounds. Each round can be thought of as a mini cipher. After plaintext goes through enough rounds, it becomes effectively impossible to reverse the computation. For AES, each round takes its own 128-bit key. AES128 uses 10 rounds, but AES256 uses 14 rounds. It's the job of the key schedule to convert a single key into a number of distinct round keys. These two versions of AES use a different key schedule to account for the different sized keys. In addition to that, AES256 needs to generate 4 more round keys than AES128 to supply the extra rounds with key material.

AES256 given a 128-bit key (whether the key is expanded using a secure KDF, padded with zeros, or simply repeated twice) is not identical to AES128 because the key schedule is acting on 256 bits of material, and because it has 14 rounds instead of 10. So yes, it can still be called AES256, but the keyspace is 2¹²⁸ instead of the expected 2²⁵⁶. This is still enough to protect from brute force.

An interesting note is that, in theory, AES256 with a 128-bit key will be slightly more secure against cryptanalysis than AES128 with a 128-bit key, simply because of the extra rounds it uses. These rounds don't increase the key space at all, but they do make certain types of mathematical attacks against the cipher significantly more difficult. Thankfully though, 10 rounds is still safe.

Answer 3

Yes it is a widely accepted implementation technique. pbkdf2 is a key expansion algorithm (key derivation function) that is used to create a key that is more resilient to traditional bruteforce attacks. It works by repeatedly computing an MAC or hash function against the initial provided key to derive a longer, more resilient key. It's also a slow-by-design algorithm, which increases the computational resources necessary for an attacker to attempt to brute force the whole key space thus limiting the impact of encrypted data being stolen.

It takes a key of lesser length and slowly expands it into a larger key. This increases the duration an attacker would need to break the key. This key is then used for AES encryption. So yes they are using AES-256 with pbkdf2 for key expansion which is fine.

One thing I would like to add, is that from the attacker's perspective, if they do not know that pbkdf2 is in use, the likelihood that they will recover the keydata becomes much lower. Because they won't be able to compute pbkdf2 against the key passphrase attempts, they'll have to target each of the 256 bits specifically. They can't just launch a wordlist at it like they could if they knew pbkdf2 was in use.

Though I'd be more considered about their claims of zero knowledge and where the proof on that is. But does this help answer your question?

Answer 4

It is AES-256 if it follows the AES-256 spec (number of rounds, etc.).

Even if they take a 128 bit key, run it through SHA-256 to get 256 bits and use that as an AES-256 key, it's still AES-256. Such a thing would not provide the security of AES-256, but it is AES-256.

If they generate a random salt and use a KDF to generate a 256 bit key, they get as much security as 128 bits + the size of the salt in bits, as Steffen Ullrich wrote in the comments.

Answer 5

It is a practice. WPA2 uses this sort of approach, for example. Whether it increase security or not in your particular example is a more nuanced question.

Let's start with AES-128 and a 128 bit key as a baseline. This would be the obvious solution. At the moment, AES-128 is very hard to break. But perhaps one is worried this might not be true in the future. AES-256 offers some future proofing (or at least it appears to offer some future proofing... devil is in the details).

So we can upgrade to AES-256 and use a 256 bit key. This would also be an obvious solution. It would give you all of the perks others have mentioned in other answers. But what if there was a reason they couldn't use a 256 bit key? I cannot speculate why one would be unable to use a 256 bit key. But let us, for sake of argument, assume that there is indeed a reason they can't use a 256 bit master key. They have to use a 128 bit master key. Maybe there's some backwards compatibility issue, or maybe the CEO was born on December 8th. For whatever reason, we find ourselves limited in this way.

We could just concatenate the 128 bit key with a bunch of zeros (or any other known value) to get a 256 bit key. That would get us many of the advantages of AES-256 (such as the extra rounds), but we would still have only 128 bits of entropy to brute force. That's currently "enough entropy" for most uses, but it's not 256.

Now AES is designed to be fast. Very fast. And energy efficient too. These are all great things for a crypto algorithm, but they're also great things for an attacker. If the attacker knew the key expansion was just concatenating zeros, they much be able to attack that directly, and they can attack an algorithm that was designed to be fast.

Enter PBKDF2. This is an algorithm that is designed from the start to run slow. How slow? Tunably slow. You pick how slow you want it by changing the number of iterations of an inner algorithm. WPA2, for example, chooses to iterate it 4096 times.

If you use PBKDF2 to expand your key from 128 to 256 bits, then use AES-256, your situation is better than if you just concatenated zeros. You still only have 128 bits of entropy -- that never changed. But now if they want to crack the problem where its only a 128 bit problem, you have to go through PBKDF2, which is much slower than AES. You don't know what iteration count they chose, so we can't calculate how much slower, but in theory they chose a count with the intent of making it very slow.

Meanwhile, the data is encoded with a 256 bit AES-256 key. This 256bit key does not have 256 bits of entropy. It only has 128. You can only get what you put in. But it is a 256 bit key. And, importantly, its hard to determine which 2¹²⁸ keys are possible outputs from PBKDF2 (with known parameters, including the salt). So in theory, if you want to attack the fast-to-attack AES encryption, you have to do it on a 256 bit key space. If you want to attack the smaller 128 bit key space, you have to do it through the slower PBKDF2.

So in theory, you are safer using this approach than just using AES-128 or using AES-256 with a simple key expansion algorithm. However, the devil is in the details. When you start layering algorithms like this, you don't get to mentally add the security they provide. You actually double your attack surface. If there's an issue with AES or if there's an issue with PBKDF2, it might break your system. However, against brute force attacks, this will be very strong.

The closing caveat is a reminder of the odd choices this company made. Why not have a 256 bit master key? If you did, all of this gets very simple. It only got complicated because there was a desire to have a 128 bit master key. In some cases this pattern makes sense. In the case of WPA2, using PBKDF2 to feed AES like this makes sense because the key is generated by an average user, who knows little of security, and would have difficulty generating a password with 256 bits of entropy. It is unclear, with the details not provided, why a 256 bit password could not be generated in your case instead. But perhaps, with more details, one could come up with an argument for why their pattern makes sense. We do have evidence that it made sense in at least one domain, WiFi.