Puncturable Symmetric KEMs For Forward-Secret 0-RTT Key .

3y ago
19 Views
2 Downloads
968.74 KB
97 Pages
Last View : 22d ago
Last Download : 2m ago
Upload by : Brady Himes
Transcription

Puncturable Symmetric KEMs forForward-Secret 0-RTT Key ExchangeMATILDA BACKENDALMASTER S THESISDEPARTMENT OF ELECTRICAL AND INFORMATION TECHNOLOGYFACULTY OF ENGINEERING LTH LUND UNIVERSITY

Puncturable Symmetric KEMs forForward-Secret 0-RTT Key ExchangeMatilda BackendalDepartment of Electrical and Information TechnologyLund UniversitySupervisors: Felix Günther, Thomas JohanssonExaminer: Fredrik RusekJune 2019

c 2019 Printed in SwedenTryckeriet i E-huset, Lund

Till Peter,som lärde mig att det inte finns några dumma frågor.Juni 2019

ii

AbstractThe latest version of the Transport Layer Security protocol (TLS 1.3) introduces apre-shared key zero round-trip time (0-RTT) mode. This enables session resumption with no latency before the first application data can be sent, at the cost oflosing forward secrecy and replay protection. There is high demand from Internet companies for this performance-enhancing feature, and some service providershave chosen to already enable it by default despite the security compromise currently associated to it. In this work we explore the possibility to achieve forwardsecrecy for resumed sessions in 0-RTT mode, mitigating the security risks presentlyadherent to it.To abstract the key exchange in TLS 0-RTT mode, we introduce a new primitive which we call symmetric-key key encapsulation mechanisms (S-KEMs). Forward secrecy is attained through “puncturing” of the secret key, which we captureformally by puncturable S-KEMs (PS-KEMs). Furthermore, to enable optimizations that leverage ordering and to achieve the greatest possible generality of ourmodel, we also introduce stateful versions of S-KEMs and PS-KEMs. We examine the relationship between these new primitives, give game-based functionalityand security notions and show how pseudorandom functions (specifically based onthe Goldreich-Goldwasser-Micali construction) can be used to build instantiationswhich meet the security goals.iii

iv

SammanfattningI den senaste versionen av kommunikationsprotokollet Transport Layer Security1(TLS 1.3), introducerades en funktion som möjliggör att sessioner återupptas i“zero round-trip time” 2 (0-RTT) vilket innebär att snabbare uppkoppling är möjligeftersom krypterad applikationsdata kan skickas redan med det första dataflödetfrån klient till server. För att uppnå detta används krypteringsnycklar som harförhandlats fram i tidigare sessioner, så kallade “pre-shared keys” 3 . Tyvärr innebär den nya funktionen att kommunikationen inte längre är säker mot framtidakorruption av dessa långlivade nycklar. Detta kallas för avsaknad av “forwardsecrecy” 4 .Trots de lägre säkerhetsgarantierna är efterfrågan på 0-RTT-funktionen storbland internetleverantörer eftersom den ger en markant hastighetsökning, framförallt för mobila nätverk där latensen är hög. I det här arbetet undersöker vimöjligheten att behålla den snabba återuppkoppling, men samtidigt uppnå sammasäkerhet som vid en vanlig anslutning. Detta görs genom en abstraktion av nyckelutbytet i en TLS-session, vilket vi modellerar med ett nytt kryptografiskt objektsom vi har döpt till “symmetriska nyckelinkapslingsmekanismer” (S-KEMs). Forward secrecy uppnås genom införandet av “nyckelpunktering”, vilket vi modellerarmed s.k. punkterbara S-KEMs (PS-KEMs). Vi formaliserar funktionalitet- ochsäkerhetsmålen med hjälp av spelbaserade definitioner för S-KEMs och PS-KEMs.Vi ger även exempel på hur algoritmer kan konstrueras för att uppnå målen, samtutvidgar modellen till att även innefatta ordningsföljden av återanslutna sessionerför att möjliggöra rsatt:2Transportlagersäkerhetnoll tur- och returtidtidigare delade nycklarframåtsäkerhetv

