Speculative data-parallel algorithms for language recognition have been widely experimented for various types of finitestate automata (FA), deterministic (DFA) and nondeterministic (NFA), often derived fromregular expressions (RE). Such an algorithm cuts the input string into chunks, independently recognizes each chunk in parallel by means of identical FAs, and at last joins the chunk results and checks the overall consistency. In chunk recognition, it is necessary to speculatively start the FAs in any state, thus causing an overhead that reduces the speedup over a serial algorithm. The existing data-parallel DFA-based recognizers suffer from an excessive number of starting states, and the NFA-based ones suffer from the number of nondeterministic transitions.

Emerging non-volatile memories (NVMs) have the potential to change the memory-storage hierarchy in computing devices, and even to replace DRAM as main memories. In fact NVMs, beside offering byte-addressability and data persistence, promise better scalability and higher capacity than DRAM. However, from a security point of view, the persistent nature of emerging memories provides a larger time window to exfiltrate data from a device with respect to current DRAM-based main memories, and NVMs have in general lower write endurance than DRAM, thus requiring wear-out conscious encryption schemes. In this work we propose an architectural solution to secure non-volatile emerging memories, providing confidentiality, integrity and authenticity to the entire set of data, addresses and commands. Our solution relies on securing and authenticating the entire information transport between the host controller and the memory, enabling the storage of cleartext data inside the NVM. Such an approach allows to retain the advantage of differential write strategies without forsaking security. We validate our proposed architecture through the simulation of a set of software benchmarks on an embedded architecture, employing the gem5 trace-based architectural simulator.

Elliptic curve cryptosystems proved to be well suited for securing systems with constrained resources like embedded and portable devices. In a fault-based attack, errors are induced during the computation of a cryptographic primitive, and the results are collected to derive information about the secret key safely stored in the device. We introduce a novel attack methodology to recover the secret key employed in implementations of the Elliptic Curve Digital Signature Algorithm. Our attack exploits the information leakage induced when altering the execution of the modular arithmetic operations used in the signature primitive and does not rely on the underlying elliptic curve mathematical structure, thus being applicable to all standardized curves. We provide both a validation of the feasibility of the attack, even employing common off-the-shelf hardware to perform the required computations, and a low-cost countermeasure to counteract it.

Implementations of cryptographic algorithms continue to proliferate in consumer products due to the increasing demand for secure transmission of confidential information. Although the current standard cryptographic algorithms proved to withstand exhaustive attacks, their hardware and software implementations have exhibited vulnerabilities to side channel attacks, e.g., power analysis and fault injection attacks. This paper focuses on fault injection attacks that have been shown to require inexpensive equipment and a short amount of time. The paper provides a comprehensive description of these attacks on cryptographic devices and the countermeasures that have been developed against them. After a brief review of the widely used cryptographic algorithms, we classify the currently known fault injection attacks into low-cost ones (which a single attacker with a modest budget can mount) and high-cost ones (requiring highly skilled attackers with a large budget). We then list the attacks that have been developed for the important and commonly used ciphers and indicate which ones have been successfully used in practice. The known countermeasures against the previously described fault injection attacks are then presented, including intrusion detection and fault detection. We conclude the survey with a discussion on the interaction between fault injection attacks (and the corresponding countermeasures) and power analysis attacks.

Elliptic curve cryptosystems proved to be well suited for securing systems with constrained resources like embedded and portable devices. In a fault attack, errors are induced during the computation of a cryptographic primitive, and the faulty results are collected to derive information about the secret key stored into the device in a non-readable way. Scenarios where the secure devices are seized by an opponent are quite common. Consequently, it is possible for an attacker to induce changes in the working environment of the device to cause alterations in the computation of the cryptographic primitive. We introduce a new fault model and attack methodology to recover the secret key employed in implementations of the Elliptic Curve Digital Signature Algorithm. Our attack exploits the information leakage induced when altering the execution of the modular arithmetic operations used in the signature primitive and does not rely on the properties of the underlying elliptic curve mathematical structure, thus being applicable to curves defined on both prime fields and binary fields. The attack is easily reproducible with low cost fault injection technologies relying on transient errors placed within a single datapath width of the target architecture.

This work presents a differential fault attack against AES employin any key size, regardless of the key scheduling strategy. The presented attack relies on the injection of a single bit flip, and is able to check for the correctness of the injection of the fault a posteriori. This fault model nicely fits the one obtained through underfeeding a computing device employing a low cost tunable power supply unit. This fault injection technique, which has been successfully applied to hardware implementations of AES, receives a further validation in this paper where the target computing device is a system-on-chip based on the widely adopted ARM926EJ-S CPU core. The attack is successfully carried out against two different devices, etched in two different technologies (a generic 130 nm and a low-power oriented 90 nm library) running a software implementation of AES-192 and AES-256 and has been reproduced on multiple instances of the same chip.

