LSFR

from z3 import *

register_size = 20

def Z3LFSR(taps, register)
	#Get the last bit from the register
	bit = Extract(register_size-1, register_size-1, register)

	#Init the new bit to be used
	new_bit = BitVec(1, 1)

	#Xor the tapped variables
	for i in range(register_size):
		new_bit = new_bit ^ (Extract(i, i, taps) & Extract(i, i, register))

	#Shift the variables by one
	new_register = Concat(Extract(register_size - 2, 0, register), new_bit)

	return bit, new_register

def Solve(cipher_iv, known_bytes, data, enc_hash):
	taps = []
	register = []

	cipher_iv_stream = BitStream(cipher_iv)

	#Setup Register and Taps
	for x in range(8):
		taps.append(BitVec("T{}".format(x), register_size))
		register.append(BitVecVal(cipher_iv_stream.get_bits(register_size), register_size))
	

	for i in range(20):
		for j in range(8):
			new_bit, new_register = Z3LFSR(taps[i], register[i])
			register[i] = new_bit
	
	#Get Keystream Bytes
	for j in range(20, len(known_bytes)):
		bits = []
		for i in range(8)
			new_bit, new_register = Z3LFSR(taps[i], register[i])
			register[i] = new_bit
			bits.append(new_bit)

		keystream_byte_test = Concat(bits[7], bits[6], bits[5], bits[4], bits[3], bits[2], bits[1], bits[0])
		keystream_byte = known_bytes[j] ^ data[j]
		s.add(keystream_byte_valid == keystream_byte)


	while True:
		ch = s.check()
		print ch
		if ch.r == -1:
			return

		model = s.model()

		poly = []
		for i in range(8):
			poly.append(model[taps[i]].as_long())

		c = SolveLFSRCipher(poly, cipher_iv)
		dec_data = c.crypt(data)
		dec_hash = c.crypt(enc_hash)

		dec_data_hash = hashlib.sha256(dec_data).digest()

		if dec_hash == dec_data_hash:
			print("YEAH!")
			with open("flag.png", "wb") as f:
				f.write(dec_data)
			return

	current_poly = Concat(
	  model[taps[7]], model[taps[6]], model[taps[5]], model[taps[4]], 
	  model[taps[3]], model[taps[2]], model[taps[1]], model[taps[0]]
	)

	s.add(current_poly != all_C)


if __name__ == "__main__":
	known_bytes = [0x89, 0x50, 0x4e, 0x47, 0x0d, 0x0a, 0x1a, 0x0a,
				   0x00, 0x00, 0x00, 0x0d, 0x49, 0x48, 0x44, 0x52,
				   0x00, 0x00, 0x02, 0x08,
				   #Height
				   0x00, 0x00, None, None,
				   #Bit Depth (Might be different)
				   0x08,
				   #Color Type (Might be different)
				   0x02,
				   #Compression Method
				   0x00,
				   #Filter Method
				   0x00,
				   #Interlaced
				   0x00,
				   #CheckSum
				   None, None, None, None,
				   #Possible new tag 
				   None, None, None, None,
				   ]

	z = zipfile.ZipFile("flag.zip")
	d = z.read("flag.png")
	key_iv = d[:20]
	cipher_iv = d[20:40]
	enc_hash = d[-32:]
	data = d[40:-32]

	Solve(cipher_iv, known_bytes, data, enc_hash)

#!/usr/bin/env python3

from functools import reduce
from operator import xor

class LFSR():
	def __init__(self, fill, taps):
		#The Register is the inital state of the Register
		if type(fill) != list:
			temp = int.from_bytes(fill, byteorder="big")
			fill = [int(x) for x in list('{0:0b}'.format(temp))]
		self.register = fill
		self.taps = taps

	def step(self):
		#XOR the elements in the register 
		tapped_bits = [self.register[t] for t in taps]
		new_bit = reduce(xor, tapped_bits)
		
		#Remove the first element of the array. This is shifts all of the elements in the register to the left
		del self.register[0]

		#This adds the new bit to the end of the register
		self.register.append(new_bit)

		#Return the new_bit that was added to the array
		return self.register[-1]
	
	def rand(self, bit_size):
		'''Generate a k-bit pseudo random number using the register.'''
		num = 0
		for _ in range(bit_size):      
			num = (num << 2) | self.step()
		return num

	def __str__(self):
		return "<LFSR: {}, taps: {}>".format(''.join(map(str,self.register)), self.taps)

