Noise box update

[enkore]

Our current noise implementation is not compliant to the current standard.

IMO the only difference to a proper Noise_X_25519_AESGCM_SHA512 is the KDF which was changed from a homebrew version to the independentenly used and published HKDF.

Since the change would invalidate all drop messages etc., these need to be re-encrypted when upgrading.

When making the change, a provision for proper crypto agility should be made as well. E.g. a type byte prefix or a plain-text prefix. Currently this would be possible via SUITE_NAME, since SUITE_NAME is mixed into the KDF this would equire a trial decryption for each possible algorithm, therefore the approach is not feasible.

There is a now a current noise implementation by Rhys Weatherley available: https://github.com/rweather/noise-java (MIT). It is based on the JCE interface and therefore implements a good bit of crypto (25519, 448, ChaCha, Blake) in Java itself. Development of it started last month.

Pinging @roeslpa

[enkore]

In terms of "starter pack" algorithms for the new noise boxes I would
recommend AES-GCM plus BLAKE2b for accelerated (AES-NI or equivalent,
I have no idea whether this is easily queried via
Java/JCE/BouncyCastle) or desktop use, while ChaCha20-Poly1305 plus
BLAKE2b is preferable for non-accelerated or mobile use. Both choices
provide a 128 bit authentication tag and a wide choice of hash lengths
(just stick with 512 bit? Noise defines BLAKE2b = 512B).

Since it is not possible to conceal that these are noise boxes when
communicated I would imho prefer a simple plain text prefix to
indicate the cipher suite over a type byte. We could just use the
noise protocol name defined by the cipher suite (and the fact we use
the one-way-protocol / Noise_X).

w.r.t. noise-java, maybe use it, but use BouncyCastle crypto? Since
it's in early development we may be able to contribute such code. Or
we stick with implementing it ourselves.

[roeslpa]

I see the performance advances and the ability to switch to different algorithms when one algorithm is exposed to be weak by providing more cipher suites. But: the main argument for using Noise was the indistinguishability of cipher texts (except from the lengths). By adding information on the used algorithms in plain, which might be chosen depending on the device, identities and their drop messages might become observable. I am not in favor of learning the algorithm by trying to decrypt the cipher text as well, since an identity already has to find messages addressed to her by trying to decrypt them. As long as there is no better solution for this issue I would suggest to chose the best algorithms (one symm., one asymm.) regarding security and performance (preferably with reasons for the choices), or stick to the current algorithms.

Regarding the implementation, even if using the JCE interface is very clean, I suggest to use established libraries since Noise mostly uses established algorithms.

Lastly, I would like to explicitly name the index DMs which would need to be reencrypted due to the KDF update.

[enkore]

If we go for a single algorithm then I think ChaCha20-Poly1305 is preferable to AES-GCM, since it is better suited for short (<2.5K drop length limit) messages. [though the difference in energy use and runtime is likely academic with all the android stuff going on anyway, and considering this is a chat application and not a 500k-msg/second broker]. That being said there is no problem per se in sticking with AES-GCM.

The spec recommends ("Application responsibilities")

