Network Working Group                                            K. Rose
Internet-Draft                                                J. Holland
Intended status: Experimental                  Akamai Technologies, Inc.
Expires: January 9, 2020                                   July 08, 2019


                Asymmetric Loss-Tolerant Authentication
                       draft-krose-mboned-alta-01

Abstract

   Establishing authenticity of a stream of datagrams in the presence of
   multiple receivers is naively achieved through the use of per-packet
   asymmetric digital signatures, but at high computational cost for
   both senders and receivers.  Timed Efficient Stream Loss-Tolerant
   Authentication (TESLA) instead employs relatively cheap symmetric
   authentication, achieving asymmetry via time-delayed key disclosure,
   while adding latency to verification and imposing requirements on
   time synchronization between receivers and the sender to prevent
   forgery.  This document introduces Asymmetric Loss-Tolerant
   Authentication (ALTA), which employs an acyclic graph of message
   authentication codes (MACs) transmitted alongside data payloads, with
   redundancy to enable authentication of all received payloads in the
   presence of certain patterns of loss, along with regularly paced
   digital signatures.  ALTA requires no time synchronization and
   enables authentication of payloads as soon as sufficient
   authentication material has been received.

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/.

   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 January 9, 2020.







Rose & Holland           Expires January 9, 2020                [Page 1]


Internet-Draft                    ALTA                         July 2019


Copyright Notice

   Copyright (c) 2019 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 Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Conventions and Definitions . . . . . . . . . . . . . . . . .   4
   3.  Protocol Overview . . . . . . . . . . . . . . . . . . . . . .   4
   4.  Protocol Details  . . . . . . . . . . . . . . . . . . . . . .   6
     4.1.  ALTA Payload  . . . . . . . . . . . . . . . . . . . . . .   6
       4.1.1.  Authentication Tag  . . . . . . . . . . . . . . . . .   7
     4.2.  Digital Signature . . . . . . . . . . . . . . . . . . . .   8
       4.2.1.  Application Data  . . . . . . . . . . . . . . . . . .   8
     4.3.  Scheme Construction . . . . . . . . . . . . . . . . . . .   8
   5.  ALTA Configuration  . . . . . . . . . . . . . . . . . . . . .   9
     5.1.  Performance Considerations  . . . . . . . . . . . . . . .   9
       5.1.1.  MAC selection . . . . . . . . . . . . . . . . . . . .   9
       5.1.2.  Digital signature selection . . . . . . . . . . . . .   9
     5.2.  Out-of-band Metadata  . . . . . . . . . . . . . . . . . .   9
   6.  Operational Considerations  . . . . . . . . . . . . . . . . .   9
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .   9
     7.1.  Parsing an ill-formed or inconsistent payload . . . . . .   9
     7.2.  Index overflow  . . . . . . . . . . . . . . . . . . . . .   9
     7.3.  Truncated MACs  . . . . . . . . . . . . . . . . . . . . .   9
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   9
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   9
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .   9
     9.2.  Informative References  . . . . . . . . . . . . . . . . .   9
   Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  10
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  10

1.  Introduction

   Authenticity of streaming data may be inexpensively established via
   symmetric message authentication codes (MACs) using keys pre-shared
   exclusively between two parties, as the receiver knows it did not



Rose & Holland           Expires January 9, 2020                [Page 2]