if __name__ == '__main__':
	register = LFSR(fill=[0,1,1,0,1,0,0,0,0,1,0], taps=[8])
	print(register.rand(8))

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#  A5.py
#  
#  Author: overxfl0w13
#  

def header():
	print """
*******************************
 _______  _______         __   
(  ___  )(  ____ \     /\/  \  
| (   ) || (    \/    / /\/) ) 
| (___) || (____     / /   | | 
|  ___  |(_____ \   / /    | | 
| (   ) |      ) ) / /     | | 
| )   ( |/\____) )/ /    __) (_
|/     \|\______/ \/     \____/
*******************************\n\n\n
"""                            


## Register ##
class LFSR:
	
	def __init__(self,i,length,clockingBit,tappedBits): self.i,self.length,self.register,self.clockingBit,self.tappedBits = i,length,[0]*length,clockingBit,tappedBits
	
	def _getID(self):	  					return self.i
	def _getRegister(self): 				return self.register
	def _getBit(self,i):				    return self.register[i]
	def _getLength(self): 					return self.length
	def _getClockingBit(self): 				return self.register[self.clockingBit]
	def _getTappedBits(self):  				return self.tappedBits
	
	def _setID(self,i):	  					self.i = i
	def _setLength(self,length): 			self.length = length
	def _setRegister(self,register):        self.register = register
	def _setClockingBit(self,clockingBit): 	self.clockingBit = clockingBit
	def _setTappedBits(self,tappedBits):  	self.tappedBits = tappedBits
	
	
## Utils ##
def xor(x,y): return 0 if x==y else 1

def stepOne(): return (LFSR(1,19,8,[13,16,17,18]),LFSR(2,22,10,[20,21]),LFSR(3,23,10,[7,20,21,22]))

def stepTwo(lfsrOne,lfsrTwo,lfsrThree,sessionKey):
	for bit in sessionKey:
		bit = int(bit)
		# LFSRONE #
		nMsb = xor(xor(xor(xor(lfsrOne._getBit(13),lfsrOne._getBit(16)),lfsrOne._getBit(17)),lfsrOne._getBit(18)),bit)	
		lfsrOne._setRegister([nMsb]+lfsrOne._getRegister()[0:lfsrOne._getLength()-1])
		# LFSRTWO #
		nMsb = xor(xor(lfsrTwo._getBit(20),lfsrTwo._getBit(21)),bit)
		lfsrTwo._setRegister([nMsb]+lfsrTwo._getRegister()[0:lfsrTwo._getLength()-1])
		# LFSRTHREE #
		nMsb = xor(xor(xor(xor(lfsrThree._getBit(7),lfsrThree._getBit(20)),lfsrThree._getBit(21)),lfsrThree._getBit(22)),bit)
		lfsrThree._setRegister([nMsb]+lfsrThree._getRegister()[0:lfsrThree._getLength()-1])
		

def stepFour(lfsrOne,lfsrTwo,lfsrThree):
	for i in xrange(100):
		clockingBits = [lfsrOne._getClockingBit(),lfsrTwo._getClockingBit(),lfsrThree._getClockingBit()]
		oneCount,zeroCount = clockingBits.count(1),clockingBits.count(0)
		majorityBit  = 1 if max(oneCount,zeroCount)==oneCount else 0
		# LFSRONE #
		if lfsrOne._getClockingBit()==majorityBit:
			nMsb = xor(xor(xor(lfsrOne._getBit(13),lfsrOne._getBit(16)),lfsrOne._getBit(17)),lfsrOne._getBit(18))
			lfsrOne._setRegister([nMsb]+lfsrOne._getRegister()[0:lfsrOne._getLength()-1])	
		# LFSRTWO #
		if lfsrTwo._getClockingBit()==majorityBit:
			nMsb = xor(lfsrTwo._getBit(20),lfsrTwo._getBit(21))
			lfsrTwo._setRegister([nMsb]+lfsrTwo._getRegister()[0:lfsrTwo._getLength()-1])
		# LFSRTHREE #
		if lfsrThree._getClockingBit()==majorityBit:
			nMsb = xor(xor(xor(lfsrThree._getBit(7),lfsrThree._getBit(20)),lfsrThree._getBit(21)),lfsrThree._getBit(22))
			lfsrThree._setRegister([nMsb]+lfsrThree._getRegister()[0:lfsrThree._getLength()-1])

