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.

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.

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.

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.

Side Channel Analysis of Some Hash Based MACs: A Response to SHA-3 Requirements

The forthcoming NIST’s Advanced Hash Standard (AHS) competition to select SHA-3 hash function requires that each candidate hash function submission must have at least one construction to support FIPS 198 HMAC application. As part of its evaluation, NIST is aiming to select either a candidate hash function which is more resistant to known side channel attacks (SCA) when plugged into HMAC, or that has an alternative MAC mode which is more resistant to known SCA than the other submitted alternatives. In response to this, we perform differential power analysis (DPA) on the possible smart card implementations of some of the recently proposed MAC alternatives to NMAC (a fully analyzed variant of HMAC) and HMAC algorithms and NMAC/HMAC versions of some recently proposed hash and compression function modes. We show that the recently proposed BNMAC and KMDP MAC schemes are even weaker than NMAC/HMAC against the DPA attacks, whereas multi-lane NMAC, EMD MAC and the keyed wide-pipe hash have similar security to NMAC against the DPA attacks. Our DPA attacks do not work on the NMAC setting of MDC-2, Grindahl and MAME compression functions.

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.

密码Hash函数相关问题研究

密码Hash函数是信息安全密码学的一个重要研究内容，是一类广泛应用的密码算法，用于把任意长度的字符串压缩成特定长度的字符串，同时需要在各种应用环境下满足一定的安全要求如抗碰撞，抗原象等。Hash函数广泛应用于数字签名、可证明安全、密码算法的构造以及重要的安全协议中。对Hash函数进行研究、分析Hash函数的安全性、构造安全高效的Hash算法有着重要意义。 本文研究了Hash函数的安全性质、设计结构以及常用分析方法，研究了Hash函数扩散层部件的设计，并且对MAME压缩函数算法进行了分析，取得了如下研究结果： (1) 研究了密码Hash函数的安全性质、设计结构、设计原理和常用分析方法，归纳总结了51个SHA-3候选算法的设计特点、设计原理和实现效率，研究了最新的分析进展，总结了新的攻击方法如REBOUND攻击等。NIST仿照AES的征集过程的SHA-3竞赛，目标是选出新的Hash函数标准SHA-3。进入第一轮的候选算法有51个，经过筛选选出其中的14个作为当前第二轮的候选算法。这些新Hash算法是由世界各国密码学家精心设计，是Hash函数领域最新设计思想的集体展示，当中涌现出很多新的设计结构和设计方法，同时激励密码学家发展新的分析方法。 (2) 设计并实现了了有限域上的扩散层构造算法以及扩散层分支数测试的算法，并针对多元域上的扩散层矩阵，本文使用编码理论，利用GRS码和柯西矩阵等设计了多元域扩散层矩阵的构造算法；使用有限域上的高斯消元法和线性码的性质设计了多元域扩散层矩阵的分支数的检测；设计了高效的二元域扩散层矩阵分支数测试算法。 (3) 针对MAME压缩函数算法进行差分分析，MAME算法是SHA-3候选算法Lesamnta的前身，于CHES 2007上提出的面向硬件有效实现的Hash算法。本文利用差分攻击对MAME算法进行分析，首先针对MAME的结构性质利用对通用Feistel结构的攻击方法构造了22轮差分攻击，碰撞攻击的复杂度为2^97，（第二）原象攻击的复杂度为2^197；对23轮的差分攻击需要的预计算是2^64张表，每张表的大小为2^64；对24轮的差分攻击需要的预计算是2^128张表，每张表的大小为2^64。针对24轮差分攻击很大的内存复杂度，我们利用了算法的细节特性，改进了差分攻击，新的差分不需要预计算的辅助内存，（第二）原象的复杂度为2^224。

一种基于分组密码的hash函数

提出了一个基于分组密码的hash函数体制,它的rate小于1但却具有更高的效率,同时,这个hash函数可以使用不安全的压缩函数进行构造,降低了对压缩函数安全性的要求.首先,在黑盒子模型下对这个新的体制的安全性进行了证明,然后给出了能够用于构造该体制的使用分组密码构造的压缩函数,最后通过实验对比发现,新hash函数的速度比rate为1的hash函数快得多.实验结果表明,除了rate以外,密钥编排也是影响基于分组密码hash函数效率的重要因素,甚至比rate影响更大.该体制只有两个密钥,不需要进行大量的密钥扩展运算,大大提高了基于分组密码hash函数的效率,而且该体制可以使用现有的分组密码来构造.

压缩函数局部平衡度与Hash函数平衡度的关系研究

主要探讨了基于MD方式构造hash函数时平衡度的保持问题，说明了压缩函数满足何种条件时hash函数能够取得最好的平衡度，提出了局部平衡度的概念，并利用此概念解决了压缩函数局部平衡度与hash函数平衡度的关系问题．这对于未来的hash函数的设计有非常重要的意义．

Simple Load Balancing for Distributed Hash Tables

Distributed hash tables have recently become a useful building block for a variety of distributed applications. However, current schemes based upon consistent hashing require both considerable implementation complexity and substantial storage overhead to achieve desired load balancing goals. We argue in this paper that these goals can b e achieved more simply and more cost-effectively. First, we suggest the direct application of the "power of two choices" paradigm, whereby an item is stored at the less loaded of two (or more) random alternatives. We then consider how associating a small constant number of hash values with a key can naturally b e extended to support other load balancing methods, including load-stealing or load-shedding schemes, as well as providing natural fault-tolerance mechanisms.

Cluster-Based Optimizations for Distributed Hash Tables

We consider the problem of performing topological optimizations of distributed hash tables. Such hash tables include Chord and Tapestry and are a popular building block for distributed applications. Optimizing topologies over one dimensional hash spaces is particularly difficult as the higher dimensionality of the underlying network makes close fits unlikely. Instead, current schemes are limited to heuristically performing local optimizations finding the best of small random set of peers. We propose a new class of topology optimizations based on the existence of clusters of close overlay members within the underlying network. By constructing additional overlays for each cluster, a significant portion of the search procedure can be performed within the local cluster with a corresponding reduction in the search time. Finally, we discuss the effects of these additional overlays on spatial locality and other load balancing scheme.

Efficient Hash-Consing of Recursive Types

Efficient storage of types within a compiler is necessary to avoid large blowups in space during compilation. Recursive types in particular are important to consider, as naive representations of recursive types may be arbitrarily larger than necessary through unfolding. Hash-consing has been used to efficiently store non-recursive types. Deterministic finite automata techniques have been used to efficiently perform various operations on recursive types. We present a new system for storing recursive types combining hash-consing and deterministic finite automata techniques. The space requirements are linear in the number of distinct types. Both update and lookup operations take polynomial time and linear space and type equality can be checked in constant time once both types are in the system.