# Is it possible to unroll stacked XOR'd strings without brute-force?

Given:

• An initial string (sBase) that is visible to EVERYONE

sBase = "syLgETsPihVXBRuVR4eI"

• Several other strings that are only visible to ME

sXOR1 = "48MjsK7SiNMGV7wxb3Kb"

sXOR2 = "jokxnPZpUWmJfaL0BS1t"

sXOR3 = "4KAh1TEAmtWFV6HvTUda"

sXOR4 = "wOnlFV4vUiJkaESXX25X"

sXOR5 = "77H6NQrcmrdHuThmBdTL"


Assume:

• XOR sBase with sXOR1 and get sResult
• XOR that sResult with sXOR2 and get the first stacked XOR sResult
• Continue to XOR the rest of the sXORn strings with each new sResult

Final sResult = "Y??Ga??' ?¤00#=]<W?*"


Questions:

1. Can I determine the original sXOR strings from the XOR stacked sResult using the known sBase string?
2. Or is the only solution to attack sResult via brute-force to determine the original sXOR strings?

In case I wasn't clear with the explanation of my XOR operations:

• The result of each XOR operation gets XOR'd with the next sXOR string

sResult = sBase XOR sXOR1
sResult = sResult XOR sXOR2
sResult = sResult XOR sXOR3
sResult = sResult XOR sXOR4
sResult = sResult XOR sXOR5

• The final sResult is a single string resulting from a series of XOR operations

• I am wondering if it is possible for someone (who only knows the values of sBase and the final sResult) to determine how many XORs took place and if they can determine what my sXORn string values were that were used in the process?

============================================================

EDITED TO SHOW SUCCESSFUL RESULTS - 2017-05-06

Looking at the answers and comment (over and over) - and finally getting a handle on the "bits" example that @daniel gave - I was able to figure out how to code a solution for finding sets of strings that generate equivalent XOR results.

Now I am able to continue to test my hypothesis.

Thanks everyone!
CBruce

Note that the xC and xD columns are totally different in these two runs.
And that the two outside result columns are the same for both runs.

This shows that (xCR$XOR xDR$) is equivalent to the multiple XOR operations
using my sXOR(n) strings.

The routine is fast - and I can now find all of the XOR equivalent strings
that I want.

FIRST RUN:
'---------------------------------------------------------
sXORResult =591D0D47611C1D27001E0F3030233D5D3C571A2A        'Hex$of the xR values in the first column - the result of my sXOR(n) operations '--------------------------------------------------------- xR=01011001 89 xC=00110110 54 xD=01101111 111 R2=01011001 89 xR=00011101 29 xC=11110111 247 xD=11101010 234 R2=00011101 29 xR=00001101 13 xC=01111011 123 xD=01110110 118 R2=00001101 13 xR=01000111 71 xC=11100001 225 xD=10100110 166 R2=01000111 71 xR=01100001 97 xC=11010111 215 xD=10110110 182 R2=01100001 97 xR=00011100 28 xC=01100110 102 xD=01111010 122 R2=00011100 28 xR=00011101 29 xC=10100111 167 xD=10111010 186 R2=00011101 29 xR=00100111 39 xC=10011011 155 xD=10111100 188 R2=00100111 39 xR=00000000 0 xC=00100010 34 xD=00100010 34 R2=00000000 0 xR=00011110 30 xC=11100000 224 xD=11111110 254 R2=00011110 30 xR=00001111 15 xC=00101111 47 xD=00100000 32 R2=00001111 15 xR=00110000 48 xC=11101111 239 xD=11011111 223 R2=00110000 48 xR=00110000 48 xC=00111101 61 xD=00001101 13 R2=00110000 48 xR=00100011 35 xC=01110111 119 xD=01010100 84 R2=00100011 35 xR=00111101 61 xC=01100010 98 xD=01011111 95 R2=00111101 61 xR=01011101 93 xC=11000000 192 xD=10011101 157 R2=01011101 93 xR=00111100 60 xC=10001100 140 xD=10110000 176 R2=00111100 60 xR=01010111 87 xC=11000010 194 xD=10010101 149 R2=01010111 87 xR=00011010 26 xC=10101110 174 xD=10110100 180 R2=00011010 26 xR=00101010 42 xC=00011010 26 xD=00110000 48 R2=00101010 42 '--------------------------------------------------------- xCR$       =36F77BE1D766A79B22E02FEF3D7762C08CC2AE1A        'Hex$of the xC values in the second column xDR$       =6FEA76A6B67ABABC22FE20DF0D545F9DB095B430        'Hex$of the xD values in the third column sCDResult =591D0D47611C1D27001E0F3030233D5D3C571A2A 'Hex$ of the R2 values in the fourth column - the result of (xCR$XOR xDR$)
'Note that sXORResult (above) and the sCDResult are equivalent
'---------------------------------------------------------