def stepFive(lfsr1,lfsr2,lfsr3):
	keyStream = ""
	keyStream += str(lfsrOne._getBit(lfsrOne._getLength()-1)^lfsrTwo._getBit(lfsrTwo._getLength()-1)^lfsrThree._getBit(22))	
	for i in xrange(227):
		clockingBits = [lfsrOne._getClockingBit(),lfsrTwo._getClockingBit(),lfsrThree._getClockingBit()]
		oneCount,zeroCount = clockingBits.count(1),clockingBits.count(0)
		majorityBit  = 1 if max(oneCount,zeroCount)==oneCount else 0
		# LFSRONE #
		if lfsrOne._getClockingBit()==majorityBit:
			nMsb = xor(xor(xor(lfsrOne._getBit(13),lfsrOne._getBit(16)),lfsrOne._getBit(17)),lfsrOne._getBit(18))
			lfsrOne._setRegister([nMsb]+lfsrOne._getRegister()[0:lfsrOne._getLength()-1])	
		# LFSRTWO #
		if lfsrTwo._getClockingBit()==majorityBit:
			nMsb = xor(lfsrTwo._getBit(20),lfsrTwo._getBit(21))
			lfsrTwo._setRegister([nMsb]+lfsrTwo._getRegister()[0:lfsrTwo._getLength()-1])
		# LFSRTHREE #
		if lfsrThree._getClockingBit()==majorityBit:
			nMsb = xor(xor(xor(lfsrThree._getBit(7),lfsrThree._getBit(20)),lfsrThree._getBit(21)),lfsrThree._getBit(22))
			lfsrThree._setRegister([nMsb]+lfsrThree._getRegister()[0:lfsrThree._getLength()-1])
		keyStream += str(lfsrOne._getBit(lfsrOne._getLength()-1)^lfsrTwo._getBit(lfsrTwo._getLength()-1)^lfsrThree._getBit(22))	
	return keyStream

def stepSix(plainText,keyStream): return "".join([str(xor(keyStream[i%228],plainText[i])) for i in xrange(len(plainText))])

def padding228(plainText):
	while len(plainText)%228!=0: plainText += "0"
	return plainText
	
if __name__ == "__main__":
	header()
	plainText = padding228(raw_input("Msg> "))
	# Step One #
	print "\nInitializing LFSR..."
	lfsrs = stepOne()
	lfsrOne,lfsrTwo,lfsrThree = lfsrs[0],lfsrs[1],lfsrs[2]
	# Step Two #
	sessionKey = padding228(raw_input("\nSession key> "))
	stepTwo(lfsrOne,lfsrTwo,lfsrThree,sessionKey)
	print "\nLFSR after step two:"
	print lfsrOne._getRegister()
	print lfsrTwo._getRegister()
	print lfsrThree._getRegister()
	print "\n\n"
	# Step Three #
	print "LFSR after step three:"
	print lfsrOne._getRegister()
	print lfsrTwo._getRegister()
	print lfsrThree._getRegister()
	print "\n\n"
	# Step Four  #
	print "LFSR after step four:"
	stepFour(lfsrOne,lfsrTwo,lfsrThree)
	print lfsrOne._getRegister()
	print lfsrTwo._getRegister()
	print lfsrThree._getRegister()
	print "\n\n"
	# Step Five #
	print "KeyStream 228b generated:"
	keyStream  = stepFive(lfsrOne,lfsrTwo,lfsrThree)
	print keyStream
	# Step Six  #
	print "\nCipher text:"
	cipherText = stepSix(plainText,keyStream)
	print cipherText,"\n\n"

#include <stdio.h>
 
 
/* Masks for the shift registers */
#define R1MASK  0x07FFFF /* 19 bits, numbered 0..18 */
#define R2MASK  0x3FFFFF /* 22 bits, numbered 0..21 */
#define R3MASK  0x7FFFFF /* 23 bits, numbered 0..22 */
#define R4MASK  0x01FFFF /* 17 bits, numbered 0..16 */
 
 
/* A bit of R4 that controls each of the shift registers */
#define R4TAP1  0x000400 /* bit 10 */
#define R4TAP2  0x000008 /* bit 3 */
#define R4TAP3  0x000080 /* bit 7 */
 
 
 
