## CryptoDB

### Goutam Paul

#### Affiliation: Indian Statistical Institute

#### Publications

**Year**

**Venue**

**Title**

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.

2018

TOSC

New Yoyo Tricks with AES-based Permutations
Abstract

In Asiacrypt 2017, Rønjom et al. reported some interesting generic properties of SPNs, leading to what they call the Yoyo trick, and applied it to find the most efficient distinguishers on AES. In this work, we explore the Yoyo idea in distinguishing public permutations for the first time. We introduce the notion of nested zero difference pattern which extends the Yoyo idea and helps to compose it using improbable and impossible differential strategies to penetrate higher number of rounds. We devise a novel inside-out application of Yoyo which enables us to start the Yoyo game from an internal round. As an application, we investigate the AES-based public permutation AESQ used inside the authenticated cipher PAEQ. We achieve the first deterministic distinguisher of AESQ up to 8 rounds and the first 9-round distinguisher of AESQ that start from the first round with a practical complexity of around 226. We manage to augment Yoyo with improbable and impossible differentials leading to distinguishers on 9, 10, 12 rounds with complexities of about 22, 228, 2126 respectively. Further, with impossible differentials and a bi-directional Yoyo strategy, we obtain a 16-round impossible differential distinguisher with a complexity of 2126. Our results outperform all previous records on AESQ by a substantial margin. As another application, we apply the proposed strategies on AES in the known-key setting leading to one of the best 8-round known-key distinguisher with a complexity of 230. Finally, this work amplifies the scope of the Yoyo technique as a generic cryptanalysis tool.

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.

2010

EPRINT

A Combinatorial Analysis of HC-128
Abstract

We show that the knowledge of any one of the two internal state arrays of HC-128 along with the knowledge of 2048 keystream words is sufficient
to construct the other state array completely in $2^{42}$ time complexity. Though our analysis does not lead to any attack on HC-128, it reveals a structural insight into the cipher. In the process, we theoretically establish certain combinatorial properties of HC-128 keystream generation algorithm. We also suggest a modification to HC-128 that takes care of the recently known cryptanalytic results with little reduction in speed.

2008

EPRINT

Analysis of RC4 and Proposal of Additional Layers for Better Security Margin
Abstract

In this paper, the RC4 Key Scheduling Algorithm (KSA) is theoretically studied to reveal non-uniformity in the expected number of times each value of the permutation is touched by the indices $i, j$. Based on our analysis and the results available in literature regarding the existing weaknesses of RC4, few additional layers over the RC4 KSA and RC4 Pseudo-Random Generation Algorithm (PRGA) are proposed. Analysis of the modified cipher (we call it RC4$^+$) shows that this new strategy avoids existing weaknesses of RC4.

2007

EPRINT

RC4 State Information at Any Stage Reveals the Secret Key
Abstract

A theoretical analysis of the RC4 Key Scheduling Algorithm (KSA) is presented in this paper, where the nonlinear operation is swapping among the permutation bytes. Explicit formulae are provided for the probabilities with which the permutation bytes at any stage of the KSA are biased to the secret key. Theoretical proofs of these formulae have been left open since Roos's work (1995). Based on this analysis, an algorithm is devised to recover the $l$ bytes (i.e., $8l$ bits, typically $5 \leq l \leq 16)$ secret key from the permutation after any round of the KSA with constant probability of success. The search requires $O(2^{4l})$ many operations which is the square root of the exhaustive key search complexity $2^{8l}$. Moreover, given the state information, i.e., (a) the permutation, (b) the number of bytes generated (which is related to the index $i$) and (c) the value of the index $j$, after any number of rounds in Pseudo-Random Generation Algorithm (PRGA) of RC4, one can deterministically get back to the permutation after the KSA and thereby extract the keys efficiently with a constant probability of success. Finally, a generalization of the RC4 KSA is analyzed corresponding to a class of update functions of the indices involved in the swaps. This reveals an inherent weakness of shuffle-exchange kind of key scheduling.

2007

EPRINT

New Form of Permutation Bias and Secret Key Leakage in Keystream Bytes of RC4
Abstract

Consider the permutation $S$ in RC4. Roos pointed out in 1995 that after the Key Scheduling Algorithm (KSA) of RC4, the initial bytes of the permutation, i.e., $S[y]$ for small values of $y$ are biased towards some linear combination of secret key bytes. In this paper, for the first time we show that the bias can be observed in $S[S[y]]$ too. Based on this new form of permuatation bias after the KSA and other related results, a complete framework is presented to show that many keystream output bytes of RC4 are significantly biased towards several linear combinations of the secret key bytes. The results do not assume any condition on the secret key. We find new biases in the initial as well as in the 256-th and 257-th keystream output bytes. For the first time biases at such later stages are discovered without any knowledge of secret key bytes. We also identify that these biases propagate further once the information for the index $j$ is revealed.

2007

EPRINT

On Non-Randomness of the Permutation after RC4 Key Scheduling
Abstract

Here we study a weakness of the RC4 Key Scheduling Algorithm (KSA) that has already been noted by Mantin and Mironov. Consider the RC4 permutation $S$ of $N$ (usually 256) bytes and denote it by $S_N$ after the KSA. Under reasonable assumptions we present a simple proof that each permutation byte after the KSA is significantly biased (either positive or negative) towards many values in the range $0, \ldots, N-1$. These biases are independent of the secret key and thus present an evidence that the permutation after the KSA can be distinguished from random permutation without any assumption on the secret key. We also present a detailed empirical study over Mantin's work when the theoretical formulae vary significantly from experimental results
due to repetition of short keys in RC4. Further, it is explained how these results can be used to identify new distinguishers for RC4 keystream.

#### Coauthors

- Christina Boura (1)
- Avik Chakraborti (1)
- Nilanjan Datta (3)
- Avijit Dutta (5)
- Gaëtan Leurent (1)
- Subhamoy Maitra (10)
- Willi Meier (2)
- Mridul Nandi (3)
- Mostafizar Rahman (1)
- Shashwat Raizada (1)
- Dhiman Saha (2)
- Santanu Sarkar (2)
- Sourav Sen Gupta (3)
- Hadi Soleimany (1)
- Rohit Srivastava (1)
- Valentin Suder (1)
- Liting Zhang (2)