Cryptography course - Message integrity

Let's talk about how to ensure integrity rather than confidentiality - for e.g. banner ads.

CRC is not enough. We need a shared key with both parties.

MAC - Message Authentication Codes => S,V

S(k,m) -> t

V(k,m,t) -> 0,1

Popular variations using AES

CBC-MAC

H-MAC

Truncated PRF is also secure if 1/2^w is negligible where w is the length after truncation.

Encrypted CBC-MAC (ECBC)

Raw CBC which doesn't do the final encryption with a different key.

NMAC (Nested MAC)

Output is in the key space. As opposed to ECBC where output is in X.

In both NMAC and ECBC last encryption step is required else it's insecure.

AES based ECBC is the most popular MAC algo.

AES based ECBC should not be used for more than 2^48 messages.

Message padding

If we append 0s at the end to pad the message, it's risky. Let's a cheque of amount 1 is the message. We pad 0s at the end, which makes it 1000. Now, both 1 and 1000 have the same tag!!

So, padding must be invertible. If m0 != m1, pad(m0) != pad(m1) should hold.

ISO standard

So, pad with 100..00. While removing the pad, keep removing till you get the first 1.

If the message is already a multiple of the block size, add a pad still.

Using CMAC we can avoid padding for messages which are multiple of block sizes.

If the message is multiple of block size, encrypt the last block with K2. If not, pad and encrypt with K1.

PMAC

Parallel, incremental.

One time MAC - parallel of one time pad for integrity

Carter wegman MAC - build many time MAC from one time MAC

Collision resistance - Merkle Damgard paradigm

Davies meyer compression function.

Timing attacks on MAC verification