vi

AcknowledgmentsFirst and foremost, I owe the idea behind this work to my advisor Felix Günther.Thank you for taking me on as your first master thesis student and for the generosity with which you have treated me, both to your time and advice. Yourcontinuous support is what made this thesis possible.A sincere thank you also to my supervisor Professor Thomas Johansson forenabling the arrangements of this project, for welcoming me in the crypto groupat LTH and for helping with formalities and logistics.Lastly, I would like to express my gratitude to several people who—throughsmall but significant acts—supported me in this project and helped shape theoutcome. Thank you Joseph Jaeger, for never saying no to a question and forhelping me imagine symmetric-key KEMs before they existed. Thank you to mymentor Malin Jonsson, for sharing your experiences and insights on thesis-writing.Thank you Erik Sandström, for keeping me motivated and for showing me thatthe only true failure is not trying. Thank you also to Marie Backendal Lundin, forencouraging me to take a walk (you are the guardian of my physical and mentalwell-being), to Malin Lundin, for understanding me better than anyone else, andto Peter Lundin, for always reading my work, for your questions and feedback andfor being my greatest supporter. I owe you my curiosity.vii

viii

Acronyms0-RTTZero Round-Trip TimeHTTPHypertext Transfer ProtocolHTTPSHypertext Transfer Protocol SecureIETFInternet Engineering Task ForceKDFKey Derivation FunctionKEMKey Encapsulation MechanismOS-KEMOrdered Symmetric-key Key Encapsulation MechanismPS-KEMPuncturable Symmetric-key Key Encapsulation MechanismPRFPseudorandom FunctionPRGPseudorandom GeneratorPSKPre-Shared KeyPOS-KEM Puncturable Ordered Symmetric-key Key EncapsulationMechanismRFCRequest For CommentsS-KEMSymmetric-key Key Encapsulation MechanismTLSTransport Layer SecurityURLUniform Resource Locatorix

x

Table of Contents1Introduction and Overview1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2Background2.1 Symmetric-Key Cryptography .2.2 Public-Key Cryptography . . . .2.3 Cryptographic Schemes: Syntax,2.4 Key Encapsulation Mechanisms2.5 Network Protocols and TLS . .2.6 Sessions and Resumption . . . .2.7 Forward Secrecy . . . . . . . .3Overview of Results4Basic Definitions4.1 Notation and Conventions4.2 Games . . . . . . . . . . .4.3 Pseudorandom Generators4.4 Pseudorandom Functions .4.5 Birthday Bound . . . . . .56. . . . . . . . . . . . . . . . .Correctness and. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Security. . . . . . . . . . . . . . . . .11355567991011.131313151616Symmetric-key KEMs5.1 Syntax . . . . . . . . . . . . . . . . . . . . .5.2 Security . . . . . . . . . . . . . . . . . . . .5.3 Instantiation using Pseudorandom Functions5.4 Integrity of Ciphertexts . . . . . . . . . . . .1919192127Ordered Symmetric-key KEMs6.1 Syntax . . . . . . . . . . . .6.2 Correctness . . . . . . . . .6.3 Robustness . . . . . . . . .6.4 Security . . . . . . . . . . .6.5 Instantiations . . . . . . . .313132393941.xi.

789Puncturable Symmetric-key KEMs7.1 Syntax . . . . . . . . . . . . . .7.2 Correctness . . . . . . . . . . .7.3 Security . . . . . . . . . . . . .7.4 Instantiation . . . . . . . . . .4949505152Puncturable Ordered Symmetric-key KEMs8.1 Syntax . . . . . . . . . . . . . . . . . . .8.2 Correctness . . . . . . . . . . . . . . . .8.3 Robustness . . . . . . . . . . . . . . . .8.4 Security . . . . . . . . . . . . . . . . . .8.5 Instantiations . . . . . . . . . . . . . . .616161666667Conclusion9.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .717272.References73A Illustration of the PS-KEMGGM Puncturing Algorithm79B Populärvetenskaplig sammanfattning80xii

