Skip to content

Key Rotation

Key Rotation

  • Update keys whenever there is a change or message

INIT Keys:
- Handled by the Delivery Service
- This contains data to a Public Key where we can use to encrypt data to them

TreeKEM

  • Uses left balancing Binary Tree of Asymmetric Public Keys
  • All of the Group Members are leafs.
  • All of the Children of the tree know the Private keys of corresponding Asymmetric Public Keys.
    • In the Example Below User C Has the private keys for H, J, and K
Key K ├── Key J │ ├── Key G │ │ ├── Key A (User A) │ │ └── Key B (User B) │ └── Key H │ ├── Key C (User C) │ └── Key D (User D) └── Key I ├── Key E (User E) └── Key F (User F)

INIT Operation

  1. We initialize the tree with all of the members for the group.
  2. When a member is Online they initiate a update.
    • For Example if A is Online then They update G,J,K

ADD Operation

  1. Add a User to the tree
    • The Second member that joins makes a single root with two leaves. Example {"G": [A,B]}
    • The Third member that joins is added to the right. Example {"K": {"J": [A,B], I}}
  2. Then the new user does an update
    • The I user updates the K key and sends it encrypted with the J key.

Update Operation

  1. User F Updates his key
  2. This then is hashed and sent to the I node
  3. Since the I node is updated this is then sent to the K node
  4. Now to update this to the rest of the group you send a message to the J Group and the User E
    • This uses 2 operations instead of 5

Remove Operation

  1. User D is removed
  2. All notes that D has the private key for are removed.
    • This means H, J, K
  3. Any User does an update to generate the tree

Why?
- Sending a Message
- Old Way: Encrypting 1kb message to 100K users takes 100Mb and 100K operations
- New Way: Encrypting 1kb message to 100K users takes 1kb and 1 operation. (Uses Root Key)
- Updating Keys
- Old Way: Making a new key to 100K users takes 100K operations
- New Way: Making a new key to 100K users takes 17 operations. (Updates Sub keys)
- Removing a new User
- Old Way: All User regenerate all keys. Takes O(N)
- New Way: User updates tree with sub keys.
- Adding a new User
- Old Way: New user needs to make 100K keys for 100K users
- New Way: New user needs to make 17 keys for 100K users