International Association for Cryptologic Research

International Association
for Cryptologic Research


Wonseok Choi


Improved Security Analysis for Nonce-based Enhanced Hash-then-Mask MACs 📺
In this paper, we prove that the nonce-based enhanced hash-then-mask MAC (nEHtM) is secure up to 2^{3n/4} MAC queries and 2^n verification queries (ignoring logarithmic factors) as long as the number of faulty queries \mu is below 2^{3n/8}, significantly improving the previous bound by Dutta et al. Even when \mu goes beyond 2^{3n/8}, nEHtM enjoys graceful degradation of security. The second result is to prove the security of PRF-based nEHtM; when nEHtM is based on an n-to-s bit random function for a fixed size s such that 1 <= s <= n, it is proved to be secure up to any number of MAC queries and 2^s verification queries, if (1) s = n and \mu < 2^{n/2} or (2) n/2 < s < 2^{n-s} and \mu < max{2^{s/2}, 2^{n-s}}, or (3) s <= n/2 and \mu < 2^{n/2}. This result leads to the security proof of truncated nEHtM that returns only s bits of the original tag since a truncated permutation can be seen as a pseudorandom function. In particular, when s <= 2n/3, the truncated nEHtM is secure up to 2^{n - s/2} MAC queries and 2^s verification queries as long as \mu < min{2^{n/2}, 2^{n-s}}. For example, when s = n/2 (resp. s = n/4), the truncated nEHtM is secure up to 2^{3n/4} (resp. 2^{7n/8}) MAC queries. So truncation might provide better provable security than the original nEHtM with respect to the number of MAC queries.
Highly Secure Nonce-based MACs from the Sum of Tweakable Block Ciphers
Tweakable block ciphers (TBCs) have proven highly useful to boost the security guarantees of authentication schemes. In 2017, Cogliati et al. proposed two MACs combining TBC and universal hash functions: a nonce-based MAC called NaT and a deterministic MAC called HaT. While both constructions provide high security, their properties are complementary: NaT is almost fully secure when nonces are respected (i.e., n-bit security, where n is the block size of the TBC, and no security degradation in terms of the number of MAC queries when nonces are unique), while its security degrades gracefully to the birthday bound (n/2 bits) when nonces are misused. HaT has n-bit security and can be used naturally as a nonce-based MAC when a message contains a nonce. However, it does not have full security even if nonces are unique.This work proposes two highly secure and efficient MACs to fill the gap: NaT2 and eHaT. Both provide (almost) full security if nonces are unique and more than n/2-bit security when nonces can repeat. Based on NaT and HaT, we aim at achieving these properties in a modular approach. Our first proposal, Nonce-as-Tweak2 (NaT2), is the sum of two NaT instances. Our second proposal, enhanced Hash-as-Tweak (eHaT), extends HaT by adding the output of an additional nonce-depending call to the TBC and prepending nonce to the message. Despite the conceptual simplicity, the security proofs are involved. For NaT2 in particular, we rely on the recent proof framework for Double-block Hash-then-Sum by Kim et al. from Eurocrypt 2020.
Indifferentiability of Truncated Random Permutations
One of natural ways of constructing a pseudorandom function from a pseudorandom permutation is to simply truncate the output of the permutation. When n is the permutation size and m is the number of truncated bits, the resulting construction is known to be indistinguishable from a random function up to $$2^{{n+m}\over 2}$$ queries, which is tight.In this paper, we study the indifferentiability of a truncated random permutation where a fixed prefix is prepended to the inputs. We prove that this construction is (regularly) indifferentiable from a public random function up to $$\min \{2^{{n+m}\over 3}, 2^{m}, 2^\ell \}$$ queries, while it is publicly indifferentiable up to $$\min \{ \max \{2^{{n+m}\over 3}, 2^{n \over 2}\}, 2^\ell \}$$ queries, where $$\ell $$ is the size of the fixed prefix. Furthermore, the regular indifferentiability bound is proved to be tight when $$m+\ell \ll n$$.Our results significantly improve upon the previous bound of $$\min \{ 2^{m \over 2}, 2^\ell \}$$ given by Dodis et al. (FSE 2009), allowing us to construct, for instance, an $$\frac{n}{2}$$-to-$$\frac{n}{2}$$ bit random function that makes a single call to an n-bit permutation, achieving $$\frac{n}{2}$$-bit security.