Internet-Draft                    ALTA                         July 2019


   originate the data and that only one other party has access to the
   key.  In the presence of multiple receivers, however, this is not
   possible because all receivers must have access to the same key,
   giving any one of them the ability to forge messages.  Consequently,
   authentication must be made asymmetric, such that only the sender has
   the ability to produce messages that correct receivers will verify as
   authentic.

   Naively, a sender may sign individual datagrams using an asymmetric
   digital signature algorithm, such as RSA or Ed25519, but this carries
   high computational cost for both the sender and receivers.  In the
   case of streaming video delivery, while the sender's computational
   load may be dominated by CPU-intensive video encoding, the receiver
   is often a device with hardware dedicated to efficient video decoding
   and with limited general purpose computing hardware and/or battery
   available for high-rate digital signature authentication.

   Timed Efficient Stream Loss-Tolerant Authentication (TESLA) [RFC4082]
   addresses this problem through the use of symmetric authentication by
   delaying the release of keying material to a deadline at which any
   packets protected by said key that are subsequently received must be
   discarded by a receiver.  While this reintroduces asymmetry between
   sender and receiver, it requires the sender and each receiver to
   (loosely) synchronize clocks and imposes authentication latency
   relative to RTT and to a pre-declared upper bound on clock skew.

   Clock synchronization is not as trivial as it appears: internet-
   connected hosts often have significant clock skew relative to stratum
   0 NTP servers [timeskew], and anyway enterprises serving valuable
   assets do not regard NTP as a reliable interdomain security protocol.
   Together with the need to avoid attacks that delay packets required
   for synchronization, this implies the need for an interactive unicast
   authenticated clock synchronization protocol, which is complicated by
   the need to maintain clock synchronization across both the stream
   publisher and multiple geographically-distributed nodes in a content
   delivery network (CDN).

   This document introduces Asymmetric Loss-Tolerant Authentication
   (ALTA), which eschews time synchronization for an application of
   digital signatures to an acyclic graph of symmetric message
   authentication codes with redundancy sufficient to tolerate certain
   patterns of loss, and with digital signature authentication load
   greatly reduced relative to the naive approach.  This algorithm is
   based on research by Golle and Modadugu, as published in [STRAUTH].
   Live multicast streaming over an unreliable transport is the intended
   application for ALTA: object-based integrity solutions or transport
   security may be more appropriate for unicast transmission or for
   static objects pulled on-demand.



Rose & Holland           Expires January 9, 2020                [Page 3]


Internet-Draft                    ALTA                         July 2019


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.

3.  Protocol Overview

   ALTA is intended for streaming datagram use cases in which the
   receiving application has a deadline for the utility of received data
   and can tolerate a degree of random packet loss.  It combines a
   segment of application data with a variable-length authentication tag
   into an ALTA payload to be sent as a unit in a single datagram, with
   the authentication tags constructed in such a way that a receiver
   will be able to authenticate nearly all such ALTA payloads received
   by the deadline under certain patterns of random packet loss.

   An authentication tag is a combination of zero or more symmetric
   message authentication codes (MACs) and either zero or one digital
   signature.  Each MAC is of another ALTA payload in the stream, while
   the digital signature is of the containing ALTA payload with the
   signature field itself replaced by all zeroes.

   The MACs included in a given authentication tag are determined by a
   scheme, as defined in section 3 of [STRAUTH].  Conceptually, a scheme
   is a mostly backward-looking directed acyclic graph of ALTA payloads
   such that the MAC of a given payload is contained in two or more
   other payloads in the stream, enabling the loss of one of these to be
   tolerated without losing the ability to authenticate the given
   payload.

   For purposes of illustration, a simple example scheme is one in which
   the ith ALTA payload's authentication tag contains MACs for the
   (i-1)th and (i-2)th payload:















Rose & Holland           Expires January 9, 2020                [Page 4]


Internet-Draft                    ALTA                         July 2019


                                                 .
                                                 .
                                                 .
   +-------------+------+                        |
   | payload i+1 | MACs |                        |
   |             |      |                        |
   |             |   i <---------------------+   |
   |             | i-1 <-----------------+   |   |
   +---------+---+------+                |   |   |
             |                    +----------+---------+
             +------------------->| MAC of payload i+1 |
                                  +--------------------+
   +-------------+------+                |   |
   | payload i   | MACs |                |   |
   |             |      |                |   |
   |             | i-1 <-----------------+   |
   |             | i-2 <-------------+   |   |
   +---------+---+------+            |   |   |
             |                    +--------+---------+
             +------------------->| MAC of payload i |
                                  +------------------+
   +-------------+------+            |   |
   | payload i-1 | MACs |            |   |
   |             |      |            |   |
   |             | i-2 <-------------+   |
   |             | i-3 <--------+    |   |
   +---------+---+------+       |    |   |
             |                  | +----+-+-------------+
             +------------------->| MAC of payload i-1 |
                                | +--------------------+
   +-------------+------+       |    |
   | payload i-2 | MACs |       |    |
   |             |      |       |    |
   |             | i-3 <--------+    |
   |             | i-4 <----+   |    |
   +---------+---+------+   |   |    |
             |              |   | ++-+-----------------+
             +------------------->| MAC of payload i-2 |
                            |   | +--------------------+
                            |   |
                            |   |
                            .   .
                            .   .
                            .   .

   The recommended scheme is more complex and will be covered in detail
   in Section 4.3.




