Intel and AMD support the carry-less multiplication (CLMUL) instruction set in their x64 processors. We use CLMUL to implement an almost universal 64-bit hash family (CLHASH). We compare this new family with what might be the fastest almost universal family on x64 processors (VHASH). We find that CLHASH is at least 60 faster. We also compare CLHASH with a popular hash function designed for speed (Google’s CityHash). We find that CLHASH is 40 faster than CityHash on inputs larger than 64 bytes and just as fast otherwise.
In this work, we provide a software benchmark for a large range of 256-bit blockcipher-based hash functions. We instantiate the underlying blockcipher with AES, which allows us to exploit the recent AES instruction set (AESNI). Since AES itself only outputs 128 bits, we consider double-blocklength constructions, as well as (single-block-length) constructions based on RIJNDAEL- 256. Although we primarily target architectures supporting AES-NI, our framework has much broader applications by estimating the performance of these hash functions on any (micro-)architecture given AES-benchmark results. As far as we are aware, this is the first comprehensive performance comparison of multiblocklength hash functions in software. PCLMULQDQ, a new instruction that supports GF(2)[x] multiplication, was introduced by Intel in 2010. This instruction brings dramatic change to software implementation of multiplication in GF(2^m) fields. In this paper, we present improved Karatsuba formulae for multiplying two small binary polynomials, compare different strategies for PCLMULQDQ-based multiplication in the five GF(2^m) fields recommended by NIST and conclude the best design approaches to software implementation of GF(2)[x] multiplication. This paper describes a new method for efficient implementation of the Galois Counter Mode on general purpose processors. Our approach is based on three concepts: a) having a 64-bit carry-less multiplication instruction in the processor; b) a method for using this instruction to efficiently multiply binary polynomials of degree 127; c) a method for efficient reduction of a binary polynomial of degree 254, modulo the polynomial x^1^2^8+x^7+x^2+x+1 (which defines the finite field of the Galois Counter Mode). The two latter concepts can be used for writing an efficient and lookup-table free software implementation of the Galois Counter Mode, for processors that have a carry-less multiplication instruction. Our approach uses only a generic carry-less multiplication instruction, without any field-specific reduction logic, making the instruction applicable to multiple use cases, and therefore an appealing addition to the instruction set of a general purpose processor. This research played a significant role in the process that eventually led to adding a carry-less multiplication instruction (called PCLMULQDQ) to the Intel Architecture. PCLMULQDQ and six AES instructions are introduced in the new 2010 Intel Core processor family, based on the 32 nm Intel microarchitecture codename ''Westmere''. On the new Westmere processors, the software that implements the methods described here, computes AES-GCM more than six times faster than the current, lookup table-based, state-of-the-art implementation. This new capability adds motivation to using AES-GCM for high performance secure networking. In this paper we introduce new methods for computing constant-time variable-base point multiplications over the Galbraith-Lin-Scott (GLS) and the Koblitz families of elliptic curves. Using a left-to-right double-and-add and a right-to-left halve-and-add Montgomery ladder over a GLS curve, we present some of the fastest timings yet reported in the literature for point multiplication. In addition, we combine these two procedures to compute a multi-core protected scalar multiplication. Furthermore, we designed a novel regular ( )-adic scalar expansion for Koblitz curves. As a result, using the regular recoding approach, we set the speed record for a single-core constant-time point multiplication on standardized binary elliptic curves at the (128 )-bit security level. This paper presents an efficient and side-channel-protected software implementation of scalar multiplication for the standard National Institute of Standards and Technology (NIST) and Standards for Efficient Cryptography Group binary elliptic curves. The enhanced performance is achieved by leveraging Intel’s AVX architecture and utilizing the pclmulqdq processor instruction. The fast carry-less multiplication is further used to speed up the reduction on the Haswell platform. For the five NIST curves over (GF(2^m) ) with (m ) ( ) ( 163,233,283,409,571 ), the resulting scalar multiplication implementation is about 5–12 times faster than that of OpenSSL-1.0.1e, enhancing the ECDHE and ECDSA algorithms significantly. The availability of a new carry-less multiplication instruction in the latest Intel desktop processors significantly accelerates multiplication in binary fields and hence presents the opportunity for reevaluating algorithms for binary field arithmetic and scalar multiplication over elliptic curves. We describe how to best employ this instruction in field multiplication and the effect on performance of doubling and halving operations. Alternate strategies for implementing inversion and half-trace are examined to restore most of their competitiveness relative to the new multiplier. These improvements in field arithmetic are complemented by a study on serial and parallel approaches for Koblitz and random curves, where parallelization strategies are implemented and compared. The contributions are illustrated with experimental results improving the state-of-the-art performance of halving and doubling-based scalar multiplication on NIST curves at the 112- and 192-bit security levels and a new speed record for side-channel-resistant scalar multiplication in a random curve at the 128-bit security level. The algorithms presented in this work were implemented on Westmere and Sandy Bridge processors, the latest generation Intel microarchitectures. In this work, we present new arithmetic formulas for a projective version of the affine point representation ((x,x+y x), ) for (x 0, ) which leads to an efficient computation of the scalar multiplication operation over binary elliptic curves. A software implementation of our formulas applied to a binary Galbraith–Lin–Scott elliptic curve defined over the field ( F _ 2^ 254 ) allows us to achieve speed records for protected unprotected single multi-core random-point elliptic curve scalar multiplication at the 127-bit security level. When executed on a Sandy Bridge 3.4 GHz Intel Xeon processor, our software is able to compute a single multi-core unprotected scalar multiplication in 69,500 and 47,900 clock cycles, respectively, and a protected single-core scalar multiplication in 114,800 cycles. These numbers are improved by around 2 and 46 on the newer Ivy Bridge and Haswell platforms, respectively, achieving in the latter a protected random-point scalar multiplication in 60,000 clock cycles.