Kryptographische Protokolle [KryptProt] · Bachelorstudiengang Informatik/IT-Sicherheit Kryptographische Protokolle [KryptProt] Autoren: Jörg Schwenk Tibor Jager Katrin Weiden Lehrstuhl

Bachelorstudiengang Informatik/IT-Sicherheit

Kryptographische Protokolle[KryptProt]

Autoren:

Jörg Schwenk

Tibor Jager

Katrin Weiden

Lehrstuhl Netz- und Datensicherheit

Modul ???

Kryptographische Protokolle[KryptProt]

Studienbrief 1: Introduction

Studienbrief 2: Introduction to Complexity Theory

Studienbrief 3: Cryptographic Foundations and Primitives

Studienbrief 4: Simple Protocols

Studienbrief 5: Zero-Knowledge (ZK)

Studienbrief 6: Authenticated Key Exchange (AKE)

Studienbrief 7: One-Round Key Exchange Protocols (ORKE)

Studienbrief 8: Transport Layer Security (TLS)

Studienbrief 9: Truncated TLS is a Secure AKE Protocol

Studienbrief 10: Authenticated and Confidential ChannelEstablishment (ACCE)

Studienbrief 11: Transport Layer Security (TLS) is a SecureACCE Protocol

Autoren:

Seite 2

Jörg SchwenkTibor JagerKatrin Weiden

1. Auflage

Lehrstuhl Netz- und Datensicherheit

© 2015 Lehrstuhl Netz- und DatensicherheitRuhr - Universität BochumUniversitätsstraße 15044801 Bochum

1. Auflage (13. Dezember 2015)

Didaktische und redaktionelle Bearbeitung:Jörg Schwenk & Katrin Weiden & Florian Giesen

Das Werk einschließlich seiner Teile ist urheberrechtlich geschützt. Jede Ver-wendung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohneZustimmung der Verfasser unzulässig und strafbar. Das gilt insbesonderefür Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspei-cherung und Verarbeitung in elektronischen Systemen.

Um die Lesbarkeit zu vereinfachen, wird auf die zusätzliche Formulierungder weiblichen Form bei Personenbezeichnungen verzichtet. Wir weisen des-halb darauf hin, dass die Verwendung der männlichen Form explizit alsgeschlechtsunabhängig verstanden werden soll.

Das diesem Bericht zugrundeliegende Vorhaben wurde mit Mitteln des Bun-desministeriums für Bildung, und Forschung unter dem Förderkennzeichen16OH1202 gefördert. Die Verantwortung für den Inhalt dieser Veröffentli-chung liegt beim Autor.

Inhaltsverzeichnis Seite 5

Inhaltsverzeichnis

Einleitung zu den Studienbriefen 8I. Abkürzungen der Randsymbole und Farbkodierungen . . . . . . . . . 8II. Zu den Autoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9III. Modullehrziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Studienbrief 1 Introduction 111.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.2 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Studienbrief 2 Introduction to Complexity Theory 132.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.4 Alan Turing: On computable numbers, with an application to the Ent-

scheidungsproblem (1937) . . . . . . . . . . . . . . . . . . . . . . . . 132.4.1 Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . 132.4.2 Church-Turing Thesis . . . . . . . . . . . . . . . . . . . . . . 162.4.3 Nondeterministic Turing Machines . . . . . . . . . . . . . . . 17

2.5 Time and Space Complexity . . . . . . . . . . . . . . . . . . . . . . . 172.5.1 Polynomial Reductions . . . . . . . . . . . . . . . . . . . . . . 182.5.2 Efficiently Computable Functions: The class P . . . . . . . . . 182.5.3 Efficiently Verifiable Functions: The class NP . . . . . . . . . . 192.5.4 The P 6= NP Conjecture . . . . . . . . . . . . . . . . . . . . . 20

2.6 Negligible Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Studienbrief 3 Cryptographic Foundations and Primitives 233.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.4 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.5 Mathematical Foundations . . . . . . . . . . . . . . . . . . . . . . . . 23

3.5.1 Mathematical Groups . . . . . . . . . . . . . . . . . . . . . . 233.5.2 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.5.3 Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.6 Cryptographic Foundations . . . . . . . . . . . . . . . . . . . . . . . 243.7 Cryptographic Primitives: Hash Functions . . . . . . . . . . . . . . . . 24

3.7.1 Collission Resistant Hash Functions . . . . . . . . . . . . . . . 243.7.2 Random Oracles . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.8 Cryptographic Primitives: Randomness . . . . . . . . . . . . . . . . . 243.8.1 Pseudo-Random Functions . . . . . . . . . . . . . . . . . . . 24

3.9 Cryptographic Primitives: Message Integrity . . . . . . . . . . . . . . 253.9.1 Message Authentication Codes . . . . . . . . . . . . . . . . . 253.9.2 Digital Signature Schemes . . . . . . . . . . . . . . . . . . . 25

3.10 Cryptographic Primitives: Confidentiality/Encryption . . . . . . . . . . 263.10.1 Symmetric Encryption . . . . . . . . . . . . . . . . . . . . . . 263.10.2 Authenticated Encryption . . . . . . . . . . . . . . . . . . . . 263.10.3 Stateful Length-Hiding Authenticated Encryption . . . . . . . 263.10.4 Public Key Encryption . . . . . . . . . . . . . . . . . . . . . . 273.10.5 Key Encapsulation Mechanism (KEM) . . . . . . . . . . . . . . 27

3.11 Complexity Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . 273.11.1 The RSA Assumptions . . . . . . . . . . . . . . . . . . . . . . 273.11.2 The Discrete Logarithm Assumption . . . . . . . . . . . . . . 273.11.3 The Computational Diffie-Hellman Assumption . . . . . . . . 273.11.4 The Decisional Diffie-Hellman Assumption . . . . . . . . . . . 28

Seite 6 Inhaltsverzeichnis

3.11.5 PRF-ODH Assumtion . . . . . . . . . . . . . . . . . . . . . . . 28

Studienbrief 4 Simple Protocols 314.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.4 Key Agreement Protocols . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.4.1 Shamir’s No-Key Protocol . . . . . . . . . . . . . . . . . . . . 314.4.2 Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . . 324.4.3 Security of the Diffe-Hellman protocol . . . . . . . . . . . . . 334.4.4 ElGamal Encryption . . . . . . . . . . . . . . . . . . . . . . . 364.4.5 RSA-KEM Key Transport Algorithm . . . . . . . . . . . . . . . 37

4.5 Authentication Protocols . . . . . . . . . . . . . . . . . . . . . . . . . 384.5.1 Challenge-and-Response . . . . . . . . . . . . . . . . . . . . 384.5.2 Signed Challenge-and-Response . . . . . . . . . . . . . . . . 394.5.3 Signed Timestamp . . . . . . . . . . . . . . . . . . . . . . . . 394.5.4 (Public-Key) Encrypted Nonce . . . . . . . . . . . . . . . . . . 39

4.6 Authenticated Key Exchange . . . . . . . . . . . . . . . . . . . . . . . 394.6.1 Signed Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 394.6.2 TLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.6.3 SSH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.6.4 IPSec IKE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Studienbrief 5 Zero-Knowledge (ZK) 435.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.2 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.4 Zero-Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.4.1 Introduction to Zero-Knowledge . . . . . . . . . . . . . . . . 435.4.2 Formalizing Zero-Knowledge . . . . . . . . . . . . . . . . . . 43

5.5 Fiat-Shamir-heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.6 Fiat-Shamir protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.7 Quadratic Remainder . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Studienbrief 6 Authenticated Key Exchange (AKE) 456.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.2 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.4 Bellare-Rogaway Model . . . . . . . . . . . . . . . . . . . . . . . . . 456.5 AKE Protocols: MAP1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 506.6 AKE Protocols: AKEP1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 546.7 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Studienbrief 7 One-Round Key Exchange Protocols (ORKE) 617.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 617.2 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 617.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617.4 2-Message Protocols: Signed Diffie-Hellman . . . . . . . . . . . . . . 617.5 Canetti-Krawczyk Model . . . . . . . . . . . . . . . . . . . . . . . . . 627.6 2-Message Protocols: HMQV . . . . . . . . . . . . . . . . . . . . . . . 627.7 2-Message Protocols: NAXOS . . . . . . . . . . . . . . . . . . . . . . . 64

7.7.1 Protocol Description . . . . . . . . . . . . . . . . . . . . . . . 647.7.2 Security Model: eCK . . . . . . . . . . . . . . . . . . . . . . . 647.7.3 Security Proof . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Studienbrief 8 Transport Layer Security (TLS) 718.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 718.2 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Inhaltsverzeichnis Seite 7

8.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718.4 TLS Handshake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718.5 TLS Record Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748.6 TLS Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748.7 Cryptographic Attacks on TLS . . . . . . . . . . . . . . . . . . . . . . 74

Studienbrief 9 Truncated TLS is a Secure AKE Protocol 759.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 759.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759.3 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 759.4 Truncated TLS with Ephemeral Diffie-Hellman is a Secure AKE Protocol 75

9.4.1 Authentication . . . . . . . . . . . . . . . . . . . . . . . . . . 769.4.2 Indistinguishability of Keys . . . . . . . . . . . . . . . . . . . 82

9.5 Truncated TLS with Static Diffie-Hellman is a Secure AKE Protocol . . 849.6 Truncated TLS with RSA Key Transport is a Secure AKE Protocol . . . . 84

Studienbrief 10 Authenticated and Confidential Channel Establishment(ACCE) 85

10.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 8510.2 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 8510.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8510.4 Introduction to ACCE Protocols . . . . . . . . . . . . . . . . . . . . . . 8510.5 Execution environment . . . . . . . . . . . . . . . . . . . . . . . . . . 8510.6 Security Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8610.7 Relation to the AKE Security Definition from Section 6 . . . . . . . . . 8710.8 Generic Constructions for ACCE Protocols . . . . . . . . . . . . . . . . 88

Studienbrief 11 Transport Layer Security (TLS) is a Secure ACCE Proto-col 89

11.1 Education Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 8911.2 Advanced Organizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 8911.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8911.4 TLS with Ephemeral Diffie-Hellman is a Secure ACCE Protocol . . . . . 8911.5 On Proving Security of TLS-DHE from Standard Assumptions . . . . . 9211.6 TLS with Static Diffie-Hellman or RSA Key Transport is a Secure ACCE

Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Verzeichnisse 97I. Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97II. Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97III. Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97IV. Kontrollaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98V. Sätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98VI. Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Seite 8 Einleitung zu den Studienbriefen

Einleitung zu den Studienbriefen

I. Abkürzungen der Randsymbole und Farbkodierungen

Beispiel B

Definition D

Kontrollaufgabe K

Satz S

Übung Ü

Zu den Autoren Seite 9

II. Zu den Autoren

Bild fehlt beschreibender Text

Bild fehlt weiterer Text

Bild fehlt weiterer Text

Seite 10 Einleitung zu den Studienbriefen

III. Modullehrziele

Hier fehlen noch die Lehrziele!

Studienbrief 1 Introduction Seite 11

Studienbrief 1 Introduction

1.1 Education Objectives

This book is on real-life cryptographic protocols like SSL/TLS, IPSec/IKE and SSH.They are the most important cryptographic protocols existing, although a largevariety of academic protocols exist.

Most real-live protocols are used to combine key establishment and entity authenti-cation. Only this combination yields cryptographic security in open networks. Thusthey are often summarized under the term “Authenticated Key Establishment“(AKE).

Real-life protocols are much more complex than their academic counterparts, andoften poorly documented. Nevertheless, they can be analyzed in a strictly scientificmanner, based on Complexity Theory and standard cryptographic assumptions.

The ultimate goal of this book is thus to give deep insight in the working of suchprotocols, to guide future improvements, and to discover security weaknessesbefore they can be exploited.

1.2 Advanced Organizer

Chapter 2 gives a very basic introduction to computational complexity theory.

Chapter 3 introduces the language in which protocols, theorems, definitions andproofs are formulated. We introduce abstract cryptographic objects like “pseudo-random functions“, “digital signatures“, "key encapsulation mechanisms“, andso on. For all these objects exist real implementations, e.g. HMAC-SHA256 as animplementation of a pseudorandom function. However, within the limitations ofcomplexity theory, the real security properties of these implementations remainunprovable.

In Chapter 4, some basic cryptographic protocols are introduced. Some of them arepurely academic examples, and some of them (e.g. Diffie-Hellman Key Exchange)will be used later to construct more complex protocols.

Chapter 5 introduces a type of protocols which historically were the first protocolswith a formal security model and formal, reduction-based security proofs.

With Chapter 6 we enter the realm of AKE protocols. Research started here withthe seminal paper of Bellare and Rogaway, and we will present their models andexample protocols.

A slightly different model (the Canetti-Krawczyk model) is presented in Chapter 7.We need this model to analyze one-round (two message) protocols, which do notfit in the Bellare-Rogaway model.

With Chapter 8 we introduce TLS, and analyze it in the remaining chapters.

Studienbrief 2 Introduction to Complexity Theory Seite 13

Studienbrief 2 Introduction to Complexity Theory


All formal models in this book are Turing machine based, and all proofs arereduction based. Cryptographic primitives are only secure if they are “hard” tobreak, i.e. if the computing time it needs to break them is very large. All these areconcepts from complexity theory, therefore a short description will be given hereto provide a better understanding of later chapters.

After working throgh this chapter, students should

• know what a Turing Machine is;

• understand the concept of time complexity;

• be able to follow a polynomial reduction described later in this book;

• know what the P 6= NP assumption is about and

• understand the definition of “negligible function”.


2.3 Related Work

• Alan Turing: On computable numbers, with an application to the Entschei-dungsproblem (1937) [28].

• Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languagesand Computation [19].

2.4 Alan Turing: On computable numbers, with anapplication to the Entscheidungsproblem (1937)

In 1937 a young mathematician named Alan Turing published an article aboutcomputability [28]. No computers existed at that point of time (Turing was to buildone of the first in Bletchley Park during WW II), but the problem was alreadyfamous and well-know in the mathematical community: Which functions can becomputed by constructive means, i.e. by some kind of algorithm?

2.4.1 Turing Machines

To answer this question, first the term “algorithms” had to be defined in a mathe-matically precise way. Turing achieved this through the definition of a constructthat is now called a Turing Machine (TM) (see Definition 2.1).

Turing observed himself while doing computations on a sheet of squared paper:He read symbols written on the paper, applied some short mental operations (e.g.

Seite 14 Studienbrief 2 Introduction to Complexity Theory

multiplying or adding single numbers) to them, and wrote the results back to thepaper.

B Beispiel 2.1

