attack.ipynb

from time import time

t0 = time()


class Generators:
    # For a (faster) proof of concept for b != 0, uncomment every line ending with `# Quick check` and comment the line just above.
    # It's exactly the same concept, but the generator now only has 40 bits of entropy (so, only 4 hidden bits instead of 27).

    m = 2**64  # seeds of 64 bits
    #m = 2**40  # Quick check
    
    mask = m - 1  # int & mask <=> int % m when m is a power of 2
    int32_mask = 2**32 - 1

    padding = 27
    #padding = 3  # Quick check
    
    
    def __init__(self, a, b, seed):
        self.a = a & self.mask
        self.b = b & self.mask
        self.seed = seed & self.mask
        
    
    # Methods can't be static because of the constants
    def LCG(self):
        r = self.seed
        self.seed = (self.a * self.seed + self.b) & self.mask
        
        return r 


    def T_LCG(self):
        """ Truncated LCG """
        return self.LCG() >> self.padding


    def PCG_from_seed(self, seed):        
        xorshift = (((seed >> 18).__xor__(seed)) >> 27) & self.int32_mask
        #xorshift = (((seed >> 18).__xor__(seed)) >> 3) & self.int32_mask  # Quick check
        rot = seed >> 59
        #rot = seed >> 35  # Quick check
                
        return (xorshift >> rot) | ((xorshift << (32 - rot)) & self.int32_mask)


    def PCG(self):
        return self.PCG_from_seed(self.LCG())


class Utils:

    @staticmethod
    def bits(n, size=None):
        """
        Given an integer, outputs the list of its bits, most significant bit first.
        If a size of bits N is given, ensures that the int fits into N bits, and pads the list with leading 0s.
        """
        if size is not None:
            assert 2**size > n

        b = []
        while n:
            b = [n & 1] + b
            n >>= 1

        if size is not None:
            return [0] * (size - len(b)) + b

        return b


    @staticmethod
    def bits_to_dec(bin_list):
        b = 1
        s = 0
        for k in bin_list[::-1]:
            s += b * k
            b = b * 2
            
        return s


    @staticmethod
    def invert_PCG(number, rot):
        """Returns a 37-bits integer, corresponding to `number` before xorshift + rotation"""
        result_array = [None] * 37
        result_array[0:5] = Utils.bits(rot, 5)

        number_array = Utils.bits(number, 32)

        # The sixth bit (result[5]) is at position 1 + rot (number_array[rot]), and so on
        for i in range(5, 18):
            result_array[i] = number_array[(rot + (i - 5)) & 0b11111]

        # Same as before, but now we have to XOR with the bit i-18
        for i in range(18, 37):
            result_array[i] = number_array[(rot + (i - 5)) & 0b11111].__xor__(result_array[i - 18])

        return Utils.bits_to_dec(result_array)


    @staticmethod
    def create_L_matrix(m, a, size=3):
        L = [[0 for _ in xrange(size)] for _ in xrange(size)]

        L[0][0] = m
        for i in range(1, size):
            L[i][0] = a ** i
            L[i][i] = -1

        return matrix(L)

    
    @staticmethod
    def LLL(L):
        return L.LLL()


