Combining Multiple Tagging Algorithms for Keyed Message Authentication (Draft)

Abstract

We propose a method for combining multiple independent tagging (MAC) algorithms to produce a tag whose length is independent of the number of algorithms used, and whose resistance to forgery is at least as strong as the strongest tagging algorithm used.

This is a draft, which describes the scheme without proving its security.

Summary

Suppose we are given four hash functions, A, B, C, and D, such that one of these functions is collision resistant, but we do not know which one. Our goal is to use these functions to construct a keyed MAC that is also collision resistant, even if the other functions are under the complete control of an adversary.

Let A(k,m) be a keyed MAC, which takes a security parameter k and a message m and outputs a fixed-length string of length l. Let $B(\cdot, \cdot)$ be an arbitrary function under the control of an adversary, with the only constraint being that the function must output a fixed-length string of length l. Let $\oplus$ denote the bitwise exclusive-or (XOR) operation.

We propose a new function T, which takes two security parameters, k₁ and k₂, and a message m, and outputs a fixed-length string of length l:

$\mathcal{T}(k_1, k_2, m) = A(k_1, m) \oplus B(k_2, m)$

Download

61kB PDF

Timestamps

This paper was published on March 8, 2006, and has been timestamped by the following entities:

Timestamp 1: I.T. Consultancy Limited
Timestamp 2: DigiStamp Inc.