Search

The innovative protocol of Juels and Weis [10] extends device authentication to low-cost RFID tags. However, despite the very simple on-tag computation there remain some practical problems with and despite an elegant proof of security against some limited active attacks, there is a simple man-in-the-middle attack due to Gilbert et al. [8]. In this paper we consider improvements to in terms of both security and practicality. We introduce a new protocol that we denote random- . This proposal avoids many practical drawbacks of , remains provably resistant to attacks in the model of Juels and Weis, and at the same time is provably resistant to a broader class of active attacks that includes the attack of [8]. We then describe an enhanced variant called which offers practical advantages over . [ABSTRACT FROM AUTHOR]

The stream cipher Py designed by Biham and Seberry is a submission to the ECRYPT stream cipher competition. The cipher is based on two large arrays (one is 256 bytes and the other is 1040 bytes) and it is designed for high speed software applications (Py is more than 2.5 times faster than the RC4 on Pentium III). The paper shows a statistical bias in the distribution of its output-words at the 1st and 3rd rounds. Exploiting this weakness, a distinguisher with advantage greater than 50% is constructed that requires 284.7 randomly chosen key/IV's and the first 24 output bytes for each key. The running time and the data required by the distinguisher are t284.7 and 289.2 respectively (t denotes the running time of the key/IV setup). We further show that the data requirement can be reduced by a factor of about 3 with a distinguisher that considers outputs of later rounds. In such case the running time is reduced to t284.7 (t denotes the time for a single round of Py). The Py specification allows a 256-bit key and a keystream of 264 bytes per key/IV. As an ideally secure stream cipher with the above specifications should be able to resist the attacks described before, our results constitute an academic break of Py. In addition we have identified several biases among pairs of bits; it seems possible to combine all the biases to build more efficient distinguishers. [ABSTRACT FROM AUTHOR]

WG and LEX are two stream ciphers submitted to eStream - the ECRYPT stream cipher project. In this paper, we point out security flaws in the resynchronization of these two ciphers. The resynchronization of WG is vulnerable to a differential attack. For WG with 80-bit key and 80-bit IV, 48 bits of the secret key can be recovered with about 231.3 chosen IVs . For each chosen IV, only the first four keystream bits are needed in the attack. The resynchronization of LEX is vulnerable to a slide attack. If a key is used with about 260.8 random IVs, and 20,000 keystream bytes are generated from each IV, then the key of the strong version of LEX could be recovered easily with a slide attack. The resynchronization attack on WG and LEX shows that block cipher related attacks are powerful in analyzing non-linear resynchronization mechanisms. Keywords: cryptanalysis, stream cipher, resynchronization attack, differential attack, slide attack, WG, LEX. [ABSTRACT FROM AUTHOR]

Algebraic attacks have received a lot of attention in studying security of symmetric ciphers. The function used in a symmetric cipher should have high algebraic immunity (${\cal AI}$) to resist algebraic attacks. In this paper we are interested in finding ${\cal AI}$ of Boolean power functions. We give an upper bound on the ${\cal AI}$ of any Boolean power function and a formula to find its corresponding low degree multiples. We prove that the upper bound on the ${\cal AI}$ for Boolean power functions with Inverse, Kasami and Niho exponents are $\lfloor \sqrt{n}\rfloor + \lceil \frac{n}{\lfloor \sqrt{n} \rfloor}\rceil -2$, $\lfloor \sqrt{n} \rfloor + \lceil \frac{n}{\lfloor \sqrt{n} \rfloor}\rceil$ and $\lfloor \sqrt{n} \rfloor + \lceil \frac{n}{\lfloor \sqrt{n} \rfloor}\rceil$ respectively. We also generalize this idea to Boolean polynomial functions. All existing algorithms to determine ${\cal AI}$ and corresponding low degree multiples become too complex if the function has more than 25 variables. In our approach no algorithm is required. The ${\cal AI}$ and low degree multiples can be obtained directly from the given formula. Keywords: Algebraic attacks, Algebraic immunity, Inverse exponent, Kasami exponent, Polynomial functions, Power functions, Niho exponent. [ABSTRACT FROM AUTHOR]

Self-Synchronizing Stream Ciphers (SSSC) are a particular class of symmetric encryption algorithms, such that the resynchronization is automatic, in case of error during the transmission of the ciphertext. In this paper, we extend the scope of chosen-ciphertext attacks against SSSC. Previous work in this area include the cryptanalysis of dedicated constructions, like KNOT, HBB or SSS. We go further to break the last standing dedicated design of SSSC, i.e. the ECRYPT proposal MOSQUITO. Our attack costs about 270 computation steps, while a 96-bit security level was expected. It also applies to ΓΥ (an ancestor of MOSQUITO) therefore the only secure remaining SSSC are block-cipher-based constructions. [ABSTRACT FROM AUTHOR]

This paper studies the state-of-the-art software optimization methodology for symmetric cryptographic primitives on the new 64-bit x64 processors, AMD Athlon64 (AMD64) and Intel Pentium 4 (EM64T). We fully utilize newly introduced 64-bit registers and instructions for extracting maximal performance of target primitives. Our program of AES with 128-bit key runs in 170 cycles/block on Athlon 64, which is, as far as we know, the fastest implementation of AES on a PC processor. Also we implemented a "bitsliced" AES and Camellia for the first time, both of which achieved very good performance. A bitslice implementation is important from the viewpoint of a countermeasure against cache timing attacks because it does not require lookup tables with a key-dependent address. We also analyze performance of SHA256/512 and Whirlpool hash functions and show that SHA512 can run faster than SHA256 on Athlon 64. This paper exhibits an undocumented fact that 64-bit right shifts and 64-bit rotations are extremely slow on Pentium 4, which often leads to serious and unavoidable performance penalties in programming encryption primitives on this processor. Keywords: Fast Software Encryption, x64 Processors, Bitslice. [ABSTRACT FROM AUTHOR]

The purpose of algebraic attacks on stream and block ciphers is to recover the secret key by solving an overdefined system of multivariate algebraic equations. They become very efficient if this system is of low degree. In particular, they have been used to break stream ciphers immune to all previously known attacks. This kind of attack tends to work when certain Boolean functions used in the ciphering process have either low degree annihilators or low degree multiples. It is therefore important to be able to check this criterion for Boolean functions. We provide in this article an algorithm of complexity $O \left( m^d\right)$ (for fixed d) which is able to prove that a given Boolean function in m variables has no annihilator nor multiple of degree less than or equal to d. This complexity is essentially optimal. We also provide a more practical algorithm for the same task, which we believe to have the same complexity. This last algorithm is also able to output a basis of annihilators or multiples when they exist. Keywords: Algebraic attacks, Algebraic immunity, Stream ciphers, Boolean functions, Annihilator, Low degree multiple. [ABSTRACT FROM AUTHOR]

In this article we present a detailed analysis of the impact of carries on the estimation of the attack complexity for SHA-1. We build up on existing estimates and refine them. We show that the attack complexity is slightly lower than estimated in all published work to date. We point out that it is more accurate to consider probabilities instead of conditions. [ABSTRACT FROM AUTHOR]

The Ideal-Cipher Model of a blockcipher is a well-known and widely-used model dating back to Shannon [25] and has seen frequent use in proving the security of various cryptographic objects and protocols. But very little discussion has transpired regarding the meaning of proofs conducted in this model or regarding the model's validity. In this paper, we briefly discuss the implications of proofs done in the ideal-cipher model, then show some limitations of the model analogous to recent work regarding the Random-Oracle Model [2]. In particular, we extend work by Canetti, Goldreich and Halevi [5], and a recent simplification by Maurer, Renner, and Holenstein [15], to exhibit a blockcipher-based hash function that is provably-secure in the ideal-cipher model but trivially insecure when instantiated by any blockcipher. Keywords: Ideal-Cipher Model, Information-Theoretic Cryptography, Random-Oracle Model, Uninstantiability. [ABSTRACT FROM AUTHOR]

We present PEP, which is a new construction of a tweakable strong pseudo-random permutation. PEP uses a hash-encrypt-hash approach which has been recently used in the construction of HCTR. This approach is different from the encrypt-mask-encrypt approach of constructions such as CMC, EME and EME*. The general hash-encrypt-hash approach was earlier used by Naor-Reingold to provide a generic construction technique for an SPRP (but not a tweakable SPRP). PEP can be seen as the development of the Naor-Reingold approach into a fully specified mode of operation with a concrete security reduction for a tweakable strong pseudo-random permutation. HCTR is also based on the Naor-Reingold approach but its security bound is weaker than PEP. Compared to previous known constructions, PEP is the only known construction of tweakable SPRP which uses a single key, is efficiently parallelizable and can handle an arbitrary number of blocks. Keywords: mode of operation, tweakable encryption, strong pseudo-random permutation. [ABSTRACT FROM AUTHOR]

In this paper, we define and analyze a new blockcipher mode of operation for encryption, CENC, which stands for Cipher-based ENCryption. CENC has the following advantages: (1) beyond the birthday bound security, (2) security proofs with the standard PRP assumption, (3) highly efficient, (4) single blockcipher key, (5) fully parallelizable, (6) allows precomputation of keystream, and (7) allows random access. CENC is based on the new construction of "from PRPs to PRF conversion," which is of independent interest. Based on CENC and a universal hash-based MAC (Wegman-Carter MAC), we also define a new authenticated-encryption with associated-data scheme, CHM, which stands for CENC with Hash-based MAC. The security of CHM is also beyond the birthday bound. [ABSTRACT FROM AUTHOR]

MD5 is a well-known and widely-used cryptographic hash function. It has received renewed attention from researchers subsequent to the recent announcement of collisions found by Wang et al. [16]. To date, however, the method used by researchers in this work has been fairly difficult to grasp. In this paper we conduct a study of all attacks on MD5 starting from Wang. We explain the techniques used by her team, give insights on how to improve these techniques, and use these insights to produce an even faster attack on MD5. Additionally, we provide an "MD5 Toolkit" implementing these improvements that we hope will serve as an open-source platform for further research. Our hope is that a better understanding of these attacks will lead to a better understanding of our current collection of hash functions, what their strengths and weaknesses are, and where we should direct future efforts in order to produce even stronger primitives. Keywords: Cryptographic Hash Functions, Differential Cryptanalysis, MD5. [ABSTRACT FROM AUTHOR]