## CryptoDB

### Mridul Nandi

#### Publications

**Year**

**Venue**

**Title**

2021

TOSC

Permutation Based EDM: An Inverse Free BBB Secure PRF
Abstract

In CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing PRF based on public permutations. They have proposed two beyond the birthday bound secure n-bit to n-bit PRF constructions, i.e., SoEM22 and SoKAC21, which are built on public permutations, where n is the size of the permutation. However, both of their constructions require two independent instances of public permutations. In FSE 2020, Chakraborti et al. have proposed a single public permutation based n-bit to n-bit beyond the birthday bound secure PRF, which they refer to as PDMMAC. Although the construction is minimal in the number of permutations, it requires the inverse call of its underlying permutation in their design. Coming up with a beyond the birthday bound secure public permutation based n-bit to n-bit PRF with a single permutation and two forward calls was left as an open problem in their paper. In this work, we propose pEDM, a single permutation based n-bit to n-bit PRF with two calls that do not require invertibility of the permutation. We have shown that our construction is secured against all adaptive information-theoretic distinguishers that make roughly up to 22n/3 construction and primitive queries. Moreover, we have also shown a matching attack with similar query complexity that establishes the tightness of our security bound.

2021

TOSC

On Length Independent Security Bounds for the PMAC Family
Abstract

At FSE 2017, Gaži et al. demonstrated a pseudorandom function (PRF) distinguisher (Gaži et al., ToSC 2016(2)) on PMAC with Ω(lq2/2n) advantage, where q, l, and n, denote the number of queries, maximum permissible query length (in terms of n-bit blocks), and block size of the underlying block cipher. This, in combination with the upper bounds of Ο(lq2/2n) (Minematsu and Matsushima, FSE 2007) and Ο(qσ/2n) (Nandi and Mandal, J. Mathematical Cryptology 2008(2)), resolved the long-standing problem of exact security of PMAC. Gaži et al. also showed that the dependency on l can be dropped (i.e. O(q2/2n) bound up to l ≤ 2n/2) for a simplified version of PMAC, called sPMAC, by replacing the Gray code-based masking in PMAC with any 4-wise independent universal hash-based masking. Recently, Naito proposed another variant of PMAC with two powering-up maskings (Naito, ToSC 2019(2)) that achieves l-free bound of O(q2/2n), provided l ≤ 2n/2. In this work, we first identify a flaw in the analysis of Naito’s PMAC variant that invalidates the security proof. Apparently, the flaw is not easy to fix under the existing proof setup. We then formulate an equivalent problem which must be solved in order to achieve l-free security bounds for this variant. Second, we show that sPMAC achieves O(q2/2n) bound for a weaker notion of universality as compared to the earlier condition of 4-wise independence. Third, we analyze the security of PMAC1 (a popular variant of PMAC) with a simple modification in the linear combination of block cipher outputs. We show that this simple modification of PMAC1 has tight security O(q2/2n) provided l ≤ 2n/4. Even if l < 2n/4, we still achieve same tight bound as long as total number of blocks in all queries is less than 22n/3.

2020

TOSC

INT-RUP Secure Lightweight Parallel AE Modes
📺
Abstract

Owing to the growing demand for lightweight cryptographic solutions, NIST has initiated a standardization process for lightweight cryptographic algorithms. Specific to authenticated encryption (AE), the NIST draft demands that the scheme should have one primary member that has key length of 128 bits, and it should be secure for at least 250 − 1 byte queries and 2112 computations. Popular (lightweight) modes, such as OCB, OTR, CLOC, SILC, JAMBU, COFB, SAEB, Beetle, SUNDAE etc., require at least 128-bit primitives to meet the NIST criteria, as all of them are just birthday bound secure. Furthermore, most of them are sequential, and they either use a two pass mode or they do not offer any security when the adversary has access to unverified plaintext (RUP model). In this paper, we propose two new designs for lightweight AE modes, called LOCUS and LOTUS, structurally similar to OCB and OTR, respectively. These modes achieve notably higher AE security bounds with lighter primitives (only a 64-bit tweakable block cipher). Especially, they satisfy the NIST requirements: secure as long as the data complexity is less than 264 bytes and time complexity is less than 2128, even when instantiated with a primitive with 64-bit block and 128-bit key. Both these modes are fully parallelizable and provide full integrity security under the RUP model. We use TweGIFT-64[4,16,16,4] (also referred as TweGIFT-64), a tweakable variant of the GIFT block cipher, to instantiate our AE modes. TweGIFT-64-LOCUS and TweGIFT-64-LOTUS are significantly light in hardware implementation. To justify, we provide our FPGA based implementation results, which demonstrate that TweGIFT-64-LOCUS consumes only 257 slices and 690 LUTs, while TweGIFT-64-LOTUS consumes only 255 slices and 664 LUTs.

2020

TOSC

Release of Unverified Plaintext: Tight Unified Model and Application to ANYDAE
📺
Abstract

Authenticated encryption schemes are usually expected to offer confidentiality and authenticity. In case of release of unverified plaintext (RUP), an adversary gets separated access to the decryption and verification functionality, and has more power in breaking the scheme. Andreeva et al. (ASIACRYPT 2014) formalized RUP security using plaintext awareness, informally meaning that the decryption functionality gives no extra power in breaking confidentiality, and INT-RUP security, covering authenticity in case of RUP. We describe a single, unified model, called AERUP security, that ties together these notions: we prove that an authenticated encryption scheme is AERUP secure if and only if it is conventionally secure, plaintext aware, and INT-RUP secure. We next present ANYDAE, a generalization of SUNDAE of Banik et al. (ToSC 2018/3). ANYDAE is a lightweight deterministic scheme that is based on a block cipher with block size n and arbitrary mixing functions that all operate on an n-bit state. It is particularly efficient for short messages, it does not rely on a nonce, and it provides maximal robustness to a lack of secure state. Whereas SUNDAE is not secure under release of unverified plaintext (a fairly simple attack can be mounted in constant time), ANYDAE is. We make handy use of the AERUP security model to prove that ANYDAE achieves both conventional security as RUP security, provided that certain modest conditions on the mixing functions are met. We describe two simple instances, called MONDAE and TUESDAE, that conform to these conditions and that are competitive with SUNDAE, in terms of efficiency and optimality.

2020

EUROCRYPT

Mind the Composition: Birthday Bound Attacks on EWCDMD and SoKAC21
📺
Abstract

In an early version of CRYPTO'17, Mennink and Neves proposed \textsf{EWCDMD}, a dual of \textsf{EWCDM}, and showed $n$-bit security, where $n$ is the block size of the underlying block cipher. In CRYPTO'19, Chen et al. proposed permutation based design \textsf{SoKAC21} and showed $2n/3$-bit security, where $n$ is the input size of the underlying permutation. In this paper we show birthday bound attacks on \textsf{EWCDMD} and \textsf{SoKAC21}, invalidating their security claims. Both attacks exploit an inherent composition nature present in the constructions.
Motivated by the above two attacks exploiting the composition nature, we consider some generic relevant composition based constructions of ideal primitives
(possibly in the ideal permutation and random oracle model) and present birthday bound distinguishers for them.
In particular, we demonstrate a birthday bound distinguisher against (1) a secret random permutation followed by a public random function and (2) composition of two secret random functions.
Our distinguishers for \textsf{SoKAC21} and \textsf{EWCDMD} are direct consequences of (1) and (2) respectively.

