## CryptoDB

### Danilo Gligoroski

#### Publications

Year
Venue
Title
2015
EPRINT
2015
EPRINT
2015
PKC
2014
EPRINT
2010
EPRINT
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
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
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
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
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
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
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
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
FSE
2005
EPRINT
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.