Do you need a HMAC if decryption attempts are severely limited? 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.
"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.