The prototype of such paper-and-pencil operations is manual multiplicationor division of large integer numbers. Here the human performs a finite setof elementary operations in his mind (e.g. multiplying two integer numbersfrom the set {0, ...,9} (“Kleines Einmaleins”), and writes intermediate re-sults on the paper. Later he adds columns of numbers, another elementaryoperation.

6 · 4 22 4

1 22 5 2

By changing the elementary operations, the algorithm can be ported to otherdomains, e.g. binary numbers or polynomial multiplication/division.

Turing then simplified his observations into a purely mathematical model:

• Instead of the two-dimensional array of squared paper (“kariertes Papier”),he used a one-dimensional tape with cells which may contain exactly onsymbol from the tape alphabet Γ. This tape is infinitely long in both directi-ons.

• Instead of the human brain he used a finite state automaton. This is a set Qof different states (shown as aoctagons in Figure 2.1) and a partial functioncalled transition function.

• The finite state automaton may read and overwrite symbols on the tape.This is similar to a mathematician working with pencil and eraser.

2.4 AlanTuring:On computable numbers,with an application to the Entscheidungsproblem (1937) Seite 15

DDefinition 2.1: Turing Machine [19]

A Turing Machine M is a tuple M = (Q,Γ,b,Σ,δ ,q0,F), whereQ is a finite, non-empty set of states,Γ is the tape alphabet,β ∈ Γ is the blank symbol,Σ⊆ Γ−{β} is the input alphabet,q0 ∈ Q is the initial state,F ⊆ Q is the set of final or accepting states, andδ : (Q−F)×Γ→ Q×Γ×{L,R} is a partial function called the transitionfunction.

A Turing machine is started by setting its internal state to q0, writingthe input string on the (infinite) tape, and positioning its read/writehead on the first input symbol. As long as no accepting state is reached,δ (s,q) = (s′,q′,m) is evaluated, where s is the actual state of the TM, and q isthe symbol read by the read/write head from the tape. As a result of thisevaluation of δ , the internal state of M is set to s′, the symbol q′ is writtenon the tape by overwriting q, anf the read/write head either moves right(m = R) or left (m = L).

β f o r ☐ i = 0 ☐ t o ☐ 1 7 ☐ d o β β β ... ...

q0 q9

q1 q3

f1

q2

(ý;ý,R)

(if; if,R)

(f;f,R) (☐;☐,R)

(o;o,R) (r;r,R)

Abb. 2.1: Turing Machine.

Let’s exemplify the execution of a Turing machine with the example from Figure2.1. Here the Turing machine starts in the internal state q0 and the read/write headis initially positioned on the first input symbol f . The transition function yieldsδ (q0, f ) = (q1, f ,R) (denoted by q0→ ( f ; f ,R)→ q1 in the figure). Hence, the newstate is q1, the head overwrites the existing f with a new f , thus preserving thevalue of the input tape, and the head moves one position to the right on the nextinput symbol o. The next step is given by δ (q1,o) = (q2,o,R); again the symbol oread is not changed, the new state is q2 and the read/write head again moves one


position to the right. This procedure continues until either a accept or reject stateis reached. In this example only a Part of the Turing algorithm is shown.

D Definition 2.2: Configuration of a Turing Machine.

The configuration or snapshot of a Turing Machine is a description of thestatus of a computation at a certain step. It contains the contents of thetape, the position of the read/write head, and the current state of the finiteautomaton.

We now have to define the task of a Turing Machine. Intuitively, a TM shouldcompute something, e.g. the product of two numbers, or the factorization of a largecomposite number.

However, there are also other tasks where a TM has to recognize strings that havea certain structure, e.g. check if a give number is prime, or check if a file containscorrect C-code. This second class of tasks is easier to describe, and thus is used athe basis for complexity theory.

Strings are finite sequences of characters (symbols) from some finite alphabet (e.g.{0,1}, ASCII, UTF-8, ...). Alphabets are usually denoted by Σ, and Σ∗ denotes the(infinite) set of all finite sequences of symbols from Σ.

D Definition 2.3

A language L is a subset of Σ∗.

This definition is very general. Typically we are only interested in languages thathave a certain structure, e.g.

• Lpal , the set of all palindromes from the alphabet of all alphanumerical ASCIIsymbols: {OT TO,oT To,1234321,1w3 f 3w1} ⊂ Lpal ;

• LJAVA, the set of all well-formed JAVA sourcecode files;

• LPRIME , the set of all prime numbers.

An example of a language that will play an important role in this book is LDDH .Here the alphabet Σ is the set of group elements of a cyclic group G =< g >, andLDDH consists of all triples (ga,gb,gab)where thenthird value is the outcome of aDiffie-Hellman computation on the first two values.

There is also a computational variant of the problem, the Computational-Diffie-Hellmann (CDH). Here the task consist of constructing a TM which is “fast” andcomputes gab from ga and gb. Please notice that if we are able to construct a “fast”CDH-TM, the we can also construct a “fast” DDH-TM: This is due to the fact thatin the DDH setting we can simply call its CDH-algorithm as a subroutine and thencompare its computed result with gc.

2.4.2 Church-Turing Thesis

During the 1930’s and 1940’s, differentmodels for computation have been proposed:λ -Calculus, Fully Recursive Functions, and von-Neumann computers. In each case,equivalence results could be given: If some problem can be solved in one model,then also in the others.

2.5 Time and Space Complexity Seite 17

Thus the so-called Church-Turing Thesis today is generally believed to b true: Thisthesis states that all these equivalent models exactly define what is computable,and that no other formalizations may exist.

2.4.3 Nondeterministic Turing Machines

A special class of TuringMachines, which have no equivalent in real-life computers,is used as a means to define different complexity classes, especialls the class NPwhich contains all cryptographically relevant problems.

A nondeterministc Turing Machine is able to perform arbitrary many computationsin parallel. I.e. for each if then else construct, both the if and the else branchwill be followed, and in for i=1 to 1.000.000, all 1.000.000 alternatives will becomputed in one step (if they are independat form each other).

To give one example: A nondeterministic TM is able to factor large compositenumbers n in constant time. Instead of sequentially trying all numbers from 2 to√

n for being divisors of n, we try them all simultaneously!

Despite the fact that they are not implementable, there is a mathematical sounddefinition: We only have to change the definition of the transition function δ , whichnow maps into the power set P(Q×Γ×{L,R}).

The running time of a nondeterministic TM is defined to be the maximum of therunning times of all parallel processes.

Please note that nondeterministic TMs do not violate the Church-Turing thesissince they do not change the set of computable functions, or the set of recognizablelanguages.

2.5 Time and Space Complexity

If we use a Turing Machine as our computing model, two types of ressources caneasily be defined:

1. Time Complexity: The number of invocations of the transition function (orthe number of steps the TM makes).

2. Space Complexity: The number of tape cells used during one computation.

It should be clear that the absolute number of steps or tape cells directly dependson the length of the input, i.e. the length of the word that should be checked formemebership in a language L. If the length of such aword w is |w|= n, thenwe needat least n cells to write it onto the input tape, and n steps to scan it once. In general,time and space complexity are functions t(n) and s(n) of the input length.

Turing Machines come in different flavors: there are TMs with multiple tapes,interactive TMs where each pair of TMs shares a common tape, and TMs wherethe read/write head can also stay at the same position. All these variants arepolynomially equivalent, i.e. if a word a∈ L is recognized by one type of TM in t steps,then there is a polynomial p(x) such that any other type of TM takes at most p(t)steps.

If we want to group problems an languages in different, clearly defined complexityclasses, we have to take into account that the absolute time complexity may changepolynomially when switching between different types of TMs. Thus is makes senseto say that two problems are in the same complexity class, if their complexity


functions only differ polynomially, i.e. if if there is a fixed polynomial p(x) suchthat if problem 1 can be solved in time t(n), then problem 2 can be solved in timep(t(n)).

In the following we will only consider time complexity, because for cryptographythis is the most critical ressource.

2.5.1 Polynomial Reductions

If we want to show equivalence between two problems (laguages), we must showthat two algorithms exist: One that transforms the TM for problem 1 into a TMfor problem 2, and one for the opposite direction. Time complexity should onlyincrease polynomially for each transform.

In cryptography, equivalence results are rare. Usually we will give a reductiononly for one direction. E.g. if we want to show a result like “Theorem A holds ifassumption B is valid’, we have to give a polynomial reduction that transforms anyalgorithm that breaks Theorem A into an algorithm that breaks assumption B.

Lets consider one standard example, for which we must informally introduce twocryptographic assumptions which will be formalized later.

• The Decisional Diffie-Hellman assumption (DDH) for G states that in themathematical group G =< g > it is impossible to efficiently distinguish (real)tuples (g,ga,gb,gab) from (random) tuples (g,ga,gb,gr).

• The Computational Diffie-Hellman assumption (CDH) for G states that in themathematical group G =< g > it is impossible to efficiently compute gab

from ga and gb.

We can now prove “CHD holds in G if DDH is valid in G” by using a polynomialreduction. We therefore assume that Alg is an arbitrary algorithm that computesgab = Alg(ga,gb). We now tranform it into an algorithm Alg∗ that distinguishesDDH tuples.

Alg∗(g,ga,gb,gc):

1. Compute h = Alg(ga,gb).

2. If h = gc output “real” else output “random”.

This transformation works for any algorithm Alg. It is a polynomial reductionbecause it only adds one comparison operation to the complexity of Alg, andindeed p(x) = x+1 is a polynomial.

2.5.2 Efficiently Computable Functions: The class P

We now define a complexity class P of algorithms which are efficiently computable.This class e.g. contains all important mathematical algorithms which are usedon computers, from (binary) addition, multiplication, division, exponentiation tocomplex algorithms which decide if a given number is prime or not.

2.5 Time and Space Complexity Seite 19

To formally define this class, we have to go through a sequence of definitions.

DDefinition 2.4

O( f ) is the set of functions g such that for some r > 0 and for all but finitelymany n we have g(n)< r · f (n).

Definition 2.4 is very useful if the complexity of one single, clearly describedalgorithm is to be defined. E.g. the sorting algorithm QUICKSORT needs at mostO(n · log(n)) SWAP operations on consecutity elements in a list of n numbers to sortthis list.

DDefinition 2.5

DT IME(t) is the set of all Languages accepted by Turing Machines withrunning time bounded by O(t(n)).

In the set DT IME(t) all languages are collected where the running time of thebest known algorithm to recognize this language is bounded by the polynomialt(x). Of course if L ∈ DT IME(t), then also L ∈ DT IME(t + 1), L ∈ DT IME(2t), orL ∈ DT IME(t2).

DDefinition 2.6

P =⋃

i∈N DT IME(ni).

Sincewe have now computed the union over all polynomials, this class of languagesis invariant under changes of the TM model, because such a change may only alterthe running time polynomially.

2.5.3 Efficiently Verifiable Functions: The class NP

The class NP can be defined in two different ways: (1) Mathematically exact as theset of languages that will be accepted by a nondeterministc TM in polynomial time,and (2) practically useful as the set of languages where a proof of membership canbe checked by a deterministic TM in polynomial time.

The problem with defining NP as in (2) is that it remains unclear what a “poof” isin general. If we go for individual languages, such proofs can however easily bedefined:

• A proof of membership for n ∈ LCOMPOSIT E , the language of non-prime num-bers, is simply a factor n1 of n. Then a polynomial (deterministc) TM caneasily check if n

n1is a natural number.

• A proof of membership for (g,ga,gb,gr) ∈ LDDH is one of the exponents, e.g.a. Then a polynomial (deterministic) TM can simply check if (gb)a equals gr.


D Definition 2.7

NT IME(t) is the set of all Languages where

• membership can be checked by a nondeterministic TM or where

• a proof of membership can be checked by (normal, deterministic)Turing Machines

with running time bounded by O(t(n)).

Again, we take the union of all polynomials to get a complexity class invaribale tochanges of the TM model, and to polynomial reductions.

D Definition 2.8

NP =⋃

i∈N NT IME(ni).

2.5.4 The P 6= NP Conjecture

One of the big open questions in Complexity Theory (and in theoretical ComputerScience) today is if P 6= NP. The known relation between these two classes can beseen in Figure 2.2.

Abb. 2.2: Relation bet-ween classes P and NP.

Many natural problems (like Travelling Salesman, Satisfiability of Boolean Expres-sions, 3-Colorings of Maps) in NP are known to be NP-complete. These problemsare the “hardest” problems to solve: If we can find a polynomial, deterministicalgorithm to solve one of them, wen can solve all problems in NP in polynomialtime! (We will come bach to this issue in the next section.)

There are only few problems in NP which are known to be in NP, but not beingNP-complete. One of these problems is the problem to decide whether two graphsare isomorphic or not (GRAPHISO).

The class co-NP is the class of languages L where L := Γ∗−L ∈ NP.

2.6 Negligible Functions Seite 21

Interestingly, the interesection of CO-NP and NP contains nearly all problems onwhich todays cryptography is based. This is illustrated in Figure 2.3.

Abb. 2.3: Relation-ship between clas-ses P and NP and NP-Completeness.

If the P 6= NP conjecture holds, then running time of any (deterministic) TM thattries to solve a problem from NP−P cannot be bounded by any polynomial, ifthe length of the input increases. I.e. for each polynomial p(x) there is an inputlength np such that for all inputs y with |y| ≥ np the running time of T M(y) is strictlygreater than p(|y|).

Remark: It may be easier (although not mathematically correct) to think of NP−Pas the class of problems that have exponential running time. One example would bethe trivial algorithm to solve the satifiability problem SAT in n Boolean variables,which simply tries all 2n possible values.

DDefinition 2.9

Let X be a finite set of Boolean variables, i.e. variables that may only beassigned the values TRUE (1) and FLASE (0). The set of Boolean formulas overX is the smallest set which is defined by:

1. The Boolean contants 1 and 0 are Boolean formulas.

2. For every Boolean variable x ∈ X , x is a Boolean formula.

3. If F anf G are Boolean formulas, then (F ∨G), (F ∧G) and F areBoolean formulas.

The SAT problem is defined as follows: Given a Boolean formula f withn variablen x1, . . . ,Xn, find an assignment of these variables to the values{TRUE,FALSE} such that f evaluates to TRUE.

2.6 Negligible Functions

In cryptography,wewill oftenmake statements about something being “negligible”.This is a concept related to the concept of algorithms in NP−P: In both cases, weare talking about the behavious of a function when (the length of) its argumentsapproach infinity. However, while the running time of an algorithm in NP−P


grows faster than any polynomial, the value of a negligible function shrinks fasterthan the inverse of any polynomial.

D Definition 2.10

A function f : N→ R+ is called negligible if for every polynomial p(λ ) andall sufficiently great λ holds that f (λ )< 1

p(λ )

Studienbrief 3 Cryptographic Foundations and Primitives Seite 23

Studienbrief 3 Cryptographic Foundations and Primitives

Christoph, kannst Du dieses Kapitel mit den Standarddefinitionen füllen?


This section is not intended for being read, but for reference purposes. Thus theobjective is to provide a clear and well-structured reference text.


3.3 Related Work

In this section we recall standard cryptographic definitions and primitives. Moredetails on collision resistant hash functions can be found in [26]. For more in-formation about pseudo-random functions we refer to [17? ]. MACs were firstsystematically analyzed in [4]. Security for digital signature schemes was firstformalized in [? ] and for more details about stateful length-hiding encryption werefer to [25].

The introduced complexity assumptions are fairly standard, except for thePRF-ODH assumption which is discussed in [20, 21].

3.4 Preliminaries

We denote with /0 the empty string, and with [n] = {1, . . . ,n} ⊂ N the set of integersbetween 1 and n. If A is a set, then a $← A denotes the action of sampling a uniformlyrandom element from A. If A is a probabilistic algorithm, then a $← A denotes thatA is run with fresh random coins and returns a.

If, in an indistinguishability based setting, a party P has to distinguish two valuesv0 and v1, then the advantage AdvP is defined as AdvP := |Pr[P(v) = b|v = vb]− 1

2 |.This reflects the fact that party P can always guess the bit b with probability 1

2 , butin this case the advantage would be 0 and thus be negligible.

3.5 Mathematical Foundations

3.5.1 Mathematical Groups

group, group operation, subgroup, order of subgroups

3.5.2 Finite Fields

GF(p), multiplicative group, classification

3.5.3 Elliptic Curves

Definition over R, point addition, group laws (associativity), definition overGF(p)

Seite 24 Studienbrief 3 Cryptographic Foundations and Primitives

3.6 Cryptographic Foundations

3.7 Cryptographic Primitives: Hash Functions

In this sectionwe recall syntax and security notions for the cryptographic primitivesto which we will refer lateron.

3.7.1 Collission Resistant Hash Functions

3.7.2 Random Oracles

3.8 Cryptographic Primitives: Randomness

3.8.1 Pseudo-Random Functions

A pseudo-random function is an algorithm PRF. This algorithm implements a deter-ministic function z = PRF(k,x), taking as input a key k ∈KPRF and some bit stringx, and returning a string z ∈ {0,1}µ .

Consider the following security experiment played between a challenger C and anadversary A .

1. The challenger samples k $← KPRF uniformly random, and tosses a coinb $←{0,1}.

2. The adversary may query arbitrary values xi to the challenger. Here i isan index, ranging between 1≤ i≤ q for some q ∈ N. Queries can be madeadaptively.

• If b = 0, the challenger replies to each query with z0i := PRF(k,xi).

• If b = 1, the challenger replies to each query with z1i

$←{0,1}µ .

3. Finally, the adversary outputs a guess b′ ∈ {0,1}.

D Definition 3.1

We say that PRF is a (t,εPRF)-secure pseudo-random function, if an adversaryrunning in time t has at most an advantage of εPRF to distinguish the PRFfrom a truly random function, i.e.∣∣Pr

[b = b′

]−1/2

∣∣≤ εPRF.

The number of allowed queries q is upper bounded by t (see Def. 3.3).

Remark 1. This definition is a slight modification of the standard definition: In thestandard definition, the challenger answers all queries from the adversary withpseudorandom values. The cahllenger only flips a coin when he receives a value xtogether with a special symbol >.Remark 2. In 2008, Fouque et al. [16] showed that the HMAC-based key-derivationfunction of TLS is a pseudo-random function for 1) KPRF = S, where S is a prime-order group of size |S| = q that is either defined over an elliptic curve or as asubgroup of Z∗p such that q|p−1, and 2) KPRF = {0,1}l where l is the size of themaster-secret (l = 384). The underlying security assumptions are all related to thefact that the compression function of the hash function used in HMAC behaveslike a pseudo-random function. More details can be found in [16].

3.9 Cryptographic Primitives: Message Integrity Seite 25

3.9 Cryptographic Primitives: Message Integrity

3.9.1 Message Authentication Codes

A message authentication code is an algorithm MAC. This algorithm implementsa deterministic function w = MAC(Kmac,m), taking as input a (symmetric) keyKmac ∈ {0,1}κ and a message m, and returning a string w.


1. The challenger samples Kmac$←{0,1}κ uniformly random.

2. The adversary may query arbitrary messages mi to the challenger. The chal-lenger replies to each query with wi = MAC(Kmac,mi). Here i is an index,ranging between 1≤ i≤ q for some q ∈ N. Queries can be made adaptively.

3. Eventually, the adversary outputs a pair (m,w).

DDefinition 3.2

We say thatMAC is a (t,εMAC)-secure message authentication code, if for alladversaries A that run in time t holds that

Pr[(m,w) $←A C (1κ) : w =MAC(Kmac,m)∧m 6∈ {m1, . . . ,mq}

]≤ εMAC.

As in Def. 3.3 and 3.1 it holds that q≤ t, where q is the number of allowedqueries.

3.9.2 Digital Signature Schemes

A digital signature scheme is a triple SIG= (GenSIG,SignSIG,VfySIG), consisting of akey generation algorithm (sk, pk) $← GenSIG(1κ) generating a (public) verificationkey pk and a secret signing key sk on input of security parameter κ , signing al-gorithm σ

$← SignSIG(sk,m) generating a signature for message m, and verificationalgorithm VfySIG(pk,σ ,m) returning 1, if σ is a valid signature for m under key pk,and 0 otherwise.


1. The challenger generates a public/secret key pair (sk, pk) $← GenSIG(1κ), theadversary receives pk as input.

2. The adversary may query arbitrary messages mi to the challenger. The chal-lenger replies to each query with a signature σi = SignSIG(sk,mi). Here i isan index, ranging between 1≤ i≤ q for some q ∈ N. Queries can be madeadaptively.

3. Eventually, the adversary outputs a message/signature pair (m,σ).


D Definition 3.3

We say that SIG is (t,εSIG)-secure against existential forgeries under adaptivechosen-message attacks (EUF-CMA), if for all adversaries A that run in time tit holds that

Pr[(m,σ)

$←A C (1κ , pk) such that VfySIG(pk,m,σ) = 1∧m 6∈ {m1, . . . ,mq}]≤ εSIG.

Note that we have q ≤ t, i.e. the number of allowed queries q is bound bythe running time t of the adversary.

3.10 Cryptographic Primitives: Confidentiality/Encryption

3.10.1 Symmetric Encryption

3.10.2 Authenticated Encryption

3.10.3 Stateful Length-Hiding Authenticated Encryption

Let us now describe the stateful variant of LHAE security (the following des-cription and security model was obtained from the authors of [25] via personalcommunication). See [25] for a detailed discussion and motivation of this model.

A stateful symmetric encryption scheme consists of two algorithms StE =

(EncStE,DecStE). Algorithm (C,st ′e)$← EncStE(k, len,H,m,ste) takes as input a se-

cret key k ∈ {0,1}κ , an output ciphertext length len ∈ N, some header dataH ∈ {0,1}∗, a plaintext m ∈ {0,1}∗, and the current state ste ∈ {0,1}∗, and outputseither a ciphertext C ∈ {0,1}len and an updated state st ′e or an error symbol ⊥if for instance the output length len is not valid for the message m. Algorithm(m′,st ′d) = DecStE(k,H,C,std) takes as input a key k, header data H, a ciphertext C,and the current state std ∈ {0,1}∗, and returns an updated state st ′d and a value m′

which is either the message encrypted in C, or a distinguished error symbol ⊥indicating that C is not a valid ciphertext. Both encryption state ste and decryptionstate std are initialized to the empty string /0. Algorithm EncStE may be probabilistic,while DecStE is always deterministic.

D Definition 3.4

We say that a stateful symmetric encryption schemeStE=(InitStE,EncStE,DecStE)is (t,εsLHAE)-secure, if Pr[b = b′] ≤ εsLHAE for all adversaries A running intime at most t in the following experiment.

• Choose b $←{0,1} and k $←{0,1}κ , and set ste := /0 and std := /0,

• run b′ $←A Encrypt,Decrypt.

Here A Encrypt,Decrypt denotes that A has access to two oracles Encrypt andDecrypt. The encryption oracle Encrypt(m0,m1, len,H) takes as input twomes-sages m0 and m1, length-parameter len and header data H. It maintains acounter u which is initialized to 0. Oracle Decrypt(C,H) takes as input aciphertext C and header H, and keeps a counter v and a variable phase, bothare initialized to 0. Both oracles process a query as defined in Figure 3.1.

3.11 Complexity Assumptions Seite 27

Encrypt(m0,m1, len,H): Decrypt(C,H):u := u+1 v := v+1(C(0),st(0)e )

$← EncStE(k, len,H,m0,ste) If b = 0, then return ⊥(C(1),st(1)e )

$← EncStE(k, len,H,m1,ste) (m,std) = DecStE(k,H,C,std)If C(0) =⊥ or C(1) =⊥ then return ⊥ If v > u or C 6=Cv, then phase := 1(Cu,ste) := (C(b),st(b)e ) If phase= 1 then return mReturn Cu Return ⊥

Abb. 3.1: Encrypt andDecrypt oracles in thestateful LHAE securityexperiment.

3.10.4 Public Key Encryption

IND-CPA secure.

3.10.5 Key Encapsulation Mechanism (KEM)

3.11 Complexity Assumptions

In the following, we give concrete security parameters t and ε for each problem.The assumption is that for each such problem there exist mathematical structuressuch that for any polynomially bounded t, ε remains negligibly small.

Thus if we lateron state “we assume that the XYZ assumption holds in G” we meanthat ....

3.11.1 The RSA Assumptions

3.11.2 The Discrete Logarithm Assumption

Let G be a group of prime order q. Let g be a generator of G. Given, (g,gx) for x ∈ Zqthe discrete logarithm (DL) assumption says that it is hard to calculate x given gx.

DDefinition 3.5

We say that the DL problem is (t,εDL)-hard in G, if for all adversaries A thatrun in time t it holds that

Pr [A (g,gx) = x]≤ εDL,

where x $← Zq.

3.11.3 The Computational Diffie-Hellman Assumption

Let G be a group of prime order q. Let g be a generator of G. Given, (g,gx,gy) forx,y ∈ Zq the computational Diffie-Hellman (CDH) assumption says that it is hardto calculate gxy given (gx,gy).


D Definition 3.6

We say that the CDH problem is (t,εCDH)-hard in G, if for all adversaries Athat run in time t it holds that

Pr [A (g,gx,gy) = gxy]≤ εCDH,

where x,y $← Zq.

3.11.4 The Decisional Diffie-Hellman Assumption

Let G be a group of prime order q. Let g be a generator of G. Given, (g,ga,gb,gc)for a,b,c ∈ Zq the decisional Diffie-Hellman (DDH) assumption says that it is hardto decide whether c = ab mod q.

D Definition 3.7

We say that the DDH problem is (t,εDDH)-hard in G, if for all adversaries Athat run in time t it holds that∣∣∣Pr

[A (g,ga,gb,gab) = 1

]−Pr

[A (g,ga,gb,gc) = 1

]∣∣∣≤ εDDH,

where a,b,c $← Zq.

The security game for DDH is defined as follows: The DDH challenger CDDH

chooses a,b,c $← Zq, and b $←{0,1}. He then computes α := ga and β := gb. If b = 0he computes γ := gab, if b = 1 he computes γ := gc. He then issues (g,α,β ,γ) tothe DDH adversary ADDH . The adversary wins if εDDH defined as above is non-negligible.

ÜÜbung 3.1: Reduction proofs: DL vs. CDH vs. DDH

Let G be a cyclic group with generator g and order |G|= q.

1. Prove formally that the CDH problem is at most as difficult to solveas the DL problem.Hint: This is the same as: “Show that you can solve the CDH problem whenyou know how to solve the DL problem”

2. Prove formally that the DDH problem is at most as difficult to solveas the CDH problem.

3. What needs to be shown in order to proof that the CDH problem isequivalent to the DL problem?

3.11.5 PRF-ODH Assumtion

Let G be a group with generator g. Let PRF be a deterministic function z =PRF(X ,m), taking as input a key X ∈ G and some bit string m, and returning astring z ∈ {0,1}µ . Consider the following security experiment played between achallenger C and an adversary A .

1. The adversary A outputs a value m.

3.11 Complexity Assumptions Seite 29

2. The Challenger samples u,v $← [q], z1$←{0,1}µ uniformly random and sets

z0 := PRF(guv,m). Then it tosses a coin b ∈ {0,1} and returns zb, gu and gv tothe adversary.

3. The adversary may query a pair (X ,m′)with X 6= gu to the challenger. Thechallenger replies with PRF(Xv,m′).

4. Finally the adversary outputs a guess b′ ∈ {0,1}.

DDefinition 3.8

We say that the PRF-ODH problem is (t,εprfodh)-hard in with respect to G andPRF, if for all adversaries A that run in time t it holds that∣∣Pr

[b = b′

]−1/2

∣∣≤ εprfodh.

The PRF-Oracle-Diffie-Hellman (PRF-ODH) assumption is a variant of the ODHassumption introduced by Abdalla, Bellare and Rogaway in [1], adopted from hashfunctions to PRFs. In contrast to allowing a polynomial number of queries as inthe original assumption [1], we allow only a single oracle query.

Studienbrief 4 Simple Protocols Seite 31

Studienbrief 4 Simple Protocols


The aim of this chapter is to introduce some simple or well-known protocols tothe reader. The simple protocols are mainly used in the academic literature, andserve as an introduction to the special problems in the filed of cryptographicprotocols. The well-known protocols include SSL/TLS, SSH and IPSec and serveas a motivation why the theory presented in this book can be useful in practice.

After finishing this chapter, students

• know what key agreement is, and be able to name some example protocols;

• know what an authentication protocol is;

• understand how both types of protocols are combined to form practicallyimportant protocols like TLS.


4.3 Related Work

JS: Please introduce shortly the papers on which this chapter s based.

4.4 Key Agreement Protocols

4.4.1 Shamir’s No-Key Protocol

Mechanical Scenario. Alice wants to send a box to Bob but does not trust theenvoy. Alice and Bob each have a padlock. It has to be ensured that the envoy is notable to open the box, therefore Alice locks it before sending to Bob. Bob receivesthe locked box, adds his own padlock, and sends it back to Alice. Now Alice canremove her own padlock and send the still locked box back to Bob. He can nowremove his own padlock and open the box.

Mechanical Scenario

Alice Bob

−−−−−−−−−−−−→

←−−−−−−−−−−−−

−−−−−−−−−−−−→

Abb. 4.1: MechanicalScenario

Seite 32 Studienbrief 4 Simple Protocols

Digital Scenario. Alice and Bob want to use a public channel to exchange arandom bitstring s. The adversary is passive and may only listen to the channelwithout modifying the transmitted data.Let G be a cyclic multiplicative group with prime order q and generator g. In thefollowing protocol A wants to send a message s to be B, they do not share a key.

Abb. 4.2: Shamir’sNo-Key Protocol

A Bs $← G

a $← {0, . . . ,q− 1}x := sa

−x

−−−−−−−−−−−→b $← {0, . . . ,q− 1}

y := xb

←−y

−−−−−−−−−−−a′ := a−1 mod q− 1

z := ya′

−z

−−−−−−−−−−−→b′ := b−1 mod q− 1

s := zb′

ÜÜbung 4.1: Analysis of Shamir’s No-Key Protocol

1. Show that Shamir’s protocol is correct. Additionally, show thatB actual-ly receives the message s if both parties act according to the protocol.

2. Assume that A always uses the same secret a. A sends at first amessages1 toB1 and later amessage s2 toB2. Describe howB2 is able to calculates1.

4.4.2 Diffie-Hellman

The Diffie-Hellman key establishment (DHKE) protocol was the first exampleof a public key algorithm, published in the seminal paper of Whit Diffie andMartin Hellman back in 1976 []. Today it is a building block in nearly all importantkey agreement protocols, from IPSec IKE (v1 and v2), SSH, TLS-DHE to firewireIEEE???.

