twofish.cpp

KeePassX用于保护密码的安全

    static Twofish_Byte k128[] = {
        0x9F, 0x58, 0x9F, 0x5C, 0xF6, 0x12, 0x2C, 0x32, 
        0xB6, 0xBF, 0xEC, 0x2F, 0x2A, 0xE8, 0xC3, 0x5A,
        };
    static Twofish_Byte p128[] = {
        0xD4, 0x91, 0xDB, 0x16, 0xE7, 0xB1, 0xC3, 0x9E, 
        0x86, 0xCB, 0x08, 0x6B, 0x78, 0x9F, 0x54, 0x19
        };
    static Twofish_Byte c128[] = {
        0x01, 0x9F, 0x98, 0x09, 0xDE, 0x17, 0x11, 0x85, 
        0x8F, 0xAA, 0xC3, 0xA3, 0xBA, 0x20, 0xFB, 0xC3
        };

    /* 192-bit test is the I=4 case of section B.2 of the Twofish book. */
    static Twofish_Byte k192[] = {
        0x88, 0xB2, 0xB2, 0x70, 0x6B, 0x10, 0x5E, 0x36, 
        0xB4, 0x46, 0xBB, 0x6D, 0x73, 0x1A, 0x1E, 0x88, 
        0xEF, 0xA7, 0x1F, 0x78, 0x89, 0x65, 0xBD, 0x44
        };
    static Twofish_Byte p192[] = {
        0x39, 0xDA, 0x69, 0xD6, 0xBA, 0x49, 0x97, 0xD5,
        0x85, 0xB6, 0xDC, 0x07, 0x3C, 0xA3, 0x41, 0xB2
        };
    static Twofish_Byte c192[] = {
        0x18, 0x2B, 0x02, 0xD8, 0x14, 0x97, 0xEA, 0x45,
        0xF9, 0xDA, 0xAC, 0xDC, 0x29, 0x19, 0x3A, 0x65
        };

    /* 256-bit test is the I=4 case of section B.2 of the Twofish book. */
    static Twofish_Byte k256[] = {
        0xD4, 0x3B, 0xB7, 0x55, 0x6E, 0xA3, 0x2E, 0x46, 
        0xF2, 0xA2, 0x82, 0xB7, 0xD4, 0x5B, 0x4E, 0x0D,
        0x57, 0xFF, 0x73, 0x9D, 0x4D, 0xC9, 0x2C, 0x1B,
        0xD7, 0xFC, 0x01, 0x70, 0x0C, 0xC8, 0x21, 0x6F
        };
    static Twofish_Byte p256[] = {
        0x90, 0xAF, 0xE9, 0x1B, 0xB2, 0x88, 0x54, 0x4F,
        0x2C, 0x32, 0xDC, 0x23, 0x9B, 0x26, 0x35, 0xE6
        };
    static Twofish_Byte c256[] = {
        0x6C, 0xB4, 0x56, 0x1C, 0x40, 0xBF, 0x0A, 0x97,
        0x05, 0x93, 0x1C, 0xB6, 0xD4, 0x08, 0xE7, 0xFA
        };

    /* Run the actual tests. */
    test_vector( k128, 16, p128, c128 );
    test_vector( k192, 24, p192, c192 );
    test_vector( k256, 32, p256, c256 );
    }   


/*
 * Perform extensive test for a single key size.
 * 
 * Test a single key size against the test vectors from section
 * B.2 in the Twofish book. This is a sequence of 49 encryptions
 * and decryptions. Each plaintext is equal to the ciphertext of
 * the previous encryption. The key is made up from the ciphertext
 * two and three encryptions ago. Both plaintext and key start
 * at the zero value. 
 * We should have designed a cleaner recurrence relation for
 * these tests, but it is too late for that now. At least we learned
 * how to do it better next time.
 * For details see appendix B of the book.
 *
 * Arguments:
 * key_len      Number of bytes of key
 * final_value  Final plaintext value after 49 iterations
 */
static void test_sequence( int key_len, Twofish_Byte final_value[] )
    {
    Twofish_Byte buf[ (50+3)*16 ];      /* Buffer to hold our computation values. */
    Twofish_Byte tmp[16];               /* Temp for testing the decryption. */
    Twofish_key xkey;           /* The expanded key */
    int i;                      
    Twofish_Byte * p;

    /* Wipe the buffer */
    memset( buf, 0, sizeof( buf ) );

    /*
     * Because the recurrence relation is done in an inconvenient manner
     * we end up looping backwards over the buffer.
     */

    /* Pointer in buffer points to current plaintext. */
    p = &buf[50*16];
    for( i=1; i<50; i++ )
        {
        /* 
         * Prepare a key.
         * This automatically checks that key_len is valid.
         */
        Twofish_prepare_key( p+16, key_len, &xkey );

        /* Compute the next 16 bytes in the buffer */
        Twofish_encrypt( &xkey, p, p-16 );

        /* Check that the decryption is correct. */
        Twofish_decrypt( &xkey, p-16, tmp );
        if( memcmp( tmp, p, 16 ) != 0 )
            {
            Twofish_fatal( "Twofish decryption failure in sequence" );
            }
        /* Move on to next 16 bytes in the buffer. */
        p -= 16;
        }

    /* And check the final value. */
    if( memcmp( p, final_value, 16 ) != 0 ) 
        {
        Twofish_fatal( "Twofish encryption failure in sequence" );
        }

    /* None of the data was secret, so there is no need to wipe anything. */
    }


