MLS Subgroups
draft-mcmillion-mls-subgroups-00

Messaging Layer Security                                    B. McMillion
Internet-Draft                                             20 March 2024
Intended status: Informational                                          
Expires: 21 September 2024

                             MLS Subgroups
                    draft-mcmillion-mls-subgroups-00

Abstract

   This document describes how the user of an MLS-based messaging
   service can synchronize the operation of its devices, such that they
   behave as a single virtual MLS client.  This prevents other users of
   the messaging service from being able to tell when a user changes its
   set of authorized devices, or which device the user sent a message
   from.

About This Document

   This note is to be removed before publishing as an RFC.

   The latest revision of this draft can be found at
   https://Bren2010.github.io/draft-subgroups/draft-mcmillion-mls-
   subgroups.html.  Status information for this document may be found at
   https://datatracker.ietf.org/doc/draft-mcmillion-mls-subgroups/.

   Discussion of this document takes place on the Messaging Layer
   Security Working Group mailing list (mailto:mls@ietf.org), which is
   archived at https://mailarchive.ietf.org/arch/browse/mls/.  Subscribe
   at https://www.ietf.org/mailman/listinfo/mls/.

   Source for this draft and an issue tracker can be found at
   https://github.com/Bren2010/draft-subgroups.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

McMillion               Expires 21 September 2024               [Page 1]
Internet-Draft                MLS Subgroups                   March 2024

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on 21 September 2024.

Copyright Notice

   Copyright (c) 2024 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.  Code Components
   extracted from this document must include Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Conventions and Definitions . . . . . . . . . . . . . . . . .   3
   3.  Generation of Private Keys  . . . . . . . . . . . . . . . . .   4
     3.1.  Secret Tree . . . . . . . . . . . . . . . . . . . . . . .   4
     3.2.  Private Keys  . . . . . . . . . . . . . . . . . . . . . .   5
     3.3.  Subgroup Extension  . . . . . . . . . . . . . . . . . . .   5
   4.  Application Messages  . . . . . . . . . . . . . . . . . . . .   6
     4.1.  Small-Space PRP . . . . . . . . . . . . . . . . . . . . .   7
     4.2.  Reuse Guard . . . . . . . . . . . . . . . . . . . . . . .   7
   5.  Adding New Devices  . . . . . . . . . . . . . . . . . . . . .   7
     5.1.  Synchronizing from Another Device . . . . . . . . . . . .   8
     5.2.  Joining Externally  . . . . . . . . . . . . . . . . . . .   9
   6.  Aligning Security of Groups . . . . . . . . . . . . . . . . .  10
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  10
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  10
     8.1.  MLS Extension Types . . . . . . . . . . . . . . . . . . .  10
     8.2.  MLS Exporter Labels . . . . . . . . . . . . . . . . . . .  10
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  10
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .  11
     9.2.  Informative References  . . . . . . . . . . . . . . . . .  11
   Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  11
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  11

McMillion               Expires 21 September 2024               [Page 2]
Internet-Draft                MLS Subgroups                   March 2024

1.  Introduction

   MLS allows users to communicate in an end-to-end encrypted fashion
   but doesn't describe how to synchronize the operation of a user's
   devices.  Instead, applications are generally expected to create
   distinct MLS clients for each device that a user has, and to ensure
   that all of the user's devices are added or removed from a group
   atomically.  This creates some technical difficulties, as it can be
   hard for other members to ensure that the group truly stays in-sync
   with each user's set of authorized devices.  It also creates a
   privacy issue because the members of a group can see which device a
   user sent a given message from, or when any user changes its set of
   authorized devices.

   This document describes how to use an MLS group between all of a
   user's authorized devices to synchronize behavior, such that other
   users of the messaging service only see the user as a single MLS
   client.  It does this in a way that preserves the Forward Secrecy and
   Post-Compromise Security guarantees of the groups that the user
   participates in, without requiring changes to the wire format of MLS.

2.  Conventions and Definitions

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in
   BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here.

   Device:  A user interface for messaging, performing encryption as
      needed.

   User:  A (normally) human operator of a device.  Users may have many
      devices, but a device only belongs to one user.

   Subgroup:  An MLS group whose membership is exactly the set of
      authorized devices of a single user.

   Virtual Client:  An MLS client that is controlled by one of many
      devices and synchronized by a subgroup.

   Supergroup:  Refers to any MLS group which is not a subgroup.

McMillion               Expires 21 September 2024               [Page 3]
Internet-Draft                MLS Subgroups                   March 2024