In the Diffie-Hellman key establishment protocol, all computations are done ina cyclic group G of order q, where q is a prime whose length is roughly 160 Bit.Typically G is embedded in a larger structure:

• In the multiplicative group (Z∗p, ·) of the finite field GF(p) of order p. Groupoperation is multiplication modulo p. If q|p−1 then a subgroup G of orderq exists in Z∗p. If we choose an element 1 6= g ∈ G, then all powers of g willalso lie in G.

• In GF(p)×GF(p), the finite 2-dimensional plane over GF(p). Here G is anelliptic curve curve (3.5.3) in this plane, i.e. the set of all points (x,y) thatfulfill an equation of the form y2 = x3 + ax+ b, with a,b ∈ GF(p). Groupoperation is point addition.

Protocol execution. Alice randomly chooses x from Zq and sends α = gx to Bob.Bob himself randomly chooses y from the same domain and sends β = gy to Alice.

4.4 Key Agreement Protocols Seite 33

Alice then computes the key k = kA by raising the received β to the power of hersecret value x: kA = β x. In a similar way, Bob computes k = kB = αy.

Diffie-Hellman Key Establishment Protocol

A B

x $← Zqα ← gx

−α

−−−−−−−−−−−→y $← Zqβ ← gy

←−β

−−−−−−−−−−−

Abb. 4.3: Diffie-Hellmankey establishmentprotocol

To show the correctness of the protocol we must show that Alice and Bob computethe same key k:

kA = (gy)x = gyx = gxy = (gx)y = kB = k.

ÜÜbung 4.2: Computing a DH key in Z23

Let p = 23, and let G =< 3 > be the subgroup of (Z∗23, ·) generated by theelement 3.

1. What is the order of G? Please write down all elements of G.

2. Let x = 3 and y = 4. Please compute the DH key k.

Remark: From a strictly mathematical point of view, the shared key k is a randomgroup element rather than a random bitstring. If G is a subgroup of Z∗p, this hardlymatters: using the least significant bits of the binary representation of the groupelement will result in a fairly random string. However, if G is an elliptic curve,the resulting group element will consist of two points in the finite plane, anda more sophisticated approach to transform this into a random string may beappropriate.

4.4.3 Security of the Diffe-Hellman protocol

The security of the DHKE is based on the DDH-assumption (cf. 3.11.4).

ÜÜbung 4.3: DDH does not hold in (Zq,+)

Please show that the DDH assumption is not valid for the group (Zq,+),the group of integers between 0 and q− 1, where the group operation isaddition modulo q. (Hint: You may also show that the CDH assumptiondoes not hold here.)

Since the DDH assumption is tailored to DH, there is not much to prove here. Wewill however use this opportunity to introduce the game-based setting in whichreduction-based security proofs are formulated in modern cryptography.


Each such (probabilistic) game is played between a challenger (who simulated theprotocol honestly) an adversary (who tries to break the protocol). If the adversarywins the game with some non-negligible probability, then we know that there is arealistic possibility that the same adversary may also break the real protocol.

In the following game, only a single execution of the DHKE is considered – if DHKEis executed multiple times, then the winning probability of the adversary mayincrease (hopefully only linearily). Additionally, our adversary is restricted to onlyobeserving the network, i.e. he can only read messages, but not alter them. This isdue to the fact that we already know that DHKE is vulnerable toman-in-the-middleattacks by active adversaries.

DHKE Security Game. Let π be an instance of a DH key exchange protocol fora key space K (e.g. elements of G) and let A be an adversary for π .

In the first step, the challenger generates all values needed for a DHKE, computesthe shared key k0 = gxy and the protocol transcript (α,β ). In the next step, a valuek1 is randomly choosen from the key space K and a fair coin b ∈ {0,1} is tossed.Then the sequence (α,β ,kb) is given to the adversary.

After performing arbitrary computations (only restricted by a polynomial timebound), the adversary A returns a bit b′ to the challenger. The challenger outputs 1if b′ equals b and 0 otherwise.

The adversary A wins the game if the challenger outputs 1.

Abb. 4.4: Securi-ty Game for Diffie-

Hellman Key ExchangeCDHKE ADHKE

x $← Zq

α ← gx

x $← Zq

α ← gx

k0← gxy

k1$← K

b ∈R {0,1} (α,β ,kb)

b′

Perform arbitrarycomputations on

(α,β ,kb)

Return some b′

Output:{

1 if b′ = b0 else

Please remark that the adversary can always win this game with probability 12

by simply guessing b′. Thus we cannot use this winning probability directly as adefinition for the (in)security of DHKE. Instead, we will require that a successfuladversary must be able to do significantly better than simply guessing.


LetPrADHKE(G) be the probability that adversaryAwins the security game described

in Abbildung 4.4 if the group G is used. Then we define the advantage of A asfollows:

AdvADHKE(G) := |PrA

DHKE(G)− 12|.

In other words, we normalize the winning probability by substracting the “trivial”winning probability 1

2 .

DDefinition 4.1

DHKE for group G is secure if AdvADHKE(G) is negligible.

To keep it simple, this definition is mathematically inprecise: Being negligibleis an asymptotic property, and the definition only mentions a single group G offixed size. However, we can introduce an asymptotic behaviour if we increase theparameters of the group, but stay within the same class of groups:

• For prime order subgroups of (Z∗p, ·), wemay increase both prime parametersp and q.

• For elliptic curves, we may increase the order p of GF(p), and we may try tofind elliptic curves with a larger order q.

SSatz 4.1

The DH protocol π is secure against passive adversaries under the DDHassumption (cf. 3.11.4).

Proof. We prove this theorem by giving a reduction from the security game to theDDH problem. Assume that our DHKE adversary ADHKE had a non-negligibleprobability εDHKE of winning the security game from Figure 4.4. Then an DDH-adversaryADDH could use this fact to break theDDHassumption forG as follows:

• The DDH adversary receives the DDH challenge (g,α,β ,γ) from the DDHchallenger.

• Then ADDH plays the role of CDHKE : He forwards the three last components(α,β ,γ) from the challenge to the DHKE-adversary ADHKE .

• When ADHKE returns a bit b′, ADDH simply forwards this bit to CDDH .

Now let us assume w.l.o.g. that AdvADHKE(G)> 1

2 .

PrADHKE(G) (4.1)

= Pr[b′ = 1|b = 1]+Pr[b′ = 0|b = 0] (4.2)= PrA

DDH(G) (4.3)= ..... (4.4)

�


ÜÜbung 4.4: Man-in-the-Middle

A Man-in-the-Mittle (MitM) attacker may intercept messages and may for-ward them modified, delete them or replace them with messages of his ownchoice. The MitM attacker is the prototype of an active attacker. His goalsdepend on the type of protocol he is attacking.

In a key exchange protocol, the target of a MitM attacker is to either com-promise the key or to be able to later read the encrypted messages withouteither of the parties noticing such.

1. Describe a MitM attack on the DH key exchange protocol. Use apicture to illustrate it. (Hint: The MitM attacker replaces all messagesby messages of his wn choice.)

2. Describe how aMitM attacker can, after the key exchange phase, readthe messages encrypted exchanged between Alice and Bob. Are Aliceand Bob able to notice this?

3. Is a MitM attacker able to modify the messages of the key exchange,i.e. gx und gy, in such a way that he can calculate the secret keys xfrom Alice and y from Bob? If Yes: How is he able to do this? If No:Why is he not able to do this? (Which assumption would he need tobreak?)

4.4.4 ElGamal Encryption

The ElGamal encryption scheme was introduced in 1985 by Taher Elgamal [15].It is based on the Diffie-Hellman key exchange protocol. The first DH share ispublished as the public key of the party, and is used in many encryptions. Thesecond DH share ich chosen randomly by the sender, and sent togenther with theciphertext to the recipient.

ElGamal encryption can be shown to be IND-CPA secure provided that in theunderlying cyclic group G (of order q) the DL (Section 3.11.2) and DDH (Section3.11.4) problems are intractable.

To be able to use ElGamal encryption, each participant has to generate its ownpublic key and make this key accessible to the other participants. In order to stressthe similarity to DHKE, in Abbildung 4.5 we use a public directory for this purpose.Here B has to register his public key together with his identity B.

If A wants to send an encrypted message to B, she has to retrieve B’s public keyfirst. Thus she sends a request containing the identity B to the public directory,and receives the public key β in the response.

Remark: In practice, Public Key Infrastructures (PKI) are used instead of publicdirectories. Here the pair (B,β ) would be signed by a Certification authority (CA),and published as a X.509 certificate. There are various means how A could retrievesuch a certificate, including receivig it directly form B.

To encrypt a message m, A chooses a random number r from {0, ...,q− 1}, andcomputes two values: The “second DH share” α := gr, and the “shared key” k := β r.She then uses k to encrypt the message m, using an arbitrary symmetric encryptionscheme E∗(∗).


ElGamal Encryption with public parameters G,g

A PublicDirectory

B(x,β )with

β = gx

←−B,β−−−−−−−

−B

−−−−−−−→

←−β

−−−−−−−r $← Zqα := gr

k := β r

c := Ek(m)

−(α,c)−−−−−−−→

k := αx

m := Dk(c)

Abb. 4.5: ElGamal En-cryption protocol

To decrypt the message, B has to “complete the DHKE” by computing the “shared”key as k := αx, and then using the specified symmetric decryption scheme toretrieve the message.

Remark: If G is a subgroup of (Z∗p, ·), then the message m may be encoded as aninteger from Z∗p, and the encryption operation simply becomes the multiplicationin Z∗p. This option is often used when ElGamal encryption is used as a KEM, i.e. ifm is a symmetric key.

ÜÜbung 4.5

Show that the same symmetric keys are used for encryption and decrypti-on.

4.4.5 RSA-KEM Key Transport Algorithm

The RSA-KEM (key encapsulation mechanism) Key Transport Algorithm is aone-pass mechanism to transport keying material with the help of the recipient’sRSA public key. Instead of directly encrypting the key k, a random integer r thatlies in the RSA modulu, is encrypted with the recipient’s RSA public key to c andused to derive a symmetric key-encrypting key kk. This kk is then used to wrap thesymmetric key k through encrypting to wk. The encrypted random integer c andthe wrapped key wk is now sent to the recipient who is capable of decrypting therandom integer, derive kk, and finally unwrap k.

The advantage of this approach is that the first step has no exploitable structuresince a random integer in the RSA modulu is encrypted. Furthermore the lengthof the key k is not limited by the RSA modulu but rather by the symmetric key-wrapping scheme. In the random orakle model where the key derivation functionis modeled as a random orakle, it can be shown that the security of this mechanismis tightly related to solving RSA or breaking the underlying key wrapping scheme.Assuming that these underlying components are secure the protocol itself can beshown to be secure.


Abb. 4.6: The RSA-KEMKey Transport Algorithm

according to RFC 5990RSA-KEM Key Transport

A(e,N)

B(e,d, p,q,N)

r $← Z∗Nc ≡ re mod N

kk = f (r)wk = enckk(k)

−(c,wk)

−−−−−−−−−−−→r ≡ cd mod N

kk = f (r)k = deckk(wk)

4.5 Authentication Protocols

4.5.1 Challenge-and-Response

The main target of a Challenge-and-Response protocol is that a claimant A provesthe knowledge of a secret k to the verifyer B over an insecure channel withoutrevealing this secret to an evesdropper.

A simple example for a Challenge-and-Response protocol is password authentica-tion. Alice wants to prove towards Bob that she is in the posession of the secretpassword k but does not want to send it in plaintext over the insecure channel.Bob can now generate a nonce c and send it as challenge to Alice. She takes thechallenge c concatinates the secret password k, calculates a one way hash functionH() over these, and sends this as response res. Bob himself also calculates the hashfunction of his challenge c and the password he saved for Alice and compares theresult with the received response res from Alice. After successful validation, Aliceis authenticated via the password k towards Bob without revealing the password kto an eavsdropper.

Abb. 4.7: Challenge-Response Authen-

tication protocolChallenge-Response

A(k)

B(k)

c $← 1κ

←−c

−−−−−−−−−−−res = H(k ‖ c)

−res

−−−−−−−−−−−→test if res = H(k ‖ c)

A possible attack to this protocol is shown in Figure 4.5.1. A better solution tocalculate res is to use a pseudo random function, for example

PRF : HMACH(k,m) = H(k⊕ `2 ‖ H(k⊕ `1 ‖ m)))

4.6 Authenticated Key Exchange Seite 39

Attack on C&R

A(k)

B

c′ $← 1κ

←−c ‖ c′

−−−−−−−−−−−res = H(res ‖ c′)←depending onthe hash function

Abb. 4.8: Possible attackto Challenge-Responseprotocol

In this way only Alice authenticates towards Bob, the protocol can be extendedto archieve mutual authentication. Since the challenge c is freshly generated forevery protocol run, replay attacks are prevented.

4.5.2 Signed Challenge-and-Response

4.5.3 Signed Timestamp

4.5.4 (Public-Key) Encrypted Nonce

Encrypted Nonce

A(skA, pkA)

πA

B(pkA)

πB

r ∈R {0,1}`c = EncpkA(r)

←−c

−−−−−−−−−−−r = DecskA(c)

−r

−−−−−−−−−−−→

Abb. 4.9: EncryptedNonce

4.6 Authenticated Key Exchange

4.6.1 Signed Diffie-Hellman

Signed DH

A B

−ga,SIGA(ga)−−−−−−−−−−−→

←−gb,SIGB(gb)−−−−−−−−−−−

Abb. 4.10: Signatur bie-tet Schutz gegen klassi-schen MitM Angriff


4.6.2 TLS

4.6.3 SSH

4.6.4 IPSec IKE

Client Server

m1: Hdr,SA,gx,rC, pidC

m2: Hdr,SA,gy,rS, pidS,CertS,σS

m3: Hdr,CertC,σC

m4: Hdr,Enck(H(h1),SA,r′C,gx′ , idC, idS)

m5: Hdr,Enck(H(h2),SA,r′S,gy′ , idC, idS)

m6: Hdr,Enck(H(h3))

Plaintext

chan

nel

enc-then

-auth

chan

nel

Phase1

Agressive

Mod

ePh

ase2

Quick

Mod

e

4.6 Authenticated Key Exchange Seite 41

TLS-DHE

C(pkC,skC)

πC

S(pkS,skS)

πSrC ∈R {o,1}λ1

−m1 : rC,cs-list−−−−−−−−−−−→

rS ∈R {0,1}λ1

tS ∈ Zq,TS = gtS mod pσS = SIG.sign(skS;rC‖RS‖p‖g‖TS)

←−m2 : rS,

T LS-DHE︷︸︸︷cs-choice

−−−−−−−−−−−−−←−

m3 : certS−−−−−−−−−−−

←−m4 : p,g,TS,σS−−−−−−−−−−−

←−m5 : get cert−−−−−−−−−−−

←−m6 : done−−−−−−−−−−−

SIG.Verify(σS)tc ∈ Zq,TC = gtC mod p

σC = SIG.sign(skC;m1‖· · ·‖m8)pms = T tC

S mod pms = PRF(pms; label1‖rC‖rS)kC→S

enc ‖kS→Cenc ‖kC→S

mac ‖kS→cmac ‖· · ·←

PRF(ms; label2‖rC‖rS)f inC = PRF(ms;‖label3‖m1‖· · ·‖m10)

−m7 : certC−−−−−−−−−−−→

−m8 : TC

−−−−−−−−−−−→

−m9 : σC

−−−−−−−−−−−→

−m10 : f lagenc−−−−−−−−−−−→

−m11 : E(k; f inC−−−−−−−−−−−→

SIG.Verify(σC)pms = T tS

C mod pms = PRF(pms; label1‖rC‖rS)kC→S

enc ‖kS→Cenc ‖kC→S

mac ‖kS→cmac ‖· · ·←

PRF(ms; label2‖rC‖rS)f inS = PRF(ms;‖label4‖m1‖· · ·‖m12)

←−m12 : f lagenc−−−−−−−−−−−

←−m13 : E(k; f inS)−−−−−−−−−−−−

Verify( f inC)Verify( f inS)

Record layer

−−−−−−−−−−−−→←−−−−−−−−−−−−

Abb. 4.11: TLS Protokollmit DHE


Abb. 4.12: Secu-re Shell Protokoll SSH

CskC,pkC,list of trusted pk

πC

SskS,pkS,list of trusted pk

πS

rC ∈R {0,1}`x ∈R {0,1}`

−rc, pklistC = IC−−−−−−−−−−−→

rS ∈R {0,1}`y ∈R {0,1}`

←−rS, pklistS = IS−−−−−−−−−−−

−gx

−−−−−−−−−−−→k = (gx)y

←−gy, pkS,sigS−−−−−−−−−−−

H,k,Veri f y(sigS)k∗

H ←(VC‖VS‖IC‖IS‖pkS‖gx‖gy‖k)

σS ← SIG.sign(skS,H)k∗ ← h(k‖H‖label‖H)

σC = SIG.sign(H‖A‘C)

−AC

−−−−−−−−−−−→

←−OK

−−−−−−−−−−−

−AC‖σC

−−−−−−−−−−−→

Studienbrief 5 Zero-Knowledge (ZK) Seite 43

Studienbrief 5 Zero-Knowledge (ZK)



5.3 Related Work

The concept of Zero-Knowledge goes back to Goldwasser, Micali and Rackoff [18].This and following early works on Zero-Knowledge are rather technical. Thereforewe will build this section on an article by Damgård and Nielsen [11].


5.4 Zero-Knowledge

5.4.1 Introduction to Zero-Knowledge

We introduce the concept of Zero-Knowledge informallywith an example. Considerthe problem of a host computer that tries to verify the identity of a user whichtries to log on. This is often done via the classical combination of username andpassword, i.e., the user types in its username and password. This is sent to the hostwho checks it against a stored list. There are many well known security issues withthis way of authentication. The most obvious is that an attacker that eavesdropsthe combination of username and password is able to impersonate that user fromthat point on. A possible approach to circumvent this problem is to protect thepassword, e.g., via encryption. We do not claim that this solution works. However,we do claim that this solution leaves us barking up the wrong tree. To see this,we recall what the purpose the authentication procedure is: The purpose of theprocedure is to identify the user, not to send its password to the host. If a user typesin its username, e.g. A, this is equivalent to claiming “I know the secret/passwordcorresponding to username A”. Actually the host needs to know only one bit ofinformation here: Is the above statement true or not? Sending the password to thehost is only one way of proving correctness of the statement. As discussed above, itis probably not the most clever way to prove it.

Informally, a Zero-Knowledge protocol is an interactive protocol where the host cancompute this one bit of information and nothing else after conducting the protocolwith a user. This means that an eavesdropper that listens to the communicationbetween user and host will also learn at most that the statement is true (and nothingelse). We conclude that in this case it learns nothing about the user’s secret. Clearly,the protocol has to satisfy some properties. Namely, an honest user should alwaysbe able to “convince” the host. I.e., if a user knows the secret to username A thenafter conducting the protocol with the user the host should accept, i.e., compute 1whereas if a user does not know the secret to username A, then after conductingthe protocol the host should not accept, i.e., it should compute 0.

5.4.2 Formalizing Zero-Knowledge

Zur Erinnerung, intuitiv ist ein solches Protokoll ein Zero-Knowledge Protokoll,wenn folgende Bedingungen erfüllt sind:

1. Completeness: Ein ehrlicher Prover, der das "Geheimnis"kennt, kann einenehrlichen Verifier überzeugen.

2. Soundness: Ein unehrlicher Prover P, der das "Geheimnis"nicht kennt, kanneinen Verifier nicht (bzw. nur mit vernachlässigbar kleiner Wahrscheinlich-keit) davon überzeugen dass er es kennt.

Seite 44 Studienbrief 5 Zero-Knowledge (ZK)

3. Zero-Knowledge: Der Verifier lernt nur, dass P tatsächlich x kennt, erhältjedoch keine weitere Information über das Geheimnis x, die er sich nichtselbst effizient berechnen könnte.

5.5 Fiat-Shamir-heuristic

5.6 Fiat-Shamir protocol

Let N = pq be a RSA modulo and x = y2 mod N. In the following protocol a proverP can proof that x is a quadratic remainder modulo N.

Abb. 5.1: Fiat-Shamir Protocol

P Vr $← ZNt = r2

−t

−−−−−−−−−−−→b $← {0,1}

←−b

−−−−−−−−−−−s = ryb

−s

−−−−−−−−−−−→test if s2 ?

= txb

ÜÜbung 5.1: Analysis of Fiat-Shamir Protocol

1. Show that the protocoll is complete.

2. Show that the protocol is sound.

3. Show that the protocol is a Zero-Knowledge protocol.

(The Jocobi-Symbol is not needed for any argumentation)

5.7 Quadratic Remainder

Let N = pq be an RSA modulu. In the following protocol a prover P can proof thathe knows the factorization of N.

Abb. 5.2: QuadraticRemainder Protocol

P Vr $← ZNt = r2

←−t

−−−−−−−−−−−s =√

t mod N

−s

−−−−−−−−−−−→test if s2 ?

= t

ÜÜbung 5.2

1. Is this protocol complete?

2. Is this protocol sound?

3. Is this protocol a Zero-Knowledge protocol?

Studienbrief 6 Authenticated Key Exchange (AKE) Seite 45

Studienbrief 6 Authenticated Key Exchange (AKE)



6.3 Related Work


6.4 Bellare-Rogaway Model

While the established security models for, say, encryption (e.g. IND-CPA or IND-CCA security), or digital signatures (e.g., EUF-CMA), are clean and simple, amore complex model is required to model the capabilities of active adversaries todefine secure authenticated key-exchange (AKE). An important line of research [7,8, 22, 10] dates back to [5], where an adversary is provided with an ‘executionenvironment’, which emulates the real-world capabilities of an active adversary,which has full control over the communication network. In the sequel we describea variant of this model, which captures adaptive corruptions, perfect forward-secrecy, and security against key-compromise impersonation attacks in a public-keysetting.

Execution Environment Consider a set of parties {P1, . . . , P }, ` ∈ N, where eachparty Pi ∈ {P1, . . . , P } is a (potential) protocol participant and has a long-term keypair (pki,ski). To model several sequential and parallel executions of the protocol,each party Pi is modeled by a collection of oracles π1

i , . . . ,πdi for d ∈ N. Each oracle

πsi represents a process that executes one single instance of the protocol. All oracles

π1i , . . . ,π

di representing party Pi have access to the same long-term key pair (pki,ski)

