Spec: Proximity Discovery & Key Exchange

Overview

This page is the full technical specification for Prototype 3. The prototype goal is described in the research prototype catalogue and the motivation in plain language in Story 3: The First Meeting. Two Android phones broadcast unlinkable BLE beacons, show an anonymous "1 person nearby" indicator, and then — when both users consent — exchange three public keys (Ed25519 identity key, X25519 DH key, ML-KEM-768 post-quantum KEM key) over a single NFC tap or QR scan. X3DH key agreement runs on both devices and both arrive at the same shared secret. The contact is persisted locally. On subsequent encounters within BLE range, a challenge-response protocol lets the devices mutually authenticate without broadcasting identity to passive observers. No messaging, no internet, no feeds — just the physical-first trust foundation everything else builds on.

API Surface / Key Interfaces

All interfaces are Kotlin pseudocode. Types reference Android SDK and BouncyCastle conventions where naming would otherwise be ambiguous.

BLE Advertising

/**
 * Rotates the BLE advertisement payload every [rotationInterval].
 * The payload is 16 random bytes — no identity, no persistent token.
 * Android randomises the MAC address automatically; rotating the payload
 * closes the remaining correlation vector (same payload across MAC changes).
 */
interface ProximityBeacon {
    fun startAdvertising(rotationInterval: Duration)
    fun stopAdvertising()
}

BLE Scanning

/**
 * Calls [callback] for every distinct beacon seen in the scan window.
 * BeaconSeen carries only signal strength (RSSI) and the raw payload bytes —
 * never a persistent identifier.
 */
data class BeaconSeen(val rssi: Int, val payload: ByteArray, val seenAt: Instant)

interface ProximityScanner {
    fun startScan(callback: (BeaconSeen) -> Unit)
    fun stopScan()
}

NFC Key Exchange

/**
 * Produces an NDEF record containing:
 *   - Ed25519 public key   (32 bytes)
 *   - X25519 public key    (32 bytes)
 *   - ML-KEM-768 public key (1184 bytes)
 *   - Unix timestamp       (8 bytes, prevents replay)
 *   Total payload: 1256 bytes, within NDEF single-record capacity.
 *
 * One phone calls this and presents the tag; the other scans in reader mode.
 * Android Beam / setNdefPushMessage is deprecated since Android 10 — this
 * implementation uses NfcAdapter.enableReaderMode() on the scanning device.
 */
interface NfcKeyExchange {
    fun generatePayload(): NdefMessage
    fun receivePayload(message: NdefMessage): KeyBundle
}

QR Key Exchange

/**
 * Encodes the same KeyBundle as the NDEF payload into a QR code.
 * 1256 bytes binary → base64url → ~1675 chars.
 * At QR version 40 / ECC level L capacity is ~2953 alphanumeric chars,
 * so the payload fits in a single QR code at a scannable size.
 * Falls back to two-frame animated QR if the implementation targets
 * smaller screen sizes (see Risks section).
 */
interface QrKeyExchange {
    fun generateQR(): Bitmap
    fun scanQR(bitmap: Bitmap): KeyBundle
}

Key Bundle

/**
 * Canonical on-wire representation of one party's public keys.
 * Serialised as a concatenation of raw public key bytes + timestamp.
 * No ASN.1, no TLS encoding — intentionally minimal.
 */
data class KeyBundle(
    val identityKey: Ed25519PublicKey,   // 32 bytes — also seeds feed_id
    val dhKey: X25519PublicKey,          // 32 bytes
    val kemPublicKey: MLKem768PublicKey, // 1184 bytes
    val timestamp: Instant
)

X3DH Key Agreement

/**
 * Extended Triple Diffie-Hellman adapted for hybrid classical + PQ:
 *
 *   DH1 = X25519(myIdentityPriv,  theirDhPub)
 *   DH2 = X25519(myEphemeralPriv, theirDhPub)
 *   DH3 = X25519(myEphemeralPriv, theirDhPub)   // standard X3DH shape
 *   KEM = ML-KEM-768 encapsulation → kemSecret
 *
 *   sharedSecret = HKDF-SHA256(DH1 || DH2 || DH3 || kemSecret)
 *
 * Both initiator and responder derive the same sharedSecret.
 * The ephemeral X25519 key is generated fresh for each exchange and discarded.
 */
