New post-quantum Key Encapsulation Mechanism (KEM) designs, evaluated as part of the NIST PQC standardization Project, pose challenging tradeoffs between communication bandwidth and computational overheads. Several KEM designs evaluated in Round-2 of the project are based on QC-MDPC codes. BIKE-2 uses the smallest communication bandwidth, but its key generation requires a costly polynomial inversion. In this paper, we provide details on the optimized polynomial inversion algorithm for QC-MDPC codes (originally proposed in the conference version of this work). This algorithm makes the runtime of BIKE-2 key generation tolerable. It brings a speedup of 11.4× over the commonly used NTL library, and 83.5× over OpenSSL. We achieve additional speedups by leveraging the latest Intel's Vector-PCLMULQDQ instructions, 14.3× over NTL and 103.9× over OpenSSL. Our algorithm and implementation were the reason that BIKE team chose BIKE-2 as the only scheme for its Round-3 specification (now called BIKE).

This paper demonstrates the use of new processor instructions VPMADD, intended to appear in the coming generation of Intel processors (codename "Cannon Lake"), in order to accelerate the newly proposed key encapsulation mechanism (KEM) named SIKE. SIKE is one of the submissions to the NIST standardization process on post-quantum cryptography, and is based on pseudo-random walks in supersingular isogeny graphs. While very small keys are the main advantage of SIKE, its extreme computational intensiveness makes it one of the slowest KEM proposals. Performance optimizations are needed. We address here the "Level 1" parameters that target 64-bit quantum security, and deemed sufficient for the NIST standardization effort. Thus, we focus on SIKE503 that operates over Fp2 with a 503-bit prime p. These short operands pose a significant challenge on using VPMADD effectively. We demonstrate several optimization methods to accelerate Fp, Fp2, and the elliptic curve arithmetic, and predict a potential speedup by a factor of 1.72x.

ZUC-256 is a Pseudo Random Number Generator (PRNG) that is proposed as a successor of ZUC-128. Similarly to ZUC-128 that is incorporated in the 128-EEA3 and 128-EIA3 encryption and integrity algorithms, ZUC-256 is designed to offer 256-bit security and to be incorporated in the upcoming encryption and authentication algorithm in 5G technologies. In this context software optimizations of ZUC-256 are desired. This paper proposes several ZUC-256 optimizations for x86 processors, especially, modern processors that have efficient AVX vectorization. Surprisingly, we also show that AES-NI can also be used for ZUC-256 and help creating constant-time implementations. Our results show speedup of up to 4.5 x(per key stream) when computational tasks are parallelized efficiently.

Polynomial multiplication over binary fields \mathbbF2nis a common primitive, used for example by current cryptosystems such as AES-GCM (with n=128). It also turns out to be a primitive for other cryptosystems, that are being designed for the Post Quantum era, with values n ≫ 128. Examples from the recent submissions to the NIST Post-Quantum Cryptography project, are BIKE, LEDAKem, and GeMSS, where the performance of the polynomial multiplications, is significant. Therefore, efficient polynomial multiplication over F2n, with large n, is a significant emerging optimization target. Anticipating future applications, Intel has recently announced that its future architecture (codename “Ice Lake”) will introduce a new vectorized way to use the current VPCLMULQDQ instruction. In this paper, we demonstrate how to use this instruction for accelerating polynomial multiplication. Our analysis shows a prediction for at least 2× speedup for multiplications with polynomials of degree 512 or more.

