In this paper we present a novel solution to address the problem of potential malicious circuitry on FPGA. This method is based on an a technique of structure extraction which consider the infection of an all lot. This structure is related to the design (place and route, power grid\dots) of the integrated circuits which composes the lot. In case of additional circuitry this design will be modify and the extracted structure will be affected. After developing the extraction techniques we present a methodology to insert detection of hardware trojan and counterfeit in different IC manufacturing steps. At last an application example using 30 FPGA boards validate our extraction method. Finally, statistical tools are then applied on the experimental results to distinguish a genuine lot from an infected one and confirm the potential of detection the extracted structure.

Modern Intel processors use an undisclosed hash function to map memory lines into last-level cache slices. In this work we develop a technique for reverse-engineering the hash function. We apply the technique to a 6-core Intel processor and demonstrate that knowledge of this hash function can facilitate cache-based side channel attacks, reducing the amount of work required for profiling the cache by three orders of magnitude. We also show how using the hash function we can double the number of colours used for page-colouring techniques.

We present a hardware architecture for all building blocks required in polynomial ring based fully homomorphic schemes and use it to instantiate the somewhat homomorphic encryption scheme YASHE. Our implementation is the first FPGA implementation that is designed for evaluating functions on homomorphically encrypted data (up to a certain multiplicative depth) and we illustrate this capability by evaluating the SIMON-64/128 block cipher in the encrypted domain. Our implementation provides a fast polynomial operations unit using CRT and NTT for multiplication combined with an optimized memory access scheme; a fast Barrett like polynomial reduction method; an efficient divide and round unit required in the multiplication of ciphertexts and an efficient CRT unit. These building blocks are integrated in an instruction-set coprocessor to execute YASHE, which can be controlled by a computer for evaluating arbitrary functions (up to the multiplicative depth 44 and 128-bit security level). Our architecture was compiled for a single Virtex-7 XC7V1140T FPGA, where it consumes 23\% of registers, 53\% of LUTs, 53\% of DSP slices, and 38\% of BlockRAM memory. The implementation evaluates SIMON-64/128 in approximately 171.3s (at 143 MHz) and it processes 2048 ciphertexts at once giving a relative time of only 83.6 ms per block. This is 24.5 times faster than the leading software implementation on a 4-core Intel Core-i7 processor running at 3.4 GHz.

Homomorphic encryption methods provide a way to outsource computations to the cloud while protecting the confidentiality of the data. In order to deal with the large and growing data sets that are being processed nowadays, good encryption performance is an important step for practicality of homomorphic encryption methods. In this article, we study the encryption performance of the Paillier cryptosystem, a partially homomorphic cryptosystem that allows to perform sums on encrypted data without having to decrypt first. With a combination of both new and known methods, we increase the encryption performance by orders of magnitude compared to a naïve implementation. The new methods reduce the bottleneck of noise calculation by using pre-computed noise to generate new noise in a much faster way than by using standard methods.

Hardware implementations of cryptographic algorithms are vulnerable to natural and malicious faults. Concurrent Error Detection (CED) can be used to detect these faults. We present NREPO, a CED which does not require redundant computational resources in the design. Therefore, one can integrate it when computational resources are scarce or when the redundant resources are difficult to harness for CED. We integrate NREPO in a low-cost Advanced Encryption Standard (AES) implementation with 8-bit datapath. We show that NREPO has 25 and 50 times lower fault miss rate than robust code and parity, respectively. The area, throughput, and power are compared with other CEDs on 45nm ASIC. The hardware overhead of NREPO is 34.9%. The throughput and power are 271.6Mbps and 1579.3μW , respectively. One can also implement NREPO in other cryptographic algorithms.

In a celebrated paper published in 1951, von Neumann presented a simple procedure allowing to correct the bias of random sources. This device outputs bits at irregular intervals. However, cryptographic hardware is usually synchronous. This paper proposes a new building block called Pace Regulator, inserted between the randomness consumer and the von Neumann regulator to streamline the pace of random bits.

In the last few years, the field of lightweight cryptography has seen an influx in the number of block ciphers and hash functions being proposed. One of the metrics that define a good lightweight design is the energy consumed per unit operation of the algorithm. For block ciphers, this operation is the encryption of one plaintext. By studying the energy consumption model of a CMOS gate, we arrive at the conclusion that the total energy consumed during the encryption operation of an r-round unrolled architecture of any block cipher is a quadratic function in r. We then apply our model to 9 well known lightweight block ciphers, and thereby try to predict the optimal value of r at which an r-round unrolled architecture for a cipher is likely to be most energy efficient. We also try to relate our results to some physical design parameters like the signal delay across a round and algorithmic parameters like the number of rounds taken to achieve full diffusion of a difference in the plaintext/key.

Masking schemes based on tables recomputation are classical countermeasures against high-order side-channel attacks. Still, they are known to be attackable at order $d$ in the case the masking involves $d$ shares. In this work, we mathematically show that an attack of order strictly greater than $d$ can be more successful than an attack at order $d$. To do so, we leverage the idea presented by Tunstall, Whitnall and Oswald at FSE 2013: we exhibit attacks which exploit the multiple leakages linked to one mask during the recomputation of tables. Specifically, regarding first-order table recomputation, improved by a shuffled execution, we show that there is a window of opportunity, in terms of noise variance, where a novel highly multivariate third-order attack is more efficient than a classical bivariate second-order attack. Moreover, we show on the example of the high-order secure table computation presented by Coron at EUROCRYPT 2014 that the window of opportunity enlarges linearly with the security order $d$.

The challenges faced in securing embedded computing systems against multifaceted memory safety vulnerabilities have prompted great interest in the development of memory safety countermeasures. These countermeasures either provide protection only against their corresponding type of vulnerabilities, or incur substantial architectural modifications and overheads in order to provide complete safety, which makes them infeasible for embedded systems. In this paper, we propose M-MAP: a comprehensive system based on multi-factor memory authentication for complete memory safety, inspired by everyday user authentication factors. We examine certain crucial theoretical and practical implications of composing memory integrity verification and bounds checking protection schemes in a comprehensive system. Based on these implications, we implement M-MAP with hardware based memory integrity verification and software based bounds checking to achieve a balance between hardware modifications and performance. We demonstrate that M-MAP implemented on top of a lightweight out-of-order processor delivers complete memory safety with only $32\%$ performance overhead on average, and incurs minimal hardware modifications and area overhead.

The Partial Sum Attack is one of the most powerful attacks, independent of the key schedule, developed in the last 15 years against reduced-round versions of AES. In this paper, we introduce a slight improvement to the basic attack which lowers the number of chosen plaintexts needed to successfully mount it. Our version of the attack on 6-round AES can be carried out completely in practice, as we demonstrate providing a full implementation. We also detail the structure of our implementation, showing the performances we achieve.

At CHES 2001, Walter introduced the Big Mac attack against an implementation of RSA. It is an horizontal collision attack, based on the detection of common operands in two multiplications. The attack is very powerful since one single power trace of an exponentiation permits to recover all bits of the secret exponent. Moreover, the attack works with unknown or blinded input. The technique was later studied and improved by Clavier et alii and presented at INDOCRYPT 2012. At SAC 2013, Bauer et alii presented the first attack based on the Big Mac principle on implementations based on elliptic curves with simulation results. In this work, we improve the attack presented by Bauer et alii to considerably increase the success rate. Instead of comparing only two multiplications, the targeted implementation permits to compare many multiplications. We give experiment results with traces taken from a real target to prove the soundness of our attack. In fact, the experimental results show that the original Big Mac technique given by Walter was better that the technique given by Clavier et alii. With our experiments on a real target, we show that the theoretical improvements are not necessarily the more suitable methods depending on the targeted implementations.

We introduce a CUDA GPU library to accelerate evaluations with homomorphic schemes defined over polynomial rings enabled with a number of optimizations including algebraic techniques for efficient evaluation, memory minimization techniques, memory and thread scheduling and low level CUDA hand-tuned assembly optimizations to take full advantage of the mass parallelism and high memory bandwidth GPUs offer. The arithmetic functions constructed to handle very large polynomial operands using number-theoretic transform (NTT) and Chinese remainder theorem (CRT) based methods are then extended to implement the primitives of the leveled homomorphic encryption scheme proposed by Löpez-Alt, Tromer and Vaikuntanathan. To compare the performance of the proposed CUDA library we implemented two applications: the Prince block cipher and homomorphic sorting algorithms on two GPU platforms in single GPU and multiple GPU configurations. We observed a speedup of 25 times and 51 times over the best previous GPU implementation for Prince with single and triple GPUs, respectively. Similarly for homomorphic sorting we obtained 12-41 times speedup depending on the number and size of the sorted elements.

Template attacks and stochastic models are among the most powerful side-channel attacks. However, they can be computationally expensive when processing a large number of samples. Various compression techniques have been used very successfully to reduce the data dimensionality prior to applying template attacks, most notably Principal Component Analysis (PCA) and Fisher's Linear Discriminant Analysis (LDA). These make the attacks more efficient computationally and help the profiling phase to converge faster. We show how these ideas can also be applied to implement stochastic models more efficiently, and we also show that they can be applied and evaluated even for more than eight unknown data bits at once.

Computing discrete logarithms takes time. It takes time to develop new algorithms, choose the best algorithms, implement these algorithms correctly and efficiently, keep the system running for several months, and, finally, publish the results. In this paper, we present a highly performant architecture that can be used to compute discrete logarithms of Weierstrass curves defined over binary fields and Koblitz curves using FPGAs. We used the architecture to compute for the first time a discrete logarithm of the elliptic curve \texttt{sect113r1}, a previously standardized binary curve, using 10 Kintex-7 FPGAs. To achieve this result, we investigated different iteration functions, used a negation map, dealt with the fruitless cycle problem, built an efficient FPGA design that processes 900 million iterations per second, and we tended for several months the optimized implementations running on the FPGAs.