2020

TOSC

ESTATE: A Lightweight and Low Energy Authenticated Encryption Mode
📺
Abstract

NIST has recently initiated a standardization project for efficient lightweight authenticated encryption schemes. SUNDAE, a candidate in this project, achieves optimal state size which results in low circuit overhead on top of the underlying block cipher. In addition, SUNDAE provides security in nonce-misuse scenario as well. However, in addition to the block cipher circuit, SUNDAE also requires some additional circuitry for multiplication by a primitive element. Further, it requires an additional block cipher invocation to create the starting state. In this paper, we propose a new lightweight and low energy authenticated encryption family, called ESTATE, that significantly improves the design of SUNDAE in terms of implementation costs (both hardware area and energy) and efficient processing of short messages. In particular, ESTATE does not require an additional multiplication circuit, and it reduces the number of block cipher calls by one. Moreover, it provides integrity security even under the release of unverified plaintext (or RUP) model. ESTATE is based on short-tweak tweakable block ciphers (or tBC, small ’t’ denotes short tweaks) and we instantiate it with two recently designed tBCs: TweAES and TweGIFT. We also propose a low latency variant of ESTATE, called sESTATE, that uses a round-reduced (6 rounds) variant of TweAES called TweAES-6. We provide comprehensive FPGA based hardware implementation for all the three instances. The implementation results depict that ESTATE_TweGIFT-128 (681 LUTs, 263 slices) consumes much lesser area as compared to SUNDAE_GIFT-128 (931 LUTs, 310 slices). When we moved to the AES variants, along with the area-efficiency (ESTATE_TweAES consumes 1901 LUTs, 602 slices while SUNDAE_AES-128 needs 1922 LUTs, 614 slices), we also achieve higher throughput for short messages (For 16-byte message, a throughput of 1251.10 and 945.36 Mbps for ESTATE_TweAES and SUNDAE_AES-128 respectively).

2020

TOSC

From Combined to Hybrid: Making Feedback-based AE even Smaller
📺
Abstract

In CHES 2017, Chakraborti et al. proposed COFB, a rate-1 sequential block cipher-based authenticated encryption (AE) with only 1.5n-bit state, where n denotes the block size. They used a novel approach, the so-called combined feedback, where each block cipher input has a combined effect of the previous block cipher output and the current plaintext block. In this paper, we first study the security of a general rate-1 feedback-based AE scheme in terms of its overall internal state size. For a large class of feedback functions, we show that the overlying AE scheme can be attacked in 2r queries if the internal state size is n + r bits for some r ≥ 0. This automatically shows that a birthday bound (i.e. 2n/2 queries) secure AE scheme must have at least 1.5n-bit state, whence COFB is almost-optimal (use 1.5n-bit state and provides security up to 2n/2/n queries). We propose a new feedback function, called the hybrid feedback or HyFB, which is a hybrid composition of plaintext and ciphertext feedbacks. HyFB has a key advantage of lower XOR counts over the combined feedback function. This essentially helps in reducing the hardware footprint. Based on HyFB we propose a new AE scheme, called HyENA, that achieves the state size, rate, and security of COFB. In addition, HyENA has significantly lower XOR counts as compared to COFB, whence it is expected to have a smaller implementation as compared to COFB.

2020

TOSC

On the Composition of Single-Keyed Tweakable Even-Mansour for Achieving BBB Security
📺
Abstract

Observing the growing popularity of random permutation (RP)-based designs (e.g, Sponge), Bart Mennink in CRYPTO 2019 has initiated an interesting research in the direction of RP-based pseudorandom functions (PRFs). Both are claimed to achieve beyond-the-birthday-bound (BBB) security of 2n/3 bits (n being the input block size in bits) but require two instances of RPs and can handle only oneblock inputs. In this work, we extend research in this direction by providing two new BBB-secure constructions by composing the tweakable Even-Mansour appropriately. Our first construction requires only one instance of an RP and requires only one key. Our second construction extends the first to a nonce-based Message Authentication Code (MAC) using a universal hash to deal with multi-block inputs. We show that the hash key can be derived from the original key when the underlying hash is the Poly hash. We provide matching attacks for both constructions to demonstrate the tightness of the proven security bounds.

2020

TOSC

On the Security of Sponge-type Authenticated Encryption Modes
📺
Abstract

The sponge duplex is a popular mode of operation for constructing authenticated encryption schemes. In fact, one can assess the popularity of this mode from the fact that around 25 out of the 56 round 1 submissions to the ongoing NIST lightweight cryptography (LwC) standardization process are based on this mode. Among these, 14 sponge-type constructions are selected for the second round consisting of 32 submissions. In this paper, we generalize the duplexing interface of the duplex mode, which we call Transform-then-Permute. It encompasses Beetle as well as a new sponge-type mode SpoC (both are round 2 submissions to NIST LwC). We show a tight security bound for Transform-then-Permute based on b-bit permutation, which reduces to finding an exact estimation of the expected number of multi-chains (defined in this paper). As a corollary of our general result, authenticated encryption advantage of Beetle and SpoC is about T(D+r2r)/2b where T, D and r denotes the number of offline queries (related to time complexity of the attack), number of construction queries (related to data complexity) and rate of the construction (related to efficiency). Previously the same bound has been proved for Beetle under the limitation that T << min{2r, 2b/2} (that compels to choose larger permutation with higher rate). In the context of NIST LwC requirement, SpoC based on 192-bit permutation achieves the desired security with 64-bit rate, which is not achieved by either duplex or Beetle (as per the previous analysis).

2020

ASIACRYPT

How to Build Optimally Secure PRFs Using Block Ciphers
📺
Abstract

In EUROCRYPT '96, Aiello and Venkatesan proposed two candidates for $ 2n $-bit to $ 2n $-bit pseudorandom functions (PRFs), called Benes and modified Benes (or mBenes), based on $ n $-bit to $ n $-bit PRFs. While Benes is known to be secure up to $ 2^n $ queries (Patarin, AFRICACRYPT '08), the security of mBenes has only been proved up to $ 2^{n(1-\epsilon)} $ queries for all $ \epsilon > 0 $ by Patarin and Montreuil in ICISC '05. In this work, we show that the composition of a $ 2n $-bit hash function with mBenes is a secure variable input length (VIL) PRF up to $ 2^{n-2} $ queries (given appropriate hash function bounds). We extend our analysis with block ciphers as the underlying primitive and obtain two optimally secure VIL PRFs using block ciphers. The first of these candidates requires $ 6 $ calls to the block cipher. The second candidate requires just $ 4 $ calls to the block cipher, but here the proof is based on Patarin's mirror theory. Further, we instantiate the hash function with a PMAC+/LightMAC+ like hash, to get six candidates for deterministic message authentication codes with optimal security.

2020

JOFC

Tight Security of Cascaded LRW2
Abstract

