NaCl, NaCl, Padding Whack — or — Give The Dev A Cryptographically-Signed Box

I've been playing with NaCl — specifically the TweetNaCl implementation — in an effort to implement reliable end-to-end encryption in a project of mine, via CurveCP.

NaCl brings powerful and safe security primitives to the table, in the form of a cryptographic box. We are accustomed to dealing with cryptography at a ludicrously low level (a hash function here, a MAC algorithm there). crypto_box, the heart and soul of NaCl, wraps up best practices, namely:

  1. Generating a random AES key
  2. Encrypting a packet with said key
  3. Hashing the encrypted packet
  4. Signing said hash with Alice's RSA secret key
  5. Encrypting the AES key + hash + signature with Bob's RSA public key

From one of the research papers on NaCl:

NaCl provides a high-level function crypto_box that does everything in one step, converting a packet into a boxed packet that is protected against espionage and sabotage. Programmers can use lower-level functions but are encouraged to use crypto_box

Usage seems straightforward.

First, we have to generate an RSA public / private keypair:

uint8_t public[32];
uint8_t secret[32];

int rc = crypto_box_keypair(public, secret);
assert(rc == 0);

The secret key will be randomly generated, and then a Curve25519 public key counterpart will be derived.

Easy.

Next up, we use crypto_box() itself to encrypt our plaintext into a ciphertext buffer. The call signature seems pretty straightforward at first glance:

int
crypto_box(uint8_t *ciphertext,
           uint8_t *plaintext,  size_t plaintext_len,
           uint8_t nonce[24],
           uint8_t public[32],
           uint8_t secret[32]);

The first argument is a buffer to house the encrypted ciphertext.

The second argument is the buffer to read the plaintext from. It should be plaintext_len octets long.

The fourth argument is a nonce (number used once), which exists to perturb the ciphertext and allow use of the same keypair without leaking key material. So long as it is unique (a counter will do), we should be good.

The fifth and sixth arguments are the recipient public key and the sender private key, respectively. Since crypto_boxes are part of a communication system, they are intended to be assembled and sender and only readable by the correct recipient.

So, let's give this a shot.

#define MESSAGE "There are strange things done in the midnight sun\n" \
                    "By the men who toil for gold;\n"                 \
                "The Arctic trails have their secret tales\n"         \
                    "That would make your blood run cold;\n"          \
                "The Northern Lights have seen queer sights,\n"       \
                    "But the queerest they ever did see\n"            \
                "Was that night on the marge of Lake Lebarge\n"       \
                    "I cremated Sam McGee.\n"
                                              /* - Robert W. Service */

#define MESSAGE_LEN 304 /* I counted */

int rc;
uint8_t client_pub[32], client_sec[32];
uint8_t server_pub[32], server_sec[32];
uint8_t cipher[256], plain[256];
uint8_t nonce[24];

/* "generate" nonce */
memset(nonce, 0, 24);

/* generate keys */
rc = crypto_box_keypair(client_pub, client_sec); assert(rc == 0);
rc = crypto_box_keypair(server_pub, server_sec); assert(rc == 0);

memcpy(plain, MESSAGE, MESSAGE_LEN);
dump("plaintext, before encryption", plain, MESSAGE_LEN);

/* encipher message from client to server */
rc = crypto_box(cipher, plain, MESSAGE_LEN,
                nonce, server_pub, client_sec);
dump("ciphertext", cipher, MESSAGE_LEN);
assert(rc == 0);

And here's the output (full, compilable code is over here on github, as encrypt.c):

plaintext, before encryption
------------------------------------------------
 54 68 65 72 65 20 61 72 65 20 73 74 72 61 6e 67
 65 20 74 68 69 6e 67 73 20 64 6f 6e 65 20 69 6e
 20 74 68 65 20 6d 69 64 6e 69 67 68 74 20 73 75
 6e 0a 42 79 20 74 68 65 20 6d 65 6e 20 77 68 6f
 20 74 6f 69 6c 20 66 6f 72 20 67 6f 6c 64 3b 0a
 54 68 65 20 41 72 63 74 69 63 20 74 72 61 69 6c
 73 20 68 61 76 65 20 74 68 65 69 72 20 73 65 63
 72 65 74 20 74 61 6c 65 73 0a 54 68 61 74 20 77
 6f 75 6c 64 20 6d 61 6b 65 20 79 6f 75 72 20 62
 6c 6f 6f 64 20 72 75 6e 20 63 6f 6c 64 3b 0a 54
 68 65 20 4e 6f 72 74 68 65 72 6e 20 4c 69 67 68
 74 73 20 68 61 76 65 20 73 65 65 6e 20 71 75 65
 65 72 20 73 69 67 68 74 73 2c 0a 42 75 74 20 74
 68 65 20 71 75 65 65 72 65 73 74 20 74 68 65 79
 20 65 76 65 72 20 64 69 64 20 73 65 65 0a 57 61
 73 20 74 68 61 74 20 6e 69 67 68 74 20 6f 6e 20
 74 68 65 20 6d 61 72 67 65 20 6f 66 20 4c 61 6b
 65 20 4c 65 62 61 72 67 65 0a 49 20 63 72 65 6d
 61 74 65 64 20 53 61 6d 20 4d 63 47 65 65 2e 0a