Chapter1Introduction and Overview1.1 IntroductionThe original goal of cryptography is to provide two parties, let’s call them Aliceand Bob, with tools that allow them to communicate openly, but securely, in theface of some adversary, Eve. By openly, we mean that the actual communicationis not hidden from Eve. Rather, it occurs across a public and insecure channel andthe adversary is both aware of the communication and assumed to have means tointercept and interact with it. The definition of securely is less straight-forward,but in classic cryptography the goal was mainly to achieve privacy, i.e. that theinformation exchanged between Alice and Bob could not be learned by Eve. Theart of hiding vulnerable information from the curious eyes of enemies has beenused for thousands of years in everything from warfare to love letters. Today, inthe digital era, cryptography has become indispensable to the general public asthe Internet has risen to be our main platform for communication.Cryptography has likewise risen to the challenge and provides a wealth of toolsfor diverse tasks such as identification, authentication and private communication.Most people today use cryptography without even noticing it, for example eachtime they access a web page through https, sign a contract digitally or use amessaging app. Users of online services unconsciously assume that their data isprotected, but still expect high performance from applications. Almost everyonebecomes frustrated when a web page loads slowly, but few are those who wouldaccept that their Internet bank publicly broadcast their account details to speedup the connection. The combined goal of security and performance is the mainworking area of modern cryptography, and while they may not seem incompatiblethey often end up going head-to-head.One example of where performance and privacy end up competing for importance is in secure browsing. Whenever a user accesses a URL starting with https,a cryptographic protocol called TLS (Transport Layer Security [42]) is used toensure that the communication is private. In order to do so, cryptographic material (such as secret keys) must first be negotiated between the communicatingparties. The parties in the applications we are concerned with will generally be auser in a browser, called the client, and a service provider (e.g. the host of a webpage) called the server. In order to establish the shared cryptographic parametersand keys, an initial phase of TLS called a handshake is run. This handshake does1

2Introduction and Overviewnot contribute to the actual data exchange between client and server, rather it isadded before the real communication begins to ensure that subsequent messagesare secure. This means that a client accessing a web page via https will experience a slow-down compared to when browsing insecurely via for example http(notice the ending s of https, which stands for secure). The slow-down comesfrom transmission latency – the time it takes for a message to travel from senderto receiver across the network. The time of one message being sent, received andresponded to is called one round-trip, and each round-trip in the handshake phaseadds latency to the communication. More latency means slower responding applications and more frustrated users, so shaving off round-trips is a major goal incurrent development of Internet protocols.Therefore, in the latest version of the Transport Layer Security protocol,TLS 1.3 [42], a new feature called zero round-trip time (0-RTT) resumption hasbeen added. The novelty consists of allowing communication sessions to be resumed (i.e., restarted for a client and server who have been communicating previously) with zero round-trips in the TLS handshake phase. This means that theactual payload data is sent right away, and no time is spent on initially negotiatingcryptographic parameters and exchanging keys before the real communication canbegin. This leads to a significant speed up in resumed sessions, which make uparound 40 % of the total connections [49]. 0-RTT resumption is possible thanksto the fact that the communicating parties have been connected previously, andalready share some secret from their previous session(s). This pre-shared secretcan be used again to derive keying material to encrypt the first message in theresumed session. However, the performance increase comes at a price.When users of the current version of TLS 1.3 re-use the pre-shared secret acrosssessions, they lose a security property called forward secrecy [23, 31]. Briefly explained, forward secrecy means that if at some future point one of the communicating parties is compromised and the secret key they hold at that point is revealed,then all past communication sessions are still secure. Usually this is achieved byusing keys derived from ephemeral key material, e.g. via a Diffie-Hellman keyexchange [22], so that if the secret of one session is compromised, messages inall other sessions are still undecipherable to the attacker. In 0-RTT resumption,the pre-shared key is long-lived and kept during several sessions (up to 7 days inTLS 1.3 [42, p. 74]), and if it is compromised all session keys derived from it aretoo. Hence messages encrypted under keys derived from the pre-shared key arenot forward-secret.In this work, we explore the possibility to achieve forward secrecy whilst keeping the pre-payload communication at zero round-trips. This is done by introducing a new cryptographic object which we call puncturable symmetric key encapsulation mechanisms. Key encapsulation mechanisms (KEMs) are well-studiedobjects in public-key cryptography [15, 17, 18, 19, 46], and here we bring the ideaover to the symmetric-key setting to match the context of session resumption.Puncturing is added to give the desired forward secrecy. Essentially it is an operation on the secret key which “punctures” the key, making it impossible to decryptcertain messages encrypted under earlier versions of the key. That way, previoussessions are safe against future compromises of the evolved key.In this project we lay the theoretic foundation of puncturable symmetric-key

