Security Implications of Fixed & Opposite Fixed Points of Sbox

Question

Fixed point means when Sbox Input is equal to Sbox Output whereas Opposite Fixed Point means when Sbox Input is complement of Sbox Output. How does Fixed and Opposite Fixed Point affect the strength/ security of Sbox?

Answer 1

One possible security threat is invariants subspace attack. a practical example is midori cipher given this.

The Midori sbox has 4 fixed points (3, 7, 8, 9). In the paper, using a plaintext composed of (8 and 9) and keys with combination of (0 and1) , it will give you cipher-text composed of (8 and 9). it works not only because of fixed points but also because of binary matrix property and constant value.

To understand the effect of fixed points , lets change the round constant values and replace 1 with 4.then use plaintext composed of 3 and 7 and keys with a combination of 0 and 4 , it will produce cipher-text composed of 3 and 7 (illustration in code below).

this is one scenario i know (with example) of security implication of fixed points but i have not come across opposite fixed points

#include <stdio.h>
#include <stdlib.h>

// 7 3 , constant 4 0; weak keys : 0 4
// 8 9 , constant 1 0; weak keys : 0 1


 uint64_t SBox0[16]= {0XC,0XA,0XD,0X3,0XE,0XB,0XF,0X7,0X8,0X9,0X1,0X5,0X0,0X2,0X4,0X6};





/*
uint64_t RC[19] = {

0X0001010110110011, 
0X0111100011000000, 
0X1010010000110101, 
0X0110001000010011, 
0X0001000001001111, 
0X1101000101110000, 
0X0000001001100110, 
0X0000101111001100, 
0X1001010010000001, 
0X0100000010111000, 
0X0111000110010111, 
0X0010001010001110, 
0X0101000100110000, 
0X1111100011001010, 
0X1101111110010000, 
0X0111110010000001, 
0X0001110000100100, 
0X0010001110110100, 
0X0110001010001010  

};

*/



uint64_t RC[19] = {

0X0004040440440044, 
0X0444400044000000, 
0X4040040000440404, 
0X0440004000040044, 
0X0004000004004444, 
0X4404000404440000, 
0X0000004004400440, 
0X0000404444004400, 
0X4004040040000004, 
0X0400000040444000, 
0X0444000440040444, 
0X0040004040004440, 
0X0404000400440000, 
0X4444400044004040, 
0X4404444440040000, 
0X0444440040000004, 
0X0004440000400400, 
0X0040004440440400, 
0X0440004040004040  

};  







uint64_t mask=0xF;

uint64_t SK[15]= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

void subKey(uint64_t K0,uint64_t K1){

    SK[0]= RC[0]^K0;
    SK[1]= RC[1]^K1;

    for(int i=2;i<15;i++){
        if(i%2==0) SK[i]= RC[i]^K0;
        else if(i%2==1)  SK[i]= RC[i]^K1;



    }




}


uint64_t Permutate(uint64_t input){

        uint64_t x[16]= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        uint64_t y[16]= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

        uint16_t P[16]=  {0,10,5,15,14,4,11,1,9,3,12,6,7,13,2,8}; 

        uint64_t output;
        uint64_t i = input;


        x[15]= (input &(mask<<0))>>0;
        x[14]= (input &(mask<<4))>>4;
        x[13]= (input &(mask<<8))>>8;
        x[12]= (input &(mask<<12))>>12;
        x[11]= (input&(mask<<16))>>16;
        x[10]= (input&(mask<<20))>>20;
        x[9]= (input&(mask<<24))>>24;
        x[8]= (input&(mask<<28))>>28;
        x[7]= (input&(mask<<32))>>32;
        x[6]= (input&(mask<<36))>>36;
        x[5]= (input&(mask<<40))>>40;
        x[4]= (input&(mask<<44))>>44;
        x[3]= (input&(mask<<48))>>48;
        x[2]= (input&(mask<<52))>>52;
        x[1]= (input&(mask<<56))>>56;
        x[0]= (input&(mask<<60))>>60;


        y[0]= x[P[0]];
        y[1]= x[P[1]];
        y[2]= x[P[2]];
        y[3]= x[P[3]];
        y[4]= x[P[4]];
        y[5]= x[P[5]];
        y[6]= x[P[6]];
        y[7]= x[P[7]];
        y[8]= x[P[8]];
        y[9]= x[P[9]];
        y[10]= x[P[10]];
        y[11]= x[P[11]];
        y[12]= x[P[12]];
        y[13]= x[P[13]];
        y[14]= x[P[14]];
        y[15]= x[P[15]];



        output= y[15]<<0|y[14]<<4|y[13]<<8|y[12]<<12|y[11]<<16|y[10]<<20|y[9]<<24|y[8]<<28|y[7]<<32|y[6]<<36|
                y[5]<<40|y[4]<<44|y[3]<<48|y[2]<<52|y[1]<<56|y[0]<<60;


        return output;

}

