Skip navigation

Bay Area Rust Meetup on Crypto

20 December 2014

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:

Arithmetic Bug in TweetNaCl

28 April 2014

This is the description of an arithmetic bug I found1 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 2255 - 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];
  FOR(j,2) {
  FOR(i,16) {

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 selected2 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:

Wrong result obtained from bugged scalarmult_base(n) in pack25519():

Expected result obtained from ref implementation:

This error should be relatively frequent, it happens around or a bit less than one time for every 216 computations for computations with different scalar values or different points. However, beyond the wrongness of the resulting x-coordinate3, 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.

  1. Bug reported on 02-13-2014 to its authors. 

  2. This example was generated with this code

  3. This bug is not limited to DH computations it should also affect the signature operations of EdDSA. 

Authenticated Encryption in 2014

22 March 2014

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 ignore1 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/TLS2. 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 270 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 238 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.

  1. I also choose not to consider schemes such as AES-CCM and AES-GCM as they'd also introduce other problems and considerations. 

  2. OpenSSH already implements a variant and it should also be available in the near future as a new EVP_AEAD cipher in OpenSSL. 

The Verification Problem Introduced by Highly Specialized Cryptographic Implementations

11 January 2014

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.

Ed25519 for Authentication in OpenSSH

26 December 2013

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.

OpenSSL stripped-out from OpenSSH on OS X

18 December 2013

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.

SPAKE2 implementation in Chrome

05 December 2013



Salsa vs ChaCha in TLS

30 November 2013

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.

Twitter's TLS Forward Secrecy Implementation

23 November 2013

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.

ECC 2013 summer school on Elliptic and Hyperelliptic Curve Cryptography

23 November 2013

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.


22 November 2013

Initial post.