5

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.

  • 1
    This makes no sense for me. How can they encrypt and later decrypt something if random data are involved in generating the key for encryption which cannot be reproduced when generating the key for decryption (otherwise they would not be random). Maybe you should provide links to the original description how they do it instead of providing your own interpretation of it. – Steffen Ullrich May 8 at 16:37
  • They apparently store the random data (salt), which I know is an acceptable practice in general. My question was about the key widening and whether doing so still can be called AES256. – Larry May 8 at 16:42
  • If the key is 128 bit and the salt is at least 128 bit one might get a real 256 bit key, i.e. with a full range of 2^256 possibilities. If the salt is less than 128 bit it is impossible to get such a key since possibilities are not created from nothing. But it is unknown from your description what they are doing exactly. – Steffen Ullrich May 8 at 16:51
  • Steffen, thank you. I have no additional details on the process and have made that note in my OP. – Larry May 8 at 16:54
  • You can use AES256 with even a single bit by just repeating it 256 times. But this in effect gives you only two possible keys which is easy to brute force. Thus it is not relevant if they use AES128 or AES256 but what the entropy of the key is they are using. Unfortunately, your question does not provide the necessary details to determine this. – Steffen Ullrich May 8 at 16:58
5

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.)
  • Yeah, everything about this screams cryptographic incompetence. – Stephen Touset May 9 at 5:19
3

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 2128 instead of the expected 2256. 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.

  • 1
    Definitely a useful addition to the discussion already here. Thanks for this. – Larry May 9 at 3:10
1

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.

  • Thank you. This was pretty much my assessment also. I'd be happier if the key were truly 256 bits of entropy but at least the approach seems fairly standard. – Larry May 8 at 17:12
  • "they get as much security as 128 bits + the size of the salt in bits".... For me, the question is: What is the level of difficulty the provider has to decrypt the files, given the provider claims they are unable to do so? For me, the answer is 2^128 brute force, since we know that the salt is known to the service provider. The only thing not known is the 128-bit master key. – Larry May 8 at 17:26
  • Yes, if the idea is that they don't keep the key, it's 128 bit security. – Z.T. May 8 at 17:28
  • I suppose if I had any quibble it would be the company's touting AES256, when in fact it may as well be using AES128 since it seems to me the latter would provide no less (or perhaps trivially less) security than their current scheme. – Larry May 8 at 17:41
  • If your key is terrible (e.g. "secret" padding with zero bytes), at least the data is encrypted with an ok key using the salt they added, so an attacker needs their salt to start guessing your key. Maybe that helps in a scenario they care about. – Z.T. May 8 at 18:02
1

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?

  • You cannot generate entropy from nothing. If you put only 128 bit entropy into a deterministic algorithm you can at most get 128 bit entropy out - even if the key itself is 256 bit long. Thus it depends on the size of the salt, i.e. with a 8 bit random salt you can get at most 128+8 bits of entropy out. – Steffen Ullrich May 8 at 16:53
  • Clarified, randomness was what I meant. – leaustinwile May 8 at 17:01
  • This makes no difference. You cannot "create" real randomness with a deterministic algorithm. – Steffen Ullrich May 8 at 17:04
  • It's not generating entropy from nothing. Standard passwords of even low quality are commonly used as a basis for pbkdf key stretching. The resultant key is a fully legitimate extended key and just as resistant to attack. The catch is that if you know the big key was generated from a trivial key and you know the stretching algorithm, it might be far easier to attack the small key to derive the big key. Typically the stretching algorithm uses a high repetition hash to dramatically slow the small key attack. – user10216038 May 8 at 17:10
  • 2
    @leaustinwile: "It takes a key of lesser randomness and expands via the methods above to a longer key while increasing the randomness of the key. This increases the duration an attacker would need to break the key." - a deterministic function does not increase the randomness. It therefore does not increase the key space. All what it does is to make computing the key space more time consuming by using a deliberately slow function to derive a long key from a short input. And only this makes brute forcing harder, not some increased randomness. – Steffen Ullrich May 8 at 17:50
0

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 2128 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.

  • Thanks for this. The only obvious explanation for why 128-bit was chosen is that it comprises part of a private URL for downloading the file--and thus a shorter URL can be generated. If this is the only reason it seems a weak argument. Some discussion of another weakness of secure file share services was reported in 2014 here newswise.com/articles/view/616521/?sc=rssn with the full paper here: arxiv.org/pdf/1404.2697v1.pdf. The weakness they found was the fact that the companies generate their own certificates rather than using third-party certificates. – Larry May 9 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.