twofish.cpp

KeePassX用于保护密码的安全

    if( key_len < 0 || key_len > 32 )
        {
        /* 
         * This can only happen if a programmer didn't read the limitations
         * on the key size. 
         */
        Twofish_fatal( "Twofish_prepare_key: illegal key length" );
        /* 
         * A return statement just in case the fatal macro returns.
         * The rest of the code assumes that key_len is in range, and would
         * buffer-overflow if it wasn't. 
         *
         * Why do we still use a programming language that has problems like
         * buffer overflows, when these problems were solved in 1960 with
         * the development of Algol? Have we not leared anything?
         */
        return;
        }

    /* Pad the key with zeroes to the next suitable key length. */
    memcpy( K, key, key_len );
    memset( K+key_len, 0, sizeof(K)-key_len );

    /* 
     * Compute kCycles: the number of key cycles used in the cipher. 
     * 2 for 128-bit keys, 3 for 192-bit keys, and 4 for 256-bit keys.
     */
    kCycles = (key_len + 7) >> 3;
    /* Handle the special case of very short keys: minimum 2 cycles. */
    if( kCycles < 2 )
        {
        kCycles = 2;
        }

    /* 
     * From now on we just pretend to have 8*kCycles bytes of 
     * key material in K. This handles all the key size cases. 
     */

    /* 
     * We first compute the 40 expanded key words, 
     * formulas straight from the Twofish specifications.
     */
    for( i=0; i<40; i+=2 )
        {
        /* 
         * Due to the byte spacing expected by the h() function 
         * we can pick the bytes directly from the key K.
         * As we use bytes, we never have the little/big endian
         * problem.
         *
         * Note that we apply the rotation function only to simple
         * variables, as the rotation macro might evaluate its argument
         * more than once.
         */
        A = h( i  , K  , kCycles );
        B = h( i+1, K+4, kCycles );
        B = ROL32( B, 8 );

        /* Compute and store the round keys. */
        A += B;
        B += A;
        xkey->K[i]   = A;
        xkey->K[i+1] = ROL32( B, 9 );
        }

    /* Wipe variables that contained key material. */
    A=B=0;

    /* 
     * And now the dreaded RS multiplication that few seem to understand.
     * The RS matrix is not random, and is specially designed to compute the
     * RS matrix multiplication in a simple way.
     *
     * We work in the field GF(2)[x]/x^8+x^6+x^3+x^2+1. Note that this is a
     * different field than used for the MDS matrix. 
     * (At least, it is a different representation because all GF(2^8) 
     * representations are equivalent in some form.)
     * 
     * We take 8 consecutive bytes of the key and interpret them as 
     * a polynomial k_0 + k_1 y + k_2 y^2 + ... + k_7 y^7 where 
     * the k_i bytes are the key bytes and are elements of the finite field.
     * We multiply this polynomial by y^4 and reduce it modulo
     *     y^4 + (x + 1/x)y^3 + (x)y^2 + (x + 1/x)y + 1. 
     * using straightforward polynomial modulo reduction.
     * The coefficients of the result are the result of the RS
     * matrix multiplication. When we wrote the Twofish specification, 
     * the original RS definition used the polynomials, 
     * but that requires much more mathematical knowledge. 
     * We were already using matrix multiplication in a finite field for 
     * the MDS matrix, so I re-wrote the RS operation as a matrix 
     * multiplication to reduce the difficulty of understanding it. 
     * Some implementors have not picked up on this simpler method of
     * computing the RS operation, even though it is mentioned in the
     * specifications.
     *
     * It is possible to perform these computations faster by using 32-bit 
     * word operations, but that is not portable and this is not a speed-
     * critical area.
     *
     * We explained the 1/x computation when we did the MDS matrix. 
     *
     * The S vector is stored in K[32..64].
     * The S vector has to be reversed, so we loop cross-wise.
     *
     * Note the weird byte spacing of the S-vector, to match the even 
     * or odd key words arrays. See the discussion at the Hxx macros for
     * details.
     */
    kptr = K + 8*kCycles;           /* Start at end of key */
    sptr = K + 32;                  /* Start at start of S */

    /* Loop over all key material */
    while( kptr > K ) 
        {
        kptr -= 8;
        /* 
         * Initialise the polynimial in sptr[0..12]
         * The first four coefficients are 0 as we have to multiply by y^4.
         * The next 8 coefficients are from the key material.
         */
        memset( sptr, 0, 4 );
        memcpy( sptr+4, kptr, 8 );

        /* 
         * The 12 bytes starting at sptr are now the coefficients of
         * the polynomial we need to reduce.
         */

        /* Loop over the polynomial coefficients from high to low */
        t = sptr+11;
        /* Keep looping until polynomial is degree 3; */
        while( t > sptr+3 )
            {
            /* Pick up the highest coefficient of the poly. */
            b = *t;

            /* 
             * Compute x and (x+1/x) times this coefficient. 
             * See the MDS matrix implementation for a discussion of 
             * multiplication by x and 1/x. We just use different 
             * constants here as we are in a 
             * different finite field representation.
             *
             * These two statements set 
             * bx = (x) * b 
             * bxx= (x + 1/x) * b
             */
            bx = (Twofish_Byte)((b<<1) ^ rs_poly_const[ b>>7 ]);
            bxx= (Twofish_Byte)((b>>1) ^ rs_poly_div_const[ b&1 ] ^ bx);

            /*
             * Subtract suitable multiple of 
             * y^4 + (x + 1/x)y^3 + (x)y^2 + (x + 1/x)y + 1 
             * from the polynomial, except that we don't bother
             * updating t[0] as it will become zero anyway.
             */
            t[-1] ^= bxx;
            t[-2] ^= bx;
            t[-3] ^= bxx;
            t[-4] ^= b;
            
            /* Go to the next coefficient. */
            t--;
            }

        /* Go to next S-vector word, obeying the weird spacing rules. */
        sptr += 8;
        }

    /* Wipe variables that contained key material. */
    b = bx = bxx = 0;

    /* And finally, we can compute the key-dependent S-boxes. */
    fill_keyed_sboxes( &K[32], kCycles, xkey );

    /* Wipe array that contained key material. */
    memset( K, 0, sizeof( K ) );
    }


