Skip to content

Instantly share code, notes, and snippets.

@ryanamaral
Forked from ignis-sec/mcaffee.py
Last active December 8, 2022 06:38
Show Gist options
  • Save ryanamaral/4a149e7fe214de7b1114c234d4fc5fba to your computer and use it in GitHub Desktop.
Save ryanamaral/4a149e7fe214de7b1114c234d4fc5fba to your computer and use it in GitHub Desktop.

Boolean algebra is one of the foundations of computer science.

There is an unusual property of the boolean XOR operation that I doubt many, or anyone at all, has considered:

If you take any three sets of characters of any equal length - let's label them A, B and C - and then:

XOR A to B Then XOR the result of B to C Then similarly XOR C to A

And then perform 4 iterations of the above.

And finally:

XOR A to B And then B to C

It will result in the original contents of A moved to C, C moved to B and B moved to A.

Of interest here is that the 3 results of the 3rd iteration, though deterministic as a whole, are entirely random within each of the 3 independent data segments. Thus if any one of the 3 segments is missing or withheld, it is impossible, from the remaining 2 to extract even the tiniest fragment of the 3 original contents.

The simplicity of this process is astonishing. A person of average intelligence could decode a message, using pencil and paper, providing they possessed all three interim segments.

I'm describing this tidbit in the hopes that my observations might be of some small use to those engaged in the research of cryptography.

Addendum:

The same concept of sequential XOR operations works with 4 data sets requiring 3 iterations and 5 data sets with 2 iterations.

Strangely with 6 sets, the process unravels and produces chaos no matter how many iterations.

Please God, someone explain.

(source)

#https://twitter.com/officialmcafee/status/1397568860082122752
#https://twitter.com/ahakcil/status/1397888724936105987
import random
import copy
RST = '\033[0m'
def rand_data(size):
d = []
for i in range(size):
d.append(random.randrange(0,255))
return d
def dump_vars(original_set,d):
for i in range(len(d)):
for j in range(len(original_set)):
if(d[i]==original_set[j][i]):
print(f'\033[{91+j}m', end='')
print(f"{d[i]:3}", end='')
print(RST, end='')
if(i !=len(d)-1):
print(", ", end='')
else:
print("")
def dump_set(original_set, set):
for i in range(len(set)):
print(f"{chr(ord('A')+i)}=", end='')
dump_vars(original_set, set[i])
def arr_xor(arr1,arr2):
ret = []
for i in range(len(arr1)):
ret.append(arr1[i]^arr2[i])
return ret
def seq_xor(set):
origin = copy.deepcopy(set)
for i in range(1,len(set)):
set[i] = arr_xor(set[i-1],set[i])
set[0] = arr_xor(set[0],set[-1])
def final_xor(set,original_set):
for i in range(1,len(set)):
set[i] = arr_xor(set[i-1], set[i])
iter_counts = [4,3,2,1]
for i in range(3,7):
set = []
original_set = []
for k in range(i):
set.append(rand_data(5))
original_set = copy.deepcopy(set)
print(f"{i} DATA SETS###########")
dump_set(original_set,set)
print()
for j in range(iter_counts[i-3]):
seq_xor(set)
print(f"Iteration {j+1}=====")
dump_set(original_set,set)
print("Final xor=====")
final_xor(set,original_set)
dump_set(original_set,set)
print()
#part below is for finding stable points
#exit()
def compare_sets(set1,set2):
for i in range(len(set1)):
for j in range(len(set1[0])):
if(set1[i-1][j]!=set2[i][j]):
return False
return True
for l in range(3,25):
print(f"{l} DATA SETS###########")
set = []
original_set = []
for k in range(l):
original_set.append(rand_data(5))
set = copy.deepcopy(original_set)
#print("Starting with following:")
#dump_set(original_set,set)
#print()
found=0
for j in range(2500000):
seq_xor(set)
set_save = copy.deepcopy(set)
final_xor(set_save,original_set)
if(compare_sets(set_save,original_set)):
print(f"Found in iteration {j+1}")
#dump_set(original_set,set_save)
found=1
break
if not found: print("NOT FOUND.")
else: print("")
@ryanamaral
Copy link
Author

ChatGPT:

The property you are describing is known as the "swap property" of the XOR operation. It states that if you XOR two numbers and then XOR the result with a third number, the final result will be the same as if you had XORed the first two numbers with each other, then XORed the second and third numbers with each other, and finally XORed the first and third numbers with each other.

This property is a consequence of the fact that XOR is a commutative and associative operation. This means that the order in which the XOR operations are performed does not matter, and that multiple XOR operations can be combined into a single operation.

For example, suppose we have three numbers A, B, and C. We can use the swap property to swap the values of A and B as follows:

A = A XOR B
B = A XOR B XOR B = A
A = A XOR B XOR A = B

We can use the same property to swap the values of A and C, or B and C. This is why your description of the process as "moving" the values from one set to another is apt - it is as if the values are being shuffled around.

The reason the process breaks down with six sets is that with more than three sets, the XOR operations are no longer sufficient to swap all the values. To see why, consider what would happen if we tried to use the same process to swap the values of all six sets. We would need to perform six XOR operations to swap the values of sets A and B, six more to swap the values of sets C and D, and so on. But since the XOR operation is reversible (that is, if we XOR a number with itself, we get 0), each of these operations would cancel out the previous one, and the final result would be the same as the original values.

In short, the swap property of XOR is a useful property, but it has its limitations. It is not a general-purpose method for encrypting or decoding messages, and it is not clear how it could be used in cryptography. It is, however, an interesting mathematical property that is worth understanding and exploring.

@ryanamaral
Copy link
Author

McAffee's point:

Of interest here is that the 3 results of the 3rd iteration, though deterministic as a whole, are entirely random within each of the 3 independent data segments. Thus if any one of the 3 segments is missing or withheld, it is impossible, from the remaining 2 to extract even the tiniest fragment of the 3 original contents.

ChatGPT:

While it is true that the results of the XOR operations in your described process are deterministic and will always produce the same result given the same input, it is not accurate to say that the results are "entirely random" or that it is impossible to extract any information from the remaining two segments if one is missing.

The XOR operation is a binary operation that takes two input values and produces an output value. The output value is determined by comparing the input values bit by bit and setting the corresponding output bit to 1 if the input bits are different, and 0 if they are the same. Because of this, the output value of an XOR operation will always be completely determined by the input values.

In your described process, the XOR operation is being performed on sets of characters, which are sequences of bits. The output of the XOR operation will be a new set of characters with the same length as the input sets. The resulting characters will be determined by the input characters in a deterministic way, as described above.

However, it is not accurate to say that the resulting characters are "entirely random". The output characters will be determined by the input characters, and it is possible to extract some information about the input characters from the output characters, even if one of the input sets is missing.

For example, suppose we have three sets of characters A, B, and C, and we perform the XOR operations as described in your question. The resulting sets of characters D, E, and F will be determined by the input sets in a deterministic way, but it is still possible to learn some information about the input sets by examining the output sets. For example, if we know the values of two of the output sets (D and E, for instance), we can use the XOR operation to recover the value of the third output set (in this case, F).

In summary, while the swap property of XOR is an interesting mathematical property, it is not accurate to say that the resulting sets of characters are "entirely random" or that it is impossible to extract any information from the remaining sets if one is missing. The output sets will be determined by the input sets in a deterministic way, and it is possible to learn some information about the input sets by examining the output sets.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment