How do encryption algorithms know if they have the

Question

I know it is a bad idea to try to implement your own encryption algorithms. Here is one reason why I think it is not:

For example let's say I want to send plainText = new byte[]{2,5,1,6,7} to bob.

If I use AES encryption or another well know algorithm then I will have:

cipherText = Aes.Encrypt(plainText, key, iv); // now I have some cipher text that is not readable to anyone if they do not have the key and iv vector.

if someone wants to decrypt that message then they will have to do something like:

newPlainText = Aes.Decrypt(cipherText, key, iv);

Now my question is how does AES knows if you entered the right key? I think it will be more secure to have an algorithm where it is not prompt to brute force attacks. In other words if the hacker knows you used AES it can keep trying a lot of passwords until the method Aes.Decrypt thorws no exception. Now consider this algorithm:

lets say I want to send the same byte array {2,5,1,6,7} to bob. My encryption algorithm may look like:

password is = "securePassword";

I will iterate though each byte on my plain text and do the Xor operator on the ASCII value of each character on the password. For instance the first byte will be 2 Xor (ASCII value of 's') then the next value will be 5 Xor (ASCII value of 'e') at the end I will end up with {2 Xor 's', 5 Xor 'e', 1 Xor 'c', 6 Xor 'u', 7 Xor 'r'} The nice thing about this algorithm is that you will never now if you have the right key!

with this algorithm it is not possible to know if you have the write key which makes it impossible I believe to decipher it. If you use the well know algorithms you are prompt to a brute force attack if your password is not to long.

*So my question is how does well known symmetric encryption algorithms such as AES knows if you entered the right key? Having an algorithm where you don't know if you supply the right key will not be more secure? *

Answer 1

But to answer your question, the .NET AES provider does know if you're using the wrong key - but that's only because you asked it to.

You tried to encrypt the bytes:

2,5,1,6,7

Using code something like:

var plainText = new byte[] {2,5,1,6,7};
byte[] cipherText;

var key = new Byte[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
var iv = new Byte[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

//encrypt plaintext using one key
using (var aes = Aes.Create())
{
   var crypt = aes.CreateEncryptor(key, iv);
   cipherText = crypt.TransformFinalBlock(plainText, 0, plainText.Length);
}

In reality, AES only operates on 16-byte blocks. In order to transform your input data into something long enough that it can actually encrypt, the input bytes are first padded. When you construct an Aes class in .NET:

using (var aes = Aes.Create())
{
}

the default padding mode in Aes is PKCS#7 padding. This causes the Aes encrypted to pad your plainText to:

2, 5, 1, 6, 7, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11

And those byes are then encrypted into:

210, 49, 160, 164, 2, 53, 121, 254, 79, 249, 91, 111, 104, 173, 50, 207

When you decrypt those cipher bytes:

byte[] recoveredPlainText;
using (var aes = Aes.Create())
{
   var key = new Byte[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
   var iv = new Byte[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
   var crypt = aes.CreateDecryptor(key, iv);
   recoveredPlainText = crypt.TransformFinalBlock(cipherText, 0, cipherText.Length);
}

Aes knows to ensure that proper PKCS#7 padding exists:

2, 5, 1, 6, 7 , 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11

If you tried to decrypt with an invalid key (e.g. {1,0,0, ..., 0}), you will end up with plainText that does not contain valid PKCS#7 padding:

154,203,183,159,52,162,186,41,127,162,152,75,114,109,107,74

And so the Aes decryptor will throw an exception.

You can still decrypt the bytes with an invalid key, all you have to do is tell Aes not to look for any padding by setting Padding = PaddingMode.None:

byte[] recoveredPlainText;
using (var aes = Aes.Create())
{
   aes.Padding = PaddingMode.None;
   var key = new Byte[] { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
   var iv = new Byte[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
   var crypt = aes.CreateDecryptor(key, iv);
   recoveredPlainText = crypt.TransformFinalBlock(cipherText, 0, cipherText.Length);
}

tl;dr: It knows because you used Padding.

Note: Any code is released into the public domain. No attribution required.

Answer 2

First off, the AES algorithm is exactly that. It's just a mathematical cipher. It can't know whether you're using the right key or not. The difference that provides this ability is usually the predefined way that the cipher primitive is combined with the key, IV and one or more "blocks" of the plaintext/ciphertext to produce the result; this is known as the cipher mode.

One of the most common modes is CBC, or Cipher Block Chaining. In this mode, the previously encrypted block of ciphertext is XORed with the next block of plaintext before it's run through the cipher (the first block is XORed with the IV). This mode requires the plaintext message length to be an exact multiple of the block size, and this is accomplished with padding.

Padding, combined with the "chaining" mode of encryption, provides a checksum of sorts. The last block must be a validly padded block (for messages that happen to be an exact length multiple of the block size, the last block is still padding; it's just all zeroes). If it's not, then either the wrong key was used, or the message was corrupted in transit (the chaining effect of the encryption means that any error introduced into the ciphertext is seen in that block of plaintext and in every later block). This is most likely the source of your exception when using the wrong key. However, CBC has been proven vulnerable to a chosen-ciphertext attack, allowing an attacker to recover the plaintext without knowing the key, if he is allowed to feed specially-modified blocks of ciphertext into a decryption algorithm and view the result.

Other modes have built-in message authentication, which prevents this type of attack. For instance, there's CCM, which is Counter with CBC-MAC. First, the message is hashed by running it through CBC encryption, but keeping only the last block of data (remember that cascading behavior? Turns out it's a great way to calculate a keyed hash). Then, the message and the hash digest are encrypted using Counter mode (the IV is XORed with a sequential value, producing a nonce that is XORed with each block of plaintext). If the wrong key is used, or the message has changed in transit, then the resulting message, when re-hashed, won't match the hash digest. It's really impossible to tell which is the case unless you're sure you have the right key, meaning that changing the ciphertext or brute-forcing the key will produce the same failure and in roughly the same amount of time, and so these modes are the gold standard for secure communications channels.

Answer 3

The encryption algorithm doesn't know whether the input key is correct or not! The algorithm works just fine decrypting with any key; it'll just end up with garbage if you use the wrong key. The application using the encryption may be able to detect this once it's done, because the decrypted message will probably have invalid padding or will be malformed in other ways, but AES itself will never "throw an exception".

The algorithm you're describing is a one-time pad. Its fatal flaw is that its keys must be at least as long as the message, and can never be reused -- if the same key is used with two messages, then the two messages A ⊕ K and B ⊕ K can be XORed together to yield A ⊕ K ⊕ B ⊕ K = A ⊕ B -- the key has now been removed from the messages, and it may be possible to guess what the messages are from this.