At CRYPTO ’12, Landecker et al. introduced the cascaded LRW2 (or CLRW2 ) construction and proved that it is a secure tweakable block cipher up to roughly $$ 2^{2n/3} $$ 2 2 n / 3 queries. Recently, Mennink has presented a distinguishing attack on CLRW2 in $$ 2n^{1/2}2^{3n/4} $$ 2 n 1 / 2 2 3 n / 4 queries. In the same paper, he discussed some non-trivial bottlenecks in proving tight security bound, i.e., security up to $$ 2^{3n/4} $$ 2 3 n / 4 queries. Subsequently, he proved security up to $$ 2^{3n/4} $$ 2 3 n / 4 queries for a variant of CLRW2 using 4-wise independent AXU assumption and the restriction that each tweak value occurs at most $$ 2^{n/4} $$ 2 n / 4 times. Moreover, his proof relies on a version of mirror theory which is yet to be publicly verified. In this paper, we resolve the bottlenecks in Mennink’s approach and prove that the original CLRW2 is indeed a secure tweakable block cipher up to roughly $$ 2^{3n/4} $$ 2 3 n / 4 queries. To do so, we develop two new tools: First, we give a probabilistic result that provides improved bound on the joint probability of some special collision events, and second, we present a variant of Patarin’s mirror theory in tweakable permutation settings with a self-contained and concrete proof. Both these results are of generic nature and can be of independent interests. To demonstrate the applicability of these tools, we also prove tight security up to roughly $$ 2^{3n/4} $$ 2 3 n / 4 queries for a variant of DbHtS , called DbHtS-p , that uses two independent universal hash functions.

2019

EUROCRYPT

Beyond Birthday Bound Secure MAC in Faulty Nonce Model
📺
Abstract

Encrypt-then-MAC (EtM) is a popular mode for authenticated encryption (AE). Unfortunately, almost all designs following the EtM paradigm, including the AE suites for TLS, are vulnerable against nonce misuse. A single repetition of the nonce value reveals the hash key, leading to a universal forgery attack. There are only two authenticated encryption schemes following the EtM paradigm which can resist nonce misuse attacks, the GCM-RUP (CRYPTO-17) and the $$\mathsf {GCM/2}^{+} $$ (INSCRYPT-12). However, they are secure only up to the birthday bound in the nonce respecting setting, resulting in a restriction on the data limit for a single key. In this paper we show that nEHtM, a nonce-based variant of EHtM (FSE-10) constructed using a block cipher, has a beyond birthday bound (BBB) unforgeable security that gracefully degrades under nonce misuse. We combine nEHtM with the CENC (FSE-06) mode of encryption using the EtM paradigm to realize a nonce-based AE, CWC+. CWC+ is very close (requiring only a few more xor operations) to the CWC AE scheme (FSE-04) and it not only provides BBB security but also gracefully degrading security on nonce misuse.

2019

JOFC

Blockcipher-Based Authenticated Encryption: How Small Can We Go?
Abstract

This paper presents a lightweight blockcipher-based authenticated encryption mode mainly focusing on minimizing the implementation size, i.e., hardware gates or working memory on software. The mode is called $$\textsf {COFB}$$COFB, for COmbined FeedBack. $$\textsf {COFB}$$COFB uses an n-bit blockcipher as the underlying primitive and relies on the use of a nonce for security. In addition to the state required for executing the underlying blockcipher, $$\textsf {COFB}$$COFB needs only n / 2 bits state as a mask. Till date, for all existing constructions in which masks have been applied, at least n bit masks have been used. Thus, we have shown the possibility of reducing the size of a mask without degrading the security level much. Moreover, it requires one blockcipher call to process one input block. We show $$\textsf {COFB}$$COFB is provably secure up to $$O(2^{n/2}/n)$$O(2n/2/n) queries which is almost up to the standard birthday bound. We first present an idealized mode $$\textsf {iCOFB}$$iCOFB along with the details of its provable security analysis. Next, we extend the construction to the practical mode COFB. We instantiate COFB with two 128-bit blockciphers, AES-128 and GIFT-128, and present their implementation results on FPGAs. We present two implementations, with and without CAESAR hardware API. When instantiated with AES-128 and implemented without CAESAR hardware API, COFB achieves only a few more than 1000 Look-Up-Tables (LUTs) while maintaining almost the same level of provable security as standard AES-based AE, such as GCM. When instantiated with GIFT-128, COFB performs much better in hardware area. It consumes less than 1000 LUTs while maintaining the same security level. However, when implemented with CAESAR hardware API, there are significant overheads both in hardware area and in throughput. COFB with AES-128 achieves about 1475 LUTs. COFB with GIFT-128 achieves a few more than 1000 LUTs. Though there are overheads, still both these figures show competitive implementation results compared to other authenticated encryption constructions.

2019

TOSC

DoveMAC: A TBC-based PRF with Smaller State, Full Security, and High Rate
📺
Abstract

Recent parallelizable message authentication codes (MACs) have demonstrated the benefit of tweakable block ciphers (TBCs) for authentication with high security guarantees. With ZMAC, Iwata et al. extended this line of research by showing that TBCs can simultaneously increase the number of message bits that are processed per primitive call. However, ZMAC and previous TBC-based MACs needed more memory than sequential constructions. While this aspect is less an issue on desktop processors, it can be unfavorable on resource-constrained platforms. In contrast, existing sequential MACs limit the number of message bits to the block length of the primitive n or below.This work proposes DoveMAC, a TBC-based PRF that reduces the memory of ZMAC-based MACs to 2n+ 2t+2k bits, where n is the state size, t the tweak length, and k the key length of the underlying primitive. DoveMAC provides (n+min(n+t))/2 bits of security, and processes n+t bits per primitive call. Our construction is the first sequential MAC that combines beyond-birthday-bound security with a rate above n bits per call. By reserving a single tweak bit for domain separation, we derive a single-key variant DoveMAC1k.

2018

EUROCRYPT

2018

TOSC

Revisiting Variable Output Length XOR Pseudorandom Function
Abstract

Let σ be some positive integer and C ⊆ {(i, j) : 1 ≤ i < j ≤ σ}. The theory behind finding a lower bound on the number of distinct blocks P1, . . . , Pσ ∈ {0, 1}n satisfying a set of linear equations {Pi ⊕Pj = ci,j : (i, j) ∈ C} for some ci,j ∈ {0, 1}n, is called mirror theory. Patarin introduced the mirror theory and provided a proof for this. However, the proof, even for a special class of equations, is complex and contains several non-trivial gaps. As an application of mirror theory, XORP[w] (known as XOR construction) returning (w−1) block output, is a pseudorandom function (PRF) for some parameter w, called width. The XOR construction can be seen as a basic structure of some encryption algorithms, e.g., the CENC encryption and the CHM authenticated encryption, proposed by Iwata in 2006. Due to potential application of XORP[w] and the nontrivial gaps in the proof of mirror theory, an alternative simpler analysis of PRF-security of XORP[w] would be much desired. Recently (in Crypto 2017) Dai et al. introduced a tool, called the χ2 method, for analyzing PRF-security. Using this tool, the authors have provided a proof of PRF-security of XORP[2] without relying on the mirror theory. In this paper, we resolve the general case; we apply the χ2 method to obtain a simpler security proof of XORP[w] for any w ≥ 2. For w = 2, we obtain a tighter bound for a wider range of parameters than that of Dai et al.. Moreover, we consider variable width construction XORP[∗] (in which the widths are chosen by adversaries adaptively), and also provide variable output length pseudorandom function (VOLPRF) security analysis for it. As an application of VOLPRF, we propose an authenticated encryption which is a simple variant of CHM or AES-GCM and provides much higher security than those at the cost of one extra blockcipher call for every message.

2018

CRYPTO

Bernstein Bound on WCS is Tight
📺
Abstract