3.  Generation of Private Keys

   When devices generate new asymmetric keypairs for a virtual client
   (such as a KeyPackage init_key or LeafNode encryption_key), they must
   do so in a way that the other devices participating in the subgroup
   can compute the private key as well.  In the Subgroups protocol, a
   virtual client's private keys are derived deterministically from a
   secret exported from the most recent epoch in a subgroup.  An
   extension is added to KeyPackages and LeafNodes generated this way to
   communicate to the other devices, which may not become aware of the
   keypair for several epochs, the epoch the private key was generated
   from.

   Note that signature private keys are not generated this way.  A
   virtual client's signature private key is generated once and shared
   directly with new devices.

3.1.  Secret Tree

   The Subgroups protocol uses a Secret Tree similar to [RFC9420].  The
   root of the Secret Tree is an exported secret from a given epoch of a
   subgroup:

   subgroup_secret_tree_root
       = MLS-Exporter("Subgroup Secret Tree", "", KDF.Nh)

   The left and right child of a node in the Secret Tree are computed as
   follows:

   tree_node_[N]_secret
           |
           |
           +--> ExpandWithLabel(., "tree", "left", KDF.Nh)
           |    = tree_node_[left(N)]_secret
           |
           +--> ExpandWithLabel(., "tree", "right", KDF.Nh)
                = tree_node_[right(N)]_secret

   The Secret Tree maps bit strings to a value of size KDF.Nh.  The
   root, subgroup_secret_tree_root, is the value associated with the
   empty bit string.  Its left child is the value associated with the
   bit string "0", while its right child is the value associated with
   the bit string "1", and so on recursively.

   Devices follow a strict deletion schedule, and delete any node as
   soon as:

   *  its left and right children have been computed, or

McMillion               Expires 21 September 2024               [Page 4]
Internet-Draft                MLS Subgroups                   March 2024

   *  a private key has been derived from the node.

   This ensures that any private keys that are derived from the Secret
   Tree can be deleted and won't be able to be re-derived, providing
   Forward Secrecy.

3.2.  Private Keys

   Devices will need to generate either an init_key for a KeyPackage, or
   an encryption_key for a LeafNode.  To do this, the device finds its
   leaf index in the subgroup leaf_index, chooses a 32-bit number
   random, converts both to a series of bits, and concatenates them to
   get a series of 64 bits: leaf_index || random.  This series of bits
   is used to lookup a node in the Secret Tree, tree_node_secret.

   For a KeyPackage init_key, the device computes:

   init_secret = DeriveSecret(tree_node_secret, "Subgroup KeyPackage")
   init_priv, init_pub = KEM.DeriveKeyPair(init_secret)

   For a LeafNode encryption_key, the device computes:

   leaf_secret = DeriveSecret(tree_node_secret, "Subgroup LeafNode")

   leaf_node_secret = DeriveSecret(leaf_secret, "node")
   leaf_priv, leaf_pub = KEM.DeriveKeyPair(leaf_node_secret)

   If the LeafNode is part of a Commit message, the device also computes
   path_secret[0] from leaf_secret:

   path_secret[0] = DeriveSecret(leaf_secret, "path")

   Individual devices MUST take care to avoid reusing random values.
   Note that the Secret Tree nodes are computed with the subgroup
   ciphersuite's algorithms, but init_secret and leaf_secret are
   computed with the supergroup ciphersuite's algorithms.

3.3.  Subgroup Extension

   As mentioned, devices may not always be immediately aware of when
   another device has generated a private key.  This means that devices
   need a way to communicate to each other the information they used to
   derive a private key.  The subgroup extension in a KeyPackage or
   LeafNode provides this information:

McMillion               Expires 21 September 2024               [Page 5]
Internet-Draft                MLS Subgroups                   March 2024

   struct {
     uint64 epoch;
     uint32 leaf_index;
     uint32 random;
   } PrivateKeyInfo;

   opaque subgroup<V>;

   The extension is a byte string containing a PrivateKeyInfo struct,
   which has been encrypted with the AEAD from the subgroup's
   ciphersuite:

   nonce is sampled at random
   subgroup = nonce || AEAD.Seal(key, nonce, "", PrivateKeyInfo)

   The epoch field is the epoch of the subgroup that was used,
   leaf_index is the index of the device's leaf in the subgroup, and
   random is the random value chosen by the device during generation.

   The key used for encryption is fixed long-term and shared among the
   devices in a subgroup.

