Cryptography Puzzle

Hackerspace Computer Science
#1

There is a algorithm that mixes bits for some hashes.

For example, using 32 bit integers
S = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)

Right Rotate, rotates the bits along the 32 bit area. It is much like a right shift but the bits appear on the other side such that rotating by a multiple of 32 will result in no change.
Xor, exclusive-ors the 32 bit result of the right rotates

The puzzle is to find ‘e’ if you have ‘S’

#2

I think that will have to be brute forced by trying all possible values of e. For 32 bits, it should not take more than a few hours on a modern machine. There are probably some values of S for which no e exists.

1 Like
#3

Actually, there is an easier and faster way. A rainbow table would work, however.

It would seem that way, but I believe it is a one to one relationship.

#4

you can write equations for the bits of S of the form S_i = e_j ^ e_k ^ e_m

using properties of xor these can be rewritten as e_j = S_i ^ e_m ^ e_k.

now you can substitute these expressions for e_m and e_k and repeat - taking advantage of the associativity and commutivity of xor and the fact that a ^ a = 0 and b ^ 0 = b, you will eventually reach an equation for each bit of e involving only bits of S.

the solution: e = (S ror 26) ^ (S ror 2) ^ (S ror 22) ^ (S ror 5) ^ (S ror 24) ^ (S ror 29) ^ (S ror 11) ^ (S ror 7) ^ (S ror 18) ^ (S ror 21) ^ (S ror 3) ^ (S ror 12) ^ (S ror 30) ^ (S ror 13) ^ (S ror 27) ^ (S ror 9) ^ (S ror 23)

someone who knows something about abstract algebra can probably explain how you could generate this sequence directly from the definition of S - I used python.

3 Likes
#5

Nice … great answer!

I found another way …

If you feed in ‘S’ in place of ‘e’ repeatedly, it will wrap around to ‘e’. It will wrap around either at 15 or 31 times depending on the numbers. In this case 15 times

1 Like
#6

@Bill - I see there are a couple of probably brilliant answers but I like brute force. Why don’t you make your computer work on it while you sleep and report back on how long it takes!

It has to be trivial compared to putting Python on a 6502.

1 Like
#7

I found this fascinating, in the same way that I find reading the results of a cricket match fascinating. That is, how can it be that I am able read the individual words, and yet have no idea what they mean as a group. :slight_smile:

3 Likes
#8

It must be encrypted! Right?

1 Like
#9

Of course I think in code so here’s my shot:

class CryptoChallenge():
    
    def __init__(self, input=str()):
        self.input = list(input)
        self.encrypt()
        
    def rotateRight(self, iterations=1):

        for idx in range(0, iterations):
            self.input = ([self.input[-1]] + self.input[0:-1])

        return self.input

    def rotateLeft(self, iterations=1):
         pass
    
    def encrypt(self):
        self._store = [
            self.rotateRight(6),
            self.rotateRight(11),
            self.rotateRight(25)
        ]

        return set(self._store[0]) ^ set(self._store[1]) ^ set(self._store[-1])
        
    @property    
    def message(self):
        return "".join(str(s) for s in self.encrypt())
        
    @message.setter
    def message(self, value):
        self.input = list(value)
        
    @message.deleter
    def message(self):
        del self.input

def main():
    disk = CryptoChallenge("Hello, World")
    print disk.message

if __name__ is '__main__':
    main()
#10

This is the code I threw together the first day to see what the hashes looked like:

def hash(seed):
    seed = seed << 32 | seed
    return ((seed >> 6) ^ (seed >> 11) ^ (seed >> 25)) & (0xffffffff)

while True:
    result = hash(int(input('value? ')))
    print(result, hex(result))

Is assembly language the only language with direct support for rotation?

Does the PDP-11 not have rotates in its instruction set since C gives access to everything else it can do?

1 Like
#11

It turns out the PDP-11 does have rotate instructions:

The designers of C must have run out of characters on their keyboards…

Maybe they should have used <@ and >@ for rotate left and right…

#12

Normally right rotate is >>> and left rotate is <<<

Here is a c implementation

uint32_t ror32(uint32_t v, unsigned int bits) {
    return (v >> bits) | (v << (32 - bits));
}
#13

That was not in the original language specification. When was it added?

#14

I’m sorry … I’m just talking in terms of symbols that people use to represent it. C doesn’t have one for it.

#15

This is not a complete hash function. It is only a small portion of one.
It was taken from SHA-256

The complete pseudo code is here … https://en.wikipedia.org/wiki/SHA-2#Pseudocode

#16

And the 32-bit rotate left complement:

uint32_t rol32(uint32_t v, unsigned int bits) { 
   return (v << bits) | (v >> (32 - bits)); }