Support for encrypting files (XSP?) ?

[e1ven]

There are several cases where it would be helpful for me to encrypt large files, and having to read the whole file into memory.

I had considered chunking the file, but I'd rather do so in a way which is compatible with other implementations. It looks like https://github.com/3nsoft/ecma-nacl#xsp-file-format has one implementation today.

Is this something that would be suitable for including into the main libsodium library? Is there a better/recommended way of handling large files?

[jedisct1]

Hi e1ven,

On 64 bit platforms, one way to do it is to use memory-mapped files (mmap()). The required padding at the beginning of the file is a bit annoying, and might require a memove() that will write the content twice. On 32 bit platforms, the file size will be limited to 2 Gb. This is not ideal, but it should definitely work.

I just glanced at the README file about the XSP format, and I might have overlooked something (maybe in the implementation itself), but since segments are independent and have their own authentication tag, how does it prevent an attacker from removing, adding, duplicating and reordering segments?

[tarcieri]

I just glanced at the README file about the XSP format, and I might have overlooked something (maybe in the implementation itself), but since segments are independent and have their own authentication tag, how does it prevent an attacker from removing, adding, duplicating and reordering segments?

The easiest way would be to encrypt them all under the same key and use a counter for the nonce

[jedisct1]

Absolutely. I don't get why they use a random nonce for each segment.

[3nsoft]

Have a look at referenced issue https://github.com/3nsoft/ecma-nacl/issues/1 I posted a story there. I shall be glad to hear your input about XSP format.

[tarcieri]

@3nsoft I think it would make a lot more sense if you made part of the nonce a block sequence number and part of it random.

If you used the first 64-bits of the nonce as a block sequence number, and had, say, 1MB per block, you could support files up to 16 yottabytes.

The remaining 128-bits could be a random value.

This would prevent reordering of blocks and file truncation (if you added an empty block on the end as a sentinel) while still eliminating worries about nonce reuse.

[3nsoft]

@tarcieri With partially (128bits) random nonce we already have to put nonce into every segment, producing a major, but necessary pain (trade-off).

At the same time, sequence number in every nonce will not allow removal and addition of segments without re-encryption of the rest of the file, as all following sequence numbers in nonces will have to change.

Ability to remove and add segments arbitrarily without re-encrypting big parts of the file is the sacred cow here.

Or can we find some hybrid way here?

[tarcieri]

@3nsoft you need to do it in such a way that an attacker can't reorder the file, truncate the file, or replay old blocks. It's a pretty tall order.

What I was describing doesn't cover it either. I'm not sure anything does short of a manifest of the entire file (e.g. ciphertext hash or possibly MAC if you're sure an attacker can't generate MAC collisions)

It's beginning to look a lot like this ;)

[3nsoft]

@tarcieri Precisely, in order to detect segments reshuffling by an attacker, one needs global cryptographic assurance. And this global assurance will not allow you to start reading/changing file in the middle without some hard work, which we try to avoid.

May be this is one of those trade-offs. Either, we have flexibility, with inability to notice segments reshuffling on the file level. Or we have to re-encrypt (transport on the wire) bigger file chunks.

We may (1) talk about significance of segments reshuffling, figuring if this DoS-like activity is a threat in some scenarios. We may (2) also suggest having two protocols, one more flexible, another one less so, each having appropriate api. And we may (3) zoom out from file level into fs level, and suggest journal-ed solution to xsp, as it stands.

Option (2).

How about having 'rxsp', Rigit XSP format. It starts with these letters. All segments have the same length, indicated in a file header. First segment's nonce is 100% random. All other segments have 64-bits of the first segment's nonce, added with segments' index, other bytes shall be random. And, non-first segments may have nonce part shorter by these predictable 8 bytes. This is @tarcieri suggestion.

Different file starting string will allow the same lib read two different file types. But, we need to make such api for rxsp, that writing a segment shall require new random nonce portion for changed segment(s). And, when the file tail needs to be shifted (file length changes), all other segments get re-encrypted with new nonces. API for rxsp should not allow user (developer that uses lib) to automatically reuse nonces. Following NaCl's wisdom, "we cannot blame the user" (actively stupid user cannot be helped in principle).

Notice, though, that when I send to service provider new version of my file, they may still feed me back with an old version. And on the level of file, I will not be able to detect that it is a wrong version that is given to me. Replay of an old file version is still possible. But it is DoS, which might be a simple server glitch (think of option 1).