Introduction and Overview3Ch. 5: S-KEMsAdd stateAdd puncturingCh. 6: OS-KEMsCh. 7: PS-KEMsCombineCh. 8: POS-KEMsFigure 1.1: Overview of project.KEMs, as well as an extension to ordered symmetric-key KEMs which capture thetransmission reliability expected of the network across which the communicationoccurs. We introduce new cryptographic objects, defining both their functionality and the security goals they are expected to meet. The result of the projectis a theoretical framework which can be used to reason about these objects, seehow they fit with the intended application and help implementers construct secureschemes. We do give some examples of constructions in this work, as well discusspotential optimizations and ideas for instantiations to explore in the future, butwe stress that the main contribution is the theory developed and not the particular constructions. To implement and optimize instantiations of puncturablesymmetric-key KEMs will have to be the subject of future work.1.2 OverviewFirst, in Chapter 2, we give some background and intuitive explanations of notions necessary for understanding the results of this project. A reader familiarwith cryptography can skip it without any loss. Chapter 3 provides a more detailed overview of the results to come. In Chapter 4 we introduce the notationused in this text, explain briefly what a cryptographic game is as well as recapthe definitions of some fundamental cryptographic objects. In Chapter 5 we definesyntax, correctness and security of symmetric-key KEMs (S-KEMs), and give aconstruction which we prove is secure. With the foundations laid, we add properties to the basic S-KEM notion to bring us closer to our end goal. First, inChapter 6, we add state (which can be used as a way to keep track of the order inwhich sessions are initiated) and define ordered S-KEMs (OS-KEMs). Next, wego back to the original stateless S-KEMs and add puncturing to get puncturableS-KEMs (PS-KEMs) as defined in Chapter 7. Finally, in Chapter 8 we combinethe two branches to obtain puncturable ordered S-KEMs (POS-KEMs). Figure 1.1shows an overview of the notions and illustrates their relations.

4Introduction and Overview

Chapter2Background2.1 Symmetric-Key CryptographyIn symmetric-key cryptography, or secret-key cryptography, the parties wishing tocommunicate securely (e.g. Alice and Bob) share a secret key which they can useboth to encrypt and, among other things, authenticate messages they exchange.The key can be a code word (as in the historic Vigenère cipher) or some piece ofinformation which gives those holding it a mutual way of transforming plaintextinto ciphertext (and reversing it). For further reading on historical ciphers, see forexample [48]. In modern cryptography, a symmetric-key cipher could for exampleconsist of a large set of permutations on a set of strings, which is both the messageand ciphertext space. The secret key is then the precise permutation used toencrypt. Without it, the large number of possible permutations makes decryptioninfeasible. With it, it is a simple matter of evaluating the permutation on theciphertext to get back the plaintext. Such a cipher is commonly referred to as ablock cipher, and famous examples include DES (Data Encryption Standard) [21]and AES (Advanced Encryption Standard) [1].The important thing to remember about secret-key cryptography is the symmetry; it requires that the involved parties have access to a common secret key. IfAlice and Bob want to communicate, they need one such key. If Alice also wantsto communicate privately with Charlie, Alice and Charlie need a different secretkey. Any parties involved in private communication need a shared secret key forthat specific session, meaning that the number of keys a user needs grows linearlywith the number of communication partners they have. A difficulty associatedwith this is key distribution, i.e., ensuring that the parties are informed of thesecret key in a secure way. This is a non-trivial problem and the difficulties associated to it spurred the invention of a different type of cryptography: public-keycryptography.2.2 Public-Key CryptographyIn public-key cryptography, or asymmetric cryptography, a user (Alice) has a secret(or private) key sk and a public key pk. The public key is like an address; it isopenly available to anyone who wishes to communicate with Alice, and (in the caseof encryption) when applied to a message it encrypts it so that only Alice, whoholds the secret key, can decrypt. Because of the asymmetry of the keys, Aliceonly needs one key-pair (sk, pk). Both Bob and Charlie can use Alice’s public5