Rose & Holland           Expires January 9, 2020                [Page 5]


Internet-Draft                    ALTA                         July 2019


   Encoding a scheme relies on ALTA payloads being addressable
   deterministically by an index even in the presence of reordering or
   loss.  This index may be deduced from the application data (e.g.,
   making use of an existing sequence number) or by a payload index
   explicitly encoded in the authentication tag.  Two modes are
   supported:

   o  If the index starts at zero and increments by exactly one for each
      payload in the stream, and if the scheme is known to both sender
      and receiver, then indices are not required to be encoded for each
      MAC in an authentication tag as they can be deduced from a given
      payload's index and from the DAG associated with the scheme.
      Hereafter, this is referred to as _implicit offset mode_.

   o  If the index increments unpredictably, or if the scheme is not
      known to the receiver, then each MAC in an authentication tag must
      be paired with the explicit index of the ALTA payload from which
      the MAC is computed.  For compactness, this index will be encoded
      as an offset relative to the index of the containing payload.
      Hereafter this is referred to as _explicit offset mode_.

   Authenticity of a payload is established by a chain of MACs rooted in
   an ALTA payload whose authentication tag contains a digital signature
   created by a key in which trust has been established out-of-band.
   Delivery of application data must be delayed until a payload has been
   authenticated.  Note that a given payload may be authenticated by a
   digital signature as well as by one or more MAC chains; within
   authentication deadline constraints, receivers should prefer to
   authenticate by MAC, minimizing the computational load imposed by
   digital signature authentication.

   The variable length of authentication tags in ALTA has implications
   for application data segmentation when constant-length datagrams are
   desired (e.g., to maximize data per UDP packet with a given path MTU
   while avoiding fragmentation).

4.  Protocol Details

4.1.  ALTA Payload

   An ALTA payload comprises the following elements (defined below)
   concatenated in-order:

   o  Authentication tag

      *  Options octet

      *  Optional payload index



Rose & Holland           Expires January 9, 2020                [Page 6]


Internet-Draft                    ALTA                         July 2019


      *  Sequence of chained MACs

      *  Optional digital signature

   o  Application data

4.1.1.  Authentication Tag

   The authentication tag is the metadata emitted by an ALTA-compliant
   sender that is required, in combination with other out-of-band
   metadata, by an ALTA-compliant receiver to authenticate a stream of
   packets in a manner tolerant to loss and reordering.

4.1.1.1.  Options Octet

    0 1 2 3 4 5 6 7
   +-+-+-+-+-+-+-+-+
   |MACct|S| rsvd  |
   +-+-+-+-+-+-+-+-+

                          Figure 1: Options Octet

   The first octet of the authentication tag contains the count of MACs
   included ("MACct") as well as a flag "S" indicating whether the tag
   also contains a digital signature.  It also contains four reserved
   bits which MUST be set to 0 by senders and ignored by receivers.

4.1.1.2.  Payload Index

    0                   1
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
   |          payload index ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

                          Figure 2: Payload Index

   If the payload index cannot be deduced from the application data in
   this payload, it must be specified explicitly in the authentication
   tag as an unsigned quantity of a fixed length specified by out-of-
   band metadata.

   Whether explicit or deduced, the payload index uniquely identifies a
   single ALTA stream payload within a rollover window of size "2^N" for
   some "N" specified in out-of-band metadata.  The payload index MUST
   start at zero and increment by one for each payload transmitted, with
   rollover to zero on overflow.




Rose & Holland           Expires January 9, 2020                [Page 7]


