## CryptoDB

### Jovan Dj. Golic

#### Publications

**Year**

**Venue**

**Title**

2008

EPRINT

Iterative Probabilistic Reconstruction of RC4 Internal States
Abstract

It is shown that an improved version of a previously proposed iterative probabilistic algorithm, based on forward and backward probability recursions along a short keystream segment, is capable of reconstructing the RC4 internal states from a relatively small number of known initial permutation entries. Given a modulus $N$, it is argued that about $N/3$ and $N/10$ known entries are sufficient for success, for consecutive and specially generated entries, respectively. The complexities of the corresponding guess-and-determine attacks are analyzed and, e.g., for $N=256$, the data and time complexities are (conservatively) estimated to be around $D \approx 2^{41}$, $C \approx 2^{689}$ and $D \approx 2^{211}$, $C \approx 2^{262}$, for the two types of guessed entries considered, respectively.

2005

EPRINT

Techniques for random maskin in hardware
Abstract

A new technique for Boolean random masking of the logic AND operation in terms of NAND logic gates
is presented and its potential for masking arbitrary cryptographic functions is pointed out.
The new technique is much more efficient than a previously known technique, recently applied to AES.
It is also applied for masking the integer addition.
In addition, new techniques for the conversions from Boolean to arithmetic random masking and vice versa
are developed. They are hardware oriented and do not require additional random bits.
Unlike the previous, software-oriented techniques showing a substantial difference in the complexity
of the two conversions, they have a comparable complexity being about the same as that
of one integer addition only.
All the techniques proposed are in theory secure against the first-order differential
power analysis on the logic gate level.
They can be applied in hardware implementations of various cryptographic functions,
including AES, (keyed) SHA-1, IDEA, and RC6.

2004

EPRINT

Vectorial Boolean functions and induced algebraic equations
Abstract

A general mathematical framework behind algebraic cryptanalytic attacks is developed. The framework relates to finding algebraic equations induced by vectorial Boolean functions and, in particular, equations of low algebraic degree. The equations may involve only a subset of input variables and may or may not be conditioned on the values of output variables. In addition, the equations may have a special form interesting for the so-called fast algebraic attacks. A possible divide-and-conquer effect is pointed out and the notion of algebraic immunity order, naturally extending the notion of correlation immunity order, is introduced. An application of general results to stream ciphers known as combiners with or without memory, with possibly multiple outputs, is studied in particular detail. Special properties of combiners with finite input memory, such as nonlinear filter generators, are established. Finally, finding induced algebraic equations for divide-and-conquer algebraic attacks on combiners with or without memory is also considered.

2004

EPRINT

Vectorial fast correlation attacks
Abstract

A new, vectorial approach to fast correlation attacks on binary memoryless combiners is proposed.
Instead of individual input sequences or their linear combinations, the new attack is targeting
subsets of input sequences as a whole, thus exploiting the full correlation between the chosen
subset and the output sequence. In particular, all the input sequences can be targeted simultaneously.
The attack is based on a novel iterative
probabilistic algorithm which is also applicable to general memoryless combiners over finite fields or finite
rings.
Experimental results obtained for randomly chosen binary combiners with balanced combining functions show
that the vectorial approach yields a considerable improvement in comparison with the classical, scalar approach.

2004

EPRINT

New paradigms for digital generation and post-processing of random data
Abstract

A new method for digital true random number generation based on asynchronous logic circuits with feedback is
introduced. In particular, a concrete technique using the so-called Fibonacci and Galois ring oscillators is
developed and experimentally tested in FPGA technology. The generated
random binary sequences inherently have a high speed and a very high and robust entropy
rate in comparison with previous proposals for digital random number generators.
A new method for digital post-processing of random data based on
non-autonomous synchronous logic circuits with feedback is also introduced
and a concrete technique using a self-clock-controlled linear feedback shift register is proposed.
The post-processing can provide both randomness extraction and computationally secure speed increase of
input random data.

2003

EPRINT

A new statistical distinguisher for the shrinking generator
Abstract

The shrinking generator is a well-known keystream generator composed
of two linear feedback shift registers, LFSR$_1$ and LFSR$_2$, where
LFSR$_1$ is clock-controlled according to regularly clocked LFSR$_2$.
The keystream sequence is thus a decimated LFSR$_1$ sequence.
Statistical distinguishers for keystream generators are algorithms whose objective is to distinguish the
keystream sequence from a purely random sequence.
Previously proposed statistical distinguishers for the shrinking generator
are based on detecting binary linear relations in the keystream sequence that hold
with a probability sufficiently different from one half.
In this paper a novel approach which significantly reduces the required computation time is introduced.
It is based on a probabilistic reconstruction of the bits in the regularly
clocked LFSR$_1$ sequence that satisfy the LFSR$_1$ recurrence
or any linear recurrence derived from
low-weight multiples of the LFSR$_1$ characteristic polynomial.
The keystream sequence length and the computation time required for a reliable statistical distinction
are analyzed both theoretically and experimentally.

2002

EPRINT

Multiplicative Masking and Power Analysis of AES
Abstract

The recently proposed multiplicative masking countermeasure against power
analysis attacks on AES is interesting as it does not require the costly recomputation and RAM storage
of S-boxes for every run of AES. This is important for applications where the
available space is very limited such as the smart card applications.
Unfortunately, it is here shown that this method is
in fact inherently vulnerable to differential power analysis.
Other possible random masking methods are also discussed.

1992

EUROCRYPT

1991

JOFC

1990

AUSCRYPT

1990

EUROCRYPT

#### Program Committees

- Asiacrypt 2008
- Asiacrypt 2005
- CHES 2004
- FSE 2003
- Asiacrypt 2001
- Eurocrypt 1996
- Eurocrypt 1992

#### Coauthors

- Vittorio Bagini (1)
- Andrew J. Clark (1)
- Ed Dawson (2)
- Markus Dichtl (1)
- Renato Menicocci (3)
- Miodrag J. Mihaljevic (5)
- Guglielmo Morgari (4)
- Luke O'Connor (2)
- Slobodan V. Petrovic (1)
- Mahmoud Salmasizadeh (1)
- Christophe Tymen (1)