This post describes nonce-sanitizer: a very simple tool that prevents the major screw-up everyone is scared to make: šŸ˜± repeated nonces under the same key šŸ˜±. In short, nonce-sanitizer provides seat belts as a thin wrapper around the AEAD code that adds a hard asserd that nonces donā€™t repeat.

But thatā€™s such a n00bā€™s mistake! If you think ā€œIā€™m a good programmer, I wonā€™t ever make that mistakeā€, think harder. Even the crypto grandmasters make this mistake. It can happen to anyone anytime ā€”even during an unrelated refactor. Do you have tests that would catch this bug? Do they run automatically every time you touch code?

Working principle #

nonce-sanitizer implements an AEAD interface. The input/output behavior is identical to the AEAD mode selected. (Currently, ChaCha20Poly1305 and AES-GCM.) In addition, it will check in the background if the nonce passed is sane, and bail if it isnā€™t. For this, nonce-sanitizer keeps the passed nonces in an internal state. The current definition of sane is: the same combination (key, nonce) hasnā€™t been passed before.1

Functionality-wise, this tool internally looks something like this:

 func encryptAEAD_NonceSanitizer(key, nonce, plaintext) -> ciphertext {
    if isRepeatedNonce(key, nonce, plaintext) {
       bail();
    }
    ciphertext = encryptAEAD(key, nonce, plaintext)
 }

Developer ergonomics #

To use nonce-sanitizer, you just replace the calls to AEAD encrypt with the implementation provided by nonce-sanitizer. Everything else should just work. This is 100% backwards compatible ā€”the encryption behavior remains identical. Thereā€™s no need to bump any protocol version.

  • In the happy path, if your nonces behave, one you set this up, you can forget about it. So this is kind of additive security precaution
  • In the sad case (naughty nonces), nonce-sanitizer will bail and prevent the confidentiality loss.

Thereā€™s no need to configure anything. Performance-wise, nonce-sanitizer takes a small hit. Check if this is significant in your application.

Golang implementation #

A PoC in golang is available at https://github.com/oreparaz/go-nonce-sanitizer. This implementation wraps golang.org/x/crypto/chacha20poly1305.

How to use it. The interface transparently wraps the AEAD mode, so you can use it as the AEAD mode. This is the single-line code modification needed to add nonce-sanitizer to age:

diff --git a/internal/stream/stream.go b/internal/stream/stream.go
index 7cf02c4..bc8a321 100644
--- a/internal/stream/stream.go
+++ b/internal/stream/stream.go
@@ -11,7 +11,7 @@ import (
        "fmt"
        "io"

-       "golang.org/x/crypto/chacha20poly1305"
+       "github.com/oreparaz/go-nonce-sanitizer/chacha20poly1305"
        "golang.org/x/crypto/poly1305"
 )

Raw performance. On a GCP ec2-micro instance:

  • for long packets (8 kB), the overhead is small (less than 10% loss of throughput)
  • for IP packets (1350 bytes), the overhead is about 33% less throughput
  • for very short packets (64 bytes), the overhead is around 3x slowdown

Raw data: output of go test -bench=.:

goos: linux
goarch: amd64
pkg: github.com/oreparaz/go-nonce-sanitizer/chacha20poly1305
cpu: Intel(R) Xeon(R) CPU @ 2.20GHz
Benchmark/Seal-WithoutNonceSanitizer-64-2     293.65 MB/s       0 B/op     0 allocs/op
Benchmark/Seal-WithNonceSanitizer-64-2        109.59 MB/s      49 B/op     2 allocs/op
Benchmark/Seal-WithoutNonceSanitizer-1350-2  1147.98 MB/s       0 B/op     0 allocs/op
Benchmark/Seal-WithNonceSanitizer-1350-2      857.35 MB/s      50 B/op     2 allocs/op
Benchmark/Seal-WithoutNonceSanitizer-8192-2  1407.33 MB/s       0 B/op     0 allocs/op
Benchmark/Seal-WithNonceSanitizer-8192-2     1323.52 MB/s      55 B/op     2 allocs/op
PASS
ok      github.com/oreparaz/go-nonce-sanitizer/chacha20poly1305      8.727s

Performance of age. In a file encryption application like age, the overhead is imperceptible to the human eye. With instrumentation, encryption of a 650 MB file takes 2.0 seconds. Without instrumentation, it takes 1.9 seconds.

# with instrumentation
$ time ./age -r age1ql3z7hjy54pw3hyww5ayyfg7zqgvc7w3j2elw8zmrj2kg5sfn9aqmcac8p < /tmp/junk > /tmp/junk.age

