1

Bitwise Reverse Operation

I have a group of encrypted bytes which I can decrypt with the following function:

        byte b = (byte) (encrypted & 0xFF);
        return b >> 5 & 0x7 | (b & 0x1F) << 3;
    }
      
    0x51 >> 5 & 0x7 | 0x51 & 0x1F << 3 = 0x98
    ^                 ^

At first glance, it precedes a complex operation, so I have decided to separate it into parts.

I need to get the reverse operation. I know how byte operations work; the displacements seem easy to reverse but the AND are not more difficult. Many thought in previous threads that you cannot but would like to know your opinions about it.

I have noticed that the operation (b & 0x1F) only returns numbers of 0x0 and 0x1F and when it reaches 0x20 restarts at 0x0, so successively until 0x39 that returns 0x20 and 0x40 naturally returns 0x0.

Thinking about a possible solution, I have to know of a function "x & y = z" that I know "y" and "z", for example "x + 0x1F = 0x1A" can determine that the original byte could be any of the next {0x1A, 0x3A, 0x5A, 0x7A, 0x9A, 0xBA, 0xDA, 0xFA}, but now the question is how do I select the correct one.

To try to answer this question 0xA1 & 0x1F = 0x1 , assuming that of "x & y = z", we only know y and "z" the possible x would only be {0x1, 0x21, 0x41, 0x61, 0x81, 0xA1, 0xC1, 0xE1}, as you can see the answer is between 8 possible bytes.

Maybe I am posing the problem badly but I cannot build a reverse operation. Can you give me your opinion or explain how to put together an operation of this type?

Community
  • 1
  • 1
Martian Source
  • 33
  • 7
  • Overall it's a rotate, if you look at it like that then it's easy to reverse – harold Oct 12 '19 at 20:17
  • If you do 1110 and 0100 you cannot reverse , from the resulting 0100, if the original was 1110 or 0100, or 0101, it's just impossible. It's not a biunique projection. – Holger Oct 12 '19 at 20:20

2 Answers2

3

To find a reverse operation, you should try looking at what the code is doing on the whole, instead of the individual operations.

The left operand of | says,

Shift b 5 places to the right >> 5 then clear all the bits except the least significant three bits & 0x7. Note that 7 is 111 in binary.

The above gets the most significant 3 bits of b and moves them all the way to the right. 1010 1100 would become 0000 0101.

The right operand of | says,

Clear all the bits except b's least significant 5 bits, and then shift b 3 places to the left. Note that 1F is 0001 1111 in binary.

This gets the least significant 5 bits of b then moves all the way to the left. 1010 1100 would become 0110 0000.

And finally, the | combines the two results together.

So on a high level of abstraction, this code just switches the first 3 and last 5 bits in a byte. 1110 0000 would become 0000 0111.

To reverse this, just switch the first 5, and last 3 bits.

byte b = (byte) (decrypted & 0xFF);
return b >> 3 & 0x1F | (b & 0x7) << 5;

You might want to learn about Bit Masks if you find this answer confusing.

Sweeper
  • 213,210
  • 22
  • 193
  • 313
  • the `& 0x1F` and `& 0x7` are redundant, They are there to null the bits, but a shift should pull `0`s in this case, so this just makes it more complicated. – Dimfred Oct 12 '19 at 21:04
  • 2
    @Dimfred IIRC Java does an arithmetic shift, not a logical shift, so it’s not necessarily 0s. – Sweeper Oct 12 '19 at 21:13
  • 1
    Ah okay, should have added C++ to my comment. But good to know that things work entirely different in java. – Dimfred Oct 12 '19 at 21:45
0

Just compute array of 256 bytes: m_encrypt; byte -> encrypted byte

If it is one-to-one then it is reversable, otherwise it isn't.

Compute decryption array m_decrypt via

for(int i=0; i< 256; i++)
  m_decrypt[m_encrypt[i]] = i;
ALX23z
  • 4,456
  • 1
  • 11
  • 18
  • Naturally, in this way we can easily obtain all possible bytes, but this generates 8 possibilities, for example for a 0x1A byte, there are three 8 possible combinations that operating with 0x1F would generate 0x1A in response: `{ 0x1A, 0x3A, 0x5A, 0x7A, 0x9A, 0xBA, 0xDA, 0xFA }` For example if I do `0x9A & 0x1F = 0x1A` Is the question as if `x & y = z` select the correct one if I only know "y" and "z"? Maybe I am focusing the problem badly and I need to see it from another angle. Maybe I have to see the result of the complete function to deduce some mathematical operation. – Martian Source Oct 12 '19 at 20:36