TY - JOUR

T1 - A high-speed hardware architecture for universal message authentication code

AU - Yang, Bo

AU - Karri, Ramesh

AU - McGrew, David A.

N1 - Funding Information:
Manuscript received September 15, 2005; revised March 30, 2006. This work was supported in part by the Cisco University Research Program. B. Yang and with R. Karri is with the Department of Electrical and Computer Engineering, Polytechnic University, Brooklyn, NY 11201 USA (e-mail: yangbo@photon.poly.edu; rkarri@duke.poly.edu). D. A. McGrew is with Cisco Systems, Inc., San Jose, CA 95134 USA (e-mail: mcgrew@cisco.com). Digital Object Identifier 10.1109/JSAC.2006.877133

PY - 2006/10

Y1 - 2006/10

N2 - 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 2ω-bit data path (with collision probability 2-2ω) into two w-bit data paths (each with collision probability 2-ω) and concatenate their results to construct an equivalent 2ω-bit data path (with a collision probability 2-2ω). 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% hard-ware overhead. Finally, the implementation of universal message authentication code (UMAC) with collision probability 2-32 using 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.

AB - 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 2ω-bit data path (with collision probability 2-2ω) into two w-bit data paths (each with collision probability 2-ω) and concatenate their results to construct an equivalent 2ω-bit data path (with a collision probability 2-2ω). 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% hard-ware overhead. Finally, the implementation of universal message authentication code (UMAC) with collision probability 2-32 using 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.

KW - Divide-and-concatenate

KW - Performance optimization

KW - Universal hash functions

KW - Universal message authentication code (UMAC)

UR - http://www.scopus.com/inward/record.url?scp=33749856204&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33749856204&partnerID=8YFLogxK

U2 - 10.1109/JSAC.2006.877133

DO - 10.1109/JSAC.2006.877133

M3 - Article

AN - SCOPUS:33749856204

VL - 24

SP - 1831

EP - 1839

JO - IEEE Journal on Selected Areas in Communications

JF - IEEE Journal on Selected Areas in Communications

SN - 0733-8716

IS - 10

M1 - 1705615

ER -