Private messaging ================= Goals: Security: - confidentiality - integrity - forward secrecy - backward/future secrecy - deniability - anonymity - metadata privacy - disappearing messages Features - group chat - asynchronous - support out of order messages - multiple devices - account recovery Recall: secure channels ----------------------- Seal(secretkey, msg): nonce <- $random c <- Encrypt(secretkey, nonce, msg) tag <- MAC(secretkey, nonce, msg) return nonce ++ c ++ tag Sign(ID_PrivateKey, msg) -> sig Verify(ID_PublicKey, msg, sig) -> ok? ID: shorthand for "long term key" Diffie-Hellman key exchange --------------------------- Alice: secret key a Bob: secret key b g is the generator of some group (i.e., integers mod p). A --- g^a --> B A <-- g^b --- B Alice computes: (g^b)^a = g^ab Bob computes: (g^a)^b = g^ab Shared key: g^ab Assumption: hard to compute g^ab from (g, g^a, g^b) Simple messaging scheme ----------------------- Setup: A --> B: ID_Alice_Public A <-- B: ID_Bob_Public A --> B: g^a, Sign(ID_Alice_Private, g^a) A <-- B: g^b, Sign(ID_Bob_Private, g^b) Alice and Bob: Verify sigs, compute and store g^ab. Chat (today): A --> B: Seal(g^ab, "hello bob") A <-- B: Seal(g^ab, "hey alice") Chat (tomorrow): A <-- B: Seal(g^ab, "any news?") Issues with this protocol? 1. MITM attack when Alice sends her long-term key 2. Attacker can steal secret key g^ab and decrypt messages. MITM attack ----------- Attack: replace ID_Alice_Public with ID_Eve and g^a with g^e. Defenses? How to ensure Alice gets the right public key for Bob and vice versa? - Ask Bob in person (e.g,. scan QR codes in WhatsApp). - Trust on First Use (TOFU): ssh style - Lookup key on a key server (pgp.mit.edu) - Keybase.io: use social media to confirm you got the right key - Lookup key on public ledger (NameCoin) - Identity-Based Encryption (e.g., Alpenhorn) Ongoing research area with many solutions and tradeoffs. Two interesting approaches: Keybase and IBE. Keybase ------- Users use social media to attest to their public key: github.com/davidlazar/gist: "My key is 0xyz" davidlazar.org (DNS entry): "My key is 0xyz" If you know me on github and twitter, then lookup my key based on those. Identity-Based Encryption ------------------------- Email addresses are the public key "lazard@mit.edu" No lookup necessary. PKG server hands out private keys. PKG has all private keys and can decrypt/MITM all messages! Solution: use several PKG servers. See Alpenhorn. Forward secrecy --------------- Attack: record ciphertexts, and then steal g^ab from Alice's or Bob's computer. To steal key: wait for an exploit, steal his phone, subpoena, etc... Forward secrecy: attacker can not decrypt previously sent messages by compromising your device / key. Solution: continuously refresh the keys. First attempt: DH ratchet (used in OTR) --------------------------------------- Setup: same as before; shared key = g^a0b0 A --> B: NEW(g^a1), Seal(g^a0b0, "hello bob") # MAC(g^a1, g^a0b0) A <-- B: NEW(g^b1), Seal(g^a1b0, "hey alice") # MAC(g^b1, g^a1b0) ...Alice deletes a0 A --> B: NEW(g^a2), Seal(g^a1b1, "...") # MAC(g^a2, g^a1b1) ...Bob deletes b0 A <-- B: NEW(g^b2), Seal(g^a2b1, "...") # MAC(g^b2, g^a2b1) ...Alice deletes a1 A --> B: NEW(g^a3), Seal(g^a2b2, "...") # MAC(g^a3, g^a2b2) A --> B: NEW(g^a3), Seal(g^a2b2, "...") # MAC(g^a3, g^a2b2) A --> B: NEW(g^a3), Seal(g^a2b2, "...") # MAC(g^a3, g^a2b2) Problem: MITM attack: adversary swaps NEW(g^a1) with NEW(g^evil)! Fix: include MACs using the previous keys: chain of trust can be verified all the way to g^a0b0 which was computed from signed DH. Problem: Bob goes away and doesn't ACK g^a3, so a2 and a3 stics around for a long time. This is bad for forward secrecy. Second attempt: KDF ratchet --------------------------- KDF: key derivation function, takes a key and returns 2 new keys. KDF(key) -> chain key, msg key Setup: same as before; shared key = g^ab A --> B: 0, Seal(k0, "hello bob") (c0, k0 = KDF(g^ab)) A <-- B: 1, Seal(k1, "hey alice") (c1, k1 = KDF(c0)) A <-- B: 2, Seal(k2, "...") (c2, k2 = KDF(c1)) A --> B: 3, Seal(k3, "...") (c3, k3 = KDF(c2)) MITM attack? No: trust goes back to signed g^ab through chain keys. Good forward secrecy: After message 3, Alice and Bob both delete c2, k3, so all messages are irrecoverable. Chain keys are useful if messages arrive out of order: can't get new k_i from old ones, so keep old k_i in memory and delete c_i Problem: bad "future" secrecy If attacker gets c_i, can decrypt all future messages. Future secrecy: attacker can not decrypt future messages after stealing the private key. Third attempt: double ratchet ----------------------------- DH ratchet: bad forward secrecy, good future secrecy KDF ratchet: good forward secrecy, bad future secrecy Idea: combine them: update the KDF ratchet occasionally with the DH ratchet. Setup: same as before; shared key = g^a0b0 A --> B: NEW(g^a1), 0, Seal(k0, "hello bob") (c0, k0 = KDF(g^a1b0)) A <-- B: NEW(g^b1), 0, Seal(k0, "hey Alice") (c0, k0 = KDF(g^a1b1)) A <-- B: NEW(g^b1), 1, Seal(k1, "...") (c1, k1 = KDF(c0)) A --> B: 2, Seal(k2, "...") (c2, k2 = KDF(c1)) A --> B: 3, Seal(k3, "...") (c3, k3 = KDF(c2)) KDFs provide forward secrecy. NEW DH keys provide future secrecy (heal if c_i is compromised) Lots of details missing: Extra MACs not needed (new DH keys added to another KDF chain for trust) Out of order messages See: https://signal.org/docs/specifications/doubleratchet/ Prekeys for Asynchrony ---------------------- What if Alice or Bob goes offline? Might not be around to generate new DH keys, or sign things. Can we still send messages? Idea: upload fresh g^b0 ... g^b100 to the server before going offline. Users can ask the server for one of these keys if you are offline, encrypt the message with the key, and store message on the server. See: https://signal.org/blog/asynchronous-security/ Deniability ----------- Signatures are "ironclad" proof of who said what; it'd be like if everyone wore a microphone all the time. Undesirable. Can we authenticate users but still have deniability? So that Bob knows he's talking to Alice, but can't prove that Alice said anything in particular. Idea: replace signatures (where only one side has the private key) with MACs. Both sides have same key, so one of them could have forged the message. Previous schemes used MACs for convo messages, but keys could always be traced back to signed DH handshake. So no deniability. Triple DH handshake ------------------- Alice longterm key: g^A (secret key = A) Bob longterm key: g^B (secret key = B) A --> B: g^A, g^a0 A <-- B: g^B, g^b0 Both compute: g^a0b0, g^Ab0, g^a0B Shared secret = KDF(g^a0b0 || g^Ab0 || g^a0B) Secure: can't compute secret without A or B. Deniable: no signatures; anyone can come along and compute a shared secret: make up g^a, combine with g^A and your own g^C and g^c See Signal blog post for details: https://whispersystems.org/blog/simplifying-otr-deniability/ Metadata privacy ---------------- Private Information Retrieval (PIR) ----------------------------------- Server has database of messages; user wants one message from DB without revealing which one. Doable with just 1 server! Easier to see with multiple servers. 3 servers, s1,s2,s3 each has the same DB with 3 messages: m1,m2,m3. User sends mask to each server: mask1 = 011 (random) mask2 = 101 (random) mask3 = 100 mask3 computed so that mask1 xor mask2 xor mask3 = 010 1 bit only in the position of the DB user wants to access. mask3 still indistinguishable from random. s1 gets mask 011; returns r1 = m2 xor m3 s2 gets mask 101; returns r2 = m1 xor m3 s3 gets mask 100; returns r3 = m1 xor results together: r1 xor r2 xor f3 = m2 (other messages cancel out!) Secure: if at least one of s1,s2,s3 is honest (doesn't reveal mask), then perfect privacy. DC-nets ------- Scenario: N users, 1 of them wants to send 1 bit. Users A, B, C: Shared secrets: k_AB, k_AC, k_BC One of them wants to send a 1 bit message msg, everyone else sends 0. A sends: k_AB xor k_AC xor msg_A B sends: k_AB xor k_BC xor msg_B C sends: k_AC xor K_BC xor msg_C Only one of msg_A or msg_B or msg_C can be 1. Security: Sender hides among the users that are honest (don't collude/reveal their secrets). Like PIR, perfect privacy (one-time pad); no crypto. Problems: what if multiple users send at the same time? longer messages. See Diesent. Mixnets ------- Chain of servers; messages are onion encrypted to force them to go in the order of the chain. Each chain removes layer of onion; shuffles; and gives messages to next server in the chain. Last server sends messages to users. Private if one server is honest and hides the shuffle, but still several attacks: Duplicate messages, drop messages. Solution: dead drops, noise. See Vuvuzela.