does using a long delimiter multiple times degrade encryption security?

Question

I need to condense multiple distinct pieces of data into a single encrypted string that can be decrypted and separated out later.

Before encrypting, I need to separate the data with some kind of delimiter that will never be confused with the data.

I have chosen to use a single, constant 20 character hexadecimal delimiter. For example:

data_piece
data_item
data_obj

becomes

data_piece214c1a16bb5236e7090cdata_item214c1a16bb5236e7090cdata_obj

which then becomes

vjXC4Xd7LU6aZX4QClZkU330XT39hnoLoQYIFNov39tPX96OKsid7mOBHwoVb4KspyvMpVPrsfHCUd1zbzXyETtgW5yF4b0oaK8Q%2FZCZN2XBvbfL3vooD%2FDLOza3%2FSrSNNzIW8oALZhv08LBzeg3DvgUgC8fg0xv4%2BCAEIQLIhM%3D

after running it through a standard Rijndael encryption algorithm with a 256 bit key and a url encoder.

Does this repetition of a single delimiter degenerate the security of the encryption if there are occasions when it may be used two dozen times? If so, should I use an array of unique delimiters so that they are never repeated within the same string, or does the difference really not matter for practical encryption purposes?

UPDATE:

The reason I chose to use a long delimiter instead of a small one is for cases like this:

delimiter = |
data1 = mydata\\\\
data2 = \|\|\|data

unescaped: mydata\\\\|\|\|\|data

escaped: mydata\\\\\\\\|\\\|\\\|\\\|data

writing code to unescape that and separate it out is not very straightforward. It is possible to do, but there will have to be a loop that continually looks for an end to sequence of escape characters preceding the delimiter, then unescapes it only if the number of escape characters in the sequence is odd.

Since this involves checks before every unescape function, I thought a long delimiter was better, because it can be practically guaranteed to never occur in the data, and allows the separation process to be as simple as possible.

Answer 1

You are supplying what is known as a "crib". If you use a long sequence, especially at the beginning, you are losing some (albeit very little) security.

You can easily mitigate the problem by using a random string, as long as you are able to recover it. For example you might use a 20-byte random string. You know that the first 20 bytes are the delimiter, and look for that in the rest of the string. This still supplies a check for a brute force attacker to determine whether he has found the correct decryption, but the brute force itself should be unwieldy enough that this little help is of almost no use. He still has to decrypt a sizeable portion of the ciphertext before running the test. Compared to only decrypting the crib section, it's an improvement.

You can also use a short, escaped delimiter. Instead of "betting" (with astronomical chances in your favour) that the delimiter will never come up "passively" in the text, you actively endeavour for it to not come up by replacing it or escaping it. For example you can escape all "\" and "|", then decide that a single "|" will represent a delimiter. The chances of a unescaped "|" in a incorrectly decoded ciphertext are astronomical, which makes cribbing worthless for an attacker. At the same time, your escaping naked "|"'s guarantees you that no naked "|"'s will occur in your plaintext. On the other hand this requires one additional stage:

 plain|text\nand --> plain\|text\\nand|another text --> ....
 another text

If you choose a delimiting character that's usually -escaped, such as maybe $, you can do this with several standard libraries and commands in various languages.

Updates

As for security: the random delimiter at the beginning does not decrease security by being at the beginning: since it's random, it cannot be used as a crib. The decrease in security comes from the fact that the delimiter will occur several times in the decrypted text, thereby supplying a confirmation that it is indeed the correctly decrypted text. (If the delimiter is short, chances of it occurring naturally in a incorrect text are not negligible, therefore its occurrence is not a confirmation. And of course its non-occurence can't be a confirmation either). The delimiter has to occur at the beginning because that's the only way you have (the delimiter being random...) of knowing yourself what the delimiter is. Every ciphertext will have its own.

Space considerations

TL;DR unless you have many chunks and/or very short, delimiters are probably the way to go to save space.

In general, you will have enough knowledge of the incoming data to choose an infrequent character as delimiter and as escape character, or at the very least, you will rarely have "pathological" plaintexts. To squeeze to the utmost the data, you can in theory write a function that will (a) determine the two less often used characters in any given plaintext, and (b) use them as delimiter and escape. At most, these characters will occur 3 times every 256 characters. All of them need escaping and will make 256 characters grow to 259, which is a 1.2% increase in size. Also, you will need to store these two characters e.g. at the beginning in order to know how to unescape the string. So we have a fixed overhead of two bytes, a size-overhead of 1.2% and a delimiter overhead of 1:1; if L is the total length of the message and N is the number of chunks, the plaintext thus treated will grow to be 1.012*L+N+2.