Distributed storage systems utilize erasure codes to reduce their storage costs while efficiently handling failures. Many of these codes (e. g., Reed-Solomon (RS) codes) rely on Galois Field (GF) arithmetic, which is considered to be fast when the field characteristic is 2. Nevertheless, some developments in the field of erasure codes offer new efficient techniques that require mostly XOR operations, and are thus faster than GF operations. Recently, Intel announced [1] that its future architecture (codename “Ice Lake”) will introduce new set of instructions called Galois Field New Instruction (GF-NI). These instructions allow software flows to perform vector and matrix multiplications over GF (28) on the wide registers that are available on the AVX512 architectures. In this paper, we explain the functionality of these instructions, and demonstrate their usage for some fast computations in GF(28). We also use the Intel®Intelligent Storage Acceleration Library (ISA-L) in order to estimate potential future improvement for erasure codes that are based on RS codes. Our results predict ≈ 1.4× speedup for vectorized multiplication, and 1.83× speedup for the actual encoding.

Multi-Prime (MP)RSA is an RSA construction in which the public modulus is a product of more than two primes, and its private key operations can be accelerated by using the Chinese Reminder Theorem (CRT). While MPRSA has been studied extensively, only limited information is found for other MP constructions, such as Paillier cryptosystem. This paper shows how to extend the security proofs for Quadratic Residue Problem (QRP), Higher Residuosity Problem (HRP) and Decisional Composite Residuosity Problem (DCRP), formulated for a two-primes modulus, to a MP setting. For the Paillier cryptosystem, we demonstrate how this technique can speed up decryption by more than 17x.

An acceptable way to assess the quality of an RNG (PRNG) is to apply a standard battery of statistical randomness tests to a sampled output. Such tests compare some observed properties of the sample to properties of a uniform distribution, with the hope to detect deviations from the expected behavior. Consider a (P)RNG that outputs M-bit values which, due to a failure or an attack, are coerced to a subset of {0, 1}Mof only 2nelements, for some n-n> 2-M, but the standard randomness tests do not necessarily detect this behavior. We show here deterministic M-bit sequences (M = 128) that belong to a subset of size 2n, but pass the DIEHARD Battery of Tests of Randomness [1] and the NIST Statistical Test Suite [2], even with a relatively small value of n = 29. To address the difficulty, we propose a detection method that is feasible even for large values of n (e.g., n = 64). As a practical example, we apply our method to rule out the existence of the speculative stealthy hardware Trojan that is discussed in [3].

The proliferating usage of cloud environments to store databases poses new challenges. Traditional encryption protects the user's data privacy, but prevents the server from executing computations on behalf of the user (client). By contrast, Partially Homomorphic Encryption schemes, such as the Paillier cryptosystem, facilitate some server queries but involve heavy computations that make them relatively slow. This paper shows a simple performance optimization for Paillier encryption. It significantly reduces the server side workload and can be deployed by the server unilaterally, while remaining transparent to the client. Our optimization trades modular multiplications with cheaper Montgomery Multiplications, by converting the database to a favourable format. We explore several techniques to accelerate the relevant Montgomery multiplications on current and future modern processor architectures, and demonstrate the resulting speed-ups by comparing to the current method implemented via the OpenSSL library. For example, on the latest Intel processor (Architecture Codename Skylake) our method speeds up aggregated queries by a factor of 4×.

Block cipher modes of operation provide a way to securely encrypt using a block cipher. The main factors in analyzing modes of operation are the \emph{level of security} achieved (chosen-plaintext security, authenticated encryption, nonce-misuse resistance, and so on) and \textit{performance}. When measuring the security level of a mode of operation, it does not suffice to consider asymptotics, and a concrete analysis is necessary. This is especially the case today, when encryption rates can be very high, and so birthday bounds may be approached or even reached. In this paper, we show that key-derivation at every encryption significantly improves the security bounds in many cases. We present a new key-derivation method that utilizes a \emph{truncated block cipher}, and show that this is far better than standard block-cipher based key derivation. We prove that by using our key derivation method, we obtain greatly improved bounds for many modes of operation, with a result that the lifetime of a key can be significantly extended. We demonstrate this for AES-CTR (CPA-security), AES-GCM (authenticated encryption) and AES-GCM-SIV (nonce-misuse resistance). Finally, we demonstrate that when using modern hardware with AES instructions (AES-NI), the performance penalty of deriving keys at each encryption is insignificant for most uses.

