On the Collision and Preimage Resistance of Certain Two-Call Hash Functions

In this paper we present concrete collision and preimage attacks on a large class of compression function constructions making two calls to the underlying ideal primitives. The complexity of the collision attack is above the theoretical lower bound for constructions of this type, but below the birthday complexity; the complexity of the preimage attack, however, is equal to the theoretical lower bound. We also present undesirable properties of some of Stam’s compression functions proposed at CRYPTO ’08. We show that when one of the n-bit to n-bit components of the proposed 2n-bit to n-bit compression function is replaced by a fixed-key cipher in the Davies-Meyer mode, the complexity of finding a preimage would be 2 n/3. We also show that the complexity of finding a collision in a variant of the 3n-bits to 2n-bits scheme with its output truncated to 3n/2 bits is 2 n/2. The complexity of our preimage attack on this hash function is about 2 n . Finally, we present a collision attack on a variant of the proposed m + s-bit to s-bit scheme, truncated to s − 1 bits, with a complexity of O(1). However, none of our results compromise Stam’s security claims.

Security Analysis of Randomize-Hash-then-Sign Digital Signatures

At CRYPTO 2006, Halevi and Krawczyk proposed two randomized hash function modes and analyzed the security of digital signature algorithms based on these constructions. They showed that the security of signature schemes based on the two randomized hash function modes relies on properties similar to the second preimage resistance rather than on the collision resistance property of the hash functions. One of the randomized hash function modes was named the RMX hash function mode and was recommended for practical purposes. The National Institute of Standards and Technology (NIST), USA standardized a variant of the RMX hash function mode and published this standard in the Special Publication (SP) 800-106. In this article, we first discuss a generic online birthday existential forgery attack of Dang and Perlner on the RMX-hash-then-sign schemes. We show that a variant of this attack can be applied to forge the other randomize-hash-then-sign schemes. We point out practical limitations of the generic forgery attack on the RMX-hash-then-sign schemes. We then show that these limitations can be overcome for the RMX-hash-then-sign schemes if it is easy to find fixed points for the underlying compression functions, such as for the Davies-Meyer construction used in the popular hash functions such as MD5 designed by Rivest and the SHA family of hash functions designed by the National Security Agency (NSA), USA and published by NIST in the Federal Information Processing Standards (FIPS). We show an online birthday forgery attack on this class of signatures by using a variant of Dean’s method of finding fixed point expandable messages for hash functions based on the Davies-Meyer construction. This forgery attack is also applicable to signature schemes based on the variant of RMX standardized by NIST in SP 800-106. We discuss some important applications of our attacks and discuss their applicability on signature schemes based on hash functions with ‘built-in’ randomization. Finally, we compare our attacks on randomize-hash-then-sign schemes with the generic forgery attacks on the standard hash-based message authentication code (HMAC).

On Randomizing Hash Functions to Strengthen the Security of Digital Signatures

Halevi and Krawczyk proposed a message randomization algorithm called RMX as a front-end tool to the hash-then-sign digital signature schemes such as DSS and RSA in order to free their reliance on the collision resistance property of the hash functions. They have shown that to forge a RMX-hash-then-sign signature scheme, one has to solve a cryptanalytical task which is related to finding second preimages for the hash function. In this article, we will show how to use Dean’s method of finding expandable messages for finding a second preimage in the Merkle-Damgård hash function to existentially forge a signature scheme based on a t-bit RMX-hash function which uses the Davies-Meyer compression functions (e.g., MD4, MD5, SHA family) in 2 t/2 chosen messages plus 2 t/2 + 1 off-line operations of the compression function and similar amount of memory. This forgery attack also works on the signature schemes that use Davies-Meyer schemes and a variant of RMX published by NIST in its Draft Special Publication (SP) 800-106. We discuss some important applications of our attack.

Phosphine Resistance in the Rust Red Flour Beetle, Tribolium castaneum (Coleoptera: Tenebrionidae): Inheritance, Gene Interactions and Fitness Costs

The recent emergence of heritable high level resistance to phosphine in stored grain pests is a serious concern among major grain growing countries around the world. Here we describe the genetics of phosphine resistance in the rust red flour beetle Tribolium castaneum (Herbst), a pest of stored grain as well as a genetic model organism. We investigated three field collected strains of T. castaneum viz., susceptible (QTC4), weakly resistant (QTC1012) and strongly resistant (QTC931) to phosphine. The dose-mortality responses of their test- and inter-cross progeny revealed that most resistance was conferred by a single major resistance gene in the weakly (3.2x) resistant strain. This gene was also found in the strongly resistant (431x) strain, together with a second major resistance gene and additional minor factors. The second major gene by itself confers only 12-206x resistance, suggesting that a strong synergistic epistatic interaction between the genes is responsible for the high level of resistance (431x) observed in the strongly resistant strain. Phosphine resistance is not sex linked and is inherited as an incompletely recessive, autosomal trait. The analysis of the phenotypic fitness response of a population derived from a single pair inter-strain cross between the susceptible and strongly resistant strains indicated the changes in the level of response in the strong resistance phenotype; however this effect was not consistent and apparently masked by the genetic background of the weakly resistant strain. The results from this work will inform phosphine resistance management strategies and provide a basis for the identification of the resistance genes.