real	0m2.082s
user	0m0.645s
sys	0m1.001s

# without instrumentation
$ time ./age -r age1ql3z7hjy54pw3hyww5ayyfg7zqgvc7w3j2elw8zmrj2kg5sfn9aqmcac8p < /tmp/junk > /tmp/junk.age

real	0m1.969s
user	0m0.605s
sys	0m0.944s

FAQ #

When should I use it? Is it good for me? If you are picking nonces, nonce-sanitizer is for you. If your library picks nonces for you, youā€™re fine.2

Iā€™m using libsodium, do I have to worry? You can use a well-established library like libsodium or tink and still misuse nonces. So refer to the previous point: if youā€™re picking nonces, yes, you can use nonce-sanitizer.

Why should I not use nonce-sanitizer? Perhaps if youā€™re struggling for performance, or are very tight on RAM. But really, so many people have tripped here before, so think twice.

Will this eat all my RAM?. The internal state that stores nonces grows as more nonces are passed. This grows until a threshold is hit, and from there on old nonces are discarded. So the RAM usage is capped and wonā€™t grow unbounded. This is a tunable parameter.

Is it going to ruin performance? There are too many different applications of AEAD to make general statements about the impact of this instrumentation. In general, nonce-sanitizer has small impact in client-side code (where an increased memory usage is tolerable), or applications that run in human time (and arenā€™t affected by slight increase in latency). Busy servers are trickier, but probably acceptable for debug builds/deployments.

Iā€™m using random nonces, I donā€™t need this? You can still screw it up, see https://chromium-review.googlesource.com/c/chromiumos/platform/ec/+/1592990 (https://www.chromium.org/chromium-os/u2f-ecdsa-vulnerability/). Would you notice in that case?

Tell me about misuse-resistant modes. You should use them! But sometimes itā€™s not easy to retrofit those.

Why havenā€™t I heard about this before? Thatā€™s a good question. We can only speculate. This isnā€™t rocket science, but probably keeping track of all nonces was too expensive. But today memory in phones and computers is cheap.

Inspiration. This tool takes inspiration from memory sanitizers for non-memory safe languages. Memory sanitizers shadow every byte of memory from your program to hopefully detect memory misuse before they become a real problem. Thanks to tools like AddressSanitizer or Valgrind we can write C and not stress too much about it. Tools help us sleep well at night. (Note that nonce-sanitizer applies both to non-memory safe and memory safe languages ā€“ memory safety doesnā€™t have anything to do with misusing nonces.)

Limitations #

The tool keeps some state in RAM. The tool wonā€™t detect all nonce collisions since this state is pruned from time to time.

Extensions #

Iā€™d love to see nonce-sanitizer in other languages, or integrated into existing libraries. Iā€™m not planning to work on this but ping me if you want some pointers to work on this.

Optimizations / internals #

The following design decisions might be useful if you want to reimplement this:

  • Should I store the cryptographic key itself? You can make all the data structures secret-free by storing a hash of the key if you need it. Unsure if this is worth it if the key lives in the same memory space

  • Should I include plaintexts also in the map? The only reason for this is to not have false alerts where the same (key, nonce, plaintext) is passed. This isnā€™t a violation of AEAD usage ā€”youā€™re performing exactly the same computation

  • What data structure should we use for storing nonces? It just should be very fast. In golang we resort to a hash map. This PoC implementation can be for sure optimized; PRs are welcome.
  • What prunning strategy should we use? Right now we store the last 1000 nonces, and prune the cache from time to time, so that memory usage doesnā€™t grow unbounded. You can use a circular buffer to have consistent performance, tbd what the sweet thresholds are.
    • You could probably use distinguished points to (probabilistically) detect collisions without enormous amounts of memory. (Keeping track only of those nonces with a certain prefix.) Feels like a combined method would be a good choice: keep the last N nonces and keep the last N ā€œdistinguishedā€ nonces.
  • Should we compress IVs? too fancy for a V1.0
  • Should we check for repeated nonces upon receiving? Not duplicating nonces is a sender responsability (as the sender will bear the consequences of the confidentiality loss), but it seems cheap enough to also do it on the receiving side. This might help spot buggy implementation on the remote peer.

  1. Thereā€™s an exception for this: same (key, nonce) combinations are allowed if the plaintext is the same. This exception isnā€™t implemented yet.Ā ↩

  2. There are cases (like TLS 1.3) in which a buggy implementation that reuses nonces just wonā€™t work at all (wonā€™t be interoperable) because the protocol mandates an implicit nonce (such as a sequence number). This is a good design principle that by design makes reusing nonces very difficult.Ā ↩