The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.

Covert Timing Channels, Caching, and Cryptography

Billy Bob Brumley

Doctoral dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the School of Science for public examination and debate in Auditorium AS1 at the Aalto University School of Science (Espoo, Finland) on the 16th of December 2011 at 12 noon.

Overview in PDF format (ISBN 978-952-60-4417-0)   [467 KB]
Dissertation is also available in print (ISBN 978-952-60-4416-3)


Side-channel analysis is a cryptanalytic technique that targets not the formal description of a cryptographic primitive but the implementation of it. Examples of side-channels include power consumption or timing measurements. This is a young but very active field within applied cryptography. Modern processors are equipped with numerous mechanisms to improve the average performance of a program, including but not limited to caches. These mechanisms can often be used as side-channels to attack software implementations of cryptosystems. This area within side-channel analysis is called microarchitecture attacks, and those dealing with caching mechanisms cache-timing attacks. This dissertation presents a number of contributions to the field of side-channel analysis. The introductory portion consists of a review of common cache architectures, a literature survey of covert channels focusing mostly on covert timing channels, and a literature survey of cache-timing attacks, including selective related results that are more generally categorized as side-channel attacks such as traditional timing attacks. This dissertation includes eight publications relating to this field. They contain contributions in areas such as side-channel analysis, data cache-timing attacks, instruction cache-timing attacks, traditional timing attacks, and fault attacks. Fundamental themes also include attack mitigations and efficient yet secure software implementation of cryptosystems. Concrete results include, but are not limited to, four practical side-channel attacks against OpenSSL, each implemented and leading to full key recovery.

This thesis consists of an overview and of the following 8 publications:

  1. Billy Bob Brumley and Risto M. Hakala. Cache-timing template attacks. In Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009, LNCS vol. 5912, pages 667-684, Springer, 2009.
  2. Onur Acıiçmez, Billy Bob Brumley, and Philipp Grabher. New results on instruction cache attacks. In Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, CA, USA, August 17-20, 2010, LNCS vol. 6225, pages 110-124, Springer, 2010.
  3. Billy Bob Brumley, Risto M. Hakala, Kaisa Nyberg, and Sampo Sovio. Consecutive s-box lookups: a timing attack on SNOW 3G. In Information and Communications Security - 12th International Conference, ICICS 2010, Barcelona, Spain, December 15-17, 2010, LNCS vol. 6476, pages 171-185, Springer, 2010.
  4. Billy Bob Brumley and Nicola Tuveri. Cache-timing attacks and shared contexts. In 2nd International Workshop on Constructive Side-Channel Analysis and Secure Design, COSADE 2011, Darmstadt, Germany, 24-25 February 2011, pages 233-242, Technische Universität Darmstadt / CASED, 2011.
  5. Billy Bob Brumley and Dan Page. Bit-sliced binary normal basis multiplication. In 20th IEEE Symposium on Computer Arithmetic, ARITH 2011, Tübingen, Germany, 25-27 July 2011, pages 205-212, IEEE Computer Society, 2011.
  6. Billy Bob Brumley and Nicola Tuveri. Remote timing attacks are still practical. In Computer Security - ESORICS 2011 - 16th European Symposium on Research in Computer Security, Leuven, Belgium, September 12-14, 2011, LNCS vol. 6879, pages 355-371, Springer, 2011.
  7. Billy Bob Brumley, Manuel Barbosa, Dan Page, and Frederik Vercauteren. Practical realisation and elimination of an ECC-related software bug attack. Accepted for publication in Topics in Cryptology - CT-RSA 2012 - The Cryptographers' Track at the RSA Conference 2012, San Francisco, CA, USA, February 27-March 2, 2012, LNCS, 18 pages, Springer, 2012.
  8. Billy Bob Brumley. Secure and fast implementations of two involution ciphers. Accepted for publication in 15th Nordic Conference on Secure IT Systems, NordSec 2010, Helsinki, Finland, 27-30 October 2010, LNCS vol. 7127, 14 pages, Springer, 2011.

Keywords: cryptography, covert channels, side-channel analysis, timing attacks, cache-timing attacks

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2011 Aalto University

Last update 2012-01-18