I am considering an application where data bandwidth is extremely limited, and considering removing message authentication codes from encrypted transmissions. The encryption method is currently AES-256-CBC.

In this particular application, decryption attempts are extremely limited. Each decryption attempt must be initiated by the user, which powers on the processor. At first decryption failure (or success), the processor is powered off.

  • I am assuming that the AES key is (initially) not known by any attacker.
  • I am also assuming that the attacker does not have physical access to the decrypting processor.

Given the above assumptions and limitations, is the encryption scheme still secure? The 16 byte overhead for HMAC are very expensive in this application.

  • 3
    $\begingroup$ "At first decryption failure" how do you know that it failed? Any CBC encrypted message should decrypt with any key, even if the data is invalid, which is one point of the HMAC, to detect if the ciphertext has changed in transit. You could further truncate the HMAC from 32 bytes to 10 bytes, and still retain min security. $\endgroup$ Commented Apr 27, 2016 at 0:13
  • $\begingroup$ My intention was to get across that after a single decryption (success or failure) the processor turns off. This is the limiting factor that limits decryption attempts by an attacker. I guess you can also assume that I can detect malformed messages outside of the decryption protocol. $\endgroup$
    – JohnDvorak
    Commented Apr 27, 2016 at 12:26
  • $\begingroup$ @RichieFrame I think I understand your advice better now, thank you! I am likely to go with a truncated HMAC solution. $\endgroup$
    – JohnDvorak
    Commented Apr 27, 2016 at 12:45

1 Answer 1


"Given the above assumptions and limitations, is the encryption scheme still secure?"

No; the attacker can

  • remove blocks of [IV + rest_of_ciphertext] from either end to remove corresponding
    plaintext blocks without affecting any other part of what it decrypts to
  • change the IV to change the initial plaintext block in the same way as for the OTP,
    without affecting any other part of what it decrypts to
  • change any other plaintext block in the same way
    at the cost of garbling the previous block
  • remove one or more consecutive internal plaintext blocks at the cost of
    xoring the next plaintext block with a pseudorandom but predictable value

. ​ ​ Furthermore, the attacker can combine those things in whatever order they want.

What follows can be improved if the algorithms can be stateful or there can
be associated data, but otherwise the best way to get short ciphertexts is:

key ​ = ​ $\langle$auth_string , PRP_key$\hspace{-0.03 in}\rangle$
encrypt$\big(\hspace{-0.04 in}\langle$auth_string,PRP_key$\hspace{-0.03 in}\rangle$,iv,m$\hspace{-0.03 in}\big)$ ​ = ​ PRP$\hspace{-0.03 in}\big(\hspace{-0.03 in}$PRP_key ,$\langle$auth_string,m,iv$\rangle \hspace{-0.04 in}\big)$
decrypt$\big(\hspace{-0.04 in}\langle$auth_string,PRP_key$\hspace{-0.03 in}\rangle$,ciphertext$\hspace{-0.02 in}\big)$ ​ ​ ​ = ​ ​ ​ if PRP-1$\hspace{-0.03 in}\big(\hspace{-0.03 in}$PRP_key,ciphertext$\hspace{-0.02 in}\big)$ parses as
an ordered triple whose left entry is auth_string then that triple's middle entry else $\bot$

auth_string being secret might help against some weakness in the PRP,
but otherwise even letting the attacker choose auth_string would be fine.
The "strong pseudorandom permutation" from Theorem 3.1 is the fastest large-domain PRP I'm aware of, and it will suffice if the number of encryptions is also sufficiently small
compared to ciphertext size. There are other constructions that handle more queries
and/or ciphertext-space sizes other than powers of 4, with these being the simplest.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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