Network Working Group                                         C. Huitema
Internet-Draft                                      Private Octopus Inc.
Intended status: Standards Track                               D. Kaiser
Expires: January 4, 2018                          University of Konstanz
                                                            July 3, 2017

           Device Pairing Using Short Authentication Strings


   This document proposes a device pairing mechanism that establishes a
   relationship between two devices by agreeing on a secret and manually
   verifying the secret's authenticity using an SAS (short
   authentication string).  Pairing has to be performed only once per
   pair of devices, as for a re-discovery at any later point in time,
   the exchanged secret can be used for mutual authentication.

   The proposed pairing method is suited for each application area where
   human operated devices need to establish a relation that allows
   configurationless and privacy preserving re-discovery at any later
   point in time.  Since privacy preserving applications are the main
   suitors, we especially care about privacy.

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

   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 4, 2018.

Copyright Notice

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

Huitema & Kaiser         Expires January 4, 2018                [Page 1]

Internet-Draft               Device Pairing                    July 2017

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   ( 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  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  Requirements  . . . . . . . . . . . . . . . . . . . . . .   3
     1.2.  Document Organization . . . . . . . . . . . . . . . . . .   4
   2.  Problem Statement and Requirements  . . . . . . . . . . . . .   4
     2.1.  Secure Pairing Over Internet Connections  . . . . . . . .   4
     2.2.  Identity Assurance  . . . . . . . . . . . . . . . . . . .   5
     2.3.  Manual Authentication . . . . . . . . . . . . . . . . . .   5
       2.3.1.  Short PIN Proved Inadequate . . . . . . . . . . . . .   5
       2.3.2.  Push Buttons Just Work, But Are Insecure  . . . . . .   6
       2.3.3.  Short Range Communication . . . . . . . . . . . . . .   6
       2.3.4.  Short Authentication Strings  . . . . . . . . . . . .   7
     2.4.  Resist Cryptographic Attacks  . . . . . . . . . . . . . .   8
     2.5.  Privacy Requirements  . . . . . . . . . . . . . . . . . .  11
     2.6.  Using TLS . . . . . . . . . . . . . . . . . . . . . . . .  11
     2.7.  QR codes  . . . . . . . . . . . . . . . . . . . . . . . .  12
     2.8.  Intra User Pairing and Transitive Pairing . . . . . . . .  14
   3.  Design of the Pairing Mechanism . . . . . . . . . . . . . . .  15
     3.1.  Discovery . . . . . . . . . . . . . . . . . . . . . . . .  15
     3.2.  Agreement . . . . . . . . . . . . . . . . . . . . . . . .  16
     3.3.  Authentication  . . . . . . . . . . . . . . . . . . . . .  16
     3.4.  Authenticating Public Keys  . . . . . . . . . . . . . . .  16
   4.  Solution  . . . . . . . . . . . . . . . . . . . . . . . . . .  16
     4.1.  Discovery . . . . . . . . . . . . . . . . . . . . . . . .  17
     4.2.  Agreement and Authentication  . . . . . . . . . . . . . .  17
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .  20
   6.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  20
   7.  Acknowledgments . . . . . . . . . . . . . . . . . . . . . . .  20
   8.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  21
     8.1.  Normative References  . . . . . . . . . . . . . . . . . .  21
     8.2.  Informative References  . . . . . . . . . . . . . . . . .  21
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  23

Huitema & Kaiser         Expires January 4, 2018                [Page 2]

Internet-Draft               Device Pairing                    July 2017

1.  Introduction

   To engage in secure and privacy preserving communication, hosts need
   to differentiate between authorized peers, which must both know about
   the host's presence and be able to decrypt messages sent by the host,
   and other peers, which must not be able to decrypt the host's
   messages and ideally should not be aware of the host's presence.  The
   necessary relationship between host and peer can be established by a
   centralized service, e.g. a certificate authority, by a web of trust,
   e.g.  PGP, or -- without using global identities -- by device

   This document proposes a device pairing mechanism that provides human
   operated devices with pairwise authenticated secrets, allowing mutual
   automatic re-discovery at any later point in time along with mutual
   private authentication.  We especially care about privacy and user-

   The proposed pairing mechanism consists of three steps needed to
   establish a relationship between a host and a peer:

   1.  Discovering the peer device.  The host needs a means to discover
       network parameters necessary to establish a connection to the
       peer.  During this discovery process, neither the host nor the
       peer must disclose its presence.

   2.  Agreeing on pairing data.  The devices have to agree on pairing
       data, which can be used by both parties at any later point in
       time to generate identifiers for re-discovery and to prove the
       authenticity of the pairing.  The pairing data can e.g. be a
       shared secret agreed upon via a Diffie-Hellman key exchange.

   3.  Authenticating pairing data.  Since in most cases the messages
       necessary to agree upon pairing data are send over an insecure
       channel, means that guarantee the authenticity of these messages
       are necessary; otherwise the pairing data is in turn not suited
       as a means for a later proof of authenticity.  For the proposed
       pairing mechanism we use manual authentication involving an SAS
       (short authentication string) to proof the authenticity of the
       pairing data.

1.1.  Requirements

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   document are to be interpreted as described in [RFC2119].

Huitema & Kaiser         Expires January 4, 2018                [Page 3]

Internet-Draft               Device Pairing                    July 2017

1.2.  Document Organization

   NOTE TO RFC EDITOR: remove or rewrite this section before

   This document is organized in two parts.  The first part, composed of
   Section 1, Section 2, and Section 3 presents the pairing need, the
   list of requirements that shall be met, and the general design of the
   solution.  This first part is informational in nature.  The second
   part, composed of Section 4 and Section 5, is the actual
   specification of the protocol.

   In his early review, Steve Kent observed that the style of the first
   part seems inappropriate for a standards track document, and
   suggested that the two parts should be split into two documents, the
   first part becoming an informational document, and the second
   focusing on standard track specification of the protocol, making
   reference to the informational document as appropriate.  We, the
   authors, will seek working group approval before performing this

2.  Problem Statement and Requirements

   The general pairing requirement is easy to state: establish a trust
   relation between two entities in a secure manner.  But details
   matter, and in this section we explore the detailed requirements that
   guide our design.

2.1.  Secure Pairing Over Internet Connections

   Many pairing protocols have already been developed, in particular for
   the pairing of devices over specific wireless networks.  For example,
   the current Bluetooth specifications include a pairing protocol that
   has evolved over several revisions towards better security and
   usability [BTLEPairing].  The Wi-Fi Alliance defined the Wi-Fi
   Protected Setup process to ease the setup of security-enabled Wi-Fi
   networks in home and small office environments [WPS].  Other wireless
   standards have defined or are defining similar protocols, tailored to
   specific technologies.

   This specification defines a pairing protocol that is independent of
   the underlying technology.  We simply make the hypothesis that the
   two parties engaged in the pairing can discover each other and then
   establish connections over IP in order to agree on a shared secret.

   [[TODO: Should we support certificates besides a shared secret?]]

Huitema & Kaiser         Expires January 4, 2018                [Page 4]

Internet-Draft               Device Pairing                    July 2017

2.2.  Identity Assurance

   The parties in the pairing must be able to identify each other.  To
   put it simply, if Alice believes that she is establishing a pairing
   with Bob, she must somehow ensure that the pairing is actually
   established with Bob, and not with some interloper like Eve or
   Nessie.  Providing this assurance requires designing both the
   protocol and the user interface (UI) with care.

   Consider for example an attack in which Eve tricks Alice into
   engaging in a pairing process while pretending to be Bob. Alice must
   be able to discover that something is wrong, and refuse to establish
   the pairing.  The parties engaged in the pairing must at least be
   able to verify their identities, respectively.

2.3.  Manual Authentication

   Because the pairing protocol is executed without prior knowledge, it
   is typically vulnerable to "Man-in-the-Middle" attacks.  While Alice
   is trying to establish a pairing with Bob, Eve positions herself in
   the middle.  Instead of getting a pairing between Alice and Bob, both
   Alice and Bob get paired with Eve. This requires specific features in
   the protocol to detect Man-in-the-Middle attacks, and if possible
   resist them.

   This section discusses existing techniques that are used in practice,
   and Section 2.4 provides a layman description of the MiTM problem and
   countermeasures.  A more in depth exploration of manually
   authenticated pairing protocols may be found in [NR11] and [thesis

2.3.1.  Short PIN Proved Inadequate

   The initial Bluetooth pairing protocol relied on a four digit PIN,
   displayed by one of the devices to be paired.  The user would read
   that PIN and provide it to the other device.  The PIN would then be
   used in a Password Authenticated Key Exchange.  Wi-Fi Protected Setup
   [WPS] offered a similar option.  There were various attacks against
   the actual protocol; some of the problems were caused by issues in
   the protocol, but most were tied to the usage of short PINs.

   In the reference implementation, the PIN is picked at random by the
   paired device before the beginning of the exchange.  But this
   requires that the paired device is capable of generating and
   displaying a four digit number.  It turns out that many devices
   cannot do that.  For example, an audio headset does not have any
   display capability.  These limited devices ended up using static
   PINs, with fixed values like "0000" or "0001".

Huitema & Kaiser         Expires January 4, 2018                [Page 5]

Internet-Draft               Device Pairing                    July 2017

   Even when the paired device could display a random PIN, that PIN will
   have to be copied by the user on the pairing device.  It turns out
   that users do not like copying long series of numbers, and the
   usability thus dictated that the PINs be short -- four digits in
   practice.  But there is only so much assurance as can be derived from
   a four digit key.

   It is interesting to note that the latest revisions of the Bluetooth
   Pairing protocol [BTLEPairing] do not include the short PIN option
   anymore.  The PIN entry methods have been superseded by the simple
   "just works" method for devices without displays, and by a procedure
   based on an SAS (short authentication string) when displays are

   A further problem with these PIN based approaches is that -- in
   contrast to SASes -- the PIN is a secret instrumental in the security
   algorithm.  To guarantee security, this PIN would have to be
   transmitted via a secure out-of-band channel.

2.3.2.  Push Buttons Just Work, But Are Insecure

   Some devices are unable to input or display any code.  The industry
   more or less converged on a "push button" solution.  When the button
   is pushed, devices enter a "pairing" mode, during which they will
   accept a pairing request from whatever other device connects to them.

   The Bluetooth Pairing protocol [BTLEPairing] denotes that as the
   "just works" method.  It does indeed work, and if the pairing
   succeeds the devices will later be able to use the pairing keys to
   authenticate connections.  However, the procedure does not provide
   any protection against MitM attacks during the pairing process.  The
   only protection is that pushing the button will only allow pairing
   for a limited time, thus limiting the opportunities of attacks.

   As we set up to define a pairing protocol with a broad set of
   applications, we cannot limit ourselves to an insecure "push button"
   method.  But we probably need to allow for a mode of operation that
   works for input-limited and display limited devices.

2.3.3.  Short Range Communication

   Many pairing protocols that use out-of-band channels have been
   defined.  Most of them are based on short range communication
   systems, where the short range limits the feasibility for attackers
   to access the channels.  Example of such limited systems include for

Huitema & Kaiser         Expires January 4, 2018                [Page 6]

Internet-Draft               Device Pairing                    July 2017

   o  QR codes, displayed on the screen of one device, and read by the
      camera of the other device.

   o  Near Field Communication (NFC) systems, which provides wireless
      communication with a very short range.

   o  Sound systems, in which one systems emits a sequence of sounds or
      ultrasounds that is picked by the microphone of the other system.

   A common problem with these solutions is that they require special
   capabilities that may not be present in every device.  Another
   problem is that they are often one-way channels.

   The pairing protocols should not rely on the secrecy of the out-of-
   band channels; most of these out-of-band channels do not provide
   confidentiality.  QR codes could be read by third parties.  Powerful
   radio antennas might be able to interfere with NFC.  Sensitive
   microphones might pick the sounds.  However, a property that all of
   these channels share is authenticity, i.e. an assurance that the data
   obtained over the out-of-band channel actually comes from the other
   party.  This is because these out-of-band channels involve the user
   transmitting information from one device to the other.  We will
   discuss the specific case of QR codes in Section 2.7.

2.3.4.  Short Authentication Strings

   The evolving pairing protocols seem to converge towards using Short
   Authentication Strins and verifying them via the "compare and
   confirm" method.  This is in line with academic studies, such as
   [KFR09] or [USK11], and, from the users' perspective, results in a
   very simple interaction:

   1.  Alice and Bob compare displayed strings that represent a
       fingerprint of the afore exchanged pairing key.

   2.  If the strings match, Alice and Bob accept the pairing.

   Most existing pairing protocols display the fingerprint of the key as
   a 6 or 7 digit numbers.  Usability studies show that this method
   gives good results, with little risk that users mistakenly accept two
   different numbers as matching.  However, the authors of [USK11] found
   that people had more success comparing computer generated sentences
   than comparing numbers.  This is in line with the argument in
   [XKCD936] to use sequences of randomly chosen common words as
   passwords.  On the other hand, standardizing strings is more
   complicated than standardizing numbers.  We would need to specify a
   list of common words, and the process to go from a binary fingerprint
   to a set of words.  We would need to be concerned with

Huitema & Kaiser         Expires January 4, 2018                [Page 7]

Internet-Draft               Device Pairing                    July 2017

   internationalization issues, such as using different lists of words
   in German and in English.  This could require the negotiation of word
   lists or languages inside the pairing protocols.

   In contrast, numbers are easy to specify, as in "take a 20 bit number
   and display it as an integer using decimal notation".

2.4.  Resist Cryptographic Attacks

   It is tempting to believe that once two peers are connected, they
   could create a secret with a few simple steps, such as for example
   (1) exchange two nonces, (2) hash the concatenation of these nonces
   with the shared secret that is about to be established, (3) display a
   short authentication string composed of a short version of that hash
   on each device, and (4) verify that the two values match.  This naive
   approach might yield the following sequence of messages:

       Alice                       Bob
       g^xA -->
                              <-- g^xB
       nA -->
                                 <-- nB
       Computes              Computes
       s = g^xAxB            s = g^xAxB
       h = hash(s|nA|nB)     h = hash(s|nA|nB)
       Displays short        Displays short
       version of h          version of h

   If the two short hashes match, Alice and Bob are supposedly assured
   that they have computed the same secret, but there is a problem.
   Let's redraw the same message flow, this time involving the attacker

Huitema & Kaiser         Expires January 4, 2018                [Page 8]

Internet-Draft               Device Pairing                    July 2017

       Alice                Eve                Bob
       g^xA -->
                                           <-- g^xB
       nA -->
                            nA -->
                                             <-- nB
                          Picks nB'
       Computes                             Computes
       s' = g^xAxB'                           s" = g^xA'xB
       h' = hash(s'|nA|nB')                    h" = hash(s"|nA|nB)
       Displays short                       Displays short
       version of h'                        version of h"

   In order to pick a nonce nB' that circumvents this naive security
   measure, Eve runs the following algorithm:

       s' = g^xAxB'
       s" = g^xA'xB
          pick a new version of nB'
          h' = hash(s'|nA|nB')
          h" = hash(s"|nA|nB)
       until the short version of h'
       matches the short version of h"

   Running this algorithm will take O(2^b) iterations on average
   (assuming a uniform distribution), where b is the bit length of the
   SAS.  Since hash algorithms are fast, it is possible to try millions
   of values in less than a second.  If the short string is made up of
   fewer than 6 digits, Eve will find a matching nonce quickly, and
   Alice and Bob will hardly notice the delay.  Even if the matching
   string is as long as 8 letters, Eve will probably find a value where
   the short versions of h' and h" are close enough, e.g. start and end
   with the same two or three letters.  Alice and Bob may well be

   Eve could also utilize the fact that she may freely choose the whole
   input for the hash function and thus choose g^xA' and g^xB' so that
   an arbitrary collision (birthday attack) instead of a second preimage
   is sufficient for fooling Alice and Bob.

   The classic solution to such problems is to "commit" a possible
   attacker to a nonce before sending it.  This commitment can be

Huitema & Kaiser         Expires January 4, 2018                [Page 9]

Internet-Draft               Device Pairing                    July 2017

   realized by a hash.  In the modified exchange, Alice sends a secure
   hash of her nonce before sending the actual value:

       Alice                       Bob
       g^xA -->
                               <-- g^xB

       Computes              Computes
       s = g^xAxB            s = g^xAxB
       h_a = hash(s|nA) -->
                                 <-- nB
       nA -->
                             verifies h_a == hash(s|nA)
       Computes              Computes
       h = hash(s|nA|nB)     h = hash(s|nA|nB)
       Displays short        Displays short
       version of h          version of h

   Alice will only disclose nA after having confirmation from Bob that
   hash(nA) has been received.  At that point, Eve has a problem.  She
   can still forge the values of the nonces but she needs to pick the
   nonce nA' before the actual value of nA has been disclosed.  Eve
   would still have a random chance of fooling Alice and Bob, but it
   will be a very small chance: one in a million if the short
   authentication string is made of 6 digits, even fewer if that string
   is longer.

   Nguyen et al.  [NR11] survey these protocols and compare them with
   respect to the amount of necessary user interaction and the
   computation time needed on the devices.  The authors state that such
   a protocol is optimal with respect to user interaction if it suffices
   for users to verify a single b-bit SAS while having a one-shot attack
   success probability of 2^-b.  Further, n consecutive attacks on the
   protocol must not have a better success probability then n one-shot

   There is still a theoretical problem, if Eve has somehow managed to
   "crack" the hash function.  We build some "defense in depth" by some
   simple measures.  In the design presented above, the hash "h_a"
   depends on the shared secret "s", which acts as a "salt" and reduces
   the effectiveness of potential attacks based on pre-computed
   catalogs.  For simplicity, the design used a simple concatenation
   mechanism, but we could instead use a keyed-hash message
   authentication code (HMAC [RFC2104], [RFC6151]), using the shared
   secret as a key, since the HMAC construct has proven very robust over
   time.  Then, we can constrain the size of the random numbers to be
   exactly the same as the output of the hash function.  Hash attacks

Huitema & Kaiser         Expires January 4, 2018               [Page 10]

Internet-Draft               Device Pairing                    July 2017

   often require padding the input string with arbitrary data;
   restraining the size limits the likelyhood of such padding.

2.5.  Privacy Requirements

   Pairing exposes a relation between several devices and their owners.
   Adversaries may attempt to collect this information, for example in
   an attempt to track devices, their owners, or their social graph.  It
   is often argued that pairing could be performed in a safe place, from
   which adversaries are assumed absent, but experience shows that such
   assumptions are often misguided.  It is much safer to acknowledge the
   privacy issues and design the pairing process accordingly.

   In order to start the pairing process, devices must first discover
   each other.  We do not have the option of using the private discovery
   protocol [I-D.ietf-dnssd-privacy] since the privacy of that protocol
   depends on a pre-existing pairing.  In the simplest design, one of
   the devices will announce a user-friendly name using DNS-SD.
   Adversaries could monitor the discovery protocol, and record that
   name.  An alternative would be for one device to announce a random
   name, and communicate it to the other device via some private
   channel.  There is an obvious tradeoff here: friendly names are
   easier to use but less private than random names.  We anticipate that
   different users will choose different tradeoffs, for example using
   friendly names if they assume that the environment is safe, and using
   random names in public places.

   During the pairing process, the two devices establish a connection
   and validate a pairing secret.  As discussed in Section 2.3, we have
   to assume that adversaries can mount MitM attacks.  The pairing
   protocol can detect such attacks and resist them, but the attackers
   will have access to all messages exchanged before the validation is
   performed.  It is important to not exchange any privacy sensitive
   information before that validation.  This includes, for example, the
   identities of the parties or their public keys.

2.6.  Using TLS

   The pairing algorithms typically combine the establishment of a
   shared secret through an [EC]DH exchange with the verification of
   that secret through displaying and comparing a "short authentication
   string" (SAS).  As explained in Section 2.4, the secure comparison
   requires a "commit before disclose" mechanism.

   We have three possible designs: (1) create a pairing algorithm from
   scratch, specifying our own cryptographic protocol; (2) use an [EC]DH
   version of TLS to negotiate a shared secret, export the key to the
   application as specified in [RFC5705], and implement the "commit

Huitema & Kaiser         Expires January 4, 2018               [Page 11]

Internet-Draft               Device Pairing                    July 2017

   before disclose" and SAS verification as part of the pairing
   application; or, (3) use TLS, integrate the "commit before disclose"
   and SAS verification as TLS extensions, and export the verified key
   to the application as specified in [RFC5705].

   When faced with the same choice, the designers of ZRTP [RFC6189]
   chose to design a new protocol integrated in the general framework of
   real time communications.  We don't want to follow that path, and
   would rather not create yet another protocol.  We would need to
   reinvent a lot of the negotiation capabilities that are part of TLS,
   not to mention algorithm agility, post quantum, and all that sort of
   things.  It is thus pretty clear that we should use TLS.

   It turns out that there was already an attempt to define SAS
   extensions for TLS ([I-D.miers-tls-sas]).  It is a very close match
   to our third design option, full integration of SAS in TLS, but the
   draft has expired, and there does not seem to be any support for the
   SAS options in the common TLS packages.

   In our design, we will choose the middle ground option -- use TLS for
   [EC]DH, and implement the SAS verification as part of the pairing
   application.  This minimizes dependencies on TLS packages to the
   availability of a key export API following [RFC5705].  We will need
   to specify the hash algorithm used for the SAS computation and
   validation, which carries some of the issues associated with
   "designing our own crypto".  One solution would be to use the same
   hash algorithm negotiated by the TLS connection, but common TLS
   packages do not always make this algorithm identifier available
   through standard APIs.  A fallback solution is to specify a state of
   the art keyed MAC algorithm.

2.7.  QR codes

   In Section 2.3.3, we reviewed a number of short range communication
   systems that can be used to facilitate pairing.  Out of these, QR
   codes stand aside because most devices that can display a short
   string can also display the image of a QR code, and because many
   pairing scenarios involve cell phones equipped with cameras capable
   of reading a QR code.

   QR codes are displayed as images.  An adversary equipped with
   powerful cameras could read the QR code just as well as the pairing
   parties.  If the pairing protocol design embedded passwords or pins
   in the QR code, adversaries could access these data and compromise
   the protocol.  On the other hand, there are ways to use QR codes even
   without assuming secrecy.

Huitema & Kaiser         Expires January 4, 2018               [Page 12]

Internet-Draft               Device Pairing                    July 2017

   QR codes could be used at two of the three stages of pairing:
   Discovering the peer device, and authenticating the shared secret.
   Using QR codes provides advantages in both phases:

   o  Typical network based discovery involves interaction with two
      devices.  The device to be discovered is placed in "server" mode,
      and waits for requests from the network.  The device performing
      the discovery retrieves a list of candidates from the network.
      When there is more than one such candidate, the device user is
      expected to select the desired target from a list.  In QR code
      mode, the discovered device will display a QR code, which the user
      will scan using the second device.  The QR code will embed the
      device's name, its IP address, and the port number of the pairing
      service.  The connection will be automatic, without relying on the
      network discovery.  This is arguably less error-prone and safer
      than selecting from a network provided list.

   o  SAS based agreement involves displaying a short string on each
      device's display, and asking the user to verify that both devices
      display the same string.  In QR code mode, one device could
      display a QR code containing this short string.  The other device
      could scan it and compare it to the locally computed version.
      Because the procedure is automated, there is no dependency on the
      user diligence at comparing the short strings.

   Offering QR codes as an alternative to discovery and agreement is
   straightforward.  If QR codes are used, the pairing program on the
   server side might display something like:

      Please connect to "Bob's phone 359"
      or scan the following QR code:

       mmmmmmm  m  m mmmmmmm
       # mmm # ## "m # mmm #
       # ### # m" #" # ### #
       #mmmmm# # m m #mmmmm#
       mm m  mm"## m mmm mm
       " ##"mm m"# ####"m""#
       #"mmm mm# m"# ""m" "m
       mmmmmmm #mmm###mm# m
       # mmm #  m "mm " "  "
       # ### # " m #  "## "#
       #mmmmm# ### m"m m  m

   If Alice's device is capable of reading the QR code, it will just
   scan it, establishes a connection, and run the pairing protocol.
   After the protocol messages have been exchanged, Bob's device will

Huitema & Kaiser         Expires January 4, 2018               [Page 13]

Internet-Draft               Device Pairing                    July 2017

   display a new QR code, encoding the hash code that should be matched.
   The UI might look like this:

      Please scan the following QR code,
      or verify that your device displays
      the number: 388125

       mmmmmmm   mmm mmmmmmm
       # mmm # ""#m# # mmm #
       # ### # "#  # # ### #
       #mmmmm# # m"m #mmmmm#
       mmmmm mmm" m m m m m
        #"m mmm#"#"#"#m m#m
       ""mmmmm"m#""#""m #  m
       mmmmmmm # "m"m "m"#"m
       # mmm # mmmm m "# #"
       # ### # #mm"#"#m "
       #mmmmm# #mm"#""m "m"

      Did the number match (Yes/No)?

   With the use of QR code, the pairing is established with little
   reliance on user judgment, which is arguably safer.

2.8.  Intra User Pairing and Transitive Pairing

   There are two usage modes for pairing: inter-user, and intra-user.
   Users have multiple devices.  The simplest design is to not
   distinguish between pairing devices belonging to two users, e.g.,
   Alice's phone and Bob's phone, and devices belonging to the same
   user, e.g., Alice's phone and her laptop.  This will most certainly
   work, but it raises the problem of transitivity.  If Bob needs to
   interact with Alice, should he install just one pairing for "Alice
   and Bob", or should he install four pairings between Alice phone and
   laptop and Bob phone and laptop?  Also, what happens if Alice gets a
   new phone?

   One tempting response is to devise a synchronization mechanism that
   will let devices belonging to the same user share their pairings with
   other users.  But it is fairly obvious that such service will have to
   be designed cautiously.  The pairing system relies on shared secrets.
   It is much easier to understand how to manage secrets shared between
   exactly two parties than secrets shared with an unspecified set of

   Transitive pairing raises similar issues.  Suppose that a group of
   users wants to collaborate.  Will they need to set up a fully
   connected graph of pairings using the simple peer-to-peer mechanism,

Huitema & Kaiser         Expires January 4, 2018               [Page 14]

Internet-Draft               Device Pairing                    July 2017

   or could they use some transitive set, so that if Alice is connected
   with Bob and Bob with Carol, Alice automatically gets connected with
   Carol?  Such transitive mechanisms could be designed, e.g. using a
   variation of Needham-Scroeder symmetric key protocol [NS1978], but it
   will require some extensive work.  Groups can of course use simpler
   solution, e.g., build some star topology.

   Given the time required, intra-user pairing synchronization
   mechanisms and transitive pairing mechanisms are left for further

3.  Design of the Pairing Mechanism

   In this section we discuss the design of pairing protocols that use
   manually verified short authentication strings (SAS), considering
   both security and user experience.

   We divide pairing in three parts: discovery, agreement, and
   authentication, detailed in the following subsections.

3.1.  Discovery

   The goal of the discovery phase is establishing a connection, which
   is later used to exchange the pairing data, between the two devices
   that are about to be paired in an IP network without any prior
   knowledge and without publishing any private information.  In
   accordance with TLS, we refer to the device initiating the
   cryptographic protocol as client, and to the other device as server;
   the server has to be discoverable by the client.

   Granting privacy during the discovery phase without relying on prior
   knowledge demands another user interaction (besides the SAS
   verification during the authentication phase).  There are two
   possible ways of realizing this user interaction depending on whether
   QR codes are supported or not.  If QR codes are supported, the
   discovery process can be independent of DNS-SD, because QR codes
   allow the transmission of a sufficient amount of data.  Leveraging QR
   codes, the discovery proceeds as follows.

   1.  The server displays a QR code containing the instance name, the
       IPv4 or IPv6 address, and the port number of the service/

   2.  The client scans the QR code retrieving the necessary information
       for establishing a connection to the server.

   If QR codes are not supported, the discovery proceeds as follows.

   1.  The server displays its chosen instance name on its screen.

Huitema & Kaiser         Expires January 4, 2018               [Page 15]

Internet-Draft               Device Pairing                    July 2017

   2.  The client performs a discovery of all the "pairing" servers
       available on the local network.  This may result in the discovery
       of several servers.

   3.  Among these available "pairing servers" the client's user selects
       the name that matches the name displayed by the server.

   4.  Per DNS-SD, the client then retrieves the SRV records of the
       selected instance, selects one of the discovered servers,
       retrieves its A or AAAA records, and establishes the connection.

3.2.  Agreement

   Once the server has been selected, the client connects to it without
   further user intervention.  Client and server use this connection for
   exchanging data that allows them to agree on a shared secret by using
   a cryptographic protocol that yields an SAS.  We discussed design
   aspects of such protocols in Section 2.4.

3.3.  Authentication

   In the authentication phase, the users are asked to validate the
   pairing by comparing the SASes -- typically represented by a number
   encoded over up to 7 decimal digits.  If the SASes match, each user
   enters an agreement, for example by pressing a button labeled "OK",
   which results in the pairing being remembered.  If they do not match,
   each user should cancel the pairing, for example by pressing a button
   labeled "CANCEL".

   Depending on whether QR codes are supported, the SAS may also be
   represented as QR code.  Despite the fact that using QR codes to
   represent the authentication string renders using longer
   authentication strings feasible, we suggest to always generate an SAS
   during the agreement phase, because this makes realizations of the
   agreement phase and the authentication phase independent.  Devices
   may display the "real" name of the other device alongside the SAS.

3.4.  Authenticating Public Keys

   [[TODO: Should we discuss verifying public keys using our pairing

4.  Solution

   In the proposed pairing protocol, one of the devices acts as a
   "server", and the other acts as a "client".  The server will publish
   a "pairing service".  The client will discover the service instance

Huitema & Kaiser         Expires January 4, 2018               [Page 16]

Internet-Draft               Device Pairing                    July 2017

   during the discovery phase, as explained in Section 4.1.  The pairing
   service itself is specified in Section 4.2.

4.1.  Discovery

   The discovery uses DNS-SD [RFC6763] over mDNS [RFC6762].  The pairing
   service is identified in DNS SD as "_pairing._tcp".  When the pairing
   service starts, the server starts publishing the chosen instance
   name.  The client will discover that name and the corresponding
   connection parameters.

   If QR code scanning is available as out-of-band channel, the
   discovery data is directly transmitted via QR codes instead of DNS-SD
   over mDNS.  The QR code data contains connection data otherwise found
   in the SRV and A or AAAA records: IPv4 or IPv6 address, port number,
   and optionally host name.

   [[TODO: We should precisely specify the data layout of this QR code.
   It could either be the wire format of the corresponding resource
   records (which would be easier for us), or a more efficient
   representation.  If we chose the wire format, we could use a fix name
   as instance name.]]

4.2.  Agreement and Authentication

   The pairing protocol is built using TLS.  The following description
   uses the presentation language defined in section 4 of [RFC5246].
   The protocol uses five message types, defined in the following enum:

   enum {
   } PairingMessageType;

   Devices implementing the service MUST support TLS 1.2 [RFC5246], and
   MAY negotiate TLS 1.3 when it becomes available.  When using TLS, the
   client and server MUST negotiate a ciphersuite providing forward
   secrecy (PFS), and strong encryption (256 bits symmetric key).  All
   implementations using TLS 1.2 MUST be able to negotiate the cipher
   suite TLS_DH_anon_WITH_AES_256_CBC_SHA256.

   Once the TLS connection has been established, each party extracts the
   pairing secret S_p from the connection context per [RFC5705], using
   the following parameters:

Huitema & Kaiser         Expires January 4, 2018               [Page 17]

Internet-Draft               Device Pairing                    July 2017

   Disambiguating label string:  "PAIRING SECRET"

   Context value:  empty.

   Length value:  32 bytes (256 bits).

   Once S_p has been obtained, the client picks a random number R_c,
   exactly 32 bytes long.  The client then selects a hash algorithm,
   which SHOULD be the same algorithm as negotiated for building the PRF
   in the TLS connection.  If there is no suitable API to retrieve that
   algorithm, the client MAY use SHA256 instead.  The client then
   computes the hash value H_c as:

      H_c = HMAC_hash(S_p, R_c)

      Where "HMAC_hash" is the HMAC function constructed with the
      selected algorithm.

   The client transmits the selected hash function and the computed
   value of H_c in the Client Hash message, over the TLS connection:

   struct {
      PairingMessageType messageType;
      hashAlgorithm hash;
      uint8 hashLength;
      opaque H_c[hashLength];
   } ClientHashMessage;

   messageType  Set to "ClientHash".

   hash  The code of the selected hash algorithm, per definition of
         HashAlgorithm in section of [RFC5246].

   hashLength  The length of the hash H_c, which MUST be consistent with
         the selected algorithm "hash".

   H_c   The value of the client hash.

   Upon reception of this message, the server stores its value.  The
   server picks a random number R_s, exactly 32 bytes long, and
   transmits it to the client in the server random message, over the TLS

   struct {
      PairingMessageType messageType;
      opaque R_s[32];
   } ServerRandomMessage;

Huitema & Kaiser         Expires January 4, 2018               [Page 18]

Internet-Draft               Device Pairing                    July 2017

   messageType  Set to "ServerRandom".

   R_s   The value of the random number chosen by the server.

   Upon reception of this message, the client discloses its own random
   number by transmitting the client random message:

   struct {
      PairingMessageType messageType;
      opaque R_c[32];
   } ClientRandomMessage;

   messageType  Set to "ClientRandom".

   R_c   The value of the random number chosen by the client.

   Upon reception of this message, the server verifies that the number
   R_c hashes to the previously received value H_c.  If the number does
   not match, the server MUST abandon the pairing attempt and abort the
   TLS connection.

   At this stage, both client and server can compute the short hash SAS

      SAS = first 20 bits of HMAC_hash(S_p, R_c + R_s)

      Where "HMAC_hash" is the HMAC function constructed with the hash
      algorithm selected by the client in the ClientHashMessage.

   Both client and server display the SAS as a decimal integer, and ask
   the user to compare the values.  If the server supports QR codes, the
   server displays a QR code encoding the decimal string representation
   of the SAS.  If the client is capable of scanning QR codes, it may
   scan the value and compare it to the locally computed value.

   If the values do not match, the user cancels the pairing.  Otherwise,
   the protocol continues with the exchange of names, both server and
   client announcing their own preferred name in a Success message

   struct {
      PairingMessageType messageType;
      uint8 nameLength;
      opaque name[nameLength];
   } ClientSuccessMessage;

   messageType  Set to "ClientSuccess" if transmitted by the client,
         "ServerSuccess" if by the server.

Huitema & Kaiser         Expires January 4, 2018               [Page 19]

Internet-Draft               Device Pairing                    July 2017

   nameLength  The length of the string encoding the selected name.

   name  The selected name of the client or the server, encoded as a
         string of UTF8 characters.

   After receiving these messages, client and servers can orderly close
   the TLS connection, terminating the pairing exchange.

5.  Security Considerations

   We need to consider two types of attacks against a pairing system:
   attacks that occur during the establishment of the pairing relation,
   and attacks that occur after that establishment.

   During the establishment of the pairing system, we are concerned with
   privacy attacks and with MitM attacks.  Privacy attacks reveal the
   existence of a pairing between two devices, which can be used to
   track graphs of relations.  MitM attacks result in compromised
   pairing keys.  The discovery procedures specified in Section 4.1 and
   the authentication procedures specified in Section 4.2 are
   specifically designed to mitigate such attacks, assuming that the
   client and user are in close, physical proximity and thus a human
   user can visually acquire and verify the pairing information.

   The establishment of the pairing results in the creation of a shared
   secret.  After the establishment of the pairing relation, attackers
   who compromise one of the devices could access the shared secret.
   This will enable them to either track or spoof the devices.  To
   mitigate such attacks, nodes MUST store the secret safely, and MUST
   be able to quickly revoke a compromised pairing.  This is however not
   sufficient, as the compromise of the pairing key could remain
   undetected for a long time.  For further safety, nodes SHOULD assign
   a time limit to the validity of pairings, discard the corresponding
   keys when the time has passed, and establish new pairings.

6.  IANA Considerations

   This draft does not require any IANA action.

7.  Acknowledgments

   We would like to thank Steve Kent for a detailed early review of this

Huitema & Kaiser         Expires January 4, 2018               [Page 20]

Internet-Draft               Device Pairing                    July 2017

8.  References

8.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,

   [RFC5246]  Dierks, T. and E. Rescorla, "The Transport Layer Security
              (TLS) Protocol Version 1.2", RFC 5246,
              DOI 10.17487/RFC5246, August 2008,

   [RFC5705]  Rescorla, E., "Keying Material Exporters for Transport
              Layer Security (TLS)", RFC 5705, DOI 10.17487/RFC5705,
              March 2010, <>.

   [RFC6762]  Cheshire, S. and M. Krochmal, "Multicast DNS", RFC 6762,
              DOI 10.17487/RFC6762, February 2013,

   [RFC6763]  Cheshire, S. and M. Krochmal, "DNS-Based Service
              Discovery", RFC 6763, DOI 10.17487/RFC6763, February 2013,

8.2.  Informative References

              Bluetooth SIG, "Bluetooth Low Energy Security Overview",

              Huitema, C. and D. Kaiser, "Privacy Extensions for DNS-
              SD", draft-ietf-dnssd-privacy-01 (work in progress), March

              Miers, I., Green, M., and E. Rescorla, "Short
              Authentication Strings for TLS", draft-miers-tls-sas-00
              (work in progress), February 2014.

Huitema & Kaiser         Expires January 4, 2018               [Page 21]

Internet-Draft               Device Pairing                    July 2017

   [KFR09]    Kainda, R., Flechais, I., and A. Roscoe, "Usability and
              Security of Out-Of-Band Channels in Secure Device Pairing
              Protocols", DOI: 10.1145/1572532.1572547, SOUPS
              09, Proceedings of the 5th Symposium on Usable Privacy and
              Security, Mountain View, CA, January 2009.

   [NR11]     Nguyen, L. and A. Roscoe, "Authentication protocols based
              on low-bandwidth unspoofable channels: a comparative
              survey", DOI: 10.3233/JCS-2010-0403, Journal of Computer
              Security, Volume 19 Issue 1, Pages 139-201, January 2011.

   [NS1978]   Needham, R. and M. Schroeder, ". Using encryption for
              authentication in large networks of computers",
              Communications of the ACM 21 (12): 993-999,
              DOI: 10.1145/359657.359659, December 1978.

   [RFC2104]  Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
              Hashing for Message Authentication", RFC 2104,
              DOI 10.17487/RFC2104, February 1997,

   [RFC6151]  Turner, S. and L. Chen, "Updated Security Considerations
              for the MD5 Message-Digest and the HMAC-MD5 Algorithms",
              RFC 6151, DOI 10.17487/RFC6151, March 2011,

   [RFC6189]  Zimmermann, P., Johnston, A., Ed., and J. Callas, "ZRTP:
              Media Path Key Agreement for Unicast Secure RTP",
              RFC 6189, DOI 10.17487/RFC6189, April 2011,

   [USK11]    Uzun, E., Saxena, N., and A. Kumar, "Pairing devices for
              social interactions: a comparative usability evaluation",
              DOI: 10.1145/1978942.1979282, Proceedings of the
              International Conference on Human Factors in Computing
              Systems, CHI 2011, Vancouver, BC, Canada, May 2011.

   [WPS]      Wi-Fi Alliance, "Wi-Fi Protected Setup", 2016,

   [XKCD936]  Munroe, R., "XKCD: Password Strength", 2011,

Huitema & Kaiser         Expires January 4, 2018               [Page 22]

Internet-Draft               Device Pairing                    July 2017

Authors' Addresses

   Christian Huitema
   Private Octopus Inc.
   Friday Harbor, WA  98250


   Daniel Kaiser
   University of Konstanz
   Konstanz  78457


Huitema & Kaiser         Expires January 4, 2018               [Page 23]