/* Feedback taps, for clocking the shift registers.
 * These correspond to the primitive polynomials
 * x^19 + x^18 + x^17 + x^14 + 1, x^22 + x^21 + 1,
 * x^23 + x^22 + x^21 + x^8 + 1, and x^16 + x^11 + 1. */
 
 
#define R1TAPS  0x072000 /* bits 18,17,16,13 */
#define R2TAPS  0x300000 /* bits 21,20 */
#define R3TAPS  0x700080 /* bits 22,21,20,7 */
#define R4TAPS  0x010800 /* bits 16,11 */
 
 
typedef unsigned char byte;
typedef unsigned long word;
typedef word bit;
 
 
/* Calculate the parity of a 32-bit word, i.e. the sum of its bits modulo 2
*/
bit parity(word x) {
    x ^= x>>16;
    x ^= x>>8;
    x ^= x>>4;
    x ^= x>>2;
    x ^= x>>1;
    return x&1;
}
 
 
/* Clock one shift register.  For A5/2, when the last bit of the frame
 * is loaded in, one particular bit of each register is forced to '1';
 * that bit is passed in as the last argument. */
 
    word clockone(word reg, word mask, word taps, word loaded_bit) {
 
        word t = reg & taps;
        reg = (reg << 1) & mask;
        reg |= parity(t);
        reg |= loaded_bit;
        return reg;
    }
 
 
/* The three shift registers.  */
    word R1, R2, R3;
    word R4;
 
/* Return 1 iff at least two of the parameter words are non-zero. */
    bit majority(word w1, word w2, word w3) {
        int sum = (w1 != 0) + (w2 != 0) + (w3 != 0);
        if (sum >= 2)
            return 1;
        else
            return 0;
    }
 
 
/* For A5/2,
 * use particular bits of R4 instead of the middle bits.  Also, for A5/2,
 * always clock R4.
 * If allP == 1, clock all three of R1,R2,R3, ignoring their middle bits.
 * This is only used for key setup.  If loaded == 1, then this is the last
 * bit of the frame number, and if we're doing A5/2, we have to set a
 * particular bit in each of the four registers. */
    void clock(int allP, int loaded) {
 
        bit maj = majority(R4&R4TAP1, R4&R4TAP2, R4&R4TAP3);
        if (allP || (((R4&R4TAP1)!=0) == maj))
                R1 = clockone(R1, R1MASK, R1TAPS, loaded<<15);
        if (allP || (((R4&R4TAP2)!=0) == maj))
                R2 = clockone(R2, R2MASK, R2TAPS, loaded<<16);
        if (allP || (((R4&R4TAP3)!=0) == maj))
                R3 = clockone(R3, R3MASK, R3TAPS, loaded<<18);
        R4 = clockone(R4, R4MASK, R4TAPS, loaded<<10);
 
    }
 
 
/* Generate an output bit from the current state.
 * You grab a bit from each register via the output generation taps;
 * then you XOR the resulting three bits.  For A5/2, in addition to
 * the top bit of each of R1,R2,R3, also XOR in a majority function
 * of three particular bits of the register (one of them complemented)
 * to make it non-linear.  Also, for A5/2, delay the output by one
 * clock cycle for some reason. */
    bit getbit() {
        bit topbits = (((R1 >> 18) ^ (R2 >> 21) ^ (R3 >> 22)) & 0x01);
 
        static bit delaybit = 0;
        bit nowbit = delaybit;
        delaybit = (
            topbits
            ^ majority(R1&0x8000, (~R1)&0x4000, R1&0x1000)
            ^ majority((~R2)&0x10000, R2&0x2000, R2&0x200)
            ^ majority(R3&0x40000, R3&0x10000, (~R3)&0x2000)
            );
        return nowbit;
    }
 
 
