Why don’t all AES encryption tools produce the same key from the same password?

Question

Alice and Bob meet regularly. They have agreed face-to-face a 128 bit password which they want use to encrypt/decrypt emails written between them.

They decide to use 256-bit AES. Alice wrote her message, but found that every AES 256 application she used to encrypt her text provided a different ciphertext. She could not therefore communicate with Bob without specifying the tool that had encrypted her text, and she couldn’t check that the tool was genuine by comparing it with others.

Why is there seemingly no standard algorithm? Why is there no simple and trusted tool (e.g. a javascript file) that can be downloaded and used offline for this purpose?

Answer 1

There are two things here:

• Encryption uses mode of operation, and not "AES alone". Some of them are randomized by an initialization vector - that means the encryption of the same text under the same algorithm is still randomized and not deterministic. The encryption methods take care of that. You only need the correct key to decrypt.
• Passwords are not keys. If you meet in person, you can create a real random key. That means each bit drawn independently from $\{0,1\}$, not just a password of a certain length, which can be found in any dictionary. If you want to use a password or a passphrase, then you are advised to use a proper key derivation function for passwords, e.g. PBKDF2, bcrypt or scrypt (most recommendations today go towards scrypt).

The problem with tools is, that if they just write "AES" on top, that doesn't mean they use the same mode or the same key derivation function inside. If they do, then the decryption will work. Still, there are non-deterministic modes, where it is an explicit goal, that the same message encrypted twice can not be distinguished from random gibberish.

All you can do is to actually test the tools available to you, if they work in conjunction. And you can stick to the verified, popular implementations. Never use some amateur implementation - never implement your own crypto.

Answer 2

That's because AES is not a password-based encryption algorithm. It's a block cipher. It may seem like a detail, but such details matter. In cryptography, and in security in general, details often matter.

AES is a pair of functions, each of which takes a key and a 128-bit message and produces a 128-bit message. The two functions are called encryption and decryption, and they are inverses. The key must be exactly 128-bit, 192-bit or 256-bit long.

If you want to encrypt a message whose length is not exactly 128 bits, you can't use just AES. You need to use a mode of operation. A mode of operation describes how to break down the message into 128-bit blocks and combine them, and call the AES encryption and decryption functions to encrypt or decrypt an arbitrary-length message. The mode of operation is typically defined in terms of chaining (dealing with multiple blocks) and padding (dealing with the last, partial block). There are modes of operation that define how to encrypt a message (e.g. CBC, CTR), how to authenticate a message (e.g. CMAC, GMAC), or both (e.g. GCM, XTS).

Additionally, decent modes of operation require some way to ensure that repeatedly encrypting the same message produces different ciphertext each time. Otherwise an adversary who sees two encrypted messages could at least tell if they were identical, or usually if they had the same prefix, and some modes like CTR have even worse failure modes when this is not done properly. All common modes use a unique value to “kickstart” the encryption; for most modes, this unique value is called an initialization vector (IV).

So to define how a message is encrypted with a key, you need to specify several things:

• AES as the block cipher (if using a cipher based on AES);
• which mode of operation is used;
• how the IV is transmitted with the ciphertext. For that last one, there's a de facto standard, which is to concatenate the IV and the ciphertext.

For example, AES-CBC is a key-based message encryption algorithm. So is AES-CTR. AES-GCM is a key-based message authenticated encryption algorithm.

There's still the problem of making a key from the password. An AES key has to be one of three standard lengths, so there needs to be a deterministic transformation from the password to a key. Transforming a password (or any other kind of input) into a key is called key derivation. When the password is memorable to a human, it needs to be stretched. Key stretching is an intrinsically slow operation, so that an attacker who tries likely password by brute force has to expend a lot of resources per attempt. There are currently four common families of key stretching algoritms, also called password-based key derivation functions: Argon2, scrypt, bcrypt and PBKDF2 (roughly from most preferred to least preferred but still ok). Each of these is a key stretching function (or a family of similarly-designed functions), which calculate a stretched key from three parameters: the password, a salt (which allows deriving multiple keys from the same password), and a difficulty parameter (the larger the slower; in its simplest form, this is an iteration count).