Pairing-based cryptography has exploded over the last decade, as this algebraic setting offers good functionality and efficiency. However, there is a huge security gap between how schemes are usually analyzed in the academic literature and how they are typically implemented. The issue at play is that there exist multiple types of pairings: Type-I called “symmetric” is typically how schemes are presented and proven secure in the literature, because it is simpler and the complexity assumptions can be weaker; however, Type-III called “asymmetric” is typically the most efficient choice for an implementation in terms of bandwidth and computation time. There are two main complexities when moving from one pairing type to another. First, the change in algebraic setting invalidates the original security proof. Second, there are usually multiple (possibly thousands) of ways to translate from a Type-I to a Type-III scheme, and the “best” translation may depend on the application. Our contribution is the design, development and evaluation of a new software tool, AutoGroup+, that automatically translates from Type-I to Type-III pairings. The output of AutoGroup+ is: (1) “secure” provided the input is “secure” and (2) optimal based on the user’s efficiency constraints (excluding software and run-time errors). Prior automation work for pairings was either not guaranteed to be secure or only partially automated and impractically slow. This work addresses the pairing security gap by realizing a fast and secure translation tool.

Binary eld multiplication is the most fundamental building block of binary eld Elliptic Curve Cryptography (ECC) and Galois/Counter Mode (GCM). Both bit-wise scanning and Look-Up Table (LUT) based methods are commonly used for binary eld multiplication. In terms of Side Channel Attack (SCA), bit-wise scanning exploits insecure branch operations which leaks information in a form of timing and power consumption. On the other hands, LUT based method is regarded as a relatively secure approach because LUT access can be conducted in a regular and atomic form. This ensures a constant time solution as well. In this paper, we conduct the SCA on the LUT based binary eld multiplication. The attack exploits the horizontal Correlation Power Analysis (CPA) on weights of LUT. We identify the operand with only a power trace of binary eld multiplication. In order to prevent SCA, we also suggest a mask based binary eld multiplication which ensures a regular and constant time solution without LUT and branch statements.

ECDSA is one of the most important public-key signature scheme, however it is vulnerable to lattice attack once a few bits of the nonces are leaked. To protect Elliptic Curve Cryptography (ECC) against Simple Power Analysis, many countermeasures have been proposed. Doubling and Additions of points on the given elliptic curve require several additions and multiplications in the base field and this number is not the same for the two operations. The idea of the atomicity protection is to use a fixed pattern, i.e. a small number of instructions and rewrite the two basic operations of ECC using this pattern. Dummy operations are introduced so that the different elliptic curve operations might be written with the same atomic pattern. In an adversary point of view, the attacker only sees a succession of patterns and is no longer able to distinguish which one corresponds to addition and doubling. Chevallier-Mames, Ciet and Joye were the first to introduce such countermeasure. In this paper, we are interested in studying this countermeasure and we show a new vulnerability since the ECDSA implementation succumbs now to C Safe-Error attacks. Then, we propose an effective solution to prevent against C Safe-Error attacks when using the Side-Channel Atomicity. The dummy operations are used in such a way that if a fault is introduced on one of them, it can be detected. Finally, our countermeasure method is generic, meaning that it can be adapted to all formulae. We apply our methods to different formulae presented for side-channel Atomicity.

Pseudorandom number generators (PRNGs) are very important for EPC Class 1 Generation 2 (EPC C1 G2) Radio Frequency Identification (RFID) systems. A PRNG is able to provide a 16-bit random number that is used in many commands of the EPC C1 G2 standard, and it can also be used in future security extensions of the EPC C1 G2 standard, such as mutual authentication protocols between the readers and tags. In this paper, we investigate efficient ASIC hardware implementations of Warbler (a lightweight PRNG), and demonstrate that Warbler can meet the area and power consumption requirements in passive RFID systems. Warbler is built upon three nonlinear feedback shift registers (NLFSRs) and four WG-5 transformation modules. We employ two design options to implement Warbler and three different compilation methods to further optimize the area, maximum operating frequency, and power consumption. We can achieve an area of 498 GEs after the place and route phase in a CMOS 65nm ASIC, with a maximum frequency of 1430 MHz and a total power consumption of 1.239uW at 100 KHz. Accordingly, an area of 534 GEs after the place and route phase, with a maximum frequency of 250 MHz and a total power consumption of 0.296 uW at 100 KHz can be obtained in a CMOS 130nm ASIC. Our results show that the LFSR counter based design is better than the binary counter-based one in terms of area and power consumption. In addition, we show that the areas of WG-5 transformation look-up tables depend on the specific decimation values.

Fault and power attacks are two common ways of extracting secrets from tamper-resistant chips. Although several protections have been proposed to thwart these attacks, resistant designs usually claim significant area or speed overheads. Furthermore, circuit-level countermeasures are usually not reconfigurable at runtime. This paper exploits the AES’ algorithmic features to propose low-cost and low-latency protections. We provide Verilog and FPGA implementation details. Using our design, real-life applications can be configured during runtime to meet the user’s needs and the system’s constraints.

In this work, we present a generic open-source software framework that can evaluate the correctness and performance of homomorphic encryption software. Our framework, called HEtest, automates the entire process of a test: generation of data for testing (such as circuits and inputs), execution of a test, comparison of performance to an insecure baseline, statistical analysis of the test results, and production of a LaTeX report. To illustrate the capability of our framework, we present a case study of our analysis of the open-source HElib homomorphic encryption software. We stress though that HEtest is written in a modular fashion, so it can easily be adapted to test any homomorphic encryption software.

This paper describes a new multiplication algorithm, particularly suited to lightweight microprocessors when one of the operands is known in advance. The method uses backtracking to find a multiplicationfriendly encoding of the operand known in advance. A 68HC05 microprocessor implementation shows that the new algorithm indeed yields a twofold speed improvement over classical multiplication for 128-byte numbers.

As part of the revelations about the NSA activities, the notion of interdiction has become known to the public: the interception of deliveries to manipulate hardware in a way that backdoors are introduced. Manipulations can occur on the firmware or at hardware level. With respect to hardware, FPGAs are particular interesting targets as they can be altered by manipulating the corresponding bitstream which configures the device. In this paper, we demonstrate the first successful real-world FPGA hardware Trojan insertion into a commercial product. On the target device, a FIPS-140-2 level 2 certified USB flash drive from Kingston, the user data is encrypted using AES-256 in XTS mode, and the encryption/decryption is processed by an off-the-shelf SRAM-based FPGA. Our investigation required two reverse-engineering steps, related to the proprietary FPGA bitstream and to the firmware of the underlying ARM CPU. In our Trojan insertion scenario the targeted USB flash drive is intercepted before being delivered to the victim. The physical Trojan insertion requires the manipulation of the SPI flash memory content, which contains the FPGA bitstream as well as the ARM CPU code. The FPGA bitstream manipulation alters the exploited AES-256 algorithm in a way that it turns into a linear function which can be broken with 32 known plaintext-ciphertext pairs. After the manipulated USB flash drive has been used by the victim, the attacker is able to obtain all user data from the ciphertexts. Our work indeed highlights the security risks and especially the practical relevance of bitstream modification attacks that became realistic due to FPGA bitstream manipulations.

The references [9,3,1] treat timing attacks on RSA with CRT and Montgomery's multiplication algorithm in unprotected implementations. It has been widely believed that exponent blinding would prevent any timing attack on RSA. At cost of significantly more timing measurements this paper extends the before-mentioned attacks to RSA with CRT when Montgomery's multiplication algorithm and exponent blinding are applied. Simulation experiments are conducted, which confirm the theoretical results. Effective countermeasures exist. In particular, the attack efficiency is higher than in the previous version [12] while large parts of both papers coincide.

The encryption mode of the Tweakable Block Cipher (TBC) of the SCREAM Authenticated Cipher is implemented in the MSP430 microcontroller. Assembly language versions of the TBC are prepared using both precomputed tweak keys and tweak keys computed “on-the-fly.” Both versions are compared against published results for the assembly language version of SCREAM on the ATMEL AVR microcontroller, and against the C reference implementation in terms of performance and size. The assembly language version using precomputed tweak keys achieves a speedup of 1.7 and memory savings of 9 percent over the reported SCREAM implementation in the ATMEL AVR. The assembly language version using tweak keys computed “on-the-fly” achieves a speedup of 1.6 over the ATMEL AVR version while reducing memory usage by 15 percent.

Physically unclonable functions (PUFs) provide data that can be used for cryptographic purposes: on the one hand randomness for the initialization of random-number generators; on the other hand individual fingerprints for unique identification of specific hardware components. However, today's off-the-shelf personal computers advertise randomness and individual fingerprints only in the form of additional or dedicated hardware. This paper introduces a new set of tools to investigate whether intrinsic PUFs can be found in PC components that are not advertised as containing PUFs. In particular, this paper investigates AMD64 CPU registers as potential PUF sources in the operating-system kernel, the bootloader, and the system BIOS; investigates the CPU cache in the early boot stages; and investigates shared memory on Nvidia GPUs. This investigation found non-random non-fingerprinting behavior in several components but revealed usable PUFs in Nvidia GPUs.

Motivated by the development of Side-Channel Analysis (SCA) countermeasures which can provide security up to a certain order, defeating higher-order attacks has become amongst the most challenging issues. For instance, Threshold Implementation (TI) which nicely solves the problem of glitches in masked hardware designs is able to avoid first-order leakages. Hence, its extension to higher orders aims at counteracting SCA attacks at higher orders, that might be limited to univariate scenarios. Although with respect to the number of traces as well as sensitivity to noise the higher the order, the harder it is to mount the attack, a d-order TI design is vulnerable to an attack at order d+1. In this work we look at the feasibility of higher-order attacks on first-order TI from another perspective. Instead of increasing the order of resistance by employing higher-order TIs, we go toward introducing structured randomness into the implementation. Our construction, which is a combination of masking and hiding, is dedicated to TI designs and deals with the concept of "affine equivalence" of Boolean functions. Such a combination hardens a design practically against higher-order attacks so that these attacks cannot be successfully mounted. We show that the area overhead of our construction is paid off by its ability to avoid higher-order leakages to be practically exploitable.

There is a significant effort in building lightweight cryptographic operations, yet the proposed solutions are typically single-purpose modules that can implement a single functionality. In contrast, we propose BitCryptor, a multi-purpose, bit-serialized compact processor for cryptographic applications on reconfigurable hardware. The proposed crypto engine can perform pseudo-random number generation, strong collision-resistant hashing and variable-key block cipher encryption. The hardware architecture utilizes SIMON, a recent lightweight block cipher, as its core. The complete engine uses a bit-serial design methodology to minimize the area. Implementation results on the Xilinx Spartan-3 s50 FPGA show that the proposed architecture occupies 95 slices (187 LUTs, 102 registers), which is 10$\times$ smaller than the nearest comparable multi-purpose design. BitCryptor is also smaller than the majority of recently proposed lightweight single-purpose designs. Therefore, it is a very efficient cryptographic IP block for resource-constrained domains, providing a good performance at a minimal area overhead.