Option (3).

Have a separate journal object, that describes miss-fitting xsp segments. Reading this journal will allow faster skips. It may have segment nonces, for example, or miss-fitting nonces, while initially, at file creation, all nonces should be related by simple counting, and segments be at creation of the same, maximum, size (excluding the last one, of cause).

Journal may have simple, non-segmented layout. When journal gets wild, due to large number of changes, file can be completely re-encrypted.

Again, there is no protection against old version of file and journal being fed by cloud provider.

Option (1).

Looking at referenced that ;) I really want something simplier. I really do not want to drop Poly, and repack primitives. This is DJB and Co. job.

When making order too tall to execute it, we should look at sacred cows here.

I'd argue that change of words on the page, against which Poly protects as part of NaCl secret-box, is way more important then misplacement of whole pages KBs or MBs. When big chunk is misplaced, neither pdf, no odt (zip container) shall open the thing without throwing up something very explicit. When file is a stored video/audio stream, chances are that your eyes will notice difference, even if codec is supposed to make sense of anything it gets.

When segment reshuffling should be prevented, when this is a sacred cow, rxsp can be used.

What do you think?

[tarcieri]

@3nsoft if I were designing this thing, my threat model would definitely include attackers that want to:

• Replay old chunks of the file
• Reshuffle the file
• Truncate the file or increase its length with other chunks

[e1ven]

This is getting off-topic for libsodium, but the functionality would be useful to have standardized and widely available as part of the lib.

@3nsoft, Help me understand why adding a signed manifest segment at the end, which includes all the nonces, wouldn't work for you? If you wanted to swap out a block for a mid-file change, you could still do so - You'd just update that particular segment, as well as the manifest segment at the end.

Attackers would not be able to re-order segments, because the manifest file specifies the exact order. They could not insert old segments without entirely reverting the file.

[tarcieri]

+1 on a manifest. It seems straightforward and secure

@e1ven good call on a list of the nonces. Much better than what I was suggesting ;)

[3nsoft]

@e1ven @tarcieri Let's suggest a particular protocol change to implement, so that we may analyse it.

Manifest with many nonces. Let's be specific. For video, and streaming, segments better be in 10K range (a guess, based on rough download speeds and decryption speed in js + ARM caches are still in KBs), for watching a thing instantaneously as it downloads. Say 100MB/10KB == 10000 segments, which is, as an upper range, roughly 24bytes*10000segs == 240K size manifest. Notice that videos can be bigger than mere 100MB.

I have, therefore, three questions for implementation here: (1) Can we arrange this manifest (or journal in my post) so that it shall be smaller? With the journal, as suggested previously, protocol should have an expectation of what nonces and segment size should be for freshly created file. Journal shall contain only deviations from the expected norm, caused by legitimate file changes. In fact, when journal is missing, reader should expect a fresh-file pattern. (2) If this manifest, or journal, is placed at the end of the file, then, where is it? I mean, how do I find where this manifest starts, without reading the whole file? In file service scenario, I expect on a client side to ask provider to give me, separately, file header and a journal, before I ask for any data bytes. (3) Really, there is no problem in placing journal as another file near our encrypted object. File names of the two can be related, and content be encrypted to the same file key. Do we gain anything, if we attach this manifest to the file?

@e1ven I do no think that we are off-topic here. Whoever started libsodium, I believe, they were captured by NaCl's do not blame user approach. Djb &Co. assembled for us strong combination of primitives. We should, in the same spirit, assemble file format and API for it, which will be very difficult to misuse (EncFS + spy_cloud || truecrypt + spy_cloud || ...)

[tarcieri]

@3nsoft a threat model is probably a good place to start. I think anything that doesn't ensure total file integrity even in the face of block swapping/truncation/extension is a backstep from the principles of NaCl.

[3nsoft]

So far, it seems to me, that having two things, (a) mandate for initial writing of the file, and (b) a flexible journal to assure about changed segments, and to provide faster seeking over the file, -- these two things strike a balance between having efficiency in changing and reading files, and a need to protect against segment shuffle.

[e1ven]

If you want to be able to read the manifest quickly, why not just put it as the first segment? Then you can read in a simple list of nonces to expect in this file. Each other segment contains a signed chunk of the file, with the nonce mentioned at the top.

Don't keep a changelog/history in the file itself- That's a higher-level function, more specific to an app like Dropbox or git than to the file. It could betray information the user doesn't expect.

[e1ven]

Streaming file encryption on libsodium is also being done by - https://github.com/TLINDEN/pcp

[TLINDEN]

Just a side note, which should be considered: usually (at least in the unix world) users expect to use pipes. In case of decrypting a file this means, the encrypted input could come from STDIN (both pcp and pbp support this, as well as STDOUT for outputs). But you cannot do seek() on STDIN, therefore any format spec should have this in mind.

• Tom

[3nsoft]

@e1ven Proposed journal will not keep history of the file, but only description about current state. Sorry for use of word journal, which may imply history. By choosing such word, I wanted to highlight a possibility that this object can be stored in a separate file. Essentially, it does not matter where it is stored. It can be even at the front of the file/stream. And, this part may keep all info about nonces, making storing of nonces in segments redundant.

Let's suggest the following. Let's call this thing/journal a file header, always remembering that it can either be placed infront of all segments (file body), or be placed into separate ?.xsph header file, when body is placed into ?.xspb file.

Body part shall contain ordered segments, each in poly+cipher standard NaCl format (no nonce). Header part shall have, in order: 1) magic bytes 'xsp', 2) packed with-nonce file key -- fixed number of bytes, 3) have 4 bytes for total header length, which, functionally, is an offset from file start to reach the body, when it sits in the same file with the header, 4) packed with-nonce header.

Header internals shall be of two sorts: a) rigid (first byte is ASCII 'r'), containing segment size (4 bytes) and one nonce (24 bytes), which is used for encryption of the first segment, with all other nonces being calculated by advancing the initial one, by segment index. Layout is simple, and is 29 bytes of data length. b) flexible (first byte is ASCII 'f'), containing some information, which will allow to immediately find needed segment (without reading xsp body), and have, or allow to calculate appropriate nonce. Layout, except for the first byte, is to be crafted.

All files, when created initially, for encryption of either some known-size data, or, unknown-length stream, should be packed with 'r' header. Such rigid header can be created before the first segment, and can be streamed/piped right away.

When file is updated, its header shall become 'f' type (flexible). When many-many-many updates happen, header may grow. At certain point, some app may decide to simplify header, re-encrypting the whole file with a new nonce, and making 'r' type header. Notice that 'f' type file can be streamed header infront.

On one hand, rigid header with implied order of nonces protects against segment shuffle of a fresh file, while flexible header protects against segment shuffle of an updated/deformed file. On another hand, there is a way to update file's middle without touching file's tail, and without sending updated file's tail in the networked scenario. Both 'r' & 'f' files can be streamed header infront, and opened/played on the fly. And since most of files will never be updated, their 'r' type has simplest and shortest layout, i.e. majority is not penalized by needs of minority.

What do you think? Seems like we have both security and efficiency requirements met. What should flexible header be in detail, and how should it be laid out?

[tarcieri]

@agl blogged about this recently:

https://www.imperialviolet.org/2014/06/27/streamingencryption.html

He mentioned AERO:

https://tools.ietf.org/html/draft-mcgrew-aero-01

[3nsoft]

