I am confused about padding when using a Message Authentication Code (MAC). This paper suggests using a different key if the message is padded, and otherwise not, which really confused me. An example is the following construction (FCBC MAC):
I want to understand padding in detail, so I will make this question bigger. I try to build it like stepping stones, so please tell me if I forget something!
The most simple MAC construction everyone learns when doing crypto is CBC MAC; I assume this as common knowledge. CBC MAC is insecure if a probabilistic polynomial time PPT adversary can queue variable length messages to a CBC MAC oracle, breaking nearly all common security definitions.
Variable-length indomain MAC
I use the term indomain if the MAC needs no padding (in other words: if the message length is a multiple of $n$, where $n$ indicates the block size of the MAC). This enables variable message length to some extent. We can achieve this for CBC MAC, when post-computing the CBC MAC output with a differently keyed pseudo-random function PRF (ECBC MAC).
From variable-length indomain to variable-length outdomain MAC
I use the term outdomain for messages that need padding (in other words: the message length is NOT a multiple of $n$, where $n$ indicates the block size of the MAC). Now I get a bit confused.
Edit (so nobody learn something wrong):
If I understand John Black and Phillip Rogaway correctly, ECBC MAC is only secure if we don't pad. Otherwise, it is not secure. But why? They don't present an attack in their paper, at least I didn't find it.
The addressed problem in the paper is not "security" but "efficiency"! End Edit
Simplified, their idea is to use a key for the indomain case and a different key for the outdomain case when post-processing the CBC MAC. They call (and prove) this Three-Key Carter-Wegman Construction. Can someone explain to me why this is necessary? Why can't I use the same key for both cases (as long as they are different to the keys used before?).
What happens if we pad somewhere else
In most constructions, padding is done at the end. But what happens when we pad somewhere else, e.g. at the beginning? Or in the middle (which may be complicated to verify)?
Reducing the number of keys
As common practice, I have seen that we can reduce the number of keys by using tag bits (0 bit for all messages before the last, 1 bit for the last message). Doing so, the last PRF does not need to be keyed differently. Can you provide me with a link for a general statement of this concept (e.g. in the Carter Wegman paradigm)? How does this comply with the different keys when padding regarding John Black and Phillip Rogaway's work?
Last but not least, did I forget something about padding?