In WISA'13, a novel lightweight block cipher named LEA was released. This algorithm has certain useful features for hardware and software implementations, i.e., simple ARX operations, non-S-box architecture, and 32-bit word size. These features are realized in several platforms for practical usage with high performance and low overheads. In this paper, we further improve 128-, 192- and 256-bit LEA encryption for low-end embedded processors. Firstly we present speed optimization methods. The methods split a 32-bit word operation into four byte-wise operations and avoid several rotation operations by taking advantages of efficient byte-wise rotations. Secondly we reduce the code size to ensure minimum code size.We nd the minimum inner loops and optimize them in an instruction set level. After then we construct the whole algorithm in a partly unrolled fashion with reasonable speed. Finally, we achieved the fastest LEA implementations, which improves performance by 10.9% than previous best known results. For size optimization, our implemen- tation only occupies the 280B to conduct LEA encryption. After scaling, our implementation achieved the smallest ARX implementations so far, compared with other state-of-art ARX block ciphers such as SPECK and SIMON.

In this paper, we show efficient implementations of binary field multiplication over ARMv8. We exploit an advanced 64-bit polynomial multiplication (\texttt{PMULL}) supported by ARMv8 and conduct multiple levels of asymptotically faster Karatsuba multiplication. Finally, our method conducts binary field multiplication within 57 clock cycles for B-251. Our proposed method on ARMv8 improves the performance by a factor of $5.5$ times than previous techniques on ARMv7.

We present DPA attacks on an ARM Cortex-A8 processor running at 1 GHz. This high-end processor is typically found in portable devices such as phones and tablets. In our case, the processor sits in a single board computer and runs a full-fledged Linux operating system. The targeted AES implementation is bitsliced and runs in constant time and constant flow. We show that, despite the complex hardware and software, high clock frequencies and practical measurement issues, the implementation can be broken with DPA starting from a few thousand measurements of the electromagnetic emanation of a decoupling capacitor near the processor. To harden the bitsliced implementation against DPA attacks, we mask it using principles of hardware gate-level masking. We evaluate the security of our masked implementation against first-order and second-order attacks. Our experiments show that successful attacks require roughly two orders of magnitude more measurements.

Lattice-based cryptography has been proposed as a postquantum public-key cryptosystem. In this paper, we present a masked ring-LWE decryption implementation resistant to first-order side-channel attacks. Our solution has the peculiarity that the entire computation is performed in the masked domain. This is achieved thanks to a new, bespoke masked decoder implementation. The output of the ring-LWE decryption are Boolean shares suitable for derivation of a symmetric key. We have implemented a hardware architecture of the masked ring-LWE processor on a Virtex-II FPGA, and have performed side channel analysis to confirm the soundness of our approach. The area of the protected architecture is around $2000$ LUTs, a $20\%$ increase with respect to the unprotected architecture. The protected implementation takes $7478$ cycles to compute, which is only a factor $\times2.6$ larger than the unprotected implementation.

In this paper we investigate relations between several masking schemes. We show that the Ishai--Sahai--Wagner private circuits construction is closely related to Threshold Implementations and the Trichina gate. The implications of this observation are manifold. We point out a higher-order weakness in higher-order Threshold Implementations, suggest a mitigation and provide new sharings that use a lower number of input shares.

Side-channel attacks have been a real threat against many critical embedded systems that rely on cryptographic algorithms as their security engine. A commonly used algorithmic countermeasure, random masking, incurs large execution delay and resource overhead. The other countermeasure, operation shuffling or permutation, can mitigate side-channel leakage effectively with minimal overhead. In this paper, we target utilizing the independence among operations in cryptographic algorithms and randomizing their execution order. We design a tool to automatically detect such independence between statements at the source code level and devise an algorithm for automatic operation shuffling. We test our algorithm on the new SHA3 standard, Keccak. Results show that the tool has effectively implemented operation-shuffling to reduce the side-channel leakage significantly, and therefore can guide automatic secure cryptographic software implementations against differential power analysis attacks.

Emerging applications such as the Internet of Things require security solutions that are small and low cost, yet feature solid protection against a wide range of sophisticated attacks. Lightweight cryptographic schemes such as the Speck cipher that was recently proposed by the NSA aim to solve some of these challenges. However, before using Speck in any practical application, sound protection against side-channel attacks must be in place. In this work, we propose a bit-serialized implementation of Speck, to achieve minimal area footprint. We further propose a Speck core that is provably secure against first-order side-channel attacks using a threshold implementation technique which depends on secure multiparty computation. The resulting design is a tiny crypto core that provides AES-like security in under 45 slices on a low-cost Xilinx Spartan 3 FPGA. The first-order side-channel resistant version of the same core needs less than 100 slices. The security of the protected core is validated by state-of-the-art side-channel leakage detection tests.

Among other threats, secure components are subjected to physical attacks whose aim is to recover the secret information they store. Most of the work carried out to protect these components generally consists in developing protections (or countermeasures) taken one by one. But this ``countermeasure-centered'' approach drastically decreases the performance of the chip in terms of power, speed and availability. In order to overcome this limitation, we propose a complementary approach: smart dynamic management of the whole set of countermeasures embedded in the component. Two main specifications for such management are required in a real world application (for example, a conditional access system for Pay-TV): it has to provide capabilities for the chip to distinguish between attacks and normal use cases (without the help of a human being and in a robust but versatile way); it also has to be based on mechanisms which dynamically find a trade-off between security and performance. In this article, a prototype which enables such security management is described. The solution is based on a double-processor architecture: one processor embeds a representative set of countermeasures (and mechanisms to define their parameters) and executes the application code. The second processor, on the same chip, applies a given security strategy, but without requesting sensitive data from the first processor. The chosen strategy is based on fuzzy logic reasoning to enable the designer to describe, using a fairly simple formalism, both the attack paths and the normal use cases. A proof of concept has been proposed for the smart card part of a conditional access for Pay-TV, but it could easily be fine-tuned for other applications.

In hardware, substitution boxes for block ciphers can be saved already masked in the implementation. The masks must be chosen under two constraints: their number is determined by the implementation area and their properties should allow to deny high-order zero-offset attacks of highest degree. First, we show that this problem translates into a known trade-off in Boolean functions, namely finding correlation-immune functions of lowest weight. For instance, this allows to prove that a byte-oriented block cipher such as AES can be protected with only $16$ mask values against zero-offset correlation power attacks of orders $1$, $2$ and $3$. Second, we study $d$th-order correlation-immune Boolean functions $\F_2^n \to \F_2$ of low-weight and exhibit such functions of minimal weight found by a satisfiability modulo theory tool. In particular, we give the minimal weight for $n \leq 10$. Some of these results were not known previously, such as the minimal weight for $(n=9, d=4)$ and $(n=10, d \in \{4,5,6\})$. These results set new bounds for the minimal number of lines of binary orthogonal arrays. In particular, we point out that the minimal weight $w_{n,d}$ of a $d$th-order correlation-immune function might not be increasing with the number of variables $n$.

In this paper, we present novel randomized techniques to enhance Montgomery powering ladder. The proposed techniques increase the resistance against side-channel attacks and especially recently published correlation collision attacks in the horizontal setting. The first of these operates by randomly changing state such that the difference between registers varies, unpredictably, between two states. The second algorithm takes a random walk, albeit tightly bounded, along the possible addition chains required to compute an exponentiation. We also generalize the Montgomery powering ladder and present randomized (both left-to-right and right-to-left) $m$-ary exponentiation algorithms.

A Eurocrypt 2013 paper "Security evaluations beyond computing power: How to analyze side-channel attacks you cannot mount?" by Veyrat-Charvillon, Gérard, and Standaert proposed a "Rank Estimation Algorithm" (REA) to estimate the difficulty of finding a secret key given side-channel information from independent subkeys, such as the 16 key bytes in AES-128 or the 32 key bytes in AES-256. The lower and upper bounds produced by the algorithm are far apart for most key ranks. The algorithm can produce tighter bounds but then becomes exponentially slower; it also becomes exponentially slower as the number of subkeys increases. This paper introduces two better algorithms for the same problem. The first, the "Extended Rank Estimation Algorithm" (EREA), is an extension of REA using statistical sampling as a second step to increase the speed of tightening the bounds on the rank. The second, the "Polynomial Rank Outlining Algorithm" (PRO), is a new approach to computing the rank. PRO can handle a much larger number of subkeys efficiently, is easy to implement in a computer-algebra system such as Sage, and produces much tighter bounds than REA in less time.

Security mechanisms to protect our systems and data from malicious adversaries have become essential. Strong encryption algorithms are an important building block of these solutions. However, each application has its own requirements and it is not always possible to find a cipher that meets them all. This work compares unrolled combinatorial hardware implementations of six lightweight block ciphers, along with an AES implementation as a baseline. Up until now, the majority of such ciphers were designed for area-constrained environments where speed is often not crucial, but recently the need for single-cycle, low-latency block ciphers with limited area requirements has arisen to build security architectures for embedded systems. Our comparison shows that some designers are already on this track, but a lot of work still remains to be done.

A persistent problem with program execution, despite numerous mitigation attempts, is its inherent vulnerability to the injection of malicious code. Equally unsolved is the susceptibility of firmware to reverse engineering, which undermines the manufacturer's code confidentiality. We propose an approach that solves both kinds of security problems employing instruction-level code encryption combined with the use of a physical unclonable function (PUF). Our novel Secure Execution PUF-based Processor (SEPP) architecture is designed to minimize the attack surface, as well as performance impact, and requires no significant changes to the development process. This is possible based on a tight integration of a PUF directly into the processor's instruction pipeline. Furthermore, cloud scenarios and distributed embedded systems alike inherently depend on remote execution; our approach supports this, as the secure execution environment needs not to be locally available at the developers site. We implemented an FPGA-based prototype based on the OpenRISC Reference Platform. To assess our results, we performed a security analysis of the processor and evaluated the performance impact of the encryption. We show that the attack surface is significantly reduced compared to previous approaches while the performance penalty is at a reasonable factor of about 1.5.