Branch Prediction Analysis has been recently proposed as an attack method to extract the key from software implementations of the RSA public key cryptographic algorithm. In this paper, we describe several solutions to protect against such an attack and analyze their impact on the execution time of the cryptographic algorithm. We show that the code transformations required for protection against branch target buffer attacks can be automated and impose only a negligible performance penalty.

One of the most effective ways of attacking a cryptographic device is by deliberate fault injection during computation, which allows retrieving the secret key with a small number of attempts. Several attacks on symmetric and public-key cryptosystems have been described in the literature and some dedicated error-detection techniques have been proposed to foil them. The proposed techniques are ad hoc ones and exploit specific properties of the cryptographic algorithms. In this paper, we propose a general framework for error detection in symmetric ciphers based on an operation-centered approach. We first enumerate the arithmetic and logic operations included in the cipher and analyze the efficacy and hardware complexity of several error-detecting codes for each such operation. We then recommend an error-detecting code for the cipher as a whole based on the operations it employs. We also deal with the trade-off between the frequency of checking for errors and the error coverage. We demonstrate our framework on a representative group of 11 symmetric ciphers. Our conclusions are supported by both analytical proofs and extensive simulation experiments

Nowadays the need of speed in cipher and decipher operations is more important than in the past. This is due to the diffusion of real time applications, which fact involves the use of cryptography. Many co-processors for cryptography were studied and presented in the past, but only few works were addressed to the enhancement of the instruction set architecture (ISA) of the embedded processor. This paper presents an extension of the ISA of a 32 bit processor, that aims at speeding up the software implementations of the AES algorithm. After the identification of the most frequently executed and the most time consuming sections of the algorithm, a set of dedicated instructions is designed in order to improve the performances of the cipher operations. We validate our instruction set extension by measuring the speed up for different optimized implementations of AES using an ARM processor simulator, but the enhancements we propose are general enough to be applied to almost all 32 bit processors.

Recently, various attacks have been proposed against many crypto systems, exploiting deliberate error injection during the computation process. In this paper, we add a residue-based error detection scheme to an RSA architecture to protect against such attacks. We then evaluate the error coverage and the expected area and latency overheads

1073-1074

On-line testing approaches can today be useful when designing circuits with severe security constraints. The reasons are summarized in the introduction to the special session on secure implementations (in these proceedings). The presentations in this special session aimed at introducing the specific concerns related to security as well as some approaches used to protect the circuits and to validate their robustness for certification. This panel aims at discussing in more details how on-line testing techniques can help in improving security and how the achieved level of security can be evaluated at different stages in the design flow. Various aspects are covered by the participants, including: counter-measures for fault attacks in hardware cryptographic primitives, design for test versus design for security, use of fault injection tools in evaluating the robustness against attacks and validation of security at the system level.

Recent research has shown that fault diagnosis and possibly fault tolerance are important features when implementing cryptographic algorithms by means of hardware devices. In fact, some security attack procedures are based on the injection of faults. At the same time, hardware implementations of cryptographic algorithms, i.e. crypto-processors, are becoming widespread. There is however, only very limited research on implementing fault diagnosis and tolerance in crypto-algorithms. Fault diagnosis is studied for the RC5 crypto-algorithm, a recently proposed block-cipher algorithm that is suited for both software and hardware implementations. RC5 is based on a mix of arithmetic and logic operations, and is therefore a challenge for fault diagnosis. We study fault propagation in RC5, and propose and evaluate the cost/performance tradeoffs of several error detecting codes for RC5. Costs are estimated in terms of hardware overhead, and performances in terms of fault coverage. Our most important conclusion is that, despite its nonuniform nature, RC5 can be efficiently protected by using low-cost error detecting codes.

The goal of the Advanced Encryption Standard (AES) is to achieve secure communication. The use of AES does not, however, guarantee reliable communication. Prior work has shown that even a single transient error occurring during the AES encryption (or decryption) process will very likely result in a large number of errors in the encrypted/decrypted data. Such faults must be detected before sending to avoid the transmission and use of erroneous data. Concurrent fault detection is important not only to protect the encryption/decryption process from random faults. It will also protect the encryption/decryption circuitry from an attacker who may maliciously inject faults in order to find the encryption secret key. In this paper, we first describe some studies of the effects that faults may have on a hardware implementation of AES by analyzing the propagation of such faults to the outputs. We then present two fault detection schemes: The first is a redundancy-based scheme while the second uses an error detecting code. The latter is a novel scheme which leads to very efficient and high coverage fault detection. Finally, the hardware costs and detection latencies of both schemes are estimated.