I want to notice a little assumption in Langley's piece. Quote: """ I don't think it need be very complex: take 64 bits of the nonce from the underlying AEAD as the chunk number, always start with chunk number zero and .... """ and a little further, ending the paragraph: """ The major worry might be that for many underlying AEADs, taking 64 bits of the nonce for the chunk counter leaves one with very little (or none!) left. """

64 bits == 8 bytes, which is AES's IV (assumed by Langley?). As I recall, nacl.cr.yp.to specifically warns about short nonce, suggesting use of something with 24 bytes nonces. So, when we use XSalsa+Poly box, then Langley's worry will not arise, as there is enough room in 24 bytes, allowing for a simple solution, as he describes it.

[dchest]

@3nsoft even better: NaCl's XSalsa20 takes 24-byte nonce and splits it into 16- and 8-byte parts: the first part is mixed with a key using HSalsa to form a subkey, the next part is directly used as a nonce to Salsa20:

unsigned char subkey[32];
crypto_core_hsalsa20(subkey,n,k,sigma);
return crypto_stream_salsa20_xor(c,m,mlen,n + 16,subkey);

If we construct the full nonce for crypto_secretbox as I proposed here, we get a performance benefit, since we can derive subkey only once and then use it for all chunks of the stream, while using the last 8 bytes as an incrementing chunk number.

[3nsoft]

@dchest thank you for pointing out that a particular choice of nonce in a sequence of segments may keep subkey the same. I'll argue, with a cost-performance analysis, that we should exploit this fact from another side.

If we do nonce such that subkey is the same for all chunks, then we save 1 (one) round of salsa20, on 16 bytes (or this order). At the same time, the following stream_salsa20 will do salsa20 on every 16 bytes in 4K segment. So, the saving gives us at best 10,000-th, or 0.01% improvement in running xsalsa.

To add insult to the injury, in a box, which is xsalsa + poly, poly part, that is code from scalarmult file, takes half the time (this is my observation in profiling ecma-nacl implementation). So, the saving will be only 0.005%.

On the other hand, have you calculated how much less search space becomes with the same subkey, when you have to do crypto-analytic attack against cipher, especially on a bigger file (more segments)?

We may say that performance gain is negligibly small. At the same time, there is, may be, some negligible reduction in security. Should we take such trade-off, if we want to be prudent? Nay.

It is great that you point out the fact that certain changes to nonce keep subkey the same. I missed it. Armed with this insight, I'll say, that we MUST have such nonces' changes that make subkey different for every segment.

In ecma-nacl, nonce advancing mechanism takes 24 bytes of nonce as three 8-byte unsigned ints, and adds one or two to each of these ints individually (modulo, obviously). This will make subkey different for every following segment. Such nonce advance seemed to me to distribute new nonces better. Now, as it turns out, it ensures that subkey is different for every segment, increasing difficulty of a crypto-analysis attack. (Yes!!)

Side comment 1. I, generally, do not see why we need to use certain bytes only for counting. This assumes that these bytes start with 000, and go 0001, etc. So, out of all given nonces, the ones with these bytes shall be used more often, effectively reducing nonce. Why not have x+n, where x is initial random nonce (or part of it). Yes, we'll have to do addition for every segment. It is a single tiny operation, yet it gives a better distribution of nonces.

Side comment 2. NaCl's spirit is that I, developer, should use a box, without dwelling about internal salsa/hsalsa/stream, etc. I'd step away from using/exposing internal bits of NaCl. I am for using NaCl's high level of abstraction, i.e. for using box as it is.

Side comment 3. Like almost any other non-trivial abstraction, even NaCl's abstraction leaks in that some choices of nonce may drastically change/not change a resulting crypto-stream. Wow. Another great lesson.

[dchest]

No-no-no-no, I didn't make this change with the goal of improving performance in favor of losing some security. There's no need to make subkeys different for each chunk:

This paper proves that XSalsa20 is secure if Salsa20 is secure: any fast attack on XSalsa20 using q queries and succeeding with probability p can be converted into a fast attack on Salsa20 succeeding with probability at least p/(q + 1).

http://cr.yp.to/snuffle/xsalsa-20110204.pdf

Nonce is there to make Salsa produce different keystreams, not to add security. If you can argue that this construction of the 24-byte XSalsa nonce:

8-byte something || 16-byte something else                   (1)

is more secure (for the security level promised by XSalsa20) than

16-byte something else || 8-byte something                 (2)

than you can as well argue that this thing doesn't fit the definition of nonce.

As for other points:

1) It seems like you are confusing a nonce with an IV for some modes such as CBC. A nonce doesn't need to be random or unpredictable -- it should be only different for the same key. In fact, in communication protocols, using simple counters 0..1..2..3... as a nonce is more common than using random bytes.

2) With my proposal you don't need to use internals (you can use them for some performance gain, but are not required to). There's no difference in implementation between (1) and (2): combine 16-byte nonce with a 8-byte counter to form 24-byte full nonce and use box.

3) I don't understand this point. Are you arguing that changing nonce will change crypto stream? Yes, it's exactly the purpose of nonce.

Your comment also implies that XSalsa20 is more secure than Salsa20. It is not.

[3nsoft]

I have a 'paranoid security' stance here. I'll take different (subkey+nonce) instead of just different (nonce) for every segment, especially, when it costs nothing to do so.

Now, looking at the paper. Imagine that I do deliberate nonce choices so, that subkey is kept the same for all segments. Then I encrypt 4GB file with it (lo-o-ots of 4K segments). Can I say, like paper does, that there is 192-bits nonce, i.e. this subkey is OK to be used that ma-a-any times? Personally, I'll blink. It really becomes 128-bits nonce, for the same subkey, for many-many jobs. In a back of my mind one commandment shows up: change thy crypto keys often! So, in 4GB file situation, a free change of a subkey is a blessing, and I'll take it.

The 3-rd comment is about http://www.joelonsoftware.com/articles/LeakyAbstractions.html

[dchest]

I have a 'paranoid security' stance here.

Does this mean that you're gonna make irrational choices disregarding any reasoning and logic? In which case, will "thou shall put chunk counter into the last part of nonce because God said so" convince you? ;-)

Now, looking at the paper. Imagine that I do deliberate nonce choices so, that subkey is kept the same for all segments. Then I encrypt 4GB file with it (lo-o-ots of 4K segments). Can I say, like paper does, that there is 192-bits nonce, i.e. this subkey is OK to be used that ma-a-any times? Personally, I'll blink. It really becomes 128-bits nonce, for the same subkey, for many-many jobs.

Yes, this "subkey" is OK to be used 2^64 times. Why would you blink? Do you blink every time Salsa20 core produces the next block? :laughing:

I don't understand your nonce-bits calculation. In my proposal you have a function that accepts 16-byte nonce, 32-byte key, and encrypts a file chunk-by-chunk using secretbox with full 24-byte nonce produced by concatenating 16-byte nonce and 8-byte chunk counter. Changing any bit of nonce will produce different ciphertext.

Again, it doesn't matter how many bits of nonce you have. All you need is to produce different keystreams for each segment of your file.

So, in 4GB file situation, a free change of a subkey is a blessing, and I'll take it.

Why would you prefer changing the subkey instead of changing Salsa20 nonce? What's the reason for this? Did you know that in Salsa20 core, key and nonce are inputs to permutation? Change a single bit in any, and it will produce different block.

The 3-rd comment is about http://www.joelonsoftware.com/articles/LeakyAbstractions.html

And where in NaCl is leaky abstraction?

[tarcieri]

I'll take different (subkey+nonce) instead of just different (nonce) for every segment, especially, when it costs nothing to do so.

The cost comes in the complexity of your protocol, for no real gain. If you're deriving a truly unique and random key per block, then you don't need a nonce at all as you're never reusing keys, so you can just use zeroes in that case.

If you're deriving a unique nonce, then you can reuse the same key over and over so long as you never reuse a nonce.

There's little gained in choosing a unique key and a unique nonce. That defeats the purpose of a nonce.

[ekodo]

@jedisct1 are there any plans, libsodium will offer something like this https://github.com/dchest/nacl-stream-js/blob/master/nacl-stream.js by @dchest ?

[tarcieri]

@ekodo I think there's a lot more specification and protocol design work that needs to be done before standardizing an API.

[ghost]

I was asking @jedisct1 about this last night, we both share the opinion that this is out of scope for libsodium itself, but he said he was considering handling this in a different project.

There are a number of people looking for something like this, it would be extremely useful for a couple projects I'm working on. Having a standard, well designed, well implemented file encryption option would be great. Though it has to be done right, so @tarcieri is completely right, there's still a lot that needs to be done.

[tarcieri]

I think there's two completely different use cases to consider, both of which need to handle reordering and truncation attacks:

• Streaming: Encrypting and decrypting a stream of data a chunk-at-a-time, but always in a specific order
• Random access: Ability to write to arbitrary chunks of a file in a nonlinear manner (i.e. mutable encrypted files). In addition to the aforementioned attacks, this one needs to deal with replay attacks. Tahoe-LAFS provides an example of a secure solution to this problem (see Figure 2)

[ekodo]

In this thread are a lot of sentiments and suggestions, but in the end it is confusing people like me (non crypto experts).

Maybe i`am able to implement a solution for my projects with the given tools (libsodium/NaCl), but i (or others like me) need to know whats the right way to do it.

like @adamcaudill said: it has to be done right

[sarciszewski]

Not to be a bother, but should this ticket be closed if file encryption is going to be a separate project?

[tarcieri]

Yeah, this issue should be closed. It involves advanced crypto-protocol design, and Tahoe-LAFS is the state of the art. Anything that isn't an improvement on Tahoe's designs is a regression.