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.

Grøstl – a SHA-3 candidate

Grøstl is a SHA-3 candidate proposal. Grøstl is an iterated hash function with a compression function built from two fixed, large, distinct permutations. The design of Grøstl is transparent and based on principles very different from those used in the SHA-family. The two permutations are constructed using the wide trail design strategy, which makes it possible to give strong statements about the resistance of Grøstl against large classes of cryptanalytic attacks. Moreover, if these permutations are assumed to be ideal, there is a proof for the security of the hash function. Grøstl is a byte-oriented SP-network which borrows components from the AES. The S-box used is identical to the one used in the block cipher AES and the diffusion layers are constructed in a similar manner to those of the AES. As a consequence there is a very strong confusion and diffusion in Grøstl. Grøstl is a so-called wide-pipe construction where the size of the internal state is significantly larger than the size of the output. This has the effect that all known, generic attacks on the hash function are made much more difficult. Grøstl has good performance on a wide range of platforms and counter-measures against side-channel attacks are well-understood from similar work on the AES.

Grøstl - a SHA-3 candidate

Grøstl is a SHA-3 candidate proposal. Grøstl is an iterated hash function with a compression function built from two �fixed, large, distinct permutations. The design of Grøstl is transparent and based on principles very different from those used in the SHA-family. The two permutations are constructed using the wide trail design strategy, which makes it possible to give strong statements about the resistance of Grøstl against large classes of cryptanalytic attacks. Moreover, if these permutations are assumed to be ideal, there is a proof for the security of the hash function. Grøstl is a byte-oriented SP-network which borrows components from the AES. The S-box used is identical to the one used in the block cipher AES and the diffusion layers are constructed in a similar manner to those of the AES. As a consequence there is a very strong confusion and diffusion in Grøstl

SHA-3 Design and Cryptanalysis Report

The competition to select a new secure hash function standard SHA-3 was initiated in response to surprising progress in the cryptanalysis of existing hash function constructions that started in 2004. In this report we survey design and cryptanalytic results of those 14 candidates that remain in the competition, about 1.5 years after the competition started with the initial submission of the candidates in October 2008. Implementation considerations are not in the scope of this report. The diversity of designs is also reflected in the great variety of cryptanalytic techniques and results that were applied and found during this time. This report gives an account of those techniques and results.

FPGA Implementations of the Round Two SHA-3 Candidates

The second round of the NIST-run public competition is underway to find a new hash algorithm(s) for inclusion in the NIST Secure Hash Standard (SHA-3). This paper presents the full implementations of all of the second round candidates in hardware with all of their variants. In order to determine their computational efficiency, an important aspect in NIST's round two evaluation criteria, this paper gives an area/speed comparison of each design both with and without a hardware interface, thereby giving an overall impression of their performance in resource constrained and resource abundant environments. The implementation results are provided for a Virtex-5 FPGA device. The efficiency of the architectures for the hash functions are compared in terms of throughput per unit area. To the best of the authors' knowledge, this is the first work to date to present hardware designs which test for all message digest sizes (224, 256, 384, 512), and also the only work to include the padding as part of the hardware for the SHA-3 hash functions.

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.

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).

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.

Grøstl

The Grøstl Hash Function Grøstl is FAST Grøstl is PROVABLY SECURE Grøstl is SIDE-CHANNEL RESISTANT Grøstl is SIMPLE

Grøstl Addendum

This document is an addendum to the submission document of Grøstl, which was selected for the second round of NIST's SHA-3 competition. We stress that we do not change the specification of Grøstl. In other words, Grøstl is defined exactly as specified in the original submission document. In this document we mention a few alternative descriptions of our SHA-3 candidate Grøstl and describe recent analysis results on Grøstl.

Intermediate Status Report

This report was produced in partial fulfillment of contract ICT-2007-216676 (ECRYPT II), sponsored by the European Commission through the ICT Programme. The information in this paper is provided as is, and no warranty is given or implied that the information is fit for any particular purpose. The user thereof uses the information at its sole risk and liability. We present a short overview of the recent results on the five finalists for NIST's SHA-3 competition. The next five chapters treat each one of the finalists.

Rotational cryptanalysis of round-reduced Keccak

In this paper we attack round-reduced Keccak hash function with a technique called rotational cryptanalysis. We focus on Keccak variants proposed as SHA-3 candidates in the NIST’s contest for a new standard of cryptographic hash function. Our main result is a preimage attack on 4-round Keccak and a 5-round distinguisher on Keccak-f[1600] permutation — the main building block of Keccak hash function.

密码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。