High reliability is a desirable property of any implementation of the Advanced Encryption Standard (AES). To achieve high reliability, all possible faults must be detected to avoid the use and transmission of erroneous encrypted/decrypted data. In this paper we first study the behavior of faults which may occur during the encryption and decryption procedures of AES, and the way such faults eventually propagate to the final result. We then describe an appropriate detection technique for these faults. This work extends our preliminary results (G. Bertoni et al, MPCS 2002) by considering more general fault models (e.g., permanent and multiple transient faults), and the possibility of fault masking.

Cryptographic applications in embedded systems for smart-cards require low-latency, low-complexity and low power dedicated hardware. In this work the GBB algorithm for finite field multiplication is optimised by recoding and the related digit-serial VLSI multiplier architecture is designed and evaluated.

Microcontrollers for embedded computer applications require a library of dedicated macrocells for specific applications. Arithmetic and basic digital signal processor (DSP) computations may be too inefficient when computed by software on the core central processing unit (CPU) of the microcontroller. Here the architecture of a VLSI macrocell is defined and developed for the ST9 microcontroller (8 bits), for the computation of the inner (scalar) product of two vectors of integer numbers based on the multiply/accumulate algorithm. The arithmetic core of the macrocell is an integer pipeline. This macrocell fully interfaces to the ST9 environment and is optimized so as to achieve the maximum performances compatible with the bandwidth of the bus of ST9 and the minimum consumption of silicon area. The macrocell Is implemented in CMOSM5H technology (0.7 /spl mu/ channel width) and its performances, measured in terms of silicon area and throughput, are evaluated.

The FERMI is a data acquisition system for calorimetry experiments in high energy physics at the LHC, CERN. The system contains a large number of acquisition channels, with a precision of 16 bits and a sampling rate of 40 MHz. A large part of the information driven by the channels is processed locally, to reduce the amount of data. This requires to cluster several channels by adding them. The paper presents the design of a fast, low cost adder chip, based on the implementation of column compression techniques for the computation of integer addition. Since the system is operating in a radiation-hard environment, fault tolerance (namely fault detection) is implemented by means of arithmetic codes.

The paper presents a study on the introduction of pipelining in parallel VLSI multipliers, built according to the column compression (CC) design techniques. A number of CC multiplier schemes have been proposed in the literature, aimed at reducing the number of stages of adders necessary to compute a multiplication. More recently CC multiplier schemes aimed at optimising the required silicon area, the regularity and the locality of the interconnections among the adders, have been proposed. The paper affords the introduction of pipelining in these last structures and compares the obtained results with existing structures, in terms of required number of components and operation frequency.

This paper is dedicated to the presentation of the architecture of a VLSI butterfly processing element, for computing FFT in serial arithmetic. This butterfly PE uses complex samples and weights, with real and imaginary parts represented separately in full fractional two's complement form. The PE is based on a compact serial/parallel to serial complex multiplier, which optimises complex multiplication by merging the generation and accumulation of partial products. The structure of the multiplier and the PE is presented; their performances are evaluated, including the possibility of reconfiguration, fault detection and fault tolerance.>

A methodology for the design of modular and optimized architectural blocks for the generation of local windows of pixels is presented. The proposed formalization and the related techniques follow a design approach derived from the window-based algorithmic decomposition of low- and medium-level image processing algorithms.>

Window-based parallel architectures are considered as target structures for the computation of low and medium level image processing algorithms. Their definition stems from a general reformulation of algorithms, based on local data processing. A methodology for high level global evaluation of such architectures is presented, considering the reachable performances of the structures as main significant parameters.>

A novel convolver is presented in which both samples and results are in serial form, while coefficients are stored in internal registers. The convolver is composed of an array of multiplier-accumulator subunits which operate in a carry-save, serial/parallel mode. The sample bits are broadcast to all subunits, each one executing the multiplication with the stored coefficient and accumulating the product with the result received from the preceding unit. The structure can be shown to be decomposable in bit-slices; a stack of slices can be programmed as a convolver for prescribed sample and coefficient bit-length under the control of a configuration register. Faulty slices can be neutralized by variables stored in a second register.>