------------------------------------------------
ciphertext
------------------------------------------------
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 20 08 4b 11 63 5c 5c 39 6c 6d a0 d0 0c 4c 11 e4
 36 db 04 89 e9 8d e5 44 e0 3f 51 65 30 1b 90 a5
 5c 8b 04 27 00 d3 f2 13 b2 4d 64 96 3e 6f a3 d9
 ba 7b 1e aa e9 1f ac ef b8 17 63 4b 40 95 77 d7
 39 fa 8b 5a 36 f3 18 d8 cc 12 54 af 45 e0 6a 78
 48 3f bb 0e c3 85 12 3b 66 d0 18 1c ff 1d a5 29
 2e c8 8f e7 67 08 f8 94 16 bb 1c b8 1d 14 b3 9b
 64 2b 4e ec 53 5a 23 22 bf b1 3c 40 f0 5d dc 97
 66 26 a5 ad 9d 2f 2c d6 8a 4f c1 57 a1 5a 0c 6f
 c1 e1 69 cd 76 f3 00 ee 40 5e d7 eb 38 05 f2 e4
 e7 68 72 1b af f6 ae 2d 1e 5d b4 53 dd 10 37 6a
 eb c7 dc bc c7 3e b2 55 33 ad fa 03 9b bc 90 66
 ed f6 4c 0c a5 c5 a7 d3 05 a1 10 c9 af 53 86 6c
 d3 30 3d d5 b4 4a 25 45 16 6f ab 9e ec cb 89 39
 b8 57 65 6b e8 87 cd 05 21 96 32 30 53 92 97 6d
 e7 32 9e 02 f4 fd dc 5e f5 14 90 d3 84 d0 98 01
 c4 7c c5 a4 64 46 74 37 ea 85 0e 65 85 8a e3 f8
 2c 1c 77 ce 69 04 cd 80 ab 60 cf e8 e3 c7 35 d6
------------------------------------------------

We have ciphertext! That first row of all zeros seems odd...

Like backups without a restore operation, encrypting data is only half of the story. We have to be able to open that cryptographic box as the receiver, or we won't really have much of a communication system...

Here are the salient bits of decrypt.c:

/* erase all trace of plaintext */
memset(plain, 0, 512);

/* decipher message as server, using client's public key */
rc = crypto_box_open(plain, cipher, MESSAGE_LEN,
                     nonce, client_pub, server_sec);
dump("plaintext, after decryption", plain, MESSAGE_LEN);
assert(rc == 0);

And here's what happens when we run it:

plaintext, after decryption
------------------------------------------------
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
------------------------------------------------
Assertion failed: (rc == 0), function main, file decrypt.c, line 88.
Abort trap: 6

You didn't really think it would be that easy, did you?

As it turns out, there is a padding requirement briefly mentioned in the docs:

WARNING: Messages in the C NaCl API are 0-padded versions of messages in the C++ NaCl API. Specifically: The caller must ensure, before calling the C NaCl crypto_box function, that the first crypto_box_ZEROBYTES bytes of the message m are all 0. Typical higher-level applications will work with the remaining bytes of the message; note, however, that mlen counts all of the bytes, including the bytes required to be 0.

crytpto_box_ZEROBYTES turns out to be 32.

If we adjust the call to crypto_box, we should get past the failing assertion and get some (hopefully correct) deciphered plaintext!

Here's our second attempt, decrypt2.c:

memset(plain, 0, 32);                    /* first 32 octest are ZERO */
memcpy(plain+32, MESSAGE, MESSAGE_LEN);  /* then comes the real data */
dump("plaintext, before encryption", plain, MESSAGE_LEN+32);

/* encipher message from client to server */
rc = crypto_box(cipher, plain, MESSAGE_LEN+32,
                nonce, server_pub, client_sec);
dump("ciphertext", cipher, MESSAGE_LEN);
assert(rc == 0);

/* erase all trace of plaintext */
memset(plain, 0, 512);

/* decipher message as server, using client's public key */
rc = crypto_box_open(plain, cipher, MESSAGE_LEN+32,
                     nonce, client_pub, server_sec);
assert(rc == 0);
dump("plaintext, after decryption", plain, MESSAGE_LEN+32);
assert(memcmp(MESSAGE, plain, MESSAGE_LEN) == 0);

plain[MESSAGE_LEN+1] = '\0';
printf("%s\n", plain);

And here's the output (I'm going to start snipping the output, for brevity's sake):

