International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Souradyuti Paul

Affiliation: ESAT/COSIC, K.U.Leuven

Publications

Year
Venue
Title
2018
TOSC
Key Assignment Scheme with Authenticated Encryption 📺
Suyash Kandele Souradyuti Paul
The Key Assignment Scheme (KAS) is a well-studied cryptographic primitive used for hierarchical access control (HAC) in a multilevel organisation where the classes of people with higher privileges can access files of those with lower ones. Our first contribution is the formalization of a new cryptographic primitive, namely, KAS-AE that supports the aforementioned HAC solution with an additional authenticated encryption property. Next, we present three efficient KAS-AE schemes that solve the HAC and the associated authenticated encryption problem more efficiently – both with respect to time and memory – than the existing solutions that achieve it by executing KAS and AE separately. Our first KAS-AE construction is built by using the cryptographic primitive MLE (EUROCRYPT 2013) as a black box; the other two constructions (which are the most efficient ones) have been derived by cleverly tweaking the hash function FP (Indocrypt 2012) and the authenticated encryption scheme APE (FSE 2014). This high efficiency of our constructions is critically achieved by using two techniques: design of a mechanism for reverse decryption used for reduction of time complexity, and a novel key management scheme for optimizing storage requirements when organizational hierarchy forms an arbitrary access graph (instead of a linear graph). We observe that constructing a highly efficient KAS-AE scheme using primitives other than MLE, FP and APE is a non-trivial task. We leave it as an open problem. Finally, we provide a detailed comparison of all the KAS-AE schemes.
2010
EPRINT
Speeding Up The Widepipe: Secure and Fast Hashing
Mridul Nandi Souradyuti Paul
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.
2007
EPRINT
Cryptanalysis of Stream Ciphers Based on Arrays and Modular Addition
Souradyuti Paul
In modern cryptography, stream ciphers are most useful in applications where information needs to be encrypted/decrypted at high speed (e.g. high resolution streaming video data) or when low footprint (gates/memory) encryption is required. In the literature, there exist plenty of stream ciphers whose internal states are based on arrays and that they use modular additions to generate output streams. The abundance of array-based stream ciphers with modular additions can be attributed to the fact that, when implemented in software skillfully, they are able to produce outputs at a very high speed. The main contribution of this thesis is a unified analysis of stream ciphers based on arrays and modular addition. During the process, we detect cryptographic weaknesses in the designs of 9 widely known stream ciphers or pseudorandom bit generators (PRBGs). At first, we show some theoretical results on solving an important class of equations known as \emph{differential equations of addition} (DEA) that combine modular additions over two different algebraic groups such as GF(2) and GF($2^{32}$). The results include, \bite \item proof of the fact that the satisfiability of an arbitrary set of DEA is in the complexity class \pP,\item deriving all the solutions of an arbitrary set of DEA. \eite Next, we apply these results to attack a practical stream cipher named Helix (designed by Ferguson \emph{et al.}) with both chosen plaintexts and adaptive chosen plaintexts. In the second phase, the thesis closely scrutinizes a number of array-based stream ciphers (or PRBGs) in order to estimate their resistance against distinguishing attacks. We eventually discover, counter-intuitively, that the correlations between the array-indices and their associated array-elements, which apparently seem to be useful from the point of view of implementation purposes, can be exploited to mount distinguishing attacks on such type of ciphers if adequate precautions are not taken. In support of our theoretical findings, we point out distinguishing attacks on 8 practical array-based stream ciphers (or PRBGs), namely RC4 (designed by Rivest), RC4A (designed by Paul and Preneel), Py, Py6 (designed by Biham and Seberry), IA, ISAAC (designed by Jenkins Jr.), GGHN, NGG (by Gong \emph{et al.}); our attacks are based on the dependence of array-elements on array-indices. In all the cases we work under the assumption that the key-setup algorithms of the ciphers produce uniformly distributed internal states. We detect flaws in the mixing of bits in the keystream generation algorithms. Our analysis can be explained as the extension, development, adaptation and deeper characterization of the \ti{fortuitous states attacks} on the RC4 cipher by Fluhrer and McGrew in 2000.
2007
EPRINT
Weaknesses in the Pseudorandom Bit Generation Algorithms of the Stream Ciphers TPypy and TPy
Gautham Sekar Souradyuti Paul Bart Preneel
The stream ciphers Py, Py6 were designed by Biham and Seberry for the ECRYPT-eSTREAM project in 2005. However, due to several recent cryptanalytic attacks on them, a strengthened version Pypy was proposed to rule out those attacks. The ciphers have been promoted to the `Focus' ciphers of the Phase II of the eSTREAM project. The impressive speed of the ciphers make them the forerunners in the competition. Unfortunately, even the new cipher Pypy was found to retain weaknesses, forcing the designers to again go for modifications. As a result, three new ciphers TPypy, TPy and TPy6 were built. Among all the members of the Py-family of ciphers, the TPypy is conjectured to be the strongest. So far, there is no known attack on the TPypy. This paper shows that the security of TPypy does not grow exponentially with the key-size. The main achievement of the paper is the detection of input-output correlations of TPypy that allow us to build a distinguisher with $2^{281}$ randomly chosen key/IVs and as many outputwords (each key generating one outputword). The cipher TPypy was claimed by the designers to be secure with keysize up to 256 bytes, i.e., 2048 bits. Our results establish that the TPypy fails to provide adequate security if the keysize is longer than 35 bytes, i.e., 280 bits. Note that the distinguisher is built within the design specifications of the cipher. Because of remarkable similarities between the TPypy and the TPy, our attacks are shown to be effective for TPy also. The paper also points out how the other members of the Py-family (i.e., Pypy and Py) are also weak against the current attacks.
2007
EPRINT
New Weaknesses in the Keystream Generation Algorithms of the Stream Ciphers TPy and Py
Gautham Sekar Souradyuti Paul Bart Preneel
The stream ciphers Py, Py6 designed by Biham and Seberry were promising candidates in the ECRYPT-eSTREAM project because of their impressive speed. Since their publication in April 2005, a number of cryptanalytic weaknesses of the ciphers have been discovered. As a result, a strengthened version Pypy was developed to repair these weaknesses; it was included in the category of `Focus ciphers' of the Phase II of the eSTREAM competition. However, even the new cipher Pypy was not free from flaws, resulting in a second redesign. This led to the generation of three new ciphers TPypy, TPy and TPy6. The designers claimed that TPy would be secure with a key size up to 256 bytes, i.e., 2048 bits. In February 2007, Sekar \emph{et al.\ }published an attack on TPy with $2^{281}$ data and comparable time. This paper shows how to build a distinguisher with $2^{275}$ key/IVs and one outputword for each key (i.e., the distinguisher can be constructed within the design specifications); it uses a different set of weak states of the TPy. Our results show that distinguishing attacks with complexity lower than the brute force exist if the key size of TPy is longer than 275 bits. Therefore, for such keys, our attack constitutes an academic break of the cipher. Furthermore, we discover a large number of similar bias-producing states of TPy and provide a general framework to compute them. The attacks on TPy are also shown to be effective on Py.
2007
EPRINT
New Attacks on the Stream Cipher TPy6 and Design of New Ciphers the TPy6-A and the TPy6-B
Gautham Sekar Souradyuti Paul Bart Preneel
The stream ciphers Py, Pypy and Py6 were designed by Biham and Seberry for the ECRYPT-eSTREAM project in 2005. The ciphers were promoted to the `Focus' ciphers of the Phase II of the eSTREAM project. However, due to some cryptanalytic results on the ciphers, strengthened versions of the ciphers, namely TPy, TPypy and TPy6 were built. So far there exists no attacks on TPy6. In this paper, we find hitherto unknown weaknesses in the keystream generation algorithms of the Py6 and of its stronger variant TPy6. Exploiting these weaknesses, a large number of distinguishing attacks are mounted on the ciphers, the best of which works with $2^{224.6}$ data and comparable time. In the second part, we present two new ciphers derived from the TPy6, namely TPy6-A and TPy6-B, whose performances are 2.65 cycles/byte and 4.4 cycles/byte on Pentium III. As a result, to the best of our knowledge, on Pentium platforms TPy6-A becomes the fastest stream cipher in the literature. Based on our security analysis, we conjecture that no attacks better than brute force are possible on the ciphers TPy6-A and TPy6-B.
2006
ASIACRYPT
2006
FSE
2005
EPRINT
On the (In)security of Stream Ciphers Based on Arrays and Modular Addition (Full Version)
Souradyuti Paul Bart Preneel
Stream ciphers play an important role in symmetric cryptology because of their suitability in high speed applications where block ciphers fall short. A large number of fast stream ciphers or pseudorandom bit generators (PRBG's) can be found in the literature that are based on arrays and simple operations such as modular additions, rotations and memory accesses (e.g. RC4, RC4A, Py, Py6, ISAAC etc.). This paper investigates the security of array-based stream ciphers (or PRBG's) against certain types of distinguishing attacks in a unified way. We argue, counter-intuitively, that the most useful characteristic of an array, namely, the association of array-elements with unique indices, may turn out to be the origins of distinguishing attacks if adequate caution is not maintained. In short, an adversary may attack a cipher simply exploiting the dependence of array-elements on the corresponding indices. Most importantly, the weaknesses are not eliminated even if the indices and the array-elements are made to follow uniform distributions separately. Exploiting these weaknesses we build distinguishing attacks with reasonable advantage on five recent stream ciphers (or PRBG's), namely, Py6 (2005, Biham \emph{et al.}), IA, ISAAC (1996, Jenkins Jr.), NGG, GGHN (2005, Gong \emph{et al.}) with data complexities $2^{68.61}$, $2^{32.89}$, $2^{16.89}$, $2^{32.89}$ and $2^{32.89}$ respectively. In all the cases we worked under the assumption that the key-setup algorithms of the ciphers produced uniformly distributed internal states. We only investigated the mixing of bits in the keystream generation algorithms. In hindsight, we also observe that the previous attacks on the other array-based stream ciphers (e.g. Py, etc.), can also be explained in the general framework developed in this paper. We hope that our analyses will be useful in the evaluation of the security of stream ciphers based on arrays and modular addition.
2004
FSE
2004
EPRINT
Solving Systems of Differential Equations of Addition
Souradyuti Paul Bart Preneel
Mixing addition modulo $2^n$ ($+$) and exclusive-or ($\oplus$) have a host of applications in symmetric cryptography as the operations are fast and nonlinear over GF(2). We deal with a frequently encountered equation $(x+y)\oplus((x\oplus\x)+(y\oplus\y))=\z$. The difficulty of solving an arbitrary system of such equations -- named \emph{differential equations of addition} (DEA) -- is an important consideration in the evaluation of the security of many ciphers against \emph{differential attacks}. This paper shows that the satisfiability of an arbitrary set of DEA -- which has so far been assumed \emph{hard} for large $n$ -- is in the complexity class P. We also design an efficient algorithm to obtain all solutions to an arbitrary system of DEA with running time linear in the number of solutions.\\ Our second contribution is solving DEA in an \emph{adaptive query model} where an equation is formed by a query $(\x,\y)$ and oracle output $\z$. The challenge is to optimize the number of queries to solve $(x+y)\oplus((x\oplus\x)+(y\oplus\y))=\z$. Our algorithm solves this equation with only 3 queries in the worst case. Another algorithm solves the equation $(x+y)\oplus(x+(y\oplus\y))=\z$ with $(n-t-1)$ queries in the worst case ($t$ is the position of the least significant `1' of $x$), and thus, outperforms the previous best known algorithm by Muller -- presented at FSE~'04 -- which required $3(n-1)$ queries. Most importantly, we show that the upper bounds, for our algorithms, on the number of queries match worst case lower bounds. This, essentially, closes further research in this direction as our lower bounds are \emph{optimal}. Finally we describe applications of our results in \emph{differential cryptanalysis.