4.  Application Messages

   Given that MLS generates the encryption keys and nonces for
   application and handshake messages sequentially, but a virtual client
   may send messages from several devices simultaneously, devices must
   take care to avoid reusing encryption keys and nonces.

   If two devices encrypt a message with the same key simultaneously,
   they may have already deleted the relevant encryption key by the time
   they receive the other device's message, which will cause a
   decryption failure.  This is a functional issue, and the best
   solution depends on whether the Delivery Service is strongly or
   eventually consistent [I-D.ietf-mls-architecture].  Devices
   communicating with a strongly consistent DS can prevent this issue by
   checking that they have processed all the messages sent to a group
   before sending their own message.  Alternatively, devices
   communicating with an eventually consistent DS may simply need to
   retain encryption keys for a short period of time after use in case
   they are still necessary.

   However, if two devices encrypt a message with both the same key and
   nonce simultaneously, this could compromise the message's
   confidentiality and integrity.  Devices prevent this by ensuring two
   devices in a subgroup never choose the same reuse_guard.

McMillion               Expires 21 September 2024               [Page 6]
Internet-Draft                MLS Subgroups                   March 2024

4.1.  Small-Space PRP

   A small-space pseudorandom permutation (PRP) is a cryptographic
   algorithm that works similar to a block cipher, while also being able
   to adhere to format constraints.  In particular, it is able to
   perform a psuedorandom permutation over an arbitrary input and output
   space.

   This document uses the FF1 mode from [NIST] with the input-output
   space of 32-bit integers, instantiated with AES-128.

   output = SmallSpacePRP.Encrypt(key, input)
   input = SmallSpacePRP.Decrypt(key, output)

4.2.  Reuse Guard

   In the unmodified MLS protocol, the reuse_guard is chosen randomly.
   In the Subgroups protocol, devices choose a random value x such that
   x modulo the number of leaves in the subgroup is equal to its
   leaf_index.  They then calculate:

prp_key = ExpandWithLabel(key_schedule_nonce, "reuse guard", leaf_secret, 16)
reuse_guard = SmallSpacePRP.Encrypt(prp_key, x)

   ExpandWithLabel is computed with the subgroup ciphersuite's
   algorithms. key_schedule_nonce is the nonce provided by the key
   schedule for encrypting this message, and leaf_secret is the secret
   corresponding to the virtual client's LeafNode in the supergroup.

   prp_key is computed in a way that it is unique to the key-nonce pair
   and computable by all the devices in a subgroup (but nobody else).
   reuse_guard is computed in a way that it appears random to outside
   observers (in particular, it does not leak which device sent the
   message), but two devices will never generate the same value.

5.  Adding New Devices

   When a user adds a new authorized device to their account, there are
   several pieces of cryptographic state that need to be synchronized
   before the device can start sending and receiving messages.  The
   device can either get this state from another one of the user's
   devices, or if all of the user's other devices are offline, the
   device can use a series of external joins to prepare itself.

McMillion               Expires 21 September 2024               [Page 7]
Internet-Draft                MLS Subgroups                   March 2024

5.1.  Synchronizing from Another Device

   If the new device is being added by another online device, this
   device sends a Welcome message to the new device, adding the new
   device to the subgroup, that contains a new_device_state extension in
   the GroupInfo:

   opaque MLSState<V>;

   enum {
     reserved(0),
     empty(1),
     present(2),
   } SecretTreeNodeType;

   struct {
     SecretTreeNodeType node_type;
     select(SecretTreeNode.node_type) {
       case empty:
         SecretTreeNode left;
         SecretTreeNode right;
       case present:
         opaque value<V>;
     }
   } SecretTreeNode;

   struct {
     uint64 epoch;
     SecretTreeNode root;
   } EpochSecretTree;

   struct {
     KeyPackageRef ref;
     opaque init_secret<V>;
     opaque leaf_secret<V>;
   } KeyPackageKey;

   struct {
     opaque signature_private_key<V>;
     opaque subgroup_extension_key<V>;
     EpochSecretTree secret_trees<V>;
     KeyPackageKey key_package_keys<V>;
     MLSState group_states<V>;
   } NewDeviceState;

   The signature_private_key contains the serialized signature private
   key of the virtual client.  Every device and virtual client SHOULD
   have distinct signature keys.  The subgroup_extension_key is the