/* 
 * Run all three sequence tests from the Twofish test vectors. 
 *
 * This checks the most extensive test vectors currently available 
 * for Twofish. The data is from the Twofish book, appendix B.2.
 */
static void test_sequences()
    {
    static Twofish_Byte r128[] = {
        0x5D, 0x9D, 0x4E, 0xEF, 0xFA, 0x91, 0x51, 0x57,
        0x55, 0x24, 0xF1, 0x15, 0x81, 0x5A, 0x12, 0xE0
        };
    static Twofish_Byte r192[] = {
        0xE7, 0x54, 0x49, 0x21, 0x2B, 0xEE, 0xF9, 0xF4,
        0xA3, 0x90, 0xBD, 0x86, 0x0A, 0x64, 0x09, 0x41
        };
    static Twofish_Byte r256[] = {
        0x37, 0xFE, 0x26, 0xFF, 0x1C, 0xF6, 0x61, 0x75,
        0xF5, 0xDD, 0xF4, 0xC3, 0x3B, 0x97, 0xA2, 0x05
        };

    /* Run the three sequence test vectors */
    test_sequence( 16, r128 );
    test_sequence( 24, r192 );
    test_sequence( 32, r256 );
    }


/*
 * Test the odd-sized keys.
 *
 * Every odd-sized key is equivalent to a one of 128, 192, or 256 bits.
 * The equivalent key is found by padding at the end with zero bytes
 * until a regular key size is reached.
 *
 * We just test that the key expansion routine behaves properly.
 * If the expanded keys are identical, then the encryptions and decryptions
 * will behave the same.
 */
static void test_odd_sized_keys()
    {
    Twofish_Byte buf[32];
    Twofish_key xkey;
    Twofish_key xkey_two;
    int i;

    /* 
     * We first create an all-zero key to use as PRNG key. 
     * Normally we would not have to fill the buffer with zeroes, as we could
     * just pass a zero key length to the Twofish_prepare_key function.
     * However, this relies on using odd-sized keys, and those are just the
     * ones we are testing here. We can't use an untested function to test 
     * itself. 
     */
    memset( buf, 0, sizeof( buf ) );
    Twofish_prepare_key( buf, 16, &xkey );

    /* Fill buffer with pseudo-random data derived from two encryptions */
    Twofish_encrypt( &xkey, buf, buf );
    Twofish_encrypt( &xkey, buf, buf+16 );

    /* Create all possible shorter keys that are prefixes of the buffer. */
    for( i=31; i>=0; i-- )
        {
        /* Set a byte to zero. This is the new padding byte */
        buf[i] = 0;

        /* Expand the key with only i bytes of length */
        Twofish_prepare_key( buf, i, &xkey );

        /* Expand the corresponding padded key of regular length */
        Twofish_prepare_key( buf, i<=16 ? 16 : (i<= 24 ? 24 : 32), &xkey_two );

        /* Compare the two */
        if( memcmp( &xkey, &xkey_two, sizeof( xkey ) ) != 0 )
            {
            Twofish_fatal( "Odd sized keys do not expand properly" );
            }
        }

    /* None of the key values are secret, so we don't need to wipe them. */
    }


/*
 * Test the Twofish implementation.
 *
 * This routine runs all the self tests, in order of importance.
 * It is called by the Twofish_initialise routine.
 * 
 * In almost all applications the cost of running the self tests during
 * initialisation is insignificant, especially
 * compared to the time it takes to load the application from disk. 
 * If you are very pressed for initialisation performance, 
 * you could remove some of the tests. Make sure you did run them
 * once in the software and hardware configuration you are using.
 */
static void self_test()
    {
    /* The three test vectors form an absolute minimal test set. */
    test_vectors();

    /* 
     * If at all possible you should run these tests too. They take
     * more time, but provide a more thorough coverage.
     */
    test_sequences();

    /* Test the odd-sized keys. */
    test_odd_sized_keys();
    }


