# Does XOR'ing a random number with its inverse reduce its security if the result is a palindrome?

[And four related questions/examples below:]

2) If a random 256-bit number is XOR'ed with its reverse (i.e. the big-endian version XOR'ed with the little-endian version), does this reduce the security properties in terms of bits, if the result is a palindrome, as there are only $${2^{128}}$$ such palindromes in the range of $${2^{256}}$$?

3) Can an adversary efficiently brute-force search just the palindromes in that range?

Example: an L-bit random N $${\oplus}$$ reverse(N) = palindromic string L-bits long.

Example using a random 256-bit binary string:

N=1000001110111000001110001111100111001000111111111111010110111001011010110110010110011001100010110110101101001000001110111111111111001110101001110001101101110101010101110011000111000010101011001010100000110110111000010101101000100111001010110110011011010110

Reverse(N)=0110101101100110110101001110010001011010100001110110110000010101001101010100001110001100111010101010111011011000111001010111001111111111110111000001001011010110110100011001100110100110110101101001110110101111111111110001001110011111000111000001110111000001

N $${\oplus}$$ Reverse(N) = 1110100011011110111011000001110110010010011110001001100110101100010111100010011000010101011000011100010110010000110111101000110000110001011110110000100110100011100001101010100001100100011110100011010110011001000111100100100110111000001101110111101100010111

4) Are there any advantages in using a longer key with reduced security than a smaller key with the same security (i.e. could there be an advantage having a 256-bit key with 128-bits of security, compared to having a 128-bit key with a 128-bits of security?)

5) In addition, could there be benefits such as only having to retain half of the palindrome, in order to reconstruct the other half, in terms of compression/notation while avoiding information loss despite any reduced security?

Example using above palindrome where only the leading 128-bits are retained: 11101000110111101110110000011101100100100111100010011001101011000101111000100110000101010110000111000101100100001101111010001100 and where reconstruction of the original 256-bit palindrome is achieved by concatenating the reverse of the 128bits to the right-end of the retained 128 bits as follows: 11101000110111101110110000011101100100100111100010011001101011000101111000100110000101010110000111000101100100001101111010001100||00110001011110110000100110100011100001101010100001100100011110100011010110011001000111100100100110111000001101110111101100010111

• "if the result is a palindrome" That phrasing implies you think that the result being a palindrome only sometimes happens. Is that your understanding? Also, what does "Can an adversary efficiently brute-force search just the palindromes in that range?" mean? Aug 6 '19 at 21:25
• Thanks for mentioning that. No, I was not implying it in that context, it should always happen, I didn't assume it sometimes happens but worded it as such because it might not be obvious to the user in the case leading zeroes are not formatted to be retained (i.e. if they are lost). Regarding the brute-force search, of the 2^128 palindromic 256-bit strings in the range of 2^256, is there an efficient/fast way to search only those palindromic strings? (i.e. either deterministically in order or searching only those and not the non-palindromic strings). Aug 9 '19 at 13:22
• You mean, is there a way to generate the 2^128 palindromic 256-bit strings? That's simple, just create a 128-bit string, then append its reverse. Aug 9 '19 at 14:33
• Right, that would indeed be one very simple way to do it and could be done in order (i.e. starting from smallest to largest or vice-versa). Thanks for sharing! Aug 9 '19 at 15:20

2. Yes. As you pointed out, there are only $$2^{128}$$ possible strings.
3. Yes. The attacker can generate all $$2^{128}$$ strings and trivially concatenate them with their reflection in each step.
• "The attacker can generate all $2^{128}$ strings and trivially concatenate them with their reflection in each step." Is that true? By my calculation, if everyone in the world generates one million strings every nanosecond, it'll still take over a million years for them to generate all $2^{128}$ strings. Aug 6 '19 at 19:12
• @TannerSwett sure. The point is that using a 256-bit palindromes doesn't gain you anything, you could still carry out the brute force search in $2^{128}$ steps (even if that by itself is unfeasible); the overhead of computing each palindrome is negligible. Aug 6 '19 at 19:29