0
$\begingroup$

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?

(edit - added comment)

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
'---------------------------------------------------------
$\endgroup$
  • 3
    $\begingroup$ Stacked xors are useless, since they can be combined into one. Also what you are looking for is OTP. $\endgroup$ – axapaxa May 3 '17 at 18:58
  • 1
    $\begingroup$ 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! $\endgroup$ – CBruce May 4 '17 at 15:10
  • $\begingroup$ 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. $\endgroup$ – axapaxa May 4 '17 at 15:28
  • 1
    $\begingroup$ 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! $\endgroup$ – CBruce May 4 '17 at 16:21
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – CBruce May 4 '17 at 0:28
  • $\begingroup$ You can find many, many strings that could be XORed together to create your result. $\endgroup$ – kodlu May 4 '17 at 3:18
  • $\begingroup$ @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. $\endgroup$ – tylo May 4 '17 at 8:24
1
$\begingroup$

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.

$\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.