Permalink
Find file Copy path
1b62779 Apr 20, 2016
1 contributor

Users who have contributed to this file

125 lines (76 sloc) 8.14 KB

EID Computation

This document specifies the cryptographic computation of the EID value and the protocol for registering an Eddystone-EID beacon with a trusted resolver.

Overview

The creation of an EID beacon requires:

  • A beacon to be provisioned as an Eddystone-EID beacon.
  • A networked service that acts as a trusted resolver and can communicate its registration parameters and receive data about the beacon.
  • A networked client that performs the cryptographic key change between the resolver and the beacon, and can register the beacon with the resolver.

An Eddystone-EID beacon must maintain three data items to compute its ephemeral identifiers:

  1. The identity key, which is a 128-bit AES key, shared between the beacon and the resolver.
  2. A beacon-specific time counter. This a 32-bit seconds counter. The counter value does not have to correspond to any real time base; the only requirement is that each increment of this counter correspond to one second of time, with a maximum error of 150 ppm.
  3. The rotation period exponent. This is a value between 0 and 15, corresponding to a power-of-two scaler on the time counter. When the scaler value is K, the beacon will generate a new identifier every 2^K seconds.

Computing an EID value

The EID value is computed using a two-step process: the first step computes a temporary key, and the second step uses this key to compute the final EID value.

Computing the temporary key

The temporary key is generated by AES-128 encrypting the following data structure with the identity key:

Byte offset Field Description
0 - 10 Padding Value = 0x00
11 Salt Value = 0xFF
12 - 13 Padding Value = 0x00
14 - 15 TS[0], TS[1] Top 16 bits of the beacon-specific time counter in 16-bit big-endian format

Computing the EID value

The 8-byte EID value is generated by AES-128 encrypting the following data structure with the temporary key:

Byte offset Field Description
0 - 10 Padding Value = 0x00
11 K Rotation period exponent
12 - 15 TS[0]...TS[3] Beacon time counter, in 32-bit big-endian format. The K lowest bits are cleared.

The result of the encryption is truncated to 64 bits by taking the leading 8 bytes of the AES cipher output.

EID configuration

Two methods of EID configuration are supported: a secure key exchange method, and a less secure shared identity key method.

Secure key exchange EID configuration

The basic registration flow is:

  1. The client queries the resolver for its registration parameters.
  2. The resolver returns its public key, along with its minimum and maximum supported rotation period exponents.
  3. The client chooses a rotation period exponent in the resolver's range and communicates that, along with the server's public key, to the beacon.
  4. The beacon uses its own key pair and the resolver's public key to compute an identity key, which it stores in its non-volatile memory.
  5. The beacon uses the computed identity key and its clock value to generate new ephemeral identifiers according to the rotation period.
  6. The client can now register the provisioned beacon with the resolver, which can map subsequent sightings of the beacon's ephemeral identifier to a stable identifier.

The cryptographic steps are specified in more detail below.

Computing the identity key

The client computes the identity key using the following procedure:

  • Compute the ECDH shared secret by multiplying the beacon's private key and the resolver's public key.
  • Verify that the shared secret is not zero. If it is, report an error.
  • Convert the shared secret to key material using HKDF-SHA256. HKDF is used with the salt set to a concatenation of the resolver's public key and beacon's public key, with a null context.
  • Truncate the key material to 128 bits to convert it to an AES-128 secret key.
  • Save this key in the beacon’s non-volatile memory.

Registering an EID beacon with the resolver

The client sends the following to the resolver:

  • The resolver's public key.
  • The beacon's public key.
  • The chosen rotation period scaler.
  • The beacon's current time counter.
  • The ephemeral identifier computed for the current time counter using the chosen rotation period scaler and the computed identity key.

The resolver then follows the same procedure to compute the identity key from its own private key and the beacon's public key. It then verifies that this key correctly decodes the ephemeral identifier supplied by the beacon.

The resolver saves the identity key, rotation period, and time counter offset from real-time in its non-volatile storage.

See the Eddystone Configuration Service for the beacon's interface definition.

Shared identity key EID configuration

In order to support registering an Eddystone-EID beacon with more than one resolver, the beacon must support disclosing its identity key to an authorised client, and must support EID configuration directly with an identity key from an authorised client.

This method of configuration is less secure than the key exchange method described above and should be used only on resource-constrained beacons that don't have sufficient resources to support a full key exchange.

Implementation guidelines

Depending upon implementation limits it may be necessary for the beacon's private/public key-pair to be fixed during manufacturing. If possible we recommend the dynamic generation of ephemeral keys at registration time, which affords some measure of forward-secrecy and means the beacon only has to store the identity key.

Given a rotation period exponent of K, an Eddystone-EID beacon should generate a new identifier every 2^K seconds on average. We recommend that the precise point at which the beaon starts advertising the new identifier is randomized within the window.

The beacon should also generate a new identifier whenever it changes its identity key (i.e. at completion of the registration procedure).

We recommend caching the temporary key for 65536 seconds, rather than recomputing it each time.

We recommend that beacons initialize their time counter at registration to a value close to the roll-over of the temporary key (i.e., time counter value mod 65536 of around 65280). This enables easier validation of the beacon’s temporary key roll-over behaviour.

The eidtools.py utility may also be of use in testing implementations of EID beacons.

Recovering from power loss

Since the beacon registered its clock value with the resolver during the configuration step, it is critical that the beacon is able to recover its clock value in the event of power loss; if it can't and the battery is replaced, the trusted resolver will fail to resolve the ID that is broadcast.

We recommend that the beacon writes its current clock value to non-volatile memory once per day, and that at boot time it checks the NVM to see if there's a value present from which to initialise. The trusted resolver should implement resolution over a time window sufficient to allow for both reasonable clock drift and this type of power loss recovery.

Security considerations

The advertisement protocol does not rely on the security of Bluetooth pairing. Instead, each beacon identifies itself by proving it possesses a specific key that is known only to this beacon and to trusted parties.

Beacons and trusted resolvers establish the keys through a separate secure registration step. The keys are generated using a Diffie-Hellman key-exchange procedure, and are never transmitted over the air.

The beacon configuration step is not authenticated: a man-in-the-middle attack on this step could have an attacker sharing one identity key with the beacon and another with the trusted resolver. This attacker could then eavesdrop on the specific beacon, but the beacon itself will not be directly resolvable by the trusted resolver. This attack may be mitigated by the implementer, for example by adding authentication at another layer. Even if not, it is considered a low-priority threat, since the attacker would need to be continuously present for the attack to proceed.

Beacons and trusted resolvers must save their ID keys in a secure non-volatile memory element.