How do encryption algorithms know if they have the right key

Question 1

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.

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

Question 3

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.