Internet-Draft                    ALTA                         July 2019


4.1.1.3.  Chained MACs

    0                   1
    0 1 2 3 4 5 6 7 8 9 0 1 ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-
   |    offset     | MAC ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-

                 Figure 3: Example MAC with explicit index

   In explicit offset mode, each MAC encoded in the payload comprises an
   offset from the payload's index, expressed as a signed octet in two's
   complement, followed by a fixed-length MAC.  The length and semantics
   of the MAC are a function of the MAC algorithm, which is specified by
   out-of-band metadata.  The offset space given in the example in
   Figure 3 is one octet, ranging from -128 to 127, but may be of any
   number of whole octets, as specified by out-of-band metadata.

   In implicit offset mode, the receiver knows the scheme being employed
   and so can deduce the indices of the chained MACs from the current
   payload's index.  Consequently, the MACs are simply concatenated in
   ascending order of source index according to the scheme.

4.2.  Digital Signature

    0 1 2 3 4 5 6 ...
   +-+-+-+-+-+-+-+-+-
   |  signature ...
   +-+-+-+-+-+-+-+-+-

                        Figure 4: Digital Signature

   If "S=1" in the options octet, then a digital signature is included
   in the tag.  The length and content of this digital signature are a
   function of the signature algorithm, which is specified by out-of-
   band metadata.

4.2.1.  Application Data

   The application data is opaque, with the exception of the payload
   index if not specified explicitly in the authentication tag.

4.3.  Scheme Construction

   In the ALTA context, a scheme describes the directed acyclic graph of
   payload MACs embedded in other payloads for purposes of chained
   authentication.  The recommended scheme is that described in section
   3.2 of [STRAUTH], with "a=3" and "p=5".



Rose & Holland           Expires January 9, 2020                [Page 8]


Internet-Draft                    ALTA                         July 2019


   FIXME: Describe how to construct this scheme in pseudocode.

5.  ALTA Configuration

5.1.  Performance Considerations

5.1.1.  MAC selection

5.1.2.  Digital signature selection

5.2.  Out-of-band Metadata

6.  Operational Considerations

   As ALTA requires an out-of-band channel for provisioning of metadata,
   including digital signature keys and cryptographic algorithms,
   versioning of the protocol to support a future ALTA revision may be
   performed there and acted upon by the application.

7.  Security Considerations

7.1.  Parsing an ill-formed or inconsistent payload

7.2.  Index overflow

7.3.  Truncated MACs

8.  IANA Considerations

   This document has no IANA actions.

9.  References

9.1.  Normative References

   [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/info/rfc8174>.

9.2.  Informative References

   [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/info/rfc2119>.






Rose & Holland           Expires January 9, 2020                [Page 9]


Internet-Draft                    ALTA                         July 2019


   [RFC4082]  Perrig, A., Song, D., Canetti, R., Tygar, J., and B.
              Briscoe, "Timed Efficient Stream Loss-Tolerant
              Authentication (TESLA): Multicast Source Authentication
              Transform Introduction", RFC 4082, DOI 10.17487/RFC4082,
              June 2005, <https://www.rfc-editor.org/info/rfc4082>.

   [STRAUTH]  Modadugu, N., "Authenticating Streamed Data in the
              Presence of Random Packet Loss", 2001,
              <https://crypto.stanford.edu/~pgolle/papers/auth.pdf>.

              ISOC Network and Distributed System Security Symposium

   [timeskew]
              "FIXME reference for how bad time sync is", n.d..

Acknowledgments

   The author wishes to acknowledge Eric Rescorla, who introduced the
   author to the paper describing the loss-tolerant symmetric
   authentication scheme used as the basis for ALTA.

Authors' Addresses

   Kyle Rose
   Akamai Technologies, Inc.
   150 Broadway
   Cambridge, MA 02144
   United States of America

   Email: krose@krose.org


   Jake Holland
   Akamai Technologies, Inc.
   150 Broadway
   Cambridge, MA 02144
   United States of America

   Email: jakeholland.net@gmail.com












Rose & Holland           Expires January 9, 2020               [Page 10]