uint64_t SubCell(uint64_t input){

uint64_t x[16]= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        uint64_t y[16]= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

        uint64_t output;
        uint64_t i = input;


        x[0]= (input &(mask<<0))>>0;
        x[1]= (input &(mask<<4))>>4;
        x[2]= (input &(mask<<8))>>8;
        x[3]= (input &(mask<<12))>>12;
        x[4]= (input&(mask<<16))>>16;
        x[5]= (input&(mask<<20))>>20;
        x[6]= (input&(mask<<24))>>24;
        x[7]= (input&(mask<<28))>>28;
        x[8]= (input&(mask<<32))>>32;
        x[9]= (input&(mask<<36))>>36;
        x[10]= (input&(mask<<40))>>40;
        x[11]= (input&(mask<<44))>>44;
        x[12]= (input&(mask<<48))>>48;
        x[13]= (input&(mask<<52))>>52;
        x[14]= (input&(mask<<56))>>56;
        x[15]= (input&(mask<<60))>>60;



        y[0]=SBox0[x[0]];
        y[1]=SBox0[x[1]];
        y[2]=SBox0[x[2]];
        y[3]=SBox0[x[3]];
        y[4]=SBox0[x[4]];
        y[5]=SBox0[x[5]];
        y[6]=SBox0[x[6]];
        y[7]=SBox0[x[7]];
        y[8]=SBox0[x[8]];
        y[9]=SBox0[x[9]];
        y[10]=SBox0[x[10]];
        y[11]=SBox0[x[11]];
        y[12]=SBox0[x[12]];
        y[13]=SBox0[x[13]];
        y[14]=SBox0[x[14]];
        y[15]=SBox0[x[15]];



        output= y[0]<<0|y[1]<<4|y[2]<<8|y[3]<<12|y[4]<<16|y[5]<<20|y[6]<<24|y[7]<<28|y[8]<<32|y[9]<<36|
                y[10]<<40|y[11]<<44|y[12]<<48|y[13]<<52|y[14]<<56|y[15]<<60;


        return output;




}

uint16_t  M(uint16_t I){  // matrix multiplication

    uint16_t x0,x1,x2,x3;
    uint16_t y0,y1,y2,y3;


    uint16_t O;

    x0= (I&(mask<<0))>>0;
    x1= (I&(mask<<4))>>4;
    x2= (I&(mask<<8))>>8;
    x3= (I&(mask<<12))>>12;



    y0=  x1^x2^x3;
    y1=  x0^x2^x3;
    y2=  x0^x1^x3;
    y3=  x0^x1^x2;



    O= y0<<0|y1<<4|y2<<8|y3<<12;
    return O;




}

uint64_t Mixcolumn(uint64_t I){

    uint16_t x0,x1,x2,x3;
    uint64_t y0,y1,y2,y3;
    uint64_t S=0xFFFF;

    uint64_t O;

    x0= (I&(S<<0))>>0;
    x1= (I&(S<<16))>>16;
    x2= (I&(S<<32))>>32;
    x3= (I&(S<<48))>>48;




    y0= M(x0);
    y1= M(x1);
    y2= M(x2);
    y3= M(x3);



    O= y0<<0|y1<<16|y2<<32|y3<<48;

    return O;


}

uint64_t AK(uint64_t i,uint64_t K){

    return i^K;
}   

void Cipher (uint64_t PT, uint64_t K0,uint64_t K1){
    uint64_t temp;
    int i;
        temp=AK(PT,K0^K1);  // whitening;
        printf("KT:%08llx%08llx\n",K0,K1);
        printf("PT:%016llx\n",PT);



    for(i=0;i<15;i++){
    temp=SubCell(temp);
    temp=Permutate(temp);
    temp=Mixcolumn(temp);
    temp=AK(temp,SK[i]);


    } 


    temp=SubCell(temp);
    temp=AK(temp,K0^K1);  // whitening;



    printf("CT:%016llx\n",temp);


}
int main(){



    // This section for RC table that contains 0 and 4 as constants.
    /*
    uint64_t k0=   0x4044400444444444;
    uint64_t k1=   0x4444000044444400;
    uint64_t PT=   0x3333333333333333;
    */

    uint64_t k0=   0x4044400444444444;
    uint64_t k1=   0x4444000044444400;
    uint64_t PT=   0x3737373737373737;



    // This section for RC table that contains 0 and 1 as constants. Rememeber to uncomment the RC table of 0,1 and comment the other one.
    /*
    uint64_t k0=0x0000101001001110;
    uint64_t k1=0x1101010100010001;
    uint64_t PT=0x9889898898898989;
    */


    /*
    uint64_t k0=0x1100110011001100;
    uint64_t k1=0x0011001100110011;
    uint64_t PT=0x9999999999999999;
    */



    subKey(k0,k1);

    Cipher(PT,k0,k1);


    return 0;
}