Adversaries with physical access to a target platform can perform cold boot or DMA attacks to extract sensitive data from the RAM. To prevent such attacks, hardware vendors announced respective processor extensions. AMD's extension SME will provide means to encrypt the RAM to protect security-relevant assets that reside there. The encryption will protect the user's content against passive eavesdropping. However, the level of protection it provides in scenarios that involve an adversary who cannot only read from RAM but also change content in RAM is less clear. This paper addresses the open research question whether encryption alone is a dependable protection mechanism in practice when considering an active adversary. To this end, we first build a software based memory encryption solution on a desktop system which mimics AMD's SME. Subsequently, we demonstrate a proof-of-concept fault attack on this system, by which we are able to extract the private RSA key of a GnuPG user. Our work suggests that transparent memory encryption is not enough to prevent active attacks.

In the growing heterogeneous Internet of Things market, which embraces a plurality of vendors and service providers, IP protection plays a central role. This paper proposes a process for the detection of IP theft in VLSI devices that exploits the internal test scan chains, designed for production test automation. The scan chains supply direct access to the internal registers in the device, enabling combinational analysis of the device logic. By using Boolean function learning methods, the learner creates a partial dependence graph of the internal flip-flops. The graph is further partitioned using the shared nearest neighbors graph clustering method, and individual blocks of combinational logic are isolated. These blocks can be matched with known building blocks that compose the original function. This enables reconstruction of the function implementation to the level of pipeline structure. The IP owner can compare the resulting structure with his own implementation to confirm whether an IP violation has occurred. We demonstrate the power of the presented approach with a test case of an open source Bitcoin SHA-256 accelerator, containing more than 80 000 registers. With the presented method, we discover the microarchitecture of the module, locate all the main components of the SHA-256 algorithm, and learn the module's flow control. In addition to the direct recognition of the IP content, we also demonstrate a combination of reverse engineering and watermark methods. We define a new watermark structure-pipeline-associated watermark (PAW), combined with pipeline stages that can be detected with the scan-based reverse engineering method.

Intel has recently announced a new set of processor instructions, dubbed AVX512IFMA, that carry out Integer Fused Multiply Accumulate operations. These instructions operate on 512-bit registers and compute eight independent 52-bit unsigned integer multiplications, to generate eight 104-bit products, and accumulate their low/high halves into 64-bit containers. Using these instructions requires that inputs are converted to (redundant form) radix 252, and outputs are converted to the desired representation. This paper demonstrates several techniques for leveraging the AVX512IFMA instructions in order to speed up big-integer multiplications. Although processors that support AVX512IFMA are not yet available at the time this paper is written, we show how currently available public tools can be used for estimating their potential performance benefits. For example, based on these tools, we expect a 2x speedup for 1024-bit integer multiplication, over the best currently available method.

This paper discusses the question of optimizing AES hardware designs, by using the composite field representation GF(24)2of the field GF(28), that underlies the definition of AES. Here, GF(24)2is the field extension of the ground field GF(24) with an extension polynomial of the form x2 + αx + β, where a and β are elements of field GF(24). Previous designs with such representations used α = 1, which seemingly leads to some obvious savings. By contrast, we seek the optimal designs among all the possibilities. Our designs are based on mapping the input, output, round keys, and the AES operations to and from any one of the 2880 possible representations of GF(28) as (24)2. For each representation, we also explore three options for the affine/invaffine constants, resulting in a total of 8640 possible designs. We identify the smallest area representations for AES encryption-only, decryption-only, and for unified encryptiondecryption. Surprisingly, the optimal representations in each case are different from each other. In addition, we identify six distinct representations that are optimal, based on operating-mode and AES pipeline depth. Among other results, we show here a set of high-bandwidth 16-byte AES datapaths with the extension polynomials of the form x2+ αx + β where α ≠ 1, showing that the a-priori obvious choice of using α = 1, does not necessarily lead to the best result. We provide the full details of all the designs possibilities, together with their respective area, based on 22nm CMOS implementation.