In Eurocrypt 2018, Luykx and Preneel described hash-key-recovery and forgery attacks against polynomial hash based Wegman-Carter-Shoup (WCS) authenticators. Their attacks require
$$2^{n/2}$$
message-tag pairs and recover hash-key with probability about
$$1.34\, \times \, 2^{-n}$$
where n is the bit-size of the hash-key. Bernstein in Eurocrypt 2005 had provided an upper bound (known as Bernstein bound) of the maximum forgery advantages. The bound says that all adversaries making
$$O(2^{n/2})$$
queries of WCS can have maximum forgery advantage
$$O(2^{-n})$$
. So, Luykx and Preneel essentially analyze WCS in a range of query complexities where WCS is known to be perfectly secure. Here we revisit the bound and found that WCS remains secure against all adversaries making
$$q \ll \sqrt{n} \times 2^{n/2}$$
queries. So it would be meaningful to analyze adversaries with beyond birthday bound complexities.In this paper, we show that the Bernstein bound is tight by describing two attacks (one in the “chosen-plaintext model” and other in the “known-plaintext model”) which recover the hash-key (hence forges) with probability at leastbased on
$$\sqrt{n} \times 2^{n/2}$$
message-tag pairs. We also extend the forgery adversary to the Galois Counter Mode (or GCM). More precisely, we recover the hash-key of GCM with probability at least
$$\frac{1}{2}$$
based on only
$$\sqrt{\frac{n}{\ell }} \times 2^{n/2}$$
encryption queries, where
$$\ell $$
is the number of blocks present in encryption queries.

2018

CRYPTO

Generic Attacks Against Beyond-Birthday-Bound MACs
📺
Abstract

In this work, we study the security of several recent MAC constructions with provable security beyond the birthday bound. We consider block-cipher based constructions with a double-block internal state, such as SUM-ECBC, PMAC+, 3kf9, GCM-SIV2, and some variants (LightMAC+, 1kPMAC+). All these MACs have a security proof up to $$2^{2n/3}$$ queries, but there are no known attacks with less than $$2^{n}$$ queries.We describe a new cryptanalysis technique for double-block MACs based on finding quadruples of messages with four pairwise collisions in halves of the state. We show how to detect such quadruples in SUM-ECBC, PMAC+, 3kf9, GCM-SIV2 and their variants with $$\mathcal {O}(2^{3n/4})$$ queries, and how to build a forgery attack with the same query complexity. The time complexity of these attacks is above $$2^n$$, but it shows that the schemes do not reach full security in the information theoretic model. Surprisingly, our attack on LightMAC+ also invalidates a recent security proof by Naito.Moreover, we give a variant of the attack against SUM-ECBC and GCM-SIV2 with time and data complexity $$\tilde{\mathcal {O}}(2^{6n/7})$$. As far as we know, this is the first attack with complexity below $$2^n$$ against a deterministic beyond-birthday-bound secure MAC.As a side result, we also give a birthday attack against 1kf9, a single-key variant of 3kf9 that was withdrawn due to issues with the proof.

2018

CRYPTO

Encrypt or Decrypt? To Make a Single-Key Beyond Birthday Secure Nonce-Based MAC
📺
Abstract

At CRYPTO 2016, Cogliati and Seurin have proposed a highly secure nonce-based MAC called Encrypted Wegman-Carter with Davies-Meyer ($$\textsf {EWCDM}$$EWCDM) construction, as $$\textsf {E}_{K_2}\bigl (\textsf {E}_{K_1}(N)\oplus N\oplus \textsf {H}_{K_h}(M)\bigr )$$EK2(EK1(N)⊕N⊕HKh(M)) for a nonce N and a message M. This construction achieves roughly $$2^{2n/3}$$22n/3 bit MAC security with the assumption that $$\textsf {E}$$E is a PRP secure n-bit block cipher and $$\textsf {H}$$H is an almost xor universal n-bit hash function. In this paper we propose Decrypted Wegman-Carter with Davies-Meyer ($$\textsf {DWCDM}$$DWCDM) construction, which is structurally very similar to its predecessor $$\textsf {EWCDM}$$EWCDM except that the outer encryption call is replaced by decryption. The biggest advantage of $$\textsf {DWCDM}$$DWCDM is that we can make a truly single key MAC: the two block cipher calls can use the same block cipher key $$K=K_1=K_2$$K=K1=K2. Moreover, we can derive the hash key as $$K_h=\textsf {E}_K(1)$$Kh=EK(1), as long as $$|K_h|=n$$|Kh|=n. Whether we use encryption or decryption in the outer layer makes a huge difference; using the decryption instead enables us to apply an extended version of the mirror theory by Patarin to the security analysis of the construction. $$\textsf {DWCDM}$$DWCDM is secure beyond the birthday bound, roughly up to $$2^{2n/3}$$22n/3 MAC queries and $$2^n$$2n verification queries against nonce-respecting adversaries. $$\textsf {DWCDM}$$DWCDM remains secure up to $$2^{n/2}$$2n/2 MAC queries and $$2^n$$2n verification queries against nonce-misusing adversaries.

2018

TCHES

Beetle Family of Lightweight and Secure Authenticated Encryption Ciphers
📺
Abstract

This paper presents a lightweight, sponge-based authenticated encryption (AE) family called Beetle. When instantiated with the PHOTON permutation from CRYPTO 2011, Beetle achieves the smallest footprint—consuming only a few more than 600 LUTs on FPGA while maintaining 64-bit security. This figure is significantly smaller than all known lightweight AE candidates which consume more than 1,000 LUTs, including the latest COFB-AES from CHES 2017. In order to realize such small hardware implementation, we equip Beetle with an “extremely tight” bound of security. The trick is to use combined feedback to create a difference between the cipher text block and the rate part of the next feedback (in traditional sponge these two values are the same). Then we are able to show that Beetle is provably secure up to min{c − log r, b/2, r} bits, where b is the permutation size and r and c are parameters called rate and capacity, respectively. The tight security bound allows us to select the smallest security parameters, which in turn result in the smallest footprint.

2018

ASIACRYPT

Short Variable Length Domain Extenders with Beyond Birthday Bound Security
Abstract

Length doublers are cryptographic functions that transform an n-bit cryptographic primitive into an efficient and secure cipher that length-preservingly encrypts strings of length in $$[n,2n-1]$$. All currently known constructions are only proven secure up to the birthday bound, and for all but one construction this bound is known to be tight. We consider the remaining candidate, $$\mathrm {LDT}$$ by Chen et al. (ToSC 2017(3)), and prove that it achieves beyond the birthday bound security for the domain [n, 3n / 2). We generalize the construction to multiple rounds and demonstrate that by adding one more encryption layer to $$\mathrm {LDT} $$, beyond the birthday bound security can be achieved for all strings of length in $$[n,2n-1]$$: security up to around $$2^{2n/3}$$ for the encryption of strings close to n and security up to around $$2^{n}$$ for strings of length close to 2n. The security analysis of both schemes is performed in a modular manner through the introduction and analysis of a new concept called “harmonic permutation primitives.”

2018

ASIACRYPT

ZCZ – Achieving n-bit SPRP Security with a Minimal Number of Tweakable-Block-Cipher Calls
Abstract

