AES-128-CTR message integrity: Construction of HMAC

(Note: This post is not about "rolling my own", but rather trying to deepen my understanding of the underlying structures.)

I'm having difficulties finding clear answers to some questions about the construction of HMACs:

Assuming we have one key for encryption and one key for message integrity checks, and we are using AES in counter mode. As far as I understand, when creating the HMAC for a message, one should utilize all available information: The encrypted message, the key, the nonce and the counter.

1. In effect, does this mean that a separate HMAC must be created for every single message, i.e. all 16 bytes?
2. If this is true, how would the security of a scheme evaluated in which the HMAC would be calculated over arbitrary multiples of 16 bytes, for example only every 160 bytes?
3. And at last, going even further, what would be the weaknesses of using merely the encrypted message (and the key, for sure) for the HMAC calculation, thus leaving out the initialization vector?

Maybe someone can shed some light on this, I have seen people doing exactly this (for example one HMAC (no counter, no nonce) for a whole file), but I'm unsure about the correctness.

• The HMAC only need be constructed over the whole message (e.g., $H(k, n || m)$). – Stephen Touset Jun 8 '14 at 23:56
• ^^ Careful - that isn't HMAC, and is susceptible to length extension attacks – Cryptographeur Jun 9 '14 at 6:53

If you received a message $n||E_{k,n}(m)||H_k(E_{k,n}(m))$, you would only be able to authenticate the ciphertext. If an attacker had tampered with the nonce $n$, AES CTR would happily decrypt your message but give you random data.