twofish.cpp

KeePassX用于保护密码的安全

 * 
 * In this field, multiplication by x is easy: shift left one bit 
 * and if bit 8 is set then xor the result with 0x169. 
 *
 * The MDS coefficients use a multiplication by 1/x,
 * or rather a division by x. This is easy too: first make the
 * value 'even' (i.e. bit 0 is zero) by xorring with 0x169 if necessary, 
 * and then shift right one position. 
 * Even easier: shift right and xor with 0xb4 if the lsbit was set.
 *
 * The MDS coefficients are 1, EF, and 5B, and we use the fact that
 *   EF = 1 + 1/x + 1/x^2
 *   5B = 1       + 1/x^2
 * in this field. This makes multiplication by EF and 5B relatively easy.
 *
 * This property is no accident, the MDS matrix was designed to allow
 * this implementation technique to be used.
 *
 * We have four MDS tables, each mapping 8 bits to 32 bits.
 * Each table performs one column of the matrix multiplication. 
 * As the MDS is always preceded by q-boxes, each of these tables
 * also implements the q-box just previous to that column.
 */

/* The actual MDS tables. */
static Twofish_UInt32 MDS_table[4][256];

/* A small table to get easy conditional access to the 0xb4 constant. */
static Twofish_UInt32 mds_poly_divx_const[] = {0,0xb4};

/* Function to initialise the MDS tables. */
static void initialise_mds_tables()
    {
    int i;
    Twofish_UInt32 q,qef,q5b;       /* Temporary variables. */

    /* Loop over all 8-bit input values */
    for( i=0; i<256; i++ ) 
        {
        /* 
         * To save some work during the key expansion we include the last
         * of the q-box layers from the h() function in these MDS tables.
         */

        /* We first do the inputs that are mapped through the q0 table. */
        q = q_table[0][i];
        /*
         * Here we divide by x, note the table to get 0xb4 only if the 
         * lsbit is set. 
         * This sets qef = (1/x)*q in the finite field
         */
        qef = (q >> 1) ^ mds_poly_divx_const[ q & 1 ];
        /*
         * Divide by x again, and add q to get (1+1/x^2)*q. 
         * Note that (1+1/x^2) =  5B in the field, and addition in the field
         * is exclusive or on the bits.
         */
        q5b = (qef >> 1) ^ mds_poly_divx_const[ qef & 1 ] ^ q;
        /* 
         * Add q5b to qef to set qef = (1+1/x+1/x^2)*q.
         * Again, (1+1/x+1/x^2) = EF in the field.
         */
        qef ^= q5b;

        /* 
         * Now that we have q5b = 5B * q and qef = EF * q 
         * we can fill two of the entries in the MDS matrix table. 
         * See the Twofish specifications for the order of the constants.
         */
        MDS_table[1][i] = (q  <<24) | (q5b<<16) | (qef<<8) | qef;
        MDS_table[3][i] = (q5b<<24) | (qef<<16) | (q  <<8) | q5b;

        /* Now we do it all again for the two columns that have a q1 box. */
        q = q_table[1][i];
        qef = (q >> 1) ^ mds_poly_divx_const[ q & 1 ];
        q5b = (qef >> 1) ^ mds_poly_divx_const[ qef & 1 ] ^ q;
        qef ^= q5b;

        /* The other two columns use the coefficient in a different order. */
        MDS_table[0][i] = (qef<<24) | (qef<<16) | (q5b<<8) | q  ;
        MDS_table[2][i] = (qef<<24) | (q  <<16) | (qef<<8) | q5b;
        }
    }


/*
 * The h() function is the heart of the Twofish cipher. 
 * It is a complicated sequence of q-box lookups, key material xors, 
 * and finally the MDS matrix.
 * We use lots of macros to make this reasonably fast.
 */

/* First a shorthand for the two q-tables */
#define q0  q_table[0]
#define q1  q_table[1]

/*
 * Each macro computes one column of the h for either 2, 3, or 4 stages.
 * As there are 4 columns, we have 12 macros in all.
 * 
 * The key bytes are stored in the Byte array L at offset 
 * 0,1,2,3,  8,9,10,11,  [16,17,18,19,   [24,25,26,27]] as this is the
 * order we get the bytes from the user. If you look at the Twofish 
 * specs, you'll see that h() is applied to the even key words or the
 * odd key words. The bytes of the even words appear in this spacing,
 * and those of the odd key words too.
 *
 * These macros are the only place where the q-boxes and the MDS table
 * are used.
 */