Thus in order to specify how a key is derived from a password, you need to say something like “PBKDF2 with the salt "ms8321damidj" and with 1000 iterations”. The salt should be public but random (it can be sent with the encrypted message) so that attackers can't make any precomputation to break many passwords. The iteration count is a compromise between low (easier to crack) and high (demanding more processing power from the legitimate users).

In summary, to specify how a message is encrypted with a password, you need to specify: a block cipher¹, a mode of operation, a key derivation function, the parameters for key derivation (salt and iteration count), and how the extra parameters (IV, salt, iteration count) are encoded together with the ciphertext in the message. That's quite a bit of room for variation.

¹ _{Assuming that's what you go, for here are other types of ciphers such as stream ciphers but all you'd gain is not to have to specify a mode of operation.}

Answer 3

There is no such thing as an AES encryption standard. There is the block cipher, which can be used for a mode of operation (and possibly a padding method). Such a mode of operation however requires a keyed block cipher. And a password is not a key - even the PGP mcrypt guys have started to see this now. So you need (at least) some kind of Password Based Key Derivation Function or PBKDF to derive a key from a password. Furthermore, you need to specify where you store the IV, you might want to have authentication etc.

The best way to go about this is to use a so called container format where these things are well defined or listed as options. The most common ones are CMS (cryptographic message syntax) and OpenPGP. These specify how the message is encrypted. Tools such as GPG - already mentioned by mikeazo - allow for password based encryption using the OpenPGP format. GPG is included as command line utility on most computers that use GNU and can be freely downloaded on Windows. CMS can often be used together with a soft token from email applications.

Because of the complexity of CMS and OpenPGP you will also see a host of simpler formats. Fernet is one I've commented on (but it is token based). RNCryptor is another that does perform key derivation. NaCl is another format that gains traction. "The nice thing about standards is that you have so many to choose from." (AST).

Answer 4

In the event this is a homework question, I'll give an answer that would be improbably correct so you may not use it. ;) But maybe people won't accuse you of asking a homework question if you would source where you got the example?

The password and the key are two different things. Early cryptographic implementations used the password directly. This is partially why the Blowfish keyschedule is so complex, it's key schedule is a hashing algorithm able to accept 56 characters (448-bits) of input.

You can see how having the password as a key is a problem in many cases.

https://www.schneier.com/paper-blowfish-fse.html

The algorithm should facilitate easy key-management for software implementations. Software implementations of DES generally use poor key management techniques. In particular, the password that the user types in becomes the key. This means that although DES has a theoretical keyspace of 2^56, the actual keyspace is limited to keys constructed with the 95 characters of printable ASCII. Additionally, keys corresponding to words and near words are much more likely.

(DES key space is actually 2^55 due to the bit complementation property)

Not mentioned in the paper is related key attacks, as if one uses 12 characters for a 128-bit (16 character) key cipher and changes it to another 12 character password, and if an attacker is aware of it, a differential attack could be mounted as the last 32-bits are known to the attacker (depending on the implementation, the last 32-bits may be all zero bits).