Strong Pseudo-random Permutations (SPRPs) are important for various applications. In general, it is desirable to base an SPRP on a single-keyed primitive for minimizing the implementation costs. For constructions built on classical block ciphers, Nandi showed at ASIACRYPT’15 that at least two calls to the primitive per processed message block are required for SPRP security, assuming that all further operations are linear. The ongoing trend of using tweakable block ciphers as primitive has already led to MACs or encryption modes with high security and efficiency properties. Thus, three interesting research questions are hovering in the domain of SPRPs: (1) if and to which extent the bound of two calls per block can be reduced with a tweakable block cipher, (2) how concrete constructions could be realized, and (3) whether full n-bit security is achievable from primitives with n-bit state size.The present work addresses all three questions. Inspired by Iwata et al.’s ZHash proposal at CRYPTO’17, we propose the ZCZ (ZHash-Counter-ZHash) construction, a single-key variable-input-length SPRP based on a single tweakable block cipher whose tweak length is at least its state size. ZCZ possesses close to optimal properties with regards to both performance and security: not only does it require only asymptotically $$3\ell /2$$ calls to the primitive for $$\ell $$-block messages; we show that this figure is close to the minimum by an PRP distinguishing attack on any construction with tweak size of $$\tau = n$$ bits and fewer than $$(3\ell -1)/2$$ calls to the same primitive. Moreover, it provides optimal n-bit security for a primitive with n-bit state and tweak size.

2018

TOSC

Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF
📺
Abstract

SUM-ECBC (Yasuda, CT-RSA 2010) is the first beyond birthday bound (BBB) secure block cipher based deterministic MAC. After this work, some more BBB secure deterministic MACs have been proposed, namely PMAC_Plus (Yasuda, CRYPTO 2011), 3kf9 (Zhang et al., ASIACRYPT 2012) and LightMAC_Plus (Naito, ASIACRYPT 2017). In this paper, we have abstracted out the inherent design principle of all these BBB secure MACs and present a generic design paradigm to construct a BBB secure pseudo random function, namely Double-block Hash-then- Sum or in short (DbHtS). A DbHtS construction, as the name implies, computes a double block hash on the message and then sum the encrypted output of the two hash blocks. Our result renders that if the underlying hash function meets certain security requirements (namely cover-free and block-wise universal advantage is low), DbHtS construction provides 2n/3-bit security. We demonstrate the applicability of our result by instantiating all the existing beyond birthday secure deterministic MACs (e.g., SUM-ECBC, PMAC_Plus, 3kf9, LightMAC_Plus) as well as a simple two-keyed variant for each of them and some algebraic hash based constructions.

2017

TOSC

On The Exact Security of Message Authentication Using Pseudorandom Functions
Abstract

Traditionally, modes of Message Authentication Codes(MAC) such as Cipher Block Chaining (CBC) are instantiated using block ciphers or keyed Pseudo Random Permutations(PRP). However, one can also use domain preserving keyed Pseudo Random Functions(PRF) to instantiate MAC modes. The very first security proof of CBC-MAC [BKR00], essentially modeled the PRP as a PRF. Until now very little work has been done to investigate the difference between PRP vs PRF instantiations. Only known result is the rather loose folklore PRP-PRF transition of any PRP based security proof, which looses a factor of Ο( σ2/2n ) (domain of PRF/PRP is {0, 1}n and adversary makes σ many PRP/PRF calls in total). This loss is significant, considering the fact tight Θ( q2/2n ) security bounds have been known for PRP based EMAC and ECBC constructions (where q is the total number of adversary queries). In this work, we show for many variations of encrypted CBC MACs (i.e. EMAC, ECBC, FCBC, XCBC and TCBC), random function based instantiation has a security bound Ο( qσ/2n ). This is a significant improvement over the folklore PRP/PRF transition. We also show this bound is optimal by providing an attack against the underlying PRF based CBC construction. This shows for EMAC, ECBC and FCBC, PRP instantiations are substantially more secure than PRF instantiations. Where as, for XCBC and TMAC, PRP instantiations are at least as secure as PRF instantiations.

2017

TOSC

ZMAC+ - An Efficient Variable-output-length Variant of ZMAC
Abstract

There is an ongoing trend in the symmetric-key cryptographic community to construct highly secure modes and message authentication codes based on tweakable block ciphers (TBCs). Recent constructions, such as Cogliati et al.’s HaT or Iwata et al.’s ZMAC, employ both the n-bit plaintext and the t-bit tweak simultaneously for higher performance. This work revisits ZMAC, and proposes a simpler alternative finalization based on HaT. As a result, we propose HtTBC, and call its instantiation with ZHash as a hash function ZMAC+. Compared to HaT, ZMAC+ (1) requires only a single key and a single primitive. Compared to ZMAC, our construction (2) allows variable, per-query parametrizable output lengths. Moreover, ZMAC+ (3) avoids the complex finalization of ZMAC and (4) improves the security bound from Ο(σ2/2n+min(n,t)) to Ο(q/2n + q(q + σ)/2n+min(n,t)) while retaining a practical tweak space.

2017

TOSC

Tight Security Analysis of EHtM MAC
Abstract

The security of a probabilistic Message Authentication Code (MAC) usually depends on the uniqueness of the random salt which restricts the security to birthday bound of the salt size due to the collision on random salts (e.g XMACR). To overcome the birthday bound limit, the natural approach to use (a) either a larger random salt (e.g MACRX3 uses 3n bits of random salt where n is the input and output size of the underlying non-compressing pseudorandom function or PRF) or (b) a PRF with increased domain size (e.g RWMAC or Randomized WMAC). Enhanced Hashthen- Mask (EHtM), proposed by Minematsu in FSE 2010, is the first probabilistic MAC scheme that provides beyond birthday bound security without increasing the randomness of the salt and the domain size of the non-compressing PRF. The author proved the security of EHtM as long as the number of MAC query is smaller than 22n/3 where n is the input size of the underlying non-compressing PRF. In this paper, we provide the exact security bound of EHtM and prove that this construction offers security up to 23n/4 MAC queries. The exactness is shown by demonstrating a matching attack.

2017

TOSC

Single Key Variant of PMAC_Plus
Abstract

At CRYPTO 2011, Yasuda proposed the PMAC_Plus message authentication code based on an n-bit block cipher. Its design principle inherits the well known PMAC parallel network with a low additional cost. PMAC_Plus is a rate-1 construction like PMAC (i.e., one block cipher call per n-bit message block) but provides security against all adversaries (under black-box model) making queries altogether consisting of roughly upto 22n/3 blocks (strings of n-bits). Even though PMAC_Plus gives higher security than the standard birthday bound security, with currently available best bound, it provides weaker security than PMAC for certain choices of adversaries. Moreover, unlike PMAC, PMAC_Plus operates with three independent block cipher keys. In this paper, we propose 1k-PMAC_Plus, the first rate-1 single keyed block cipher based BBB (Beyond Birthday Bound) secure (in standard model) deterministic MAC construction without arbitrary field multiplications. 1k-PMAC_Plus, as the name implies, is a simple one-key variant of PMAC_Plus. In addition to the key reduction, we obtain a higher security guarantee than what was proved originally for PMAC_Plus, thus an improvement in two directions.

2017

TOSC

Turning Online Ciphers Off
Abstract