plaintext, before encryption
------------------------------------------------
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 54 68 65 72 65 20 61 72 65 20 73 74 72 61 6e 67
 65 20 74 68 69 6e 67 73 20 64 6f 6e 65 20 69 6e
 ..................  snip  .....................
 65 20 4c 65 62 61 72 67 65 0a 49 20 63 72 65 6d
 61 74 65 64 20 53 61 6d 20 4d 63 47 65 65 2e 0a
------------------------------------------------

ciphertext
------------------------------------------------
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 cc ec 2a d9 12 73 24 ed 9f 98 40 37 e4 f7 1e 84
 42 c7 09 9e ac c0 ed 52 eb 76 45 79 36 5a 8d b7
 ..................  snip  .....................
 d2 7c fd a9 67 53 26 3e e6 e8 2f 31 c6 97 e8 b5
 39 00 77 8a 24 36 de 8a ee 0d c3 c9 a6 ee 7a b7
------------------------------------------------

plaintext, after decryption
------------------------------------------------
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 54 68 65 72 65 20 61 72 65 20 73 74 72 61 6e 67
 65 20 74 68 69 6e 67 73 20 64 6f 6e 65 20 69 6e
 ..................  snip  .....................
 65 20 4c 65 62 61 72 67 65 0a 49 20 63 72 65 6d
 61 74 65 64 20 53 61 6d 20 4d 63 47 65 65 2e 0a
------------------------------------------------

Assertion failed: (memcmp(MESSAGE, plain, MESSAGE_LEN) == 0), function main,
file decrypt2.c, line 49.
Abort trap: 6

If you look closely, you'll see that the plaintext lines up, but the plain buffer doesn't actually match our input message (per the memcmp assertion failure). That's because that 32 bytes of padding is still there!

Let's remove that. Here's our third (and hopefully final) attempt, decrypt3.c:

/* decipher message as server, using client's public key */
rc = crypto_box_open(plain, cipher, MESSAGE_LEN+32,
                     nonce, client_pub, server_sec);
assert(rc == 0);
memmove(plain, plain+32, MESSAGE_LEN);
dump("plaintext, after decryption", plain, MESSAGE_LEN);
assert(memcmp(MESSAGE, plain, MESSAGE_LEN) == 0);

plain[MESSAGE_LEN] = '\0';
printf("\n%s\n", plain);

The memmove call overwrites the 32 zeros from crypto_box_open(). Let's see where that leaves us:

plaintext, before encryption
------------------------------------------------
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 54 68 65 72 65 20 61 72 65 20 73 74 72 61 6e 67
 65 20 74 68 69 6e 67 73 20 64 6f 6e 65 20 69 6e
 ..................  snip  .....................
 65 20 4c 65 62 61 72 67 65 0a 49 20 63 72 65 6d
 61 74 65 64 20 53 61 6d 20 4d 63 47 65 65 2e 0a
------------------------------------------------
ciphertext
------------------------------------------------
 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 cc ec 2a d9 12 73 24 ed 9f 98 40 37 e4 f7 1e 84
 42 c7 09 9e ac c0 ed 52 eb 76 45 79 36 5a 8d b7
 ..................  snip  .....................
 9d 29 4f 25 1e 6a 0a 99 83 7c e2 2e 94 24 7d b5
 3d f7 4f 96 77 3d d9 3c 65 2a 95 52 2a 07 8d 1c
------------------------------------------------
plaintext, after decryption
------------------------------------------------
 54 68 65 72 65 20 61 72 65 20 73 74 72 61 6e 67
 65 20 74 68 69 6e 67 73 20 64 6f 6e 65 20 69 6e
 ..................  snip  .....................
 65 20 4c 65 62 61 72 67 65 0a 49 20 63 72 65 6d
 61 74 65 64 20 53 61 6d 20 4d 63 47 65 65 2e 0a
------------------------------------------------

There are strange things done in the midnight sun
By the men who toil for gold;
The Arctic trails have their secret tales
That would make your blood run cold;
The Northern Lights have seen queer sights,
But the queerest they ever did see
Was that night on the marge of Lake Lebarge
I cremated Sam McGee.

Success!

Conclusions

There is a 32-octet padding requirement on the plaintext buffer that you pass to crypto_box. Internally, the NaCl implementation uses this space to avoid having to allocate memory or use static memory that might involve a cache hit (see Bernstein's paper on cache timing side-channel attacks for the juicy details).

Similarly, the crypto_box_open call requires 16 octets of zero padding before the start of the actual ciphertext. This is used in a similar fashion. These padding octets are not part of either the plaintext or the ciphertext, so if you are sending ciphertext across the network, don't forget to remove them!

Not that such a thing would keep someone up until 2:14am...

Happy Hacking!

James (@iamjameshunt) works on the Internet, spends his weekends developing new and interesting bits of software and his nights trying to make sense of research papers.

Currently working on Bolo.