We present an architecture level low-power design technique called divide and concatenate for universal hash functions based on the following observations. (1) The power consumption of a w-bit array multiplier and associated universal hash data path decreases as O(w4) if its clock rate remains constant. (2) Two universal hash functions are equivalent if they have the same collision probability property. In the proposed approach, we divide a w-bit data path (with collision probability2-w) into two/four w/2-bit data paths (each with collision probability 2-w/2) and concatenate their results to construct an equivalent w-bit data path (with a collision probability 2-w). A popular low-power technique that uses parallel data paths saves 62.10% dynamic power consumption incurring 102% area overhead. In contrast, the divide-and-concatenate technique saves 55.44% dynamic power consumption with only 16% area overhead.

We present an architecture level optimization technique called divide-and-concatenate based on two observations: 1) the area of an array multiplier and its associated data path decreases quadratically and their delay decreases linearly as their operand size is reduced and 2) in universal hash functions and their associated message authentication codes, two one-way hash functions are equivalent if they have the same collision probability property. In the proposed approach, we divide a 2w-bit data path (with collision probability 2-2w) into two w-bit data paths (each with collision probability 2-w) and concatenate their results to construct an equivalent 2w-bit data path (with a collision probability 2-2w). We applied this technique on NH universal hash, a universal hash function that uses multiplications and additions. We implemented the straightforward 32-bit pipelined NH universal hash data path and the divide-and-concatenate architecture that uses four equivalent 8-bit divide-and-concatenate NH universal hash data paths on a Xilinx Virtex II XC2VP7-7 field programmable gate array (FPGA) device. This divide-and-concatenate architecture yielded a 94% increase in throughput with only 40% hardware overhead. Finally, the implementation of universal message authentication code (UMAC) with collision probability 2-32using the divide-and-concatenate NH hash as a building block yielded a throughput of 79.2 Gb/s with only 3840 Virtex II XC2VP7-7 FPGA slices

Secure operation of cryptographic algorithms is critical to the success of secure transactions. Fault-based attacks that recover secret keys by deliberately introducing fault(s) in cipher implementations and analyzing the faulty outputs have been proven to be extremely powerful. Substitution Permutation Networks (SPN) and Feistel Networks (FN) are the two important classes of Symmetric Block Ciphers. Some SPN ciphers and all FN Ciphers satisfy the involution property. A function F is an involution if F(F(x)) = x. In this paper, we investigate tamper proofing techniques that use low cost involution-based time redundancy concurrent error detection (CED) schemes for involutional SPN and FN symmetric block ciphers. We incorporated this tamper proofing by design technique in a hardware implementation of the 128-bit ANUBIS SPN cipher (an involution variant of the Advanced Encryption Standard (AES)) and the 128-bit TwoFish FN cipher (an AES finalist). We performed fault simulation at both the algorithm and the gate level to show that the low-cost involution-based CED schemes, in addition to detecting all transient faults, can detect all single-bit permanent faults and > 99 percent of all multiple-bit permanent faults. Consequently, this low cost CED technique can protect the crypto device against Differential Fault Analysis (DFA) attacks.

Scan-based design for test (DFT) is a powerful testing scheme, but it can be used to retrieve the secrets stored in a crypto chip, thus compromising its security. On one hand, sacrificing the security for testability by using a traditional scan-based DFT restricts its use in privacy sensitive applications. On the other hand, sacrificing the testability for security by abandoning the scan-based DFT hurts the product quality. The security of a crypto chip comes from the small secret key stored in a few registers, and the testability of a crypto chip comes from the data path and control path implementing the crypto algorithm. Based on this key observation, the authors propose a novel scan DFT architecture called secure scan that maintains the high test quality of traditional scan DFT without compromising the security. They used a hardware implementation of the advanced encryption standard to show that the traditional scan DFT scheme can compromise the secret key. They then showed that by using secure-scan DFT, neither the secret key nor the testability of the AES implementation is compromised

Scan-based Design-for-Test (DFT) is a powerful testing scheme, but it can be used to retrieve the secrets stored in a crypto chip thus compromising its security. On one hand, sacrificing security for testability by using traditional scan-based DFT restricts its use in privacy sensitive applications. On the other hand, sacrificing testability for security by abandoning scan-based DFT hurts product quality. The security of a crypto chip comes from the small secret key stored in a few registers and the testability of a crypto chip comes from the data path and control path implementing the crypto algorithm. Based on this key observation, we propose a novel scan DFT architecture called secure scan that maintains the high test quality of traditional scan DFT without compromising the security. We used a hardware implementation of the Advanced Encryption Standard (AES) to show that the traditional Scan DFT scheme can compromise the secret key. We then showed that by using secure scan DFT, neither the secret key nor the testability of the AES implementation is compromised.

