# Is there any existing analysis for this construction to turn a tweakable blockcipher into a PRF?

I'm basically looking at this construction to turn a tweakable blockcipher $E_c(x)$ taking a key $k$, nonce $n$, counter $c$ (forming tweak $t = c||n$) and an input $x$ into a PRF on an arbitrary-length message $M$ that has $m$ blocks. Without further ado:

$$tag = E_0(E_1(M_1) \oplus \dots \oplus E_{m-1}(M_{m-1}) \oplus M_{m} \oplus E_{\ell + |M_m|}(0) \oplus E_{\lambda + |M_m|}(0))$$

$l$ is a constant larger than any legal value for $m$. $\lambda$ is larger than any legal value for $l + |M_m|$. $|M_m|$ is the length of the final block, and the XOR of the last two elements $M_{m} \oplus E_{\ell + |M_m|}(0)$ is truncated to $|M_m|$ bytes. $E_{\lambda + |M_m|}(0)$ is not truncated.

The closest to this construction what I found is the authentication part of OCB3 mode defined in terms of the tweakable blockcipher. How the last block is handled however is quite different.

-
Where is this construction from? – pg1989 Sep 24 '13 at 6:23
@pg1989 From my own paper, not quite ready for release. A pre-preprint is available here. – orlp Sep 24 '13 at 21:37
@D.W. Sorry, I think I failed to mention that the nonce is an implied argument to $E$. I left it out of the notation to prevent exploding it even more. – orlp Sep 25 '13 at 0:24
@D.W. What I originally called tweak in my post could better be called a counter. The nonce in my post really is just that: a number passed to the construction known to used once and once only. You can see $E^t_k(x)$ as a tweakable blockcipher taking tweak $t = counter||nonce$, key $k$, plaintext $x$ and returning the encrypted ciphertext. – orlp Sep 25 '13 at 0:33
Got it. Sounds like you should either omit the nonce from the question, or edit the question to explain this business more clearly. (Incidentally, this construction is going to impose some unfortunate limitations on how people can choose the nonce. If your block cipher admits a 128-bit tweak, and you want to encrypt messages up to $2^{40}$ blocks long, then you're only left with 88 bits for the nonce. In that case, it's not safe to generate nonces randomly: after $2^{44}$ nonces, by the birthday paradox, there's a good chance some nonce will be repeated. A bit painful.) – D.W. Sep 25 '13 at 0:42

I don't have a proof myself, but here's how you could analyze this / prove it secure yourself, if you want to have a go.

Your construction is basically $F(M) = E_0(G(M))$, where $G(M) = E_1(M_1) \oplus \dots \oplus E_{\lambda+|M_m|}(0)$ (that long thing defined in the question). To prove this secure, it suffices to prove the following:

1. The tweak values used in computing $G(M)$ are never $0$.

2. It is highly unlikely that the attacker can find a "collision". In other words, say that two messages $M,M'$ form a "collision" if $G(M)=G(M')$. Consider an (adaptive) attacker with an oracle for $F$, and let $M^1,\dots,M^q$ denote the $q$ messages that the attacker queries its oracle on. Let $\mathsf{BAD}$ denote the event that there exists some $i,j$ with $i\ne j$ and $G(M^i)=G(M^j)$. If you can prove that $\Pr[\mathsf{BAD}]$ is negligible, then you are home-free. That's because $E_0(Y^1),\dots,E_0(Y^q)$ will be pseudorandom if $Y^1,\dots,Y^q$ are all distinct.

The first condition should be easy to establish, as long as you put appropriate bounds on the length of the message to ensure that $l+|M_m|$ and $\lambda+|M_m|$ never wrap around to become equal to $0$.

You will have to analyze the second condition carefully. It looks like you might be able to establish that the second condition holds through some sort of case analysis, but that looks too tedious for me to do it -- so I'm going to leave that to you to establish.

Other comments. I don't understand why you have $E_{l+|M_m|}(0)$ in the xor; that looks pointless to me. I don't understand why you treat $M_m$ differently (premature optimization?). I don't understand why you don't just use some existing construction, like PMAC.

If you're going to invent something new, the following seems cleaner and easier to analyze:

$$F(M) = E_0(E_1(M_1) \oplus E_2(M_2) \oplus \cdots \oplus E_m(M_m) \oplus E_\lambda(\text{length}(M))),$$

where $\lambda$ is a constant chosen to be larger than any possible value of $m$, and where $M_m$ is padded with zeros (say) deterministically.

Related work. I suggest you make sure ythat you read the following papers:

-
I carefully designed the entire thing to make sure that every combination of tweak + nonce will always be unique, effectively creating an unique permutation for each message block. Note that the nonce is an implied argument for $E$, otherwise the notation would become too bulky. – orlp Sep 25 '13 at 0:09
To reply to your concerns on $E_{\ell + |M_m|}(0)$, the different treating for $M_m$ and why I chose a different construction from an existing one I suggest you to take a look at my (unfinished, work-in-progress) pre-preprint of my paper. The whole point of this is to combine this MAC with similar encryption allowing you to either run the combination in one pass or allow for verification in half the time of decryption. I'm deliberately being quite bold and innovative here - this is for a CAESAR submission. – orlp Sep 25 '13 at 0:22
@nightcracker, (regarding your first comment:) yup, I understand that. I don't think that contradicts anything in my answer. I think my answer remains valid.... If I've missed some implication or connection or inference, you might need to spell it out, as I'm not seeing it. – D.W. Sep 25 '13 at 0:25
@nightcracker, sorry, I probably won't have time to look at the pre-print soon. Apologies about that. The alternatives that I suggest also allow for one-pass processing of a message in parallel with encryption. (On the other hand, if you want to share the same key for both the MAC and the encryption, that's a-whole-nother level of trickiness. At that point you really need an extremely careful security proof, and not just a handwavy sketch, because it is so easy to go awry. I would not trust any construction that reused the same key for both purposes without a super-detailed proof.) – D.W. Sep 25 '13 at 0:27
Yes, the situation at hand however is even worse than simple key-sharing :) My idea in short is using the midstate (the inner state after $n/2$ rounds) of the blockcipher as input for the MAC, where the MAC is just an encrypted XOR of midstate blocks. The special-case for the last block is to allow an optimal-length ciphertext while still allowing half-time MAC verification and defeating length extension attacks securely. The advantage of this scheme is that you can run the entire thing one-pass, or two-pass with verification in half the time of decryption. – orlp Sep 25 '13 at 0:37