AKE Notes

You                                                 Friend
 \              {   I N T E R N E T   }             /
  ()---[]------[]--------[]------Z ? 7-----[]------() 

1. Encryption!

Symmetric encryption:
    AES / ChaCha / 3DES / MORUS / NORX / Deoxys-II / etc.
    Secure constructions of encryption
        (AEAD) Authenticated Encryption with Associated Data
        AES-GCM, AES-GCM-SIV, XChaCha-Poly1305

    aead_encrypt(message, key) \___ SAME KEY
    aead_decrypt(message, key) /

How to exchange keys over an untrusted medium?

2. Key encapsulation!

Diffie-Hellman Key Agreement Protocol

• Classical a.k.a. FFDH
• Elliptic Curve a.k.a ECDH
• Supersingular isogeny-based Diffie-Hellman (SIDH)

Example:

    FFDH
     - g = 2,3,5 ... constant chosen ahead of time
     - [1, p) for some large prime, p
    
    Fox:
     - large random prime between 1 and p -> FoxSecretKey
     - (g ** FoxSecretKey) % p -> WolfPublicKey
    
    Wolf:
     - large random prime between 1 and p -> WolfSecretKey
     - (g ** WolfSecretKey) % p -> WolfPublicKey
    
    FFDH Key Exchange:
        Fox:
            (g ** (FoxSecretKey * WolfPublicKey)) % p
            -> SharedPrivateKey
        Wolf:
            (g ** (WolfSecretKey * FoxPublicKey)) % p
            -> SharedPrivateKey
    
    Secret  -> Nobody else can know (Keep to yourself)
    Private -> Don't want the world to know 
               (Limited sharing of information)

However...

3. Public Key Infrastructure (PKI)

• Certificate Authorities (We certify that [public key] is bound to [identity] for [duration]) (Signed by a pre-determined set of authorities with known public keys)
  • Centralized to a finite set of authorities
• "Web of Trust" PGP Model Mostly security theater, nobody actually bothers with checking this
  • Decentralized in theory, federated in practice
• "Notary Model" (my term, not the industry's)
  • Relies on cryptographic ledgers
  • Verifiable Data Structures
    • Hash tree (a.k.a. Merkle tree)
    • Hash chains
    • Cryptographic hash functions
    • Verifiable delay functions (VDFs)
  • Centralized or decentralized publishing
  • Always decentralized verification (or federated if you want it)
  • Publish [identifier, public key] -> {point in time}
    • This gets mirrored into other places
      • Mirrors always verify hashes when replicating
  • Parse the chain
    • add/remove [identifier, public key] pairs
  • Verify that other participants see the same "summary hash" at a given T value (number of records), you can authenticate the entire dataset (so long as H(x) is secure)
  • DOES NOT NEED ANY PROOF OF WORK ALGORITHM!!!

Aside: Bitcoin proof of work (very early and inefficient VDF)

  H(x) = SHA256d(x) === SHA256(SHA256(x))

  Try to find some value such that SHA256d(yourAddress || random)
  starts with a specific number of 0s (in hex)

  Number of prefixed 0s is set by network consensus to ensure it always
  takes an average of 10 minutes per block

  Not necessary for a notary-based PKI.
  (Some people feel more comfortable if hashes are cross-signed onto one
  or more cryptocurrency ledgers.)

4. Authenticated Key Exchange

a.k.a. Using 2 with 3.

Bad idea:

<?php
$ciphertext = $api->encrypt($message, $identityPublicKey);

Cons:

• No key compromise protection

Better idea:

<?php

[$ephSecret, $ephPublic] = $api->generateEcdhKeypair();
$ecdh = $api->ecdh($ephSecret, $theirPublic);
$ciphertext = $api->encrypt($message, $ecdh);
sodium_memzero($ecdh);
$signed = $api->sign($ephPublic, $myIdentitySecret);

[$signed, $ciphertext];

Cons:

• Only protects if sender's secret key is compromised

Good idea:

Preamble

1. Generate some number of session ECDH keys. Sign their public
   components with your identity key. Publish the bundle of signed
   ephemeral public keys with your identiy key. (100 is what Signal does)
2. Take one, and use that in the "better idea" protocol instead of
   the identity public key.
3. When you reconnect, generate and publish more session public keys.

If sender is compromised, some protection (forward secrecy). If recipient is compromised, some protection (forward secrecy).