Two days ago I've given a talk about memory protections and crypto data at the Bay Area Rust Meetup held by Mozilla San Francisco and dedicated to the topic of cryptography. The corresponding project I created is also available on Github as project TARS.

This whole meetup was filled with great talks:

• Thoughts on Rust Cryptography, by Tony Arcieri
• Crypto Interface Pitfalls (and how to avoid them), by Sean Devlin
• Using Linux Kernel crypto APIs from Rust, by Matthew McPherrin
• std::rand::random::<Talk>(), by Huon Wilson

This is the description of an arithmetic bug I found¹ in one of the operations used during the computations of Curve25519 scalar multiplications in the TweetNaCl library.

The culprit is the code handling the final reduction modulo 2²⁵⁵ - 19 located in the function pack25519(). The following snippet presents the original code (version 20131229) of this function:

sv pack25519(u8 *o, const gf n)
{
  int i,j,b;
  gf m,t;
  FOR(i,16) t[i]=n[i];
  car25519(t);
  car25519(t);
  car25519(t);
  FOR(j,2) {
    m[0]=t[0]-0xffed;
    for(i=1;i<15;i++) {
      m[i]=t[i]-0xffff-((m[i-1]>>16)&1);
      m[i-1]&=0xffff;
    }
    m[15]=t[15]-0x7fff-((m[14]>>16)&1);
    b=(m[15]>>16)&1;
    m[15]&=0xffff;
    sel25519(t,m,1-b);
  }
  FOR(i,16) {
    o[2*i]=t[i]&0xff;
    o[2*i+1]=t[i]>>8;
  }
}

This bug is triggered when the last limb n[15] of the input argument n of this function is greater or equal than 0xffff. In these cases the result of the scalar multiplication is not reduced as expected resulting in a wrong packed value. This code can be fixed simply by replacing m[15]&=0xffff; by m[14]&=0xffff;.

Examples triggering this error are easy to generate. For instance, here is a case where a carefully selected² scalar n when multiplied with the base point (9, y) in the Montgomery curve representation and using TweetNaCl's scalarmult_base() function outputs a wrong result:

Scalar value n:
 76f6507a08e5d77a9a7b316d93cbb59b
 afa2e13d1f84d181a35779e7fc471d19

Wrong result obtained from bugged scalarmult_base(n) in pack25519():
 829253d8647cd88e3fb76358cfef0a91
 51aa8e7189fb6326dfb0603f6bff0000

Expected result obtained from ref implementation:
 6f9253d8647cd88e3fb76358cfef0a91
 51aa8e7189fb6326dfb0603f6bffff7f

This error should be relatively frequent, it happens around or a bit less than one time for every 2¹⁶ computations for computations with different scalar values or different points. However, beyond the wrongness of the resulting x-coordinate³, and because this error happens at the end of computations steps there is no risk it could lead to greater damages like for instance revealing bits of user's secret. So just update your code with the new version (20140427) and you'll be fine.

I see two main use cases: one where relatively short messages or packets are encrypted and another one where files of any size could be encrypted. As the title of this post implies I deliberately ignore¹ the recent AEAD submissions made in the CAESAR competition as the process will not be achieved this year. Currently what I think are the most interesting schemes for encrypting and authenticating for these two uses cases:

In a messages scenario you could either use the crypto_secretbox() function implemented in NaCl, it is based on Salsa20 for encryption and Poly1305 for authentication, or you could use ChaCha20 for encryption again combined with Poly1305 as it is currently specified for inclusion in SSL/TLS². Assuming your protocol uses as expected deterministic nonces and somehow split messages in packets in another layer of your application thus not having to encrypt multi-terabytes files, both schemes are equally fines. The only distinction I would make is that crypto_secretbox() is more tunnel-oriented (or end-to-end) in the sense that as it doesn't provide additional data authentication, you would use it in a context where everything must be encrypted. Whereas the second scheme is a bit more versatile it can mix authenticated plaintext with encrypted-then-authenticated data.

In a file encryption scenario crypto_secretbox() is more adapted as it is based on XSalsa meaning that it accepts larger nonces than a pure Salsa or ChaCha version. Therefore it may safely uses random nonces for encryption while keeping 64 bits internally as counter which is large enough to virtually encrypt files up to 2⁷⁰ bytes. Moreover in this context there is usually no need for authentication of additional data so the lack of this feature in crypto_secretbox() is not a limitation in this case. The scheme based on ChaCha on the other end is not a good fit, it is not conceived for that purpose, it can't use random nonces and its size of ciphertext is limited to 2³⁸ bytes.