/*
 * We can now start on the actual encryption and decryption code.
 * As these are often speed-critical we will use a lot of macros.
 */

/*
 * The g() function is the heart of the round function.
 * We have two versions of the g() function, one without an input
 * rotation and one with.
 * The pre-computed S-boxes make this pretty simple.
 */
#define g0(X,xkey) \
 (xkey->s[0][b0(X)]^xkey->s[1][b1(X)]^xkey->s[2][b2(X)]^xkey->s[3][b3(X)])

#define g1(X,xkey) \
 (xkey->s[0][b3(X)]^xkey->s[1][b0(X)]^xkey->s[2][b1(X)]^xkey->s[3][b2(X)])

/*
 * A single round of Twofish. The A,B,C,D are the four state variables,
 * T0 and T1 are temporaries, xkey is the expanded key, and r the 
 * round number.
 *
 * Note that this macro does not implement the swap at the end of the round.
 */
#define ENCRYPT_RND( A,B,C,D, T0, T1, xkey, r ) \
    T0 = g0(A,xkey); T1 = g1(B,xkey);\
    C ^= T0+T1+xkey->K[8+2*(r)]; C = ROR32(C,1);\
    D = ROL32(D,1); D ^= T0+2*T1+xkey->K[8+2*(r)+1]

/*
 * Encrypt a single cycle, consisting of two rounds.
 * This avoids the swapping of the two halves. 
 * Parameter r is now the cycle number.
 */
#define ENCRYPT_CYCLE( A, B, C, D, T0, T1, xkey, r ) \
    ENCRYPT_RND( A,B,C,D,T0,T1,xkey,2*(r)   );\
    ENCRYPT_RND( C,D,A,B,T0,T1,xkey,2*(r)+1 )

/* Full 16-round encryption */
#define ENCRYPT( A,B,C,D,T0,T1,xkey ) \
    ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 0 );\
    ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 1 );\
    ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 2 );\
    ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 3 );\
    ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 4 );\
    ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 5 );\
    ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 6 );\
    ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 7 )

/*
 * A single round of Twofish for decryption. It differs from
 * ENCRYTP_RND only because of the 1-bit rotations.
 */