Numerous applications in Digital Signal Processing (DSP), telecommunications, graphics, cryptography and control systems have computations that involve a large number of multiplications of one variable with one or several constants. In this paper, we present a constant array multiplier core generator using dynamic partial evaluation. The proposed constant array multiplier core generator combines a new partial evaluation method named Full Complement Recoding with Booth's recoding and the straightforward partial evaluation method. Based on the number of 0s, the number of runs that have more than two consecutive 1s and the total number of 1s in all the runs in the constant operand, the proposed multiplier core generator selects one of the three partial evaluation methods to construct a partial evaluation architecture and generate an efficient Hardware Description Language (HDL) code that can be used as a design component. The constant multiplier core generated by the Xilinx CORE GeneratorTM system does not provide the optimized constant multipliers for a large number of cases. When implemented using Xilinx FPGA Virtex II device, the average area saving and delay improvement of the constant multiplier generated by proposed core generator is 70% and 36% compared to the 55% and 15% of constant multipliers generated by Xilinx CORE GeneratorTM system.

The authors present an architectural optimization technique called divide-and-concatenate for hardware architectures of universal hash functions based on three observations: 1) the area of a multiplier and associated data path decreases quadratically and their speeds increase gradually as their operand size is reduced; 2) multiplication is at the core of universal hash functions and multipliers consume most of the area of universal hash function hardware; and 3) two universal hash functions are equivalent if they have the same collision-probability property. In the proposed approach, the authors divide a 2w-bit data path (with collision probability 2/sup -2w/) into two w-bit data paths (each with collision probability 2/sup -w/), apply one message word to these two w-bit data paths and concatenate their results to construct an equivalent 2w-bit data path (with a collision probability 2/sup -2w/). The divide-and-concatenate technique is complementary to all circuit-, logic-, and architecture-optimization techniques. The authors applied this technique on a linear congruential universal hash (LCH) family. When compared to the 100% overhead associated with duplicating a straightforward 32-bit LCH data path, the divide-and-concatenate approach that uses four equivalent 8-bit data paths yields a 101% increase in throughput with only 52% hardware overhead.

We present an architecture optimization technique called divide-and-concatenate for universal hash functions. The area of a multiplier increases quadratically and its speed increases gradually with the operand size and two universal hash functions are equivalent if they have the same collision probability property. Based on these observations, the divide-and-concatenate approach divides a 2w-bit data path (with collision probability 2-2w) into two w-bit data paths (each with collision probability 2-w), applies one message word to these two w-bit data paths and concatenates their results to construct an equivalent 2w-bit data path (with collision probability 2-2w). We demonstrate this technique on Linear Congruential Hash (LCH) family. When compared to the 100% overhead associated with duplicating a straightforward 32-bit LCH data path, the divide-and-concatenate approach that uses four equivalent 8-bit data paths yields a 101% increase in throughput with only 52% hardware overhead.

We present a cryptographic architecture optimization technique called divide-and-concatenate based on two observations: (i) the area of a multiplier and associated data path decreases quadratically and their speeds increase gradually as their operand size is reduced. (ii) in hash functions, message authentication codes and related cryptographic algorithms, two functions are equivalent if they have the same collision probability property. In the proposed approach we divide a 2w-bit data path into two w-bit data paths and concatenate their results to construct an equivalent 2w-bit data path. We applied this technique on NH hash. When compared to the 100% overhead associated with duplicating a straightforward 32-bit pipelined NH hash data path, the divide-and-concatenate approach yields a 94% increase in throughput with only 40% hardware overhead. The NH hash associated message authentication code UMAC architecture with collision probability 2-32 that uses four equivalent 8-bit divide-and-concatenate NH hash data paths yields a throughput of 79.2 Gbps with only 3840 FPGA slices when implemented on a Xilinx FPGA.

Scan based test is a double edged sword. On one hand, it is a powerful test technique. On the other hand, it is an equally powerful attack tool. We show that scan chains can be used as a side channel to recover secret keys from a hardware implementation of the Data Encryption Standard (DES). By loading pairs of known plaintexts with one-bit difference in the normal mode and then scanning out the internal state in the test mode, we first determine the position of all scan elements in the scan chain. Then, based on a systematic analysis of the structure of the nonlinear substitution boxes, and using three additional plaintexts we discover the DES secret key. Finally, some assumptions in the attack are discussed.