Short Authenticated Strings

sas.md

Abstract

cross-authentication protocols using short authenticated strings:

• pretty much an unauthenticated key exchange between two devices
• followed by comparing a short value (6 digits usually) displayed by the devices to authenticate the transcript/output of the key exchange
• this short value is public, but cannot be tampered with

Attacker Model

thee messages are routed via an active adversary Charlie who can drop, delay, modify and insert messages. A low bandwidth out-of-band channel between Alice and Bob is bidirectional and authentic, but Charlie can arbitrarily delay OOB messages. As communication is asynchronous, Charlie can arbitrarily reorder in-band messages

we require that the OOB messages have been specified in such a way that either both Alice and Bob accept the output or neither of them does.

Charlie succeeds in deception if at the end of the protocol Alice and Bob reach the accepting state but [Alice sees different public keys than Bob]

A protocol is correct if Alice and Bob always reach the accepting state when Charlie does not intervene.

Timeline

• 2006 - Pasini, Vaudenay - SAS-based Authenticated Key Agreement (Vaudenay SAS protocol + SAS-MCA)
• 2006 - Laur, Nyberg - Efficient Mutual Data Authentication Using Manually Authenticated Strings (MANA IV, MA-DH)

  Compared to previous articles by Vaudenay and Pasini the results of this paper are more general and based on weaker security assumptions

• 2008 - Laur, Pasini - SAS-Based Group Authentication and Key Agreement Protocols
• 2009 - Laur, Pasini - User-Aided Data Authentication (survey)

Schemes

From the user-aided data authentication paper it seems like after SAS-MCA, MANA IV, and MA-DH there is not improvements to look for in the field.

First, all of them use one-time pad encryption to assure that the adversary preserves the temporal order between protocol messages.

Secondly, the commitment scheme is used as an additional measure against substitution attacks.

Thirdly, it seems that there are no other designs patterns that could overcome the shortcomings of the MANA II protocol.

MANA II. Vulnerable to active MITM

The Vaudenay SAS protocol. Only authenticate a message (public key) from one-side

SAS-MCA. The MCA indicates that the two sides can authenticate something (their public keys)

• Q is the number of protocol instances (considering that every time, the user has to check that a SAS matches)
• matching (attack) succeeds with probability 1 - 2^(-Qp) (2^p)! / (2^p - Q)! ~ Q(Q-1)2^(-p-1) when Q << 2^(p/2)

MANA IV.

http://www.tcs.hut.fi/Publications/slaur/MANA-IV.pdf

MA-DH.

This is MANA IV instantiated with an unauthenticated DH.

http://www.tcs.hut.fi/Publications/slaur/MANA-IV.pdf

• weirdly, the h(.) does not include the DH output...
• I would also have expected m_a and m_b to be used as ephemeral public keys, but here k_a and k_b are the ephemeral public keys.

The Bluetooth authentication mechanisms are undergoing the standardisation phase and the current proposal for the standard [BT06] includes an instantiation of Mana IV (NUMERIC COMPARISON) among other methods. Our security analysis provides the necessary theoretical validation

Mana IV and MA–DH protocols are secure in any computational context if (a) random values are never reused, (b) protocol outputs are never used before reaching the accepting state, (c) there are no multiple protocol instances between the same device pair at any time

The last quote is interesting, maybe a device could talk to itself, and so on.

Background

These schemes rely on:

commitment schemes.

• hiding
• binding
• non-malleability

  Intuitively, a commitment scheme is non-malleable, if given a valid commitment c, it is infeasible to generate related commitments c1,...,cn that can be successfully opened after seeing a decommitment value d the definition of non-malleable encryption is stronger and therefore non-malleable encryption schemes (including CCA2 secure encryption schemes) can be used as non-malleable commitments provided that the public parameters pk are generated by the trusted party

• this can be implemented with a hash function:
  • remember (c, d) = Com(x, r), you reveal c first, you open using d which reveals r
  • (c, d) = Com(x, r) with c = { H(x||r), d = (x||r)} or c = HMAC(r, x), d = r
  • but these are not hiding, OAEP?

hash function.

In practice, one can use h_K(x) = trunc(hash(K||x)) where hash is a collision-resistant hash function and trunc truncates to the leading ρ bits.

They say that truncation is under 14 bits

out-of-band channel.