#define H02( y, L )  MDS_table[0][q0[q0[y]^L[ 8]]^L[0]]
#define H12( y, L )  MDS_table[1][q0[q1[y]^L[ 9]]^L[1]]
#define H22( y, L )  MDS_table[2][q1[q0[y]^L[10]]^L[2]]
#define H32( y, L )  MDS_table[3][q1[q1[y]^L[11]]^L[3]]
#define H03( y, L )  H02( q1[y]^L[16], L )
#define H13( y, L )  H12( q1[y]^L[17], L )
#define H23( y, L )  H22( q0[y]^L[18], L )
#define H33( y, L )  H32( q0[y]^L[19], L )
#define H04( y, L )  H03( q1[y]^L[24], L )
#define H14( y, L )  H13( q0[y]^L[25], L )
#define H24( y, L )  H23( q0[y]^L[26], L )
#define H34( y, L )  H33( q1[y]^L[27], L )

/*
 * Now we can define the h() function given an array of key bytes. 
 * This function is only used in the key schedule, and not to pre-compute
 * the keyed S-boxes.
 *
 * In the key schedule, the input is always of the form k*(1+2^8+2^16+2^24)
 * so we only provide k as an argument.
 *
 * Arguments:
 * k        input to the h() function.
 * L        pointer to array of key bytes at 
 *          offsets 0,1,2,3, ... 8,9,10,11, [16,17,18,19, [24,25,26,27]]
 * kCycles  # key cycles, 2, 3, or 4.
 */
static Twofish_UInt32 h( int k, Twofish_Byte L[], int kCycles )
    {
    switch( kCycles ) {
        /* We code all 3 cases separately for speed reasons. */
    case 2:
        return H02(k,L) ^ H12(k,L) ^ H22(k,L) ^ H32(k,L);
    case 3:
        return H03(k,L) ^ H13(k,L) ^ H23(k,L) ^ H33(k,L);
    case 4:
        return H04(k,L) ^ H14(k,L) ^ H24(k,L) ^ H34(k,L);
    default: 
        /* This is always a coding error, which is fatal. */
        Twofish_fatal( "Twofish h(): Illegal argument" );
		return 0;
        }
    }


/*
 * Pre-compute the keyed S-boxes.
 * Fill the pre-computed S-box array in the expanded key structure.
 * Each pre-computed S-box maps 8 bits to 32 bits.
 *
 * The S argument contains half the number of bytes of the full key, but is
 * derived from the full key. (See Twofish specifications for details.)
 * S has the weird byte input order used by the Hxx macros.
 *
 * This function takes most of the time of a key expansion.
 *
 * Arguments:
 * S        pointer to array of 8*kCycles Bytes containing the S vector.
 * kCycles  number of key words, must be in the set {2,3,4}
 * xkey     pointer to Twofish_key structure that will contain the S-boxes.
 */
static void fill_keyed_sboxes( Twofish_Byte S[], int kCycles, Twofish_key * xkey )
    {
    int i;
    switch( kCycles ) {
        /* We code all 3 cases separately for speed reasons. */
    case 2:
        for( i=0; i<256; i++ )
            {
            xkey->s[0][i]= H02( i, S );
            xkey->s[1][i]= H12( i, S );
            xkey->s[2][i]= H22( i, S );
            xkey->s[3][i]= H32( i, S );
            }
        break;
    case 3:
        for( i=0; i<256; i++ )
            {
            xkey->s[0][i]= H03( i, S );
            xkey->s[1][i]= H13( i, S );
            xkey->s[2][i]= H23( i, S );
            xkey->s[3][i]= H33( i, S );
            }
        break;
    case 4:
        for( i=0; i<256; i++ )
            {
            xkey->s[0][i]= H04( i, S );
            xkey->s[1][i]= H14( i, S );
            xkey->s[2][i]= H24( i, S );
            xkey->s[3][i]= H34( i, S );
            }
        break;
    default: 
        /* This is always a coding error, which is fatal. */
        Twofish_fatal( "Twofish fill_keyed_sboxes(): Illegal argument" );
        }
    }


/* A flag to keep track of whether we have been initialised or not. */
static int Twofish_initialised = 0;

/*
 * Initialise the Twofish implementation.
 * This function must be called before any other function in the
 * Twofish implementation is called.
 * This routine also does some sanity checks, to make sure that
 * all the macros behave, and it tests the whole cipher.
 */
