## CryptoDB

### Souradyuti Paul

#### Affiliation: ESAT/COSIC, K.U.Leuven

#### Publications

**Year**

**Venue**

**Title**

2018

TOSC

Key Assignment Scheme with Authenticated Encryption
📺
Abstract

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
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.

2007

EPRINT

Cryptanalysis of Stream Ciphers Based on Arrays and Modular Addition
Abstract

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
Abstract

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
Abstract

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
Abstract

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.

2005

EPRINT

On the (In)security of Stream Ciphers Based on Arrays and Modular Addition (Full Version)
Abstract

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
Abstract

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.

#### Coauthors

- Suyash Kandele (1)
- Mridul Nandi (1)
- Bart Preneel (8)
- Gautham Sekar (4)