defense

Simultaneously Ensuring Privacy and Authenticity in Digital Communication : Simultaneously Ensuring Privacy and Authenticity in Digital Communication Chanathip Namprempre (aka Meaw) University of California, San Diego


Contents of Dissertation : Contents of Dissertation Generic Composition Paradigm M. Bellare and C. Namprempre. 'Authenticated encryption: Relations among notions and analysis of the generic composition paradigm,' Asiacrypt 2000. A case study: Secure Shell (SSH) M. Bellare, T. Kohno, and C. Namprempre. 'Authenticated encryption in SSH: Provably fixing the binary packet protocol,' ACM Conference on Computer and Communications Security – CCS 2002. Secure Channels C. Namprempre. 'Secure channels based on authenticated encryption schemes: A simple characterization,' Asiacrypt 2002.


Other Publications : Other Publications M. Abdalla, J. An, M. Bellare, and C. Namprempre. 'From identification to signatures via the Fiat-Shamir transform minimizing assumptions for security and forward security,' Eurocrypt 2002. M. Bellare, A. Boldyreva, Lars Knudsen, and C. Namprempre. 'On-line ciphers and the Hash-CBC construction,' Crypto 2001. M. Bellare, C. Namprempre, D. Pointcheval, and M. Semanko. 'The power of RSA inversion oracles and the security of Chaum’s RSA-based blind signature scheme,' Financial Cryptography 2001. M. Abdalla, S. Miner, and C. Namprempre. 'Forward security in threshold signature schemes,' CT-RSA 2001. C. Namprempre, J. Sussman, and K. Marzullo. 'Implementing causal logging using OrbixWeb interception,' USENIX Conference on Object-Oriented Technologies and Systems, May 1999. R. Weiss, B. Velez, M.Sheldon, C. Namprempre, P. Szilagyi, and D. Gifford. 'HyPursuit: a hierarchical network search engine that exploits content-link hypertext clustering,' Hypertext conference, March 1996.


Common Goals in Digital Communication : Common Goals in Digital Communication Alice Bob 0 1 1 0 1 ... Adversary EVE Shared Network


Achieving Privacy and Authenticity : Achieving Privacy and Authenticity Much work in cryptography has been done to achieve each goal separately: Encryption schemes for privacy Message authentication schemes for authenticity Many schemes are accompanied by provable security analyses. However, in practice we often want to achieve the goals simultaneously. A natural and commonly used approach is to combine the above tools.


Symmetric (aka shared key) Setting : Symmetric (aka shared key) Setting Assumption: The communicating parties share a random string called a key which is not a priori known to the adversary. (e.g. 128 bits long, to be used as a key to a block cipher.) We do not concern ourselves here with how the parties got this key but rather with how to use it to get privacy and authenticity. Alice Bob Shared Network K K EVE


Tool for Privacy: Symmetric Encryption Scheme : Tool for Privacy: Symmetric Encryption Scheme EVE K M M C Alice Bob D E K Key …………… K Message ………. M Ciphertext ………C Encryption Alg ….. E Decryption Alg ….. D Goal: It should be hard for EVE to obtain partial information about M. Many constructions: CBC mode, CTR mode, OFB mode, …


Tool for Authenticity: Message Authentication Codes (MACs) : Tool for Authenticity: Message Authentication Codes (MACs) EVE K M valid/ invalid (M,) Alice Bob V T K Key …………… K Message ………. M Tag …….……… MAC Alg ……….. T Verification Alg …. V Goal: It should be hard for EVE to forge a valid new pair (M,). Many constructions: CBC MAC, HMAC, UMAC, … 


Tool for Privacy and Authenticity: Authenticated Encryption Scheme : Tool for Privacy and Authenticity: Authenticated Encryption Scheme Goal: It should be hard for EVE - to obtain partial information about M OR - to forge a valid new ciphertext. EVE K Alice Bob D E K Key …………… K Message ………. M Ciphertext ………C Encryption Alg ….. E Decryption Alg ….. D


Relevance to Internet Security : Relevance to Internet Security Many popular Internet protocols rely on authenticated encryption schemes for privacy and authenticity. Examples: SSL, TLS, SSH, IPSEC, … Many applications on the Internet require both privacy and authenticity. Examples: online banking, online retail, online auctions, instant messaging, remote login, secure file transfer, … There has been a recent surge of research interest. Many workshops, patents, and proposed modes of operation for this purpose. Many new schemes proposed.


Plan : Plan Background on generic composition Results on SSH Description of SSH An attack against SSH Provably secure fixes to SSH Focus: authenticated encryption in SSH


Generic Composition Methods : Generic Composition Methods Encryption scheme Message Authentication scheme Authenticated Encryption Scheme Encrypt-and-MAC EKe,Km(M) = EKe(M)  TKm(M) MAC-then-Encrypt EKe,Km(M) = EKe(M  TKm(M)) Encrypt-then-MAC EKe,Km(M) = EKe(M)  TKm(EKe(M)) Obvious ways to combine the base schemes as black-boxes. Alice can do any of the following:


Generic Composition Results : Generic Composition Results Formal security goals for authenticated encryption: Authenticity: Integrity of ciphertexts (INT-CTXT) Privacy: Indistinguishability under chosen-plaintext attacks (IND-CPA) Chapter 3 [BN00] analyzes generic composition using a provable-security approach.


Generic Composition Results : Generic Composition Results Security Composition Method insecure [can fail to provide privacy or authenticity] insecure [can fail to provide authenticity] secure [always provides privacy and authenticity]


Status of Authenticated Encryption : Status of Authenticated Encryption Generic composition seems well-understood and solved. Well-defined security goals for authenticated encryption, and analyses of methods, exist. Clear recommendation: Use encrypt-then-MAC Why is that not the end of the story? Because, meanwhile, in practice ...


Slide16 : We took a close look at SSH and found that Its authenticated encryption scheme is based on encrypt-and-MAC [  ] But with a twist: Data is pre-processed via an 'encoding' transform before encrypt-and-MAC is applied [, maybe?] Important pragmatic questions arise: Is the SSH authenticated encryption scheme secure? If not, what should we do?


SSH Results : SSH Results Break: The currently implemented scheme is NOT secure. Re-make: We target, and provide, fixes that Are PROVABLY secure Are sympathetic to the design, security, and performance goals of SSH Are relatively cheap to implement Preserve or enhance performance Breaks and re-makes have been communicated to the body of SSH developers. They have expressed interest.


What this involved : What this involved Combination of systems and theory work: Closely examined the codes of popular SSH implementations like openSSH Developed new models and notions of security, and provided security proofs Encode-then-Eandamp;M paradigm that generalizes SSH Strong new security notions for schemes with stateful decryption Relations between notions Concrete security analyses


Plan : Plan Background on generic composition Results on SSH Description of SSH An attack against SSH Provably secure fixes to SSH


Encode-then-E&M Paradigm : Encode-then-Eandamp;M Paradigm EK Each black box can use randomness and/or maintain internal state such as a counter. Encoding may be as simple as padding the payload. Encoding is keyless. It is possible to have different portions of encoded payload go into Encrypt box and MAC box.


Encode-then-E&M Paradigm : Encode-then-Eandamp;M Paradigm EK EncryptKe MACKm It is possible to have different portions of encoded payload go into Encrypt box and MAC box. Each black box can use randomness and/or maintain internal state such as a counter. Encoding may be as simple as padding the payload. Encoding is keyless.


Authenticated Encryption in SSH : Authenticated Encryption in SSH payload M pl pdl padding packet length (in bytes) padding length (in bytes) intermediate ciphertext tag ctr minimum 4 bytes maximum 255 bytes maintained internally, not transmitted EK


Authenticated Encryption in SSH : Authenticated Encryption in SSH payload M payload M pl pdl padding data to be communicated EncryptKe MACKm ctr minimum 4 bytes maximum 255 bytes maintained internally, not transmitted EK


Authenticated Encryption in SSH : Authenticated Encryption in SSH DK


Authenticated Encryption in SSH : Authenticated Encryption in SSH payload M VerifyKm ctr DK


SSH uses CBC Mode for Encryption : SSH uses CBC Mode for Encryption payload M payload M pl pdl padding intermediate ciphertext tag ctr EncryptKe MACKm HMAC-SHA1


SSH uses CBC mode with Inter-Packet Chaining : SSH uses CBC mode with Inter-Packet Chaining $ … … … … … … payload M1 pl1 pdl1 padding1 ctr Observation: IV is known in advance! payload M1 payload M2 pl2 pdl2 padding2 ctr+1 payload M2


Attack against SSH based on CBC with IPC : Attack against SSH based on CBC with IPC EVE has the ability to observe the traffic and to get the sender to process packets of her choice (i.e. to mount a chosen-plaintext attack). C1  C2  G If X = Y, EVE declares that G is correct. EVE waits until she sees two encryptions such that the first 40 bits of the last ciphertext blocks are the same in both (called a collision). This will allow EVE to verify a guess G as to the value of the last L-40 bits of the first plaintext block of a message. (L is the block size.) EVE uses C1  C2  G as the payload. This causes a collision between two points, leading to the collision between X, Y.


Analysis of Attack : Analysis of Attack It takes approximately 220 packets for a collision on 40 bits of two ciphertext packets to occur. For 128-bit blocks, this comes to about 16MBytes of data. With 10Mbit/sec network, it takes only tens of seconds to successfully mount the attack. SSH standard suggests re-keying every 1GByte or 1 hour.


What just happened? : What just happened? This attack violates the privacy property of SSH. EVE only needs to be able to observe packets on the wire and to mount a chosen-plaintext attack. The vulnerability comes from the interaction between the underlying encryption scheme and the encoding. This attack exploits a well-known weakness that occurs when one uses CBC mode with known or predictable IV. Rogaway documented it in 1995!


Fixing SSH : Fixing SSH Recall our design goals: provably secure fixes that preserve or improve efficiency minimize necessary changes to the specifications and implementations Our approach: replace the underlying encryption scheme replace the underlying encoding scheme


