Suppose I have x = <64 bits of data>. I build a 128 bit block $P = x || x$, and transmit a message $M = AES(K, P)$. The receiver has the same $K$.

The receiver can then decrypt the message, split the decrypted block in two 64 bits parts, and comparing them for equality. What kind of guarantee would the equality check provide? Would they be able to securely authenticate the message?

Edit: as stated in a couple answers, the $x||x$ concatenation is a red herring. The scheme looks equivalent to padding x to 128 bits with all zeroes, then checking the decrypted block for the same sequence.

  • $\begingroup$ Found a very similar question that has an interesting answer: crypto.stackexchange.com/questions/25658/… $\endgroup$ – Davide R. Jul 10 '15 at 17:16
  • $\begingroup$ Another answer here addresses a similar case of using AES-ECB as a MAC: crypto.stackexchange.com/questions/18945/… $\endgroup$ – Davide R. Jul 10 '15 at 17:29
  • 2
    $\begingroup$ This scheme loses semantic security — if you ever encrypt the same message twice with the same key, an attacker can see that the message was replayed (likewise, an attacker can themselves replay messages). You will also at best case only have a 64-bit MAC, which is considered within the realm of brute force. Note also that this scheme is equivalent to padding with 64 bits of zeroes and checking the decrypted text for that value. $\endgroup$ – Stephen Touset Jul 10 '15 at 17:33
  • $\begingroup$ @StephenTouset, very complete short answer, thank you. Semantic security is not my worry here, but I see the weakness. Same goes with the 64 bits MAC: it's fine for my use case, but not for every case. The note about padding with all zeroes was especially eye opening, as I got myself narrow minded on the idea of providing redundancy within the message. $\endgroup$ – Davide R. Jul 10 '15 at 17:44
  • 2
    $\begingroup$ Note that I make no claims about the overall security of the scheme, those are just the immediate concerns I noticed. I suspect that AES being a PRP (and therefore a PRF) ensures that an attacker cannot break this scheme in less than $\DeclareMathOperator{\O}{O}\O(2^{64})$, but I'll wait for actual cryptographers to state that definitively. That said, if you're having to ask questions like these, it's undoubtedly simpler to just use AES-GCM and not try to be clever. $\endgroup$ – Stephen Touset Jul 10 '15 at 17:55

Concatenating two copies of your message is unnecessary and is equivalent to padding out your 64 bit message to the full 128 bits with zeros from a security standpoint (which happens automatically in the encryption process).

Would they be able to securely authenticate the message?

I assume you mean Authenticated Encryption. The simple answer is no. AES on its own only provides provides confidentiality, not Authenticated Encryption (which is defined as confidentiality, integrity, and authenticity). To get true Authenticated Encryption you would need to use some sort of hash function to create and append a mac, which is validated during the decryption process.

More information on Authenticated Encryption can be found here.

EDIT: Sorry I was making a few assumptions about other concepts outside the scope of this question. The reason why simply encrypting one block of AES doesn't give you integrity or authenticity is because it is susceptible to modification by an active attacker. One way this would work is actually pretty simple, but it assumes you would also use an Initialization Vector (IV). While not specifically stated in your question, this would be required to make the message resistant to Replay Attacks and is the only way a block cipher is CPA secure.

Assuming CBC mode, the IV is XOR'd over the plain text before encryption. If you were to XOR what you think is in the plain text (a guess), then XOR what you want to be in the plain text, it will be XOR'd into the plain text before it is encrypted, thus modifying it to whatever the attacker wants. Other modes could be venerable to attacks like this also.

You could also use this method and the fact that the first 64 bits of the message should match the second 64 bits as a oracle where by you could test one character at a time and watch what response a server gives back to actually decode the message.

  • $\begingroup$ To clarify, the authentication I'm referring to is: decrypting the message, splitting the two 64 bits blocks, and comparing them for equality. What kind of guarantee would the equality check provide? $\endgroup$ – Davide R. Jul 10 '15 at 16:24
  • $\begingroup$ Using the terminology from your link, it would be a particular case of MAC-then-Encrypt with the MAC function being an identity, and the message + MAC fitting in a single AES block. $\endgroup$ – Davide R. Jul 10 '15 at 16:35
  • $\begingroup$ It isn't a true mac without a hash function of some kind involved because there is the possibility that an attacker could modify both strings equally. If you used P=MAC(x||K)||x where MAC is a collision resistant hash function on a concatenation of the message and the key, then yes, this would be the MAC then encrypt form of AE. The idea being that K is secret and would be required to create a new valid MAC for a modified message. $\endgroup$ – DuneWalker Jul 10 '15 at 16:41
  • $\begingroup$ my question would then be: can an attacker modify both strings equally, even if the concatenation fits within a single AES block? This is the point I don't see addressed in your answer :) $\endgroup$ – Davide R. Jul 10 '15 at 17:04
  • $\begingroup$ Thanks for the edit. I was thinking of the AES cipher itself, not any specific mode of operation, since we are talking about a single block. If you'd rather, think ECB. So, no IV. The message itself is the 128 bits. I think I wasn't clear in my question about my security requirements, so I was trying to leave it open to understand what security properties would such a scheme provide. $\endgroup$ – Davide R. Jul 12 '15 at 13:32

Sorry for not being specific (as I don't know that much about AES itself) but you should go with RSA for messages, generally asymmetric encryption is great, but slow. The best solution is to encrypt AES password with RSA (pgp for example) and then use this password to encrypt messages. This way you can share passwords in safe way.

And pgp allows source verification, that makes best solution for you.

  • 3
    $\begingroup$ Sorry, this doesn't even get close to answering the question. $\endgroup$ – Davide R. Jul 10 '15 at 17:18
  • $\begingroup$ Well I thought you want to verify if message is not modified and comes from verified source. Got something wrong? Well possible as I'm so confused now with my problems :p $\endgroup$ – Chlorek Jul 10 '15 at 17:21
  • $\begingroup$ Sorry, I re-read once again, now I figured out what exactly you want. "What kind of guarantee would the equality check provide? Would they be able to securely authenticate the message?" - as far as I know it does not guarantee anything, yet it might be quite difficult obstacle for attacker to get through $\endgroup$ – Chlorek Jul 10 '15 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.