However for both there is a bigger problem that may prevent them to be used in encrypting large files as their interfaces require that all the data to fit in memory before starting encryption/decryption. Actually stateful encryption and decryption present an important challenge for doing it securely and efficiently in encrypt-then-mac schemes, especially for decryption because you'd want to only let the caller access the plaintext data once the ciphertext has been fully authenticated while at the same time you'd want to buffer the decryption in order to alleviate the memory footprint. Of course you could authenticate and decrypt in two separate passes but in this case it wouldn't be very efficient. So, for now there is no perfect solution for this use case.

As cryptographic implementations naturally strive for better and better performances it's actually very common to see generic implementations dropped in favor of highly specialized ones. Therefore, there's often a dedicated implementation not only for any single family of crypto algorithm but also for any single combination of parameters and cpu architectures. The obvious downside is this could easily result in large code bases difficult to verify and audit.

TweetNaCl – a compact implementation of NaCl – developped by Bernstein et al. discusses the challenges introduced by these specialized cryptographic implementations:

However, NaCl’s performance comes at a price. A single NaCl function usually consists of several different implementations, often including multiple assembly-language implementations optimized for different CPUs. NaCl’s compilation system is correspondingly complicated. Auditing the NaCl source is a time-consuming job. For example, four implementations of the ed25519 signature system have been publicly available and waiting for integration into NaCl since 2011, but in total they consist of 5521 lines of C code and 16184 lines of qhasm code.

Highlighting a bug found in the relatively large amount of code implementing operations on Edwards curves such as point addition.

Partial audits have revealed a bug in this software (r1 += 0 + carry should be r2 += 0 + carry in amd64-64-24k) that would not be caught by random tests; this illustrates the importance of audits. There has been some progress towards computer verification of formal proofs of correctness of software, but this progress is still far from complete verification of a usable high-security cryptographic library.

The support for the Ed25519 signature scheme has recently been committed to OpenSSH and it relies on the SUPERCOP implementation. Damien Miller:

Markus has just committed a few changes that add support for the Ed25519 signature algorithm as a new private key type.

I'm not holding my breath for a quick implementation of Ed25519 in Common Crypto though.

The current situation of the crypto implementation of OpenSSH as shipped by Apple in OS X 10.9 is a real mess. Continuing their push in favor of Common Crypto and their deprecating of libcrypto (OpenSSL) they implemented in their version of OpenSSH a new crypto module compatible with OpenSSL's interface but targetting the Common Crypto library instead. However this implementation seems currently incomplete due to limitations of Common Crypto and as a result they also have embedded fallbacks on big chunks of OpenSSL code.

A concrete shortcoming is that there is actually no elliptic curve support, thus it is not possible to generate EC keys and use ECDSA signatures for authentication.

The Chrome browser provides an implementation (p224_spake.h, p224_spake.cc) for the password-based encrypted key exchange protocol SPAKE2. This code is implemented in C++ and its operations are based over the elliptic group NIST P-224, using their standalone implementation (p224.h, p224.cc).

Note: In the SPAKE protocols it is vitally important to either validate the public points used to mask the password or to use as they do in this implementation hard-coded static points with verifiable non-random seeds.

From this thread, what seems to be the main opposing argument against the choice of ChaCha as new cipher in TLS is that Salsa20 presents the advantage of already being standardized in the eSTREAM portfolio.

Jacob Hoffman-Andrews detailing Twitter's TLS session tickets implementation for session resumption with forward secrecy:

We have a set of key generator machines, of which one is the leader. The leader generates a fresh session ticket key every twelve hours and zeroes old keys after thirty-six hours. Keys are stored in tmpfs (a RAM-based filesystem), with no swap partitions configured. It's important that there be no swap, because tmpfs will use swap if available, which could write keys to long-term disk storage.

Every five minutes, our frontends fetch the latest ticket keys from a key generator machine via SSH.

The course is intended for graduate students in cryptography and mathematics. Introductory topics on elliptic curves and cryptographic applications will be covered, with an emphasis on providing a strong background in support of the research talks at ECC.

Slides are available online and it's very good, it covers the main fields related to EC.

And, don't miss the rule 34 of crypto from the lecture on pairings:

Rule 34 of crypto. If you can think of a crypto scenario, there is already a pairing-based article about it.

Initial post.