/*
 * And now, the actual Twofish implementation.
 *
 * This implementation generates all the tables during initialisation. 
 * I don't like large tables in the code, especially since they are easily 
 * damaged in the source without anyone noticing it. You need code to 
 * generate them anyway, and this way all the code is close together.
 * Generating them in the application leads to a smaller executable 
 * (the code is smaller than the tables it generates) and a 
 * larger static memory footprint.
 *
 * Twofish can be implemented in many ways. I have chosen to 
 * use large tables with a relatively long key setup time.
 * If you encrypt more than a few blocks of data it pays to pre-compute 
 * as much as possible. This implementation is relatively inefficient for 
 * applications that need to re-key every block or so.
 */

/* 
 * We start with the t-tables, directly from the Twofish definition. 
 * These are nibble-tables, but merging them and putting them two nibbles 
 * in one byte is more work than it is worth.
 */
static Twofish_Byte t_table[2][4][16] = {
    {
        {0x8,0x1,0x7,0xD,0x6,0xF,0x3,0x2,0x0,0xB,0x5,0x9,0xE,0xC,0xA,0x4},
        {0xE,0xC,0xB,0x8,0x1,0x2,0x3,0x5,0xF,0x4,0xA,0x6,0x7,0x0,0x9,0xD},
        {0xB,0xA,0x5,0xE,0x6,0xD,0x9,0x0,0xC,0x8,0xF,0x3,0x2,0x4,0x7,0x1},
        {0xD,0x7,0xF,0x4,0x1,0x2,0x6,0xE,0x9,0xB,0x3,0x0,0x8,0x5,0xC,0xA}
    },
    {
        {0x2,0x8,0xB,0xD,0xF,0x7,0x6,0xE,0x3,0x1,0x9,0x4,0x0,0xA,0xC,0x5},
        {0x1,0xE,0x2,0xB,0x4,0xC,0x3,0x7,0x6,0xD,0xA,0x5,0xF,0x9,0x0,0x8},
        {0x4,0xC,0x7,0x5,0x1,0x6,0x9,0xA,0x0,0xE,0xD,0x8,0x2,0xB,0x3,0xF},
        {0xB,0x9,0x5,0x1,0xC,0x3,0xD,0xE,0x6,0x4,0x7,0xF,0x2,0x0,0x8,0xA}
    }
};


/* A 1-bit rotation of 4-bit values. Input must be in range 0..15 */
#define ROR4BY1( x ) (((x)>>1) | (((x)<<3) & 0x8) )

/*
 * The q-boxes are only used during the key schedule computations. 
 * These are 8->8 bit lookup tables. Some CPUs prefer to have 8->32 bit 
 * lookup tables as it is faster to load a 32-bit value than to load an 
 * 8-bit value and zero the rest of the register.
 * The LARGE_Q_TABLE switch allows you to choose 32-bit entries in 
 * the q-tables. Here we just define the Qtype which is used to store 
 * the entries of the q-tables.
 */
#if LARGE_Q_TABLE
typedef Twofish_UInt32      Qtype;
#else
typedef Twofish_Byte        Qtype;
#endif

/* 
 * The actual q-box tables. 
 * There are two q-boxes, each having 256 entries.
 */
static Qtype q_table[2][256];


/*
 * Now the function that converts a single t-table into a q-table.
 *
 * Arguments:
 * t[4][16] : four 4->4bit lookup tables that define the q-box
 * q[256]   : output parameter: the resulting q-box as a lookup table.
 */
static void make_q_table( Twofish_Byte t[4][16], Qtype q[256] )
    {
    int ae,be,ao,bo;        /* Some temporaries. */
    int i;
    /* Loop over all input values and compute the q-box result. */
    for( i=0; i<256; i++ ) {
        /* 
         * This is straight from the Twofish specifications. 
         * 
         * The ae variable is used for the a_i values from the specs
         * with even i, and ao for the odd i's. Similarly for the b's.
         */
        ae = i>>4; be = i&0xf;
        ao = ae ^ be; bo = ae ^ ROR4BY1(be) ^ ((ae<<3)&8);
        ae = t[0][ao]; be = t[1][bo];
        ao = ae ^ be; bo = ae ^ ROR4BY1(be) ^ ((ae<<3)&8);
        ae = t[2][ao]; be = t[3][bo];

        /* Store the result in the q-box table, the cast avoids a warning. */
        q[i] = (Qtype) ((be<<4) | ae);
        }
    }


/* 
 * Initialise both q-box tables. 
 */
static void initialise_q_boxes() {
    /* Initialise each of the q-boxes using the t-tables */
    make_q_table( t_table[0], q_table[0] );
    make_q_table( t_table[1], q_table[1] );
    }


/*
 * Next up is the MDS matrix multiplication.
 * The MDS matrix multiplication operates in the field
 * GF(2)[x]/p(x) with p(x)=x^8+x^6+x^5+x^3+1.
 * If you don't understand this, read a book on finite fields. You cannot
 * follow the finite-field computations without some background.