fromz3import*register_size=20defZ3LFSR(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
foriinrange(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)returnbit, new_registerdefSolve(cipher_iv,known_bytes,data,enc_hash):taps=[]register=[]cipher_iv_stream=BitStream(cipher_iv)#Setup Register and Taps
forxinrange(8):taps.append(BitVec("T{}".format(x),register_size))register.append(BitVecVal(cipher_iv_stream.get_bits(register_size),register_size))foriinrange(20):forjinrange(8):new_bit, new_register=Z3LFSR(taps[i],register[i])register[i]=new_bit#Get Keystream Bytes
forjinrange(20,len(known_bytes)):bits=[]foriinrange(8)new_bit, new_register=Z3LFSR(taps[i],register[i])register[i]=new_bitbits.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)whileTrue:ch=s.check()printchifch.r==-1:returnmodel=s.model()poly=[]foriinrange(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()ifdec_hash==dec_data_hash:print("YEAH!")withopen("flag.png","wb")asf:f.write(dec_data)returncurrent_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
fromfunctoolsimportreducefromoperatorimportxorclassLFSR:def__init__(self,fill,taps):# Convert bytes to bit list if needed
iftype(fill)!=list:temp=int.from_bytes(fill,byteorder="big")fill=[int(b)forbinf"{temp:0{len(fill)*8}b}"]iflen(fill)!=48:raiseValueError("Fill must be a 48-bit list")self.register=fillself.taps=tapsdefstep(self):tapped_bits=[self.register[t]fortinself.taps]new_bit=reduce(xor,tapped_bits)# Shift and append
delself.register[0]self.register.append(new_bit)returnnew_bitdefrand(self,bit_size):num=0for_inrange(bit_size):num=(num<<1)|self.step()returnnumdef__str__(self):returnf"<LFSR: {''.join(map(str,self.register))}, taps: {self.taps}>"if__name__=="__main__":seed=[0]*48taps=[47,42,38,37,35,33,32,30,28,23,22,20,18,12,8,6,5,0]l=LFSR(seed,taps)print(l.rand(64))
#include<stdio.h>/* Masks for the shift registers */#defineR1MASK0x07FFFF/* 19 bits, numbered 0..18 */#defineR2MASK0x3FFFFF/* 22 bits, numbered 0..21 */#defineR3MASK0x7FFFFF/* 23 bits, numbered 0..22 */#defineR4MASK0x01FFFF/* 17 bits, numbered 0..16 *//* A bit of R4 that controls each of the shift registers */#defineR4TAP10x000400/* bit 10 */#defineR4TAP20x000008/* bit 3 */#defineR4TAP30x000080/* 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. */#defineR1TAPS0x072000/* bits 18,17,16,13 */#defineR2TAPS0x300000/* bits 21,20 */#defineR3TAPS0x700080/* bits 22,21,20,7 */#defineR4TAPS0x010800/* bits 16,11 */typedefunsignedcharbyte;typedefunsignedlongword;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)return1;elsereturn0;}/* 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. */voidclock(intallP,intloaded){
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. */voidkeysetup(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. */voidrun(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. */voidtest(){
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",(unsignedint)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");}}intmain(void){test();return0;}