I don't understand what's so hard about encryption. There are simple, well-known rules (except the timing one that is sort of news), and if you follow them you should be safe, no?
1. Use a blocks-size unique prefix (IV) for each message (random will do as well)
2. SHA-256 your entire message before encryption and add the hash value at the end to prevent tampering
3. Use AES-256 with chaining to encrypt
4. Use SHA-256 to turn a password into a key.
If your key space is small harden it with hashing 1000 times or so.
5. The time your algorithm takes should be always the same (or at worst one time for success and one for failure)
6. Don't use any other symmteric crypto algorithm.
Almost everything you wrote just now has problems.
1. Has a well-known problem, which is why "Practical" suggests using a nonce.
2. SHA-256'ing a known plaintext doesn't authenticate a messge. In fact, even simply taking a secret key and appending it to your message before you SHA-256 the message isn't secure; there's a reason HMAC is as complicated as it is.
3. This whole blog post was about things that go wrong with CBC mode. For instance, nothing you wrote addressed padding checks --- btw, not strictly a "timing" attack.
4. Using a password as a crypto key is bad for reasons illustrated in the post, which is why secure keystores use random bytes. Hashing 1000 times has nothing to do with your key space.
5. This is like saying "your algorithm should be secure". Easy to say.
6. Everything we're talking about going wrong goes wrong even when you're using AES.
So, yes, I believe you don't understand what's so hard about encryption. You're obviously smart and you've taken some time with this material, and I still don't believe you'd get this right in your first fielded version.
I am not advocating usage of passwords for encryption, I am saying that if you have to use passwords, this is how you use them. Obviously a strong random bytestring is the best key one could possibly have and should be used when possible.
Anyways, re padding - what if I hash the padding as well? surely an attacker would not get anything of value by playing with it?
1. Use a blocks-size unique prefix (IV) for each message (random will do as well)
2. SHA-256 your entire message before encryption and add the hash value at the end to prevent tampering
3. Use AES-256 with chaining to encrypt
4. Use SHA-256 to turn a password into a key. If your key space is small harden it with hashing 1000 times or so.
5. The time your algorithm takes should be always the same (or at worst one time for success and one for failure)
6. Don't use any other symmteric crypto algorithm.