The first part of the talk discusses some potential implications of attacks on the system memory of a computing platform. We show that encryption to protect privacy is not necessarily sufficient to protect against active attacks. In the second part of the talk, we explore the Memory Encryption Engine, which is part of Intel's Software Guard Extensions (SGX) technology.

This article describes a technique for implementing the quicksort sorting algorithm. Our method ‘vectorizes’ the computations and leverages the capabilities of the advanced vector extensions (AVX) instructions, available on Intel Core processors, and of the AVX2 instructions that were introduced with Intel's recent architecture codename Haswell. Our solution offers several advantages when compared with other high-performance sorting implementations, such as the radix sort, as implemented in Intel IPP library, or the introsort, as implemented in the |$\hbox {C}{++}$| STL. In addition to sorting numeric arrays, our method can also be used to sort complex structures with numeric keys and even pointers to such structures.

Authenticated encryption schemes guarantee both privacy and integrity, and have become the default level of encryption in modern protocols. One of the most popular authenticated encryption schemes today is AES-GCM due to its impressive speed. The current CAESAR competition is considering new modes for authenticated encryption that will improve on existing methods. One property of importance that is being considered more today -- due to multiple real-life cases of faulty sources of randomness -- is that repeating nonces and IVs can have disastrous effects on security. A (full) nonce misuse-resistant authenticated encryption scheme has the property that if the same nonce is used to encrypt the same message twice, then the same ciphertext is obtained and so the fact that the same message was encrypted is detected. Otherwise, full security is obtained -- even if the same nonce is used for different messages. In this paper, we present a new fully nonce misuse-resistant authenticated encryption scheme that is based on carefully combining the GCM building blocks into the SIV paradigm of Rogaway and Shrimpton. We provide a full proof of security of our scheme, and an optimized implementation using the AES-NI and PCLMULQDQ instruction sets. We compare our performance to the highly optimized OpenSSL 1.0.2 implementation of GCM and show that our nonce misuse-resistant scheme is only 14% slower on Haswell architecture and 19% slower on Broadwell architecture. On Broadwell, GCM-SIV encryption takes only 0.92 cycles per byte, and GCM-SIV decryption is exactly the same as GCM decryption taking only 0.77 cycles per byte. In addition, we compare to other optimized authenticated-encryption implementations carried out by Bogdanov et al., and conclude that our mode is very competitive. Beyond being very fast, our new mode of operation uses the same building blocks as GCM and so existing hardware and software can be utilized to easily deploy GCM-SIV. We conclude that GCM-SIV is a viable alternative to GCM, providing full nonce misuse-resistance at little cost.

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure computation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao's garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.

This paper proposes a set of mechanisms for enhancing the security of the generalized MDC-2 mode of operation. The MDC-2 mode is used for constructing a double length hash function, using block cipher building blocks, and is believed to provide some collision resistance. Recently, several attacks on MDC-2 have been published - collision, first and second pre-image attacks, with complexity below the ideal. In this paper we analyze the root-cause of these attacks, as applied to the generalized MDC-2 mode, and propose techniques for mitigating them. By mitigating we mean that with our amendments the attacks are either not applicable, or their complexity is pushed to ideal.

End-to-end communication encryption is considered necessary for protecting the privacy of user data in the Internet. Only a small fraction of all Internet traffic, however, is protected today. The primary reason for this neglect is economic, mainly security protocol speed and cost. In this paper we argue that recent advances in the implementation of cryptographic algorithms can make general purpose processors capable of encrypting packets at line rates. This implies that the Internet can be gradually transformed to an information delivery infrastructure where all traffic is encrypted and authenticated. We justify our claim by presenting technologies that accelerate end-to-end encryption and authentication by a factor of 6 and a high performance TLS 1.2 protocol implementation that takes advantage of these innovations. Our implementation is available in the public domain for experimentation.