0
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ "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? $\endgroup$
    – poncho
    Commented Sep 6, 2020 at 22:44
  • $\begingroup$ @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. $\endgroup$
    – andy
    Commented Sep 6, 2020 at 23:46
  • 1
    $\begingroup$ Again, what security property is broken if you find a collision; that is, two different messages that MAC to the same value? $\endgroup$
    – poncho
    Commented Sep 7, 2020 at 2:03
  • $\begingroup$ @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. $\endgroup$
    – andy
    Commented Sep 8, 2020 at 14:37
  • $\begingroup$ 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. $\endgroup$
    – poncho
    Commented Sep 8, 2020 at 14:50

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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". $\endgroup$
    – poncho
    Commented Sep 8, 2020 at 16:13
  • $\begingroup$ 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. $\endgroup$
    – Serpent27
    Commented Sep 8, 2020 at 16:20
  • $\begingroup$ I cover the math for identifying the possible permutations in more detail here. $\endgroup$
    – Serpent27
    Commented Sep 8, 2020 at 16:23
  • $\begingroup$ @Serpent27 Where is this fun fact covered in detail? schneier's book? $\endgroup$
    – andy
    Commented Sep 8, 2020 at 19:28
  • $\begingroup$ 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. $\endgroup$
    – Serpent27
    Commented Sep 8, 2020 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.