Adrian Perrig's research projects
 
Home
Publications
Projects
  BiBa
  TESLA
  ELK
  APG
  SED
  Déjà Vu
   
Photos
Links
 

Recent Publications

Network security projects

Secure Ad Hoc Network Routing

Ad hoc networks are on the brink of wide-spread deployment. Research in ad hoc routing protocols has made great progress, however, the majority of this research assumed a trusted environment. Many real-world applications lack a trustworthy environment, and they require secure ad hoc routing protocols to prevent an adversary from performing denial-of-service (DoS) attacks on the routing infrastructure. Together with Dave Johnson and Yih-Chun Hu, we designed several secure ad hoc network routing protocols.

Security for Sensor Networks

As sensor networks edge closer towards wide-spread deployment, security issues become a central concern. So far, much research has focused on making sensor networks feasible and useful, and has not concentrated on security. We are working on several projects to secure sensor networks.

We present a suite of security building blocks optimized for resource-constrained environments and wireless communication. SPINS has two secure building blocks: SNEP and mTESLA. SNEP provides the following important baseline security primitives: Data confidentiality, two-party data authentication, and data freshness. A particularly hard problem is to provide efficient broadcast authentication, which is an important mechanism for sensor networks. mTESLA is a new protocol which provides authenticated broadcast for severely resource-constrained environments. We implemented the above protocols, and show that they are practical even on minimal hardware: the performance of the protocol suite easily matches the data rate of our network. Additionally, we demonstrate that the suite can be used for building higher level protocols.

Authentication and signature of broadcast streams

Assuring authenticity or non-repudiation of broadcast information is an important research challenge. Current solutions are largely impractical, due to their high communication and/or computation overhead. We propose three protocols: TESLA and BiBa provide source authentication, and EMSS offers non-repudiation (signature).

TESLA

One of the main challenges of securing multicast communication is source authentication, or enabling receivers of multicast data to verify that the received data originated with the claimed source and was not modified en-route. The problem becomes more complex in common settings where other receivers of the data are not trusted, and where lost packets are not retransmitted.

Check out our TESLA project page.

BiBa

The BiBa broadcast authentication protocol is based on the BiBa one-time signature. The BiBa one-time signature is a new signature construction that uses one-way functions without trapdoors. BiBa features a low verification overhead and a relatively small signature size. In comparison to other one-time signature schemes, BiBa has smaller signatures and is at least twice as fast to verify (which probably makes it one of the fastest signature schemes to date for verification).

  • The BiBa One-Time Signature and Broadcast Authentication Protocol PS, PDF, PS.GZ, HTML, BIB, in Proceedings of the ACM Conference on Computer and Communications Security CCS 2001, November 2001.

EMSS

EMSS is an efficient protocol to sign data streams. The main idea is to ammortize an expensive digital signature operation over a large number of data packets. For more information, please see:

  • Efficient Authentication and Signing of Multicast Streams over Lossy Channels PS, PDF, and PS.GZ, BIB, with Ran Canetti, Dawn Song, and Doug Tygar, in Proc. of IEEE Security and Privacy Symposium S&P2000, May 2000.

Key distribution and agreement of dynamic groups

Confidentiality is the main purpose of secure group communication. The general approach is to establish a secret group key shared by all members to encrypt all confidential communication. Dealing with dynamic membership is a challenging problem since secure group communication requires forward and backward secrecy. Forward secrecy guarantees that a passive adversary who knows a contiguous subset of old group keys cannot discover subsequent group keys. Similarly, backward secrecy guarantees that a passive adversary who knows a contiguous subset group keys cannot discover preceding group keys.

In my research I distinguish two common group settings:

  • Large groups (over 100 receivers) with a small number of senders. In general, the group is managed centrally, and has a small number of senders (usually only one).
  • Small groups (3-100 members). In this setting, every member is usually a sender and a receiver.

ELK - Key distribution for large groups

ELK is a new key distribution scheme for large broadcast groups. The main goal is to improve the efficiency such that the key distribution scales to larger and more dynamic groups. Inhibitors for scalability include:

ELK uses new techniques to improve the scalability of key distribution:
  • We observe that the computation power of servers continues to increase. Hence, we design a protocol such that member join events do not require any broadcast message at all, for the cost that the key server needs to compute a one-way function on all keys in each time interval. This approach increases the scalability since no key update message is sent and hence no message can get lost.
  • We also provide a mechanism for smaller key update messages, by trading off security and communication overhead. A lower security margin directly translates into smaller key update. Note that previous techniques did not have this property: As keys became smaller, the scheme becomes vulnerable to pre-computation attacks.
  • ELK also introduces "hints", another technique to reduce the size of key updates. As the receiver's workstation gets faster, we trade off receiver computation for communication overhead.
  • We introduce the notion of Maximum Impact Keys (MIK). Assume a LKH or OFT based key tree. Note that if a member leaves the group, half of the remaining members only need a single key update - the updated root key. So if we just send the key update for the group key only, half the members could recover from a lost key update. Similarly, if we send the update for two keys, 3/4 of all members can update their key tree. We propose to piggyback hints to the MIKs with data packets, such that the majority of members can recover from lost key updates.

Key agreement for small groups

Secure group communication for dynamic peer groups is an important service in the future. Considering collaborative workplaces, audio and video conferencing, and the intercommunication between devices in ubiquitous computing, I expect that the number of small groups (between 3 and 100 members) will greatly outnumber large groups (more than 100 members). Furthermore, the setting in small dynamic peer groups has different requirements from large groups: Autonomous and contributory key agreement, and fault tolerance to network partitions (members in each partition form an independent peer group).

  • Group Key Agreement Efficient in Communication PS, PDF, with Yongdae Kim and Gene Tsudik, to appear in IEEE Transactions on Computers.
  • Simple and Fault-Tolerant Key Agreement for Dynamic Collaborative Groups (the Tree Group Diffie Hellman (TGDH) protocol), PS, PS.GZ, PDF, HTML, BIB, with Yongdae Kim and Gene Tsudik, 7th ACM Conference on Computer and Communication Security CCS 2000.
  • Communication-Efficient Group Key AgreementPS, PS.GZ, PDF, HTML, BIB, with Yongdae Kim and Gene Tsudik, International Federation for Information Processing IFIP SEC 2001.
  • Efficient Collaborative Key Management Protocols for Secure Autonomous Group Communication, BIB, International Workshop on Cryptographic Techniques and E-Commerce CrypTEC '99.
More information is on the Secure Multicast Group (SMuG) web page.

Practical techniques for IP-traceback

Denial-of-service (DoS) attacks are among the most challenging security problems on today's Internet. One difficulty to thwart DoS attacks is to trace the source of the attacks because they often use incorrect, or ``spoofed'' IP addresses to disguise the true origin. We present two new schemes, the Advanced Marking Scheme and the Authenticated Marking Scheme, which allow the victim to traceback the approximate origin of spoofed IP packets. Our techniques have very low network and router overhead and support incremental deployment. Comparing with previous work, our techniques have significantly higher precision (lower false positive rate) and lower computation overhead for the victim to reconstruct the attack paths under large scale distributed denial-of-service attacks. Furthermore the Authenticated Marking Scheme provides efficient authentication of routers' markings such that even a compromised router cannot forge or tamper markings from other uncompromised routers. For more details:

Automatic Security Protocol Generation and Verification

The current process of designing a security protocol is usually ad-hoc and involves little formalism and mechanical assistance. Such a design process is not only slow but also error-prone. Evidence shows that even when security protocols are designed with care and examined intensely (even over time of years), they can still be fundamentally flawed. A classic example is the Needham-Schroeder public-key mutual authentication protocol, in which Gavin Lowe discovered a flaw 18 years later. Due to the lack of formalism and mechanical assistance, manually designed protocols often contain undocumented assumptions and hence can lead to implementation errors. Further, simply because a manual design process cannot search a large number of candidates, it may not find the optimal protocol for the given system requirements.

