2
$\begingroup$

I have a project where I want to encrypt a file and split it up into several fragments and place these files on different systems. I want to do it on mobile phones as well, so I chose poly-chacha20 as encryption. In my tests it was faster than AES based encryptions. The concern of my tutor is now, that because of the nature of stream ciphers, it would be possible to decrypt each of the several fragments on its own, as long as you have the key, which would be a no go. In my tests I could decrypt the starting fragment, but not the fragments after that, so I'm not sure what is correct now. Is it possible to decrypt every fragment with the given key? Or is it needed that you have all the fragments first before decrypting them?

$\endgroup$
  • 2
    $\begingroup$ Why is being able to decrypt parts bad for your use-case? To me its sounds like you're trying to solve your problem is the wrong way. Perhaps secret-sharing or error-correcting-code are what you actually need. $\endgroup$ – CodesInChaos Nov 14 '16 at 11:09
  • $\begingroup$ The feature you desire is achievable through use of block ciphers, where each block depends on the previous block encryption/decryption result. $\endgroup$ – DarkLighting Nov 14 '16 at 15:23
  • $\begingroup$ @DarkLighting That's wrong - that is achieved by the proper mode of operation, not the block cipher itself. Don't forget there is ECB, although no one should ever use it. $\endgroup$ – tylo Nov 14 '16 at 17:05
  • $\begingroup$ @DarkLighting You'd need a pretty exotic mode of operation to prevent piece wise decryption. ECB, CBC, CTR, CFB, OFB, GCM, OCB, XTS all allow some degree of decryption (sometimes requiring the IV). $\endgroup$ – CodesInChaos Nov 14 '16 at 19:05
  • $\begingroup$ @CodesInChaos So you're saying blockcipher have the same problem? It is bad because we want/have to store the key on one of these places with some of the fragmented parts. This would mena that those parts which are stored with the key, could be decrypted. Do you have some material which I can read up and show to my tutor that changing to blockcipher won't help? $\endgroup$ – MikiMoto Nov 15 '16 at 10:15
4
$\begingroup$

Unless I'm misunderstanding something this should be fairly easy to do. The scheme of a stream cipher is the following :

                    Key
                     |
                     v
               +------------+
               |            |
     IV -----> |  Chacha20  +-----+
               |            |     |
               +------------+     |
                                  |
                                  v
MESSAGE ------------------------> +------>  CIPHER TEXT

Thus you have : $$K_{stream} \oplus Message = CipherText$$

If afterward you split your $CipherText$ into blocks of $n$-bits. Then you will notice that the first $n$ bits of the $K_{stream}$ are used to encrypt the first $n$ bits of the $Message$ resulting into the first $n$ bits of the $CipherText$ and so on...

Therefore, in order to decrypt a $block$ on a separated device, you need to know its position into the full $CipherText$ (how many bits are present before), generate the $K_{stream}$ from the $Key$ and $IV$, drop the first $n$ bits of this $K_{stream}$ where $n$ is the position of the $block$ in the full $CipherText$, and then you can start decrypting your $block$.

Remarks:

  • you don't need to know the length of the full $CipherText$ but only the number $n$ of preceding bits.
  • you will need this number anyway when you will want to recombine the blocks on a single device.
$\endgroup$
  • $\begingroup$ So it is indeed possible to decrypt each fragment on it's own if you have the key,iv and know the position of the fragment to get part of the plaintext... alright thanks for the quick answer, I guess I have to look for another solution then, because it is part of the requierment that this shouldn't be possible. $\endgroup$ – MikiMoto Nov 14 '16 at 12:49
  • 1
    $\begingroup$ Splitting the whole message into $n$ blocks is a bad solution here - the required functionality sounds like a secret sharing scheme, and in this case you could decrypt every piece locally given $n,k,iv$ - without needing the parts saved on the other devices. $\endgroup$ – tylo Nov 14 '16 at 17:12
2
$\begingroup$

A stream cipher on itself is not going to give you the properties you need.

Encryption can be a first step here, although it technically might not be needed - depending on your exact setup. But what you need is called a secret sharing scheme. There are various kinds of secret sharing, and the most simple one is:

  • If you want $n$ parts for message $m$, then generate $n-1$ random strings for $x_1,\dots, x_{n-1}$, and set $x_n = x_1 \oplus x_2 \oplus \dots x_{n-1} \oplus m$.
  • This is a "$n$ our of $n$" secret sharing. You need all $n$ strings and XOR them, otherwise you can't get back $m$ itself. (Assuming true randomness, this is information theoretically secure - it's an OTP).

You can also use information theoretically secure secret sharing for "$k$ out of $n$" schemes, where there are $n$ different shares and you only need $k$ shares to get the secret back (and it can be any $k$ shares, not specific ones). A well known scheme for this is Shamir's secret sharing.

But then it also depends on your other constraints. For example, in the schemes above each share has the same size as the original message / file. If you don't need information theoretic security but only computational security, the size can actually be reduced, e.g. with the construction in Secret Sharing Made Short, Hugo Krawczyk (1993), combining Rabin's Information Dispersal Algorithm and Shamir's secret sharing. But the security claim there isn't accurate, as described in Robust Computational Secret Sharing and a Unified Account of Classical Secret-Sharing Goals by Bellare and Rogaway (2007). For a practical work, Kraczyk's construction is still fine (because a proper block cipher has both of the mentioned security properties, also noted in the abstract).

But if your tutor didn't point you into this direction, Krywczyk's scheme is most likely beyond the scope of your project. If you're fine with "$n$ out of $n$" and don't care about the size, then the XOR construction above should be fine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.