Using a delimiter and an unescaped plaintext of length L bytes, the probability of a sequence of length D occurring at position x is (1/256)^D and there are (L-D+1) possible values for x. So the probability of D not occurring anywhere is 1-(1-(1/(256^D)))^(L-D+1).

(Or =(1-POWER((1-POWER(1/256,$D$1)),A2-$D$1+1))*1000000 if you want to get it into a Google spreadsheet and calculate collision probability in millionths).

For a sequence of chunks 16K in size, to be sure to have a Pcoll < 1/million I need at least a delimiter length of 5 (which is overkill; but 4 is too short, giving a Pcoll of around 4/1000000).

So four chunks of 4K each would require 1.012*16384+4+2 = 16586 bytes with escaping and 16384+4*5 without, i.e., delimiters allow a saving of about 182 bytes (with a probability of the delimiter occurring by chance of less than one in a million), and 178 bytes if you use a 6-character delimiter (chances of less than one in a billion, or one thousandth as before).

We hit parity when 1.012*16384+N+2 = 16384+N*5, i.e. when you have more than 50 chunks (or 38 chunks if you use six-char delimiters).

PHP

Working in PHP I think you might find it advantageous a sequence like:

• serialize (you obtain a string with all your chunks)
• gzcompress (you save space, and get a maximum-entropy block of data)
• encrypt

Bruteforcing the first AES block will allow verifying whether the decryption key is correct (the beginning of the gzcompressed serialized object may act as a crib), but doing this in the first place (and weeding out the false positives) is still computationally unfeasible. It would still be cheaper to beat the key out of you. And the implementation and maintainability advantages are worthy of the risk.

Answer 2

What you are describing is a variation on a known-plaintext attack, which is a type of cryptographic attack that the Rijndael family of ciphers is highly resistant to.

With such a long delimiter, an entire encryption block is likely to contain only characters from the delimiter string, which gives an attacker a minor advantage (they don't need to worry about the non-delimiter parts of the data), but performing an attack is so difficult that it's not worth worrying about.

Assuming by "Rijndael" you mean AES-256 (Rijndael with a 256-bit key and a 128-bit block), you can eliminate even that trivial weakness by using a 15-character string for separation. Such a string is one byte shorter than the block size, so you ensure that at least one byte of varying data is always encoded in the same block as the separator.

Answer 3

You need to consider the encryption mode you are using and also consider the fact that most encryption modes alone do not authenticate the data.

I recommend using GCM mode as it is fast, used in TLS 1.2, makes use of an IV so regardless of what your message starts with a crib is not feasible. It also authenticates the message in the same pass so you can know what you decrypt is valid/authentic.

But the ultimate answer on modes and with a warning to beginners is here: https://stackoverflow.com/a/22958889/2238268

If you really care about security you really have to use experts who understand the many subtle aspects. Security is achieved not just with technology controls and requires an organisational commitment and undertaking.

I would also use a more robust approach to delimiters. A single delimiter character and proper escaping with a simple regex string replacement can suffice and avoid higher order attacks on your system.

Answer 4

Yes. But the encryption (using AES-256) is still strong enough to withstand real world brute force attacks, so the added weakness is negligible.

This long delimiter technique can be improved by using a random delimiter for each string of condensed data.

However, using a long delimiter is not the best technique for any circumstance. A one character delimiter is sufficient and better for both security and memory usage. To mitigate the issue I described above, use the following procedure:

delimiter = |
data1 = mydata\\\\
data2 = \|\|\|data

encode data separately to remove delimiter character altogether
(ex. using php rawurlencode)
mydata%5C%5C
%5C%7C%5C%7C%5C%7Cdata

serialize the data
mydata%5C%5C|%5C%7C%5C%7C%5C%7Cdata

encrypt the serialization
8XcaEW2st4qBZhGB1MbO200eLbhhoOV3V4MCpa9k6ODiN6dcJypTWabq2YsUwBC2tnkKdaUOU7jviilahNQ2B+DRvtLMYDrFNp3qHh0oWMUAuAnjCcKuHfE9tIcd/Jhv

If you reverse that process, it is very straightforward to separate the data and get it back to its original form.

Notice that the final encrypted string is 30% shorter than the one that used the long delimiter.

See lserni's answer for more details and space saving methods.