15

While the one time pad seems obvious, I am not sure about Carter-Wegman-Style message auth. What they are talking about is a Carter-Wegman authentication method that uses a stream of random bits as a part of the process (just like a one time pad uses a stream of random bits to encrypt). Normally, when we implement CW, we use some almost universal (au) ...


11

Can the $AES_k(n)$ portion be simply replaced with $k \oplus n$? No, but you're close, it would be replaced with $k + n$, where $+$ is addition modulo $2^{128}$; then it becomes informational theoretic. Here's why: Poly1305 is based on a polynomial universal hash. This is a hash where we select a finite field $GF(p^i)$, select a private value $x \in GF(p^...


9

You didn't mention at what level you're hoping for, so I'll provide a few resources, and you can figure out which ones best meet your needs. UMAC: Fast and secure message authentication. John Black, Shai Halevi, Hugo Krawczyk, Ted Krovetz and Phillip Rogaway, CRYPTO 1999. (This research paper describes UMAC, a fast Carter-Wegman style hash. It also gives ...


8

A lot has changed recently in this area. Now the only ciphersuites Chrome considers non-obsolete (those that use AES-GCM or ChaCha+Poly1305), do use Carter-Wegman MACs. So, I would say that there is no disadvantage and that any low popularity has been just an artifact of historical decisions in standardization. Secure hashes were the first to be openly ...


8

A simplified* Carter-Wegman MAC could be defined as: $$ t=\sum_{i=1}^n {k_1^i m_i} + k_2 \pmod p$$ $p$ is a sufficently large prime (e.g. 256 bits). You must choose a new truly random $k_2$ uniformly from $0\leq k_2 <p$. It acts as a one-time-pad that prevents an attacker who sees the tag $t$ from learning anything about $k_1$. The polynomial $\sum {...


6

Tight security bound for elementary attack model: Well, here's the general theory; suppose the attacker had a valid message, MAC pair $(m_{1,...,l}, H)$ with $$H=s+\sum_{i=1}^l m_{(l+1-i)}\cdot {r}^i$$ and he selects a different pair $(m'_{1, ..., l}, H')$. His pair would authenticate if: $$H'=s+\sum_{i=1}^l m'_{(l+1-i)}\cdot {r}^i$$ or, if $r$ happens ...


5

You can use methods for hiding the output of the polynomial hash that don't require nonces, such as encrypting with a block-cipher of matching block-size or hashing it with a keyed hash (PRF). Not using a nonce reduces the security bounds (security decreases as the attacker sees more messages using the same key), makes it incompatible with stream ciphers ...


3

The MAC consists of the pair of the n-bit random value $r$ and the n-bit value $t = F(k_1,r) \oplus S(k_2,m)$. The length of $(r,t)$ is at least $2n$ bits, partly depending on how it is encoded. If the two values are simply concatenated, the total length is $2n$, as stipulated.


2

Let's consider a degenerate case. Suppose you're authenticating 16-byte messages, your DUF (better known as (almost) xor-universal hash) is $\text{AES}_k$, and your PRF is also $\text{AES}_k$. Then you have $$ \text{WC}(m, n) = \text{AES}_k(m) \oplus \text{AES}_k(n)\,, $$ where $m$ is your 16-byte message, and $n$ is a 16-byte nonce. This is obviously ...


2

So in this scenario the $k$, $r$ and $n$ are unique and truly random per message sent. […] Now given that this construction creates the Poly1305 tag: $$\textsf{Poly1305}_r(m, \textsf{AES}_k(n))$$ Can the $\textsf{AES}_k(n)$ portion be simply replaced with $k \oplus n$? Yes, but it's still needlessly complicated. As long as each 128-bit key $k$ is ...


2

No, it is not information-theoretically secure as a MAC. Poly1305-AES, like GHASH and a few other MACs, is based on a construction due to Carter and Wegman which does meet information-theoretic security for a single message. Replacing $\text{AES}_k(n)$ with a true one-time pad might work, but seems unnecessary. As long as the number of messages ...


2

How about GMAC? It's a Carter-Wegman MAC that meets the requirements of being fast to compute, and parallelizable. In addition, it can be securely updated, that is, given a long message, you can compute the MAC of a modified version of that message faster than recomputing the entire MAC. For example, suppose you have a message/nonce/tag triple of $(N, M, T)...


1

If I understand your proposal, you are suggesting to modify GCM by not using a fixed secret $H$, but instead you're making it a secret function of the nonce $f_{key}(nonce)$. If so, I don't believe that actually improves security. For attacks on GCM integrity, the attacker needs to recover the value of $H$. Now, because of how we xor in a nonce-dependent ...


1

Is this a better GCM? Not really. You can derive an independent GHASH key for each message instead of using the same GHASH key for many messages as AES-GCM does. It won't reduce security. It's costlier without hardware support: you can't reuse the same GHASH lookup table to quickly leak secrets through timing side channelsauthenticate multiple messages. ...


Only top voted, non community-wiki answers of a minimum length are eligible