Can Skein be used as a secure MAC in format H(k || m)?

Question

Can Skein be used as a secure MAC in format H(k || m)?

I understand it can work with HMAC, but it is fine as a one-pass MAC in the format above and resists length extension attacks. Is this assumption correct?

One of the Skein authors mentions that Skein has another MAC construction with a security proof in their paper, but I can't find it. Does anyone know how that works?

Answer 1

Length extension attack

The reason why $H(k \mathbin\| m)$ is insecure with most older hashes is that they use the Merkle–Damgård construction which suffers from length extensions. When length extensions are available it's possible to compute $H(k \mathbin\| m \mathbin\| m^\prime)$ knowing only $H(k \mathbin\| m)$ but not $k$. This violates the security requirements of a MAC.

Like all SHA-3 finalists Skein does not suffer from length extensions, so this attack does not apply.

State collision attack

There is also a potential attack based on state collisions where an attacker searches for a pair of messages which collide for all (or at least many) keys. This does not work for the sequential mode of Skein when computing $H(k \mathbin\| m)$, since it consumes the key before the message and the attacker thus doesn't know the internal state when the message gets hashed.

This attack applies in theory when using $H(k\mathbin\|m)$ in the treed mode of Skein since only the first node will have key dependent state and state collisions in other nodes can be searched for without knowledge of the key. This also applies to $H(m\mathbin\|k)$ in the sequential mode.

But since Skein has a 512 bit internal state, finding collisions by brute force costs $2^{256}$ operations, which is ridiculously infeasible.

Still collisions are usually the first property to fall to advancing cryptanalysis, so I have more confidence in MACs where this attack is not applicable at all, instead of merely being infeasible.

Built in MAC mode

Skein has a built in MAC mode, where the key is passed in as a separate parameter. The way it consumes the key is pretty similar to $H(k\mathbin\|m)$ but it doesn't simply concatenate them.

This mode has a few advantages over the simple $H(k\mathbin\|m)$:

1. It cleanly separates the domains of key and message
2. The initial state depends on the key for all nodes in a tree, not just the first
3. The key is consumed before any other parameter
4. The authors supplied an explicit security proof for this mode.
5. You can cache the state after consumption of the key improving performance for fixed keys (but reducing performance for single use keys). You can achieve a similar effect by padding the key to 512 bits (the block size) with $H(k\mathbin\|m)$, but implementations are unlikely to have support for that.

Properties 2 and 3 mean that the state collision attack does not apply even if you use some of Skein's additional features.

Unfortunately not every implementation includes the keyed Skein feature.

Conclusion

$H(k\mathbin\|m)$ is secure as MAC. But it's preferable to use the built in MAC mode where available, especially if you use any advanced Skein features such as trees.