SECOND RUN:
'---------------------------------------------------------
sXORResult =591D0D47611C1D27001E0F3030233D5D3C571A2A
'---------------------------------------------------------
xR=01011001  89   xC=00000010   2   xD=01011011  91   R2=01011001  89
xR=00011101  29   xC=11001100 204   xD=11010001 209   R2=00011101  29
xR=00001101  13   xC=00100101  37   xD=00101000  40   R2=00001101  13
xR=01000111  71   xC=00011110  30   xD=01011001  89   R2=01000111  71
xR=01100001  97   xC=11000111 199   xD=10100110 166   R2=01100001  97
xR=00011100  28   xC=11100100 228   xD=11111000 248   R2=00011100  28
xR=00011101  29   xC=01000101  69   xD=01011000  88   R2=00011101  29
xR=00100111  39   xC=10010011 147   xD=10110100 180   R2=00100111  39
xR=00000000   0   xC=00100011  35   xD=00100011  35   R2=00000000   0
xR=00011110  30   xC=10010000 144   xD=10001110 142   R2=00011110  30
xR=00001111  15   xC=00010110  22   xD=00011001  25   R2=00001111  15
xR=00110000  48   xC=10000000 128   xD=10110000 176   R2=00110000  48
xR=00110000  48   xC=01111110 126   xD=01001110  78   R2=00110000  48
xR=00100011  35   xC=00110011  51   xD=00010000  16   R2=00100011  35
xR=00111101  61   xC=11000000 192   xD=11111101 253   R2=00111101  61
xR=01011101  93   xC=00001010  10   xD=01010111  87   R2=01011101  93
xR=00111100  60   xC=01100010  98   xD=01011110  94   R2=00111100  60
xR=01010111  87   xC=10000010 130   xD=11010101 213   R2=01010111  87
xR=00011010  26   xC=00001111  15   xD=00010101  21   R2=00011010  26
xR=00101010  42   xC=01001000  72   xD=01100010  98   R2=00101010  42
'---------------------------------------------------------
xCR$=02CC251EC7E44593239016807E33C00A62820F48 xDR$       =5BD12859A6F858B4238E19B04E10FD575ED51562
sCDResult  =591D0D47611C1D27001E0F3030233D5D3C571A2A
'---------------------------------------------------------

• Stacked xors are useless, since they can be combined into one. Also what you are looking for is OTP. May 3, 2017 at 18:58
• Hmm ... just noticed my question was down-voted. I wish people would comment and explain why they did that, so I could figure out what I did wrong. Oh well - who really cares? It's Star Wars DAY! MAY the FOURTH be with You! May 4, 2017 at 15:10
• I did downvote your question since it doesn't explain what you are trying to achieve and you are obviously overdoing things. I consider what you are asking about pointless and easy enough to understand with some basic research. I tried to point you in right direction (OTP), but sadly I don't think you did read about that. May 4, 2017 at 15:28
• Thanks @axapapa! Believe me, I researched for two weeks before coming here to ask. But I couldn't find the answer to my question - which was - can you tell the number of and exact strings I was XOR'ing together. I understand OTPs completely (they're simple) and I am using OTPs as the sXORn strings - but I didn't have the math expertise to find the answer to my question. My company wouldn't let me give the full explanation of WHY I was asking - so I just tried to make the question itself as straightforward as possible. Sorry if it didn't make sense to you. But THANKS for the feedback! May 4, 2017 at 16:21

I don't know what your security goal is but the flip side of the correct statement " stacked XORs are useless" is that any string can be "unstacked" into an XOR of as many strings as you like, and no one can tell how many strings were used.

Fixed length strings under XOR form a group, say $G$. So for any $S \in G$ we can write $$S=X \oplus (S\oplus X),$$ which gives an unstacking for any nonzero string $X$.

So for $n$ bit strings there are $(2^n-1)$ ways of unstacking a string into two XORs since there are as many nonzero strings $X.$

You can repeat this process as many times as you like.

• Apologies @kodlu - I'm a programmer, not a mathematician. I believe your notation says: S is a member of group G; S = X xor (S xor X) - but I don't know how to plug which of my strings into that formula. Anyway ... Given (the above) sBase and final sResult - do you mean that you can find the five key strings that I used to create sResult - or just that you can find many possible strings that could be XOR'd together to recreate my sResult? Thanks! May 4, 2017 at 0:28
• You can find many, many strings that could be XORed together to create your result. May 4, 2017 at 3:18
• @CBruce If you just know $A=B \oplus C \oplus D$ and you know the value of $A$ and $B$, then you can make up many pairs $(C,D)$ which fullfill the equation. It is impossible for anyone to know the original ones - but it is also impossible to prove that one specific pair was used. Basically the individual information of $C$ and $D$ is lost and only the value $C \oplus D$ remains.
– tylo
May 4, 2017 at 8:24

I'll show what the first comment meant

Given:

• An initial bit that is visible to EVERYONE

sBase = "1"

• Several other bits that are only visible to ME

sXOR1 = "1",

sXOR2 = "1", 1 XOR 1 = 0

sXOR3 = "1", 0 XOR 1 = 1

sXOR4 = "0", 1 XOR 0 = 1

sXOR5 = "0", 1 XOR 0 = 1

all = "1"


Comparing results:

    Final sResult = sBase XOR sXOR1 XOR sXOR2... = "0"
Final sResult = sBase XOR all = "0"


So this means instead of XORing with the 5 strings I could have just used one string and the result would be the same. So the way you used 5 strings instead of 1 just seems wasteful, you could have just used 1 string. How you get that 1 string might involve putting 5 together, if you have 5 sources of uniformly distributed random data but don't trust each one separately you might do this for example.

Also if you are using this XOR cipher with truly random data as the key (as a one time pad) then it cannot be brute forced. Again chose the message to be only 1 bit long, by 'brute force' you can only show that the encrypted message was either a 1, or a 0.