## CryptoDB

### Danilo Gligoroski

#### Affiliation: Dep of Telematics, NTNU, Norway

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Practical consequences of the aberration of narrow-pipe hash designs from ideal random functions
Abstract

In a recent note to the NIST hash-forum list, the following
observation was presented: narrow-pipe hash functions differ
significantly from ideal random functions $H:\{0,1\}^{N} \rightarrow
\{0,1\}^n$ that map bit strings from a big domain where $N=n+m,\
m\geq n$ ($n=256$ or $n=512$). Namely, for an ideal random function
with a big domain space $\{0,1\}^{N}$ and a finite co-domain space
$Y=\{0,1\}^n$, for every element $y \in Y$, the probability
$Pr\{H^{-1}(y) = \varnothing\} \approx e^{-2^{m}} \approx 0$ where
$H^{-1}(y) \subseteq \{0,1\}^{N}$ and $H^{-1}(y) = \{x \ |\ H(x)=y
\}$ (in words - the probability that elements of $Y$ are
``unreachable'' is negligible). However, for the narrow-pipe hash
functions, for certain values of $N$ (the values that are causing
the last padded block that is processed by the compression function
of these functions to have no message bits), there exists a huge
non-empty subset $Y_\varnothing \subseteq Y$ with a volume
$|Y_\varnothing|\approx e^{-1}|Y|\approx 0.36 |Y|$ for which it is
true that for every $y \in Y_\varnothing,\ H^{-1}(y) = \varnothing$.
In this paper we extend the same finding to SHA-2 and show
consequences of this abberation when narrow-pipe hash functions are
employed in HMAC and in two widely used protocols: 1. The
pseudo-random function defined in SSL/TLS 1.2 and 2. The
Password-based Key Derivation Function No.1, i.e. PBKDF1.

2010

EPRINT

Generic Collision Attacks on Narrow-pipe Hash Functions Faster than Birthday Paradox, Applicable to MDx, SHA-1, SHA-2, and SHA-3 Narrow-pipe Candidates
Abstract

In this note we show a consequence of the recent observation that narrow-pipe hash designs manifest an abberation from ideal random
functions for finding collisions for those functions with complexities much lower than the so called generic birthday paradox lower bound. The problem is generic for narrow-pipe designs including classic Merkle-Damgard designs but also recent narrow-pipe SHA-3 candidates. Our finding does not reduces the generic collision security of n/2 bits that narrow-pipe functions are declaring, but it clearly shows that narrow-pipe designs have a property when we count the calls to the hash function as a whole, the birthday paradox bound of 2^{n/2} calls to the hash function is clearly
broken. This is yet another property in a series of similar non-ideal random properties (like HMAC or PRF constructions) that narrow-pipe hash function manifest and that are described in [1] and [2].

2009

EPRINT

On a Conditional Collision Attack on NaSHA-512
Abstract

A collision attack on NaSHA-512 was proposed by L. Ji et al. The
claimed complexity of the attack is $2^{192}$. The proposed attack
is realized by using a suitable differential pattern. In this note
we show that the correct result that can be inferred from their
differential pattern is in fact a conditional one. It can be
stated correctly as follows: A collision attack on NaSHA-512 of
complexity $k=1,2,\dots,2^{320}$ can be performed with an unknown
probability of success $p_k$, where $ 0\le p_1\le p_2\le
p_{2^{320}}\le 1$. Consequently, the attack proposed by L. Ji et
al. can be considered only as a direction how a possible collision
attack on NaSHA-512 could be realized. The birthday attack remains
the best possible attack on NaSHA-512.

2008

EPRINT

Public Key Block Cipher Based on Multivariate Quadratic Quasigroups
Abstract

We have designed a new class of public
key algorithms based on quasigroup string transformations using a
specific class of quasigroups called \emph{multivariate quadratic
quasigroups (MQQ)}. Our public key algorithm is a bijective mapping,
it does not perform message expansions and can be used both for
encryption and signatures. The public key consist of $n$ quadratic
polynomials with $n$ variables where $n=140, 160, \ldots$. A
particular characteristic of our public key algorithm is that it is
very fast and highly parallelizable. More concretely, it has the
speed of a typical modern symmetric block cipher -- the reason for
the phrase \emph{"A Public Key Block Cipher"} in the title of this
paper. Namely the reference C code for the 160--bit variant of the
algorithm performs decryption in less than 11,000 cycles (on Intel
Core 2 Duo -- using only one processor core), and around 6,000
cycles using two CPU cores and OpenMP 2.0 library. However,
implemented in Xilinx Virtex-5 FPGA that is running on 249.4 MHz it
achieves decryption throughput of 399 Mbps, and implemented on four
Xilinx Virtex-5 chips that are running on 276.7 MHz it achieves
encryption throughput of 44.27 Gbps. Compared to fastest RSA
implementations on similar FPGA platforms, MQQ algorithm is more
than 10,000 times faster.