of Pi and to all public keys pk1, . . . , pk`. Moreover, each oracle πsi maintains as

internal state the following variables:

• Λ ∈ {accept,reject}.

• k ∈K , where K is the keyspace of the protocol.

• Π ∈ {1, . . . , `} containing the intended communication partner, i.e., an indexj that points to a public key pk j used to perform authentication.1

• Variable ρ ∈ {Client,Server}.

• Some additional temporary state variable st (whichmay, for instance, be usedto store ephemeral Diffie-Hellman exponents or a transcript of messages).

The internal state of each oracle is initialized to (Λ,k,Π,ρ,st) = ( /0, /0, /0, /0, /0), whereV = /0denotes that variableV is undefined. Furthermore, wewill always assume (forsimplicity) that k = /0 if an oracle has not reached accept-state (yet), and containsthe computed key if an oracle is in accept-state, so that we have

k 6= /0 ⇐⇒ Λ = accept. (6.1)

1 We assume that each party Pi is uniquely identified by its public key pki. In practice, several keysmay be assigned to one identity. Furthermore, there may be other ways to determine identities, forinstance by using certificates. However, this is out of scope of this study package.

Seite 46 Studienbrief 6 Authenticated Key Exchange (AKE)

K Kontrollaufgabe 6.1

What is the connection between the keys ski, pki, and k?

Adversarial Model An adversary A may interact with these oracles by issuingthe following queries.

• Send(πsi ,m): The adversary can use this query to sendmessage m to oracle πs

i .The oracle will respond according to the protocol specification, dependingon its internal state. If the attacker asks the first Send-query to oracle πs

i , thenthe oracle checks whether m consists of a special ‘initialization’ symbol >. Iftrue, then it sets its internal variable ρ := Client and responds with the firstprotocol message. Otherwise it sets ρ := Server and responds as specified inthe protocol. 2 The variables Λ,k,Π,st are also set after certain Send-queries.3

• Reveal(πsi ): Oracle πs

i responds to aReveal-querywith the contents of variablek. Note that we have k 6= /0 if and only if Λ = accept, see (6.1).

• Corrupt(Pi): Oracle π1i responds with the long-term secret key ski of party Pi.4

If Corrupt(Pi) is the τ-th query issued by A , then we say that Pi is τ-corrupted.For parties that are not corrupted we define τ := ∞.

• Test(πsi ): This query may be asked only once throughout the game. If πs

i hasstate Λ 6= accept, then it returns some failure symbol ⊥. Otherwise it flips afair coin b, samples an independent key k0

$←K , sets k1 = k to the ‘real’ keycomputed by πs

i , and returns kb.

The Send-query enables the adversary to initiate and run an arbitrary numberof protocol instances, sequential or in parallel, and provides full control over thecommunication between all parties. The Reveal- query may be used to learn thesession keys used in previous/concurrent protocol executions. The Corrupt- queryallows the attacker to learn ski of party Pi , it may for instance be used by A toimpersonate Pi. The Test-query will be used to define security.


Why is it important that the Test-query may only be issued once?

Security Definition [5] have introduced the notion of matching conversations inorder to define correctness and security of an AKE protocol precisely. We denotewith Ti,s the sequence that consists of all messages sent and received by πs

i inchronological order (not including the initialization-symbol >). We also say thatTi,s is the transcript of πs

i . For two transcripts Ti,s and Tj,t , we say that Ti,s is a prefix

2 Note that we assume that learning identities of communication partners (which is necessary todetermine the public-key used to perform authentication) is part of the protocol.

3 For details on when and how they are set in TLS, see the description in Section 8.4 and Figure 8.1.4 Note, that the adversary does not ‘take control’ of oracles corresponding to a corrupted party. But helearns the long-term secret key, and can henceforth simulate these oracles.

6.4 Bellare-Rogaway Model Seite 47

of Tj,t , if Ti,s contains at least one message, and the messages in Ti,s are identical toand in the same order as the first |Ti,s|messages of Tj,t .

BBeispiel 6.1

Matching Conversation

Πsi Πt

j

−m1−−−−−−→ −

m1−−−−−−→

←−a1

−−−−−− ←−a1

−−−−−−−

m2−−−−−−→ −

m2−−−−−−→

An example for a matching conversation is shown in Beispiel 6.1. The sequencem1,a1,m2 denotes Ti,s which is a prefix of the sequenz denoted by Tj,t , whereby thestar denotes that Πt

j may send further messages.

DDefinition 6.1: Matching conversations

We say that πsi has a matching conversation to π t

j, if

• Tj,t is a prefix of Ti,s and πsi has sent the last message(s), or

• Ti,s is a prefix of Tj,t and π tj has sent the last message(s).

Remark 3. We remark that matching conversations in the above sense can also beseen as post-specified session identifiers. The ‘asymmetry’ of the definition (i.e., thefact that we have to distinguish which party has sent the last message) is necessary,due to the fact that protocol messages are sent sequentially. For instance in theTLS handshake protocol (see Figure 8.1) the last message of the client is the ‘clientfinished’ message f inC, and then it waits for the ’server finished’ message f inSbefore acceptance. In contrast, the server sends f inS after receiving f inC. Thereforethe server has to ‘accept’ without knowingwhether its last messagewas received bythe client correctly. We have to take this into account in the definition of matchingconversations, since it will later be used to define security of the protocol in presenceof an active adversary that simply drops the last protocol message.

KKontrollaufgabe 6.3

What effekt has the last messages of the Server to amatching conversation?

Security of AKE protocols is now defined by requiring that (i) the protocol isa secure authentication protocol, and (ii) the protocol is a secure key-exchangeprotocol.

We formalize this in the following games and definitions. To have a controlledenvironment and to guarantee that all queries by the adversary will indeed beanswered, the network, the different parties, and all process oracles will be simu-lated by a challenger C . The challenger simulates the original games faithfully, i.e.all the process oracles fully adhere to the protocol specification, and all queriesby the adversary are answered correctly. that means that the winning probability


of the adversary in this simulation is exactly the same as if the adversary wouldinteract with a real network like the internet, and with a real implementation ofthe protocol.

During each proof, we will modify the simulation slightly step by step, and wewill carefully argue how these modifications may alter the winning probability ofthe adversary. The goal of this process is to end up with a modified game wherethe winning probability directly depends on combinatorics only, or on one well-established cryptographic assumption. Going backwards from this final winningprobability, we will compute an upper bound on the winning probability of theadversary in the original game, taking into account all modifications made inbetween the original and the final game.

Authentication Game GA.

In this game, the adversary A is only allowed to ask Send queries, i.e. he acts as anactive adversary. Since we do not consider the secrecy of the session key in thisgame, Reveal and Test queries do not make sense. The adversary wins the gameif he can force an arbitrary oracle to accept, but there is no second oracle with amatching conversation.

D Definition 6.2

We say that an adversary (t,ε)-breaks an authentication (A-) protocol ΠA ingame GA, if A runs in time t, and the following condition holds:

1. When A terminates, then with probability at least ε there exists anoracle πs

i such that• πs

i ‘accepts’ when A issues its τ0-th query with intended part-ner Π = j, and

• there is no unique oracle π tj such that πs

i has a matching con-versation to π t

j.If an oracle πs

i accepts in the above sense, then we say that πsi accepts

maliciously.

We say that an A protocol ΠA is (t,ε)-secure, if there exists no adversary that(t,ε)-breaks it.

AKE Game GstatAKE with Static Corruptions.

In this game, the adversary A tries to break either the authentication propoertyof the protocol, or the secrecy of the session key. He is therefore allowed to askpolynomially many Send and Reveal, and one Test query. In addition we allow static

6.4 Bellare-Rogaway Model Seite 49

corruptions, i.e. the adversary must send all Corrupt queries at the beginning ofthe game (this helps to make the proof simpler).

DDefinition 6.3

We say that an adversary (t,ε)-breaks an AKE protocol ΠstatAKE in game Gstat

AKE ,if A runs in time t, and at least one of the following two conditions holds:

1. When A terminates, then with probability at least ε there exists anuncorrupted oracle πs

i such that• πs

i ‘accepts’ with uncorrupted intended partner Π = j, and



j.If an oracle πs


maliciously.

2. When A issues a Test-query to any uncorrupted oracle πsi and

• πsi ‘accepts’ with uncorrupted intended partner Π = j,

• A does not issue a Reveal-query to πsi , nor to π t

j such that πsi

has a matching conversation to π tj (if such an oracle exists), and

then the probability that A outputs b′ which equals the bit b sampledby the Test-query satisfies∣∣Pr[b = b′]−1/2

∣∣≥ ε.

If an adversaryA outputs b′ such that b′ = b and the above conditionsare met, then we say that A anwers the Test-challenge correctly.

We say that an AKE protocol ΠstatAKE is (t,ε)-secure, if there exists no adversary

that (t,ε)-breaks it.

AKE Game with Perfect Forward Secrecy.

