Crypto Design Decisions

Getting Help
1

After reading https://restic.readthedocs.io/en/stable/references.html#keys-encryption-and-mac, I have some questions on the design:

The data is then encrypted with AES-256 and afterwards a message authentication code (MAC) is computed over the ciphertext, everything is then stored as IV || CIPHERTEXT || MAC.

Do I understand correctly that the IV is not (directly) part of the MAC, i.e. not passed to the MAC algorithm as part of the message?

This is used both as the IV for counter mode and the nonce for Poly1305.

But instead the IV is somehow implicitly authenticated that way?

Can someone please elaborate a bit on that design? Why was it taken instead of a more conservative approach where IV and ciphertext are both part of the message input to the MAC algorithm? Does that correspond to some best-practice for using Poly1305? Also, it’s non-obvious to me, that using the same value as both AES-CTR-IV and Poly1305-nonce is a good idea.

2

Hey, thanks for asking. You are right: The IV is used both for the Poly1305-AES MAC and the AES-CTR encryption. I think the way we use the 16 bytes of random twice is safe here, but I agree with you that it would be more conservative to have a nonce for the MAC which is separate from the IV for the encryption. I’ve also learned a lot since implementing the first repo layout :slight_smile:

So, in order to answer your questions let me first point out that two different, independent keys are used for the MAC and the encryption.

Do I understand correctly that the IV is not (directly) part of the MAC, i.e. not passed to the MAC algorithm as part of the message?

The IV is part of the MAC: If the IV is modified in any way, the MAC check will fail.

In Poly1305-AES, the nounce is encrypted with AES and the MAC key to get a mask value, which is then combined with the result of the computation on the message. The details can be found in the Poly1305 paper here: https://cr.yp.to/mac/poly1305-20050329.pdf

If the IV value is changed by just a single bit, the 16 bytes mask value will be entirely different (the result of an AES encryption with the MAC key), so the resulting computed MAC will be different and the MAC check will fail.

But instead the IV is somehow implicitly authenticated that way?

The IV is explicitly authenticated, it is part of the MAC.

Also, it’s non-obvious to me, that using the same value as both AES-CTR-IV and Poly1305-nonce is a good idea.

I think in this case it is safe. Let’s look at what the IV is used for:

  • For checking the MAC, it is is encrypted with AES using the MAC key and then added to the result of the computation on the message.
  • For encryption in counter mode it is used in combination with the block number, then encrypted with AES using the encryption key.

So in both cases the IV is encrypted with AES with different keys, so the result will be entirely different.

I hope that this answers your questions. If we were to reimplement the repository encryption format (which we’ll do eventually) we’ll probably switch to something like AES-GCM.

3

FYI, Filippo Valsorda recently had a look at the restic crypto: https://blog.filippo.io/restic-cryptography/