#define DECRYPT_RND( A,B,C,D, T0, T1, xkey, r ) \
    T0 = g0(A,xkey); T1 = g1(B,xkey);\
    C = ROL32(C,1); C ^= T0+T1+xkey->K[8+2*(r)];\
    D ^= T0+2*T1+xkey->K[8+2*(r)+1]; D = ROR32(D,1)

/*
 * Decrypt a single cycle, consisting of two rounds. 
 * This avoids the swapping of the two halves. 
 * Parameter r is now the cycle number.
 */
#define DECRYPT_CYCLE( A, B, C, D, T0, T1, xkey, r ) \
    DECRYPT_RND( A,B,C,D,T0,T1,xkey,2*(r)+1 );\
    DECRYPT_RND( C,D,A,B,T0,T1,xkey,2*(r)   )

/* Full 16-round decryption. */
#define DECRYPT( A,B,C,D,T0,T1, xkey ) \
    DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 7 );\
    DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 6 );\
    DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 5 );\
    DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 4 );\
    DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 3 );\
    DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 2 );\
    DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 1 );\
    DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 0 )

/*
 * A macro to read the state from the plaintext and do the initial key xors.
 * The koff argument allows us to use the same macro 
 * for the decryption which uses different key words at the start.
 */
#define GET_INPUT( src, A,B,C,D, xkey, koff ) \
    A = GET32(src   )^xkey->K[  koff]; B = GET32(src+ 4)^xkey->K[1+koff]; \
    C = GET32(src+ 8)^xkey->K[2+koff]; D = GET32(src+12)^xkey->K[3+koff]

/*
 * Similar macro to put the ciphertext in the output buffer.
 * We xor the keys into the state variables before we use the PUT32 
 * macro as the macro might use its argument multiple times.
 */
#define PUT_OUTPUT( A,B,C,D, dst, xkey, koff ) \
    A ^= xkey->K[  koff]; B ^= xkey->K[1+koff]; \
    C ^= xkey->K[2+koff]; D ^= xkey->K[3+koff]; \
    PUT32( A, dst   ); PUT32( B, dst+ 4 ); \
    PUT32( C, dst+8 ); PUT32( D, dst+12 )


/*
 * Twofish block encryption
 *
 * Arguments:
 * xkey         expanded key array
 * p            16 bytes of plaintext
 * c            16 bytes in which to store the ciphertext
 */
void Twofish_encrypt( Twofish_key * xkey, Twofish_Byte p[16], Twofish_Byte c[16])
    {
    Twofish_UInt32 A,B,C,D,T0,T1;       /* Working variables */

    /* Get the four plaintext words xorred with the key */
    GET_INPUT( p, A,B,C,D, xkey, 0 );

    /* Do 8 cycles (= 16 rounds) */
    ENCRYPT( A,B,C,D,T0,T1,xkey );

    /* Store them with the final swap and the output whitening. */
    PUT_OUTPUT( C,D,A,B, c, xkey, 4 );
    }


/*
 * Twofish block decryption.
 *
 * Arguments:
 * xkey         expanded key array
 * p            16 bytes of plaintext
 * c            16 bytes in which to store the ciphertext
 */
void Twofish_decrypt( Twofish_key * xkey, Twofish_Byte c[16], Twofish_Byte p[16])
    {
    Twofish_UInt32 A,B,C,D,T0,T1;       /* Working variables */

    /* Get the four plaintext words xorred with the key */
    GET_INPUT( c, A,B,C,D, xkey, 4 );

    /* Do 8 cycles (= 16 rounds) */
    DECRYPT( A,B,C,D,T0,T1,xkey );

    /* Store them with the final swap and the output whitening. */
    PUT_OUTPUT( C,D,A,B, p, xkey, 0 );
    }

/*
 * Using the macros it is easy to make special routines for
 * CBC mode, CTR mode etc. The only thing you might want to
 * add is a XOR_PUT_OUTPUT which xors the outputs into the
 * destinationa instead of overwriting the data. This requires
 * a XOR_PUT32 macro as well, but that should all be trivial.
 *
 * I thought about including routines for the separate cipher
 * modes here, but it is unclear which modes should be included,
 * and each encryption or decryption routine takes up a lot of code space.
 * Also, I don't have any test vectors for any cipher modes
 * with Twofish.
 */