nearby/presence/README.md

# What is this?

Implementations of XTS and LDT for Nearby Presence "v0" advertisements.

See the appendix below for more details on XTS and LDT.

## Project structure

*Note all new crates follow the convention of using underscore `_` instead of
hyphen `-` in crate names

### `ldt`

An implementation
of [`LDT`](https://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/1619-2007-NIST-Submission.pdf)
which can use `xts-aes` as its tweakable block cipher.

### `ldt_tbc`

The Tweakable Block Cipher traits for use in LDT. These traits have
implementations in the `xts_aes`

### `ldt_np_adv`

Higher-level wrapper around the core LDT algorithm that does key derivation and
payload validation the way Nearby Presence advertisements need.

### `ldt_np_adv_ffi`

C API for rust library, currently exposes C/C++ clients the needed API's to use
the NP specific LDT rust implementation.
For an example of how to integrate with these API's see program
in `ldt_np_c_sample`

### `ldt_np_c_sample`

Sample c program which provides its own OpenSSL based AES implementation to
encrypt data through the LDT rust implementation
An example of how to interface with the `ldt_np_adv_ffi` API's

### `np_hkdf`

The Key Derivation functions used for creating keys used by nearby presence from
a key_seed

### `xts_aes`

An implementation
of [`XTS-AES`](https://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/1619-2007-NIST-Submission.pdf)

## Setup for MacOS local development

Dependencies:

```
brew install protobuf rapidjson google-benchmark
```

We depend on OpenSSL of version at least 3.0.5 being installed on your machine
to build the fuzzers, for macOS run:

The in-box version of Clang which comes from XCode developer tools does not have
a fuzzer runtime so we will have to use our own

```
brew install llvm
```

then to override the default version it needs to come before it in $PATH. first
find your path:

```
$(brew --prefix llvm)/bin
```

then add this to the beginning of your path

```
echo 'export PATH="/opt/homebrew/opt/llvm/bin:$PATH"' >> ~/.bash_profile
export PATH="/opt/homebrew/opt/llvm/bin:$PATH"
```

verify success with:

```
clang --version
```

it should display the path to the homebrew version and not the xcode version.

Some other dependencies you may need include:

```
brew install ninja bindgen
```

## Examples

Examples use [clap](https://docs.rs/clap/latest/clap/) for nice CLIs, so try
running with `--help` to see all args.

*Note:* the examples are in the `ldt` crate, so `cd` into that first.

### `ldt_prp`

Confirm that LDT is, in fact, behaving as a PRP. That is, flipping one bit in
the ciphertext is on average going to flip half of the bits in the decrypted
plaintext, and that a change to the first `n` bytes of plaintext is increasingly
likely to be detected as `n` increases.

```
cargo run --release --example ldt_prp -- \
    --trials 1000000 \
    --check-leading-bytes 16
```

### `ldt_benchmark`

For interactive exploration of LDT performance looking for a needle in a
haystack of ciphertexts.

```
cargo run --release --example ldt_benchmark -- \
    --trials 500 \
    --keys 1000
```

### `ldt_np_c_sample`

From the root directory run the following commands to build and run the C
sample.

```
mkdir -p cmake-build && cd cmake-build
cmake ..
make
./ldt_np_c_sample/sample
```

### `ldt_np_c_sample/tests`

Test cases for the ldt_np_adv_ffi C API which are built alongside the sample,
use the following commands to run the tests, from root of repo:

```
mkdir -p cmake-build && cd cmake-build
cmake .. -DENABLE_TESTS=TRUE
make
cd ldt_np_c_sample/tests && ctest
```

you can then view the output of the tests
in `ldt_np_c_sample/tests/Testing/Temporary/LastTest.log`

To run the benchmarks:

`ldt_np_c_sample/tests/benchmarks`

## Fuzzing

To build all the fuzzers, run `scripts/build-fuzzers.sh`.

### Rust

Crates with fuzzers: `ldt`, `ldt_np_adv`, `xts_aes`

- `cd` to a crate's directory
- `cargo fuzz list` to list available fuzzers
- `cargo fuzz run [fuzzer name]` to run a fuzzer

### C

Build cmake project with `-DENABLE_FUZZ=true`<br>
Fuzz targets will be output to the build dir for:<br>

- `ldt_np_adv_ffi_fuzz`<br>
- `np_cpp_ffi/fuzz`
    - To run `fuzzer_np_cpp_deserialize`
      use: `./fuzzer_np_cpp_deserialize -max_len=255 corpus`
    - The `corpus` directory provides seed data to help the fuzzer generate
      more relevant data to input

## Cross-compilation for Android

- Add the 64bit ARM target to the stable and nightly toolchains:
    - `rustup target add aarch64-linux-android`
    - `rustup target add aarch64-linux-android --toolchain nightly`

- Install the v22 NDK that still links against `libgcc` the way rust's stdlib
  expects.
    - Newer NDKs use `libunwind` instead, which can be used just fine if you
      build your own rust stdlib, but for our purposes there's no problem with
      just using NDK 22
    - `./sdkmanager --install platform-tools 'ndk;22.0.7026061'`

- Configure the linker used for the ARMv8 Android target to be the NDK's linker.
    - `export CARGO_TARGET_AARCH64_LINUX_ANDROID_LINKER=$ANDROID_HOME/ndk/22.0.7026061/toolchains/llvm/prebuilt/linux-x86_64/bin/aarch64-linux-android30-clang`
    - `export PKG_CONFIG_SYSROOT_DIR=$ANDROID_HOME/ndk/22.0.7026061/toolchains/llvm/prebuilt/linux-x86_64/sysroot`

- See if everything builds, using the nightly toolchain for the moment to
  convince the `aes` crate to use intrinsics on aarch64
    - `cargo +nightly build --workspace --all-targets --target aarch64-linux-android`
    - `cargo +nightly bench --workspace --no-run --target aarch64-linux-android`

- Prepare a place for the benchmark to be on the phone

    - `adb shell`
    - then
    - `mkdir -p /data/local/tmp/np && cd /data/local/tmp/np`
    - Leave the shell on the phone open so you can use it to run the benchmark.

- Find the benchmark binary in the build products

    - Use whatever directory you configured as the `target-dir` in
      `.cargo/config.toml` initially, and look for the file without the
      trailing `.d`.
    - `find TARGET_DIR -name 'ldt_scan*' | grep android`
    - Copy the file to the phone
    - `adb push FILE_FOUND_ABOVE /data/local/tmp/np/`

- In your `adb shell`, run the benchmark

    - `./ldt_scan-... --bench`

### Building min-sized release cross-compiled for Android

- Copy and paste the following into your `~/.cargo/config.toml`, replacing with
  a path to your NDK and Host OS

```
[target.aarch64-linux-android]
# Replace this with a path to your ndk version and the prebuilt toolchain for your Host OS
linker = "Library/Android/sdk/ndk/23.2.8568313/toolchains/llvm/prebuilt/darwin-x86_64/bin/aarch64-linux-android21-clang"
```

- then run:
  `cargo +nightly build -Z build-std=core,alloc -Z build-std-features=panic_immediate_abort --target aarch64-linux-android --profile release-min-size`

## Appendix

### XTS

XTS-AES has a NIST
spec: [The XTS-AES Tweakable Block Cipher - An Extract from IEEE Std 1619-2007](https://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/1619-2007-NIST-Submission.pdf)

XTS is a scheme for turning a block cipher (AES in this case) into a _tweakable_
block cipher. Tweakable block ciphers incorporate a _tweak_ which is cheaper to
change than the key, with the assumption being that the tweak will change with
each block or sequence of blocks. XTS-AES in particular is used in disk
encryption, where the sector number or the like might be incorporated into the
tweak to prevent the same data in different places on the disk being encrypted
into the same ciphertext.

### LDT

LDT is the current state of the art in length
doublers: [Efficient Length Doubling From Tweakable Block Ciphers](https://eprint.iacr.org/2017/841.pdf)
. It builds on top of a tweakable block cipher, which is why we also have an XTS
implementation.

A length doubler is a way of adapting a block cipher to act as a secure PRP (
pseudo random permutation) on data of lengths in `[block size, 2 * block size)`.
For comparison, block ciphers act as PRPs on one block at a time rather than the
whole message. Wide block modes would also work, but have higher overhead.

We use a length doubler in Nearby Presence so that changing any ciphertext bit
should flip each bit in the decrypted plaintext with 50% probability for each
bit, making it possible to detect changes anywhere because it is very unlikely
for none of the bit flips to affect the metadata key (which has a known digest).