Building indifferentiable compression functions from the PGV compression functions

Preneel, Govaerts and Vandewalle (PGV) analysed the security of single-block-length block cipher based compression functions assuming that the underlying block cipher has no weaknesses. They showed that 12 out of 64 possible compression functions are collision and (second) preimage resistant. Black, Rogaway and Shrimpton formally proved this result in the ideal cipher model. However, in the indifferentiability security framework introduced by Maurer, Renner and Holenstein, all these 12 schemes are easily differentiable from a fixed input-length random oracle (FIL-RO) even when their underlying block cipher is ideal. We address the problem of building indifferentiable compression functions from the PGV compression functions. We consider a general form of 64 PGV compression functions and replace the linear feed-forward operation in this generic PGV compression function with an ideal block cipher independent of the one used in the generic PGV construction. This modified construction is called a generic modified PGV (MPGV). We analyse indifferentiability of the generic MPGV construction in the ideal cipher model and show that 12 out of 64 MPGV compression functions in this framework are indifferentiable from a FIL-RO. To our knowledge, this is the first result showing that two independent block ciphers are sufficient to design indifferentiable single-block-length compression functions.

EPC: a provably secure permutation based compression function

The security of permutation-based hash functions in the ideal permutation model has been studied when the input-length of compression function is larger than the input-length of the permutation function. In this paper, we consider permutation based compression functions that have input lengths shorter than that of the permutation. Under this assumption, we propose a permutation based compression function and prove its security with respect to collision and (second) preimage attacks in the ideal permutation model. The proposed compression function can be seen as a generalization of the compression function of MD6 hash function.

On hash functions using checksums

We analyse the security of iterated hash functions that compute an input dependent checksum which is processed as part of the hash computation. We show that a large class of such schemes, including those using non-linear or even one-way checksum functions, is not secure against the second preimage attack of Kelsey and Schneier, the herding attack of Kelsey and Kohno and the multicollision attack of Joux. Our attacks also apply to a large class of cascaded hash functions. Our second preimage attacks on the cascaded hash functions improve the results of Joux presented at Crypto’04. We also apply our attacks to the MD2 and GOST hash functions. Our second preimage attacks on the MD2 and GOST hash functions improve the previous best known short-cut second preimage attacks on these hash functions by factors of at least 226 and 254, respectively. Our herding and multicollision attacks on the hash functions based on generic checksum functions (e.g., one-way) are a special case of the attacks on the cascaded iterated hash functions previously analysed by Dunkelman and Preneel and are not better than their attacks. On hash functions with easily invertible checksums, our multicollision and herding attacks (if the hash value is short as in MD2) are more efficient than those of Dunkelman and Preneel.

Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3-512

In this paper, we analyze the SHAvite-3-512 hash function, as proposed and tweaked for round 2 of the SHA-3 competition. We present cryptanalytic results on 10 out of 14 rounds of the hash function SHAvite-3-512, and on the full 14 round compression function of SHAvite-3-512. We show a second preimage attack on the hash function reduced to 10 rounds with a complexity of 2497 compression function evaluations and 216 memory. For the full 14-round compression function, we give a chosen counter, chosen salt preimage attack with 2384 compression function evaluations and 2128 memory (or complexity 2448 without memory), and a collision attack with 2192 compression function evaluations and 2128 memory.

Cryptanalysis of Tav-128 Hash Function

Many RFID protocols use cryptographic hash functions for their security. The resource constrained nature of RFID systems forces the use of light weight cryptographic algorithms. Tav-128 is one such 128-bit light weight hash function proposed by Peris-Lopez et al. for a low-cost RFID tag authentication protocol. Apart from some statistical tests for randomness by the designers themselves, Tav-128 has not undergone any other thorough security analysis. Based on these tests, the designers claimed that Tav-128 does not posses any trivial weaknesses. In this article, we carry out the first third party security analysis of Tav-128 and show that this hash function is neither collision resistant nor second preimage resistant. Firstly, we show a practical collision attack on Tav-128 having a complexity of 237 calls to the compression function and produce message pairs of arbitrary length which produce the same hash value under this hash function. We then show a second preimage attack on Tav-128 which succeeds with a complexity of 262 calls to the compression function. Finally, we study the constituent functions of Tav-128 and show that the concatenation of nonlinear functions A and B produces a 64-bit permutation from 32-bit messages. This could be a useful light weight primitive for future RFID protocols.

