International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Somitra Kumar Sanadhya

Publications

Year
Venue
Title
2021
TOSC
Quantum Free-Start Collision Attacks on Double Block Length Hashing with Round-Reduced AES-256
Amit Kumar Chauhan Abhishek Kumar Somitra Kumar Sanadhya
Recently, Hosoyamada and Sasaki (EUROCRYPT 2020), and Xiaoyang Dong et al. (ASIACRYPT 2020) proposed quantum collision attacks against AES-like hashing modes AES-MMO and AES-MP. Their collision attacks are based on the quantum version of the rebound attack technique exploiting the differential trails whose probabilities are too low to be useful in the classical setting but large enough in the quantum setting. In this work, we present dedicated quantum free-start collision attacks on Hirose’s double block length compression function instantiated with AES-256, namely HCF-AES-256. The best publicly known classical attack against HCF-AES-256 covers up to 9 out of 14 rounds. We present a new 10-round differential trail for HCF-AES-256 with probability 2−160, and use it to find collisions with a quantum version of the rebound attack. Our attack succeeds with a time complexity of 285.11 and requires 216 qRAM in the quantum-attack setting, where an attacker can make only classical queries to the oracle and perform offline computations. We also present a quantum free-start collision attack on HCF-AES-256 with a time complexity of 286.07 which outperforms Chailloux, Naya-Plasencia, and Schrottenloher’s generic quantum collision attack (ASIACRYPT 2017) in a model when large qRAM is not available.
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2008
EPRINT
Attacking Reduced Round SHA-256
Somitra Kumar Sanadhya Palash Sarkar
The SHA-256 hash function has started getting attention recently by the cryptanalysis community due to the various weaknesses found in its predecessors such as MD4, MD5, SHA-0 and SHA-1. We make two contributions in this work. First we describe message modification techniques and use them to obtain an algorithm to generate message pairs which collide for the actual SHA-256 reduced to 18 steps. Our second contribution is to present differential paths for 19, 20, 21, 22 and 23 steps of SHA-256. We construct parity check equations in a novel way to find these characteristics. Further, the 19-step differential path presented here is constructed by using only 15 local collisions, as against the previously known 19-step near collision differential path which consists of interleaving of 23 local collisions. Our 19-step differential path can also be seen as a single local collision at the message word level. We use a linearized local collision in this work. These results do not cause any threat to the security of the SHA-256 hash function.
2008
EPRINT
Non-Linear Reduced Round Attacks Against SHA-2 Hash family
Somitra Kumar Sanadhya Palash Sarkar
Most of the attacks against (reduced) SHA-2 family in literature have used local collisions which are valid for linearized version of SHA-2 hash functions. Recently, at FSE '08, an attack against reduced round SHA-256 was presented by Nikoli\'{c} and Biryukov which used a local collision which is valid for the actual SHA-256 function. It is a 9-step local collision which starts by introducing a modular difference of 1 in the two messages. It succeeds with probability roughly 1/3. We build on the work of Nikoli\'{c} and Biryukov and provide a generalized nonlinear local collision which accepts an arbitrary initial message difference. This local collision succeeds with probability 1. Using this local collision we present attacks against 18-step SHA-256 and 18-step SHA-512 with arbitrary initial difference. Both of these attacks succeed with probability 1. We then present special cases of our local collision and show two different differential paths for attacking 20-step SHA-256 and 20-step SHA-512. One of these paths is the same as presented by Nikoli\'{c} and Biryukov while the other one is a new differential path. Messages following both these differential paths can be found with probability 1. This improves on the previous result where the success probability of 20-step attack was 1/3. Finally, we present two differential paths for 21-step collisions for SHA-256 and SHA-512, one of which is a new path. The success probability of these paths for SHA-256 is roughly $2^{-15}$ and $2^{-17}$ which improves on the 21-step attack having probability $2^{-19}$ reported earlier. We show examples of message pairs following all the presented differential paths for up to 21-step collisions in SHA-256. We also show first real examples of colliding message pairs for up to 20-step reduced SHA-512.
2008
EPRINT
Searching for Low Weight Codewords in Linear Binary Codes
Somitra Kumar Sanadhya Palash Sarkar
In this work we revisit the known algorithms for searching for low weight codewords in linear binary codes. We propose some improvements on them and also propose a new efficient heuristic.
2008
EPRINT
Collision attacks against 22-step SHA-512
Somitra Kumar Sanadhya Palash Sarkar
In this work, we present two attacks against 22-step SHA-512. Our first attack succeeds with probability about $2^{-8}$ whereas the second attack is deterministic. To construct the attack, we use a single local collision and handle conditions on the colliding pair of messages. All but one condition can be satisfied deterministically in our first attack while in the second attack all conditions can be satisfied deterministically. There are four free words in our second attack and hence we get exactly $2^{256}$ collisions for 22-step SHA-512. Recently, attacks against up to 24-step SHA-256 have been reported in the literature which use a local collision given earlier by Nikoli\'{c} and Biryukov at FSE'08. We provide evidence which shows that using this local collision is unlikely to produce collisions for step reduced SHA-512. Consequently, our attacks are currently the best against reduced round SHA-512. The same attacks also work against SHA-256. Since our second attack is a deterministic construction, it is also the best attack against 22-step SHA-256.
2008
EPRINT
Attacking Step Reduced SHA-2 Family in a Unified Framework
Somitra Kumar Sanadhya Palash Sarkar
In this work, we make a detailed analysis of local collisions and their applicability to obtain collisions for step reduced SHA-2 hash family. Our analysis explains previously reported collisions for up to 22-step SHA-2 hash functions with probability one. We provide new and improved attacks against 23 and 24-step SHA-256 using a local collision given by Sanadhya and Sarkar (SS) at ACISP '08. The computational efforts for the 23-step and 24-step attacks are respectively $2^{12.5}$ and $2^{28.5}$ calls to the corresponding step reduced SHA-256. Using a look-up table having $2^{32}$ entries the computational effort for finding 24-step collisions can be reduced to $2^{14.5}$ calls. We exhibit colliding message pairs for both the 23 and 24-step attacks. The previous work on 23 and 24-step SHA-256 attacks is due to Indesteege et al. and utilizes the local collision presented by Nikoli\'{c} and Biryukov (NB) at FSE '08. The reported computational efforts are $2^{18}$ and $2^{28.5}$ respectively. The previous 23 and 24-step attacks first constructed a pseudo-collision and later converted it into a collision for the reduced round SHA-256. We show that this two step procedure is unnecessary. Although these attacks improve upon the existing reduced round SHA-256 attacks, they do not threaten the security of the full SHA-2 family.
2008
EPRINT
Some Observations on Strengthening the SHA-2 Family
Somitra Kumar Sanadhya Palash Sarkar
In this work, we study several properties of the SHA-2 design which have been utilized in recent collision attacks against reduced SHA-2. We suggest small modifications to the SHA-2 design to thwart these attacks. The cost of SHA-2 evaluations does not change significantly due to our modifications but the new design provides resistance to the recent collision attacks. Further, we describe an easy method of exhibiting non-randomness of the compression functions of the entire SHA family, that is SHA-0, SHA-1 and all the hash functions in SHA-2. Specifically, we show that given any $\IV_1$ and any pair of messages $M_1$ and $M_2$, an $\IV_2$ can be easily and deterministically constructed such that the relation $H(\IV_1,M_1)-\IV_1 = H(\IV_2,M_2)-\IV_2$ holds. For a truly random hash function $H$ outputting a $k$-bit digest, such a relation should hold with probability $2^{-k}$. We introduce the general idea of ``multiple feed-forward" in the context of construction of cryptographic hash functions. When used in SHA designs, this technique removes the non-randomness mentioned earlier. Perhaps more importantly, it provides increased resistance to the Chabaud-Joux type ``perturbation-correction'' collision attacks. The idea of feed-forward is taken further by introducing the idea of feed-forward across message blocks. This provides quantifiably better resistance to Joux type generic multi-collision attacks. For example, with our modification of SHA-256, finding $2^r$ messages which map to the same value will require $r\times 2^{384}$ invocations of the compression function.
2008
EPRINT
A Combinatorial Analysis of Recent Attacks on Step Reduced SHA-2 Family
Somitra Kumar Sanadhya Palash Sarkar
We perform a combinatorial analysis of SHA-2 compression function. This analysis explains in a unified way the recent attacks against reduced round SHA-2. We start with a general class of local collisions and show that the previously used local collision by Nikoli\'{c} and Biryukov (NB) and Sanadhya and Sarkar (SS) are special cases. The study also clarifies several advantages of the SS local collision over the NB local collision. Deterministic constructions of up to 22-round SHA-2 collisions are described using the SS local collision and up to 21-round SHA-2 collisions are described using the NB local collision. For 23 and 24-round SHA-2, we describe a general strategy and then apply the SS local collision to this strategy. The resulting attacks are faster than those proposed by Indesteege et al using the NB local collision. We provide colliding message pairs for 22, 23 and 24-round SHA-2. Although these attacks improve upon the existing reduced round SHA-256 attacks, they do not threaten the security of the full SHA-2 family. \footnote{This work builds upon and subsumes previous work done by us. Whereas the previous works focused on obtaining collisions for fixed number of rounds, the current work provides the combinatorial framework for understanding how such collisions arise.}
2008
EPRINT
New Collision attacks Against Up To 24-step SHA-2
Somitra Kumar Sanadhya Palash Sarkar
In this work, we provide new and improved attacks against 22, 23 and 24-step SHA-2 family using a local collision given by Sanadhya and Sarkar (SS) at ACISP '08. The success probability of our 22-step attack is 1 for both SHA-256 and SHA-512. The computational efforts for the 23-step and 24-step SHA-256 attacks are respectively $2^{11.5}$ and $2^{28.5}$ calls to the corresponding step reduced SHA-256. The corresponding values for the 23 and 24-step SHA-512 attack are respectively $2^{16.5}$ and $2^{32.5}$ calls. Using a look-up table having $2^{32}$ (resp. $2^{64}$) entries the computational effort for finding 24-step SHA-256 (resp. SHA-512) collisions can be reduced to $2^{15.5}$ (resp. $2^{22.5}$) calls. We exhibit colliding message pairs for 22, 23 and 24-step SHA-256 and SHA-512. This is the \emph{first} time that a colliding message pair for 24-step SHA-512 is provided. The previous work on 23 and 24-step SHA-2 attacks is due to Indesteege et al. and utilizes the local collision presented by Nikoli\'{c} and Biryukov NB) at FSE '08. The reported computational efforts are $2^{18}$ and $2^{28.5}$ for 23 and 24-step SHA-256 respectively and $2^{43.9}$ and $2^{53}$ for 23 and 24-step SHA-512. The previous 23 and 24-step attacks first constructed a pseudo-collision and later converted it into a collision for the reduced round SHA-2 family. We show that this two step procedure is unnecessary. Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family.
2007
EPRINT
New Local Collisions for the SHA-2 Hash Family
Somitra Kumar Sanadhya Palash Sarkar
The starting point for collision attacks on practical hash functions is a local collision. In this paper, we make a systematic study of local collisions for the SHA-2 family. The possible linear approximations of the constituent Boolean functions are considered and certain impossible conditions for such approximations are identified. Based on appropriate approximations, we describe a general method for finding local collisions. Applying this method, we obtain several local collisions and compute the probabilities of the various differential paths. Previously, only one local collision due to Gilbert-Handschuh was known. We point out two impossible conditions in the GH local collision and provide an example of an impossible differential path for linearized SHA-2 using this local collision. Sixteen new local collisions are obtained none of which have any impossible conditions. The probabilities of these local collisions are a little less than the GH local collision. On the other hand, the absence of impossible conditions may make them more suitable for (reduced round) collision search attacks on the SHA-2 family.