But times have changed. While there are still horrid implementations of cryptography ( http://arstechnica.com/security/2014/07/crypto-weakness-in-smart-led-lightbulbs-exposes-wi-fi-passwords/ , they are less frequent as people are more aware of certain issues, ciphers in CBC or CFB mode leak plaintext if there is a colliding IV.

As a result, a password and a random salt is hashed, to reduce the likelyhood of each plaintext being leaked, by effectively generating a new key before a new ciphertext is generated. To reduce the effectiveness of offline brute-force attacks, often the hash is iterated many times to strengthen security.

Although to answer the question you did not ask, test vectors exist.

Answer 5

There exist plenty of standards for that, Alice and Bob just haven't agreed on any.

AES by itself is just a block cipher. Like any block cipher, it transforms an input block of data into an equally sized output block data. The block size of AES is 128 bits. How this transformation is performed is controlled by a key. In case of AES keys can either be 128, 192, or 256 bits. Note that the key size is not related to the block size, the block size is always 128 bits for AES.

Now 128 bits are 16 bytes, so basically AES can only encrypt exactly 16 bytes of data. Most messages are not exactly 16 bytes of data. So if you want to encrypt more than 16 bytes, less than 16 bytes or any message that is not a multiple of 16 bytes, you require a way how to split this message up into equally sized pieces that you can feed into the AES block cipher.

The simplest way would just be to break up the message into blocks of 16 bytes and then encrypt each block on its own, padding the last block as required. But this is a very poor block chaining as the same input data will always result in the same output data. A very famous example why that is a bad idea is shown below. Below you see the Tux image to the left and the encrypted Tux image to the right where just every block was encrypted on its own using the same key:

See the problem? As the same block is always encrypted in the same way, patterns will persist even after the encryption and often these patterns reveal too much information about the otherwise protected message.

There are various better ways to do that, called block cipher mode of operation. The most widely used one is called CBC, yet for better performance many software prefers CTR today. Other well known alternatives are CFB and OFB. Not specifying the block cipher mode of operation is the first shortfall of Alice and Bob. Instead of agreeing to use AES-128, they should have agreed to use AES-128-CBC or AES-128-CFB. Note that any of these modes can be combined with any block cipher, even those with a different block size.

The next problem is that passwords are poor keys. So almost no software uses passwords for keys directly, instead they feed passwords into a key derivation function, that produces good keys out of these passwords. Alice and Bob did not agree on a key derivation function to use or about the exact parameters of such a function.

The most widely used key derivation function today is named PBKDF2 and it requires two parameters to be known: The hash method (which can be any hash function you can think of) and the number of rounds. E.g. the hash method could be SHA-1 and the number of rounds could be 5000. With the same password and the same parameters, PBKDF2 will always generate the same key. The more rounds, the more complex is the calculation of that key, which is good when people try to break encryption by guessing the password as they must run every guess through PBKDF2 before trying it and the more complex that is, the less passwords an attacker can try in the same time using the same piece of hardware.

Of course other methods exist, like bcrypt, scrypt, or the new Argon2, which was the winner of the last Password Hashing Competition in 2015. If you have no other option, you can also just hash a password using any cryptographic hash function and then shorten the hash to the required key size but this way you make it easier for attackers to try out passwords as cryptographic hash functions are designed to be fast and efficient in calculation and in this very special case, being fast is actually not desirable. Not specifying which method to use for key derivation and their parameters was the second shortfall of Alice and Bob.

Last but not least, even when using a block cipher mode of operation, the same data encrypted with the same key would still always produce the same output data and this is not desired as if a lot of messages are encrypted and some of them may be the same as previous messages (e.g. think of network packets encrypted for a VPN tunnel), an attacker not knowing the key, cannot see their content, but he can see how often the same message is being sent or at which intervals and this alone may already reveal too much information. That's why all modes of operation add some randomness to the encrypted data, which is similar how sometimes a "salt" is added to hashed data as otherwise the same data would also always result in the same hash.

This added randomness is called an initialization vector (IV), and it's a piece of data that usually equals the block size of the cipher. So in case of AES the IV is 128 bit (16 byte). The IV usually doesn't have to be special other than that the same key should never be used with the same IV to process different data. It's not horrible if this happens but every time it happens, your encryption gets weaker and weaker. Most of the time the IV is chosen randomly as 2^128 is a very big number, the same size as a UUID and thus chances for a collision are tiny as you can see here.

Of course, the other side requires to know the IV to decrypt the data again but that is not an issue. As the IV can just be a random piece of data, there is no need to protect it at all. Usually the IV is added to the beginning of the decryption output as if it was the first block. But the IV can also be added to the end or being sent separately. How, where and in which format the IV is transmitted as part of the encrypted message is the third thing that Alice and Bob failed to specify.

So the entire problem is that Alice and Bob didn't really specify most of the important details how to exchange the message. It's like saying "We will meet at 9" but without telling the other side the day, p.m. or a.m., or where the meeting will take place. If one person waits at the park at 9 a.m. on Monday but the other person waits at the mall at 9 p.m. on Tuesday, you don't really have to ask why the meeting didn't take place, do you? There were just not enough information exchanged. Saying AES just specify the block cipher being used but this is far too little for specifying a message exchange.

This is why there are standardized message formats that include all these variable parameters as part of the message, e.g. PGP (Pretty Good Privacy). If Alice and Bob had agreed just on a password and to use PGP, they would not need to know any of these details, no matter what Alice selects (maybe just keeping the defaults of her PGP software), the selection is written to the message and thus Bob doesn't need to know it as Bob's PGP software will know how to decrypt the message by just looking at the message itself. And the PGP format is supported by various apps, so Alice and Bob doesn't have to use the same software.