Spring and Fall 2004

Unless indicated otherwise, the CryptoSeminar is being held in the Atwater Kent building on the WPI Worcester campus. The Atwater Kent building is at the intersection of Salisbury Street and the extension of West Street (labeled "Private Way"). See directions to campus.

The talks are 30-45 minutes long and are open to everyone.

Refreshments are usually being served 15 minutes before the talk. There is no fee and no formal registration. If you are attending a Seminar for the first time, a short e-mail to Profs. Berk Sunar or Bill Martin, saying that you would like to attend, would be appreciated.

Elliptic Curves and BMWs, or Why Cars Will Need Embedded IT Security

Prof. Christof Paar, Ruhr University Bochum and WPI
Monday, August 9, 2004, 3pm, Atwater Kent, WPI, Room 108

Abstract

Information technology is the driving force behind innovations in the automotive industry, with perhaps 90% of all innovations in cars based on electronics and software. Up to 80 embedded processors can be found in a high-end car, and electronics & software will soon also be the major single cost factor in car manufacturing. The situation is similar for commercial vehicles such as trucks. One crucial aspect of future IT applications in vehicles is the security of these systems. Whereas software safety is a relatively well established (if not necessarily well understood) field, the protection of automotive IT systems against manipulation has only very recently started to emerge. At the same time, security will be an enabling technology for many - perhaps for most - future automotive IT applications. IT security will both increase reliability & safety, and enable new business models.

In this talk I will give an overview of the different applications within the automotive domain with current and future security needs. After a brief threat analysis, a discussion of the specific problems of integrating embedded security in automotive applications will be presented. The talk concludes with an overview of our activities in this field at eurobits, the European Competence Center for IT-Security in Bochum, Germany.

Public Key Cryptography in Sensor Networks -- Revisited

Gunnar Gaubatz, Cryptography and Information Security (CRIS) Laboratory, Worcester Polytechnic Institute (WPI)
Friday July 30, 2004, 3pm, Atwater Kent, WPI, Room 108

Abstract

The common perception of public key cryptography is that it is complex, slow and power hungry, and as such not at all suitable for use in ultra-low power environments like wireless sensor networks. It is therefore common practice to emulate the asymmetry of traditional public key based cryptographic services through a set of protocols using symmetric key based message authentication codes (MACs). Although the low computational complexity of MACs is advantageous, the protocol layer requires time synchronization between devices on the network and a significant amount of overhead for communication and temporary storage. The requirement for a general purpose CPU to implement these protocols as well as their complexity makes them prone to vulnerabilities and practically eliminates all the advantages of using symmetric key techniques in the first place.

In this talk we challenge the basic assumptions about public key cryptography in sensor networks which are based on a traditional software based approach. We propose a custom hardware assisted approach for which we claim that it makes public key cryptography feasible in such environments, provided we use the right selection of algorithms and associated parameters, careful optimization, and low-power design techniques.

In order to validate our claim, we present proof of concept implementations of two different algorithms -- Rabin's Scheme and NtruEncrypt -- and analyze their architecture and performance according to various established metrics like power consumption, area, delay, throughput, level of security and energy per bit. Our implementation of NtruEncrypt in ASIC standard cell logic uses no more than 3,000 gates, with an average power consumption of less than 20 uW. We envision that our public key core would be embedded into a light-weight sensor node architecture.

Two Aspects of the Discrete Logarithm Problem

Dr. Douglas R. Stinson, School of Computer Science, University of Waterloo, Canada
Tuesday, April 27, 2004, 4:00pm, WPI Campus Center, Hagglund Room

Abstract

The discrete logarithm problem is of fundamental importance in cryptography. The security of many widely-used cryptosystems depends on the unproved assumption that certain versions of the discrete logarithm problem are intractable.

In this talk, we discuss two aspects of the discrete logarithm problem. First we investigate and extend two algorithms of Coppersmith that pertain to the so-called "low hamming weight" discrete logarithm problem. This is the special case of the discrete log problem in which the unknown logarithm has a small number of 1's in its binary representation. Such a logarithm might be chosen in order to speed up computations in a cryptosystem; however, the algorithms we describe show that determining the discrete logarithm in this case can also be speeded up significantly. These algorithms make use of certain set systems known as "splitting systems".

The second topic we discuss is an elementary treatment of the complexity of the so-called "generic" algorithms for the discrete log problem. Informally, a generic algorithm is one that works in any group. A well-known result of Nechaev and Shoup shows that generic algorithms in a group of prime order, n, have complexity that is lower bounded by the square root of n. We describe an approach to the analysis of generic algorithms that allows an exact (rather than asymptotic) analysis to be given. This approach demionstrates a link between generic algorithms on the one hand, and sets of points in (finite) Desarguesian affine planes that generate large numbers of slopes, on the other hand.

WPI's 2004 Annual Math Awareness Lecture: Visual Cryptography, or Seeing is Believing

Dr. Douglas R. Stinson, School of Computer Science, University of Waterloo, Canada
Monday, April 26, 2004, 4:00pm, Higgins Laboratories, WPI, Room 116

This talk is intended for a general audience. No particular background in mathematics is required.

M.S. Thesis Defense: Universal Hash Functions for Ultra-Low Power Cryptographic Hardware Applications

Kaan Yüksel, CRIS Laboratory, Worcester Polytechnic Institute
Friday, April 23, 2004, 2:00pm, Atwater Kent, WPI, Room 108

Abstract

Message Authentication Codes (MACs) are valuable tools for ensuring the integrity of messages. MACs may be built around a keyed hash function. The idea of using a universal hash function (NH) was explored in the construction of UMAC. This M.S. Thesis presents three variations on NH, namely PH, PR and WH. Our main motivation was to prove that universal hash functions can be employed to provide provable security in ultra-low-power applications such as the next generation self-powered sensor networks.

The first hash function we propose, i.e. 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 hash length of w only. 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 achieved 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 the key material. At low frequencies the power and energy reductions are achieved simultaneously while keeping the hashing time constant. We developed formulae for estimation of the leakage and dynamic power consumptions as well as the 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 implementation of WH-16 consumes only 2.95 uW at 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 will fill an important gap in cryptographic hardware applications.

Maintained by webmaster@wpi.edu
Last modified: Sep 22, 2006, 20:31 EDT