# collision resistance with added permutation

Suppose we have an $$n$$ bit ciphertext $$c$$ protected by a $$k$$ bit $$MAC$$, with $$k < n$$. Generally, we expect collisions after $$O(2^{k/2})$$ ciphertext/MAC pairs are seen.

Consider the following modifcation:

1. Adversary chooses $$m \in \{0, 1\}^n$$ and sends to oracle.
2. Oracle sends back $$\sigma((c) || MAC(c))$$, where $$c=E(m)$$ is a randomized encryption, and $$\sigma$$ is a permutation on $$n+k$$ bits. $$\sigma$$ remains unknown to the adversary.

Suppose $$\sigma$$ stays constant. It seems that we either attack the MAC/Encryption, or figure out the permutation. If the MAC and Encryption are perfect, then I don't see how we can find the MAC bits: any k element subset of the n+k bits will have the same birthday paradox probability of collisions. In fact, if we take $$2^k + 1$$ messages, the pigeonhole principle gives collisions to all subsets.

It seems our only help is if the MAC/Encryption has statistical biases that we can detect among the $$O(2^{k/2})$$ messages, but this seems that we must analyze all message k bit projections, which may be huge. Can we do better?

If we can't do better, what is the drawback of such a scheme? Is it impractical to have the hidden permutation be a shared secret? What about a set of such permutations?

Thanks

• "Generally, we expect collisions after $O(2^{k/2})$ ciphertext/MAC pairs are seen."; what's the big deal about that? What weakness do you foresee from that? Why bring in $\sigma$ at all? Sep 6 '20 at 22:44
• @poncho I know normally you pick k large enough. I'm looking a a particular design where authors propose to reduce $k$, so birthday collisions become realistic, but they want to argue that $\sigma$ makes it impossible to recognize the collisions.
– andy
Sep 6 '20 at 23:46
• Again, what security property is broken if you find a collision; that is, two different messages that MAC to the same value? Sep 7 '20 at 2:03
• @poncho I don’t know why the authors picked a permutation, but my guess is this. For some MAC constructions, like crypto.stackexchange.com/questions/15542/…, collisions help with forgeries. So I guess they want to avoid making this cheaper if they reduce MAC output size, so they add a permutation.
– andy
Sep 8 '20 at 14:37
• I have no ideas what authors you're referring to, but (IMHO) if the problem is "with this particular MAC design, truncating the MAC leads to weakness", my suggestion would be "use a different MAC design that retains its security with truncated MACs". Note that Ferguson et al was referring to MACs with $n$ bits internal state having $O(2^{n/2})$ security (which is debatable), not $k$ bits of truncated output. Sep 8 '20 at 14:50

If the permutation is a shared secret, I don't see how that's different from normal HMAC; in the sense that you can't find a collision unless you know the key, the amount of permutations would be too many to calculate; but HMAC has those same cryptographic properties, even for a less-than-ideal hashing algorithm.

### Update:

Here I explain the details of the number of possible permutations of the input bits (fun fact: this calculation actually comes into play when designing block ciphers). The issue is, while the number of ways you could permute the bits is extraordinarily high, the number of possible states will be upper-bounded at $$2^n$$ for $$n$$ bits. For an $$m P n$$ case (you select $$n$$ bits from set of bits $$M$$) you will be bounded by the number of possible $$M$$, as well as the possible $$N$$, making $$2^n$$ still your upper limit.

You cannot exceed the security provided by a normal $$2^n$$ bit hash, you can only match it with more permutation. Since any decent hashing algorithm already does this (and more), you end up with no change in your level of security. We're comparing internal states with input/output possibilities, and the input/output possibilities will always cap your security level. For this reason, I fail to see how it is different from a normal cryptographic hash.

• Actually, the permutation he refers to appears to be a permutation of the bits (e.g. "move bit 0 to bit 19, etc), not a more general "wide block cipher". Sep 8 '20 at 16:13
• I am aware; but the algorithm performs the same way in either case, just with a different search space. If a wide block cipher uses the number of possible output states ($2^k$) as its base for collision resistance, merely shuffling the bits would use the number of permutations of $k$ bits. The search space changes but the fundamental properties stay the same. Sep 8 '20 at 16:20
• I cover the math for identifying the possible permutations in more detail here. Sep 8 '20 at 16:23
• @Serpent27 Where is this fun fact covered in detail? schneier's book?
– andy
Sep 8 '20 at 19:28
• The calculation comes from the definition of an "ideal block cipher"... If I have a so-called ideal encryption algorithm, I should be able to get every possible plaintext-ciphertext mapping, depending on the key. The number of possible mappings is defined by the number of possible $n$-bit states, where $n$ is the block-size. I'd be happy to answer in more detail if you ask it as a separate question, or you can read about it here. Sep 8 '20 at 19:35