/* Do the A5 key setup.  This routine accepts a 64-bit key and
 * a 22-bit frame number. */
    void keysetup(byte key[8], word frame) {
        int i;
        bit keybit, framebit;
 
 
        /* Zero out the shift registers. */
        R1 = R2 = R3 = 0;
        R4 = 0;
 
 
        /* Load the key into the shift registers,
         * LSB of first byte of key array first,
         * clocking each register once for every
         * key bit loaded.  (The usual clock
         * control rule is temporarily disabled.) */
        for (i=0; i<64; i++) {
            clock(1,0); /* always clock */
            keybit = (key[i/8] >> (i&7)) & 1; /* The i-th bit of the key */
            R1 ^= keybit; R2 ^= keybit; R3 ^= keybit;
            R4 ^= keybit;
 
        }
 
 
        /* For A5/2, signal when the last bit is being clocked in. */
        for (i=0; i<22; i++) {
            clock(1,i==21); /* always clock */
            framebit = (frame >> i) & 1; /* The i-th bit of the frame # */
            R1 ^= framebit; R2 ^= framebit; R3 ^= framebit;
            R4 ^= framebit;
        }
 
 
        /* Run the shift registers for 100 clocks
         * to mix the keying material and frame number
         * together with output generation disabled,
         * so that there is sufficient avalanche.
         * We re-enable the majority-based clock control
         * rule from now on. */
        for (i=0; i<100; i++) {
            clock(0,0);
        }
        /* For A5/2, we have to load the delayed output bit.  This does _not_
         * change the state of the registers.  */
        getbit();
 
 
        /* Now the key is properly set up. */
    }
 
 
/* Generate output.  We generate 228 bits of
 * keystream output.  The first 114 bits is for
 * the A->B frame; the next 114 bits is for the
 * B->A frame.  You allocate a 15-byte buffer
 * for each direction, and this function fills
 * it in. */
    void run(byte AtoBkeystream[], byte BtoAkeystream[]) {
        int i;
 
 
        /* Zero out the output buffers. */
        for (i=0; i<=113/8; i++)
            AtoBkeystream[i] = BtoAkeystream[i] = 0;
 
 
        /* Generate 114 bits of keystream for the
         * A->B direction.  Store it, MSB first. */
        for (i=0; i<114; i++) {
            clock(0,0);
            AtoBkeystream[i/8] |= getbit() << (7-(i&7));
        }
 
 
        /* Generate 114 bits of keystream for the
         * B->A direction.  Store it, MSB first. */
        for (i=0; i<114; i++) {
            clock(0,0);
            BtoAkeystream[i/8] |= getbit() << (7-(i&7));
        }
    }
 
 
/* Test the code by comparing it against
 * a known-good test vector. */
    void test() {
 
        byte key[8] = {0x00, 0xfc, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
        word frame = 0x21;
        byte goodAtoB[15] = { 0xf4, 0x51, 0x2c, 0xac, 0x13, 0x59, 0x37,
                              0x64, 0x46, 0x0b, 0x72, 0x2d, 0xad, 0xd5, 0x00 };
        byte goodBtoA[15] = { 0x48, 0x00, 0xd4, 0x32, 0x8e, 0x16, 0xa1,
                              0x4d, 0xcd, 0x7b, 0x97, 0x22, 0x26, 0x51, 0x00 };
 
        byte AtoB[15], BtoA[15];
        int i, failed=0;
 
 
        keysetup(key, frame);
        run(AtoB, BtoA);
 
 
        /* Compare against the test vector. */
        for (i=0; i<15; i++)
            if (AtoB[i] != goodAtoB[i])
                failed = 1;
        for (i=0; i<15; i++)
            if (BtoA[i] != goodBtoA[i])
                failed = 1;
 
 
        /* Print some debugging output. */
        printf("key: 0x");
        for (i=0; i<8; i++)
            printf("%02X", key[i]);
        printf("\n");
        printf("frame number: 0x%06X\n", (unsigned int)frame);
        printf("known good output:\n");
        printf(" A->B: 0x");
        for (i=0; i<15; i++)
            printf("%02X", goodAtoB[i]);
        printf("  B->A: 0x");
        for (i=0; i<15; i++)
            printf("%02X", goodBtoA[i]);
        printf("\n");
        printf("observed output:\n");
        printf(" A->B: 0x");
        for (i=0; i<15; i++)
            printf("%02X", AtoB[i]);
        printf("  B->A: 0x");
        for (i=0; i<15; i++)
            printf("%02X", BtoA[i]);
        printf("\n");
 
 
        if (!failed) {
            printf("Self-check succeeded: everything looks ok.\n");
            exit(0);
        } else {
            /* Problems!  The test vectors didn't compare*/
            printf("\nCODE IS NOT WORKIND PROPERLY\n");
        }
    }
 
 
    int main(void) {
        test();
        return 0;
    }