Possible Fixes to SSH : Possible Fixes to SSH Security Proposed Fix Works only if padding is random and is always there. Increases bandwidth cost SSH-$NPC: use CBC with new random IV per packet SSH-EIV-CBC: use CBC with IPC but compute the IV by applying the block cipher to the last block of the previous ciphertext SSH-CTR: use CTR mode with stateful decryption instead of CBC Works with or without the padding Requires only one more block cipher invocation per packet Works with or without the padding Requires same amount of computation but is fully parallelizable


SSH-CTR: A Provably Secure Fix : SSH-CTR: A Provably Secure Fix payload M payload M pl pdl padding intermediate ciphertext tag ctr EncryptKe MACKm AESKe … … … Encryption in Counter (CTR) mode with stateful decryption ctr + 1 ctr + n AESKe


Provable Security Results for SSH-CTR : Provable Security Results for SSH-CTR IF base components are secure, THEN SSH-CTR provides privacy and authenticity. We prove statements of the form: Following provable security approach, we provide precise definitions of privacy and authenticity of authenticated encryption schemes with stateful decryption algorithms use the reduction approach to show that, as long as the base components are secure (under appropriate definitions), the composed scheme is secure.


Finding Appropriate Security Definitions : Finding Appropriate Security Definitions Authenticated encryption in SSH uses internal states for both encryption and decryption algorithms. All pre-existing security definitions assume that decryption algorithms are deterministic and stateless. We need new security definitions to analyze SSH. Observation: Internal states help prevent out-of-order delivery. Security definitions for real protocols should capture this. Our new security definitions can be used to analyze many real-world protocols targetting security goals not covered by standard, pre-existing security definitions.


(New) Security Notion of Authenticated Encryption Schemes: Integrity : (New) Security Notion of Authenticated Encryption Schemes: Integrity Adv int-sfctxt (EVE ) is the probability that EVE wins. Scheme is said to be INT-SFCTXT secure if the advantage of any adversary of practical resources (running time, number of oracle queries) is small. C encryption oracle EK(•) EVE can submit a message to an encryption oracle and get back the corresponding ciphertext. EVE can also submit a ciphertext to a verification oracle and get back an indication whether it is valid. EVE wins if she can submit a valid and out-of-sync query to the verification oracle. C verification oracle valid/ invalid M DK(•) * AE


What is an “Out-of-Sync” Query? : What is an 'Out-of-Sync' Query? an 'out-of-sync' query if C  C3 * Encryption Oracle Verification Oracle Recall that we want to require security against out-of-order delivery attacks, in addition to standard forgery attacks.


(Existing) Security Notion of Authenticated Encryption Schemes: Privacy : (Existing) Security Notion of Authenticated Encryption Schemes: Privacy b C LR-encryption oracle Answer: 0/1 EK(•) b is a random bit unknown to EVE EVE can submit a pair of plaintexts to an LR-encryption oracle and get back a ciphertext. After a few queries, EVE tries to guess b. EVE wins if she guesses b correctly. Mb M0 M1 IND-CPA + INT-SFCTXT  IND-SFCCA Adv ind-cpa (EVE ) is the probability that EVE wins. Scheme is said to be IND-CPA secure if the advantage of any adversary of practical resources (running time, number of oracle queries) is small. AE


SSH-CTR Integrity Result : SSH-CTR Integrity Result Informally: IF the MAC is secure (uf-cma), THEN SSH-CTR provides authenticity (int-sfctxt).


SSH-CTR Privacy Result : SSH-CTR Privacy Result Informally: IF the MAC is secure (uf-cma), if AES is pseudorandom (prf), and if the MAC is also pseudorandom (prf), THEN SSH-CTR provides privacy (ind-sfcca).


Proof Sketch for Integrity Result : Proof Sketch for Integrity Result Adv int-sfctxt ( I )  Adv uf-cma ( F ) SSH-CTR MA Let MA be a message authentication scheme. Given any int-sfctxt adversary I against SSH-CTR, assuming that the counter does not wrap during I’s attack, we can construct a forger F such that where F has running time and other resources similar to those of I.


Proof Sketch for Integrity Result : Proof Sketch for Integrity Result I F TKm(•) VKm(•) K = (Ke, Km) generates its own Ke


Proof Sketch for Integrity Result : Proof Sketch for Integrity Result I F * TKm(•) VKm(•) generates its own Ke This means that C is out-of-sync and valid. K = (Ke, Km) Let C = C’  T Forgery: ( ctr  DKe(C’) , T ) Since ctr never wraps, F wins. (M,)


Slide44 : SSH-CTR provides strong privacy and authenticity guarantees. It does so under precise security notions for privacy and authenticity that we defined: INT-SFCTXT and IND-SFCCA. Chapter 4 [BKN02] provides general provable security results. They can be applied to prove our other fixes secure. These results can be used to analyze any schemes that follow the Encode-then-Encrypt-and-MAC composition method.


Conclusions : Conclusions Ensuring both privacy and authenticity simultaneously is crucial in most cryptographic applications. Generic composition is a powerful paradigm for constructing authenticated encryption schemes. Intuition alone is not sufficient in protocol design. Provable security can really help standards bodies and implementors! Really!