Public key encryption and big files with NaCL

Question

I am trying to encrypt big files using NaCL (actually PyNaCL) - see http://nacl.cr.yp.to/box.html

After reading some docs, I came up with this prototype :

Bob wants to send a big file to Sarah. They both have a public/private key pair.

• set "position" to 0
• for each 256ko file chunk
  • generate a random nonce
  • append to the chunk 10 bytes containing position zfilled with zeroes
  • encrypt the chunk using crypto_box (using Bob private key and Sarah public key)
  • increment position

When Sarah gets the encrypted chunks:

• set "position" to 0
• for each encrypted chunk
  • decrypt the chunk using crypto_box (using Bob pub key and Sarah priv key)
  • extract the position and assert it's equal to "position"
  • increment position

prototype code here : https://github.com/tarekziade/fxakeys/blob/master/fxakeys/crypto.py#L119

What do you think ?

Answer 1

You're vulnerable to a chunk-level replay attack, where Mallory (the man-in-the-middle) can mix and match chunks from different files, to produce a file that appears to be from Bob but which Bob never wrote.

1. Bob sends two messages to Sarah. Let's say the first message comes in chunks A1 and A2, and the second message comes in chunks B1 and B2.
2. Mallory intercepts both messages. She then constructs the new message A1+B2.
3. Mallory sends the forged message to Sarah. The boxes open with Bob's key, and the sequence numbers look good.

Since Mallory can forge a message, this scheme fails to provide authenticity.

You could fix this problem in a couple ways. One way would be to put another token inside each chunk, next to the position bytes, that's shared by all the chunks and unique for each message. Then in addition to verifying the position, the receiver would have to check that this identifier matched the previous chunks.

Another approach would be to use NaCl's nonce to do this for you. (Since after all, a "unique token for each message" is sort of what a nonce is.) If you use 16 random bytes (shared by all the chunks) plus an 8-byte counter as your nonce, you can avoid nonce reuse and also prevent the chunk-swapping replay attack. This saves you some space because you only have to transmit the 16 random bytes once, and it's also safer: a forged plaintext will never be decrypted at all, so it's impossible for an implementation to somehow forget to check the tokens. This sort of use case is why NaCl was designed with a large nonce.

Edit: Adam Langley has a post on this: https://www.imperialviolet.org/2015/05/16/aeads.html