CAESAR has caused a heated discussion regarding the merits of one-pass encryption and online ciphers. The latter is a keyed, length preserving function which outputs ciphertext blocks as soon as the respective plaintext block is available as input. The immediacy of an online cipher affords a clear performance advantage, but it comes at a price: ciphertext blocks cannot depend on later plaintext blocks, limiting diffusion and hence security. We show how one can attain the best of both worlds by providing provably secure constructions, achieving full cipher security, based on applications of an online cipher around blockwise reordering layers. Explicitly, we show that with just two calls to the online cipher, prp security up to the birthday bound is both attainable and maximal. Moreover, we demonstrate that three calls to the online cipher suffice to obtain beyond birthday bound security. We provide a full proof of this for a prp construction, and, in the ±prp setting, security against adversaries who make queries of any single length. As part of our investigation, we extend an observation by Rogaway and Zhang by further highlighting the close relationship between online ciphers and tweakable blockciphers with variable-length tweaks.

2017

TOSC

Understanding RUP Integrity of COLM
Abstract

The authenticated encryption scheme COLM is a third-round candidate in the CAESAR competition. Much like its antecedents COPA, ELmE, and ELmD, COLM consists of two parallelizable encryption layers connected by a linear mixing function. While COPA uses plain XOR mixing, ELmE, ELmD, and COLM use a more involved invertible mixing function. In this work, we investigate the integrity of the COLM structure when unverified plaintext is released, and demonstrate that its security highly depends on the choice of mixing function. Our results are threefold. First, we discuss the practical nonce-respecting forgery by Andreeva et al. (ASIACRYPT 2014) against COPA’s XOR mixing. Then we present a noncemisusing forgery against arbitrary mixing functions with practical time complexity. Finally, by using significantly larger queries, we can extend the previous forgery to be nonce-respecting.

2017

CHES

Blockcipher-Based Authenticated Encryption: How Small Can We Go?
Abstract

This paper presents a design of authenticated encryption (AE) focusing on minimizing the implementation size, i.e., hardware gates or working memory on software. The scheme is called $$\textsf {COFB}$$, for COmbined FeedBack. $$\textsf {COFB}$$ uses an n-bit blockcipher as the underlying primitive, and relies on the use of a nonce for security. In addition to the state required for executing the underlying blockcipher, $$\textsf {COFB}$$ needs only n / 2 bits state as a mask. Till date, for all existing constructions in which masks have been applied, at least n bit masks have been used. Thus, we have shown the possibility of reducing the size of a mask without degrading the security level much. Moreover, it requires one blockcipher call to process one input block. We show $$\textsf {COFB}$$ is provably secure up to $$O(2^{n/2}/n)$$ queries which is almost up to the standard birthday bound. We also present our hardware implementation results. Experimental implementation results suggest that our proposal has a good performance and the smallest footprint among all known blockcipher-based AE.

2016

TOSC

OleF: an Inverse-Free Online Cipher. An Online SPRP with an Optimal Inverse-Free Construction
Abstract

Online ciphers, in spite of being insecure against an sprp adversary, can be desirable at places because of their ease of implementation and speed. Here we propose a single-keyed inverse-free construction that achieves online sprp security with an optimal number of blockcipher calls. We also include a partial block construction, without requiring any extra key.

2010

EPRINT

A Unified Method for Improving PRF Bounds for a Class of Blockcipher based MACs
Abstract

This paper provides a unified framework for {\em improving} \PRF(pseudorandom function) advantages of several popular MACs (message authentication codes) based on a blockcipher modeled as \tx{RP} (random permutation). In many known MACs, the inputs of the underlying blockcipher are defined to be some deterministic affine functions of previously computed outputs of the blockcipher. Keeping the similarity in mind, we introduce a class of \tx{ADE}s (affine domain extensions) and a wide subclass of \tx{SADE}s (secure \tx{ADE}) containing $\mathcal{C} = \{ \tx{CBC-MAC},\ \tx{GCBC}^*,\ \tx{OMAC},\ \tx{PMAC} \}$. We define a parameter $N(t,q)$ for each domain extension and show that all \tx{SADE}s have \PRF advantages $O(tq/2^n + N(t,q)/2^n)$ where $t$ is the total number of blockcipher computations needed for all $q$ queries. We prove that \PRF advantage of any \tx{SADE} is $O(t^2/2^n)$ by showing that $N(t,q)$ is always at most ${t \choose 2}$. We provide a better estimate $O(tq)$ of $N(t,q)$ for all members of $\mathcal{C}$ and hence these MACs have {\em improved advantages $O(tq / 2^n)$}. Our proposed bounds for \tx{CBC-MAC} and $\tx{GCBC}^*$ are better than previous best known bounds.

2010

EPRINT

Speeding Up The Widepipe: Secure and Fast Hashing
Abstract

In this paper we propose a new sequential mode of operation -- the \emph{Fast wide pipe} or FWP for short -- to hash
messages of arbitrary length. The mode is shown to be (1)
\emph{preimage-resistance preserving}, (2)
\emph{collision-resistance-preserving} and, most importantly, (3)
\emph{indifferentiable} from a random oracle up to $\mathcal{O}(2^{n/2})$
compression function invocations. In addition, our rigorous investigation suggests that
any variants of Joux's multi-collision, Kelsey-Schneier 2nd preimage and
Herding attack are also ineffective on this mode. This fact leads us to conjecture that the indifferentiability security bound of FWP can be extended beyond the birthday barrier. From the point of view of efficiency, this new mode, for example, is \textit{always} faster than the Wide-pipe mode when both modes use an identical compression function. In particular, it is nearly twice as fast as the Wide-pipe for a reasonable selection of the input and output size of the compression function. We also compare the FWP with several other modes of operation.

2008

EPRINT

A Short Proof of the PRP/PRF Switching Lemma
Abstract

In Eurocrypt 2006, Bellare and Rogaway \cite{BeRo06} gave a proof of the PRP/PRF switching Lemma using their game-based proof technique. In the appendix of the same paper, they also gave an proof without games. In this paper, we give another proof of the switching lemma, which is simple and mathematically-clear and easy to uderstand. Our proof is based on \textit{the strong interpolation theorem}.

2008

EPRINT

Improving upon HCTR and matching attacks for Hash-Counter-Hash approach
Abstract

McGrew and Fluhrer first proposed hash-counter-hash approach to
encrypt arbitrary length messages. By its nature, counter can handle
incomplete message blocks as well as complete message blocks in the
same manner. HCTR is the till date best (in terms of efficiency)
strong pseudo random permutation or SPRP among all known counter
based SPRPs. But as of now, a cubic bound for HCTR is known.
Moreover, all invocations of underlying block ciphers can not be
made in parallel. Our new proposal (we call it HMC or Hash Modified
Counter) provides a quadratic security bound and all block cipher
invocations are parallel in nature even if we have an incomplete
message block. We also present a prp-distinguishing attack on a
generic counter based encryption, which makes $q$ non-adaptive
encryption queries consisting of $(\ell+1)$ $n$-bit blocks and has
success probability roughly $\ell^2q^2/2^n$. Loosely speaking, the
success probability matches with the upper bound of distinguishing
probability. As a result, we prove that the known quadratic bounds
for XCB, HCH and HMC are tight.

2008

EPRINT

A Generic Method to Extend Message Space of a Strong Pseudorandom Permutation
Abstract

