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/1iupyVe8Iz39XJshZ2qV2prGPhtERsmqS/view?usp=sharing
https://crocs.fi.muni.cz @CRoCS_MUNI2 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
3 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 protocols4
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)
5 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
User vs. key-oriented goals
• User-oriented authentication goals
– Entity authentication
– Strong entity authentication – fresh entity authentication
– Mutual authentication
• Key-oriented goals
– Key establishment
– Key derivation
– Implicit key establishment
– Key confirmation
– Mutual belief in the key
PV204 - Secure channel protocols6
https://crocs.fi.muni.cz @CRoCS_MUNI
Hierarchy of AUTH&KE goals
PV204 - Secure channel protocols
Protocols for Authentication and Key Establishment By Colin Boyd, Anish Mathuria
7
https://crocs.fi.muni.cz @CRoCS_MUNI
Entity authentication
• Entity = user, machine/device
• Something entity knows (password, key…)
• Something entity is (biometrics…)
• Something entity have (smartcard…)
• Multi-factor authentication
– More than one factor (password + smartcard)
– Aim to increase attacker’s cost to compromise multiple security layers (factors)
8 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
Protocol message components
1. Keys
– Long-term keys
– Session keys
2. Identifiers
– Protocol principals (Alice, Bob…)
3. Nonce(s)
– Random values, timestamps, counters
• Components are combined by crypto mechanism(s)
PV204 - Secure channel protocols9
https://crocs.fi.muni.cz @CRoCS_MUNI
PROTOCOLS AND ATTACKS
PV204 - Secure channel protocols10
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 protocols11
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 protocols12
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?
13
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 protocols14
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 protocols15
https://crocs.fi.muni.cz @CRoCS_MUNI
How to reason about attack and countermeasures?
1. Where does an attack come from (principle)?
– Understand the principles
2. Different hypothesis for the attack to be practical
– More ways how to exploit the same weakness
3. Attack’s countermeasures by cancel of hypothesis
– For every way you are aware of
4. Costs and benefits of the countermeasures
– Cost of the assets protected
– Cost for an attacker to perform attack
– Cost of a countermeasure
• Important: Consider Break Once, Run Everywhere (BORE)
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 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 protocols17
https://crocs.fi.muni.cz @CRoCS_MUNI
Needham–Schroeder protocol: asymmetric
• Simple asymmetric AUTH & KE protocol
• Designed by R. Needham and M. Schroeder (1978)
– (below is simplified version without PKI server S)
1. A → B: {A, NA}PKB
2. B → A: {NA, NB}PKA
3. A → B: {NB}PKB
PV204 - Secure channel protocols
Can you spot the problem?
18
Which part ensures:
Authentication
Freshness
Key establishment
https://crocs.fi.muni.cz @CRoCS_MUNI
N-S asymmetric: Problem?
• Discovered by G. Lowe 17 years after using formal verification
method/tool
PV204 - Secure channel protocols19
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
20 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
21 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
References
• Security Protocols Open Repository
– http://www.lsv.ens-cachan.fr/Software/spore/
• C. Cremer, Scyther tool
– https://github.com/cascremers/scyther/
• Cas Cremer’s exercise sheet
– https://www.cs.ox.ac.uk/people/cas.cremers/scyther/scyther-exercises.html
PV204 - Secure channel protocols22
https://crocs.fi.muni.cz @CRoCS_MUNI
N-S asymmetric: Fix
• Fixed by addition of B’s identity into second step
1. A → B: {A, NA}PK(B)
2. B → A: {B, NA, NB}PK(A)
3. A → B: {NB}PK(B)
PV204 - Secure channel protocols23
https://crocs.fi.muni.cz @CRoCS_MUNI
KEY ESTABLISHMENT
PV204 - Secure channel protocols24
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. …
25 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
Methods for key confirmation
• Goal: ensure that parties use same key value(s)
• Implicit confirmation by use of valid key
– E.g., MAC by session key on future message is valid
• Explicit confirmation by challenge-response
– Dedicated steps in protocol
PV204 - Secure channel protocols26
http://www.themccallums.org/nathaniel/2014/10/27/authenticated-key-exchange-with-speke-or-dh-eke/
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/
27
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 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)
28 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/
29
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 Password-Authenticated Key Exchange
• DH can be used as basis for Forward/Backward/Future secrecy
PV204 - Secure channel protocols30
https://crocs.fi.muni.cz @CRoCS_MUNI
PERFECT FORWARD SECRECY
PV204 - Secure channel protocols31
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 protocols32
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 protocols33
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 protocols34
https://crocs.fi.muni.cz @CRoCS_MUNI
PASSWORD-AUTHENTICATED KEY
EXCHANGE (PAKE)
PV204 - Secure channel protocols35
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 protocols36
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 protocols37
https://crocs.fi.muni.cz @CRoCS_MUNI
To protect against offline
bruteforce attack against
the used password, 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]
38 PV204 - Secure channel protocols
http://www.themccallums.org/nathaniel/2014/10/27/authenticated-key-exchange-with-speke-or-dh-eke/
Various options
available
https://crocs.fi.muni.cz @CRoCS_MUNI
Simple Password Exponential Key Exchange (SPEKE)
PV204 - Secure channel protocols
http://www.themccallums.org/nathaniel/2014/10/27/authenticated-key-exchange-with-speke-or-dh-eke/
39
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
• Asymmetric Password Authenticated Key Exchange (aPAKE)
• Apple uses SRP extensively in its iCloud Key Vault
40 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI41 PV204 - Secure channel protocols
https://www.codeproject.com/KB/security/1082676/SrpAuthenticationSequence.png
https://crocs.fi.muni.cz @CRoCS_MUNI
PAKEs evolution
1. Only password
2. “PAKE” protocols
3. “aPAKE” protocols
4. Strong aPAKE (“SaPAKE”)
• Compromised if server hack
• Prevent MitM offline cracking,
still server hack compromise
• Like PAKE, but using salted hash
instead of password, salt-specific
precomputation possible
• Prevent offline cracking and
precomputation attack (using
zero-knowledge proofs)
42 PV204 - Secure channel protocols
https://blog.cryptographyengineering.com/2018/10/19/lets-talk-about-pake/
Properties
https://crocs.fi.muni.cz @CRoCS_MUNI
Current state of the art SaPAKE
• OPAQUE protocol (Eurocrypt 2018)
– https://eprint.iacr.org/2018/163.pdf
– https://blog.cryptographyengineering.com/2018/10/19/lets-talk-about-pake/
• Prediction about future PAKE uptake
– https://emilymstark.com/2020/07/30/should-web-apps-use-pakes.html
43 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
SECURE INSTANT MESSAGING
PV204 - Secure channel protocols44
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
45 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
46 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)
47 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
OTR protocol
PV204 - Secure channel protocols48
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
• …
• State of Knowledge: Secure Messaging (2015)
– Systematic mapping of Secure Messaging protocols
– http://www.ieee-security.org/TC/SP2015/papers-archived/6949a232.pdf
49 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
SIGNAL PROTOCOL
50 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
• 3-DH with Curve25519, AES-256, HMAC-SHA256
51 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/
52 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
Message keys in Signal
53 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/
54 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
The Signal protocol – group messaging
• Speaker consistency
• Out-of-order resilience
• Dropped message resilience
• Computational equality
• Trust equality
• Subgroup messaging
• Contractible and expandable group membership
• Read more details at https://www.whatsapp.com/security/WhatsApp-
Security-Whitepaper.pdf
55 PV204 - Secure channel protocols
https://en.wikipedia.org/wiki/Signal_(software)#Encryption_protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
NOISE PROTOCOL FRAMEWORK
56 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
57 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
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
58 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
Some examples of existing Noise patterns
59 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
60
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 protocols61
https://crocs.fi.muni.cz @CRoCS_MUNI
Chip and antenna
PV204 - Secure channel protocols62
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 protocols63
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 protocols64
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 protocols65
SG: security goal, S: solution used
https://crocs.fi.muni.cz @CRoCS_MUNI
Basic Access Control (BAC) protocol
• Authentication&secure channel between inspection terminal and chip
– Based on symmetric crypto (3DES), similar to SCP’0x protocols
– Low computational requirements
• Problem: anyone with access to MRZ can authenticate
• Problem: MRZ has insufficient entropy
– Document number, birth date, expiration date used
– Theoretically 58/74 bits, but in practice about 32 bits
• Offline attack (eavesdrop then crack)
– Eavesdrop valid communication between chip and reader
– Brute-force attack in less then hour (232 ops, offline attack)
• Online attacks against chip (att. model: found passport)
– Significantly slower, ~20 ms for every attempt
PV204 - Secure channel protocols66
https://crocs.fi.muni.cz @CRoCS_MUNI
Extended Access Control (EAC) protocol
• Based on asymmetric cryptography (RSA/DH/ECDSA)
• Chip Authentication (CA) based on PACE protocol
– Password Authenticated Connection Establishment (PACE)
– Uses chip’s static DH/ECDSA key and terminal’s ephemeral DH key pair (perfect forward secrecy)
– Both parties combines chip’s public static and ephemeral public key into same key K
– Keys for encryption and MAC (KENC, KMAC) are derived from exchanged K
• How can be Terminal sure of authenticity of chip’s static key?
– Signed by Issuing country
• Terminal Authentication (TA)
– Based on challenge-response protocol (RSA/ECDSA, SHA-1/2)
– Hash of the ephemeral DH key from previous step hashed with challenges
PV204 - Secure channel protocols67
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
68 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
STILL WANT TO DESIGN OWN
PROTOCOL? ☺
69 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 protocols70
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/
71 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI72 PV204 - Secure channel protocols
• Place/upvote questions in slido
while listening to lecture video
• We will together discuss these
during every week lecture Q&A
(every Monday, 17-18:00)
https://crocs.fi.muni.cz @CRoCS_MUNI73 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
DESIGN OF PROTOCOLS
PV204 - Secure channel protocols74
https://crocs.fi.muni.cz @CRoCS_MUNI
Design of cryptographic protocols
• Don’t design own cryptographic protocols
– Use existing well-studied protocols (TLS, EAC-PACE…)
– Don’t remove “unnecessary” parts of existing protocols
• Follow all required checks on incoming messages
– Verification of cryptograms, check for revocation…
• Don’t design and implement your own (if possible)
– Potential for error, implementation attacks…
• 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 protocols75
https://crocs.fi.muni.cz @CRoCS_MUNI
Design principles I. (Abadi & Needham)
• The conditions for a message to be acted should be clearly set out so reviewer
can judge if they are acceptable.
– Documentation, diagrams, formal specification
• Every message should say what it means, message interpretation should
depend only on its content.
– “This is 2nd message of SCP’02 from A to B”
– No assumptions like next random chunk number should be encrypted 2nd message because
I just received 1st message
• Mention name of principal (“Alice01”)
– Prevents (if checked) unintended parallel runs of protocol
– Prevents reflection attack
PV204 - Secure channel protocols76
https://crocs.fi.muni.cz @CRoCS_MUNI
Design principles II. (Abadi & Needham)
• Be clear about why encryption is being done
– For confidentiality, not to “somewhat” ensure integrity
• When signing encrypted data, it should not be inferred that signing
entity knows data content
– No knowledge of encryption key
• Be clear about properties of nonce
– random, never repeated, unpredictable, secret
– Random → almost never repeated unintentionally
PV204 - Secure channel protocols77
https://crocs.fi.muni.cz @CRoCS_MUNI
Design principles III. (Abadi & Needham)
• If predictable quantity is to be effective, it should be protected so that an
intruder cannot simulate a challenge and later replay the message
– Counter as challenge → counter freshness verification necessary → state
• If timestamps are used as freshness guarantees, then difference between
local clocks at various machines must be much less then allowable age of
message
– Otherwise an attacker can replay within time window
• Key may have been used recently and yet be old and possibly compromised
– Clear session state after session end, check freshness
PV204 - Secure channel protocols78
https://crocs.fi.muni.cz @CRoCS_MUNI
Design principles IV. (Abadi & Needham)
• It should be possible to deduce which protocol and which run of
that protocol a message belongs to including order number in the
protocol
– Danger of parallel runs of same protocol
– MAC and chaining with fresh session keys prevents message mixing
• Trust relation should be made explicit and there should be good
reason for its necessity.
– Less trust needed → better security achieved
PV204 - Secure channel protocols79
https://crocs.fi.muni.cz @CRoCS_MUNI
Design principles V. (Hanno Böck)
• Always use an AEAD. No CBC, OFB, CFB. No "signatures
are as good as an AEAD".
• Stay away from PKCS #1 1.5. If you want to use RSA use
PSS/OAEP, but maybe don't use RSA.
• Don't use ECDSA, don't use any old ECC. Use X25519,
Ed25519 or alike.
• Don't use DSA, 64-bit-blocks, sha1/md5 and other old crap.
• Think about duplicate nonces. If you can't easily avoid
nonce repetition consider AES-SIV.
• Still talk to a real cryptographer, but if you follow these
you're already better than a lot of others :-)
80 PV204 - Secure channel protocols
https://crocs.fi.muni.cz @CRoCS_MUNI
Secure channel – typical composition
1. Exchange basic (public) parameters
2. Generate random challenges (freshness)
3. Use pre-distributed secrets and challenges to generate session keys
(protect long term secrets)
4. Compute and verify authentication cryptograms (entity
authentication)
5. Encrypted&MAC message(s) (Secure Messaging)
6. End secure channel (erase session keys)
PV204 - Secure channel protocols81
https://crocs.fi.muni.cz @CRoCS_MUNI
SCP – what to take into account
• Usage scenario and expected attackers
• Confidentiality and integrity of command data
• Network level attacks (replay…)
• Atomicity of critical operations
• Robustness against side channel attacks (time and power analysis,
fault attacks…)
• Robustness against incorrect attempts (limit, delay retries…)
• Resilience against traffic analysis
• API and implementation attacks
PV204 - Secure channel protocols82
https://crocs.fi.muni.cz @CRoCS_MUNI
SCP – usage scenario and attacker model
• What are the sensitive objects (keys, data, functions)?
• What are these sensitive objects used for and what is the data flow of these
objects?
• What are the capabilities of the attackers (funding, tools, knowledge)?
• What are the points where an attacker can observe the system (dump of
exchanged messages, debugging, ...)?
• Which parts of the system must be trusted to achieve required functionality
(less the better)?
PV204 - Secure channel protocols83
https://crocs.fi.muni.cz @CRoCS_MUNI
SCP – network attacks
• Use HMAC or OMAC instead of simple hash only
• Include command header/metadata into MAC
• Pre-share two keys (encryption, mac) or derive from master instead of using
only one
• Use pre-shared keys only to derive session keys. Session keys are used than
to generate cryptograms etc.
• Session keys must be dependent on contributions from both parties. One party
cannot force resulting key into specific value
PV204 - Secure channel protocols84
https://crocs.fi.muni.cz @CRoCS_MUNI
SC – network attacks
• Replay attack – hash chain better than counter only
• Encrypt then MAC: MAC(ENC(data))
• Close channel on error
• Use GCM rather than CBC rather than ECB
• Be aware of block swap in ECB mode, cut attack in CBC
• Do not use XOR for combination of values – use hash/HMAC instead
• Reflection attack: Do not use symmetric protocol messages (A→B cannot be
reflected as B→A)
PV204 - Secure channel protocols85
https://crocs.fi.muni.cz @CRoCS_MUNI
ELECTRONIC PASSPORTS
- MORE DETAILS
PV204 - Secure channel protocols86
https://crocs.fi.muni.cz @CRoCS_MUNI
Authorization and passports
1. Inspection terminal to read basic info from chip
2. Inspection terminal to read biometric data from chip
3. You to enter country based on chip data
PV204 - Secure channel protocols87
https://crocs.fi.muni.cz @CRoCS_MUNI
Basic Access Control (BAC) protocol
• Authentication&secure channel between inspection terminal and chip
– Based on symmetric crypto (3DES), similar to SCP’0x protocols
– Low computational requirements
• Problem: anyone with access to MRZ can authenticate
• Problem: MRZ has insufficient entropy
– Document number, birth date, expiration date used
– Theoretically 58/74 bits, but in practice about 32 bits
• Offline attack (eavesdrop then crack)
– Eavesdrop valid communication between chip and reader
– Brute-force attack in less then hour (232 ops, offline attack)
• Online attacks against chip (att. model: found passport)
– Significantly slower, ~20 ms for every attempt
PV204 - Secure channel protocols88
https://crocs.fi.muni.cz @CRoCS_MUNI
EAC – motivation
• EU passports stores fingerprints (from 2009)
– More sensitive than facial photo => better protocol needed
• Goal: not everyone with access to passport (and MRZ for BAC)
should be able to read out fingerprint
– Issuing country decides who else can access
• Stronger authentication than BAC required
PV204 - Secure channel protocols89
https://crocs.fi.muni.cz @CRoCS_MUNI
Mind exercise: symmetric crypto
• What if only symmetric crypto is used?
– Every chip has own unique symmetric key
– Large number of keys in inspection terminals
– Compromise of single terminal breach security
– => impractical and insecure => not used
PV204 - Secure channel protocols90
https://crocs.fi.muni.cz @CRoCS_MUNI
Extended Access Control (EAC) protocol
• Based on asymmetric cryptography (RSA/DH/ECDSA)
• Chip Authentication (CA) based on PACE protocol
– Password Authenticated Connection Establishment (PACE)
– Uses chip’s static DH/ECDSA key and terminal’s ephemeral DH key pair (perfect forward secrecy)
– Both parties combines chip’s public static and ephemeral public key into same key K
– Keys for encryption and MAC (KENC, KMAC) are derived from exchanged K
• How can be Terminal sure of authenticity of chip’s static key?
– Signed by Issuing country
• Terminal Authentication (TA)
– Based on challenge-response protocol (RSA/ECDSA, SHA-1/2)
– Hash of the ephemeral DH key from previous step hashed with challenges
PV204 - Secure channel protocols91
https://crocs.fi.muni.cz @CRoCS_MUNI
Terminal authentication I.
• Only authorized border authorities can read the secondary biometric
data (fingerprints and iris)
– The inspection system must prove to the chip it is authorized
– The chip stores a trust point – root certificate
– Inspection system presents a valid certificate chain (starting from the passport’s
trust point) specifying the IS’s authorizations (e.g. to read DG3)
– Challenge-response where IS proves knowledge/access of a secret key (whose
public part is certified)
– Certificates in Card-verifiable (CV) format
PV204 - Secure channel protocols92
https://crocs.fi.muni.cz @CRoCS_MUNI
Terminal Authentication II
Country
A
Country
B
CV CA CV CA
IS
DV
IS... IS
DV
IS... IS
DV
IS...IS
DV
IS...
CV CA
Country
C
Root public key of
issuing country: CV CA
PV204 - Secure channel protocols93
https://crocs.fi.muni.cz @CRoCS_MUNI
Terminal Authentication III
• Supported algorithms
– RSA PKCS#1 v1.5 with SHA-1 or SHA-256
– RSA PSS with SHA-1 or SHA-256
– ECDSA with SHA-1, SHA-224 or SHA-256
– Key lengths
• For ECDSA allowed 160, 192, 224, 256 bits
• For RSA allowed 1024, 1280, 1536, 2048 and 3072 bits
• In practice ECDSA is more common, key lengths 192 and 224 bit most popular, existing
implementations also support 256 and 384 bits.
• For RSA the PKCS#1 v1.5 padding is much more popular than PSS, key lengths are
between 512 (test only) and 2048 bits.
PV204 - Secure channel protocols94
https://crocs.fi.muni.cz @CRoCS_MUNI
Active Authentication (AA) protocol
• Motivation: Prevent cloning of passport
– Is chip inside passport authentic?
• Passport-specific asymmetric key stored on chip
• Public key freely readable (DG15 file, hash signed)
• Authentication against terminal
– Terminal generates 8 random bytes
– Chip adds additional 8 random bytes, hash and sign
– Terminal verifies signature
• Privacy attack: terminal’s challenge is date → signed
• PACE protocol replaces Active Authentication
PV204 - Secure channel protocols95
https://crocs.fi.muni.cz @CRoCS_MUNI
EAC Chip authentication
• Verifies the authenticity of the chip
– Replaces Active Authentication
– Improves the security of Secure Messaging
• Keys with higher entropy than for Basic Access Control (BAC)
• Diffie-Hellman key pair (passport’s chip)
– Public key and domain parameters stored in DG14
– Private key never leaves the chip
• Diffie-Hellman key pair (inspection system – IS)
– Key pair generated according to passport’s domain parameters
– Private key kept secret, public key sent to chip
• Both the parties (passport, IS) now share a secret
– The secret is used to derive the SM keys, the ability to communicate proves the authenticity of the
chip
PV204 - Secure channel protocols96
https://crocs.fi.muni.cz @CRoCS_MUNI
Chip authentication II
• Algorithms supported by the EAC specification
– Diffie-Hellman (PKCS#3)
– Elliptic Curve Diffie-Hellman (ISO 15946, BSI TR-03111 )
– Both DH and ECDH popular with chip manufacturers
• DH with 1024 or 1536 bit prime
• ECDH with mostly 224 bit curves, some implementations use 256 or 384 bits
• No challenge semantics
• Coexistence of CA and AA
PV204 - Secure channel protocols97
https://crocs.fi.muni.cz @CRoCS_MUNI
Passive Authentication
• Goal: are data in chip unchanged?
• The list of the hashes (SHA-1/2)
of all present data groups is digitally
signed by the issuing organisation
(Document Signer)
– State printing house, Embassy, Etc.
• The X.509 certificate of the Document Signer issued by the CA of the issuing country (Country
Signing CA – e.g. the ministry of interior) is included.
• The CSCA certificates must be exchanged bilaterally
• ICAO PKD for DS certificates, CSCA CRL and cross certificates
• Passive authentication is a mandatory security feature of all ePassports
CSCA
DS1 DS2
ePassport 1 ePassport 2 ePassport 3
PV204 - Secure channel protocols98
https://crocs.fi.muni.cz @CRoCS_MUNI
Passive Authentication – the details
• The file EF.SOD contains a CMS (PKCS#7) SignedData structure (file is read and validated by inspection system)
– The signed data is the list of hashes of the present data groups
– The DS certificate is included (ICAO optional, EU mandatory)
– Data is signed by the DS
• Signature schemes
– RSA with PKCS#1 v1.5 padding (min. 3072 bits for CSCA, 2048 bits for DS)
• E.g. Hungary, France, Spain, Portugal, Italy: RSA 4096 bit key with SHA-1
• E.g. Austria, Netherlands: RSA 3072 bit key with SHA-256
– RSA with PSS padding (min 3072 bits for CSCA, 2048 for DS)
• E.g. Czech Republic, Norway, Denmark, Japan and Australia – all with SHA-256
– DSA (not standardized for key lengths > 1024)
– ECDSA (domain parameters must be specified, min. 256 bits for CSCA, 224 bits for DS)
• E.g. Switzerland, Germany, Russia – all with SHA-1
• Message Digest algorithms (for signature schemes and hashes of Data Groups)
– SHA-1 and all SHA-2 algorithms
PV204 - Secure channel protocols99