Type fields: Applications are recommended to include a single-byte type field prior to each Noise handshake message (and prior to the length field, if one is included). A recommended idiom is for the value zero to indicate no change from the current Noise protocol, and for applications to reject messages with an unknown value. This allows future protocol versions to specify handshake re-initialization or any other compatibility-breaking change (protocol extensions that don't break compatibility can be handled within Noise payloads).

[roeslpa]

Okay, that sounds reasonable. Especially since mobile devices might suffer from receiving drop messages as soon as real drop ID collisions are provoked.

Yes, prepending a version field is sensible but providing multiple cipher suites, which usage depends on the client device, could reveal information on the client.

[enkore]

Yes, prepending a version field is sensible but providing multiple cipher suites, which usage depends on the client device, could reveal information on the client.

I see/understand your concerns there

[jmt85]

spike needed

[roeslpa]

(don't know what spike means in this context, but: )
My advice:

• update the KDF in our Noise implementation
• prepend a version field in Drop messages
• reencrypt index DMs in the updated client
• if desired different curve and symmetric encryption scheme is used. Currently both of our primitives are very frequently used.
• during the roll out of the updated client, messages could be sent twice (one for each KDF) for simplicity or (if traffic is already expensive) we could send the key derived from the old KDF encrypted with the key derived from the new KDF and the actual message is encrypted with the old key (remember the KDF is used twice in each message). The overhead would increase negligibly, the message would be readable from both versions but the implementation overhead could be too high.

[enkore]

spike is devmanagement term for "someone needs to spend an hour / a couple hours to see how this can be done and how much work that may be".

[audax]

• update the KDF in our Noise implementation ✓

  We can keep using our Noise implementation imho.

• prepend a version field in Drop messages ✓

  We already have a version field as the first byte in any drop message

• reencrypt index DMs in the updated client ✓

  I don't see a problem here

• if desired different curve and symmetric encryption scheme is used. Currently both of our primitives are very frequently used. ✓

  @roeslpa our primitves are now supported directly in spongycastle: https://www.bouncycastle.org/docs/docs1.5on/index.html (spongycastle is the same library, it just has a different name for packaging reasons)
  Since I don't feel confident to evaluate that part: @enkore Can we use this instead of our packaged c-library?

• during the roll out of the updated client, messages could be sent twice (one for each KDF) for simplicity or (if traffic is already expensive) we could send the key derived from the old KDF encrypted with the key derived from the new KDF and the actual message is encrypted with the old key (remember the KDF is used twice in each message). The overhead would increase negligibly, the message would be readable from both versions but the implementation overhead could be too high. ✓

  Sending each message twice would be a straightforward solution, but we need to remove duplicate messages. This can by done by using the timestamp, since the timestamp is sent in milliseconds which is precise enough.

---

We can and should update the noise protocol. When we do this, we should first switch to another crypto provider to remove as much self-maintained code as possible. After we switched to another cryptoprovider (libsodium or bouncy/spongycastle) for the noise box crypto, we can implement both KDF methods and increment the version byte of the encrypted drop message.
In the transition period we send each drop message twice, once with the old KDF and once with the new KDF. The clients ignore duplicate messages. The timestamp of a drop message can be used for this purpose.

[roeslpa]

• Regarding the implementation of the primitives: I suggest to use implementations in faster languages than Java and therefore would not replace TweetNaCl if we keep Curve25519.
• Regrading the choice of primitives: @enkore which primitives would you like to use?
• Regarding everything else: I support @audax summary

[audax]

We will take a look at libsodium instead of Bouncycastle. Even if we can't replace TweetNaCl, maybe we can replace BouncyCastle. From an end user perspective, this would probably increase the performance.

Replacing both BouncyCastle and TweetNaCl would be great, since we wouldn't have to maintain the TweetNaCl bindings ourselves. They are fiddly on Android and an annoyance to set up on desktop development systems.

I'll port our noise stuff to libsodium and run them side by side for testing, then can we implemented the updated noise protocol. This will of course be just a proof of concept and will have to be reviewed by people who actually understand the crypto stuff before we put it into production. From a software perspective, this means that the CryptoUtils will become an Interface with our current implementation as the default implementation and a drop in replacement with the alternative implementation.

[enkore]

From a software perspective, this means that the CryptoUtils will become an Interface with our current implementation as the default implementation and a drop in replacement with the alternative implementation.

I think it would be wise to split it up first, since it holds unrelated functionality in one class at the moment (encrypting files, encrypting noiseboxes... at least these two should be in separate interfaces).

[audax]

Indeed. I'll make one noise-stuff interface and one symmetric-stuff interface at least. Maybe I'll split it up further.

[audax]

So...I evaluated this libsodium stuff. My findings are:

• Seems to work on Android just fine by importing the AAR package. This includes the native library and just works
• The library also runs on the JVM, but we need to supply the native libsodium ourselves. The projects has a docker container to build libsodium and we can use those native libs in the core. They are not included in the jar that we can import in the build-file.
• I am bad with gradle and I hate JNI
• It seems that Blake2 is missing in the JNI bindings
• The curve25519 is fine and the chacha-stuff is also available
• I hate build systems

Spike done.

[thechauffeur]

To thoroughly discuss the end of this spike it would be good to have all points mentioned (see above) here addressed in some way. E.g.:

• @roeslpa asked @enkore about the primitives and some of you already talked in the office / chat about other primitives. A summary at least would be nice.
• Regarding TweetNaCl / bouncy-/spongycastle and libsodium I'm missing some comparisons and confrontations about advantages / disadvantages, why this and not that etc.

[enkore]

Primitives:

• Symmetric encryption uses AES-GCM-256. However, that is the slowest choice for computers with no AES instructions (eg. Intel AES-NI, ARM NEON [all aarch64/arm64 devices]).

  A commonly used alternative is ChaCha20-Poly1305. Like AES-GCM-256 it uses 256 bit keys and generates a 128 bit authentication tag. On hardware w/o AES acceleration it vastly outperforms AES. It also seems to outperform AES on ARM devices (hence it's use for eg. TLS by Google on Android).

  This mostly matters for box, not so much for the drop due to the short message length (<2.5 KB). But we could just use it everywhere.

• Hashes / MAC. AFAIK we already use BLAKE2b in the box module. Nothing to do here?

---

TweetNaCl vs. *Castle vs libsodium:

We don't use TweetNaCl, only a subset of it, implementing Curve25519 crypto and nothing else. The full TweetNaCl is (API wise) identical to NaCl identical to libsodium.

All of these implement: ChaCha20-Poly1305, BLAKE2 or SHA2-512, Curve25519, Ed25519.

None of them is alone sufficient to support the current state of our crypto. Because AES-GCM is only available if hardware support is available, which is nothing we can rely on.

*Castle implements all crypto in pure Java. I have a bad feeling about that. It doesn't seem to have ever been audited / reviewed. In recent versions it also includes Curve25519.

OpenSSL (in recent versions) has all the algos we need (including Curve25519, which is more accurately called X25519 in libcrypto). This is what eg. Signal uses (and of course countless others).

Even though OpenSSL has had many vulnerabilities in the past (many of these were in fact developed with|for OpenSSL, and first patched in it - only later other libraries where updated), and still suffers from some poor APIs, I think it is a solid choice if cross-platform crypto is needed with many primitives.

[audax]

Comparison between the libs:

TweetNaCl:

• We wrote the JNI bindings ourselves.
• It's in C
• We maintain the build config and esp. the Android integration ourselves and it is a pain on Android

Bouncy/Spongy:

• Java-Code, so no JNI-stuff
• Probably not the most secure stuff, but we are just guessing
• Horribly slow

Sodium:

• C
• Has bindings to every language out there that I can think of
• JNI bindings and esp. a prepared Android package are available, so much less build-horror

OpenSSL:

• Has all the stuff
• Needs a spike

[enkore]

Oh right, I totally forgot how slow the castles are.

[audax]

Currently about 20s for a 20mb file slow :(

[enkore]

For detailed benchmarks of OpenSSL across many different CPUs I'll refer to: borgbackup/borg#45 (comment) These more or less transfer 1:1 to other optimized libraries (libsodium/NaCl)

Notice how even the little ARM Cortex A53 manages to crank out almost 250 MB/s with ChaCha20-Poly1305. Also notice how BLAKE2 is not always the better choice compared to SHA-2 (the aforementioned ARM box w/ NEON).

Btw.: AES-OCB may look very nice in these benchmarks, almost always outperforming everyone else, but bear in mind that it comes with a license fee when deployed in a non-OSI-licensed piece of software.

[audax]

@jan-schreib If you'd like to take a look at the build-pain for libsodium-jni, esp. on Windows. Maybe it is not so bad…

[enkore]

When implementing the update we also want to work towards personalizing the noise boxes, since they are used in different context and an attacker should not be able to swap noise boxes from different contexts (even if their contents might not make sense in the swapped context, blocking the possibility at this level makes it easier and safer to use)¹. In noise protocol terms this would mean that we assign a bytestring to every context and use it as the prologue (which is hashed by both parties into the handshake hash h).

For example, noise boxes for the index API would get qabel-index-api or api.index.qabel.org, while drop messages would have message.drop.qabel.org or similar, while the index DM would get index.dm.box.qabel.org (or whatever).

¹ The cryptographic principle here is called the Horton principle: authenticate what is meant, not what is said.