void Twofish_initialise()
    {
    /* First test the various platform-specific definitions. */
    test_platform();

    /* We can now generate our tables, in the right order of course. */
    initialise_q_boxes();
    initialise_mds_tables();

    /* We're finished with the initialisation itself. */
    Twofish_initialised = 1;

    /* 
     * And run some tests on the whole cipher. 
     * Yes, you need to do this every time you start your program. 
     * It is called assurance; you have to be certain that your program
     * still works properly. 
     */
    self_test();
    }


/*
 * The Twofish key schedule uses an Reed-Solomon code matrix multiply.
 * Just like the MDS matrix, the RS-matrix is designed to be easy
 * to implement. Details are below in the code. 
 *
 * These constants make it easy to compute in the finite field used 
 * for the RS code.
 *
 * We use Bytes for the RS computation, but these are automatically
 * widened to unsigned integers in the expressions. Having unsigned
 * ints in these tables therefore provides the fastest access.
 */
static unsigned int rs_poly_const[] = {0, 0x14d};
static unsigned int rs_poly_div_const[] = {0, 0xa6 };


/*
 * Prepare a key for use in encryption and decryption.
 * Like most block ciphers, Twofish allows the key schedule 
 * to be pre-computed given only the key. 
 * Twofish has a fairly 'heavy' key schedule that takes a lot of time 
 * to compute. The main work is pre-computing the S-boxes used in the 
 * encryption and decryption. We feel that this makes the cipher much 
 * harder to attack. The attacker doesn't even know what the S-boxes 
 * contain without including the entire key schedule in the analysis. 
 *
 * Unlike most Twofish implementations, this one allows any key size from
 * 0 to 32 bytes. Odd key sizes are defined for Twofish (see the 
 * specifications); the key is simply padded with zeroes to the next real 
 * key size of 16, 24, or 32 bytes.
 * Each odd-sized key is thus equivalent to a single normal-sized key.
 *
 * Arguments:
 * key      array of key bytes
 * key_len  number of bytes in the key, must be in the range 0,...,32.
 * xkey     Pointer to an Twofish_key structure that will be filled 
 *             with the internal form of the cipher key.
 */
void Twofish_prepare_key( Twofish_Byte key[], int key_len, Twofish_key * xkey )
    {
    /* We use a single array to store all key material in, 
     * to simplify the wiping of the key material at the end.
     * The first 32 bytes contain the actual (padded) cipher key.
     * The next 32 bytes contain the S-vector in its weird format,
     * and we have 4 bytes of overrun necessary for the RS-reduction.
     */
    Twofish_Byte K[32+32+4]; 

    int kCycles;        /* # key cycles, 2,3, or 4. */

    int i;
    Twofish_UInt32 A, B;        /* Used to compute the round keys. */

    Twofish_Byte * kptr;        /* Three pointers for the RS computation. */
    Twofish_Byte * sptr;
    Twofish_Byte * t;

    Twofish_Byte b,bx,bxx;      /* Some more temporaries for the RS computation. */

    /* Check that the Twofish implementation was initialised. */
    if( Twofish_initialised == 0 )
        {
        /* 
         * You didn't call Twofish_initialise before calling this routine.
         * This is a programming error, and therefore we call the fatal
         * routine. 
         *
         * I could of course call the initialisation routine here,
         * but there are a few reasons why I don't. First of all, the 
         * self-tests have to be done at startup. It is no good to inform
         * the user that the cipher implementation fails when he wants to
         * write his data to disk in encrypted form. You have to warn him
         * before he spends time typing his data. Second, the initialisation
         * and self test are much slower than a single key expansion.
         * Calling the initialisation here makes the performance of the
         * cipher unpredictable. This can lead to really weird problems 
         * if you use the cipher for a real-time task. Suddenly it fails 
         * once in a while the first time you try to use it. Things like 
         * that are almost impossible to debug.
         */
        Twofish_fatal( "Twofish implementation was not initialised." );
        
        /*
         * There is always a danger that the Twofish_fatal routine returns,
         * in spite of the specifications that it should not. 
         * (A good programming rule: don't trust the rest of the code.)
         * This would be disasterous. If the q-tables and MDS-tables have
         * not been initialised, they are probably still filled with zeroes.
         * Suppose the MDS-tables are all zero. The key expansion would then
         * generate all-zero round keys, and all-zero s-boxes. The danger
         * is that nobody would notice as the encryption function still
         * mangles the input, and the decryption still 'decrypts' it,
         * but now in a completely key-independent manner. 
         * To stop such security disasters, we use blunt force.
         * If your program hangs here: fix the fatal routine!
         */
        for(;;);        /* Infinite loop, which beats being insecure. */
        }

    /* Check for valid key length. */