Skip to Content

'Find My Ex' - A guess on Apple's FindMy cryptography

Posted on by Jonathan 'smuggler' Logan 4 mins read

“Find My Ex” - A guess on Apple’s FindMy cryptography

A couple of days ago Apple has announced a new service, the “Find My” feature that allows owners of at least two Apple devices to locate a lost device.

The description of the service is rather shallow, but essentially Apple is going to enlist all Apple devices to relay location information about devices they sense nearby to Apple, and then to allow the owner to query that database for the location of a lost device.

While this new service is hailed as utterly practical, safe, private and nothing short of awesome, I’d rather consider it as a global network of digital snitches.

That being said, people are wondering how the cryptography of such a system could work and how it can keep Apple from finding out too much information about lost devices, or the snitch devices. Here I’ll give a quick and dirty guess on how such a protocol can work. I’m not claiming this is what Apple actually does, but should anybody wonder how it could be done, be my guest :)

To kick it off, let’s start with a few definitions.

We have four entities involved:

  • Stalker: The device trying to find another device.
  • Victim: The device to be found.
  • Snitch: The device that is employed in relaying the location of the Victim.
  • Big Sister: The database that holds the information on the Victim so Snitch can find it.

We also need a few cryptographic primitives:

  • HMAC(k,m): The HMAC of m, with key k. HMAC
  • Elliptic Curve cryptography. ECC

That’s it. Now the protocol (skip if you are not at all into cryptography):

  1. Definitions: Agree on elliptic curve, generator point, updateDuration.
  2. Pairing phase. Victim creates:
  • Private key. privKey[0], ratchetSecret := random()
  • Pairing date: pairDate := unixtime()
    // unixtime is the number of seconds since 1970-01-01 00:00
  • Victim shares privKey[0], ratchetSecret, pairDate with Stalker.
  1. Ratcheting:
  • Every updateDuration seconds, both Victim and Stalker calculate:
    privKey[n+1] := HMAC(ratchetSecret, privKey[n])
  • Victim also calculates N public keys:
    tempPubkey{x:0…N} := HMAC(privKey[n+1],ratchetSecret | x) * G
    // skalar multiply with a publicly agreed on generator point on the curve.
  • privKey[n] is discarded.
  1. Victim gets lost and broadcasts tempPubKey{0,N} via Bluetooth LE.
  2. Snitching phase:
  • Snitch receives tempPubKey{0,N}.
  • Snitch calculates selector: sel := HMAC(tempPubKey{0,N}, SnitchDeviceID)
  • Snitch picks one myTempPubkey: tempPubKey{0,N}[sel]
  • Snitch generates ephemeral keypair:
    ePrivkey := random; rPubkey := ePrivkey * G
  • Snitch calculates message key: messageKey := ePrivkey * myTempPubkey
  • Snitch encrypts it’s own location with messageKey. (Use your standard NaCL suite here for symmetric encryption).
  • Snitch sends “myTempPubkey | rPubkey | encryptedLocation” to Big Sister.
  1. The Hunt. Stalker wants to know Victim’s location.
  • Stalker re-creates tempPubkey. It has a synchronized knowledge of the current privKey, time and ratchetSecret to do so.
  • Stalker sends tempPubkey to Big Sister.
  • Big Sister searches the database for messages containing tempPubKey and returns them to Stalker.
  • Stalker calculates the message key := privkey * rPubkey.
  • And finally stalker decrypts the location.
  1. The Catch: Stalker reconnects to Victim and the protocol repeats with a new pairing phase.

This protocol is rather simple but still solves a couple of requirements:

  • Snitch never has to reveal its own location or identity to Big Sister.
  • Snitch never has to reveal its own identity to Stalker.
  • Victim does not broadcast a static or publicly determinable identity.
  • Stalker cannot learn anything about Victim unless both share the secrets from the pairing phase.
  • If the current secrets (privKey[n], ratchetSecret) are leaked then no historical data from before the leak is recoverable by the attacker.
  • Big Sister cannot easily track the handover of Victim between multiple Snitches.

However, the protocol comes with some big downsides.

  • The lookup for tempPubKey is expensive. Stalker has to look up N tempPubKeys for each updateDuration in which it is searching.
  • Big Sister can learn that multiple tempPubKeys are referring to the same Victim. This can be solved with the help of Private Information Retrieval protocols PIR.

Let’s assume however that Apple does everything right (that is, much better than above amateur protocol). Why am I still critical of this service?

Designing and implementing a global, passive snitching service is hard. Preventing Stalker’s requests to be correlated with location information about Snitches from an unrelated source is non-trivial, and might quickly turn “Find My” into a nice little tracking tool that can be used by any semi-smart stalker to track his or her Ex. By employing millions of devices sold by a “Privacy as a Service” company.

Please Apple, can we first see your design before you roll it out?

* Minor explanation on the protocol above: The point of ratching is to achieve forward secrecy in case secrets are lost. That way location data from before the breach becomes unavailable to the attacker. The point of using multiple tempPubKeys is to make it harder for Big Sister to track a Victim through correlating sightings by multiple Snitches during the same updateDuration. However, without PIR this information will get revealed as soon as Stalker makes requests to Big Sister.

** I’m investing in local area bluetooth jammers and faraday bags. Just in case.