Elliptic Curve Cryptography (ECC) is a popular tool to construct public-key crypto-systems. The security of ECC is based on the hardness of the elliptic curve discrete logarithm problem (ECDLP). Implementing and analyzing the performance of the best known methods to solve the ECDLP is useful to assess the security of ECC and choose security parameters in practice. We present a novel many-core hardware architecture implementing the parallel version of Pollard's rho algorithm to solve the ECDLP. This architecture results in a speed-up of almost 300% compared to the state of the art and we use it to estimate the monetary cost of solving the Certicom ECCp-131 challenge using FPGAs.

Homomorphic encryption allows computation on encrypted data and makes it possible to securely outsource computational tasks to untrusted environments. However, all proposed schemes are quite inefficient and homomorphic evaluation of ciphertexts usually takes several seconds on high-end CPUs, even for evaluating simple functions. In this work we investigate the potential of FPGAs for speeding up those evaluation operations. We propose an architecture to accelerate schemes based on the ring learning with errors (RLWE) problem and specifically implemented the somewhat homomorphic encryption scheme YASHE, which was proposed by Bos, Lauter, Loftus, and Naehrig in 2013. Due to the large size of ciphertexts and evaluation keys, on-chip storage of all data is not possible and external memory is required. For efficient utilization of the external memory we propose an efficient double-buffered memory access scheme and a polynomial multiplier based on the number theoretic transform (NTT). For the parameter set (n=16384,log_2(q)=512) capable of evaluating 9 levels of multiplications, we can perform a homomorphic addition in 48.67 and a homomorphic multiplication in 0.94 ms.

This paper presents extremely fast algorithms for code-based public-key cryptography, including full protection against timing attacks. For example, at a 2^128 security level, this paper achieves a reciprocal decryption throughput of just 60493 cycles (plus cipher cost etc.) on a single Ivy Bridge core. These algorithms rely on an additive FFT for fast root computation, a transposed additive FFT for fast syndrome computation, and a sorting network to avoid cache-timing attacks.

We consider how to perform privacy-preserving analyses on private data from different data providers and containing personal information of many different individuals. We combine differential privacy and secret sharing in the same system to protect the privacy of both the data providers and the individuals. We have implemented a prototype of this combination and the overhead of adding differential privacy to secret sharing is small enough to be usable in practice.

Higher-order side-channel attacks are becoming amongst the major interests of academia as well as industry sector. It is indeed being motivated by the development of countermeasures which can prevent the leakages up to certain orders. As a concrete example, threshold implementation (TI) as an efficient way to realize Boolean masking in hardware is able to avoid first-order leakages. Trivially, the attacks conducted at second (and higher) orders can exploit the corresponding leakages hence devastating the provided security. Hence, the extension of TI to higher orders was being expected which has been presented at ASIACRYPT 2014. Following its underlying univariate settings it can provide security at higher orders, and its area and time overheads naturally increase with the desired security order. In this work we look at the feasibility of higher-order attacks on first-order TI from another perspective. Instead of increasing the order of resistance by employing higher-order TIs, we realize the first-order TI designs following the principles of a power-equalization technique dedicated to FPGA platforms, that naturally leads to hardening higher-order attacks. We show that although the first-order TI designs, which are additionally equipped by the power-equalization methodology, have significant area overhead, they can maintain the same throughput and more importantly can avoid the higher-order leakages to be practically exploitable by up to 1 billion traces.

In his keynote speech at CHES 2004, Kocher advocated that side-channel attacks were an illustration that formal cryptography was not as secure as it was believed because some assumptions (e.g., no auxiliary information is available during the computation) were not modeled. This failure is caused by formal methods' focus on models rather than implementations. In this paper we present formal methods and tools for designing protected code and proving its security against power analysis. These formal methods avoid the discrepancy between the model and the implementation by working on the latter rather than on a high-level model. Indeed, our methods allow us (a) to automatically insert a power balancing countermeasure directly at the assembly level, and to prove the correctness of the induced code transformation; and (b) to prove that the obtained code is balanced with regard to a reasonable leakage model, and we show how to characterize the hardware to use the resources which maximize the relevancy of the model. The tools implementing our methods are then demonstrated in a case study in which we generate a provably protected PRESENT implementation for an 8-bit AVR smartcard.

PUF-based key generators have been widely considered as a root-of-trust in digital systems. They typically require an error-correcting mechanism (e.g. based on the code-offset method) for dealing with bit errors between the enrollment and reconstruction of keys. When the used PUF does not have full entropy, entropy leakage between the helper data and the device-unique key material can occur. If the entropy level of the PUF becomes too low, the PUF-derived key can be attacked through the publicly available helper data. In this work we provide several solutions for preventing this entropy leakage for PUFs suffering from bias. The methods proposed in this work pose no limit on the amount of bias that can be tolerated, which solves an important open problem for PUF-based key generation. Additionally, the solutions are all evaluated based on reliability, efficiency, leakage and reusability showing that depending on requirements for the key generator different solutions are preferable.

Over the last years lattice-based cryptography has received much attention due to versatile average-case problems like Ring-LWE or Ring-SIS that appear to be intractable by quantum computers. But despite of promising constructions, only few results have been published on implementation issues on very constrained platforms. In this work we therefore study and compare implementations of Ring-LWE encryption and the bimodal lattice signature scheme (BLISS) on an 8-bit Atmel ATxmega128 microcontroller. Since the number theoretic transform (NTT) is one of the core components in implementations of lattice-based cryptosystems, we review the application of the NTT in previous implementations and present an improved approach that significantly lowers the runtime for polynomial multiplication. Our implementation of Ring-LWE encryption takes 27 ms for encryption and 6.7 ms for decryption. To compute a BLISS signature, our software takes 329 ms and 88 ms for verification. These results outperform implementations on similar platforms and underline the feasibility of lattice-based cryptography on constrained devices.

Having ciphers that provide confidentiality and authenticity, that are fast in software and efficient in hardware, these are the goals of the CAESAR authenticated encryption competition. In this paper, the promising CAESAR candidate Ascon is implemented in hardware and optimized for different typical applications to fully explore Ascon's design space. Thus, we are able to present hardware implementations of Ascon suitable for RFID tags, Wireless Sensor Nodes, Embedded Systems, and applications that need maximum performance. For instance, we show that an Ascon implementation with a single unrolled round transformation is only 7 kGE large, but can process up to 5.5 Gbit/sec of data (0.75 cycles/byte), which is already enough to encrypt a Gigabit Ethernet connection. Besides, Ascon is not only fast and small, it can also be easily protected against DPA attacks. A threshold implementation of Ascon just requires about 8 kGE of chip area, which is only 3.1 times larger than the unprotected low-area optimized implementation.

Evoked by the increasing need to integrate side-channel countermeasures into security-enabled commercial devices, evaluation labs are seeking a standard approach that enables a fast, reliable and robust evaluation of the side-channel vulnerability of the given products. To this end, standardization bodies such as NIST intend to establish a leakage assessment methodology fulfilling these demands. One of such proposals is the Welch's t-test, which is being put forward by Cryptography Research Inc., and is able to relax the dependency between the evaluations and the device's underlying architecture. In this work, we deeply study the theoretical background of the test's different flavors, and present a roadmap which can be followed by the evaluation labs to efficiently and correctly conduct the tests. More precisely, we express a stable, robust and efficient way to perform the tests at higher orders. Further, we extend the test to multivariate settings, and provide details on how to efficiently and rapidly carry out such a multivariate higher-order test. Including a suggested methodology to collect the traces for these tests, we point out practical case studies where different types of t-tests can exhibit the leakage of supposedly secure designs.

We propose a lightweight coprocessor for 16-bit microcontrollers that implements high security elliptic curve cryptography. It uses a 283-bit Koblitz curve and offers 140-bit security. Koblitz curves offer fast point multiplications if the scalars are given as specific $\tau$-adic expansions, which results in a need for conversions between integers and $\tau$-adic expansions. We propose the first lightweight variant of the conversion algorithm and, by using it, introduce the first lightweight implementation of Koblitz curves that includes the scalar conversion. We also include countermeasures against side-channel attacks making the coprocessor the first lightweight coprocessor for Koblitz curves that includes a set of countermeasures against timing attacks, SPA, DPA and safe-error fault attacks. When the coprocessor is synthesized for 130 nm CMOS, it has an area of only 4,323 GE. When clocked at 16 MHz, it computes one 283-bit point multiplication in 98 ms with a power consumption of 97.70 $\mu$W, thus, consuming 9.56 $\mu$J of energy.

Side channel collision attacks are a powerful method to exploit side channel leakage. Otherwise than a few exceptions, collision attacks usually combine leakage from distinct points in time, making them inherently bivariate. This work introduces the notion of near collisions to exploit the fact that values depending on the same sub-key can have similar while not identical leakage. We show how such knowledge can be exploited to mount a key recovery attack. The presented approach has several desirable features when compared to other state-of-the-art collision attacks: Near collision attacks are truly univariate. They have low requirements on the leakage functions, since they work well for leakages that are linear in the bits of the targeted intermediate state. They are applicable in the presence of masking countermeasures if there exist distinguishable leakages, as in the case of leakage squeezing. Results are backed up by a broad range of simulations for unprotected and masked implementations, as well as an analysis of the measurement set provided by DPA Contest v4.

We describe three contributions regarding the Soft Analytical Side-Channel Attacks (SASCA) introduced at Asiacrypt 2014. First, we compare them with Algebraic Side-Channel Attacks (ASCA) in a noise-free simulated setting. We observe that SASCA allow more efficient key recoveries than ASCA, even in this context (favorable to the latter). Second, we describe the first working experiments of SASCA against an actual AES implementation. Doing so, we analyse their profiling requirements, put forward the significant gains they provide over profiled Differential Power Analysis (DPA) in terms of number of traces needed for key recoveries, and discuss the specificities of such concrete attacks compared to simulated ones. Third, we evaluate the distance between SASCA and DPA enhanced with computational power to perform enumeration, and show that the gap between both attacks can be quite reduced in this case. Therefore, our results bring interesting feedback for evaluation laboratories. They suggest that in several relevant scenarios (e.g. attacks exploiting many known plaintexts), taking a small margin over the security level indicated by standard DPA with enumeration should be sufficient to prevent more elaborate attacks such as SASCA. By contrast, SASCA may remain the only option in more extreme scenarios (e.g. attacks with unknown plaintexts/ciphertexts or against leakage-resilient primitives). We conclude by recalling the algorithmic dependency of the latter attacks, and therefore that our conclusions are specific to the AES.

