https://crocs.fi.muni.cz @CRoCS_MUNI PV204 Security technologies Secure channel protocols: From basic key establishment via Signal protocol to Noise framework Petr Švenda svenda@fi.muni.cz @rngsec Centre for Research on Cryptography and Security, Masaryk University Please provide any corrections and comments here (thank you!): https://drive.google.com/file/d/1n8rLLlJChWn1aFEAfZdWF1aEvmLUHn38/view?usp=sharing https://crocs.fi.muni.cz @CRoCS_MUNI2 I PV204 - Q&A session https://crocs.fi.muni.cz @CRoCS_MUNI3 PV204 - Secure channel protocols Key Establishment Diffie-Hellman ECDH Perfect Forward Secrecy (Future Secrecy) Password-authenticated key exchange (PAKE) Off-The-Record protocol (IM) Signal protocol (IM) Extended Access Control ECDH+PACE BAC Electronic passports Backward Secrecy Noise framework https://crocs.fi.muni.cz @CRoCS_MUNI SECURITY PROTOCOLS 4 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI Security protocols • Security protocol = composition of cryptoprimitives • “Security protocols are three line programs that people still manage to get wrong.” (R. Needham) • Many different aspects of security protocols – Entity authentication – Key agreement, establishment or distribution – Data encryption and integrity protection – Non-repudiation – Secure multi-party computation (SMPC) – … PV204 - Secure channel protocols5 https://crocs.fi.muni.cz @CRoCS_MUNI Authentication (AUTH) vs. Key establishment (KE) • Early literature called protocols used to establish session keys as “authentication protocols” • Session keys can be established without authentication – Example: non-authenticated Diffie-Hellman • Authentication is also possible without session keys – Example: Challenge-response protocol like FIDO U2F • Common protocol workflow (e.g., TLS): 1. Authenticate parties 2. Establish session keys 3. Use session keys to encrypt and authenticate messages – (do it in as few messages as possible) 6 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI PROTOCOLS AND ATTACKS PV204 - Secure channel protocols11 https://crocs.fi.muni.cz @CRoCS_MUNI Typical models of adversary • Adversary controls the communication – Between all principals – Observe, alter, insert, delay or delete messages • Adversary can obtain session/long term keys – used in previous runs • Malicious insider – adversary is legitimate protocol principal • Attacker can obtain partial knowledge – Secrets compromise, side-channels… • … PV204 - Secure channel protocols12 https://crocs.fi.muni.cz @CRoCS_MUNI Needham–Schroeder protocol: symmetric • Basis for Kerberos protocol (AUTH, KE), 1978 – Two-party protocol (A,B) + trusted server (S) – Session key KAB generated by S and distributed to A together with part intended for B – Parties A and B are authenticated via S 1. A → S: A, B, NA 2. S → A: {NA, KAB, B, {KAB, A}KBS}KAS 3. A → B: {KAB, A}KBS 4. B → A: {NB, A}KAB 5. A → B: {NB - 1}KAB PV204 - Secure channel protocols13 Can you spot problem? Which part ensures: Authentication Key confirmation Freshness https://crocs.fi.muni.cz @CRoCS_MUNI N-S symmetric: Problem? • Vulnerable to replay attack (Denning, Sacco, 1981) • If an attacker compromised older KAB then – {KAB, A}KBS can be replayed to B (step 3.) – B will not be able to tell if KAB is fresh – Attacker will then impersonate A using old (replayed, compromised) key KAB • Fixed by inclusion of nonce/timestamp N’B generated by B (two additional steps before step 1.) – Bob can now check freshness of {KAB, A, N’B}KBS PV204 - Secure channel protocols What is required attacker model to perform the attack? 14 https://crocs.fi.muni.cz @CRoCS_MUNI What is required attacker model? • Able to capture valid communication ({KAB, A}KBS) • Able to compromise older KAB • Actively communicate with B (reply ({KAB, A}KBS) PV204 - Secure channel protocols15 But is an assumption of compromise of old key realistic? https://crocs.fi.muni.cz @CRoCS_MUNI How (not) to reason about potential compromise • NO: all my (many) keys are in secure hardware and therefore I’m secure (no compromise possible) – Nothing like perfect security exists • YES: assume compromise and evaluate impact – Where the sensitive keys are – How hard is to compromise them – What will be the impact of the compromise – Can I limit number/exposure of keys? For what price? PV204 - Secure channel protocols16 https://crocs.fi.muni.cz @CRoCS_MUNI What if key is compromised? • Prevention, detection (is hard), reaction • Prevention of compromise – Limit usage of a key • master key → session keys (use secure key derivation function) • Use PKI instead of many symmetric keys in trusted terminals – Limit key availability • Erase after use, no/limited copy in memory, trusted element – Limited-time usefulness of keys (key update) • (Perfect) forward secrecy: messages sent before is secure • Reaction on compromise – stop using key, update and let know (revocation) PV204 - Secure channel protocols18 https://crocs.fi.muni.cz @CRoCS_MUNI Formal verification of protocols • Negatives • Specific attacker model – Different attacker (e.g., sidechannels) => attack possible • Assumes perfect crypto- primitives • Sensitive to precise specification • Hard to express real-world complex protocols – Search space too large • Positives • Automated process • Prevents basic and some advanced design flaws • Favours simple solutions – Complexity is enemy of security 21 PV204 - Secure channel protocols Is formal verification panacea? Proofs by formal verification now considered good practice and actively aimed for (e.g., TLS1.3) https://crocs.fi.muni.cz @CRoCS_MUNI MORALE: PROTOCOL DESIGN IS VERY HARD => USE EXISTING, PROVEN ONES 22 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI KEY ESTABLISHMENT PV204 - Secure channel protocols25 https://crocs.fi.muni.cz @CRoCS_MUNI Methods for key establishment 1. Derive from pre-shared secret (PBKDF2) 2. Establish with help of trusted party (Kerberos, PKI) 3. Establish over insecure channel (Diffie-Hellman) 4. Establish over other (secure) channel (code book) 5. Establish over non-eavesdropable channel (BB84) 6. … 26 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI Diffie-Hellman key exchange PV204 - Secure channel protocols http://www.themccallums.org/nathaniel/2014/10/27/authenticated-key-exchange-with-speke-or-dh-eke/ 28 Which part ensures: Key establishment Key confirmation Authentication Cyclic group with large order, generator g, large prime p https://crocs.fi.muni.cz @CRoCS_MUNI Diffie-Hellman in practice • Be aware of particular p and g – If g is widely used with length up to 1024b then precomputation is possible • “Logjam” attack, [CCS’15] • Huge precomputation effort, but feasible for large national agency • Certain combination of g and p => fast discrete log to obtain A – If p is really prime and g has larger order (Indiscrete logs, [NDSS17]) • Variant of DH based on elliptic curves used (ECDH) – ECDH is preferred algorithm for TLS, ePassport… – ECDH is algorithm of choice for secure IM (Signal) 29 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI DH based on elliptic curves used (ECDH) PV204 - Secure channel protocols http://www.themccallums.org/nathaniel/2014/10/27/authenticated-key-exchange-with-speke-or-dh-eke/ 30 EC curve, G (base point) A x G (scalar multiplication) B x G A x B x G A x b B x a A x B x G EC curve options: • Edwards curves (e.g., Ed25519) • NIST FIPS curves (e.g., NIST P-256) • … many options, see https://safecurves.cr.yp.to/ https://crocs.fi.muni.cz @CRoCS_MUNI Diffie-Hellman in practice • K is not used directly, but K’ = KDF(K) is used 1. Original K may have weak bits 2. Multiple keys may be required (KENC, KMAC) • Is vulnerable to man-in-the-middle attack (MitM) – Attacker runs separate DH with A and B simultaneously – (Unless a and b are authenticated) • DH can be used as basis for Forward/Backward/Future secrecy • DH can be used as basis for Data encryption • DH can be used as basis for Password-Authenticated Key Exchange PV204 - Secure channel protocols31 https://crocs.fi.muni.cz @CRoCS_MUNI ECDH for data encryption: ECIES Hybrid Encryption Scheme 1. New ECDH key on server side 2. ECDH key agreement 3. Key derivation for symmetric keys 4. Data Encryption (ENC) 5. Data Authentication (MAC) 6. Message blob (Cryptogram) 32 PV204 - Secure channel protocols https://cryptobook.nakov.com/asymmetric-key-ciphers/ecies-public-key-encryption https://crocs.fi.muni.cz @CRoCS_MUNI PERFECT FORWARD SECRECY PV204 - Secure channel protocols33 https://crocs.fi.muni.cz @CRoCS_MUNI Forward secrecy - motivation • Assume that session keys are exchanged using long-term secrets 1. Pre-distributed symmetric cryptography keys (SCP’02) 2. Public key cryptography (PGP, TLS_RSA_...) • What if long-term secret is compromised? I. All future transmissions can be read II. Attacker can impersonate user in future sessions III. All previous transmissions can be compromised (if traffic was captured) • Can III. be prevented? (Forward secrecy) • Can I. be prevented? (Backward secrecy, “healing”) PV204 - Secure channel protocols34 Must not have past keys Must not derive future keys deterministically https://crocs.fi.muni.cz @CRoCS_MUNI Forward/backward secrecy – how to • (Perfect) Forward Secrecy – Compromise of long-term keys does not compromise past session keys • Solution: ephemeral key pair (DH/ECDH/RSA/…) 1. Fresh keypair generated for every new session 2. Ephemeral public key used to exchange session key 3. Ephemeral private key is destroyed after key exchange • Captured encrypted transmission cannot be decrypted • Long-term key is used only to authenticate ephemeral public key to prevent MitM – E.g., MAC over DH share PV204 - Secure channel protocols35 https://crocs.fi.muni.cz @CRoCS_MUNI Use of forward secrecy: examples • HTTPS / TLS – TLS1.2: ECDHE-ECDSA, ECDHE-RSA… – TLS1.3: TLS_ECDHE_ECDSA_WITH_xxx… • SSH (RFC 4251) • PAKE protocols: EKE, SPEKE, SRP… • Off-the-Record Messaging (OTR) protocol (2004) • Signal protocol (2015) • Noise protocol framework (2017) PV204 - Secure channel protocols36 https://crocs.fi.muni.cz @CRoCS_MUNI PASSWORD-AUTHENTICATED KEY EXCHANGE (PAKE) PV204 - Secure channel protocols37 https://crocs.fi.muni.cz @CRoCS_MUNI PAKE protocols - motivation • Diffie-Hellman can be used for key establishment – Authentication ca be added via pre-shared (longterm) key • But why not directly derive session keys from preshared instead of running DH? 1. Compromise of pre-shared key => compromise of all data transmissions (including past) => no forward secrecy 2. Pre-shared key can have low entropy (password / PIN) => attacker can brute-force • Password-Authenticated Key Exchange (PAKE) – Sometimes called “key escalation protocols” PV204 - Secure channel protocols38 https://crocs.fi.muni.cz @CRoCS_MUNI PAKE protocols - principle • Goal: prevent MitM and offline brute-force attack 1. Generate asymmetric keypair for every session – Both RSA and DH possible, but DH provides better performance in keypair generation 2. Authenticate public key by (potentially weak) shared secret (e.g., password or even PIN) – Must limit number of failed authentication requests! 3. Exchange/establish session keys for symmetric key cryptography using authenticated public key PV204 - Secure channel protocols39 https://crocs.fi.muni.cz @CRoCS_MUNI To protect against offline bruteforce attack against the password used, an attacker must not be able to tell if the decrypted a’ is valid (any structure of a’ can reveal successful decryption) Diffie-Hellman Encrypted Key Exchange [PAKE] 40 PV204 - Secure channel protocols http://www.themccallums.org/nathaniel/2014/10/27/authenticated-key-exchange-with-speke-or-dh-eke/ Various options a,b,c available https://crocs.fi.muni.cz @CRoCS_MUNI Secure Remote Password protocol (SRP), [aPAKE] • Earlier Password-Authenticated Key Exchange protocols (PAKEs) were patented: EKE, SPEKE… (patent expired in 2017) • Secure Remote Password protocol (SRP) 1998 – Designed to work around existing patents – Royalty free, open license (Standford university), basis for multiple RFCs – Several revisions since 1998 (currently 6a) – Originally with DH, variants with ECDH exist – Widely used, support in common cryptographic libraries • Apple uses SRP extensively in its iCloud Key Vault • Asymmetric Password Authenticated Key Exchange (aPAKE) 42 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI43 PV204 - Secure channel protocols https://www.codeproject.com/KB/security/1082676/SrpAuthenticationSequence.png SRP is unnecessarily complex to work around existing patens https://crocs.fi.muni.cz @CRoCS_MUNI SECURE INSTANT MESSAGING PV204 - Secure channel protocols46 https://crocs.fi.muni.cz @CRoCS_MUNI “Toy” protocol for protection of instant messaging • Relatively short sessions with multiple messages • Perfect forward secrecy – Ephemeral DH to establish Alice/Bob master keys • Past keys/messages are secure • Derive next key within session by KDF (hash) • We also need “Future” secrecy – Automatic self-healing after key compromise – Next key must NOT be deterministically generated from previous ones 47 PV204 - Secure channel protocols Key 2 is compromised All subsequent session keys now compromised https://signal.org/blog/advanced-ratcheting/ https://crocs.fi.muni.cz @CRoCS_MUNI “Ratcheting” == new DH exchange for every message 48 PV204 - Secure channel protocols https://signal.org/blog/advanced-ratcheting/ https://crocs.fi.muni.cz @CRoCS_MUNI Off-The-Record Messaging (OTR), 2004 • Protocol for protection of instant messaging – Establish session, communicate, close (minutes/hours) • Perfect forward secrecy (using ephemeral DH keys) – Also “future” secrecy: automatic self-healing after compromise • OTR “ratcheting” (new DH key for every session & new message) • Plausible deniability of messages – Message MAC is computed, message send and received – MAC key used to compute MAC is then publicly broadcast – As MAC key is now public, everyone can forge past messages (will not affect legitimate users but can dispute claims of cryptographic message log in court) 49 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI OTR protocol PV204 - Secure channel protocols50 Key exchange Message exchange See https://blog.cryptographyengineering.com/2014/07/26/noodling-about-im-protocols/ for details https://crocs.fi.muni.cz @CRoCS_MUNI OTR – some problems • How to work with asynchronous messages? – OTR designed for instant messaging with short sessions • What if out-of-order message is received? – OTR has counter to prevent replay • Window of compromise is extended – Decryption key cannot be deleted until message arrives • … • Systematization of Knowledge: Secure Messaging (2015) – Systematic mapping of Secure Messaging protocols – http://www.ieee-security.org/TC/SP2015/papers-archived/6949a232.pdf 51 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI SIGNAL PROTOCOL 52 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI The Signal protocol • State-of-the-art of instant messaging protocols – Used in Signal, WhatsApp, Facebook Messenger, Google Allo… • The Signal protocol provides: – confidentiality, integrity, message authentication, – participant consistency, destination validation, – forward secrecy, backward secrecy (aka future secrecy) – causality preservation, message unlinkability, message repudiation, participation repudiation and asynchronicity – end-to-end encrypted group chats • Requires servers (but servers are untrusted wrt message privacy/integrity) – relaying of messages and storage of public key material • ECDH with Curve25519, AES-256, HMAC-SHA256 53 PV204 - Secure channel protocols https://signal.org/blog/advanced-ratcheting/ https://crocs.fi.muni.cz @CRoCS_MUNI The Signal protocol implementation • Authentication of users: 1) Trust on first use 2) Trusted party (PKI) 3) Fingerprint check using other channel (hex, QR code…) • Protection of messages – Perfect forward secrecy and backward secrecy (ratcheting) – New DH for (almost) every message (announced in the previous one) – Message key derived both from long-term key and chain key – Authenticated Encryption with deniability (MAC key broadcasted later) • Protection of metadata (but no strong anonymity such as in Tor) – Message delivery time and communicating parties available – Service provider may choose to keep or delete this information • Private contact discovery using Intel SGX – https://signal.org/blog/private-contact-discovery/ 54 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI Message keys in Signal 55 PV204 - Secure channel protocols • Basic trick: combine frequent ECDH and hash chains • Root key(s) (RK) – Established from last ECDH ratchet and previous RK • Chain key(s) (CK) – Established from the most recent RK + hash chain – KDF to derive next CK = HMAC-HASH(CK, "1") • Message key(s) (MK) – Derived from CK as MK = HMAC-HASH(CKs, "0") – Message Ax encrypted by MKx • RK&CK compromise is “healed” by next ECDH • Out-of-order messages by storage of corresponding MKx https://signal.org/docs/specifications/doubleratchet/ https://crocs.fi.muni.cz @CRoCS_MUNI https://signal.org/docs/specifications/doubleratchet/ 56 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI NOISE PROTOCOL FRAMEWORK 58 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI Noise protocol framework (https://noiseprotocol.org/) • Do you have exactly same situation as Signal? – Then use Signal’s code, but: different usage scenario, unnecessarily large code base… • What if different usage scenario is required with some changes needed? – Custom changes to protocol are always risky – (Signal is formally verified, but change may break the proof + change in assumptions) • And formally verified protocols is not enough – we need also secure implementation! • Ideally: custom, but formally verified protocol + generator of its code 59 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI Noise protocol framework (https://noiseprotocol.org/) • Ideally, formally verified protocol + generator of code • Noise protocol framework is exactly that – T. Perrin (co-author of Signal’s double-ratchet protocol) – https://noiseprotocol.org/noise.pdf + generator (https://noiseexplorer.com/) – Used by WhatsApp since October 2020, Bitcoin Lighting protocol, I2P anonymity network, WireGuard VPN… 1. Protocol designer to describe what needs using simple language or picks from already existing patterns (many of them) 2. Execute formal verification (ProVerif) to verify protocol claims – E.g., claim: same shared key, one party authenticated for passive attacker 3. Run code generator to get complete code in target language 60 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI Some existing Noise patterns 61 PV204 - Secure channel protocols https://noiseexplorer.com/patterns/NN/ https://noiseexplorer.com/patterns/NX/ https://noiseexplorer.com/patterns/IKpsk2/ • Noise protocols use set of rules: – If you already have some key, use it immediately to encrypt all subsequent messages – When new entropy is available (ECDH), update current state (keys) => forward&backward secrecy – Use AEAD for all message encryption – … https://crocs.fi.muni.cz @CRoCS_MUNI ELECTRONIC PASSPORTS AND CITIZEN ID CARDS PV204 - Secure channel protocols Credit: Slides partially based on presentation by Zdenek Říha 62 https://crocs.fi.muni.cz @CRoCS_MUNI Passports of the first generation • Electronic passport – Classical passport booklet + passive contactless smartcard (ISO14443, communication distance 0-10 cm) – Chip & antenna integrated in a page or cover • Technical specification standardized by ICAO – Standard 9303, 6th edition – References many ISO standards • Data is organised in 16 data groups (DG) and 2 meta files – DG1-DG16, EF.COM, EF.SOD – Mandatory is DG1 (MRZ), DG2 (photo), EF.COM and EF.SOD (passive authentication) PV204 - Secure channel protocols63 https://crocs.fi.muni.cz @CRoCS_MUNI Chip and antenna PV204 - Secure channel protocols64 https://crocs.fi.muni.cz @CRoCS_MUNI Data groups Data group Stored data DG1 Machine readable zone (MRZ) DG2 Biometric data: face DG3 Biometric data: fingerprints DG4 Biometric data: iris DG5 Picture of the holder as printed in the passport DG6 Reserved for future use DG7 Signature of the holder as printed in the passport DG8 Encoded security features – data features DG9 Encoded security features – structure features DG10 Encoded security features – substance features DG11 Additional personal details (address, phone) DG12 Additional document details (issue date, issued by) DG13 Optional data (anything) DG14 Data for securing secondary biometrics (EAC) DG15 Active Authentication public key info DG16 Next of kin PV204 - Secure channel protocols65 https://crocs.fi.muni.cz @CRoCS_MUNI Protocols used in ePassports I. I. Authentication of inspection system to chip [BAC] – Read basic digital data from chip (MRZ, photo) – SG: Passport provides basic data only to local terminal with physical access to passport – S: Auth. SCP, sym. crypto keys derived from MRZ [BAC] II. Authorized access to more sensitive chip data – SG: Put more sensitive data on chip (fingerprint, iris), but limit availability only to inspection systems of trustworthy countries – S: Challenge-response auth. protocol [EAC,EAC-PACE], PKI + cross-signing between trustworthy states [EAC] PV204 - Secure channel protocols66 SG: security goal, S: solution used https://crocs.fi.muni.cz @CRoCS_MUNI Protocols used in ePassports II. III. Genuine data on passport – SG: Are data on passport unmodified? – S: digital signatures, PKI [passive authentication] IV. Authentication of chip to inspection system – SG: Is physical chip inside passport genuine? – S: Challenge-response authentication protocol [AA, EAC-PACE] V. Transfer data between chip and IS securely – SG: attacker can’t eavesdrop/modify/replay – S: secure channel [EAC, EAC-PACE] PV204 - Secure channel protocols67 SG: security goal, S: solution used https://crocs.fi.muni.cz @CRoCS_MUNI How Signal and ePassports compare? • Completely different usage scenario – Instant messaging vs. person/terminal authentication – Frequent software updates possible vs. 15 years passport validity • Different trust relations and participants structure – N friends vs. many partially or fully distrusting participants – Mostly online vs. mixed offline/online (even without clock!) • Underlying cryptographic primitives are shared – Forward secrecy, ECDH, AES, SHA-2… – Ratcheting and deniability not necessary for ePass 70 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI STILL WANT TO DESIGN OWN PROTOCOL? ☺ 71 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI Design of cryptographic protocols • Don’t design own cryptographic protocols – Use existing and well-studied protocols (TLS, EAC-PACE…) – Don’t remove “unnecessary” parts of existing protocols • Don’t implement existing/your protocol (if possible) – Potential for error, implementation attacks…, use existing implementations • Follow all required checks on incoming messages – Verification of cryptograms, check for revocation… • But more likely you will need to design own protocol than to design own crypto algorithm – Always use existing protocol if possible PV204 - Secure channel protocols72 https://crocs.fi.muni.cz @CRoCS_MUNI Conclusions • Design of (secure) protocols is very hard – Understand what are your requirements – Use existing protocols, e.g., TLS, Signal or EAC-PACE – Use existing implementations (very hard to implement securely) • Resiliency against compromise of long-term secrets is crucial (forward secrecy) • Strong session keys authenticated by weak passwords (PAKEs) • Signal protocol is state-of-the-art and widely deployed (Instant messaging) • Electronic passport uses variety of protocols (Interesting and complex scenarios) • Mandatory reading – M. Green, Noodling about IM protocols, http://blog.cryptographyengineering.com/2014/07/noodling-about-im- protocols.html – M. Marlinspike, Advanced cryptographic ratcheting https://whispersystems.org/blog/advanced-ratcheting/ 73 PV204 - Secure channel protocols https://crocs.fi.muni.cz @CRoCS_MUNI74 PV204 - Secure channel protocols