• Communications Security Lab, Guang Gong, Department of E&CE.
• Laboratory for Side-Channel Security of Embedded Systems, Cathy Gebotys, Department of E&CE.
• Cryptography, Security and Privacy Research Group, Ian Goldberg, Urs Hengartner and Doug Stinson, David R. Cheriton School of Computer Science.

Security for Pervasive Computing Environments

Pervasive computing environments allow users to seamlessly interact with embedded computers, depending on the users' current context. These new environments raise a variety of privacy and security challenges. For example, context-sensitive services can easily leak information about a user's context or uncertainty about a user's context might lead to wrongfully disclosed information.

In our research, we examine pervasive computing environments for security and privacy challenges. We address these challenges by applying cryptographic algorithms in new ways and by implementing and evaluating these algorithms in prototype applications.

Hash Functions

The recent discovery of collision-finding algorithms for many popular hash functions has led to an increased interest in the development and analysis of hash functions. Recent work includes analysis of multicollision attacks on hash functions and analysis of reductions among fundamental computational problems involving hash functions.

Pseudorandom Sequences

Pseudorandom sequences have many important applications in communications and cryptography. Randomness of a sequence refers to the unpredictability of the sequence. Any deterministically generated sequence used in practical applications is not truly random. The course of this research has two directions.

Sequence design for wireless code division multiplexing (CDMA) communication systems. In wireless CDMA systems, multiple users share a common channel. The problem is to find good signal sets having low correlation (decreasing interferences among users in the detection process), large linear span (for providing certain security features for the users who are assigned those sequences, e.g. preventing cloning of cell phones), and a large number of sequences (so that more users can be supported). These problems have many connections with combinatorics and Boolean functions. For example, sequences having 2-level autocorrelation corresponds to cyclic Hadamard difference sets, and the polynomial functions used to generate binary sequences correspond to Boolean functions. Constructions of Boolean functions with high nonlinearity (against linear cryptanalysis), high order correlation immunity or resilience (against various correlation attacks and differential cryptanalysis), and high algebraic immunity (against algebraic attacks) for both stream cipher and block ciphers are also being pursued.

Sequence design for applications in stream ciphers and pseudorandom number generators. Since tranmission errors are more likely in wireless communications than in wireline communications, stream ciphers are preferred over block ciphers. CACR researchers are designing pseudorandom sequence generators with good randomness properties which can be efficiently and securely implemented in hardware. Also being studied are the pseudorandom number generators that arise from the sequence generators.

Computational Number Theory

In the last twenty-five years, computational number theory and cryptology have become closely intertwined. Number theory provides most of the hard computational problems that can be used to guarantee the security of public-key cryptographic schemes. The main aim of computational number theory is the design, implementation, and analysis of algorithms for solving problems in number theory. Apart from algorithms for problems arising in cryptography such as the integer factorization problem or the discrete logarithm problem in various structures, this includes algorithms for computing fundamental invariants in algebraic number fields and algebraic function fields.

CACR researchers have made many contributions to the discrete logarithm problem in finite fields, elliptic curves and hyperelliptic curves. We have also studied combinatorial approaches to generic algorithms for the discrete logarithm problem, and considered "low hamming weight" variants of the problem.

Distributed Cryptographic Protocols

Many cryptographic tools can be adapted to a distributed setting where the authority to perform a certain cryptographic computation is shared among various entities in a network. For example, we might desire a certain threshold of entities in order to compute a signature, decrypt a ciphertext, etc. The simplest example of this type of scheme is a "secret sharing scheme", in which an authorized subset of entities (say at least t out of n) is required in order to reconstruct a certain secret, where each entity holds a "piece" of the secret called a share.

The advantage of a distributed protocol (as compared to a one-to-one protocol) is increased security against attacks (since there is no longer a single point of failure) and fault-tolerance (the desired action can be completed even if some of the entities are not functioning correctly). Many types of cryptographic protocols have been investigated in a distributed setting, including oblivious transfer and broadcast encryption.

Key Distribution

Distribution of keys by a trusted authority to users in a network is a fundamental tool in enabling secure communication. Security of key distribution schemes can be based on computational assumptions; however, it is also possible to design schemes that are "unconditionally secure". Schemes of this type are proven secure using combinatorial or information-theoretic techniques, independent of the computing power of an adversary.

Of particular interest are key distribution schemes for sensor networks, where it is imperative to minimize storage requirements and computational costs. In this setting, it may not be appropriate to ensure that every pair of nodes shares a common key, so efficient methods for establishing secure multi-hop communication paths are necessary.

Cryptographic Computations - Algorithms, Architectures and Fault Tolerance

Many cryptosystems are based on computations in very large finite fields. Dedicated hardware realization of processors or accelerators for such computations requires a large number of logic gates. A number of CACR researchers are working towards development of efficient algorithms for cryptographic computations. These algorithms are in turn mapped onto high performance and/or resource constrained architectures to meet requirements of various applications - from web servers to smart-cards. Research is also being carried out to devise efficient schemes for performing correct cryptographic computations in presence of hardware faults caused by defects of silicon devices or malicious acts of attackers.

Side-Channel Attacks and Countermeasures

Side-channel attacks reveal information about cryptographic keys by capture and analysis of electromagnetic emission or power dissipation from embedded systems. A side-channel analysis laboratory has been established which supports the verification of countermeasures and attacks through real measurement of electromagnetic emissions and power. Software-based and VLSI countermeasures to thwart side-channel attacks in wireless embedded systems are being investigated.

Copyright Protection

Copyright protection is a fundamental goal of digital rights management. Two methods of copyright protection are broadcast encryption and tracing. Broadcast encryption ensures that an encrypted broadcast can be decrypted only by designated authorized receivers. Tracing schemes use certain codes to allow pirated data or decoders to be traced back to their rightful owners.

Security in Ad Hoc Networks

Internet, wireless networks, and ad hoc networks have vastly differing characteristics such as the availability of a fixed infrastructure, the network topology, the capabilities of network nodes, and the availability of a centralized authority. These variations result in different requirements and constraints for implementing security features such as key distribution, authentication, encryption, and integrity checking.

In general, an ad hoc network does not have a fixed infrastructure, the network topology changes frequently, and the nodes have limited computational, bandwidth, and power resources. In practice, ad hoc networks may be associated with Personal Area Networks (PANs), as for instance wireless communications among PDAs, cellular phones, and laptops using the Bluetooth protocol, or sensor networks.

CACR researchers are developing applications-based security protocols for authentication among nodes in an ad hoc network and for authenticated key distributions or session key establishment. Symmetric, hybrid (for example, public-key cryptography with passwords), and asymmetric (i.e., public-key approach using threshold cryptography and identity-based schemes) solutions are being sought. Both single-hop and multi-hop scenarios are being considered. The performance of our proposed solutions will be evaluated through simulations.