class Attack:
    """
    The attack uses, in the case of a truncated LCG without b (x_{i+1} = a * x_i mod m), three consecutive numbers
    """
    def __init__(self, gen):
        self.gen = gen

    def bruteforce_for_diff(self, d, outputs):
        """
        We have exactly solved d_i = x_{i+1} - x_i, but we do not know the exact value of x_0
        (x_0 == y_0 + z_0, we only know y_0). We bruteforce on the 2**27 possible values z_0 can have, and
        computing b from x_0 and x_1 == d_0 + x_0, we look for the probably only value of z_0 such that
        a * (y_1 + z_1) + b % m == d_1 + (y_1 + z_1) (== x_2)

        Returns the first seed (x_0)
        """
        for z in xrange(2**self.gen.padding):
            x_0 = (outputs[0] << self.gen.padding) + z
            x_1 = (d[0] + x_0) & self.gen.mask
            computed_b = (x_1 - self.gen.a * x_0) & self.gen.mask

            hypothetical_x_2 = (self.gen.a * x_1 + computed_b) & self.gen.mask
            
            real_x_2 = (d[1] + x_1) & self.gen.mask
            
            if hypothetical_x_2 == real_x_2:
                #print 'Secret found! Secret for first seed: {}, giving initial seed: {}'.format(z, x_0)
                yield (x_0, computed_b)
        
        yield (None, None)


    def solve_tlcg(self, outputs):
        """
        Using FHKL algorithm to break a truncated LCG with b = 0.
        See 'Reconstructing Truncated Integer Variables Satisfying Linear Congruences',
        by Frieze, Hastad, Kannan, Lagarias and Shamir

        we pose x = y + z, with z < 2**27 and y % 2**27 == 0. We know y, we want to find z
        """
        assert len(outputs) >= 3
        self.L_p = Utils.LLL(Utils.create_L_matrix(self.gen.m, self.gen.a, len(outputs)))

        y = vector([(2**self.gen.padding * x) & self.gen.mask for x in outputs])
        reduced_outputs = self.L_p * y

        c_prime = vector([round(e / self.gen.m) * self.gen.m - e for e in reduced_outputs])
        z = vector(ZZ, self.L_p.solve_right(c_prime))  # Converting z coords to the integer ring (rational otherwise)
        
        return y + z


    def attack_tlcg(self, outputs, output_to_predict):
        assert len(outputs) >= 3
        
        computed_seeds = self.solve_tlcg(outputs)

        predicted_seed = ((self.gen.a * computed_seeds[-1]) & self.gen.mask)
        predicted_generator = Generators(self.gen.a, 0, predicted_seed)

        if predicted_generator.T_LCG() == output_to_predict:
            return predicted_generator


    def solve_tlcg_with_b(self, outputs):
        """
        If our LCG is of the form ax + b, then by posing d_i = x_{i+1} - x_i
        we get d_{i+1} = a * d_i, that we can solve.
        """
        assert len(outputs) >= 4
        diffs = [outputs[i + 1] - outputs[i] for i in range(len(outputs) - 1)]
        
        computed_seeds_diff = self.solve_tlcg(diffs)
        bruteforce = self.bruteforce_for_diff(computed_seeds_diff, outputs)
        
        for x_0, computed_b in bruteforce:

            # This cannot happen when we attack a T_LCG. On the contrary, on a PCG, when bruteforcing on 32^3 values,
            # It is most probable that many triplets cannot be the result of a T_LCG with given a.
            if x_0 is None:
                raise ValueError()

            computed_seeds = [x_0]

            # Reconstruct all the seeds
            for diff in computed_seeds_diff:
                computed_seeds.append((diff + computed_seeds[-1]) & self.gen.mask)

            yield computed_seeds, computed_b

    
    def attack_tlcg_with_b(self, outputs, output_to_predict):
        assert len(outputs) >= 4
        
        predicted_generator = Generators(self.gen.a, 0, 0)  # Initializing with dummy values
        solver = self.solve_tlcg_with_b(outputs)
        
        for computed_seeds, computed_b in solver:
            predicted_seed = ((self.gen.a * computed_seeds[-1] + computed_b) & self.gen.mask)
            predicted_generator = Generators(self.gen.a, computed_b, predicted_seed)
            
            if predicted_generator.T_LCG() == output_to_predict:
                return predicted_generator


    def attack_PCG(self, outputs, output_to_predict):
        # We only use 3 outputs, as more would add too much complexity.
        assert len(outputs) == 3
        for i in range(32):
            possibility_0 = Utils.invert_PCG(outputs[0], i)
            for j in range(32):
                possibility_1 = Utils.invert_PCG(outputs[1], j)
                for k in range(32):
                    possibility_2 = Utils.invert_PCG(outputs[2], k)
                    
                    computed_seeds = self.solve_tlcg([possibility_0, possibility_1, possibility_2])
                    predicted_seed = ((self.gen.a * computed_seeds[2]) & self.gen.mask)
                    predicted_generator = Generators(self.gen.a, 0, predicted_seed)
                    
                    # Compare prediction to a number not seen before
                    if predicted_generator.PCG() == output_to_predict:
                        return predicted_generator


    def attack_PCG_with_b(self, outputs, output_to_predict):
        assert len(outputs) == 4
        for i in range(32):
            #print i
            possibility_0 = Utils.invert_PCG(outputs[0], i)

            for j in range(32):
                possibility_1 = Utils.invert_PCG(outputs[1], j)

                for k in range(32):
                    possibility_2 = Utils.invert_PCG(outputs[2], k)

                    for l in range(32):
                        possibility_3 = Utils.invert_PCG(outputs[3], l)

                        try:
                            solver = self.solve_tlcg_with_b([possibility_0, possibility_1, possibility_2, possibility_3])

                            for computed_seeds, computed_b in solver:
                                predicted_seed = ((self.gen.a * computed_seeds[3] + computed_b) & self.gen.mask)
                                predicted_generator = Generators(self.gen.a, computed_b, predicted_seed)

                                if predicted_generator.PCG() == output_to_predict:
                                    return predicted_generator
                            
                        except ValueError:
                            pass


### Creating inputs

gen = Generators(a=234583, b=23475435433, seed=6464645678443)
attack = Attack(gen)
outputs = [0] * 5

################
# T_LCG attack #
################

for i in range(len(outputs)):
    outputs[i] = gen.T_LCG()

predicted_gen = attack.attack_tlcg_with_b(outputs[:4], outputs[4])
print 'Predictions may be a bit different from generator'
print 'Predictions: \t', predicted_gen.T_LCG(), predicted_gen.T_LCG(), predicted_gen.T_LCG(), predicted_gen.T_LCG()
print 'Generator: \t', gen.T_LCG(), gen.T_LCG(), gen.T_LCG(), gen.T_LCG()


##############
# PCG attack #
##############

#for i in range(len(outputs)):
#    outputs[i] = gen.PCG()
#predicted_gen = attack.attack_PCG_with_b(outputs[:4], outputs[4])
#print
#print 'Predictions: \t', predicted_gen.PCG(), predicted_gen.PCG(), predicted_gen.PCG(), predicted_gen.PCG()
#print 'Generator: \t', gen.PCG(), gen.PCG(), gen.PCG(), gen.PCG()


print 'Done!'
print time() - t0