Extensive use of third party IP cores (e.g., HDL, netlist) and open source tools in the FPGA application design and development process in conjunction with the inadequate bitstream protection measures have raised crucial security concerns in the past for reconfigurable hardware systems. Designing high fidelity and secure methodologies for FPGAs are still infancy and in particular, there are almost no concrete methods/techniques that can ensure trust in FPGA applications not entirely designed and/or developed in a trusted environment. This work strongly suggests the need for an anomaly detection capability within the FPGAs that can continuously monitor the behavior of the underlying FPGA IP cores and the communication activities of IP cores with other IP cores or peripherals for any abnormalities. To capture this need, we propose a technique called FIDelity Enhancing Security (FIDES) methodology for FPGAs that uses a combination of access control policies and behavior learning techniques for anomaly detection. FIDES essentially comprises of two components: (i) {\em Trusted Wrappers}, a layer of monitors with sensing capabilities distributed across the FPGA fabric; these wrappers embed the output of each IP core $i$ with a tag $\tau_i$ according to the pre-defined security policy $\Pi$ and also verifies the embeddings of each input to the IP core to detect any violation of policies. The use of tagging and tracking enables us to capture the normal interactions of each IP core with its environment (e.g., other IP cores, memory, OS or I/O ports). {\em Trusted Wrappers} also monitors the statistical properties exhibited by each IP core module on execution such as power consumption, number of clock cycles and timing variations to detect any anomalous operations; (ii) a {\em Trusted Anchor} that monitors the communication between the IP cores and the peripherals with regard to the centralized security policies $\Psi$ as well as the statistical properties produced by the peripherals. We target FIDES architecture on a Xilinx Zynq 7020 device implemented with a red-black system comprising of sensitive and non-sensitive IP cores. Our results show that FIDES implementation leads to only 1-2\% overhead in terms of the logic resources per wrapper and incurs minimal latency per wrapper for tag verification and embedding. On the other hand, as compared to the baseline implementation, when all the communications within the system are routed to the Trusted Anchor for centralized policy checking and verification, a latency of 1.5X clock cycles is observed; this clearly manifests the advantage of using distributed wrappers as opposed to centralized policy checking.

Advanced modern processors support Single Instruction Multiple Data (SIMD) instructions (e.g. Intel-AVX, ARM-NEON) and a massive body of research on vector-parallel implementations of modular arithmetic, which are crucial components for modern public-key cryptography ranging from RSA, ElGamal, DSA and ECC, have been conducted. In this paper, we introduce a novel Double Operand Scanning (DOS) method to speed-up multi-precision squaring with non-redundant representations on SIMD architecture. The DOS technique partly doubles the operands and computes the squaring operation without Read-After-Write (RAW) dependencies between source and destination variables. Furthermore, we presented Karatsuba Cascade Operand Scanning (KCOS) multiplication and Karatsuba Double Operand Scanning (KDOS) squaring by adopting additive and subtractive Karatsuba's methods, respectively. The proposed multiplication and squaring methods are compatible with separated Montgomery algorithms and these are highly efficient for RSA crypto system. Finally, our proposed multiplication/squaring, separated Montgomery multiplication/squaring and RSA encryption outperform the best-known results by 22/41\%, 25/33\% and 30\% on the Cortex-A15 platform.

Physical Unclonable Functions (PUFs), as novel lightweight hardware security primitives, provide a higher level security with lower power and area overhead in comparison with traditional cryptographic solutions. However, it has been demonstrated that PUFs are vulnerable to model building attacks, especially those using linear additive functions such as Arbiter PUF (APUF) and k-sum PUF as building units. Nevertheless, both APUFs and k-sum PUFs are highly desirable security primitives, especially for authentication, because they are capable of producing a huge number of challenge response pairs (CRPs) and can be easily integrated into silicon. In this paper, we actually rely on the demonstrated vulnerability of PUFs to model building attacks as well as the relative ease with which this can be achieved to develop a new parameter-based authentication protocol based on obfuscating challenges sent to PUFs and their subsequent recovery. We show, using statistical analysis and model building attacks using published approaches, that constructing a model using machine learning techniques are infeasible when our proposed method is employed. Finally, we also demonstrate that our challenge obfuscation and recovery method can be successfully used for secure key exchange between two parties.

In this work we focus on tailoring and optimizing the computational Private Information Retrieval (cPIR) scheme proposed in WAHC 2014 for efficient execution on graphics processing units (GPUs). Exploiting the mass parallelism in GPUs is a commonly used approach in speeding up cPIRs. Our goal is to eliminate the efficiency bottleneck of the Doröz et al construction which would allow us to take advantage of its excellent bandwidth performance. To this end, we develop custom code to support polynomial ring operations and extend them to realize the evaluation functions in an optimized manner on high end GPUs. Specifically, we develop optimized CUDA code to support large degree/large coefficient polynomial arithmetic operations such as modular multiplication/reduction, and modulus switching. Moreover, we choose same prime numbers for both the CRT domain representation of the polynomials and for the modulus switching implementation of the somewhat homomorphic encryption scheme. This allows us to combine two arithmetic domains, which reduces the number of domain conversions and permits us to perform faster arithmetic. Our implementation achieves 14-34 times speedup for index comparison and 4-18 times speedup for data aggregation compared to a pure CPU software implementation. tion compared to a pure CPU software implementation.

Higher-order side-channel attacks are able to break the security of cryptographic implementations even if they are protected with masking countermeasures. In this paper, we derive the best possible distinguishers (High-Order Optimal Distinguishers or HOOD) against masking schemes under the assumption that the attacker can profile. Our exact derivation admits simple approximate expressions for high and low noise and shows to which extent the optimal distinguishers reduce to known attacks in the case where no profiling is possible. From these results, we can explain theoretically the empirical outcome of recent works on second-order distinguishers. In addition, we extend our analysis to any order and to the application to masked tables precomputation. Our results give some insight on which distinguishers have to be considered in the security analysis of cryptographic devices.

Side channel and fault attacks take advantage from the fact that the behavior of crypto implementations can be observed and provides hints that simplify revealing keys. In a real word a lot of devices, that are identical to the target device, can be attacked before attacking the real target to increase the success of the attack. Their package can be opened and their electromagnetic radiation and structure can be analyzed. Another example of how to improve significantly the success rate of attacks is the measurement of the difference of the side channel leakage of two identical devices, one of these devices being the target, using the Wheatstone bridge measurement setup. Here we propose to individualize the electrical circuit of cryptographic devices in order to prevent attacks that use identical devices: attacks, that analyze the structure of devices identical to the target device in a preparation phase; usual side channel attacks, that use always the same target device for collecting many traces, and attacks that use two identical devices at the same time for measuring the difference of side-channel leakages. The proposed individualization can prevent such attacks because the power consumption and the electromagnetic radiation of devices with individualized electrical circuit are individualized while providing the same functionality. We implemented three individualized ECC designs that provide exactly the same cryptographic function on a Spartan-6 FPGA. These designs differ from each other in a single block only, i.e. in the field multiplier. The visualization of the routed design and measurement results show clear differences in the topology, in the resources consumed as well as in the power and electromagnetic traces. We show that the influence of the individualized designs on the power traces is comparable with the influence of inputs. These facts show that individualizing of electrical circuits of cryptographic devices can be exploited as a protection mechanism. We envision that this type of protection mechanism is relevant if an attacker has a physical access to the cryptographic devices, e.g. for wireless sensor networks from which devices can easily be stolen for further analysis in the lab.

Achieving high reliability across environmental variations and over aging in physical unclonable functions (PUFs) remains a challenge for PUF designers. The conventional method to improve PUF reliability is to use powerful error correction codes (ECC) to correct the errors in the raw response from the PUF core. Unfortunately, these ECC blocks generally have high VLSI overheads, which scale up quickly with the error correction capability. Alternately, researchers have proposed techniques to increase the reliability of the PUF core, and thus significantly reduce the required strength (and complexity) of the ECC. One method of increasing the reliability of the PUF core is to use normally detrimental IC aging effects to reinforce the desired (or "golden") response of the PUF by altering the PUF circuit characteristics permanently and hence making the PUF more reliable. In this work, we present a PUF response reinforcement technique based on hot carrier injection (HCI) which can reinforce the PUF golden response in short stress times (i.e., tens of seconds), without impacting the surrounding circuits, and that has high permanence (i.e., does not degrade significantly over aging). We present a self-contained HCI-reinforcement-enabled PUF circuit based on sense amplifiers (SA) which autonomously self-reinforces with minimal external intervention. We have fabricated a custom ASIC testchip in 65nm bulk CMOS with the proposed PUF design. Measured results show high reliability across environmental variations and accelerated aging, as well as good uniqueness and randomness. For example, 1600 SA elements, after being HCI stressed for 125s, show 100% reliability (zero errors) across ~20% voltage variations a temperature range of -20C to 85C.

In the last years code-based cryptosystems were established as promising alternatives for asymmetric cryptography since they base their security on well-known NP-hard problems and still show decent performance on a wide range of computing platforms. The main drawback of code-based schemes, including the popular proposals by McEliece and Niederreiter, are the large keys whose size is inherently determined by the underlying code. In a very recent approach, Misoczki et al. proposed to use quasi-cyclic MDPC (QC-MDPC) codes that allow for a very compact key representation. In this work, we investigate novel implementations of the McEliece scheme using such QC-MDPC codes tailored for embedded devices, namely a Xilinx Virtex-6 FPGA and an 8-bit AVR microcontroller. In particular, we evaluate and improve different approaches to decode QC-MDPC codes. Besides competitive performance for encryption and decryption on the FPGA, we achieved a very compact implementation on the microcontroller using only 4,800 and 9,600 bits for the public and secret key at 80 bits of equivalent symmetric security.

