Published on

Cracking Transformation-Breaking Simple Bitwise Shift Encryption (Python)

Authors

I was doing some picoCTF the other day and stumble open a simple, easy reverse engineering challenge called “Transformation” from 2021 picoCTF. Normally I wouldn't really bother writing about easy challenges, but what sets this apart is that, even though I understood (or so I thought I did) and cracked it, it was not easy for my friend to get it. This is whom I did these challenges with. I had some hard time explaining it to him as well. Mainly because I myself wasn't really understood much behind the concepts, so I did some googling, and it took me a while to come up with a good explanation for him. Eventually I did, so here we are. (We both forgot about ChatGPT, calm down)

Looking at the challenge,

It had a title of “Transformation” and a description as below:

I wonder what this really is... enc ''.join([chr((ord(flag[i]) << 8) + ord(flag[i + 1])) for i in range(0, len(flag), 2)])

the bold enc text there had been linked to here: https://mercury.pic…99f0358d7a1a786/enc, this download a file which contains some weird characters in it, in my case it has this:

灩捯䍔䙻ㄶ形楴獟楮獴㌴摟潦弸彥㜰㍢㐸㙽

Yes, obviously this is our flag but transformed by that algorithm given in the description, oh also they had a hint: “You may find some decoders online”, yeah well hints are cool, but this is an “easy” one so we tried not to use hints. Simply, if we can reverse that algorithm (I just love using that word) we can get our flag out from this gibberish.

Understanding the algorithm used.

''.join([chr((ord(flag[i]) << 8) + ord(flag[i + 1])) for i in range(0, len(flag), 2)])

Let's take a closer look at this code, first what are these functions chr and ord they have used? I am lazy, so let me get you a Stack Overflow answer to that question:

https://stackoverflow.com/questions/57501478/what-does-ordc-and-chrn-do-and-what-does-this-code-output-and-why-i-do-not

or you could just google it, don't be a lazy ass and expect me to write everything. Actually, let's try to re-implement this code. We start with some string, in this case the flag, but we don't know the flag yet. So let's start something that we know "helloworld", yes that will be the flag. We define that first.:

flag = "helloworld"

# let's also define some list to hold the transformed chars
# later we will join this list to make a proper string like the one in enc file
enc = []

If you look at their algorithm, you can see that they are just simply looping through this flag, with a step of 2, so that they take the ord of the first letter and left shift that by 8. Then they add ord of the next character to it and finally convert the resulted number into a character.

for i in range(0, len(flag), 2):
    first_step = ord(flag[i]) << 8) # ex: ord('h') << 8 
    second_step = first_step + ord(flag[i + 1]) # ex: 26624 + ord('e')
    third_step = chr(second_step)
    enc.append(third_step)

enc_flag = ''.join(enc)
print(enc_flag) # output: 桥汬潷潲汤

"""
note that our output is half the length of original, yes because
we can see that we make two characters into one character at second step
"""

We first need to understand what is bitwise operator left shift is, you can do your own research of bitwise operators but for this article I'll keep it simple.

Left Shift (<< n): Moves all bits n places to the left, filling the empty rightmost bits with 0s. This is equivalent to multiplying by 2 to the power of n (2^n).

Right Shift (>> n): Moves all bits n places to the right, discarding the rightmost n bits. The behavior depends on whether it is logical (>>> in some languages like JavaScript) or arithmetic (>>, we are in python and using this).

  • In an arithmetic right shift, the leftmost bit (sign bit in signed integers) is preserved. (again, we use this here)

  • In a logical right shift, zeros are inserted from the left.

Reversing the algorithm

Before doing this, we need to understand how those shifts affecting the process of encrypting (is this the right word?, I don't know) this flag. Because ord results in just a number and chr results in the character that corresponding to a number, so that's not actually a big deal to understand. What's need to understand is the shifts that occurring.

As we know, the algorithm uses a left shift of 8, so this would be like multiplying the number by 2^8, which is 256. So if it was “h” character, we get the ord('h') = 104 then we essentially multiply 104 * 256 = 26624. Then we add the next character e which is ord('e') = 101, 26624 + 101 = 26725.

Note: see in comparison to the first step, the second step of addition is actually pretty small right? Like it was already a big number after the first step, so a simple 100 or so addition wouldn't make much of a difference. (Left shift amplifies a number: x << 8 is equivalent to x * 256, which produces a large number. You will see why this is important as we go on)

What did we just do? We basically packed h and e into a number of 26725, now if we could get these two characters (well the numbers corresponding to these characters) back from this big number, that means we can then successfully reverse the algorithm because that is all this algorithm does after all.

So my first intuition is just reverse the left shift by doing a right shift, so that exactly what I did, 26725 >> 8, which surprisingly gives me back 104. Now, why is this? Why gives me the number corresponding to a one letter while we have two in that, well it turns out that 101 never did any effect in case of right shifting.

(Right shift collapses a number: x >> 8 is equivalent to x//256 in python)

so simply put 101/256 = 0.39453125 so in integer division we forget about the decimal part 101//256 = 0.

Great now we can get half the characters of the flag, but what about the other half? what should we do? Well,

Given (encrypted number) : 26725

Get the first character by doing right shift: 26725 >> 8 = 104

(remember our number is build like this: 26624 + 101 = 26725, where 104 * 256 = 26624)

We do a left shift on that again so we can get the bigger number the original algorithm produced at its first step : 104 << 8 = 26624

Now just subtract it from the given number (encrypted number) : 26725 - 26624 = 101

Boom! We cracked the code, let's put this into a function that can actually get the characters and hopefully recover the flag for us.

def crack_enc(enc):
    text = [] # we fist init an list so keep track of chars
    for i in range(0, len(enc)): # start running though the chars using indexes
        
        ord_of_the_current = ord(enc[i]) # we get the current ord, ex: h->104
        
        # right shift to get the first part,
        # ex: 26725 >> 8 = 104
        part_1 = (ord_of_the_current >> 8)

        # left shift the above to get the big number which was originally used
        # by that algorithm to encrypt essentiallly encrypt the smaller number
        # ex: 104 << 8 = 26624
        enc_part_1 = part_1 << 8

        # subtract the enc_part_1 from ord_of_the_current to get the little number
        # that they hide which corresponding to second character ( second part )
        # ex: 26725 - 26624 = 101
        part_2 = ord_of_the_current - enc_part_1
        
        # convert the part_1 & part_2 number back to characters
        # ex: 104 -> h and 101 => e
        # and append them to the text list
        chr_part_1 = chr(part_1)
        text.append(chr_part_1)
        chr_part_2 = chr(part_2)
        text.append(chr_part_2)

    return ''.join(text) # finally we join them and return

Finally, use the decryptor to get the flag.

enc = "桥汬潷潲汤" # for helloworld
print(crack_enc(enc)) # this prints helloworld

print(crack_enc("灩捯䍔䙻ㄶ形楴獟楮獴㌴摟潦弸彥㜰㍢㐸㙽"))
# output: picoCTF{16_bits_inst34d_of_8_e703b486}

# Oh and yes, the flag speaks for itself!

Thanks for checking out (instead of using ChatGPT haha), hope you learned something :)