McMillion               Expires 21 September 2024               [Page 8]
Internet-Draft                MLS Subgroups                   March 2024

   encryption key for the subgroup extension (Section 3.3).  The
   secret_trees array contains the serialized Secret Trees for any
   epochs where they may still be necessary.  The key_package_keys array
   contains the init_secret and leaf_secret for any KeyPackages that are
   still unused but have been purged from the Secret Tree.  And finally,
   the group_states array contains the cryptographic states of all the
   groups that the virtual client is a member of, serialized in an
   application-specific way.

5.2.  Joining Externally

   Without another online device to bootstrap from, the new device can
   follow these steps to join externally:

   1.  Issue a credential for the virtual client with a new signature
       key and generate a new subgroup extension key.

   2.  Perform an External Join to the subgroup.  Send an application
       message containing a ResyncMessage to the subgroup with the new
       keys.

   3.  Replace all unused KeyPackages with new KeyPackages, generated
       from the new subgroup epoch.

   4.  Perform an External Join to all of the groups that the virtual
       client is a member of, using LeafNodes generated from the new
       subgroup epoch.  Welcome messages which were unprocessed by the
       offline devices are discarded, and these groups are Externally
       Joined instead (potentially being queued for user approval
       first).

   struct {
     opaque signature_private_key<V>;
     opaque subgroup_extension_key<V>;
   } ResyncMessage;

   Note that this involves changing the subgroup extension key.  Devices
   that were in the subgroup before the new device joined externally can
   determine whether to use the new or old subgroup extension key by
   checking whether the new or old credential is in the relevant
   LeafNode.

   Also note that the new device learns the set of groups that the
   virtual client is a member of, including groups corresponding to
   unprocessed Welcome messages, from the Delivery Service, which has
   access to this information as part of supporting External Joins.

McMillion               Expires 21 September 2024               [Page 9]
Internet-Draft                MLS Subgroups                   March 2024

6.  Aligning Security of Groups

   Subgroups deprive supergroup members of visibility into whether key
   rotation is happening on a regular basis, and the extent to which
   compromised devices may have access to group secrets.  As such,
   subgroups need to enforce policies that manage this concern.

   A subgroup MUST have either the same or a stronger policy on how
   frequently devices must update their leaf node, than the groups that
   the virtual client is a member of.

   Any time that a device is removed from a subgroup, an Update (or
   Commit with path populated) MUST be sent to all groups that the
   virtual client is a member of.

7.  Security Considerations

   TODO Security

8.  IANA Considerations

   This document defines two new MLS Extension Types, and a new MLS
   Exporter Label.

8.1.  MLS Extension Types

         +========+==================+============+===+==========+
         | Value  | Name             | Message(s) | R | Ref      |
         +========+==================+============+===+==========+
         | 0x0006 | subgroup         | LN, KP     | - | RFC XXXX |
         +--------+------------------+------------+---+----------+
         | 0x0007 | new_device_state | GI         | - | RFC XXXX |
         +--------+------------------+------------+---+----------+

                                  Table 1

8.2.  MLS Exporter Labels

           +========================+=============+===========+
           | Label                  | Recommended | Reference |
           +========================+=============+===========+
           | "Subgroup Secret Tree" | -           | RFC XXXX  |
           +------------------------+-------------+-----------+

                                 Table 2

9.  References

McMillion               Expires 21 September 2024              [Page 10]
Internet-Draft                MLS Subgroups                   March 2024

9.1.  Normative References

   [NIST]     Dworkin, M., "Recommendation for Block Cipher Modes of
              Operation: Methods for Format-Preserving Encryption",
              n.d.,
              <https://nvlpubs.nist.gov/nistpubs/SpecialPublications/
              NIST.SP.800-38G.pdf>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/rfc/rfc2119>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

   [RFC9420]  Barnes, R., Beurdouche, B., Robert, R., Millican, J.,
              Omara, E., and K. Cohn-Gordon, "The Messaging Layer
              Security (MLS) Protocol", RFC 9420, DOI 10.17487/RFC9420,
              July 2023, <https://www.rfc-editor.org/rfc/rfc9420>.

9.2.  Informative References

   [I-D.ietf-mls-architecture]
              Beurdouche, B., Rescorla, E., Omara, E., Inguva, S., and
              A. Duric, "The Messaging Layer Security (MLS)
              Architecture", Work in Progress, Internet-Draft, draft-
              ietf-mls-architecture-12, 3 March 2024,
              <https://datatracker.ietf.org/doc/html/draft-ietf-mls-
              architecture-12>.

Acknowledgments

   TODO acknowledge.

Author's Address

   Brendan McMillion
   Email: brendanmcmillion@gmail.com

McMillion               Expires 21 September 2024              [Page 11]