21-05-2012, 10:33 AM
Classical Authenticated Key Exchange and Quantum Cryptography
Classical Authenticated Key Exchange and Quantum Cryptography.pdf (Size: 2.3 MB / Downloads: 26)
Abstract
Cryptography plays an integral role in secure communication and is usually the
strongest link in the chain of security. Yet security problems abound in electronic
communication: spyware, phishing, denial of service, and side-channel attacks are
still major concerns. The main goal in this thesis is to consider how cryptographic
techniques can be extended to offer greater defence against these non-traditional
security threats.
In the first part of this thesis, we consider problems in classical cryptography.
We introduce multi-factor password-authenticated key exchange which allows secure
authentication and key agreement based on multiple short secrets, such as a
long-term password and a one-time response; it can provide an enhanced level of
assurance in higher security scenarios because a multi-factor protocol is designed to
remain secure even if all but one of the factors has been compromised due to attacks
such as phishing or spyware. Next, we consider the integration of denial of service
countermeasures with key exchange protocols: by introducing a formal model for
denial of service resilience that complements the extended Canetti-Krawczyk model
for secure key agreement, we cover a wide range of existing denial of service attacks
and prevent them by carefully using client puzzles. Additionally, we look at how
side-channel attacks affect certain types of formulæ used in elliptic curve cryptography,
and demonstrate that information leaked during field operations such as
addition, subtraction, and multiplication can be exploited by an attacker.
In the second part of this thesis, we examine cryptography in the quantum
setting. We argue that quantum key distribution will have an important role to play
in future information security infrastructures and will operate best when integrated
with the powerful public key infrastructures that are used today. Finally, we present
a new look at quantum money and describe a quantum coin scheme where the coins
are not easily counterfeited, are locally verifiable, and can be transferred to another
party.
iii
Acknowledgements
I am grateful to the many people who have helped me throughout my PhD. First, I
thank my supervisor, Michele Mosca, for his guidance and support over the years.
I am also grateful for the mentorship of my industrial supervisor, Sheueling Chang
of Sun Microsystems Laboratories, and the kind advice of Alfred Menezes.
Much of the work that appears in this thesis is the result of collaboration with
others: Sheueling Chang, Norbert Lütkenhaus, Matthew McKague, Michele Mosca,
Nicholas Thériault, Poornaprajna Udupi, and Berkant Ustaoglu.
I have had many helpful discussions with others during this PhD, including Scott
Aaronson, Niel de Beaudrap, Anne Broadbent, Donny Cheung, Isabelle Déchène,
Joseph Fitzsimons, Ian Goldberg, Nils Gura, Elham Kashefi, Debbie Leung, Bodo
Möller, Kenny Paterson, Barry Sanders, Miklos Santha, and John Watrous, and
received helpful reports from various anonymous referees.
My research and studies have been supported by an NSERC Industrial Postgraduate
Scholarship in conjunction with Sun Microsystems Laboratories, an NSERC
Canada Graduate Scholarship, and University of Waterloo Sinclair, William Tutte,
and President’s Postgraduate Scholarships, as well as funding for the Institute for
Quantum Computing from CIFAR, CFI, CSE, MITACS, and ORDCF.
Finally, I would like to acknowledge those whose friendship was especially important
to me during my PhD — Paul Dickinson, Matthew McKague, and Lana
Sheridan — and my parents who have encouraged me throughout my studies.
1.1 Introduction
Cryptography plays an essential role in modern life as it allows for secure communication
over insecure channels, even in the face of powerful adversaries. Cryptography
has been used for military and government communications for more than
2000 years, but only in the past 20 years has cryptography come to be used in
day-to-day life. The expansion of the Internet from a small-scale academic network
to a global network enabling hundreds of billions of dollars of electronic commerce
[Sho08] was due in no small part to the availability of cryptography.
The successful design of multitudes of secure cryptographic algorithms — public
key agreement, digital signatures, block and stream ciphers, hash functions, message
authentication codes — and secure protocols that employ these primitives is a
remarkable achievement. Of those that have been widely adopted, the majority
have remained fundamentally secure despite years of intensive cryptanalysis and
advancing computer technology.
Yet security problems abound on the Internet. The servers of governments and
major corporations are subjected to denial of service attacks. Spyware, viruses,
and malware are installed on users’ computers. Individuals fall victim to phishing
attacks and identity theft. Devices are subject to attacks that exploit subtle
variations in their power usage.
These security problems do not arise as a result of a break of cryptographic
algorithms or protocols. Rather, they arise by working around the cryptography:
1
Chapter 1. Introduction
why exert billions of hours of computer effort to break an advanced encryption
protocol to crack a user’s password when you can simply trick the user into telling
you their password directly?
The first part of this thesis aims to extend cryptographic techniques to offer
greater defence against some of these non-traditional security threats. Using cryptographic
protocols, we can defend users’ passwords from phishing attacks that
aim to trick the user into revealing their password to an attacker. We can protect
servers from being flooded by millions of bogus requests that would otherwise lead
to a denial of service attack during key establishment protocols. We can guard
against side-channel attacks that exploit variations in power consumption in elliptic
curve cryptography. By extending the scope of cryptography to these settings,
we can hope to offer greater robustness against attacks in a hostile communications
network.
While the discussion above deals with present threats, it is important to be
aware of threats that are on the horizon. One of the most significant discoveries in
theoretical computer science in the last 15 years was the field of quantum computation
which grew out of the notion that all computation is physical: computational
devices that exploit the properties of quantum physics will have a significant advantage
compared to current computers where the computational model is based
on classical physics. Most importantly for cryptography, large scale quantum computers
would be able to solve the hard problems that underlie the most widely used
public key cryptography systems — RSA, finite field Diffie-Hellman, and elliptic
curve cryptography — and which are the basis of security for the techniques in the
first part of this thesis.
Thus, the second part of this thesis considers the field of cryptography in a
quantum setting. Though quantum computers may eventually take away many of
the public key techniques that are widely used today, quantum cryptography makes
new tools available for use. The most researched of these new techniques is quantum
key distribution, where two parties can establish a secure key over an authentic,
public channel by using quantum communication. Most interestingly, the key that
is established is entirely independent of any inputs to the protocol, a feature which
cannot be achieved with classical physics. Quantum techniques can also be applied
to other cryptographic tasks, and one such task is digital cash: the no-cloning
theorem which prevents quantum states from being copied naturally leads one to
ask if one could create quantum money which could not be counterfeited because
of the laws of nature.
1.2 Contributions
We now summarize the main contributions of this thesis.
2
1.2.1 Classical Authenticated Key Exchange
1.2.1.1 Password-Authenticated Key Exchange (Chapter 3)
More Efficient PAK (Section 3.3.2.2) and More Efficient PAK-Z+ (Section
3.3.3.2) In this section we describe more efficient forms of the PAK and
PAK-Z+ protocols for password-authenticated key exchange. Our improvement for
the non-verifier-based PAK protocol allows the protocol to achieve the same number
of operations as Diffie-Hellman — two exponentiations — on both client and
server. For the verifier-based PAK-Z+ protocol, we achieve a protocol with just
three exponentiations on both client and server.
1.2.1.2 Multi-Factor Password-Authenticated Key Exchange
(Chapter 4)
In this chapter, we provide the first formal security treatment of multi-factor
password-authenticated key exchange. We define a formal model which is an extension
of the Bellare-Pointcheval-Rogaway model [BPR00] for password-authenticated
key exchange. We formalize the security notion that a multi-factor protocol should
remain secure even if all but one of the factors has been compromised by adapting
the definition of freshness of a session.
We present an efficient two-factor protocol, MFPAK, that is secure in this model
under standard cryptographic assumptions in the random oracle model.
Our multi-factor authentication protocol offers enhanced authentication protection
through two complementary factors, a long-term password and a one-time
response, and achieves two-factor security with the same computational efficiency
as the one-factor protocol mePAK-Z+ from Section 3.3.3.2. The protocol remains
secure even if all but one of the authentication factors is fully known to an adversary.
Protocols secure in our model are resistant to man-in-the-middle and impersonation
attacks, providing enhanced authentication in the face of more complex threats like
spyware and phishing.
Our work differs from previous work in password-authenticated key exchange because
it utilizes two independent, complementary factors for authentication. Other
work has considered some aspects of multi-factor authentication, but these have
either used at least one factor that is a long cryptographic secret (as opposed to
our work which allows both factors to be short, human-friendly strings), or have
not provided strong server-to-client authentication resistant to man-in-the-middle
attacks.
The work on models for multi-factor password authenticated key exchange and
the MFPAK protocol in Chapter 4 is joint work with Poornaprajna Udupi and
Sheueling Chang and appeared as the following publication:
Douglas Stebila, Poornaprajna Udupi, and Sheueling Chang. Multi-factor
3
Chapter 1. Introduction
password-authenticated key exchange. In preparation, 2009. eprint http:
//eprint.iacr2008/214.
1.2.1.3 Denial-of-Service-Resilient Authenticated Key Exchange (Chapter5)
In this chapter, we propose a formal model for denial of service attacks in the
context of the extended Canetti-Krawczyk (eCK) model for secure and authentic
shared key establishment that takes into account denial of service (DoS) attacks.
Whereas previous work focused mainly on proper DoS countermeasures, we are
interested in the integration of DoS countermeasures with key establishment: just
giving the client a puzzle and checking that it was solved is not enough to guarantee
denial of service resistance for key agreement.
We analyze many of the DoS attacks presented in the literature and argue that
they do not stem from a weak DoS countermeasure but from incorrect integration
into the key agreement protocol. Existing formal methods have already led to the
discovery of some novel DoS attacks, but not all attacks can be identified in this way.
Our model covers a wider range of denial of service resistance goals and provides
a framework which can be used to analyze and compare DoS countermeasures.
Previous formal treatments of denial of service deal with the two-party setting:
an honest server and an adversary. These previous models do not capture goals
related to hijacking of connections, but do allow for a fine analysis of the strength
of a DoS countermeasure. Our approach can be used in conjunction with previous
analyses: our model deals with the integration of DoS countermeasures and key
agreement protocols, and previous work can be used to analyze the strength of the
countermeasures.
The work on denial-of-service-resilient key exchange in Chapter 5 is joint work
with Berkant Ustaoglu.
1.2.1.4 Unified Point Addition Formulæ in Elliptic Curve Cryptography (Chapter 6)
In this chapter, we give a projective version of the elliptic curve unified point
addition formulæ of Brier, Déchène, and Joye [BDJ04]. We extend Walter’s sidechannel
attack [Wal04] to make use of the detection of a conditional addition which
appears in many field subtraction implementations. This conditional modular reduction
attack substantially decreases the amount of work necessary to recover the
key: when used with projective coordinates and Montgomery field representation
and combined with Walter’s original technique, our attack is feasible on prime field
elliptic curves up to 384 bits. We suggest some countermeasures which may help
achieve constant run-time field operations. We also provide some performance results
for the various unified point addition formulæ and discuss the applicability of
timing attacks.
4
Chapter 1. Introduction
The work on side-channel attacks on unified point addition formulæ in elliptic
curve cryptography in Section 6.3 is joint work with Nicholas Thériault and
appeared as the following publication:
Douglas Stebila and Nicolas Thériault. Unified point addition formulæ and
side-channel attacks. In Louis Goubin and Mitsuru Matsui, editors, Cryptographic
Hardware and Embedded Systems (CHES) 2006, LNCS, volume
4249, pp. 354–368. Springer, 2006. doi:10.1007/11894063_28. eprint
http://eprint.iacr2005/419.
1.2.2 Quantum Cryptography
1.2.2.1 The Case for Quantum Key Distribution (Chapter 7)
In this chapter, we examine the role of quantum key distribution (QKD) in cryptographic
infrastructures. QKD promises secure key agreement by using quantum
mechanical systems. We argue that QKD will be an important part of future cryptographic
infrastructures. It can provide long-term confidentiality for encrypted
information without reliance on computational assumptions. Although QKD still
requires authentication to prevent man-in-the-middle attacks, it can make use of
either information-theoretically secure symmetric key authentication or computationally
secure public key authentication: even when using public key authentication,
we argue that QKD still offers stronger security than classical key agreement.
The work on the case for quantum key distribution in Chapter 7 is joint work
with Michele Mosca and Norbert Lütkenhaus and appeared as the following publication:
Douglas Stebila, Michele Mosca, and Norbert Lütkenhaus. The case for
quantum key distribution. eprint arXiv:0902.2839, http://eprint.iacr.
org/2009/082.
1.2.2.2 Quantum Money (Chapter 8)
In this chapter, we present a new type of quantum money, which we call quantum
coins: coins are transferable, locally verifiable, and unforgeable, and have some
anonymity properties. Each coin generated by the bank is a copy of the same
quantum state; in such a scheme, coins should be indistinguishable from one another.
Additionally, a circuit is provided to allow the coins to be verified locally
and then transferred for later use.
We describe how to achieve quantum coins with black box quantum circuits and
with blind quantum computation. The unforgeability of coins in our scheme comes
from complexity theoretic assumptions on the adversary’s running time.
5
Chapter 1. Introduction
Our work on quantum coins contrasts with previous quantum money schemes,
which we call quantum bills: in a quantum bill scheme, the bank generates tokens
that are classical/quantum pairs, which in general are distinct. The classical string
may serve as a serial number or as some input value to be used in the verification
procedure.
The work on quantum money is joint work with Michele Mosca and parts of it
appeared as the following poster:
Michele Mosca and Douglas Stebila. A framework for quantum money. In
Quantum Information Processing (QIP) 2007.