diff options
Diffstat (limited to 'nearby/presence/README.md')
| -rw-r--r-- | nearby/presence/README.md | 236 |
1 files changed, 236 insertions, 0 deletions
diff --git a/nearby/presence/README.md b/nearby/presence/README.md new file mode 100644 index 0000000..07fb50f --- /dev/null +++ b/nearby/presence/README.md @@ -0,0 +1,236 @@ +# 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: + +``` +brew install openssl@3 +``` + +Your build system may still be picking up an older version so you will have to symlink to the brew installed version: +``` +brew link --force openssl +``` + +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. + +## 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 w/ cmake as per `ldt_np_c_sample` instructions. Fuzzers will be in `np_ffi_fuzz` in the build directory. + +## 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). |