The verification of an ECDSA signature requires a double-base scalar multiplication, an operation of the form $k \cdot G + l \cdot Q$ where $G$ is a generator of a large elliptic curve group of prime order $n$, $Q$ is an arbitrary element of said group, and $k$, $l$ are two integers in the range of $[1, n-1]$. We introduce in this paper an area-optimized VLSI design of a Prime-Field Arithmetic Unit (PFAU) that can serve as a loosely-coupled or tightly-coupled hardware accelerator in a system-on-chip to speed up the execution of double-base scalar multiplication. Our design is optimized for twisted Edwards curves with an efficiently computable endomorphism that allows one to reduce the number of point doublings by some 50% compared to a conventional implementation. An example for such a special curve is $-x^2 + y^2 = 1 + x^2y^2$ over the 207-bit prime field $F_p$ with $p = 2^{207} - 5131$. The PFAU prototype we describe in this paper features a ($16 \times 16$)-bit multiplier and has an overall silicon area of 5821 gates when synthesized with a $0.13\mu$ standard-cell library. It can be clocked with a frequency of up to 50 MHz and is capable to perform a constant-time multiplication in the mentioned 207-bit prime field in only 198 clock cycles. A complete double-base scalar multiplication has an execution time of some 365k cycles and requires the pre-computation of 15 points. Our design supports many trade-offs between performance and RAM requirements, which is a highly desirable property for future Internet-of-Things (IoT) applications.

As Keccak has been selected as the new SHA-3 standard, Message Authentication Code (MAC) (MAC-Keccak) using a secret key will be widely used for integrity checking and authenticity assurance. Recent works have shown the feasibility of side-channel attacks against software implementations of MAC-Keccak to retrieve the key, with the security assessment of hardware implementations remaining an open problem. In this paper, we present a comprehensive and practical side-channel analysis of a hardware implementation of MAC-Keccak on FPGA. Different from previous works, we propose a new attack method targeting the first round output of MAC-Keccak rather than the linear operation $\theta$ only. The results on sampled power traces show that the unprotected hardware implementation of MAC-Keccak is vulnerable to side-channel attacks, and attacking the nonlinear operation of MAC-Keccak is very effective. We further discuss countermeasures against side-channel analysis on hardware MAC-Keccak. Finally, we discuss the impact of the key length on side-channel analysis and compare the attack complexity between MAC-Keccak and other cryptographic algorithms.

This paper deals with the protection of elliptic curve scalar multiplications against side-channel analysis by using the atomicity principle. Unlike other atomic patterns, we investigate new formul\ae{} with same cost for both doubling and addition. This choice is particularly well suited to evaluate double scalar multiplications with the Straus-Shamir trick. Since fixed point multiplications highly benefit from this trick, our pattern allows a huge improvement in this case as other atomic patterns cannot use it. Surprisingly, in other cases our choice remains very efficient. Besides, we also point out a security threat when the curve parameter $a$ is null and propose an even more efficient pattern in this case.

Side-channel attacks are one of the major concerns for security-enabled applications as they make use of information leaked by the physical implementation of the underlying cryptographic algorithm. Hence, reducing the side-channel leakage of the circuits realizing the cryptographic primitives is amongst the main goals of circuit designers. In this work we present a novel circuit concept, which decouples the main power supply from an internal power supply that is used to drive a single logic gate. The decoupling is done with the help of buffering capacitances integrated into semiconductor. We also introduce – compared to the previously known schemes – an improved decoupling circuit which reduces the crosstalk from the internal to the external power supply. The result of practical side-channel evaluation on a prototype chip fabricated in a 150nm CMOS technology shows a high potential of our proposed technique to reduce the side-channel leakages.

This paper describes a bug in the implementation of the Rabin-Williams digital signature in the \texttt{Crypto++} framework. The bug is in the misuse of blinding technique that is aimed at preventing timing attacks on the digital signature system implementation, but eventually results in an opportunity to find the private key having only two different signatures of the same message. The CVE identifier of the issue is \texttt{CVE-2015-2141}.

Masking is a widely used countermeasure to protect block cipher implementations against side-channel attacks. The principle is to split every sensitive intermediate variable occurring in the computation into d + 1 shares, where d is called the masking order and plays the role of a security parameter. A masked implementation is then said to achieve dth-order security if any set of d (or less) intermediate variables does not reveal key-dependent information. At CHES 2010, Rivain and Prouff have proposed a higher-order masking scheme for AES that works for any arbitrary order d. This scheme, and its subsequent extensions, are based on an improved version of the shared multiplication processing published by Ishai et al. at CRYPTO 2003. This improvement enables better memory/timing performances but its security relies on the refreshing of the masks at some points in the algorithm. In this paper, we show that the method proposed at CHES 2010 to do such mask refreshing introduces a security flaw in the overall masking scheme. Specically, we show that it is vulnerable to an attack of order d/2 + 1 whereas the scheme is supposed to achieve dth-order security. After exhibiting and analyzing the flaw, we propose a new solution which avoids the use of mask refreshing, and we prove its security. We also provide some implementation trick that makes our proposed solution, not only secure, but also faster than the original scheme.

TinyECC 2.0 is an open source library for Elliptic Curve Cryptography (ECC) in wireless sensor networks. This paper analyzes the side channel susceptibility of TinyECC 2.0 on a LOTUS sensor node platform. In our work we measured the electromagnetic (EM) emanation during computation of the scalar multiplication using 56 different configurations of TinyECC 2.0. All of them were found to be vulnerable, but to a different degree. The different degrees of leakage include adversary success using (i) Simple EM Analysis (SEMA) with a single measurement, (ii) SEMA using averaging, and (iii) Multiple-Exponent Single-Data (MESD) with a single measurement of the secret scalar. It is extremely critical that in 30 TinyECC 2.0 configurations a single EM measurement of an ECC private key operation is sufficient to simply read out the secret scalar. MESD requires additional adversary capabilities and it affects all TinyECC 2.0 configurations, again with only a single measurement of the ECC private key operation. These findings give evidence that in security applications a configuration of TinyECC 2.0 should be chosen that withstands SEMA with a single measurement and, beyond that, an addition of appropriate randomizing countermeasures is necessary.

In this article, we propose a new comparison metric, the figure of adversarial merit (FOAM), which combines the inherent security provided by cryptographic structures and components with their implementation properties. To the best of our knowledge, this is the first such metric proposed to ensure a fairer comparison of cryptographic designs. We then apply this new metric to meaningful use cases by studying Substitution-Permutation Network permutations that are suited for hardware implementations, and we provide new results on hardware-friendly cryptographic building blocks. For practical reasons, we considered linear and differential attacks and we restricted ourselves to fully serial and round-based implementations. We explore several design strategies, from the geometry of the internal state to the size of the S-box, the field size of the diffusion layer or even the irreducible polynomial defining the finite field. We finally test all possible strategies to provide designers an exhaustive approach in building hardware-friendly cryptographic primitives (according to area or FOAM metrics), also introducing a model for predicting the hardware performance of round-based or serial-based implementations. In particular, we exhibit new diffusion matrices (circulant or serial) that are surprisingly more efficient than the current best known, such as the ones used in AES, LED and PHOTON.

Since the discovery of simple power attacks, the cryptographic research community has developed significantly more advanced attack methods. The idea behind most algorithms remains to perform a statistical analysis by correlating the power trace obtained when executing a cryptographic primitive to a key-dependent guess. With the advancements of cryptographic countermeasures, it is not uncommon that sophisticated (higher-order) power attacks require computation on many millions of power traces in order to find the desired correlation. In this paper, we study the computational aspects of calculating the most widely used correlation coefficient: the Pearson product-moment correlation coefficient. We study various time-memory trade-off techniques which apply specifically to the cryptologic setting and present methods to extend already completed computations using incremental versions. Moreover, we show how this technique can be applied to second-order attacks, reducing the attack cost significantly when adding new traces to an existing dataset. We also present methods which allow one to split the potentially huge trace set into smaller, more manageable chunks in order to reduce the memory requirements. Our concurrent implementation of these techniques highlights the benefits of this approach as it allows efficient computations on power measurements consisting of hundreds of gigabytes on a single modern workstation.

A common countermeasure to thwart side-channel analysis attacks is algorithmic masking. For this, algorithms that mix Boolean and arithmetic operations need to either apply two different masking schemes with secure conversions or use dedicated arithmetic units that can process Boolean masked values. Several proposals have been published that can realize these approaches securely and efficiently in software. But to the best of our knowledge, no hardware design exists that fulfills relevant properties such as efficiency and security at the same time. In this paper, we present two design strategies to realize a secure and efficient arithmetic adder for Boolean-masked values. First, we introduce an architecture based on the ripple-carry adder that targets low-cost applications. The second architecture is based on a pipelined Kogge-Stone adder and targets high-performance applications. In particular, all our implementations adopt the threshold implementation approach to improve their resistance against SCA attacks even in the presence of glitches. We evaluated the security of our designs practically against SCA using a non-specific statistical t-test. Based on our analysis, we show that our constructions not only achieve resistance against first- and (univariate) second-order attacks but also require fewer random bits per operation compared to any existing software-based approach.

After being introduced in 2009, the first fully homomorphic encryption (FHE) scheme has created significant excitement in academia and industry. Despite rapid advances in the last 6 years, FHE schemes are still not ready for deployment due to an efficiency bottleneck. Here we introduce a custom hardware accelerator optimized for a class of reconfigurable logic to bring LTV based somewhat homomorphic encryption (SWHE) schemes one step closer to deployment in real-life applications. The accelerator we present is connected via a fast PCIe interface to a CPU platform to provide homomorphic evaluation services to any application that needs to support blinded computations. Specifically we introduce a number theoretical transform based multiplier architecture capable of efficiently handling very large polynomials. When synthesized for the Xilinx Virtex 7 family the presented architecture can compute the product of large polynomials in under $6.25$~msec making it the fastest multiplier design of its kind currently available in the literature and is more than 102 times faster than a software implementation. Using this multiplier we can compute a relinearization operation in $526$ msec. When used as an accelerator, for instance, to evaluate the AES block cipher, we estimate a per block homomorphic evaluation performance of $442$~msec yielding performance gains of $28.5$ and $17$ times over similar CPU and GPU implementations, respectively.

The single-shot collision attack on RSA proposed by Hanley et al. is studied focusing on the difference between two operands of multipliers. There are two consequences. Firstly, designing order of operands can be a cost-effective countermeasure. We show a concrete example in which operand order determines success and failure of the attack. Secondly, countermeasures can be ineffective if the asymmetric leakage is considered. In addition to the main results, the attack by Hanley et al. is extended using the signal-processing technique of the big mac attack. An experimental result to successfully analyze an FPGA implementation of RSA with the multiply-always method is also presented.