2008

EPRINT

High Performance Implementation of a Public Key Block Cipher - MQQ, for FPGA Platforms
Abstract

We have implemented in FPGA recently published class of public key algorithms -- MQQ, that are based on quasigroup string transformations. Our implementation achieves decryption throughput of 399 Mbps on an Xilinx Virtex-5 FPGA that is running on 249.4 MHz. The encryption throughput of our implementation achieves 44.27 Gbps on four Xilinx Virtex-5 chips that are running on 276.7 MHz. Compared to RSA implementation on the same FPGA platform this implementation of MQQ is 10,000 times faster in decryption, and is more than 17,000 times faster in encryption.

2007

EPRINT

Edon--${\cal R}(256,384,512)$ -- an Efficient Implementation of Edon--${\cal R}$ Family of Cryptographic Hash Functions
Abstract

We have designed three fast implementations of recently proposed family of hash functions Edon--${\cal R}$. They produce message digests of length 256, 384 and 512 bits. We have defined huge quasigroups of orders $2^{256}$, $2^{384}$ and $2^{512}$ by using only bitwise operations on 32 bit values (additions modulo $2^{32}$, XORs and left rotations) and achieved processing speeds of the Reference C code of 16.18 cycles/byte, 24.37 cycles/byte and 32.18 cycles/byte on x86 (Intel and AMD microprocessors). In this paper we give their full description, as well as an initial security analysis.

2007

EPRINT

On the insecurity of interchanged use of OFB and CBC modes of operation
Abstract

The security of interchanged use of modes of operation of block ciphers have not been discussed in the public literature. So far, the modes of operation of block ciphers have been treated as completely independent and uncorrelated. In this paper we represent both CBC and OFB as quasigroup string transformations, and then show that OFB mode is a special case of the CBC mode of operation. That raise possibilities for construction of several devastating attack scenarios against that interchanged use of CBC and OFB. These attacks have not been addressed in NIST Special Publication 800-38A 2001, ``Recommendation for Block Cipher Modes of Operation''. More specifically, in the chosen plaintext attack scenario with interchanged use of CBC and OFB mode, we give a concrete list of openssl commands that extract the complete plaintext without knowing the secret key.

2007

EPRINT

Turbo SHA-2
Abstract

In this paper we describe the construction of Turbo SHA-2 family of cryptographic hash functions. They are built with design components from the SHA-2 family, but the new hash function has three times more chaining variables, it is more robust and resistant against generic multi-block collision attacks, its design is resistant against generic length extension attacks and it is 2 - 8 times faster than the original SHA-2. It uses two novel design principles in the design of hash functions: {\em 1. Computations in the iterative part of the compression function start by using variables produced in the message expansion part that have the complexity level of a random Boolean function, 2. Variables produced in the message expansion part are not discarded after the processing of the current message block, but are used for the construction of the three times wider chain for the next message block.} These two novel principles combined with the already robust design principles present in SHA-2 (such as the nonlinear message expansion part), enabled us to build the compression function of Turbo SHA-2 that has just 16 new variables in the message expansion part (compared to 48 for SHA-256 and 64 for SHA-512) and just 8 rounds in the iterative part (compared to 64 for SHA-256 and 80 for SHA-512).

2005

EPRINT

Candidate One-Way Functions and One-Way Permutations Based on Quasigroup String Transformations
Abstract

In this paper we propose a definition and construction of a new
family of one-way candidate functions ${\cal R}_N:Q^N \rightarrow
Q^N$, where $Q=\{0,1,\ldots,s-1\}$ is an alphabet with $s$
elements. Special instances of these functions can have the
additional property to be permutations (i.e. one-way
permutations). These one-way functions have the property that for
achieving the security level of $2^n$ computations in order to
invert them, only $n$ bits of input are needed. The construction
is based on quasigroup string transformations. Since quasigroups
in general do not have algebraic properties such as associativity,
commutativity, neutral elements, inverting these functions seems
to require exponentially many readings from the lookup table that
defines them (a Latin Square) in order to check the satisfiability
for the initial conditions, thus making them natural candidates
for one-way functions.

#### Coauthors

- Sergey Bezzateev (1)
- Christopher Carr (1)
- V. Dimitrova (1)
- Mohamed El-Hadedy (1)
- Jean-Charles Faugère (1)
- Britta Hale (1)
- Håkon Jacobsen (1)
- Vlastimil Klima (2)
- Svein J. Knapskog (4)
- Ljupco Kocarev (1)
- Smile Markovski (3)
- Hristina Mihajloska (1)
- A. Mileva (1)
- Ludovic Perret (1)
- Simona Samardjiska (3)
- Enrico Thomae (1)