In this paper we present an efficient and secure generic method
which can encrypt messages of size at least $n$. This generic
encryption algorithm needs a secure encryption algorithm for
messages of multiple of $n$. The first generic construction, XLS,
has been proposed by Ristenpart and Rogaway in FSE-07. It needs
two extra invocations of an independently chosen strong
pseudorandom permutation or SPRP defined over $\s^n$ for
encryption of an incomplete message block. Whereas our
construction needs only one invocation of a weak pseudorandom
function and two multiplications over a finite field
(equivalently, two invocations of an universal hash function). We
prove here that the proposed method preserves (tweakable) SPRP.
This new construction is meaningful for two reasons. Firstly, it
is based on weak pseudorandom function which is a weaker security
notion than SPRP. Thus we are able to achieve stronger security
from a weaker one. Secondly, in practice, finite field
multiplication is more efficient than an invocation of SPRP. Hence
our method can be more efficient than XLS.

2008

EPRINT

An Efficient SPRP-secure Construction based on Pseudo Random Involution
Abstract

Here we present a new security notion called as pseudo random
involution or PRI which are associated with tweakable involution
enciphering schemes or TIES (i.e., the encryption and decryption are
same algorithm). This new security notion is important in two
reasons. Firstly, it is the natural security notion for TIES which
are having practical importance. Secondly, we show that there is a
generic method to obtain a sprp-secure tweakable enciphering scheme
(TES) from pri-secure construction. The generic method costs an
extra xor with an extra key. In this paper, we also propose an
efficient pri-secure construction Hash-Counter Involution or HCI and
based on it we obtain a sprp-secure construction which is real
improvement over XCB. We call the new construction as MXCB or
Modified-XCB. HCH, XCB and HCTR are some of the popular counter
based enciphering schemes, where HCTR is more efficient among them
and HCH, XCB guarantee more security compare to HCTR. The new
proposal MXCB has efficiency similar to HCTR and guarantees more
security similar to HCH and XCB. We consider this new construction
to be an important in light of the current activities of the IEEE
working group on storage security which is working towards a
standard for a wide block TES.

2008

EPRINT

Two New Efficient CCA-Secure Online Ciphers: MHCBC and MCBC
Abstract

Online ciphers are those ciphers whose ciphertexts can be computed
in real time by using a length-preserving encryption algorithm.
HCBC1 and HCBC2 are two known examples of Hash Cipher Block
Chaining online ciphers. The first construction is secure against
chosen plaintext adversary (or called CPA-secure) whereas the
latter is secure against chosen ciphertext adversary (or called
CCA-secure). In this paper, we have provided simple security
analysis of these online ciphers. We have also proposed two new
more efficient chosen ciphertext secure online ciphers
modified-HCBC (MHCBC) and modified-CBC (MCBC). If one uses a
finite field multiplication based universal hash function, the
former needs one less key and one less field multiplication
compared to HCBC2. The MCBC does not need any universal hash
function and it needs only one blockcipher key unlike the other
three online ciphers where two independent keys (hash function and
blockcipher) are required.

2007

EPRINT

Improved Security Analysis of PMAC
Abstract

In this paper we provide a simple, concrete and improved security
analysis of {\bf PMAC}, a Parallelizable Message Authentication
Code. We show that the advantage of any distinguisher for {\bf PMAC}
based on a random permutation is at most $\mathbf{\frac{5q\sigma -
3.5 q^2}{2^n}}$, where $\sigma$ is the total number of message
blocks in all $q$ queries made by the distinguisher. In the original
paper by Black and Rogaway in Eurocrypt-2002, the bound was
$\frac{(\sigma+1)^2}{2^{n-1}}$. Very recently, Minematsu and
Matsushima in FSE-2007, have provided a bound $\frac{10\ell
q^2}{2^n}$ where $\ell$ is the maximum block length of all messages
queried by the distinguisher. Our new bound is better than both
original and recently proposed bound and guarantees much more
security of PMAC. We also have provided a complete, independent and
simple combinatorial proof. This proof idea may help us to find a
similar result for other MAC algorithms.

2007

EPRINT

Hash Function Design Principles Supporting Variable Output Lengths from One Small Function
Abstract

In this paper, we introduce new hash function design principles with variable output lengths (multiple of $n$).
It is based on a function or a block cipher which has output size $n$. In the random oracle model it has
optimal collision resistance which requires $\Theta(2^{(t+1)n/2})$ queries to find $(t+1)n$-bit hash
output collisions, where $t$ is any positive integer. Similarly, in the ideal cipher model, $\Theta(2^{(t+1)n/2})$
queries are required to find $(t+1)n$-bit hash output collisions.

2007

EPRINT

An improved collision probability for CBC-MAC and PMAC
Abstract

In this paper we compute the collision probability of
CBC-MAC for suitably chosen messages. We show
that the probability is $\Omega(\ell q^2/N)$ where $\ell$ is the
number of message block, $N$ is the size of the domain and $q$ is
the total number of queries. For random oracle the probability is
$O(q^2/N)$. This improved collision probability will help us to have
an efficient distinguishing attack and MAC-forgery attack. We also
show collision probability for PMAC with collision probability
$\Omega(q^2/N)$ (strictly more than birth day bound). We have used a
purely combinatorial approach to obtain this bound. The similar
analysis can be made for other MAC like XCBC,
TMAC, OMAC etc. We hope
this approach will help us to calculate related probabilities.

2007

EPRINT

A Simple Security Analysis of Hash-CBC and a New Efficient One-Key Online Cipher
Abstract

In Crypto 2001, Bellare {\em et al.} introduced {\em online cipher} (or online permutation) and proposed two Hash-CBC mode constructions, namely {\bf HCBC} and {\bf HPCBC} along with security proofs. We observe that, the security proofs in their paper are {\em wrong} and it may not be fixed easily. In this paper, we provide a {\em simple} security analysis
of these online ciphers. Moreover, we propose two variants of HPCBC,
namely {\bf MHCBC-1} and {\bf MHCBC-2}. The first variant, MHCBC-1,
is a slight modification of HPCBC so that it is more efficient in
performance as well as in memory compare to HPCBC. The other one,
MHCBC-2 requires only {\em one-key} (note that, HCBC and HPCBC
require at least two and three keys respectively) and does not
require any $\varepsilon$-$\mathrm{\Delta}$Universal Hash Family (which is costly in general).

2007

EPRINT

Improved security analysis of OMAC
Abstract

We present an improved security analysis of OMAC, the construction
is widely used as a candidate of MAC or Pseudo Random Function (or
PRF). In this direction, the first result was given in Crypto-05
where an improved security analysis of CBC (for fixed length or for
arbitrary length prefix-free messages) had provided. Followed by
this work, improved bounds for XCBC, TMAC and PMAC were found. The
improved bounds are of the form $\mathrm{O}(\frac{Lq^2}{2^n})$ where
the original bounds are $\mathrm{O}(\frac{\sigma^2}{2^n})$ which is
roughly $\mathrm{O}(\frac{L^2q^2}{2^n})$. Here, a distinguisher can
make at most $q$ queries having at most $\sigma$ many blocks with
$L$ as the maximum block size. The original bound for OMAC was
roughly $\frac{5L^2q^2}{2^n}$ shown in FSE-03 and the next improved
bound was $\frac{4\sigma^2}{2^n}$ shown in Indocrypt-03. In this
paper we have provided an improved bound (a similar form as provided
for others) for OMAC and the bound we show is roughly
$\frac{4q\sigma}{2^n} = \mathrm{O}(\frac{Lq^2}{2^n})$.

2006

ASIACRYPT

