2
$\begingroup$

[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

Improve this question
$\endgroup$
4
  • $\begingroup$ "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? $\endgroup$
    – Acccumulation
    Aug 6 '19 at 21:25
  • $\begingroup$ 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). $\endgroup$
    – Steven Hatzakis
    Aug 9 '19 at 13:22
  • $\begingroup$ 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. $\endgroup$
    – Acccumulation
    Aug 9 '19 at 14:33
  • $\begingroup$ 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! $\endgroup$
    – Steven Hatzakis
    Aug 9 '19 at 15:20
10
$\begingroup$

The xor of two random strings is a random string, so you're basically generating a 128-bit random string from a 256-bit random string.

  1. Yes, it reduces security compared to a pure 256-bit random string.
  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.
  4. No, both have 128-bit security against brute force attacks.
  5. No, as mentioned there is no security gain in using palindromes, which implies that there is no advantage at all in use palindromes. For example, a 256-bit palindrome can be stored "compressed" in 128 bits, but it still provides only 128 bits of security. You could simply use a normal 128-bit key instead, which fits in the same size, has the same security, and is a lot simpler.
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Hi @Conrado, great answers, could you expand more on number 5 as I was asking not just for potential "security" advantages but maybe other advantages such as convenience where there could be a trade-off (i.e. reduces string size/compression)? Thank you. $\endgroup$
    – Steven Hatzakis
    Aug 6 '19 at 12:47
  • 1
    $\begingroup$ @StevenHatzakis sure, I've expanded it $\endgroup$
    – Conrado
    Aug 6 '19 at 13:20
  • $\begingroup$ "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. $\endgroup$
    – Tanner Swett
    Aug 6 '19 at 19:12
  • 2
    $\begingroup$ @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. $\endgroup$
    – Conrado
    Aug 6 '19 at 19:29

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.