Cryptographic Hash Functions

In the modern era of information and communication technology, cryptographic hash functions play an important role in ensuring the authenticity, integrity, and nonrepudiation goals of information security as well as efficient information processing. This entry provides an overview of the role of hash functions in information security, popular hash function designs, some important analytical results, and recent advances in this field.

The Role of Second Generation Antiretroviral Drugs in HIV-1 Subtype B and non-B Variants Harboring Natural Polymorphisms and Drug Resistance Mutations.

Cette thèse traite de la résistance du VIH-1 aux antirétroviraux, en particulier de l'activité antivirale de plusieurs inhibiteurs non nucléosidiques de la transcriptase inverse (INNTI) ainsi que des inhibiteurs de protéase (IP). Nous avons exploré l’émergence et la spécificité des voies de mutations qui confèrent la résistance contre plusieurs nouveaux INNTI (étravirine (ETR) et rilpivirine (RPV)) (chapitres 2 et 3). En outre, le profil de résistance et le potentiel antirétroviral d'un nouvel IP, PL-100, est présenté dans les chapitres 4 et 5. Pour le premier projet, nous avons utilisé des sous-types B et non-B du VIH-1 pour sélectionner des virus résistants à ETR, et ainsi montré que ETR favorise l’émergence des mutations V90I, K101Q, E138K, V179D/E/F, Y181C, V189I, G190E, H221H/Y et M230L, et ce, en 18 semaines. Fait intéressant, E138K a été la première mutation à émerger dans la plupart des cas. Les clones viraux contenant E138K ont montré un faible niveau de résistance phénotypique à ETR (3,8 fois) et une diminution modeste de la capacité de réplication (2 fois) par rapport au virus de type sauvage. Nous avons également examiné les profils de résistance à ETR et RPV dans les virus contenant des mutations de résistance aux INNTI au début de la sélection. Dans le cas du virus de type sauvage et du virus contenant la mutation unique K103N, les premières mutations à apparaître en présence d’ETR ou de RPV ont été E138K ou E138G suivies d’autres mutations de résistance aux INNTI. À l’inverse, dans les mêmes conditions, le virus avec la mutation Y181C a évolué pour produire les mutations V179I/F ou A62V/A, mais pas E138K/G. L'ajout de mutations à la position 138 en présence de Y181C n'augmente pas les niveaux de résistance à ETR ou RPV. Nous avons également observé que la combinaison de Y181C et E138K peut conduire à un virus moins adapté par rapport au virus contenant uniquement Y181C. Sur la base de ces résultats, nous suggérons que les mutations Y181C et E138K peuvent être antagonistes. L’analyse de la résistance au PL-100 des virus de sous-type C et CRF01_AE dans les cellules en culture est décrite dans le chapitre 4. Le PL-100 sélectionne pour des mutations de résistance utilisant deux voies distinctes, l'une avec les mutations V82A et L90M et l'autre avec T80I, suivi de l’addition des mutations M46I/L, I54M, K55R, L76F, P81S et I85V. Une accumulation d'au moins trois mutations dans le rabat protéique et dans le site actif est requise dans chaque cas pour qu’un haut niveau de résistance soit atteint, ce qui démontre que le PL-100 dispose d'une barrière génétique élevée contre le développement de la résistance. Dans le chapitre 5, nous avons évalué le potentiel du PL-100 en tant qu’inhibiteur de protéase de deuxième génération. Les virus résistants au PL-100 émergent en 8-48 semaines alors qu’aucune mutation n’apparaît avec le darunavir (DRV) sur une période de 40 semaines. La modélisation moléculaire montre que la haute barrière génétique du DRV est due à de multiples interactions avec la protéase dont des liaison hydrogènes entre les groupes di-tétrahydrofuranne (THF) et les atomes d'oxygène des acides aminés A28, D29 et D30, tandis que la liaison de PL-100 est principalement basée sur des interactions polaires et hydrophobes délocalisées à travers ses groupes diphényle. Nos données suggèrent que les contacts de liaison hydrogène et le groupe di-THF dans le DRV, ainsi que le caractère hydrophobe du PL-100, contribuent à la liaison à la protéase ainsi qu’à la haute barrière génétique contre la résistance et que la refonte de la structure de PL-100 pour inclure un groupe di-THF pourrait améliorer l’activité antivirale et le profil de résistance.