Divide-and-concatenate: an architecture level optimization technique for universal hash functions

ABSTRACT

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.

REFERENCES

• 1: B. Schneier, "Applied Cryptography," Second Edition, John Wiley & Sons, Inc. New York, 1996.
• 2: Shai Halevi , Hugo Krawczyk, MMH: Software Message Authentication in the Gbit/Second Rates, Proceedings of the 4th International Workshop on Fast Software Encryption, p.172-189, January 20-22, 1997
• 3: D. A. McGrew, "The Truncated Multi-Modular Hash Function (TMMH)," IETF Internet Draft, 2001. http://www. mindspring.com/ dmcgrew/draft-mcgrew-saag-tmmh-01.txt
• 4: S. Dharmapurikar, P. Krishnamurthy, T. Sproull and J. Lockwood. "Deep Packet Inspection Using Parallel Bloom Filters." Symposium on High Performance Interconnects http://csdl.computer.org/comp/proceedings/hoti/2003/2012/00/2012toc.htm, pp.44--52, 2003.
• 5: http://www.cs.ucdavis.edu/rogaway/umac/perf00bis.html
• 6: Helion Technology. Datasheet-High Performance SHA1 Hash Core for ASIC, 2003. http://www.heliontech.com/downloads/sha1_asic_helioncore.pdf
• 7: Amphion. Datasheet-High Performance MD5 Core, 2003. http://www.amphion.com/acrobat/DS5315.pdf
• 8: L. Carter, and M. Wegman, "Universal hash functions," Journal of Computer and System Sciences, vol 18, pp.143--154, 1979.
• 9: Adam J. Elbirt , W. Yip , B. Chetwynd , C. Paar, An FPGA-based performance evaluation of the AES block cipher candidate algorithm finalists, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.4, p.545-557, Aug. 2001 [doi>10.1109/92.931230]
• 10: Paul F. Stelling , Charles U. Martel , Vojin G. Oklobdzija , R. Ravi, Optimal Circuits for Parallel Multipliers, IEEE Transactions on Computers, v.47 n.3, p.273-285, March 1998 [doi>10.1109/12.660163]
• 11: G. Goto et al., "A 54--54-b Regularly Structured Tree Multiplier," IEEE J. Solid-State Circuits, vol. 27, no. 9, pp.1229--1236, 1992.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Cost/performance

General Terms:
Design, Experimentation, Performance

Keywords:
Design, Performance, Experimentation