While Sylvain conducted a light cryptanalysis on the BUGS Algorithm for his MSc Thesis (Available HERE) he came across what could be a new type of cryptanalysis attack. It is important to note at this point, this is only a theoretical attack which may not be practical.
Although the following two attacks are relevant to the BUGS algorithm, they could also be used to attack any algorithms using some type of Cipher Block Chaining (CBC) or Cipher Feedback (CFB) mode of operation, in fact, any algorithms using a XOR function between plaintext blocks as part of their encryption process.
The following assume the reader is familiar with the different block cipher modes of operation. Although we start with a simple example, it helps setting the context for which the final attack could be in theory applied to: any XOR operations.
1. Chosen plaintext attack with restricted input elements
This is an extension of a known plain text attack by choosing the plaintext to be encrypted.
While conducting the cryptanalysis of one function of my BUGS algorithm, the shuffling function, we quickly encountered a problem when trying to use known or chosen plaintext attacks. Please note that although we have kept the word “shuffling”, this really should be renamed after some type of “Chain Block” references.
First, let describe a very simple CBC function example which could be one using a key/password to generate a “unique” sequence where a specific plaintext block “source” is XORed to another plaintext block “target” resulting into the targeted plaintext block to become encrypted, in other words, a ciphertext block. The process can then be repeated with another “source” plaintext block being XORed to another “target” plaintext block until all the blocks have been XORed/encrypted but one. That last “source” plaintext block would then have to be encrypted in a different way (i.e.: Xored with the key). To decrypt such ciphertext would require the right password/key to be used to reverse that “unique” sequence used during the encryption.
The above simple shuffling function is effectively using the plaintext to encrypt/XOR itself using a key or password as the sequence generator.
Those simple shuffling functions can easily be attacked using known or chosen plaintext attack to recover information on the key/password used.
However, like all modern algorithms, the BUGS algorithm shuffling function does not simply XOR a plaintext block with another. It first XOR two “source” plaintext blocks together, resulting into a XOR-sum of this “source” pair. The resulting XOR-sum is then XORed to another “target” plaintext block to encrypt it and therefore become a ciphertext block. The process is then repeated with two different “source” plaintext blocks and the target has to be one of the two previous “source” plaintext blocks, this is to avoid the same “source” pair to be used more than once as a XOR-sum. The last “source” block is then encrypted with the key. That key was also used to generate the sequence where the selection of the “source” pair and the “target” were derived from.
This creates a new problem when trying to apply a traditional known or chosen plaintext attack. You cannot just take a block of known plaintext and try to XOR it to a different ciphertext block until it reveals another known plaintext block. Please note this is only one part of the BUGS algorithm, for a more in-depth description please refer to this SUMMARY or, even better, download the full explanation.
The idea, therefore, is to find a way to populate the plaintext with specific values making it easy to extract which pair of plaintexts were used to generate the XOR-SUMs and then, ultimately, extract information from the keys used to XOR those XOR-SUMs.
A solution would be to have different values producing unique paired XOR-sums but this is generally not the case as shown below where two different pairs produce the same XOR-sums:
10110 XOR 10000 = 00110
00100 XOR 00010 = 00110
To solve our problem, we can restrict plaintext values to be power of twos. This implies that only values whose representation in base 2 is of the form shown below are allowed:
S0={1, 10, 100, 1000, …etc}
If we XOR two values from our new set, S0, then we have for example:
1000 XOR 100 = 1100
And only 1000 and 100 could have been used to produce a XOR-sum of 1100
We will call this property a XOR-sum uniqueness property from now on.
This allows us to reconstruct the full XOR sequence used during the encryption process in a very fast manner. As before, because this sequence is dependant of the key used to encrypt the plaintext we would gather information that could be used to recover the key.
It is interesting to note that our very simple rule, used to create the S0 set mentioned above, is also very restrictive in the number of unique values that can populate S0 for a given bit length. Therefore, the size of the chosen plaintexts will also be governed by the limitation in the number of unique values available for a given plaintext block size. If the attacked cipher uses 128 bits plaintext block, then the maximum number of unique values we can generate is 128. This means the maximum size our chosen plaintext could have in this context is: 128 bits * 128 = 2Kb
This has no impact on our ability to reconstruct the full XOR encryption sequence but if more statistics were required to recover the key then it may impact the performance of this attack.
However, while researching this problem it seems there might be different sets which could keep the same properties we are looking for, a XOR-sum uniqueness on two elements of S, but with a larger element population. Indeed, the following elements are of 8 bits size and have that XOR-sum uniqueness property:
S1={ 1, 10, 100, 1000, 1111, 10000, 100000, 110011, 1000000, 1010101, 1101010, 10000000, 10010110, 10101011, 11011011, 11101101, 11110111, …}
What is interesting to note is that there are more than 8 elements in this set. These numbers were filtered out by designing a rudimentary computer program designed to brute force all possible set of 8 bits values yielding the XOR-sum uniqueness property. To my knowledge, there is currently no known method to optimally compute those numbers other than using a near optimal “Greedy” algorithm mathematical function. Finding such optimal method to generalize that property was not in scope for my thesis.
< strong>Further extension of this technique could yield an even more interesting concept as described in the next attack.
2. Unrestricted XOR-Sum Uniqueness Cryptanalysis attack
If the plaintext was not chosen but had been created using elements from S0={10,100,1000,…} then it would still be possible to attack the corresponding ciphertext without choosing or knowing the plaintext because our XOR-sum uniqueness property still holds true for any number of XOR operations on elements of S0
For example, if our plaintext is: P={10,100,1000} and the ciphertext is C={1110} we can reconstruct the XOR sequence as follow:
10 XOR 100 XOR 1000 = 1110
As only 10, 100, 1000 could have produced that XOR. This means we do not have to first XOR the plaintext out of the ciphertext to conduct our attack and in this specific case we do not need to know the plaintext.
This attack is obviously not practical because it is more than unlikely anyone would use this type of elements to produce plaintexts. However, the really interesting aspect of this concept, is to extend it one last step further.
For a practical attack we would need the XOR-sum uniqueness property discussed earlier to also hold true for a set of values created without any restrictions.
However this is not the case, if we XOR two elements from such a set the XOR-sum will not be unique.
Taking into consideration what we have learnt when discussing the different modern cryptanalysis techniques (MSc Thesis available HERE), one attack was created to resolve the following problem:
How to define linear equations from a non linear cipher?
The solution, through Linear Cryptanalysis (LC), was to define linear approximations of the cipher and use probabilities and statistics to attack it.
It may be possible to use the same logic to resolve the following problem:
How to define XOR-sum uniqueness properties on an unrestricted set of elements?
A possible solution would be to define XOR-sum uniqueness “approximations” of the cipher combined with a similar LC technique of using probabilities and statistics to attack it.
By “approximations” we mean the following:
Let E() be an encryption function which takes two plaintext blocks, calculate a XOR-sum and use it to encrypt another plaintext block.
For P={P0, P1, P2} = {11110000, 11111111, 10101010}
Then C0= E(P0 XOR (P1 XOR P2)) = 11110000 XOR 01010101 = 10100101
The approximation would single out bits on the plaintext and ciphertext so the XOR-sum uniqueness property holds true, in our example a possible approximation would be:
From P= {11110000, 11111111, 10101010} and C0= 10100101
Then single out the bits highlighted in Red and consider the following approximation:
P= {00100000, 00000100, 10000000} and C0= 10100100
This new set has the XOR-sum uniqueness property we are looking for and is related to the original plaintext and corresponding ciphertext on the bits highlighted in Red.
Therefore, as stated before, using a similar logic as the one used in Linear Cryptanalysis we could calculate the probabilities for this type of approximation holding true, produce some statistics using large number of plaintext/ciphertext pairs encrypted with the same secret key, try all possible sub-key values and record when our approximation did hold true. This may indicate probable correct bits values of the secret key.
This technique could be generalized and extended to attack anything being a result of a XOR-sum, such as keys being XORed to plaintext/ciphertext blocks.
It may be possible to refine that technique by studying the probability distribution of the possible XOR-sums. It was unfortunately out of scope for my thesis to investigate that concept further and as stated at the beginning of this page, it may be a completely unpractical attack with no chances of success. On the other hand, if this could work, it would be called an Unrestricted XOR-sum Uniqueness Cryptanalysis attack.
Time permitting, we will try to investigate this form of attack further and update this website with our findings.