Title page for ETD etd-0428104-195331

Document Type thesis

Author Name Yuksel, Kaan

URN etd-0428104-195331

Title Universal Hashing for Ultra-Low-Power Cryptographic Hardware Applications

Degree MS

Department Electrical & Computer Engineering

Advisors
Berk Sunar, Advisor
William J. Martin, Committee Member
Brian King, Committee Member
Fred J. Looft, Department Head

Keywords
self-powered
universal hashing
ultra-low-power
message authentication codes
provable security

Date of Presentation/Defense 2004-04-29

Availability unrestricted

Abstract
Message Authentication Codes (MACs) are valuable tools for ensuring the integrity
of messages. MACs may be built around a keyed hash function. Our main motivation
was to prove that universal hash functions can be employed as underlying primitives
of MACs in order to provide provable security in ultra-low-power applications such
as the next generation self-powered sensor networks. The idea of using a universal
hash function (NH) was explored in the construction of UMAC. This work presents
three variations on NH, namely PH, PR and WH. The first hash function we propose,
PH, produces a hash of length 2w and is shown to be 2^(-w)-almost universal. The
other two hash functions, i.e. PR and WH, reach optimality and are proven to be
universal hash functions with half the hash length of w. In addition, these schemes
are simple enough to allow for efficient constructions. To the best of our knowledge the
proposed hash functions are the first ones specifically designed for low-power hardware
implementations. We achieve drastic power savings of up to 59% and speedup of up
to 7.4 times over NH. Note that the speed improvement and the power reduction
are accomplished simultaneously. Moreover, we show how the technique of multi-
hashing and the Toeplitz approach can be combined to reduce the power and energy
consumption even further while maintaining the same security level with a very slight
increase in the amount of key material. At low frequencies the power and energy
reductions are achieved simultaneously while keeping the hashing time constant. We
develope formulae for estimation of leakage and dynamic power consumptions as
well as energy consumption based on the frequency and the Toeplitz parameter t.
We introduce a powerful method for scaling WH according to specific energy and
power consumption requirements. This enables us to optimize the hash function
implementation for use in ultra-low-power applications such as "Smart Dust" motes,
RFIDs, and Piconet nodes. Our simulation results indicate that the implementation
of WH-16 consumes only 2.95 韰 500 kHz. It can therefore be integrated into a self-
powered device. By virtue of their security and implementation features mentioned
above, we believe that the proposed universal hash functions fill an important gap in
cryptographic hardware applications.

Files
yuksel.pdf

Browse by Author | Browse by Department | Search all available ETDs

Questions? Email etd-questions@wpi.edu
Maintained by webmaster@wpi.edu

Document Type	thesis
Author Name	Yuksel, Kaan
URN	etd-0428104-195331
Title	Universal Hashing for Ultra-Low-Power Cryptographic Hardware Applications
Degree	MS
Department	Electrical & Computer Engineering
Advisors	Berk Sunar, Advisor William J. Martin, Committee Member Brian King, Committee Member Fred J. Looft, Department Head
Keywords	self-powered universal hashing ultra-low-power message authentication codes provable security
Date of Presentation/Defense	2004-04-29
Availability	unrestricted
Abstract Message Authentication Codes (MACs) are valuable tools for ensuring the integrity of messages. MACs may be built around a keyed hash function. Our main motivation was to prove that universal hash functions can be employed as underlying primitives of MACs in order to provide provable security in ultra-low-power applications such as the next generation self-powered sensor networks. The idea of using a universal hash function (NH) was explored in the construction of UMAC. This work presents three variations on NH, namely PH, PR and WH. The first hash function we propose, PH, produces a hash of length 2w and is shown to be 2^(-w)-almost universal. The other two hash functions, i.e. PR and WH, reach optimality and are proven to be universal hash functions with half the hash length of w. In addition, these schemes are simple enough to allow for efficient constructions. To the best of our knowledge the proposed hash functions are the first ones specifically designed for low-power hardware implementations. We achieve drastic power savings of up to 59% and speedup of up to 7.4 times over NH. Note that the speed improvement and the power reduction are accomplished simultaneously. Moreover, we show how the technique of multi- hashing and the Toeplitz approach can be combined to reduce the power and energy consumption even further while maintaining the same security level with a very slight increase in the amount of key material. At low frequencies the power and energy reductions are achieved simultaneously while keeping the hashing time constant. We develope formulae for estimation of leakage and dynamic power consumptions as well as energy consumption based on the frequency and the Toeplitz parameter t. We introduce a powerful method for scaling WH according to specific energy and power consumption requirements. This enables us to optimize the hash function implementation for use in ultra-low-power applications such as "Smart Dust" motes, RFIDs, and Piconet nodes. Our simulation results indicate that the implementation of WH-16 consumes only 2.95 韰 500 kHz. It can therefore be integrated into a self- powered device. By virtue of their security and implementation features mentioned above, we believe that the proposed universal hash functions fill an important gap in cryptographic hardware applications.
Files	yuksel.pdf