6Backgroundkey to encrypt their messages to her, and neither will be able to read the other’scommunication because only Alice has the secret key that allows decryption. Thiseffectively solves the key distribution problem, since each user simply broadcaststheir public key openly. However public-key cryptography has its own drawbacks,such as being less efficient than symmetric primitives. For this reason, the publickey infrastructure is often used as a means of distributing symmetric keys, whichare then used for the actual communication. One way to do this is by using akey encapsulation mechanism, which is a kind of encryption scheme for keys. Wediscuss it in more detail in Section 2.4.2.3 Cryptographic Schemes: Syntax, Correctness and SecurityThis project revolves around the description of new cryptographic objects. Thedescription is given in terms of schemes. A “scheme” is a plan, program or strategy.A cryptographic scheme is the description of a cryptographic object; a design forachieving a cryptographic goal. The base layer of

helping me imagine symmetric-key KEMs before they existed. Thank you to my mentor Malin Jonsson, for sharing your experiences and insights on thesis-writing. Thank you Erik Sandström, for keeping me motivated and for showing me that the only true failure is not trying. Thank you also to Marie Backendal Lundin, for

Related Documents:

Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original

Forward Basic MB-02 Forward Basic MG-04 Forward Basic PD-05 Forward Break BL-04 Forward Change (Natural to Rev) VW-03 Forward Change (Rev. to Natural) VW-04 Forward Chassé CH-Int Forward Lock Step QS-14 Forward Progressive Basic MB-11 Forward Spot Turn MG-18 Forward Tipple Chassé QS-37 For

10 tips och tricks för att lyckas med ert sap-projekt 20 SAPSANYTT 2/2015 De flesta projektledare känner säkert till Cobb’s paradox. Martin Cobb verkade som CIO för sekretariatet för Treasury Board of Canada 1995 då han ställde frågan

service i Norge och Finland drivs inom ramen för ett enskilt företag (NRK. 1 och Yleisradio), fin ns det i Sverige tre: Ett för tv (Sveriges Television , SVT ), ett för radio (Sveriges Radio , SR ) och ett för utbildnings program (Sveriges Utbildningsradio, UR, vilket till följd av sin begränsade storlek inte återfinns bland de 25 största

Hotell För hotell anges de tre klasserna A/B, C och D. Det betyder att den "normala" standarden C är acceptabel men att motiven för en högre standard är starka. Ljudklass C motsvarar de tidigare normkraven för hotell, ljudklass A/B motsvarar kraven för moderna hotell med hög standard och ljudklass D kan användas vid

LÄS NOGGRANT FÖLJANDE VILLKOR FÖR APPLE DEVELOPER PROGRAM LICENCE . Apple Developer Program License Agreement Syfte Du vill använda Apple-mjukvara (enligt definitionen nedan) för att utveckla en eller flera Applikationer (enligt definitionen nedan) för Apple-märkta produkter. . Applikationer som utvecklas för iOS-produkter, Apple .

Cryptography and Network Security 2. Symmetric Ciphers Lectured by Nguyễn Đức Thái. 2 Outline Symmetric Encryption Substitution Techniques Transposition Techniques Steganography. 3 Symmetric Encryption There are tw

Alex Rider: Never say Die by Anthony Horowitz Below are the complete reviews, written by the Lovereading4kids members. George Hutton - Dormston Secondary School Alex Rider receives a suspicious email from who could be Jack Starbright who was kidnapped on his previous mission. However, whilst trying to locate Jack, he accidentally manages to get tangled up in another MI6 Mission which could put .