On the security margin of MAC striping

• A scheme to reduce the message overhead when authenticating short messages is cryptanalyzed.

MAC striping intermixes a payload with its authentication tag, placing the bits used for message authentication in positions derived from a secret key. The use of MAC striping has been suggested to authenticate encrypted payloads using short tags. For an idealized MAC scheme, the probability of a selective forgery has been estimated as (ℓ+mm)−1⋅2−m, when utilizing MAC striping with ℓ-bit payloads and m  -bit tags. We show that this estimate is too optimistic. For m≤ℓm≤ℓ and any payload, we achieve a selective forgery with probability ≥(ℓ+mm)−1, and usually many orders of magnitude more than that.