Assume a message protocol whereby one time pad messages are authenticated with a Carter Wegman type hash on the ciphertext, or some similar construct utilizing a unique authentication key per message.

Since this is a OTP system, there is a store of key material at both the sender's and receiver's ends. Some material is drawn to create the authentication tag and the message sent. It is then authenticated upon receipt by drawing the equivalent key material from the receiver's key store.

What happens if fake messages are received? Does every failed authentication consume unique key material which is then discarded, maintaining information-theoretic security? Or is the key material reused until a correctly authenticated message is received?

To be clear (following comments), I'm specifically looking at the inbound authentication process for fake messages. Not at the sending node. If a fake message is received which fails the authentication process, should the entropy used for the C-R tag test be discarded? Or should it be reused until a valid message is received?

You see my concern; having the phrases "key material" and "reused" in a unique key per message setting.

  • 1
    $\begingroup$ I think you want either "What should happen if fake messages are received?", or "assuming the receiver disregards messages that do not authenticate and reuses the corresponding key material until one message authenticates, to what degree is security jeopardized?". In the other hypothesis (key material never reused), how sender and receiver agree on key material used needs to be considered. I suggest adding the Carter-Wegman hash is on ciphertext. $\endgroup$
    – fgrieu
    Mar 2, 2023 at 14:02
  • $\begingroup$ @fgrieu Err, is this not clear cut then? I can't really follow the C-W security proof, but I imagined that the key handing would be an integral part of the proof, just as in OTPs. $\endgroup$
    – Paul Uszak
    Mar 2, 2023 at 14:31
  • $\begingroup$ If the authentication tag is $k$-bit, in $s$ submissions, adversaries have probability at least $1-{(1-2^{-k})}^s\approx s\,2^{-k}$ to get thru, if the authentication key is not reused. If the key is reused, they can get some tiny extra advantage, and it's worth asking what exactly, as you do. $\endgroup$
    – fgrieu
    Mar 2, 2023 at 14:44
  • 1
    $\begingroup$ @fgrieu: actually, it's more complicated than that. Some Carter-Wegman hashes have a $> 2^{-k}$ probability of allowing a forgery, thus raising the $s$-time success probability (these hashes have other advantages, such as using a fixed amount of key to authenticate, independent of the message length, that makes them attractive). $\endgroup$
    – poncho
    Mar 2, 2023 at 16:06

1 Answer 1


The Carter–Wegman system of authenticating multiple messages works as follows:

  • Sender and receiver agree in advance on a key $(f, (b_1, \dotsc, b_n))$ to authenticate a sequence of $n$ messages.

    $f$ is a random choice of a function from messages to hash values in a universal hash family, and $b_1, \dotsc, b_n$ are uniform random hash values that serve as one-time pads. Hash values can be added and subtracted (e.g., mod $2^{128}$, or with xor).

  • Messages are sent in order or otherwise identified with their message number. For example, the number $i$ may be affixed to the message $m_i$, or the messages may be placed in numbered mailboxes.

  • When the sender wants to send the $i^{\mathit{th}}$ message $m_i$, they affix the authentication tag $t_i = f(m_i) + b_i$ and send $(m_i, t_i)$. They will reuse $f$, but never again reuse $b_i$.

  • When receiver receives a pair $(m'_i, t'_i)$ alleged to be the $i^{\mathit{th}}$ authenticated message, they accept it as genuine only if $$t'_i = f(m'_i) + b_i,$$ after which they will never again reuse $b_i$.

    Otherwise, they reject it as a forgery. Next time the receiver receives pairs $(m''_i, t''_i), (m'''_i, t'''_i), \dotsc$, alleged to be the $i^{\mathit{th}}$ authenticated message, they recompute the same equation with the same $b_i$, and continue to reuse it until they accept a message.

    Of course, for two different message numbers $i \ne j$ (or two different message mailboxes), the receiver will use the appropriate independent $b_i$ and $b_j$ pads.

In other words, the sender discards the one-time pad material $b_i$ after sending each message. The receiver discards the one-time pad material $b_i$ only after accepting an alleged $i^{\mathit{th}}$ message as genuine, not after merely receiving an alleged message which may be a forgery.

Of course, if $(m'_i, t'_i) = (m_i, t_i)$, then the receiver will correctly accept the sender's message. But if $m'_i \ne m_i$ because $m'_i$ is a forgery attempt, the probability that the receiver accepts it is small, bounded by the largest value of $$\Pr[f(x) = h \mathrel\vert f(y) = k]$$ for all $x \ne y, h, k$ over random choices $f$ in a universal hash family—even if the forger knows all the legitimate authenticated messages $(m_1, t_1), \dotsc, (m_n, t_n)$, and even if the messages are all cleartext and chosen by the forger.

Actually it is bounded by $\Pr[f(x) - f(y) = h]$ for all $x, y, h$ over random choices of $f$, but Carter and Wegman didn't realize they could use this weaker property. In typical universal hash families like GHASH and Poly1305,* this probability is below $L/2^{100}$, where $L$ is the maximum length of a message (in some appropriate units) that the receiver will accept.

* Poly1305 was introduced in an instance of the Carter–Wegman authentication system called Poly1305-AES, but today it is very seldom used in the Carter–Wegman system—almost all use of it is in the ChaCha/Poly1305 authenticated cipher, which doesn't follow the Carter–Wegman system at all.

  • $\begingroup$ Welcome Jark :-) So. If a recipient has a limited store of OTP material, it cannot be depleted by spamming him with many fake messages? Only received authentic messages consume the recipient's entropy? $\endgroup$
    – Paul Uszak
    Mar 4, 2023 at 12:50
  • $\begingroup$ That's correct. $\endgroup$ Mar 4, 2023 at 12:51
  • $\begingroup$ Not a bad start... $\endgroup$
    – Paul Uszak
    Mar 4, 2023 at 12:53

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.