# Is tweakable block-cipher based on the Merkle-Damgård construction secure if $F$ is a PRP

Assume $$F$$ is a pseudo-random permutation (PRP) then the tweakable block-cipher based on the Merkle-Damgård construction (take this as the way I understand, here is the equation):

$$F_k[t](m) := F_{F_k(t)}(m)$$

is a secure tweakable block cipher. This is marked with two stars in my notes.

First question: is it right or wrong?

Second question (if it is right): will a standard argument - that distinguishes the real world from the ideal world - work?

• Minematsu (Section 5) showed this is secure up to $2^{n/2}$ queries for an $n$-bit tweak. – Samuel Neves Dec 27 '18 at 17:12
• @SamuelNeves care to turn that into an answer? – Maarten Bodewes Dec 28 '18 at 2:03

The idea is simple: the tweakable SPRP security of this construction, for $$q$$ queries distributed arbitrarily over $$t \le q$$ different tweaks, is the security of $$t$$ instances of $$F$$, plus the distance from the key derivation to uniformly distributed keys.
The security of $$t$$ instances of $$F$$ is otherwise known as multi-key or multi-user security, and we can bound it as $$t \cdot \mathbf{Adv}_{F}^{\text{sprp}}(\mathcal{D})$$, i.e., at most $$t$$ times the security of any single instance.
So we have $$\mathbf{Adv}^{\widetilde{\text{sprp}}}_{F}(\mathcal{D}) \le \mathbf{Adv}^{\text{prf}}_F(\mathcal{D'}) + t \cdot \mathbf{Adv}^{\text{sprp}}_{F}(\mathcal{D''}) \,,$$ for a distinguisher $$\mathcal{D'}$$ making $$t$$ queries and a distinguisher $$\mathcal{D''}$$ making at most $$q$$ queries. The first distance can be refined by the PRP-PRF switch, so we end up with $$\mathbf{Adv}^{\widetilde{\text{sprp}}}_{F}(\mathcal{D}) \le \frac{\binom{q}{2}}{2^n} + (t + 1) \cdot \mathbf{Adv}^{\text{sprp}}_{F}(\mathcal{D''}) \,.$$
So this construction is secure until approximately $$2^{n/2}$$ blocks are queried and, assuming a perfect block cipher with $$\mathbf{Adv}(\mathcal{D}) \le t/2^k$$, around $$2^k/t$$ evaluations.
Imagine for example a concrete instance of AES-128 where an attacker queries $$2^{64}$$ different tweaks $$x_i = \text{AES}_{\text{AES}_k(t_i)}(0)$$ then tries $$2^{64}$$ keys $$k_i$$ until $$\text{AES}_{k_j}(0) = x_i$$. Each attempt has success probability $$2^{64-128}$$, since there are $$2^{64}$$ distinct keys. Then, $$\text{AES}_{\text{AES}_k(t_i)}(1)$$ must also be equal to $$\text{AES}_{k_j}(1)$$.