> the payloads are decrypted before the HMAC is checked
I mean, on ClientA, I can calculate the HMACA of the plain-text, then encrypt the plain-text using KeyA to get MessageA
Then, on ClientB, I decrypt the MessageA using KeyB to get plain-text, and calculate HMACB from the plain-text.
After all that, I can still compare HMACA against HMACB to check if the message is authentic.
So what seems to be the problem here?
Long story short: writing HMAC code that works correctly is fairly easy, writing Encryption code that works correctly much harder, which means there are way more chances a bug will appear. You don't want to send wild unchecked data to that piece of code, because an attacker might be able to exploit the total lack of checks and extract some information about the plaintext, so you really want to verify it comes from a trusted party before munching it.
The recommended, more safer and sturdier method is EtM (Encrypt then MAC), in which you encrypt the plaintext then MAC the ciphertext.
This way you can verify the cipher before you operate on it.
EtM is [according to wikipedia] "[...] the only method which can reach the highest definition of security in AE [...]".
Being able to supply arbitrary data into your system and have said system blindly apply a secret key to it is IMO not the safe mode. The safe mode is verifying that the data is from a source we can at least moderately trust to now spew out garbage and has the secret key anyway.
Now, it seems like I may did it horribly wrong, I'm going to fix it right now.
Thank you!
EDIT:
After I read an answer[0] on StackExchange, I realized I maybe did it right (Because of the CFB mode is different than CBC). Looks like I need to learn a whole lot more before start that fixing.
Next time I'll just use GCM and save all these troubles.
[0] https://crypto.stackexchange.com/questions/42369/is-this-sym...
In particular, problem number 17 from set 3 is an attack against CBC mode AES used with Mac-the-Encrypt. Maybe a fun exercise would be to first implement that attack against CBC mode, and then try to see if you can make it work against your CFB-HMAC protocol.
The best I can recommend is to take NaCl and then just using secret box. That picks the good defaults for you. Anything after that needs some research as even seemingly harmless naive implementations can ruin the entire cryptography of a program.