We formally capture this notion as a game, played between an adversary A and achallengerC . The challenger implements the collection of oracles {πs

i : i∈ [`],s∈ [d]}.At the beginning of the game, the challenger generates ` long-term key pairs(pki,ski) for all i ∈ [`]. The adversary receives the public keys pk1, . . . , pk` as input.


Now the adversary may start issuing Send, Reveal and Corrupt queries, as well asone Test-query. Finally, the adversary outputs a bit b′ and terminates.

D Definition 6.4

We say that an adversary (t,ε)-breaks an AKE protocol ΠAKE in game GAKE ,if A runs in time t, and at least one of the following two conditions holds:


i such that• πs

i ‘accepts’ when A issues its τ0-th query with intended part-ner Π = j, and

• Pj is τ j-corrupted with τ0 < τ j,5 and



j.If an oracle πs


maliciously.

2. When A issues a Test-query to any oracle πsi and

• πsi ‘accepts’ when A issues its τ0-th query with intended part-

ner Π = j, and Pj is τ j-corrupted with τ0 < τ j,

• A does not issue a Reveal-query to πsi , nor to π t

j such that πsi

has a matching conversation to π tj (if such an oracle exists), and

then the probability that A outputs b′ which equals the bit b sampledby the Test-query satisfies∣∣Pr[b = b′]−1/2

∣∣≥ ε.

If an adversaryA outputs b′ such that b′ = b and the above conditionsare met, then we say that A anwers the Test-challenge correctly.

We say that an AKE protocol ΠAKE is (t,ε)-secure, if there exists no adversarythat (t,ε)-breaks it.

Remark 4. Note that the above definition even allows to corrupt oracles involvedin the Test-session (of course only after the Test-oracle has reached accept-state,in order to exclude trivial attacks). Thus, protocols secure with respect to thisdefinition provide perfect forward secrecy. Note also that we allow the ‘accepting’oracle to be corrupted even before it reaches accept-state, which provides securityagainst key-compromise impersonation attacks.


What is the connection and the main difference between the three definiti-ons?

6.5 AKE Protocols: MAP1

The name ’MAP1’ corresponts to ’multiple authentication protocol one’ introducedin [5].

5 That is, Pj is not corrupted when πsi ‘accepts’. Recall that uncorrupted parties are τ-corrupted with

τ = ∞.

6.5 AKE Protocols: MAP1 Seite 51

MAP1 protocol

Ak = kAB

Bk = kAB

RA$← {0,1}κ

−RA

−−−−−−−−−→RB

$← {0,1}κ

[B.A.RA.RB]k :=(B.A.RA.RB,PRF(k,B.A.RA.RB))

←−[B.A.RA.RB]k−−−−−−−−−−

[A.RB]k :=(A.RB,PRF(k,A.RB))

−[A.RB]k−−−−−−−−−→

Abb. 6.1: The MAP1 pro-tocol from [5].

Theorem 1. MAP1 is a (t,ε)-secure authentication protocol with

ε ≤ ` ·d2κ

.

Proof.Wehave to show that there is no adversary that (t,ε)-breaksMAP1 accordingto Definition 6.2.


State in your own words what needs to be shown.

The proof proceeds in a sequence of games. The first game is the real security experi-ment. We then describe several intermediate games that modify the original gamestep-by-step, and argue that our complexity assumptions imply that each game iscomputationally indistinguishable from the previous one. We end up in the finalgame, where no adversary can break the security of the protocol.

Let break(A)δ

be the event that occurs when the adversary A breaks the security ofGame δ .

Game 0.

We start with the original game GA where a challenger C faithfully simulatesMAP1, and correctly answers all Send queries from the adversary A . Thus, forsome ε we have

Pr[break(A)0 ] = ε.

Game 1.

In this game, we add an abort rule to the simulation: If any nonce value appearstwice, the game will be aborted.


This abort conditionmay occur with a certain probability, whichwe approximate asfollows: If an oracle generates a nonce, this nonce is compared with all previouslyissued nonces. The more nonces have already been generated, the higher theprobability of a match is. If we therefore have a look at the last nonce that maybe generated, the nonce of the last activated oracle, which is number ` · d. Theprobability that this nonce is equal to one of the (` ·d)−1 onces already generatedis (`·d)−1

2κ . For all nonces generated earlier, this probability is smaller.

Thus we may state that the probability that any of the newly generated noncesis equal to a previously generated nonce is strictly smaller than (`·d)

2κ , for all ` · dnonces that may be generated during the simulation. Thus we get an upper boundfor the abort event

Pr[abortnoncecollission]<(` ·d)2

2κ.

Note: This is a very generous upper bound, which can of course be improved. Forthe purpose of this proof it is however only important that this upper bound isnegligible, which is guaranteed by the fact that the numerator term is ploynomial,whereas the denominator term is exponential in the security parameter κ .

If we assume that adversary A could win the original game with probability 1 incase the abort condition occurs, we know that

Pr[break(A)0 ] = Pr[break(A)1 ]+Pr[abortnoncecollission]

⇔ Pr[break(A)0 ]< Pr[break(A)1 ]+(` ·d)2

2κ.

Please note that starting from the present game, replay attacks are no longerpossible, since each nonce is unique.

Game 2.

In this game, we successively replace the PRF computations for each long-livedkey by the evaluation of a truly random fuction f (·). 6 Thus we create a sequence ofsubgames G0

2,G12, . . . ,G

`·(`−1)2 , where game Gk

2 contains `− k PRF evaluations, andk evaluations of the random funtion f (·).

More precisely, we proceed as follows: In game G(k+1)2 we randomly choose one of

the long-lived keys ki j shared between parties Pi and Pj, which was used in gameGk

2 to evaluate the pseudorandom function. Instead of computing

[x]ki j := (x,PRF(ki j,x)),

the challenger computes[x]ki j := (x, f (ki j.x)).

This can be achieved using the standard database trick: In each simulation, thechallenger sets up a empty database to construct a truly random function value byvalue:

• If f (·) is evaluated for the first time on value y, then f (y) is chosen randomlyand the pair (y, f (y)) is stored in the database.

6 Such truly random functions are sometimes called non-programmable Random Oracles.

6.5 AKE Protocols: MAP1 Seite 53

• If f (·) has already been evaluated on value y, then f (y) is retrieved from thedatabase.

The adversary A is not able to evaluate the PRF since he doesn’t know any of thelong-lived keys, thus it is legitimate to prevent the adversary from accessing f (·).

Claim 1. The winning probability of the adversary in any two consecutive games Gk2 and

Gk+12 only differs negligibly.

Proof. We prove this claim by contradiction. Suppose there is at least one value kfor wich the winning probability of the adversary in games Gk

2 and Gk+12 has a non-

negligible difference ∆. We show that in this case we can break the PRF-assumptionfrom Definition 3.1.

Our A-challenger C , who simulates the games Gk2, guesses the value k where the

non-negligible winning difference occurs. His guess will be correct with probability1

`·(`−1) .

Now C randomly chooses a long-lived key ki j from the set of keys that were stillused in Gk

2 to compute the pseudorandom values exchanged between parties Pi andPj. However, instead of replacing the pseudorandom function evaluation with theevaluation of the random function f (·), C lets the PRF-challenger from Definition3.1 compute the checksums. 7

Let b be the bit chosen by the PRF-challenger.

• If b = 0, the new game equals Gk2, although with ki j replaced by an unknown

value k. Thus the winning probability of the adversary equals Pr[break(k,A)2 ].

• If b = 1, the new game equals Gk+12 . Thus the winning probability of the

adversary equals Pr[break(k+1,A)2 ].

C may now break the PRF assumption by issuing b′ = 0 in case A wins the newgame, and setting b′ $←{0,1}κ else. If b = 0, the winning probability is higher byan amount of ∆, so the advantage of C in breaking the PRF assumption is ∆.

This is a contradiction to our assumption that PRF is a secure PRF, and thus wehave proven the claim. �

Game 3.

In the present game, all checksums are random values computed by evaluatingf (·). Since each value over which the checksum is computed contains at leastone different nonce, the adversary A may only guess the correct checksum. Thissucceeds only with probability 1

2κ for a single oracle, and at most with probability`·d2κ for any oracle. Thus we have

Pr[break(A)3 ]≤ ` ·d2κ

.

�

7 Since random nonces are unique in the current game, all query values sent to the PRF-challengerwill be different from the values queried to f (·), so the adversary A is not able to detect this.


Abb. 6.2: The MAP2protocol from [5]. MAP2 protocol

Ak = kAB

Bk = kAB

RA$← {0,1}κ

−−−RA.Text1

−−−−−−−−−−−−−→RB

$← {0,1}κ

←−[B.A.RA.RB.Text1.Text2]k−−−−−−−−−−−−−−−−−−−

−−−[A.RB.Text3]k−−−−−−−−−−−−−→

MAP2 (cf. Figure 6.5) is an extension of MAP1: Three authenticated textsText1,Text2,Text3 are transported. This extension does not change the security pro-perties of the protocol, the proof for MAP1 can be re-used without change. Pleasenote that according to the security proof, parties A and B will only accept if there isa matching conversation with a partner oracle. This implies that B knows that Text1and Text3 are authentic messages from A, and A knows that Text2 is an authenticmessage from B.


Why is Text1 considered as authentic message from A eventhough A nevercomputes a checksum over it?

6.6 AKE Protocols: AKEP1Abb. 6.3: The AKEP1

protocol from [5]. AKEP1 protocol

Akint = kint

AB, kenc = kencAB

Bkint = kint

AB, kenc = kencAB

RA$← {0,1}κ

−−RA

−−−−−−−−−−−−→RB

$← {0,1}κ

k $← {0,1}κ

{k}kenc :=(r,PRF′(kenc,r)⊕ k)

←−[B.A.RA.RB.{k}kenc ]kint

−−−−−−−−−−−−−−−−−

−−[A.RB]kint

−−−−−−−−−−−−→

6.6 AKE Protocols: AKEP1 Seite 55

AKEP1 is the first of two authenticated key exchange protocols introduced in [5].It is based on MAP1 introduced in Section 6.5.


What are the main tagets of the AKEP1 protocol and how are they achie-ved?

Theorem 2. If AKEP1 is instantiated with a secure PRF the protocol is secure with

AdvAKEAKEP1(A )≤ AdvAuthMAP2(B1)+n2Advpr f

PRF(B2)

where B1 and B2 are algotihms with the same running time as A , n is the number ofprotocol parties, and d the maximal number of sessions per party.

Proof. We proceed in a sequence of games.

Game 0.

Let G0 be the original AKE game. Thus we have

AdvG0AKEP1(A ) = AdvAKE

AKEP1(A )

Game 1.

In Game G1 we abort, if one of the aspects in definitions 6.3 is violated.From the proof of MAP2 we get

AdvG0AKEP1(A )≤ AdvG1

AKEP1(B1)+AdvAuthMAP2(B1)

Game 2.

In Game G2 we guess which parties are involved in the session where the adversarywill ask the Test-query. We abort, if the guess was wrong. Thus we get

AdvG1AKEP1(A )≤ n2AdvG2

AKEP1(A )

Game 3.

In Game G3 we replace all PRF computations for the encryption by the evalutationof a truly random function f (·).

Claim 2. No adversary A can distinguish between G2 and G3 with a probability largerthan Advpr f

PRF(A ).

Proof. of Claim

• We construct a destinguisher for the PRF.

• for all computations of {k}kenci j

we call a PRF-challenger on a fresh randomvalue r and receive a value z.

• we set {k}kenci j

:= (r,z⊕ k)


• if the PRF-challenger works with an internal bit b = 0, z is always the eva-luation of the PRF, otherweise it is an evaluation of a random functionf .

• Thus, if b = 0 we are in game G2and if b = 1 we are in game G3.

This proves the Claim. �From the proof of the Claim it is obvious that every adversary A who answersthe Test-query correctly, can be used to construct an adversary B2 against a PRF-challenger. Thus we get

AdvG2AKEP1(A )≤ AdvG3

AKEP1(A )+Advpr fPRF(B2)

Since A can not win the game G3 without breaking the PRF, we haveAdvG3

AKEP1(A ) = 0.Collecting all probabilities, we get

AdvAKEAKEP1(A )≤ (nd)2

2`+n2Advpr f

PRF(B1)︸︷︷︸AdvAuth

MAP1(B1)

+n2Advpr fPRF(B2)

�


Why is it necessary that each value for r is only used once?

6.7 Exercise Seite 57

6.7 Exercise

For the whole excercise let RA,RB be random numbers, κ a security parameterand

• t :=MACk(m) be the message authentication code t of the message m withkey k,

• s := SIGsk(m) be the signature s of the message m with the secret key sk,

• c := sENCk(m) be the symmetric encryption c of the message m with key k,

• c := aENCpk(m) be the asymmetric encryption c of the message m with thepublic key pk.

Please justify your answer for each excercise by reducing a successful attacker to ahard problem. It is not required to give a formal correct proof.

ÜÜbung 6.1: Analysis of Protocols in the BR-Model I

The following authentication protocol between two parties A and B whichshare a symmetric long-term key k is given:

A B

←−RB.MACk(RB)−−−−−−−−−−−

−RA.RB.MACk(RA)−−−−−−−−−−−−−−→

1. Is this protocol a secure authentication protocol in the BR-Model?

ÜÜbung 6.2: Analysis of Protocols in the BR-Model II

The following key exchange protocol between two parties A and B whichshare a symmetric long-term key k is given:

A B

←−−−−−−RB.MACk(RB)−−−−−−−−−−−−−−−−

sk $← {0,1}κ

−RA.RB.sENCk(sk).MACk(RB.RA.sk)−−−−−−−−−−−−−−−−−−−−−−−−−−→

←−−−−−−MACsk(RB)−−−−−−−−−−−−−−−

1. Is this protocol a secure key exchange protocol in the BR-Model?



ÜÜbung 6.3: Analysis of Protocols in the BR-Model III

The following key exchange and authenticate protocol between two partiesA and B is given whereby only party B authenticates towards party A. Forthis purpose B possesses an asymmetric key pair (skB, pkB) for RSA signatureand encryption. The public key pkB is known by party A.

ApkB

B(skB, pkB)

k $← {0,1}κ

−RA.aENCpkB(k)−−−−−−−−−−−−→

←−SIGskB(RA)−−−−−−−−−−

1. Is this protocol a secure key exchange protocol in the BR-Model?


6.7 Exercise Seite 59

ÜÜbung 6.4: Signed Diffie-Hellman

In this exercise we consider the signed Diffie-Hellman protocol where theexchanged values gx and gy are signed individually. Additionally to the keyexchange the signature should ensure authenication and protect againstactive adversaries. We assume that the used signature is generated by a(ts,εs) - secure EUF-CMA signing scheme SIG= (Gen,Sign,Vrfy).

A B

x $← ZqσA ← SignSIGskAgx

−gx,σA

−−−−−−−−−−→If VrfyvkA

(gx,σA) = 0:break

y $← ZqσB ← SignSIGskBgy

←−gy,σB

−−−−−−−−−−If VrfyvkB

(gy,σB) = 0:break

k = gxy

k = gxy

1. Show that this protocol is not a secure AKE protocol in the BR-Model!

2. Modify the protocol to a proofable secure AKE protocol in the BR-Model under the DDH assumption!

3. Phrase a theorem about the security of the modified protocol in theBR-Model.Regard following points: Which pre-conditions apply, what are the securityassumtions, what ist the maximal success probability of the adversary?

Studienbrief 7 One-Round Key Exchange Protocols (ORKE) Seite 61

Studienbrief 7 One-Round Key Exchange Protocols (ORKE)

Authenticated key exchange protocols which need only two message (one round)to establish a key in such a way that it is secure against active adversaries (ORKEprotocols for short) have one very interesting advantage over other AKE protocols:they are fast. More precisely, they only need one Round-Trip-Time (RTT, i.e. thetime from sending a message across the Internet until reception of an answer) toestablish a key.

Therefore, and for the strong security guarantees one can achieve, they have recei-ved much attention in the research community. Two of them are subject to stan-dardization: The Menezes-Qu-Vanstone (MQV) protocol has been standardized inIEEE P1363, and Hashed MQV (HMQV) is a candidate for standardization.

However, they also come with their own set of problems: Replay attacks are possi-ble, and the matching conversations definition from the Bellare-Rogaway modelis not applicable. In addition, too many slightly different security models havebeen proposed, rendering the numerous results achieved in this field pairwiseincomparable.


In this chapter, we give an introduction to ORKE protocols, their security propertiesand limitations, and present three examples: MQV and HMQV for their practicalimportance, and NAXOS for a relatively simple security proof.

The reader should learn which additional security guarantees these protocols givecompared to signed Diffie-Hellman, and what the general disign principles forORKE protocols are.


7.3 Related Work


7.4 2-Message Protocols: Signed Diffie-Hellman

Signed DH

A B

−X = (gx,sigA(x))−−−−−−−−−−−−−→

←−Y = (gy,sigB(y))−−−−−−−−−−−−−

k = gxy

Abb. 7.1: Signed DiffieHellman

Theorem 3. SDH ...

Proof.

�

Seite 62 Studienbrief 7 One-Round Key Exchange Protocols (ORKE)

7.5 Canetti-Krawczyk Model

A protocol Π is (t,ε)-secure if for any t-bounded adversary A

Adv(A,Π)≤ ε

Adv(A,Π) = |A answers Test query correctly − 12 |

7.6 2-Message Protocols: HMQVAbb. 7.2: The HM-

QV protocol from []. (H)MQV protocol

A(pkA,skA) = (A = ga,a)

B(pkB,skB) = (B = gb,b)

x $← {0,1}κ

X := gx

−X

−−−−−−−−−−−→y $← {0,1}κ

Y := gy

k := H((X ·Ad)y+eb)

←−Y

−−−−−−−−−−−k := H((Y ·Be)x+da)

Whereby A and B calculate the same value since:

σA = (Y ·Be)x+da = (gy ·gbe)x+da = g(y+be)(x+da) = (gx ·gda)y+be = (X ·Ad)y+eb = σB

MQV : d = X := 2`+(X mod 2`)

e = Y := 2`+(Y mod 2`)

HMQV : d = H(X , B)

e = H(Y, A)

When an Adversary A sends an Reveal (Exponent) query to a party participating inthe HMQV protocol he is not able to calculate the session key, since the knowledgeof the private long term key is necessary, as can be seen in Figure 7.6 and thereforeis not able to impersonate this party.

ΠA ΠB

TA TB

rA

rB

7.6 2-Message Protocols: HMQV Seite 63

ΠA ΠB

In the BR model there exist a problem with replay attacks against the responderorakle. In general the BR model is not well suited to analyze two way protocols.

Test ΠA A

Π1B

Π2B

Π3B

Π4B

m1

m12

m22

m32

m 42

m22

m1

m1

m1

m1

Reveal Key?

��RevealKey

Theorem 4. HMQV ...

Proof. We have ...

Game 0.

We start with the original game GA where a challenger C faithfully simulatesAKEP1, and correctly answers all Send, Corrupt and Reveal queries from the adver-sary A . Thus, for some ε we have

Pr[break(A)0 ] = ε.

Game 1.

In this game, we try to guess in which session the adversary will ask the Test query.We abort the game if our guess was wrong. Tus we get

Pr[break(A)0 ]≤ Pr[break(A)1 ] · (1(d · `)2 .

In the following let πsi and π t

j the two oracles participating in the Test session.

�


7.7 2-Message Protocols: NAXOS

NAXOS is the name of a protocol proposed by Brian A. LaMacchia, Kristin Lauterand Anton Mityagin in [22]. The authors claim to stregthen the CK model byreplacing SessionStateReveal with EphemeralKeyReveal, but this is just a choicewithin the CK model: By defining the state to be revealed by SessionStateReveal tobe the secret ephemeral exponent of each oracle (denoted by eskX in Abbildung 7.3),this query is identical to the newly proposed EphemeralKeyReveal.

NAXOS comes with a security proof in the Random Oracle Model (ROM). Thesecuritymodel and the protocol construction are closely related, a fact that has beencritizised afterwards. The security model has been labeled “extended Cannetti-Krawczyk” (eCK), the first in a series of slightly different eCK models. The factthat no standad security model was established for the analysis of ORKE protocolsis the main weakness of this research area.

7.7.1 Protocol DescriptionAbb. 7.3: The NAXOS

protocol from [22]. Plea-se note that we havemodified the protocolslightly by adding the

identities of sender andrecipient to each messa-

ge. This does not changethe security of the pro-tocol, but makes defini-

tions and proofs clearer.

NAXOS protocol

A(pkA,skA) = (A = ga,a)

πsA

B(pkB,skB) = (B = gb,b)

π tB

eskA$← {0,1}κ

X := gH1(eskA,skA)

−A, B,X

−−−−−−−−−−−→eskB

$← {0,1}κ

Y := gH1(eskB,skB)

←−B, A,Y

−−−−−−−−−−−

K := H2(DH(X , pkB),DH(Y, pkA),DH(X ,Y ), A, B)

In Abbildung 7.3, the NAXOS protocol is described. The computations involve agroup G=< g> of prime order q (either a subgroup of some groupZ∗p, or an ellipticcurve group), and two random oracles H1 : {0,1}κ ×Zq → Zq and H2 : {0,1}∗→{0,1}κ .

7.7.2 Security Model: eCK

M winsif b′ = b b′ M

Send

Reveal

Corrupt

EKR

Test

ζ

P1, . . . ,P2

Π

Π

• Testmay only be asked against a clean oracle

• An oracle is not clean if (for sid = sid∗)

7.7 2-Message Protocols: NAXOS Seite 65

– Corrupt and REK to sid or sid∗

– Reveal to sid or sid∗

– if sid∗ does not exist Corrupt(B) for intended Partner B

Session identifier sid

sid = (role, ID, ID∗,X ,Y )

matching sessions sid = sid∗

sid = (role, ID, ID∗,X ,Y )

sid∗= (role′, ID∗, ID,X ,Y )

role 6= role’

7.7.3 Security Proof

We first prove an indistinguishability result, which will be used several times inthe proof of the main theorem.

Lemma 1. The advantage that an eCK-adversary can distinguish, in the test session, amessage Z = gH1(esk,sk) computed according to the NAXOS specification from a randomvalue Z′ is bounded by εDLOG), where εDLOG is the probability that the DLOG assumptionis broken.

Proof. To check if a message was computed according to the NAXOS specification,an adversary has to know the input to the random oracle H1. To do so, he can followone of the following strategies:

(1) Guess esk and sk: This strategy only succeeds with probability 1q·2κ .

(2) Query Corrupt, and guess esk: This strategy succeeds with probability 12κ .

(3) Query RevealEphemeralKey, and guess sk: probability 1q .

(4) Query RevealEphemeralKey and compute sk from pk: This amounts to breakingthe DLOG assumption, and thus only happens with probability εDLOG.

If we assume that q≤ 2κ , then the maximum of these values (and thus the optimalstrategy) is εDLOG, since the discrete log can also be computed by guessing it.

Please not that the adversary cannot query both esk and sk in the test session. �

Add Gap-DH-Assumption to Section 3

Theorem 5. If H1 and H2 are modelled as random oracles, and if all computations areperformed in a group in which the Gap-DH assumption holds, then NAXOS is secure inthe eCK security model and we have

AdvA0 ≤

(nk)2

2κ+(nk) · ((nk) · (εDLOG + εCDH)+n · (εDLOG + εGDH)).


Proof. We distinguish 2 cases, andmodel each case as a sequence of games. In Case1, there is a second oracle simulated by the challenger from which the tst oraclereceives a unmodified message. In Case 2, the adversary has created or modifiedthe message which the test oracle receives. For each case, we embedd the Gap-DHchallenge differently: For Case 1 in the two messages exchanged, and for Case 2 inthe public key in the intended partner of the test oracle, and in the message sentby the test oracle.

Game 0: Original Game. We start with the original game GA where a chal-lenger C faithfully simulates NAXOS, and correctly answers all Send, Corrupt,RevealE phemeralKey and Reveal queries from the adversary A . In this game, thetwo random oracles are separate entities, to which bothA andC maymake queries.Thus, for some ε we have

Pr[break(A)0 ] =12+ ε,

and thusAdvA

0 = ε.

Game 1: Exclude H1 collissions. In this game, the challenger aborts the simulationif he ever sees a H1 collission, i.e. the same value is returned from H1 for differentqueries. Let Ecoll be the event that such a collission occurs. The we have

break(A)0 = (break

(A)0 ∩Ecoll)∪ (break

(A)0 ∩Ecoll) =

= (break(A)0 ∩Ecoll)∪break

(A)1 ≤ (T RUE ∩Ecoll)∪break

(A)1 = Ecoll ∪break

(A)1 .

This translates into probabilities as

Pr[break(A)0 ]≤ Pr[Ecoll ]+Pr[break(A)1 ].

We now have to estimate the probability that a collisionmay occur. Since the outputof a random oracle is a random variable, we can argue with independent choiceprobabilities. Für the first output of H1 the collission probability is 0, for the secondit is 1

2κ , for the third 22κ , and so on: each new value my have a collission with one

of the previously returned values. Since each oracle queries H1 at most once, theupper bound for the number of oracle queries is n · k (number of parties timesnumber of oracles per party). So we have

Pr[Ecoll ]≤ 0+1

2κ+

22κ

+3

2κ+ . . .+

nk−12κ

≤ nk2κ

+nk2κ

+nk2κ

+nk2κ

+ . . .+nk2κ

= nknk2κ

=(nk)2

2κ.

Therefore we havePr[break(A)0 ]≤ (nk)2

2κ+Pr[break(A)1 ]

and get, by subtracting 12 on both sides of the inequality,

AdvA0 ≤

(nk)2

2κ+AdvA

1 .

Game 2: Guess Test Oracle. In this game, the challenger guesses the test oracle


πsC (i.e. the oracle to which the adversary will ask Test), which may either be an

initiator or a responder oracle, out of the set of all nk orcales. C aborts the game ifhis guess was wrong, so the advantage of A is reduced by a factor of nk:

AdvA1 ≤ (nk) ·AdvA

2 .

From now on we have to consider two different cases, and the proof will branch.

Case 1: The test oracle πsX has a a matching conversation to another

oracle simulated by C : πsC

ms←− π tD

Add hasmatchingto definition to the security model of this section.

This case is handled in Lemma 2.

Case 2: The test oracle πsX does not have a matching conversation to any

other oracle simulated by C

This case is handled in Lemma 3.

�

Lemma 2. If πsC

ms←− π tD, then AdvA

2 in Theorem 5 is bounded by

AdvA2 ≤ (nk) · (εDLOG + εCDH).

Proof. To prove the lemma, we embedd a CDH challenge (X0,Y0) in the messagesexchanged between the two oracles, which we therefore have to guess correctly.By simulationg the random oracle H2, the challenger will learn the solution of theCDH challenge.

Game 3: Guess Matching oracle. In this game, we try to guess which oracle π tD

will send the message that is received by the test oracle. We abort the game if ourguess was wrong. Again the advantage of A is reduced by a factor of nk:

AdvA2 ≤ (nk) ·AdvA

3 .

Game 4: Simulate H2. The “real” random oracle H2 is now replaced by a simulatedrandomoracleH ′2, and the simulation is done by the challenger. Since both functionsare random oracles, this does not change the advantage of the adversary:

AdvA3 = AdvA

4 .

Please note that from now on, the challenger can see any input to H ′2.

Game 5: Use GDH challenge in test session. In this game, we embed the GDHchallenge (X0,Y0) in the two messages exchanged between the test oracle πs

C andπ t

D. Let w.l.o.g. assume that πsC sends X0.

The challenger C still can simulate the protocol, by answering all queries notadressed to other oracles according to the protocol specification. For the two oraclesπs

C and π tD, all queries except RevealEphemeralKey can be answered. If the adversary

queries RevealEphemeralKey to one of these two oracles, the challenger answerswith a random value.


The adversary could detect this modification if he was allowed to query bothCorrupt and RevealEphemeralKey to one of the two oracles, but this is prohibitedby the security model. According to Lemma 1, the adversary can only detect thismodification with advantage εDLOG. Thus we have

AdvA4 = AdvA

5 + εDLOG.

If the adversary tries to answer the Test query without asking H ′2, or if he queriesH ′2 with a different 5-tuple, his advantage is negligible, since for b = 0 and b = 1the answer from the test oracle is just a random value.

His only chance to increase his advantage is to query H ′2 with the correct 5-tuple,i.e. with (DH(X0, pkD),DH(Y0, pkC),DH(X0,Y0),C,D. To do so, he has to computeDH(X0,Y0), i.e. he has to break the CHD assumption. Therfore we have

Pr[break(A)5 ] =12+ εCDH ,

and thusAdvA

5 = εCDH

.

�

Lemma 3. If the message received by πsC has been generated or modified by the adversary,

then AdvA2 in Theorem 5 is bounded by

AdvA2 ≤ n · (εGDH + εDLOG).

Proof. To prove this lemma, we embed a GDH challenge (X0,Y0) in (a) the publickey of the party whose identity is included in the message received by the testoracle, and (b) in the message sent by the test oracle. Again, by simulating H1, thechallenger will learn the solution of the GDH challenge. Please note that we needthe GDH assumption here instead of the CDH assumption, since the challengerneeds access to a DDH oracle to simulate the NAXOS protocol in such a way thatthe adversary is unable to detect the inclusion of the challenge.

Game 3’: Guess Public Key. In this game, we try to guess which identifier theadversary will use in themessage received by the test oracle πs

C (which was guessedin the main theorem). We denote the guessed identifier by D in the following. Weabort the game if our guess was wrong. The winning probability of A is reducedby a factor of n:

AdvA2 ≤ n ·AdvA

3′ .

Game 4’: Embed X0 in the chosen Public Key and simulate H2. In this game, weset pkD := X0. In doing so, we get a simulation problem: the challenger is no longerable to simulate Corrupt(D) and Reveal. Fortunately, since we are in the test session,A is not allowed to ask Corrupt(D) because of the restrictions imposed by the eCKmodel.

To be able to answer Reveal queries, which are forbidden in the test session, butmay be asked in other protocol sessions involving a D-oracle, the challenger now


simulates the random oracle H2. W.l.o.g. we may now assume that the D-oraclefor which Reveal is asked is a responder oracle. (The case of an initiator oracle isidentical, only the first 2 values of the 5-tuple input to H2 re exchanged.)

Whenever a Reveal query is asked to some responder oracle πrD belon-

ging to party D, the challenger normally would have to compute τ =

(DH(X ,X0),DH(Y, pkF),DH(X ,Y ), F , D), select a random value K $← {0,1}κ , andrecord K as the output of H2 on input τ . However, if the value X was not generatedby the challenger itself, but by the adversary, the challenger cannot computethe first component DH(X ,X0) of τ , and therefore the adversary may detect themodification pkD := X0 in this game by querying H2 with two different values τ,τ ′,which differ in the first component, and by asking Reveal(πr

D).

The challenge for the challenger is to assign the randomly chosen K to the correctH2-input τ . This is where the GDH assumption comes in: To simulate Game 4’correctly, the challenger needs access to a DDH oracle, to query for the value(X ,X0,τ1). If this oracle returns TRUE, then τ1 = DH(X ,X0), and in the simulationof H2 the value K must be assigned to the input τ . If not, a new random value isassigned to τ .

Since the simulation is perfect, we have

AdvA3′ = AdvA

4′ .

Game 5’: Assign Y0 to the message sent by the test oracle. In this game, we ge-nerate the ephemeral private key of the test oracle randomly according to thespecification (wen need this to be able to answer RevealEphemeralKey queries), butwe set the message sent by the test oracle to Y0.

In order to achieve an advantage greater than 0, the adversary has to query H2with the correct input τ , which contains DH(X0,Y0) as one of its components. SinceH2 is simulated by the challenger, he learns this value, and thus can answer theGDH challenge. (GDH instead of CDH because the adversary may also query theDDH oracle.)

The only way for A to distinguish this game from the previous game is to detectthat Y0 was not computed according to the NAXOS specification. The advantagefor this was shown to be εDLOG in Lemma 1.

Thus we have

AdvA4′ ≤ εGDH + εDLOG.

�

Studienbrief 8 Transport Layer Security (TLS) Seite 71

Studienbrief 8 Transport Layer Security (TLS)



8.3 Related Work


8.4 TLS Handshake

The current version of TLS is 1.2 [14] and coexists with its predecessors TLS 1.0 [12]and TLS 1.1 [13]. In the following we give a description of all messages sent duringthe TLS Handshake with ephemeral Diffie-Hellman key exchange and client au-thentication (i.e. for ciphersuites TLS_DHE_*). This description and its illustrationin Figure 8.1 are valid for all TLS versions since v1.0. Our description makes use ofseveral ‘state variables’ (Λ,k,Π,ρ,st). For instance, variable Λ ∈ {accept,reject}determines whether one party ‘accepts’ or ‘rejects’ an execution of the protocoland variable k stores the session key. These variables correspond to the ones usedin the security model (Section 6.4).

TLS Handshake

Client CIC = pkC,skC

Server SIS = pkS,skS

m1$← C_Req()

−m1

−−−−−−−−−−−→(m2, . . . ,m6)

$←S_Resp(m1)

←−m2, . . . ,m6−−−−−−−−−−−

(m7, . . . ,m11)$←

C_Resp(m2, . . . ,m6)

−m7, . . . ,m11−−−−−−−−−−−→

(m12,m13) ←S_Acc(m7, . . . ,m11)

←−m12,m13

−−−−−−−−−−−C_Acc(m12,m13)

pre-accept phase

post-accept phase

−EncStE(kClientenc , len,H,data,ste)−−−−−−−−−−−−−−−−−−−−−−−→

←−EncStE(kServerenc , len,H,data,ste)−−−−−−−−−−−−−−−−−−−−−−−

Abb. 8.1: TLS hands-hake for ciphersuitesTLS_DHE_* with clientauthentication

The TLS-DHE Handshake Protocol consists of 13 messages (m1 . . .m13), whosecontent ranges from constant byte values to tuples of cryptographic values. Not all

Seite 72 Studienbrief 8 Transport Layer Security (TLS)

messages are relevant for our security proof, we list them merely for completeness.All messages are prepended with a numeric tag that identifies the type of message,a length value, and the version number of TLS. All messages are sent throughthe TLS Record Layer, which at startup provides no encryption nor any othercryptographic transformations.

Client Hello.Messagem1 is the Client Hellomessage. It contains four values, twoof which are optional. For our analysis the only important value is rC, the randomvalue chosen by the client. It consists of 32 bytes (256 Bits), where 4 Bytes are usuallyused to encode the local time of the client. The remaining 28 Bytes are chosenrandomly by the client. This is followed by a list cs-list of ciphersuites, whereeach ciphersuite is a tuple of key exchange method, signing, encryption and MACalgorithms, coded as two bytes. Data compression is possible before encryptionand is signaled by the inclusion of zero or more compression methods.

Server Hello and Server Key Exchange. The Server Hellomessage m2 has the sa-me structure as Client Hello, with the only exception that at most one ciphersuiteand one compression method can be present. In our analysis the random value rSis important. The server may send a TLS session ID sID to the client. Message m3may contain a chain of certificates, starting from the TLS server certificate up to adirect child of a root certificate. Since we do not include public key infrastructuresin our analysis (the identity of each party is its public key pkS), one certificate certScontaining pkS (which may be self-signed) is sufficient here. When the certificatecertS is received, the client sets its partner id Π := S. The public key in the certificatemust match the ciphersuite chosen by the server. For ephemeral Diffie-Hellmankey exchange, the public key may be any key that can be used to sign messages.The Diffie-Hellman (DH) key exchange parameters are contained in the ServerKey Exchange message m4, including information on the DH group (e.g. primenumber p and generator g for a prime-order q subgroup of Z∗p), the DH share TS,and a signature computed over these values plus the two random numbers rC andrS. The next two messages are very simple: the Certificate Requestmessage m5only contains a list of certificate types that the client may use to authenticate itself,and the Server Hello Done message m6 does not contain any data, but consistsonly of a constant tag with byte-value ‘14’ and a length value ‘0’.

Client Key Exchange and Client Finished. Having received these messages, thesignature σS is verified. If this fails, the client ‘rejects’ and aborts. Otherwise, aftersuccessful verification, the client is able to complete the key exchange and tocompute the cryptographic keys. The Client Certificatemessage m7 containsa signing certificate certC with the public key pkC of the client. Message m8 iscalled Client Key Exchange, and contains the Diffie-Hellman share TC of the client.When the certificate certC is received by the server, the server sets its partner idΠ :=C. To authenticate the client, a signature σC is computed on a concatenationof all previous messages (up to m8) and padded prefixes, thus including the tworandom nonces and the two Diffie-Hellman shares. This signature is contained inthe Certificate Verifymessage m9.

The client is now also able to compute the premaster secret pms, from which allfurther secret values are derived. After computing the master secret ms, it is storedfor the lifetime of the TLS session, and pms is erased from memory. The mastersecret ms is subsequently used, together with the two random nonces, to deriveall encryption and MAC keys as well as the Client Finishedmessage finC. More

8.4 TLS Handshake Seite 73

precisely, the key material kClientenc := (KC→Senc ,KC→S

mac ) and kClientdec := (KS→Cenc ,KS→C

mac ) iscomputed as

KC→Senc ||KS→C

enc ||KC→Smac ||KS→C

mac := PRF(ms, label2||rC||rS) (8.1)

where kClientenc is used to encrypt and authenticate data sent from the client to theserver, and kClientdec is used to decrypt and verify data received from the server.

After these computations have been completed, the keys are handed over to theTLS Record Layer of the client, which is now able to encrypt and MAC any data. Tosignal the ‘start of encryption’ to the server, a single message m10 (Change CipherSpec) with byte value ‘1’ ( f lagenc) is sent unencrypted to S. Then message m11consists of an authenticated encryption of the Client Finishedmessage finC.Remark 5. Please note that a padding is applied to finC before encryption and thatthis padding allows for (partially) known plaintext attacks on m11. Thus if weanalyse TLS in a key-indistinguishability-based security model, the answer to aTest query could be determined by simply decrypting m11, and checking if theresulting plaintext has the appropriate padding. Thus TLS is not provably securein any such model.

Server Finished. After the server has received messages m7,m8,m9, the server ve-rifies the signature in m9. If this fails, the server ‘rejects’ (i.e., sets Λ = ‘reject’)and aborts. Otherwise, after successful verification, the server determines pmsand ms. From this the encryption and MAC keys kServerenc := (KS→C

enc ,KS→Cmac ) and

kServerdec := (KC→Senc ,KC→S

mac ) are computed as in (8.1).1 Now m11 can be decrypted tocheck finC by computing the pseudo-random value on the ms and all previousmessages (m1 . . .m10). If this check fails, the serrver ‘rejects’ and aborts. If the checkis successful, it ‘accepts’ (i.e. sets Λ = ‘accept’), computes the Server Finishedmessage finS and sends messages m12 and m13 to the client. If the check of finS onthe client side is successful, the client also ‘accepts’.

Encrypted Payload Transmission. The obtained keys can now be used to transmitpayload data in the TLS Record Layer using a stateful symmetric encryption sche-me StE = (EncStE,DecStE) (cf. Section 3.10.3). The CBC-based TLS Record Layerprotocols work as follows. The state ste of the encryption algorithm consists of asequence number, which is incremented on each encryption operation. The en-cryption algorithm takes a message m and computes a MAC over m, the sequencecounter, and some additional header data H (such as version numbers, for instan-ce). Then message and MAC are encoded into a bit string by using a padding to aspecified length len and encrypted (‘MAC-then-Encode-then-Encrypt’).

The state std of the decryption algorithm consists of a sequence number, which isincremented on each decryption operation. Given a ciphertext, the algorithm de-crypts and verifies the MAC using its own sequence counter. See [25] for details.

Abbreviated TLS Handshakes, side-channels, and cross-protocol attacks. In ouranalysis, we do not consider abbreviated TLS Handshakes, but we note that theserver can always enforce a full TLS Handshake. Moreover, we do not considerattacks based on side-channels, such as error messages or implementation issueslike the cross-protocol attack from [29].

1 Note that we have kServerenc = kClientdec and kServerdec = kClientenc .

Seite 74 Studienbrief 8 Transport Layer Security (TLS)

Abb. 8.2: Computati-on of Client/Server

Handshake Messages

Client_Request()

ρ := Client

rC$←{0,1}λ

m1 := (rC,cs-list)

Server_Response()

ρ := Server

rS$←{0,1}λ

tS$← Zq,TS := gtS mod p

σS := SignSIG(skS,rC||rS||p||g||TS)m2 := (rS,cs-choice)m3 := certSm4 := (p,g,TS,σS)m5 := get-certm6 := done

Client_Accept()

If finC 6= PRF(ms, label3||m1|| . . . ||m10)Λ := ‘reject’ and abort

elseΛ := ‘accept’ and output k

Client_Response()

Π := S, S is determined from certSif VfySIG(pkΠ,σS,rC||rS||p||g||TS) = 0

Λ := ‘reject’ and abortelse

tC$← Zq,TC := gtC mod p

(m7,m8) := (certC,TC)σC := SignSIG(skC,m1|| . . . ||m8)

pms := T tCS mod p

ms := PRF(pms, label1||rC||rS)

KC→Senc ||KS→C


mac :=PRF(ms, label2||rC||rS)

kClientenc := (KC→Senc ,KC→S

mac )

kClientdec := (KS→Cenc ,KS→C

mac )

k := (kClientenc ,kClientdec )(m9,m10) := (σC, f lagenc)finC := PRF(ms, label3||m1|| . . . ||m10)

m11 := EncStE(kClientenc , len,H,finC,ste)

Server_Accept()

Π :=C, C is determined from certCif VfySIG(pkΠ,σC,m1|| . . . ||m8) = 0


pms := T tSC mod p

ms := PRF(pms, label1||rC||rS)

KC→Senc ||KS→C


mac :=PRF(ms, label2||rC||rS)

kServerenc := (KS→Cenc ,KS→C

mac )

kServerdec := (KC→Senc ,KC→S

mac )

k := (kServerenc ,kServerdec )m12 := f lagencfinS := PRF(ms, label4||m1|| . . . ||m12)

m13 := EncStE(kServerenc , len,H,finS,ste)If finC 6= PRF(ms, label3||m1|| . . . ||m10)


Λ := ‘accept’ and output k

8.5 TLS Record Layer

JS: Description of the TLS Record Layer needed.

8.6 TLS Ciphersuites

JS: Description of the CipherSuite families TLS-RSA, TLS-DH and TLS-DHE.

8.7 Cryptographic Attacks on TLS

JS: Bleichenbacher, CRIME, Lucky13.

Studienbrief 9 Truncated TLS is a Secure AKE Protocol Seite 75

Studienbrief 9 Truncated TLS is a Secure AKE Protocol


9.2 Related Work



9.4 Truncated TLS with Ephemeral Diffie-Hellman is a SecureAKE Protocol

In this section we prove the security of a modified version of the TLS Handshakeprotocol. As discussed in Section 8.4 remark 5, it is impossible to prove the full TLSHandshake protocol secure in any securitymodel based on key-indistinguishability,like the model from Section 6, because the encryption and MAC of the Finishedmessages provide a ‘check value’, that can be exploited by an adversary to deter-mine the bit b chosen by the Test-query.

Therefore we consider a ‘truncated TLS’ protocol as in [23, 24]. In this truncatedversion, we assume that the Finished messages are sent in clear, that is, neitherencrypted nor authenticated by aMAC.More precisely, wemodify the TLS protocoldepicted in Figure 8.1 such that

• message m11 contains only finC (instead of EncStE(kClientenc , len,H,finC,ste)), and

• message m13 contains only finS (instead of EncStE(kServerenc , len,H,finS,ste)).

This simple modification allows to prove security in the key-indisinguishability-based security model from Section 6.

Theorem 6. Let µ be the output length of PRF and let λ be the length of the nonces rC andrS. Assume that the pseudo-random function PRF is (t,εprf)-secure, the signature schemeis (t,εsig)-secure, the DDH-problem is (t,εddh)-hard in the group G used to compute theTLS premaster secret, and the PRF-ODH-problem is (t,εprfodh)-hard with respect to G andPRF.

Then for any adversary that (t ′,εttls)-breaks the truncated ephemeral Diffie-Hellman TLSHandshake protocol in the sense of Definition 6.4 with t ≈ t ′ holds that

εttls ≤ 4 ·d`(

d`2λ

+ ` · εsig+54· εddh+

52· εprf +d`

(εprfodh+ εprf +

12µ

)).

We consider three types of adversaries:

1. Adversaries that succeed in making an oracle accept maliciously, such thatthe first oracle that does so is a Client-oracle (i.e., an oracle with ρ = Client).We call such an adversary a Client-adversary.

2. Adversaries that succeed in making an oracle accept maliciously, such thatthe first oracle that does so is a Server-oracle (i.e., an oracle with ρ = Server).We call such an adversary a Server-adversary.

3. Adversaries that do not succeed in making any oracle accept maliciously, butwhich answer theTest-challenge.We call such an adversary aTest-adversary.

Seite 76 Studienbrief 9 Truncated TLS is a Secure AKE Protocol

We prove Theorem 6 by proving three lemmas. Lemma 4 bounds the probabilityεclient that a Client-adversary succeeds, Lemma 5 bounds the probability εserver thata Server-adversary succeeds, and Lemma 6 bounds the success probability εke of aTest-adversary. Then we have

εttls ≤ εclient+ εserver+ εke.

9.4.1 Authentication

Lemma 4. For any adversary A running in time t ′ ≈ t, the probability that there existsan oracle πs

i with ρ = Client that accepts maliciously is at most

εclient ≤ d`(

d`2λ

+ ` · εsig+d`(

εprfodh+ εprf +1

2µ

))where all quantities are defined as stated in Theorem 6.

Proof. The proof proceeds in a sequence of games, following [6, 27]. The first gameis the real security experiment. We then describe several intermediate games thatmodify the original game step-by-step, and argue that our complexity assumptionsimply that each game is computationally indistinguishable from the previous one.We end up in the final game, where no adversary can break the security of theprotocol.

Let break(1)δ

be the event that occurs when the first oracle that accepts maliciouslyin the sense of Definition 6.4 with ρ = Client in Game δ .

Game 0.

This game equals the AKE security experiment described in Section 6. Thus, forsome εclient we have

Pr[break(1)0 ] = εclient.

Game 1.

In this game we add an abort rule. The challenger aborts, if there exists any oracleπs

i that chooses a random nonce rC or rS which is not unique. More precisely, thegame is aborted if the adversary ever makes a first Send query to an oracle πs

i , andthe oracle replies with random nonce rC or rS such that there exists some otheroracle πs′

i′ which has previously sampled the same nonce.

In total less than d` nonces rC and rS are sampled, each uniformly random from{0,1}λ . Thus, the probability that a collision occurs is bounded by (d`)22−λ , whichimplies

Pr[break(2)0 ]≤ Pr[break(2)1 ]+(d`)2

2λ.

Note that now each oracle has a unique nonce rC or rS, which is included in thesignatures. We will use this to ensure that each oracle that accepts with non-corrupted partner has a unique partner oracle.

9.4 Truncated TLS with Ephemeral Diffie-Hellman is a Secure AKE Protocol Seite 77

Game 2.

We try to guess which client oracle will be the first oracle to accept maliciously.If our guess is wrong, i.e. if there is another (Client or Server) oracle that acceptsbefore, then we abort the game.

Technically, this game is identical, except for the following. The challenger guessestwo random indices (i∗,s∗) $← [`]× [d]. If there exists an oracle πs

i that ‘accepts’maliciously, and (i, j) 6= (i∗, j∗) and πs

i has ρ 6= Client, then the challenger abortsthe game. Note that if the first oracle πs

i that ‘accepts’ maliciously has ρ = Client,then with probability 1/(d`)we have (i, j) = (i∗, j∗), and thus

Pr[break(2)1 ] = d` ·Pr[break(2)2 ].

Note that in this game the attacker can only break the security of the protocol,if oracle πs∗

i∗ is the first oracle that ‘accepts’ maliciously and has ρ = Client, asotherwise the game is aborted.

Game 3.

Again the challenger proceeds as before, but we add an abort rule. We want tomake sure that πs∗

i∗ receives as input exactly the Diffie-Hellman value TS that wasselected by some other uncorrupted oracle that received the nonce rC chosen byπs∗

i∗ as first input (note that there may be several such oracles, since the attackermay send copies of rC to many oracles).

Technically, we abort and raise event abortsig, if oracle πs∗i∗ ever receives as input a

messagem3 = certS indicating intended partnerΠ= j andmessagem4 =(p,g,TS,σS)such that σS is a valid signature over rC||rS||p||g||TS, but there exists no oracle π t

jwhich has previously output σS. Clearly we have

Pr[break(1)2 ]≤ Pr[break(1)3 ]+Pr[abortsig].

Note that the experiment is aborted, if πs∗i∗ does not accept maliciously, due to

Game 2. This means that party Pj must be τ j-corrupted with τ j = ∞ (i.e., notcorrupted) when πs∗

i∗ accepts (as otherwise πs∗i∗ does not acceptmaliciously). To show

that Pr[abortsig] ≤ ` · εsig, we construct a signature forger as follows. The forgerreceives as input a public key pk∗ and simulates the challenger for A . It guessesan index φ

$← [`], sets pkφ = pk∗, and generates all long-term public/secret keysas before. Then it proceeds as the challenger in Game 3, except that it uses itschosen-message oracle to generate a signature under pkφ when necessary.

If φ = j, which happens with probability 1/`, then the forger can use the signaturereceived by πs∗

i∗ to break the EUF-CMA security of the signature scheme with suc-cess probability εsig, so Pr[abortsig]/`≤ εsig. Therefore if Pr[abortsig] is not negligible,then εsig is not negligible as well and we have

Pr[break(1)2 ]≤ Pr[break(1)3 ]+ ` · εsig.

Note that in Game 3 oracle πs∗i∗ receives as input a Diffie-Hellman value TS such

that TS was chosen by another oracle, but not by the attacker. Note also that theremay be multiple oracles that issued a signature σS containing rC, since the attackermay have sent several copies of rC to several oracles.


Game 4.

In this game we want to make sure that we know which oracle π tj will issue the

signature σS that πs∗i∗ receives. Note that this signature includes the random nonce

rS, which is unique due to Game 1. Therefore the challanger in this game proceedsas before, but additionally guesses two indices ( j∗, t∗) $← [`]× [d]. It aborts, if theattacker does not make a Send-query containing rC to π t∗

j∗ , and π t∗j∗ responds with

messages containing σS such that σS is forwarded to πs∗i∗ .

We know that there must exists at least one oracle that outputs σS such that σS isforwarded to πs∗

i∗ , due to Game 3. Thus we have

Pr[break(1)3 ]≤ d` ·Pr[break(1)4 ].

Note that in this game we know exactly that oracle π t∗j∗ chooses the Diffie-Hellman

share TS that πs∗i∗ uses to compute its premaster secret.

Game 5.

Recall that πs∗i∗ computes the master secret as ms = PRF(T tc

S , label1||rC||rS), whereTS denotes the Diffie-Hellman share received from π t∗

j∗ , and tc denotes the Diffie-Hellman exponent chosen by πs∗

i∗ . In this game we replace the master secret mscomputed by πs∗

i∗ with an independent random value ms. Moreover, if π t∗j∗ receives

as input the same Diffie-Hellman share TC that was sent from πs∗i∗ , then we set

the master secret of π t∗j∗ equal to ms. Otherwise we compute the master secret as

specified in the protocol. We claim that

Pr[break(1)4 ]≤ Pr[break(1)5 ]+ εPRF-ODH.

Suppose there exists an adversary A that distinguishes Game 5 from Game 4. Weshow that this implies an adversary B that solves the PRF-ODH problem.

Adversary B outputs (label1||rC||rS) to its oracle and receives in response(g,gu,gv,R), where either R = PRF(guv, label1||rC||rS) or R $← {0,1}µ . It runs A byimplementing the challenger for A , and embeds (gu,gv) as follows. Instead ofletting πs∗

i∗ choose TC = gtC for random tC$← Zq, B defines TC := gu. Similarly, the

Diffie-Hellman share TS of π t∗j∗ is defined as TS := gv. Finally, the master secret of

πs∗i∗ is set equal to R.

Note that πs∗i∗ computes the master secret after receiving TS from π t∗

j∗ , and then itsends m8 = TC. If the attacker decides to forward m8 to π t∗

j∗ , then the master secretof π t∗

j∗ is set equal to R. If π t∗j∗ receives TC′ 6= TC, then B queries its oracle to compute

ms′ = PRF(T vC′ , label1||rC||rS), and sets the master secret of π t∗

j∗ equal to ms′.

Note that in any case algorithm B ‘knows’ the master secret of πs∗i∗ and π t∗

j∗ , andthus is able to compute all further protocol messages (in particular the finishedmessages finC and finS) and answer a potential Reveal-query to π t∗

j∗ as required (notethat there is no Reveal-query to πs∗

i∗ , as otherwise the experiment is aborted, due toGame 2). If R = PRF(guv, label1||rC||rS), then the view of A is identical to Game 4,while if R $←{0,1}µ then it is identical to Game 5, which yields the above claim.


Game 6.

In this gamewe replace the function PRF(ms, ·) used by πs∗i∗ with a random function.

If π t∗j∗ uses the samemaster secret ms as πs∗

i∗ (cf. Game 5), then the function PRF(ms, ·)used by π t∗

j∗ is replaced as well. Of course the same random function is used forboth oracles sharing the same ms. In particular, this function is used to computethe Finishedmessages by both partner oracles.

Distinguishing Game 6 from Game 5 implies an algorithm breaking the security ofthe pseudo-random function PRF, thus

Pr[break(1)5 ]≤ Pr[break(1)6 ]+ εprf

Game 7.

Finally we use that the full transcript of all messages sent and received is used tocompute the Finished messages, and that Finished messages are computed byevaluating a truly random function that is only accessible to πs∗

i∗ and (possibly) π t∗j∗

due to Game 6. This allows to show that any adversary has probability at most 12µ

of making oracle πs∗i∗ accept without having a matching conversation to π t∗

j∗ .

Thus, this game proceeds exactly like the previous game, except that the challengernow aborts if oracle πs∗

i∗ accepts without having a matching conversation to π t∗j∗ .

Thus we have Pr[break(1)7 ] = 0.

The Finishedmessages are computed by evaluating a truly random function Fms,which is only accessible to oracles sharing ms, and the full transcript containing allprevious messages is used to compute the Finishedmessages. If there is no oraclehaving amatching conversation to πs∗

i∗ , the adversary receives no information aboutFms(label3||m1|| · · · ||m12). Therefore we have Pr[break(1)7 ] = 2−µ and

Pr[break(1)6 ]≤ Pr[break(1)7 ]+1

2µ=

12µ

.

Collecting probabilities from Game 0 to Game 7 yields Lemma 4. �


i with ρ = Server that accepts maliciously is at most

εserver ≤ d`(

d`2λ

+ ` · εsig+ εddh+2 · εprf +1

2µ

)where all quantities are defined as stated in Theorem 6.

Proof. Let break(2)δ

be the event that occurs when the first oracle that accepts mali-ciously in the sense of Definition 6.4 with ρ = Server in Game δ .

Game 0.

This game equals the AKE security experiment described in Section 6. Thus, forsome εserver we have

Pr[break(2)0 ] = εserver.


Game 1.

In this gamewe add an abort rule. The challenger aborts, if there exists any oracle πsi

that chooses a randomnonce rC or rS which is not unique.With the same argumentsas in Game 1 from the proof of Lemma 4 we have

Pr[break(2)0 ]≤ Pr[break(2)1 ]+(d`)2

2λ.

Game 2.

This game is identical, except for the following. The challenger guesses two randomindices (i∗,s∗) $← [`]× [d]. If there exists an oracle πs

i that ‘accepts’ maliciously, and(i, j) 6= (i∗, j∗) and πs

i has ρ 6= Server, then the challenger aborts the game. Note thatif the first oracle πs

i that ‘accepts’ maliciously has ρ = Server, then with probability1/(d`)we have (i, j) = (i∗, j∗), and thus

Pr[break(2)1 ] = d` ·Pr[break(2)2 ].

Note that in this game the attacker can only break the security of the protocol,if oracle πs∗

i∗ is the first oracle that ‘accepts’ maliciously and has ρ = Server, asotherwise the game is aborted.

Game 3.

The challenger proceeds as before, but we add an abort rule. We want to makesure that πs∗

i∗ receives as input exactly the Diffie-Hellman value m8 = TC that wasselected by some other uncorrupted oracle.

Technically, we abort and raise event abortsig, if oracle πs∗i∗ ever receives as input

a message m7 = certC indicating intended partner Π = j and message m9 = σC =SignSIG(skC,m1|| . . . , ||m8) such that σC is a valid signature but there exists no oracleπ t

j which has previously output σC. Clearly we have

Pr[break(2)2 ]≤ Pr[break(2)3 ]+Pr[abortsig].

Note that the experiment is aborted, if πs∗i∗ does not acceptmaliciously, due toGame 2.

Thismeans that party Pj must be τ j-corruptedwith τ j =∞ (i.e., not corrupted)whenπs∗

i∗ accepts. To show that Pr[abortsig] ≤ ` · εsig, we construct a signature forger asfollows. The forger receives as input a public key pk∗ and simulates the challengerfor A . It guesses an index φ

$← [`], sets pkφ = pk∗, and generates all long-termpublic/secret keys as before. Then it proceeds as the challenger in Game 3, exceptthat it uses its chosen-message oracle to generate a signature under pkφ whennecessary.

If φ = j, which happens with probability 1/`, then the forger can use the signaturereceived by πs∗

i∗ to break the EUF-CMA security of the signature scheme with suc-cess probability εsig, so Pr[abortsig]/`≤ εsig. Therefore if Pr[abortsig] is not negligible,then εsig is not negligible as well and we have

Pr[break(2)2 ]≤ Pr[break(2)3 ]+ ` · εsig.

Note that in Game 3 oracle πs∗i∗ receives as input a Diffie-Hellman value TC such

that TC was chosen by another oracle, but not by the attacker. Note also that this


oracle is unique, since the signature includes the client nonce rC, which is uniquedue to Game 1. From now on we denote this unique oracle with π t∗

j∗ .

Note also that πs∗i∗ and π t∗

j∗ share a premaster secret pms = T tSC = T tC

S , where TC = gtC

and TS = gtS for random exponents tS and tC chosen by πs∗i∗ and π t∗

j∗ , respectively.

Game 4.

In this game, we replace the premaster secret pms = gtCtS shared by πs∗i∗ and π t∗

j∗

with a random value gr, r $← Zq. The fact that the challenger has full control overthe Diffie-Hellman shares TC and TS exchanged between πs∗

i∗ and π t∗j∗ , due to the

modifications introduced in the previous games, provides us with the leverage toprove indistinguishability under the Decisional Diffie-Hellman assumption.

Technically, the challenger in Game 4 proceeds as before, but when πs∗i∗ and π t∗

j∗

compute the premaster secret as pms = gtCtS , the challenger replaces this value witha uniformly random value pms = gr,r $← Z∗p, which is in the following used by bothpartner oracles.

Suppose there exists an algorithm distinguishing Game 4 from Game 3. Then wecan construct an algorithm B solving the DDH problem as follows. Algorithm Breceives as input a DDH challenge (g,gu,gv,gw). The challenger defines TC := gu andTS := gv for the Diffie-Hellman shares chosen by πs∗

i∗ and π t∗j∗ , respectively. Instead

of computing the Diffie-Hellman key as in Game 3, it sets pms = gw both for the‘client’ and the ‘server’ oracle. Now if w = uv, then this game proceeds exactly likeGame 3, while if w is random than this game proceeds exactly like Game 4. TheDDH assumption therefore implies that

Pr[break(2)3 ]≤ Pr[break(2)4 ]+ εddh.

Note that in Game 4 the premaster secret of πs∗i∗ and π t∗

j∗ is uniformly random, andindependent of TC and TS. This will provide us with the leverage to replace thefunction PRF(pms, ·)with a truly random function in the next game.

Game 5.

In Game 5 we make use of the fact that the premaster secret pms of πs∗i∗ and π t∗

j∗

is chosen uniformly random, and independent of TC and TS. We thus replace thevalue ms = PRF(pms, label1||rC||rS)with a random value ms.


Pr[break(2)4 ]≤ Pr[break(2)5 ]+ εprf .

Game 6.

In this game we replace the function PRF(ms, ·) used by πs∗i∗ and π t∗

j∗ with a randomfunction. Of course the same random function is used for both oracles πs∗

i∗ andπ t∗

j∗ . In particular, this function is used to compute the Finishedmessages by bothpartner oracles.


Distinguishing Game 6 from Game 5 again implies an algorithm breaking thesecurity of the pseudo-random function PRF, thus

Pr[break(2)5 ]≤ Pr[break(2)6 ]+ εprf .

Game 7.

Finally we use that the full transcript of all messages sent and received is usedto compute the Finished messages, and that Finished messages are computedby evaluating a truly random function that is only accessible to πs∗

i∗ and π t∗j∗ due

to Game 6. This allows to show that any adversary has probability at most 12µ of

making oracle πs∗i∗ accept without having a matching conversation to π t∗

j∗ .

Thus, this game proceeds exactly like the previous game, except that the challengernow aborts if oracle πs∗

i∗ accepts without having a matching conversation to π t∗j∗ .

Therefore we have Pr[break(1)7 ] = 0.

The Finishedmessages are computed by evaluating a truly random function Fms,which is only accessible to oracles sharing ms, and the full transcript containing allprevious messages is used to compute the Finishedmessages. If there is no oraclehaving amatching conversation to πs∗

i∗ , the adversary receives no information aboutFms(label3||m1|| · · · ||m10). Thus we have

Pr[break(1)6 ]≤ Pr[break(1)7 ]+1

2µ=

12µ

.

Collecting probabilities from Game 0 to Game 7 yields Lemma 5. �

9.4.2 Indistinguishability of Keys

Lemma 6. For any adversary A running in time t ′ ≈ t, the probability that A answersthe Test-challenge correctly is at most 1/2+ εke with

εke ≤ εclient+ εserver+d` · (εddh+2 · εprf) .

where εclient+ εserver is an upper bound on the probability that there exists an oracle thataccepts maliciously in the sense of Definition 6.4 (cf. Lemmas 4 and 5) and all other quan-tities are defined as stated in Theorem 6.

Proof. Assume without loss of generality that the A always asks a Test-querysuch that all conditions in Property 2 of Definition 6.4 are satisfied. Let break(3)

δ

denote the event that b′ = b in Game δ , where b is the random bit sampled bythe Test-query, and b′ is either the bit output by A or (if A does not output a bit)chosen by the challenger. Let Advδ := Pr[break(3)

δ]−1/2 denote the advantage of A

in Game δ . Consider the following sequence of games.

Game 0.

This game equals the AKE security experiment described in Section 6. For someεke we have

Pr[break(3)0 ] =12+ εke =

12+Adv0.


Game 1.

The challenger in this game proceeds as before, but it aborts and chooses b′ uni-formly random, if there exists any oracle that accepts maliciously in the sense ofDefinition 6.4. Thus we have

Adv0 ≤ Adv1 + εclient+ εserver,

where εclient+εserver is an upper bound on the probability that there exists an oraclethat accepts maliciously in the sense of Definition 6.4 (cf. Lemmas 4 and 5).

Recall that we assume that A always asks a Test-query such that all conditionsin Property 2 of Definition 6.4 are satisfied. In particular it asks a Test-query toan oracle πs

i that ‘accepts’ after the τ0-th query of A with intended partner Π = j,such that Pj is τ j-corrupted with τ j > τ0. Note that in Game 1 for any such oracle πs

ithere exists a unique ‘partner oracle’ π t

j such that πsi has a matching conversation

to π tj, as the game is aborted otherwise.

Game 2.

The challenger in this game proceeds as before, but in addition guesses indices(i∗,s∗) $← [`]× [d]. It aborts and chooses b′ at random, if the attacker issues aTest(πs

i )-query with (i, j) 6= (i∗,s∗). With probability 1/(d`) we have (i, j) = (i∗,s∗), andthus

Adv1 ≤ d` ·Adv2.

Note that in Game 2 we know that A will issue a Test-query to oracle πs∗i∗ . Note

also that πs∗i∗ has a unique ‘partner’ due to Game 1. In the sequel we denote with

π t∗j∗ the unique oracle such that πs∗

i∗ has a matching conversation to π t∗j∗ , and say that

π t∗j∗ is the partner of πs∗

i∗ .

Game 3.

Let Ti∗,s∗ = gu denote the Diffie-Hellman share chosen by πs∗i∗ , and let Tj∗,t∗ = gv

denote the share chosen by its partner π t∗j∗ . Thus, both oracles compute the premaster

secret as pms = guv.

The challenger in this game proceeds as before, but replaces the premaster secretpms of πs∗

i∗ and π t∗j∗ with a random group element pms = gw, w $← Zq. Note that both

gu and gv are chosen by oracles πs∗i∗ and π t∗

j∗ , respectively, as otherwise πs∗i∗ would

not have a matching conversation to π t∗j∗ and the game would be aborted.

Suppose that there exists an algorithm A distinguishing Game 3 from Game 2.Then we can construct an algorithm B solving the DDH problem as follows. Breceives as input (g,gu,gv,gw). It implements the challenger for A as in Game 2,except that it sets Ti∗,s∗ := gu and Tj∗,t∗ := gv, and the premaster secret of πs∗

i∗ and π t∗j∗

equal to pms := gw. Note that B can simulate all messages exchanged between πs∗i∗

and π t∗j∗ properly, in particular the finished messages using knowledge of pms = gw.

Since all other oracles are not modified, B can simulate these oracles properly aswell.

If w = uv, then the view of A when interacting with B is identical to Game 2, whileif w $← Zq then it is identical to Game 3. Thus, the DDH assumption implies that

Adv2 ≤ Adv3 + εddh.


Game 4.

In Game 4 we make use of the fact that the premaster secret pms of πs∗i∗ and π t∗

j∗ ischosen uniformly random. We thus replace the value ms = PRF(pms, label1||rC||rS)with a random value ms.


Adv3 ≤ Adv4 + εprf .

Game 5.

In this game we replace the function PRF(ms, ·) used by πs∗i∗ and π t∗

j∗ with a randomfunction Fms. Of course the same random function is used for both oracles πs∗

i∗ andπ t∗

j∗ . In particular, this function is used to compute the key material as

KC→Senc ||KS→C


mac := Fms(label2||rC||rS)

Distinguishing Game 5 from Game 4 again implies an algorithm breaking thesecurity of the pseudo-random function PRF. Moreover, in Game 5 the adversa-ry always receives a random key in response to a Test-query, thus receives noinformation about b′, which implies Adv5 = 0 and

Adv4 ≤ Adv5 + εprf = εprf .

Collecting probabilities from Game 0 to Game 5 yields Lemma 6. �Summing up probabilities from Lemmas 4 to 6, we obtain that

εttls ≤ εclient+ εserver+ εke

≤ 2 · (εclient+ εserver)+d` · (εddh+2 · εprf)≤ 4 ·max{εclient,εserver}+d` · (εddh+2 · εprf)

≤ 4 ·d`(

d`2λ

+ ` · εsig+ εddh+2 · εprf +d`(

εprfodh+ εprf +1

2µ

))+d` · (εddh+2 · εprf)

= 4 ·d`(

d`2λ


52· ·εprf +d`

(εprfodh+ εprf +

12µ

)),

which yields Theorem 6.

9.5 Truncated TLS with Static Diffie-Hellman is a Secure AKEProtocol

JS: Short summary on results (Not Paterson etal !)

9.6 Truncated TLS with RSA Key Transport is a Secure AKEProtocol

JS: Short summary on results (Not Paterson etal !)

Studienbrief 10 Authenticated and Confidential Channel Establishment (ACCE) Seite 85

Studienbrief 10 Authenticated and Confidential ChannelEstablishment (ACCE)



10.3 Related Work


10.4 Introduction to ACCE Protocols

An authenticated and confidential channel establishment (ACCE) protocol is a protocolexecuted between two parties. The protocol consists of two phases, called the‘pre-accept’ phase and the ’post-accept’ phase.

Pre-accept phase. In this phase a ‘handshake protocol’ is executed. In terms offunctionality this protocol is an AKE protocol as in Section 6, that is, bothcommunication partners are mutually authenticated, and a session key k isestablished. However, it need not necessarily meet the security definition forAKE protocols (Definition 6.4). This phase ends, when both communicationpartners reach an accept-state (i.e. Λ = ‘accept’).

Post-accept phase. This phase is entered, when both communication partnersreach an accept-state. In this phase data can be transmitted, encrypted andauthenticated with key k.

The prime example for an ACCE protocol is TLS. Here, the pre-accept phaseconsists of the TLS Handshake protocol. In the post-accept phase encrypted andauthenticated data is transmitted over the TLS Record Layer.

To define security of ACCE protocols, we combine the security model for authenti-cated key exchange from Section 6.4 with stateful length-hiding encryption in thesense of [25]. Technically, we provide a slightly modified execution environmentthat extends the types of queries an adversary may issue.

10.5 Execution environment

The execution environment is very similar to the model from Section 6.4, except fora few simple modifications. We extend themodel such that in the post-accept phasean adversary is also able to ‘inject’ chosen-plaintexts by making an Encrypt-query,1and chosen-ciphertexts by making a Decrypt-query. Moreover, each oracle πs

i keepsas additional internal state a bit bs

i$←{0,1}, chosen at random at the beginning of

the game, two counters u and v required for the security definition, and two statevariables ste and std for encryption and decryption with a stateful symmetric cipher.In the sequel we will furthermore assume that the key k consists of two differentkeys k = (kρ

enc,kρ

dec) for encryption and decryption. Their order depends on the roleρ ∈ {Client,Server} of oracle πs

i . This is the case for TLS (see Section 8).

An adversary may interact with the provided oracles by issuing the followingqueries.

1 This models that an adversary may trick one party into sending some adversarially chosen data.A practical example for this attack scenario are cross-site request forgeries [30] on web servers, orBard’s chosen-plaintext attacks on SSL3.0 [2, 3].

Seite 86 Studienbrief 10 Authenticated and Confidential Channel Establishment (ACCE)

• Sendpre(πsi ,m): This query is identical to the Send-query in the AKE model

from Section 6.4, except that it replies with an error symbol ⊥ if oracle πsi

has state Λ = ‘accept’. (Send-queries in an accept-state are handled by theDecrypt-query below).

• Reveal(πsi ) and Corrupt(Pi): These queries are identical to the corresponding

queries in the AKE model from Section 6.4.

• Encrypt(πsi ,m0,m1, len,H): This query takes as input twomessages m0 and m1,

length parameter len, and header data H. If Λ 6= ‘accept’ then πsi returns ⊥.

Otherwise, it proceeds as depicted in Figure 10.1, depending on the randombit bs

i$←{0,1} sampled by πs

i at the beginning of the game and the internalstate variables of πs

i .

• Decrypt(πsi ,C,H): This query takes as input a ciphertextC and header data H.

If πsi has Λ 6= ‘accept’ then πs

i returns ⊥. Otherwise, it proceeds as depictedin Figure 10.1.

Abb. 10.1: Encrypt andDecrypt oracles in the AC-CE security experiment.

Encrypt(πsi ,m0,m1, len,H): Decrypt(πs

i ,C,H):u := u+1 v := v+1(C(0),st(0)e )

$← EncStE(kρenc, len,H,m0,ste) If bs

i = 0, then return ⊥(C(1),st(1)e )

$← EncStE(kρenc, len,H,m1,ste) (m,std) = DecStE(k

ρ

dec,H,C,std)If C(0) =⊥ or C(1) =⊥ then return ⊥ If v > u or C 6=Cv, then phase := 1

(Cu,ste) := (C(bsi ),st(b

si )

e ) If phase= 1 then return mReturn Cu

Here u,v,bsi ,ρ,k

ρenc,k

ρ

dec denote the values stored in the correspondinginternal variables of πs

i .

10.6 Security Definition

Security of ACCE protocols is defined by requiring that (i) the protocol is a secureauthentication protocol and (ii) in the post-accept phase all data is transmittedover an authenticated and confidential channel in the sense of Definition 3.4.

Again this notion is captured by a game, played between an adversary A and achallengerC . The challenger implements the collection of oracles {πs

i : i∈ [`],s∈ [d]}.At the beginning of the game, the challenger generates ` long-term key pairs(pki,ski) for all i ∈ [`]. The adversary receives the public keys pk1, . . . , pk` as input.

10.7 Relation to the AKE Security Definition from Section 6 Seite 87

Now the adversary may start issuing Send, Reveal, Corrupt, Encrypt, and Decryptqueries. Finally, the adversary outputs a triple (i,s,b′) and terminates.

DDefinition 10.1

We say that an adversary (t,ε)-breaks an ACCE protocol, if A runs in time t,and at least one of the following two conditions holds:


i such that• πs

i ‘accepts’ when A issues its τ0-th query with partner Π = j,and

• Pj is τ j-corrupted with τ0 < τ j, and



j.If an oracle πs

i accept in the above sense, then we say that πsi accepts

maliciously.

2. When A terminates and outputs a triple (i,s,b′) such that• πs

i ‘accepts’ when A issues its τ0-th query with intended part-ner Π = j, and Pj is τ j-corrupted with τ0 < τ j,

• A did not issue a Reveal-query to πsi , nor to π t

j such that πsi has

a matching conversation to π tj (if such an oracle exists), and

then the probability that b′ equals bsi is bounded by∣∣Pr[bs

i = b′]−1/2∣∣≤ ε.

If an adversary A outputs (i,s,b′) such that b′ = bsi and the above

conditions are met, then we say that A anwers the encryption-challengecorrectly.

We say that an ACCE protocol is (t,ε)-secure, if there exists no adversary that(t,ε)-breaks it.

Remark 6. Note that the above definition even allows to corrupt the oracle πsi whose

internal secret bit the attacker tries to determine. Of course this is only allowed afterπs

i has reached an accept-state, in order to exclude trivial attacks. Thus, protocolssecure with respect to this definition provide perfect forward secrecy. Note alsothat again we allow the ‘accepting’ oracle to be corrupted even before it reaches anaccept-state, which provides security against key-compromise impersonation attacks.

10.7 Relation to the AKE Security Definition from Section 6

Note that an ACCE protocol can be constructed in a two-step approach.

1. (AKE part) First an authenticated key-exchange (AKE) protocol is executed.This protocol guarantees the authenticity of the communication partner, andprovides a cryptographically ‘good’ (i.e., for the attacker indistinguishablefrom random) session key.

2. (Symmetric part) The session key is then used in a symmetric encryptionscheme providing integrity and confidentiality.

This modular approach is simple and generic, and therefore appealing. It can beshown formally that this two-step approach yields a secure ACCE protocol, if the‘AKE part’ meets the security in the sense of Definition 6.4, and the ‘symmetric

Seite 88 Studienbrief 10 Authenticated and Confidential Channel Establishment (ACCE)

part’ consists of a suitable authenticated symmetric encryption scheme (e.g. secureaccording to Definition 3.4).

However, if the purpose of the protocol is the establishment of an authenticatedconfidential channel, then it is not necessary that the ‘AKE-part’ of the protocolprovides full indistinguishability of session keys. It actually would suffice if en-crypted messages are indistinguishable, and cannot be altered by an adversary. Theserequirements are strictly weaker than indistinguishability of keys in the sense of De-finition 6.4, and thus easier to achieve (possibly fromweaker hardness assumptions,or by more efficient protocols).

We stress that our ACCE definition is mainly motivated by the fact that securitymodels based on key indistinguishability do not allow for a security analysis offull TLS, as detailed in the introduction. We do not want to propose ACCE as anew security notion for key exchange protocols, since it is very complex and themodular two-step approach approach seems more useful in general.

10.8 Generic Constructions for ACCE Protocols

JS: Research!

Studienbrief 11 Transport Layer Security (TLS) is a Secure ACCE Protocol Seite 89

Studienbrief 11 Transport Layer Security (TLS) is a SecureACCE Protocol



11.3 Related Work


11.4 TLS with Ephemeral Diffie-Hellman is a Secure ACCEProtocol

Theorem 7. Let µ be the output length ofPRF and let λ be the length of the nonces rC andrS. Assume that the pseudo-random function PRF is (t,εprf)-secure, the signature schemeis (t,εsig)-secure, the DDH-problem is (t,εddh)-hard in the group G used to compute theTLS premaster secret, and the PRF-ODH-problem is (t,εprfodh)-hard with respect to G andPRF. Suppose that the stateful symmetric encryption scheme is (t,εsLHAE)-secure.

Then for any adversary that (t ′,εtls)-breaks the ephemeral Diffie-Hellman TLS protocol inthe sense of Definition 10.1 with t ≈ t ′ holds that

εtls ≤ 4 ·d`(

d`2λ


52· εprf +

14· εsLHAE+d`

(εprfodh+ εprf +

12µ

)).

To prove Theorem 7, we divide the set of all adversaries into two categories:

1. Adversaries that succeed in making an oracle accept maliciously. We callsuch an adversary an authentication-adversary.

2. Adversaries that do not succeed in making any oracle accept maliciously,but which answer the encryption-challenge. We call such an adversary anencryption-adversary.

We prove Theorem 6 by two lemmas. Lemma 7 bounds the probability εclient thatan authentication-adversary succeeds, Lemma 8 bounds the probability εenc thatan encryption-adversary succeeds. Then we have

εtls ≤ εauth+ εenc.

We prove Theorem 7 via the following lemmas.


i that accepts maliciously is at most

εauth ≤ 2 ·d`(

d`2λ


εprfodh+ εprf +1

2µ

))where all quantities are defined as stated in Theorem 7.

Note that εauth ≤ εclient+ εserver, where εclient is an upper bound on the probabilitythat there exists an oracle with ρ = Client that accepts maliciously in the sense of

Seite 90 Studienbrief 11 Transport Layer Security (TLS) is a Secure ACCE Protocol

Definition 10.1, and εserver is an upper bound on the probability that there exists anoracle with ρ = Client that accepts maliciously. We claim that

εclient ≤ d`(

d`2λ

+ ` · εsig+d`(

εprfodh+ εprf +1

2µ

))εserver ≤ d`

(d`2λ

+ ` · εsig+ εddh+2 · εprf +1

2µ

)and thus

εauth ≤ εclient+ εserver ≤ 2 ·d`(

d`2λ


εprfodh+ εprf +1

2µ

)).

The bounds on εclient and εserver are derived exactly like in the proofs of Lemma 4and Lemma 5, therefore we omit the details.

Lemma 8. For any adversary A running in time t ′ ≈ t, the probability that A anwersthe encryption-challenge correctly is at most 1/2+ ε with

εenc ≤ εauth+d`(εddh+2 · εprf + εsLHAE) .

where εauth is an upper bound on the probability that there exists an oracle that acceptsmaliciously in the sense of Definition 10.1 (cf. Lemma 7) and all other quantities are definedas stated in Theorem 7.

The proof of this lemma extends the proof of Lemma 6 by one game-hop thatexploits the sLHAE-security of the encryption scheme.

Proof. Assume without loss of generality that the A always outputs (i,s,b′) suchthat all conditions in Property 2 of Definition 10.1 are satisfied. Let break(4)

δdenote

the event that b′ = b in Game δ , where b is the random bit sampled by the Test-query, and b′ is either the bit output by A or (if A does not output a bit) chosen bythe challenger. Let Advδ := Pr[break(4)

δ]−1/2 denote the advantage of A in Game δ .

Consider the following sequence of games.

Game 0.

This game equals the ACCE security experiment described in Section 6. For someεenc we have

Pr[break(3)0 ] =12+ εenc =

12+Adv0.

Game 1.

The challenger in this game proceeds as before, but it aborts and chooses b′ uni-formly random, if there exists any oracle that accepts maliciously in the sense ofDefinition 10.1. Thus we have

Adv0 ≤ Adv1 + εauth,

where εauth an upper bound on the probability that there exists an oracle thataccepts maliciously in the sense of Definition 10.1 (cf. Lemma 7).

Recall that we assume that A always outputs (i,s,b′) such that all conditions inProperty 2 of Definition 10.1 are satisfied. In particular it outputs (i,s,b′) suchthat πs

i ‘accepts’ after the τ0-th query of A with intended partner Π = j, and Pj isτ j-corrupted with τ j > τ0. Note that in Game 1 for any such oracle πs

i there exists a

11.4 TLS with Ephemeral Diffie-Hellman is a Secure ACCE Protocol Seite 91

unique ‘partner oracle’ π tj such that πs

i has a matching conversation to π tj, as the

game is aborted otherwise.

Game 2.

The challenger in this game proceeds as before, but in addition guesses indices(i∗,s∗) $← [`]× [d]. It aborts and chooses b′ at random, if the attacker outputs (i,s,b′)with (i, j) 6= (i∗,s∗). With probability 1/(d`)we have (i, j) = (i∗,s∗), and thus

Adv1 ≤ d` ·Adv2.

Note that in Game 2 we know that A will output (i∗,s∗,b′). Note also that πs∗i∗ has a

unique ‘partner’ due to Game 1. In the sequel we denote with π t∗j∗ the unique oracle

such that πs∗i∗ has a matching conversation to π t∗

j∗ , and say that π t∗j∗ is the partner of

πs∗i∗ .

Game 3.

The challenger in this game proceeds as before, but replaces the premaster secretpms of πs∗

i∗ and π t∗j∗ with a random group element pms = gw, w $← Zq. Note that both

gu and gv are chosen by oracles πs∗i∗ and π t∗

j∗ , respectively, as otherwise πs∗i∗ would

not have a matching conversation to π t∗j∗ and the game would be aborted.

With the same arguments as in Game 3 in the proof of Lemma 6, we have

Adv2 ≤ Adv3 + εddh.

Game 4.

As in Game 4 in the proof of Lemma 6, we now make use of the fact that thepremaster secret pms of πs∗

i∗ and π t∗j∗ is chosen uniformly random. We thus replace

the value ms = PRF(pms, label1||rC||rS)with a random value ms.



Game 5.

As in Game 5 in the proof of Lemma 6, we replace the function PRF(ms, ·) used byπs∗

i∗ and π t∗j∗ with a random function Fms. Of course the same random function is

used for both oracles πs∗i∗ and π t∗

j∗ . In particular, this function is used to computethe key material as

KC→Senc ||KS→C


mac := Fms(label2||rC||rS)

Distinguishing Game 5 from Game 4 again implies an algorithm breaking thesecurity of the pseudo-random function PRF, thus we have



Note that in Game 5 the key material KC→Senc ||KS→C


mac of oracles πs∗i∗ and

π t∗j∗ is uniformly random and independent of all TLS Handshake messages exchan-

ged in the pre-accept phase.

Game 6.

Now we use that the key material KC→Senc ||KS→C


mac used by πs∗i∗ and π t∗

j∗ inthe stateful symmetric encryption scheme uniformly at random and independentof all TLS Handshake messages.

In this game we construct a simulator B that uses a successful ACCE attacker A tobreak the security of the underlying sLHAE secure symmetric encryption scheme(Definition 3.4). By assumption, the simulator B is given access to an encryptionoracle Encrypt and a decryption oracle Decrypt. B embeds the sLHAE experimentby simply forwarding all Encrypt(πs∗

i∗ , ·) queries to Encrypt, and all Decrypt(π t∗j∗ , ·)

queries to Decrypt. Otherwise it proceeds as the challenger in Game 5.

Observe that the values generated in this game are exactly distributed as in theprevious game. We thus have

Adv5 = Adv6.

If A outputs a triple (i∗,s∗,b′), then B forwards b′ to the sLHAE challenger. Other-wise it outputs a random bit. Since the simulator essentially relays all messages itis easy to see that an attacker A having advantage ε ′ yields an attacker B againstthe sLHAE security of the encryption scheme with success probability at least1/2+ ε ′.

Since by assumption any attacker has advantage at most εsLHAE in breaking thesLHAE security of the symmetric encryption scheme, we have

Adv6 ≤ 1/2+ εsLHAE.

�

Addig up probabilities from Lemmas 7 and 8, we obtain that

εtls ≤ εauth+ εenc

≤ 2 · εauth+d`(εddh+2 · εprf + εsLHAE)

≤ 4 ·d`(

d`2λ


52· εprf +

14· εsLHAE+d`

(εprfodh+ εprf +

12µ

))which yields Theorem 7.

11.5 On Proving Security of TLS-DHE from StandardAssumptions

In this section we illustrate why we had to make the PRF-ODH-assumption in theproofs of Lemmas 4 and 7, and why we can prove Lemma 5 based on the standardDDH assumption. In order to allow a comprehensive exposition, let us consider thesimplified protocol from Figure 11.1 which abstracts the TLS-DHE Handshake.

Let us start with an informal description of the issue. Suppose we are given a Client-adversary, that is, an adversary which always makes Client-oracle C := πs

i (i.e., aparticular oracle πs

i with ρ =Client) accept maliciously with intended partner Π= S.Suppose we want to argue that the adversary is not able to forge the finS-message

11.5 On Proving Security of TLS-DHE from Standard Assumptions Seite 93

Client C Server S

rC$← {0,1}λ

−−m1 := rC

−−−−−−−−−−−−→rS

$← {0,1}λ


σS :=SignSIG(skS,(rC,rS,TS))

←−m2 := (rS,TS,σS)−−−−−−−−−−−−−


ms := PRF(T tCS mod

p, label1||rC||rS)f inC :=

PRF(ms,m1||m2||(TC,σC))σC :=

SignSIG(skS,(rC,rS,TS,TC))

−m3 := (TC,σC, f inC)−−−−−−−−−−−−−−−→

ms := PRF(T tSC mod

p, label1||rC||rS)f inS :=

PRF(ms,m1|| . . . ||m3)

←−−m4 := f inS−−−−−−−−−−−−

Abb. 11.1: Abstraction ofthe TLS-DHE handshake

received by C (which we would have to, since the finS-message is the only messagethat cryptographically protects all messages previously received by πs

i , and thusis required to ensure that πs

i has a matching conversation), and that we want toassume only that the PRF is secure in the standard sense (Definition 3.1). Then atsome point in the proof we would have to replace the premaster secret computedby πs

i as pms = T tCS = gtCtS with an independent random value.

Note that in order to replace pms with a random value and argue in the proofwith indistinguishability, we must not know any of the exponents tC and tS inTC = gtC and TS = gtS , as otherwise we can trivially distinguish the real pms = gtCtS

from a random pms′. The problematic property of TLS-DHE is, that an adversarymay test whether the challenger ‘knows’ tS, and then make Client-oracle πs

i acceptmaliciously only if this holds. This works as follows.

1. The adversary establishes a communication between two oracles πsi (repre-

senting the clientC) and π tj (representing the server S) by simply forwarding

the messages m1 and m2 between C and S.

2. The C will respond with m3 = (TC,σC,finC). This message is not forwarded.

3. Instead, the adversary corrupts some party P∗ 6∈ {Pi,Pj}, and obtains thesecret key sk∗ of this party. Then it computes

a) T ∗ := gt∗ mod p for random t∗ $← Zq,

b) σ∗ := SignSIG(sk∗;(rC,rS,TS,T ∗)) using the corrupted key sk∗,

c) ms∗ := PRF(T t∗S , label1||rC||rS) using knowledge of t∗, and

d) fin∗C := PRF(ms∗,m1||m2||(T ∗,σ∗)).and sends m∗3 := (T ∗,σ∗,fin∗C) to S. Note that S cannot determine that its


communication partner has changed, because any messages previouslyreceived by S were perfectly anonymous.

4. If S responds with a correct fin∗S message (note that the adversary is able tocompute all keys, in particular pms∗ := T t∗

S , since it ‘knows’ t∗, and thus is ableto verify the validity of fin∗S), then adversary concludes that the challenger‘knows’ tS and forges the required finS-message to make πs

i accept withoutmatching conversations. Otherwise the adversary aborts.

Note that the above adversary is a valid, successful adversary in the real securityexperiment. It does not issue any Reveal-query and only one Corrupt-query to anunrelated party, such that the intended communication partner Π = S of C = πs

iremains uncorrupted, but still it makes C = πs

i ‘accept’ and there is no oracle thatC has a matching conversation to.

However, we will not be able to use this adversary in a simulated security experi-ment where the challenger does not know the exponent tS of TS = gtS . Intuitively, thereason is that in this case the challenger would first have to compute the Finished-message fin∗S, where

fin∗S = PRF(ms,m1|| . . . ||m3) and ms = PRF(T t∗S , label1||rC||rS),

but ‘knowing’ neither tS = logTS, nor t∗ = logT ∗. This is the technical problem weare faced with, if we want to prove security under a standard assumption likeDDH. Under the PRF-ODH-assumption, we can however use the given oracle tocompute first ms, and from this the Finished-message fin∗S.

Server-adversaries. Interestingly, the above technical problem does not appear ifwe consider Server-adversaries (i.e., adversaries that make an oracle πs

i accept mali-ciously with ρ = Server) instead of Client-adversaries. This is due to the asymmetryof the TLS-DHE Handshake protocol. The reason is, that in this case the adversaryis not allowed to corrupt the intended partner of the server (in order to excludetrivial attacks), and is therefore not able to inject an adversarially-chosen Diffie-Hellman share T ∗. Note here that the signature sent from the client to the serveris computed over both Diffie-Hellman shares received and chosen by the client.Therefore in this case the server is able to verify whether its intended partner hasreceived the correct Diffie-Hellman share, and thus the standard DDH assumptionis sufficient to prove security.

Disallowing corruptions. One possibility to circumvent the above problem, andthus to avoid the PRF-ODH-assumption, is to consider a weaker security model. Ifwe disallow Corrupt-queries in the model, then the adversary will not be able toinject an adversarially-chosen, validly signed Diffie-Hellman share. This preventsthe above ‘test’ and again allows a proof under the DDH assumption. However, asecurity model without corruptions is rather weak. Albeit it may be reasonable forcertain applications, it is certainly not adequate for the way how TLS-DHE is usedon the Internet.

Adopting Σ0 to TLS. In [9] Canetti and Krawczyk describe a protocol called Σ0,which exhibits many similarities to the TLS-DHE Handshake protocol and thesimplified protocol from Figure 11.1, but is provably secure under standard ass-umptions (in particular under DDH instead of PRF-ODH). Let us discuss why thedifferences between Σ0 and TLS-DHE, albeit subtle, are crucial.

In Figure 11.2 we describe a simple variant Σ of Σ0, which essentially extends Σ0with a server nonce rS and replaces the MAC computed over identities in Σ0 with

11.5 On Proving Security of TLS-DHE from Standard Assumptions Seite 95

a MAC (implemented with PRF) computed over all previous protocol messages.Note that thesemessages include the identities, so the security analysis of Σ0 carriesover to Σ.

Client C Server S

rC$← {0,1}λ


−−m1 := (rC,TC)−−−−−−−−−−−−→

rS$← {0,1}λ


σS :=SignSIG(skS,(rC,rS,TC,TS))

ms := PRF(T tSC mod

p, label1||rC||rS)finS :=

PRF(ms,m1|| . . . ||m3)

←−m2 := (rS,TS,σS,finS)−−−−−−−−−−−−−−−−

ms := PRF(T tCS mod

p, label1||rC||rS)finC :=

PRF(ms,m1||m2||(TC,σC))σC :=

SignSIG(skS,(rC,rS,TS,TC))

−m3 := (TC,σC,finC)−−−−−−−−−−−−−−−→

Abb. 11.2: Provably secu-re TLS-DHE Adopting Σ0variant, adopted to theclient/server setting andour notation.

The major difference between Σ0 and TLS-DHE is, that the client ‘accepts’ alreadyafter receiving m2. There is no message m4 sent from the server to the client (whichthus need not be simulated in a security experiment). This m4-message is notrequired in Σ0, since the client Diffie-Hellman share gc is sent already in messagem1 (before m2!), and thus finS can be contained in m2.

We stress that one could make TLS-DHE provably secure under DDH by makingit more similar to Σ0:

1. Include the client Diffie-Hellman share gc in• the first message m1 of TLS-DHE and

• in the signature sent from client to server.

2. Include all data in m4 of TLS-DHE into message m2 of TLS-DHE, and omitm4.

This modification would allow to carry the security analysis of Σ0 from [9] overto TLS-DHE, and thus allow a security proof under DDH instead of PRF-ODH(and the additional standard assumptions on the security of the PRF, the signaturescheme, and (considering full TLS-DHE) the stateful encryption scheme).

This would of course require changes to the TLS-DHE protocol, and may there-fore be unrealistic. This section should therefore merely be seen as an additionaldiscussion of the issue analysed in this section.


Including identities in the client nonce. Another way (the ‘engineering-approach’)to circumvent the problem, and thus allow a proof under the DDH assumptioninstead of PRF-ODH, is to modify TLS such that the client C is able to verify thatthe server has indeed intended partner C, and not some third party C′. Note thatthe client nonce rC is included in both signatures, in particular in the signature σSsent from the server to the client. According to [12, 13, 14] the nonce rC consistsof 28 random bytes (=224 bits). The only requirement on the nonces in the proofis that a collision occurs with sufficiently small probability, for which 160 bitsshould be sufficient in practice. One could use the remaining 64 bits to encodean ‘identity’ that refers uniquely to the client certificate. The server would haveto check whether this identity matches the received client certificate. This would,again, require changes to the TLS-DHE protocol, and may therefore be unrealistic,even though these changes are minimal.

11.6 TLS with Static Diffie-Hellman or RSA Key Transport is aSecure ACCE Protocol

JS: Short Summary of the Paterson etal paper!

Verzeichnisse Seite 97

Verzeichnisse

I. Abbildungen

Abb. 2.1: Turing Machine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15Abb. 2.2: Relation between classes P and NP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20Abb. 2.3: Relationship between classes P and NP and NP-Completeness. . . . . . . . . . . . . . . . . . 21Abb. 3.1: Encrypt and Decrypt oracles in the stateful LHAE security experiment. . . . . . . . . . . . . . 27Abb. 4.1: Mechanical Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31Abb. 4.2: Shamir’s No-Key Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32Abb. 4.3: Diffie-Hellman key establishment protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Abb. 4.4: Security Game for Diffie-Hellman Key Exchange . . . . . . . . . . . . . . . . . . . . . . . . . 34Abb. 4.5: ElGamal Encryption protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Abb. 4.6: The RSA-KEM Key Transport Algorithm according to RFC 5990 . . . . . . . . . . . . . . . . . 38Abb. 4.7: Challenge-Response Authentication protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Abb. 4.8: Possible attack to Challenge-Response protocol . . . . . . . . . . . . . . . . . . . . . . . . . 39Abb. 4.9: Encrypted Nonce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39Abb. 4.10: Signatur bietet Schutz gegen klassischen MitM Angriff . . . . . . . . . . . . . . . . . . . . . 39Abb. 4.11: TLS Protokoll mit DHE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Abb. 4.12: Secure Shell Protokoll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Abb. 5.1: Fiat-Shamir Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44Abb. 5.2: Quadratic Remainder Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44Abb. 6.1: The MAP1 protocol from [5]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51Abb. 6.2: The MAP2 protocol from [5]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54Abb. 6.3: The AKEP1 protocol from [5]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54Abb. 7.1: Signed Diffie Hellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61Abb. 7.2: The HMQV protocol from []. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62Abb. 7.3: The NAXOS protocol from [22]. Please note that we have modified the protocol slightly by

adding the identities of sender and recipient to each message. This does not change thesecurity of the protocol, but makes definitions and proofs clearer. . . . . . . . . . . . . . . . 64

Abb. 8.1: TLS handshake for ciphersuites TLS_DHE_* with client authentication . . . . . . . . . . . . . 71Abb. 8.2: Computation of Client/Server Handshake Messages . . . . . . . . . . . . . . . . . . . . . . . 74Abb. 10.1: Encrypt and Decrypt oracles in the ACCE security experiment. . . . . . . . . . . . . . . . . . 86Abb. 11.1: Abstraction of the TLS-DHE handshake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93Abb. 11.2: Provably secure TLS-DHE Adopting Σ0 variant, adopted to the client/server setting and our

notation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

II. Beispiele

Beispiel 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14Beispiel 6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

III. Definitionen

Definition 2.1: Turing Machine [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15Definition 2.2: Configuration of a Turing Machine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16Definition 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16Definition 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19Definition 2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19Definition 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19Definition 2.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20Definition 2.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20Definition 2.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Definition 2.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22Definition 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24Definition 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Seite 98 Verzeichnisse

Definition 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26Definition 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26Definition 3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27Definition 3.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28Definition 3.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28Definition 3.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Definition 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Definition 6.1: Matching conversations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47Definition 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Definition 6.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49Definition 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50Definition 10.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

IV. Kontrollaufgaben

Kontrollaufgabe 6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Kontrollaufgabe 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Kontrollaufgabe 6.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47Kontrollaufgabe 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50Kontrollaufgabe 6.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51Kontrollaufgabe 6.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54Kontrollaufgabe 6.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55Kontrollaufgabe 6.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

V. Sätze

Satz 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

VI. Literatur

[1] M. Abdalla, M. Bellare, and P. Rogaway. The oracle Diffie-Hellman assumptions and an analysis of DHIES.In D. Naccache, editor, CT-RSA 2001, volume 2020 of LNCS, pages 143–158. Springer, Apr. 2001.

[2] G. V. Bard. The vulnerability of SSL to chosen plaintext attack. Cryptology ePrint Archive, Report 2004/111,2004. http://eprint.iacr.org/.

[3] G. V. Bard. A challenging but feasible blockwise-adaptive chosen-plaintext attack on SSL. In M. Malek,E. Fernández-Medina, and J. Hernando, editors, SECRYPT, pages 99–109. INSTICC Press, 2006.

[4] M. Bellare, R. Canetti, and H. Krawczyk. Keying hash functions for message authentication. In N. Koblitz,editor, CRYPTO’96, volume 1109 of LNCS, pages 1–15. Springer, Aug. 1996.

[5] M. Bellare and P. Rogaway. Entity authentication and key distribution. In D. R. Stinson, editor, CRYPTO’93,volume 773 of LNCS, pages 232–249. Springer, Aug. 1993.

[6] M. Bellare and P. Rogaway. The security of triple encryption and a framework for code-based game-playingproofs. In S. Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 409–426. Springer, May / June2006.

[7] S. Blake-Wilson, D. Johnson, and A. Menezes. Key agreement protocols and their security analysis. InM. Darnell, editor, 6th IMA International Conference on Cryptography and Coding, volume 1355 of LNCS, pages30–45. Springer, Dec. 1997.

[8] R. Canetti and H. Krawczyk. Analysis of key-exchange protocols and their use for building secure channels.In B. Pfitzmann, editor, EUROCRYPT 2001, volume 2045 of LNCS, pages 453–474. Springer, May 2001.

http://eprint.iacr.org/

Literatur Seite 99

[9] R. Canetti and H. Krawczyk. Security analysis of IKE’s signature-based key-exchange protocol. In M. Yung,editor, CRYPTO 2002, volume 2442 of LNCS, pages 143–161. Springer, Aug. 2002. http://eprint.iacr.org/2002/120/.

[10] C. J. F. Cremers. Session-state reveal is stronger than ephemeral key reveal: Attacking the NAXOS authentica-ted key exchange protocol. In M. Abdalla, D. Pointcheval, P.-A. Fouque, and D. Vergnaud, editors, ACNS 09,volume 5536 of LNCS, pages 20–33. Springer, June 2009.

[11] I. Damgard and J. B. Nielsen. Commitment schemes and zero-knowledge protocols (2008).

[12] T. Dierks and C. Allen. The TLS Protocol Version 1.0. RFC 2246 (Proposed Standard), Jan. 1999. Obsoleted byRFC 4346, updated by RFCs 3546, 5746.

[13] T. Dierks and E. Rescorla. The Transport Layer Security (TLS) Protocol Version 1.1. RFC 4346 (ProposedStandard), Apr. 2006. Obsoleted by RFC 5246, updated by RFCs 4366, 4680, 4681, 5746.

[14] T. Dierks and E. Rescorla. The Transport Layer Security (TLS) Protocol Version 1.2. RFC 5246 (ProposedStandard), Aug. 2008. Updated by RFCs 5746, 5878.

[15] T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In G. R. Blakleyand D. Chaum, editors, CRYPTO’84, volume 196 of LNCS, pages 10–18. Springer, Aug. 1984.

[16] P.-A. Fouque, D. Pointcheval, and S. Zimmer. HMAC is a randomness extractor and applications to TLS. InM. Abe and V. Gligor, editors, ASIACCS 08, pages 21–32. ACM Press, Mar. 2008.

[17] O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions (extended abstract). In 25thFOCS, pages 464–479. IEEE Computer Society Press, Oct. 1984.

[18] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAMJournal on computing, 18(1):186–208, 1989.

[19] J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation.Addison-Wesley, 3rd edition, 2006.

[20] T. Jager, F. Kohlar, S. Schäge, and J. Schwenk. On the security of TLS-DHE in the standard model. InR. Safavi-Naini and R. Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 273–293. Springer, Aug.2012.

[21] H. Krawczyk, K. G. Paterson, and H. Wee. On the security of the TLS protocol: A systematic analysis. InR. Canetti and J. A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 429–448. Springer, Aug.2013.

[22] B. A. LaMacchia, K. Lauter, and A. Mityagin. Stronger security of authenticated key exchange. In W. Susilo,J. K. Liu, and Y. Mu, editors, ProvSec 2007, volume 4784 of LNCS, pages 1–16. Springer, Nov. 2007.

[23] P. Morrissey, N. P. Smart, and B. Warinschi. A modular security analysis of the TLS handshake protocol. InJ. Pieprzyk, editor, ASIACRYPT 2008, volume 5350 of LNCS, pages 55–73. Springer, Dec. 2008.

[24] P. Morrissey, N. P. Smart, and B. Warinschi. The TLS handshake protocol: A modular analysis. Journal ofCryptology, 23(2):187–223, Apr. 2010.

[25] K. G. Paterson, T. Ristenpart, and T. Shrimpton. Tag size does matter: Attacks and proofs for the TLS recordprotocol. In D. H. Lee and X.Wang, editors,ASIACRYPT 2011, volume 7073 of LNCS, pages 372–389. Springer,Dec. 2011.

[26] P. Rogaway. Formalizing human ignorance. In P. Q. Nguyen, editor, Progress in Cryptology - VIETCRYPT 06,volume 4341 of LNCS, pages 211–228. Springer, Sept. 2006.

http://eprint.iacr.org/2002/120/

http://eprint.iacr.org/2002/120/

Seite 100 Verzeichnisse

[27] V. Shoup. Sequences of games: a tool for taming complexity in security proofs. Cryptology ePrint Archive,Report 2004/332, Nov 2004.

[28] A. M. Turing. On computable numbers, with an application to the entscheidungsproblem. a correction.Proceedings of the London Mathematical Society, s2-43(1):544–546, 1938.

[29] D. Wagner and B. Schneier. Analysis of the SSL 3.0 protocol. In Proceedings of the Second USENIX Workshopon Electronic Commerce, pages 29–40. USENIX Association, 1996.

[30] W. Zeller and E. W. Felten. Cross-site request forgeries: Exploitation and prevention. Technical report,October 2008. Available at http://from.bz/public/documents/publications/csrf.pdf.

Documents

Kryptographische Protokolle [KryptProt] · Bachelorstudiengang Informatik/IT-Sicherheit Kryptographische Protokolle [KryptProt] Autoren: Jörg Schwenk Tibor Jager Katrin Weiden Lehrstuhl