Precomputation techniques are useful to improve real-time performance of complex algorithms at the expense of extra memory, and extra preparatory computations. This practice is neglected especially in the embedded context where energy and memory space is limited. Instead, the embedded space favors the immediate reduction of energy and memory footprint. However, the embedded platforms of the future may be different from the traditional ones. Energy-harvesting sensor nodes may extract virtually limitless energy from their surrounding, while at the same time they are able to store more data at cheaper cost, thanks to Moore's law. Yet, minimizing the run-time energy and latency will still be primary targets for today's as well as future real-time embedded systems. Another important challenge for the future systems is to provide efficient public-key based solutions that can thwart quantum-cryptanalysis. In this article, we address these two concepts. We apply precomputation techniques on two post-quantum digital signature schemes: hash-based and lattice-based digital signatures. We first demonstrate that precomputation methods are extensible to post-quantum cryptography and are applicable on current energy-harvesting platforms. Then, we quantify its impact on energy, execution time, and the overall system yield. The results show that precomputation can improve the run-time latency and energy consumption up to a factor of 82.7$\times$ and 11.8$\times$, respectively. Moreover, for a typical energy-harvesting profile, it can triple the total number of generated signatures. We reveal that precomputation enables very complex and even probabilistic algorithms to achieve acceptable real-time performance on resource-constrained platforms. Thus, it will expand the scope of post-quantum algorithms to a broader range of platforms and applications.

In this paper, we consider the multi-bit Differential Power Analysis (DPA) in the Hamming weight model. In this regard, we revisit the definition of Transparency Order (TO) from the work of Prouff (FSE 2005) and find that the definition has certain limitations. Although this work has been quite well referred in the literature, surprisingly, these limitations remained unexplored for almost a decade. We analyse the definition from scratch, modify it and finally provide a definition with better insight that can theoretically capture DPA in Hamming weight model for hardware implementation with precharge logic. At the end, we confront the notion of (revised) transparency order with attack sim- ulations in order to study to what extent the low transparency order of an s-box impacts the efficiency of a side channel attack against its processing. To the best of our knowledge, this is the first time that such a critical analysis is conducted (even considering the original notion of Prouff). It practically confirms that the transparency order is indeed re- lated to the resistance of the s-box against side-channel attacks, but it also shows that it is not sufficient alone to directly achieve a satisfying level of security. Regarding this point, our conclusion is that the (revised) transparency order is a valuable criterion to consider when designing a cryptographic algorithm, and even if it does not preclude to also use classical countermeasures like masking or shuffling, it enables to improve their effectiveness.

Scalar multiplication is the most important and expensive operation in elliptic curve cryptosystems. In this paper we improve the efficiency of the Elliptic Net algorithm to compute scalar multiplication by using the equivalence of elliptic nets. The proposed method saves $four$ multiplications in each iteration loop. Experimental results also indicates that our algorithm will be more efficient than the previously known results in this line.

In this paper we propose a modified Elliptic Net algorithm to compute pairings. By reducing the number of the intermediate variables which should be updated in the iteration loop of the Elliptic Net algorithm, we speed up the computation of pairings. Experimental results show that the proposed method is about $14\%$ faster than the original Elliptic Net algorithm on certain supersingular elliptic curves with embedding degree $two$.

In this paper we present a new multiplication algorithm for residues modulo the Mersenne prime $2^{521} - 1$. Using this approach, on an Intel Haswell Core i7-4770, constant-time variable-base scalar multiplication on NIST's (and SECG's) curve P-521 requires 1,073,000 cycles, while on the recently proposed Edwards curve E-521 it requires just 943,000 cycles. As a comparison, on the same architecture openSSL's ECDH speed test for curve P-521 requires 1,319,000 cycles. Furthermore, our code was written entirely in C and so is robust across different platforms. The basic observation behind these speedups is that the form of the modulus allows one to multiply residues with as few word-by-word multiplications as is needed for squaring, while incurring very little overhead from extra additions, in contrast to the usual Karatsuba methods.

We analyse the security regarding timing attacks of implementations of the decryption in McEliece PKC with binary Goppa codes. First, we review and extend the existing attacks, both on the messages and on the keys. We show that, until now, no satisfactory countermeasure could erase all the timing leakages in the Extended Euclidean Algorithm (EEA) step. Then, we describe a version of the EEA never used for McEliece so far. It uses a constant number of operations for given public parameters. In particular, the operation flow does not depend on the input of the decryption, and thus closes all previous timing attacks. We end up with what should become a central tool toward a secure implementation of McEliece decryption.

Fibonacci ring oscillators are shown to have a risk to oscillate periodically instead of chaotically. The security implications of this are discussed. The probability of the occurrence of the periodic oscillations is determined experimentally on an FPGA for Fibonacci ring oscillators of lengths 16 and 32. Means to overcome the problem of the periodic oscillations are also discussed.

Side Channel Attacks (SCA) using power measurements are a known method of breaking cryptographic algorithms such as AES. Published research into attacks on AES frequently target only AES-128, and often target only the core Electronic Code-Book (ECB) algorithm, without discussing surrounding issues such as triggering, along with breaking the initialization vector. This paper demonstrates a complete attack on a secure bootloader, where the firmware files have been encrypted with AES-256-CBC. A classic Correlation Power Analysis (CPA) attack is performed on AES-256 to recover the complete 32-byte key, and a CPA attack is also used to attempt recovery of the initialization vector (IV).

Reconfigurability is a unique feature of modern FPGA devices to load hardware circuits just on demand. This also implies that a completely different set of circuits might operate at the exact same location of the FPGA at different time slots, making it difficult for an external observer or attacker to predict what will happen at what time. In this work we present and evaluate a novel hardware implementation of the lightweight cipher PRESENT with built-in side-channel countermeasures based on dynamic logic reconfiguration. In our design we make use of Configurable Look-Up Tables (CFGLUT) integrated in modern Xilinx FPGAs to nearly instantaneously change hardware internals of our cipher implementation for improved resistance against side-channel attacks. We provide evidence from practical experiments based on a Spartan-6 platform that even with 10 million recorded power traces we were unable to detect a first-order leakage using the state-of-the-art leakage assessment.

Power-equalization schemes for digital circuits aim to harden cryptographic designs against power analysis attacks. With respect to dual-rail logics most of these schemes have originally been designed for ASIC platforms, but much efforts have been spent to map them to FPGAs as well. A particular challenge is here to apply those schemes to the predefined logic structures of FPGAs (i.e., slices, LUTs, FFs, and routing switch boxes) for which special tools are required. Due to the absence of such routing tools Yu and Schaumont presented the idea of duplicating (i.e., dualizing) a fully-placed-and-routed dual-rail precharge circuit with equivalent routing structures on an FPGA. They adopted such architecture from WDDL providing the Double WDDL (DWDDL)scheme. In this work we show that this general technique - regardless of the underlying dual-rail logic - is incapable to properly prevent side-channel leakages. Besides theoretical investigations on this issue we present practical evaluations on a Spartan-6 FPGA to demonstrate the flaws in such an approach. In detail, we consider an AES-128 encryption module realized by three dual-rail precharge logic styles as a case study and show that none of those schemes can provide the desired level of protection.

By shrinking the technology and reducing the energy requirements of integrated circuits, producing ultra-low-power devices has practically become possible. Texas Instruments as a pioneer in developing FRAM-based products announced a couple of different microcontroller (MCU) families based on the low-power and fast Ferroelectric RAM technology. Such MCUs come with embedded cryptographic module(s) as well as the assertion that - due to the underlying ultra-low-power technology - mounting successful side-channel analysis (SCA) attacks has become very difficult. In this work we practically evaluate this claimed hardness by means of state-of-the-art power analysis attacks. The leakage sources and corresponding attacks are presented in order to give an overview on the potential risks of making use of such platforms in security-related applications. In short, we partially confirm the given assertion. Some modules, e.g., the embedded cryptographic accelerator, can still be attacked but with slightly immoderate effort. On the contrary, the other leakage sources are easily exploitable leading to straightforward attacks being able to recover the secrets.

Block Memory Content Scrambling (BMS), presented at CHES 2011, enables an effective way of first-order side-channel protection for cryptographic primitives at the cost of a significant reconfiguration time for the mask update. In this work we analyze alternative ways to implement dynamic first-order masking of AES with randomized look-up tables that can reduce this mask update time. The memory primitives we consider in this work include three distributed RAM components (RAM32M, RAM64M, and RAM256X1S) and one BRAM primitive (RAMB8BWER). We provide a detailed study of the area and time overheads of each implementation technique with respect to the operation (encryption) as well as reconfiguration (mask update) phase. We further compare the achieved security of each technique to prevent first-order side-channel leakages. Our evaluation is based on one of the most general forms of leakage assessment methodology known as non-specific t-test. Practical SCA evaluations (using a Spartan-6 FPGA platform) demonstrate that solely the BRAM primitive but none of the distributed RAM elements can be used to realize an SCA-protected implementation.

The paper describes a new RNS modular inversion algorithm based on the extended Euclidean algorithm and the plus-minus trick. In our algorithm, comparisons over large RNS values are replaced by cheap computations modulo 4. Comparisons to an RNS version based on Fermat’s little theorem were carried out. The number of elementary modular operations is significantly reduced: a factor 12 to 26 for multiplications and 6 to 21 for additions. Virtex 5 FPGAs implementations show that for a similar area, our plus-minus RNS modular inversion is 6 to 10 times faster.

Designers of secure hardware are required to harden their implementations against physical threats, such as power analysis attacks. In particular, cryptographic hardware circuits are required to decorrelate their current consumption from the information inferred by processing (secret) data. A common technique to achieve this goal is the use of special logic styles that aim at equalizing the current consumption at each single processing step. However, since all hiding techniques like Dual-Rail Precharge (DRP) were originally developed for ASICs, the deployment of such countermeasures on FPGA devices with fixed and predefined logic structure poses a particular challenge. In this work, we propose and practically evaluate a new DRP scheme (GliFreD) that has been exclusively designed for FPGA platforms. GliFreD overcomes the well-known early propagation issue, prevents glitches, uses an isolated dual-rail concept, and mitigates imbalanced routings. With all these features, GliFreD significantly exceeds the level of physical security achieved by any previously reported, related countermeasures for FPGAs.

Hardware and software of secured embedded systems are prone to physical attacks. In particular, fault injection attacks revealed vulnerabilities on the data and the control flow allowing an attacker to break cryptographic or secured algorithms implementations. While many research studies concentrated on successful attacks on the data flow, only a few targets the instruction flow. In this paper, we focus on electromagnetic fault injection (EMFI) on the control flow, especially on the instruction cache. We target the very widespread (smartphones, tablets, settop-boxes, health-industry monitors and sensors, etc.) ARMv7-M architecture. We describe a practical EMFI platform and present a methodology providing high control level and high reproducibility over fault injections. Indeed, we observe that a precise fault model occurs in up to 96\% of the cases. We then characterize and exhibit this practical fault model on the cache that is not yet considered in the literature. We comprehensively describe its effects and show how it can be used to reproduce well known fault attacks. Finally, we describe how it can benefits attackers to mount new powerful attacks or simplify existing ones.

In this work we have analyzed some password hashing schemes for performance under various settings of time and memory complexities. We have attempted to benchmark the said algorithms at similar levels of memory consumption. Given the wide variations in security margins of the algorithms and incompatibility of memory and time cost settings, we have attempted to be as fair as possible in choosing the various parameters while executing the benchmarks.

This paper is devoted to the design of a 258-bit multiplier for computing pairings over Barreto-Naehrig (BN) curves at 128-bit security level. The proposed design is optimized for Xilinx field programmable gate array (FPGA). Each 258-bit integer is represented as a polynomial with five, 65 bit signed integer, coefficients. Exploiting this splitting we designed a pipelined 65-bit multiplier based on new Karatsuba- Ofman variant using non-standard splitting to fit to the Xilinx embedded digital signal processor (DSP) blocks. We prototype the coprocessor in two architectures pipelined and serial on a Xilinx Virtex-6 FPGA using around 17000 slices and 11 DSPs in the pipelined design and 7 DSPs in the serial. The pipelined 128-bit pairing is computed in 1. 8 ms running at 225MHz and the serial is performed in 2.2 ms running at 185MHz. To the best of our knowledge, this implementation outperforms all reported hardware designs in term of DSP use. Keywords-

Resource constraints in smart devices demand an efficient cryptosystem that allows for low power and memory consumption. This has led to popularity of comparatively efficient Elliptic curve cryptog-raphy (ECC). Prior to this paper, much of ECC is implemented on re-configurable hardware i.e. FPGAs, which are costly and unfavorable as low-cost solutions. We present comprehensive yet efficient implementations of ECC on fixed-point TMS54xx series of digital signal processors (DSP). 160-bit prime field GF(p) ECC is implemented over a wide range of coordinate choices. This paper also implements windowed recoding technique to provide better execution times. Stalls in the programming are mini-mized by utilization of loop unrolling and by avoiding data dependence. Complete scalar multiplication is achieved within 50 msec in coordinate implementations, which is further reduced till 25 msec for windowed-recoding method. These are the best known results for fixed-point low power digital signal processor to date.

This paper presents several methods for reducing the number of bit operations for multiplication of polynomials over the binary field. First, a modified Bernstein’s 3-way algorithm is introduced, followed by a new 5-way algorithm. Next, a new 3-way algorithm that improves asymptotic arithmetic complexity compared to Bernstein’s 3-way algorithm is introduced. This new algorithm uses three multiplications of one-third size polynomials over the binary field and one multiplication of one-third size polynomials over the finite field with four elements. Unlike Bernstein’s algorithm, which has a linear delay complexity with respect to input size, the delay complexity of the new algorithm is logarithmic. The number of bit operations for the multiplication of polynomials over the finite field with four elements is also computed. Finally, all these new results are combined to obtain improved complexities.

Secure transmission of message was the concern of early men. Several techniques have been developed ever since to assure that the message is understandable only by the sender and the receiver while it would be meaningless to others. In this century, cryptography has gained much significance. This paper proposes a scheme to generate a Dynamic Key-dependent S-Box for the SubBytes Transformation used in Cryptographic Techniques.

The recent Bimodal Lattice Signature Scheme (BLISS) showed that lattice-based constructions have evolved to practical alternatives to RSA or ECC. It offers small signatures of 5600 bits for a 128-bit level of security, and proved to be very fast in software. However, due to the complex sampling of Gaussian noise with high precision, it is not clear whether this scheme can be mapped efficiently to embedded devices. Even though the authors of BLISS also proposed a new sampling algorithm using Bernoulli variables this approach is more complex than previous methods using large precomputed tables. The clear disadvantage of using large tables for high performance is that they cannot be used on constrained computing environments, such as FPGAs, with limited memory. In this work we thus present techniques for an efficient Cumulative Distribution Table (CDT) based Gaussian sampler on reconfigurable hardware involving Peikert's convolution lemma and the Kullback-Leibler divergence. Based on our enhanced sampler design, we provide a scalable implementation of BLISS signing and verification on a Xilinx Spartan-6 FPGA supporting either 128-bit, 160-bit, or 192-bit security. For high speed we integrate fast FFT/NTT-based polynomial multiplication, parallel sparse multiplication, Huffman compression of signatures, and Keccak as hash function. Additionally, we compare the CDT with the Bernoulli approach and show that for the particular BLISS-I parameter set the improved CDT approach is faster with lower area consumption. Our BLISS-I core uses 2,291 slices, 5.5 BRAMs, and 5 DSPs and performs a signing operation in 114.1 us on average. Verification is even faster with a latency of 61.2 us and 17,101 supported verification operations per second.

We provide the first provable-security analysis of the Intel Secure Key hardware RNG (ISK-RNG), versions of which have appeared in Intel processors since late 2011. To model the ISK-RNG, we generalize the PRNG-with-inputs primitive, introduced Dodis et al. introduced at CCS'13 for their /dev/[u]random analysis. The concrete security bounds we uncover tell a mixed story. We find that ISK-RNG lacks backward-security altogether, and that the forward-security bound for the ``truly random'' bits fetched by the RDSEED instruction is potentially worrisome. On the other hand, we are able to prove stronger forward-security bounds for the pseudorandom bits fetched by the RDRAND instruction. En route to these results, our main technical efforts focus on the way in which ISK-RNG employs CBCMAC as an entropy extractor.

Program obfuscation is the process of making a program "unintelligible" without changing the program's underlying input/output behavior. Although there is a long line of work on heuristic techniques for obfuscation, such approaches do not provide any cryptographic guarantee on their effectiveness. A recent result by Garg et al. (FOCS 2013), however, shows that cryptographic program obfuscation is indeed possible based on a new primitive called a \emph{graded encoding scheme}. In this work, we present the first implementation of such an obfuscator. We describe several challenges and optimizations we made along the way, present a detailed evaluation of our implementation, and discuss research problems that need to be addressed before such obfuscators can be used in practice.

With increasing popularity of cloud storage, efficiently proving the integrity of data stored at an untrusted server has become significant. Authenticated Skip Lists and Rank-based Authenticated Skip Lists (RBASL) have been used to provide support for provable data update operations in cloud storage. However, in a dynamic file scenario, an RBASL falls short when updates are not proportional to a fixed block size; such an update to the file, even if small, may result in O(n) block updates to the RBASL, for a file with n blocks. To overcome this problem, we introduce FlexList: Flexible Length-Based Authenticated Skip List. FlexList translates variable-size updates to O(u/B) insertions, removals, or modifications, where u is the size of the update, and B is the (average) block size. We further present various optimizations on the four types of skip lists (regular, authenticated, rank-based authenticated, and FlexList). We build such a structure in O(n) time, and parallelize this operation for the first time. We compute one single proof to answer multiple (non-)membership queries and obtain efficiency gains of 35%, 35% and 40% in terms of proof time, energy, and size, respectively. We propose a method of handling multiple updates at once, achieving efficiency gains of up to 60% at the server side and 90% at the client side. We also deployed our implementation of FlexDPDP (DPDP with FlexList instead of RBASL) on the PlanetLab, demonstrating that FlexDPDP performs comparable to the most efficient static storage scheme (PDP), while providing dynamic data support.

In this paper we study the existing CRT-RSA countermeasures against fault-injection attacks. In an attempt to classify them we get to achieve deep understanding of how they work. We show that the many countermeasures that we study (and their variations) actually share a number of common features, but optimize them in different ways. We also show that there is no conceptual distinction between test-based and infective countermeasures and how either one can be transformed into the other. Furthermore, we show that faults on the code (skipping instructions) can be captured by considering only faults on the data. These intermediate results allow us to improve the state of the art in several ways: (a) we fix an existing and that was known to be broken countermeasure (namely the one from Shamir); (b) we drastically optimize an existing countermeasure (namely the one from Vigilant) which we reduce to 3 tests instead of 9 in its original version, and prove that it resists not only one fault but also an arbitrary number of randomizing faults; (c) we also show how to upgrade countermeasures to resist any given number of faults: given a correct first-order countermeasure, we present a way to design a provable high-order countermeasure (for a well-defined and reasonable fault model). Finally, we pave the way for a generic approach against fault attacks for any modular arithmetic computations, and thus for the automatic insertion of countermeasures.

GLV curves (Gallant et al.) have performance advantages over standard elliptic curves, using half the number of point doublings for scalar multiplication. Despite their introduction in 2001, implementations of the GLV method have yet to permeate widespread software libraries. Furthermore, side-channel vulnerabilities, specifically cache-timing attacks, remain unpatched in the OpenSSL code base since the first attack in 2009 (Brumley and Hakala) even still after the most recent attack in 2014 (Benger et al.). This work reports on the integration of the GLV method in OpenSSL for curves from 160 to 256 bits, as well as deploying and evaluating two side-channel defenses. Performance gains are up to 51%, and with these improvements GLV curves are now the fastest elliptic curves in OpenSSL for these bit sizes.

Field inversion in GF($2^m$) dominates the cost of modern software implementations of certain elliptic curve cryptographic operations, such as point encoding/hashing into elliptic curves. Itoh--Tsujii inversion using a polynomial basis and precomputed table-based multi-squaring has been demonstrated to be highly effective for software implementations, but the performance and memory use depend critically on the choice of addition chain and multi-squaring tables, which in prior work have been determined only by suboptimal ad-hoc methods and manual selection. We thoroughly investigated the performance/memory tradeoff for table-based linear transforms used for efficient multi-squaring. Based upon the results of that investigation, we devised a comprehensive cost model for Itoh--Tsujii inversion and a corresponding optimization procedure that is empirically fast and provably finds globally-optimal solutions. We tested this method on 8 binary fields commonly used for elliptic curve cryptography; our method found lower-cost solutions than the ad-hoc methods used previously, and for the first time enables a principled exploration of the time/memory tradeoff of inversion implementations.