interface X3DH {
    fun initiateKeyAgreement(
        myKeys: KeyBundle,
        myPrivateKeys: PrivateKeyBundle,
        theirKeys: KeyBundle
    ): SharedSecret
}

Contact Store

/**
 * Persists a contact after successful key agreement.
 * feed_id = base64url(SHA-256(theirKeys.identityKey.publicBytes))
 * sharedSecret is stored in Android Keystore-backed encrypted storage.
 * displayName is optional — user can label the contact later.
 */
interface ContactStore {
    fun storeContact(
        theirFeedId: String,
        sharedSecret: SharedSecret,
        displayName: String? = null
    )

    fun lookupByFeedId(feedId: String): Contact?
    fun allContacts(): List<Contact>
}

BLE Contact Recognizer

/**
 * After a prior key exchange, a known contact can be re-identified over BLE
 * using an authenticated challenge-response:
 *
 *   1. Device A sees an unrecognised beacon payload.
 *   2. A connects to B's GATT service, sends a 32-byte random challenge
 *      encrypted with B's Ed25519 pubkey (NaCl box).
 *   3. B decrypts, signs the challenge + a nonce with its Ed25519 privkey,
 *      returns the signature.
 *   4. A verifies the signature against the stored Ed25519 pubkey.
 *
 * Passive observers see only a GATT connection with opaque encrypted bytes —
 * no identity is revealed unless the challenge succeeds.
 */
interface ContactRecognizer {
    fun identifyDevice(scanResult: ScanResult): Contact?
}

Dependencies & Libraries

Note on ML-KEM-768: BouncyCastle 1.77+ ships org.bouncycastle.pqc.crypto.mlkem.MLKEMParameters. Verify the specific artifact is bcprov-jdk18on not bcprov-jdk15on — the older artifact does not include the PQ primitives. If Tink is already in the build, prefer it for Ed25519 and X25519 and use BouncyCastle only for the KEM.

Platform Constraints

NFC

• Android Beam deprecated (Android 10+): setNdefPushMessage() and enableForegroundNdefPush() are no longer available. The replacement is NFC reader mode (NfcAdapter.enableReaderMode()): one device acts as an NDEF tag (using Host Card Emulation or a static NDEF tag record), the other scans it in reader mode. This works on all Android versions that support NFC (API 19+).
• iOS NFC: Core NFC in reader mode only — iPhones can scan NDEF tags but cannot act as a tag. QR code is the only viable iOS path for key exchange. This prototype targets Android; the QR fallback is the iOS bridge.
• NFC range: ~4 cm physical proximity. This is intentional — the tap gesture is the consent signal. Spoofing requires physical access.

BLE

• Minimum SDK for BLE advertising: API 21 (Android 5.0). Scanning is available from API 18, but advertising requires 21.
• MAC address randomisation: Android 8+ randomises the BLE MAC address per scan session. This is insufficient on its own to prevent tracking — a persistent advertisement payload would still correlate across MAC rotations. The payload must also rotate.
• Rotation interval: Every 15–20 minutes maximum. Shorter intervals reduce tracking risk; longer intervals save battery. 15 minutes is the recommended default.
• Background BLE: Android permits background BLE scanning with ACCESS_BACKGROUND_LOCATION (API 29+). The prototype does not require background scanning for MVP — foreground only is sufficient to validate the UX.

Cryptographic Performance on Mobile

The full key agreement completes well within the NFC tap interaction window (~1–2 seconds from tap to stored contact). No performance constraints apply.

QR Payload Size

KeyBundle serialised: 32 + 32 + 1184 + 8 = 1256 bytes raw. Base64url encoding: ~1675 characters. At QR version 40, ECC level L, byte mode capacity is 2953 bytes — this fits. At ECC level M (recommended for robustness) capacity is 2331 bytes — still fits for raw bytes if binary mode is used instead of base64url. Verify encoding mode in ZXing's BarcodeEncoder.encodeBitmap() to confirm binary vs character encoding is selected.

Build & Test Instructions

Prerequisites

• Android Studio Hedgehog (2023.1.1) or later
• Two physical Android devices with NFC support (NFC cannot be tested in the emulator)
• Both devices on API 21+ (API 29+ recommended for background location permission flow)
• JAVA_HOME pointing to JDK 17+

Project Setup

# Create a new Android project (Kotlin, empty activity)
# In Android Studio: File → New → New Project → Empty Views Activity
# Language: Kotlin, Min SDK: 21

# Or clone a reference skeleton and replace the module
git clone https://github.com/your-org/prototype-key-exchange.git
cd prototype-key-exchange

Gradle Dependencies

// build.gradle.kts (app module)
dependencies {
    // Google Tink for Ed25519, X25519, HKDF
    implementation("com.google.crypto.tink:tink-android:1.11.0")

    // BouncyCastle for ML-KEM-768
    implementation("org.bouncycastle:bcprov-jdk18on:1.78.1")

    // ZXing for QR generation and scanning
    implementation("com.journeyapps:zxing-android-embedded:4.3.0")

    // Room for contact store
    implementation("androidx.room:room-runtime:2.6.1")
    implementation("androidx.room:room-ktx:2.6.1")
    kapt("androidx.room:room-compiler:2.6.1")

    // Encrypted storage backed by Android Keystore
    implementation("androidx.security:security-crypto:1.1.0-alpha06")

    // Coroutines (BLE and NFC callbacks are async)
    implementation("org.jetbrains.kotlinx:kotlinx-coroutines-android:1.7.3")
}

Build

./gradlew assembleDebug

Deploy to Physical Devices

# Connect both devices via USB (enable USB debugging on each)
adb devices   # verify both appear

# Install on device 1
adb -s <DEVICE_1_SERIAL> install app/build/outputs/apk/debug/app-debug.apk

# Install on device 2
adb -s <DEVICE_2_SERIAL> install app/build/outputs/apk/debug/app-debug.apk

Run Unit Tests

./gradlew test
# Covers: X3DH shared secret derivation, KeyBundle serialisation, NDEF encode/decode

Run Instrumented Tests (Requires Physical Device)

# NFC and BLE tests require physical hardware — emulator will fail
./gradlew connectedAndroidTest -Pandroid.testInstrumentationRunnerArguments.annotation=PhysicalDeviceTest

Manual Test Flow

1. Open the app on both devices. Verify BLE beacons appear in logcat on both.
2. On Device A, tap "Show QR" or tap phones for NFC. On Device B, scan or tap.
3. Both devices should show "Contact stored" within 3 seconds (NFC) or 5 seconds (QR).
4. Force-close and restart both apps. Verify contacts persist.
5. Bring devices back into BLE range. Verify "Contact nearby" indicator appears.

Test Matrix

Success Criteria

1. NFC tap → contact stored in < 3 seconds (measured from first NFC field detection to Room insert confirmed).
2. QR scan → contact stored in < 5 seconds (measured from camera focus confirmed to Room insert confirmed).
3. Both devices derive an identical X3DH shared secret, verified by a deterministic test vector with a fixed seed.
4. BLE advertisement payload changes every rotationInterval; no payload repeats within a 60-minute observation window on a third scanning device.
5. After key exchange, devices mutually recognise each other over BLE within 10 seconds of coming within BLE range (challenge-response complete).
6. No identity information (feed_id, public key bytes, display name) appears in the BLE advertisement payload at any time; confirmed by packet capture on the third device.
7. Contact store (Room database) survives app force-stop, device reboot, and app update with data migration.

Risks & Unknowns

2-Week Day-by-Day Build Plan