2006

EPRINT

Multicollision Attacks on some Generalized Sequential Hash Functions
Abstract

A multicollision for a function
is a set of inputs whose outputs are all identical.
A. Joux showed multicollision
attacks on the classical iterated hash function. He also showed how
these multicollision attacks can be used to get a collision attack
on a concatenated hash function. In this paper,
we study multicollision attacks in a more general class of hash functions which
we term ``generalized sequential hash functions''.
We show that multicollision attacks exist for this class of hash functions provided that
every message block is used at most twice in the computation
of the message digest.

2006

EPRINT

General Distinguishing Attacks on NMAC and HMAC with Birthday Attack Complexity
Abstract

Kim {\em et al}. \cite{KiBiPrHo06} and Contini {\em et al}.
\cite{CoYi06} studied on the security of HMAC and NMAC based on
HAVAL, MD4, MD5, SHA-0 and SHA-1. Especially, they considered the
distinguishing attacks. However, they did not describe generic
distinguishing attacks on NMAC and HMAC. In this paper, we describe
the generic distinguishers to distinguish NMAC and HMAC with the
birthday attack complexity and we prove the security bound when the
underlying compression function is the random oracle.

2006

EPRINT

A Simple and Unified Method of Proving Unpredictability
Abstract

Recently Bernstein has provided a simpler proof of
unpredictability of CBC construction which is
giving insight of the construction. Unpredictability of any
function intuitively means that the function behaves very closely
to a uniform random function. In this paper we make a unifying and
simple approach to prove unpredictability of many existing
constructions. We first revisit Bernstein's proof. Using this idea
we can show a simpler proof of unpredictability of a class of DAG
based construction, XCBC, TMAC, OMAC and PMAC. We also provide a simpler proof for stronger bound of CBC and a simpler proof of security of on-line Hash-CBC. We note that there is a flaw in the original security proof of Hash-CBC. This paper will help to understand security analysis of unpredictability of many constructions in a simpler way.

2004

EPRINT

A Generalization of PGV-Hash Functions and Security Analysis in Black-Box Model
Abstract

In~\cite{B02} it was proved that 20 out of 64 PGV-hash
functions~\cite{P94} based on block cipher are collision resistant
and one-way-secure in black-box model of the underlying block
cipher. Here, we generalize the definition of PGV-hash function
into a hash family and we will prove that besides the previous 20
hash functions we have 22 more collision resistant and one-way
secure hash families. As all these 42 families are keyed hash
family, these become target collision resistant also. All these 42
hash families have tight upper and lower bounds on (target)
collision resistant and one-way-ness.

2004

EPRINT

Designs of Efficient Secure Large Hash Values
Abstract

A double length hash function is a 2n-bit hash function based on
an n-bit compression function. To increase the security level,
designs of good double length hash functions are important. In
this paper we construct a class of maximally secure double length
hash functions in random oracle model based on some good
permutations. This class contains recently proposed double length
hash functions. We also propose an efficient double length hash function and study its security level in the random oracle model. We prove that any attack algorithm in the random oracle model needs \Omega(2^n/(s^2n^s)) time complexity, where $s$ is some parameter related to the rate of the hash function. Thus there is a trade-off between the efficiency and security. We use the notion of computable
message to make the security analysis of proposed hash functions. We also see that the security analysis of hash functions based on random permutations and hash functions based on random functions are very much related.

2004

EPRINT

Security Analysis of a 2/3-rate Double Length Compression Function in Black-Box Model
Abstract

In this paper, we propose a $2/3$-rate double length compression
function and study its security in black-box model. We prove that
to get a collision attack for the compression function requires
$\Omega(2^{2n/3})$ queries, where $n$ is the single length output
size. Thus, it has better security than a most secure single
length compression function. This construction is more efficient
than the construction given in~\cite{Hirose04}. Also the three
computations of underlying compression functions can be done in
parallel. The proof idea uses a concept of computable message
which can be helpful to study security of other constructions like
~\cite{Hirose04},~\cite{Lucks04},~\cite{Nandi04} etc.

2004

EPRINT

Multicollision Attacks on Generalized Hash Functions
Abstract

In a recent paper in crypto-04, A. Joux showed a
multicollision attacks on the classical iterated hash function. He
also showed how the multicollision attack can be used to get a
collision attack on the concatenated hash function. In this paper
we have shown that the multicollision attacks exist in a general
class of sequential or tree based hash functions even if message
blocks are used twice unlike the classical hash function.

2003

EPRINT

A New Tree based Domain Extension of UOWHF
Abstract

We present a new binary tree based parallel algorithm for extending the domain of a UOWHF. The key length expansion is m(t+O(log*(t))) bits. In particular, the key length expansion is 2m bits for t=2; m(t+1) bits for 3\leq t\leq 6 and m(t+2) bits for 7\leq t\leq 134, where m is the length of the message digest and t\geq 2 is the height of the binary tree. The previously best known binary tree algorithm required a key length expansion of m(t+[log_2 (t-1)]) bits. We also give a sufficient condition for valid domain extension in sequental domain extension.

2003

EPRINT

A Sufficient Condition and Optimal Domain Extension of UOWHF
Abstract

Here, we present how one can extend domain of a given Hash Family. We will give a sufficient condition for UOWHF-preserving domain extension (the extended Hash Family is UOWHF whenever the base Hash Family is UOWHF). We present also a binary tree based parallel algorithm for extending the domain of a UOWHF whose key-length expansion is optimum in a sub-class of binary tree based domain extension algorithm. We will show the optimality under an assumption.

#### Program Committees

- Asiacrypt 2018
- Asiacrypt 2017
- Eurocrypt 2016
- FSE 2016

#### Coauthors

- Elena Andreeva (1)
- Guy Barwell (1)
- Srimanta Bhattacharya (2)
- Rishiraj Bhattacharyya (1)
- Ritam Bhaumik (7)
- Avik Chakraborti (9)
- Debrup Chakraborty (1)
- Bishwajit Chakraborty (2)
- Donghoon Chang (9)
- Soumya Chattopadhyay (1)
- Anupam Chattopadhyay (2)
- Yu Long Chen (1)
- Benoît Cogliati (1)
- Nilanjan Datta (12)
- Avijit Dutta (9)
- Tony Grochow (1)
- Muhammad Hassan (2)
- Seokhie Hong (1)
- Tetsu Iwata (2)
- Ashwin Jha (10)
- Jesang Lee (1)
- Wonil Lee (4)
- Sangjin Lee (5)
- Gaëtan Leurent (1)
- Eik List (3)
- Atul Luykx (1)
- Cuauhtemoc Mancillas-Lopez (2)
- Avradip Mandal (4)
- Bart Mennink (3)
- Kazuhiko Minematsu (2)
- Snehal Mitragotri (1)
- Nicky Mouha (1)
- Dan Page (1)
- Tapas Pandit (2)
- Souradyuti Paul (1)
- Goutam Paul (3)
- Kouichi Sakurai (3)
- Somitra Sanadhya (1)
- Palash Sarkar (1)
- Yu Sasaki (2)
- Ferdinand Sibleyras (2)
- Martijn Stam (1)
- Douglas R. Stinson (2)
- Jaechul Sung (1)
- Soo Hak Sung (1)
- Suprita Talnikar (3)
- Kan Yasuda (3)
- Moti Yung (2)
- Liting Zhang (2)