Hence, we design and implement a different approach, Automatic Protocol Generation (APG). The approach of APG is efficient and provides high confidence and high quality of protocols. APG is able to through large protocol space and generate protocols that suit the system the best.

For details about how APG works and the new protocols it generated in experiments:

  • A First Step towards the Automatic Generation of Security Protocols PS, PS.GZ, PDF, HTML, BIB, with Dawn Song. In Proc. of Network and Distributed System Security NDSS 2000, February 2000.
  • Looking for diamonds in the desert: Automatic security protocol generation for three-party authentication and key distribution PS, PS.GZ, PDF, HTML, BIB, with Dawn Song. In Proc. of IEEE Computer Security Foundations Workshop CSFW 13, July 2000.
  • AGVI --- Automatic Generation, Verification, and Implementation of Security ProtocolsPS, PS.GZ, PDF, HTML, BIB, with Dawn Song and Doantam Phan. In Proceedings of 13th Conference on Computer Aided Verification CAV 2001, July 2001.

Applied Cryptography

Search on Encrypted Data

It is desirable to store data on data storage servers such as mail servers and file servers in encrypted form to reduce security and privacy risks. But this usually implies that one has to sacrifice functionality for security. For example, if a client wishes to retrieve only documents containing certain words, it was not previously known how to let the data storage server perform the search and answer the query without loss of data confidentiality.

We design a cryptographic schemes for the problem of searching on encrypted data and provide proofs of security for the resulting crypto systems. Our technique is efficient and provably secure.

Human Factors in Computer Security

Hash Visualization and User Authentication through Image Recognition

Long random strings, such as digital fingerprints or hash values, are difficult to remember. It is much easier for people to deal with images instead of meaningless strings. We therefore generate a visual represantation of the hash value, which we call hash visualization. Hash visualization is particularly useful in settings where people need to repeatedly verify the integrity of data, because people can easily remember the images generated.

We also developped Déjà Vu, a method to authenticate people through image recognition. The key insight we had is to base the person authentication on a human strength instead of on a human weakness. Most currently used authentication schemes authenticate the user through precise recall, a task that people are not particularly good at. Instead, studies have shown that people are extremely good at recognizing previously seen images, which is the main ingredient of Déjà Vu. Furthermore, our system prevents people from picking poor passwords, writing down or sharing passwords with others, and prevents an attacker from guessing passwords.

In this research, we use Andrej Bauer's Random Art

Security and E-Commerce

Secure Auction Architecture

Increasing numbers of economic transactions are conducted through on-line auctions. Nevertheless, most current auction implementations fail to address important security concerns. In particular, most auction systems force buyers and sellers to trust the auctioneer; alternative secure systems are inflexible and have a high computational and/or communication overhead.

To overcome these limitations, we propose a secure auction marketplace (SAM) architecture, based on the recently available tool of high-performance, programmable secure coprocessors.

Unlike previous schemes, this approach provides a general framework that can incorporate arbitrary auction schemes by using different evaluation programs, as well as provide complex security properties by using the secure coprocessor and our auction protocols.

Our approach features strong security guarantees for the buyers and sellers without trusting the auctioneer, precise definition of the information disclosed during and after the auction, and high flexibility to adapt to new types of auctions.

Previous Projects

Digital Image Watermarking

Digital Image Watermarking was initially perceived by some people as the white knight of intellectual property protection. My position is that watermarking is an interesting research problem, and it may be one building block in the solution of IP protection.

In collaboration with Alexander Herrigel and Joseph O'Ruanaidh I worked on a digital image copyright environment which does not solely rely on the watermark in the image to enforce the copyright. My more recent research focused on the robustness of watermarking techniques.

Protection of medical databases

When releasing medical databases to the public, sensitive information needs to be removed from the database. Unfortunately, sensitive infomation could potentially be inferred from less sensitive information. In a class project with Dawn Song and Qifa Ke, we developed an algorithm that automatically finds inference rules in medical databases. This is an important step in removing sensitive information from the medical database.

  • The report is available in PS and HTML.

Other reports: