dvd_css.c

/*****************************************************************************
 * dvd_css.c: Functions for DVD authentification and unscrambling
 *****************************************************************************
 * Copyright (C) 1999-2001 VideoLAN
 * $Id: dvd_css.c,v 1.18 2001/03/03 11:01:07 sam Exp $
 *
 * Author: Stphane Borel <stef@via.ecp.fr>
 *
 * based on:
 *  - css-auth by Derek Fawcus <derek@spider.com>
 *  - DVD CSS ioctls example program by Andrew T. Veliath <andrewtv@usa.net>
 *  - The Divide and conquer attack by Frank A. Stevenson <frank@funcom.com>
 *  - DeCSSPlus by Ethan Hawke
 *  - DecVOB
 *  see http://www.lemuria.org/DeCSS/ by Tom Vogt for more information.
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA.
 *****************************************************************************/

/*****************************************************************************
 * Preamble
 *****************************************************************************/
#include "defs.h"

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <fcntl.h>
#include <netinet/in.h>
#ifdef HAVE_SYS_IOCTL_H
# include <sys/ioctl.h>
#endif
#ifdef HAVE_SYS_DVDIO_H
# include <sys/dvdio.h>
#endif
#ifdef LINUX_DVD
# include <linux/cdrom.h>
#endif

#include "common.h"

#include "intf_msg.h"

#include "dvd_css.h"
#ifdef HAVE_CSS
#include "dvd_csstables.h"
#endif /* HAVE_CSS */
#include "dvd_ioctl.h"
#include "dvd_ifo.h"

#include "input_dvd.h"

/*****************************************************************************
 * Local prototypes
 *****************************************************************************/
#ifdef HAVE_CSS
static int  CSSGetASF    ( int i_fd );
static void CSSCryptKey  ( int i_key_type, int i_varient,
                           u8 const * pi_challenge, u8* pi_key );
static int  CSSCracker   ( int i_start, unsigned char * p_crypted,
                           unsigned char * p_decrypted,
                           dvd_key_t * p_sector_key, dvd_key_t * p_key );
#endif /* HAVE_CSS */

/*****************************************************************************
 * CSSTest : check if the disc is encrypted or not
 *****************************************************************************/
int CSSTest( int i_fd )
{
    dvd_struct dvd;

    dvd.type = DVD_STRUCT_COPYRIGHT;
    dvd.copyright.layer_num = 0;

    if( dvd_ioctl( i_fd, DVD_READ_STRUCT, &dvd ) < 0 )
    {
        intf_ErrMsg( "css error: DVD ioctl failed" );
        return -1;
    }

    return dvd.copyright.cpst;
}

/*****************************************************************************
 * CSSInit : CSS Structure initialisation and DVD authentication.
 *****************************************************************************
 * It simulates the mutual authentication between logical unit and host.
 * Since we don't need the disc key to find the title key, we just run the
 * basic unavoidable commands to authenticate device and disc.
 *****************************************************************************/
css_t * CSSInit( int i_fd )
{
#ifdef HAVE_CSS
    /* structures defined in cdrom.h or dvdio.h */
    dvd_struct      dvd;
    dvd_authinfo    auth_info;
    css_t *         p_css;

    int             i_error = -1;
    int             i;

    p_css = malloc( sizeof(css_t) );
    if( p_css == NULL )
    {
        return NULL;
    }

    p_css->i_fd = i_fd;

    memset( &auth_info, 0, sizeof(auth_info) );

    /* Test authentication success */
    switch( CSSGetASF( i_fd ) )
    {
    case -1:
        free( p_css );
        return NULL;
    case 1:
        return p_css;
    case 0:
        intf_WarnMsg( 3, "css info: authenticating" );
    }

    /* Init sequence, request AGID */
    for( i = 1; i < 4 ; ++i )
    {
        intf_WarnMsg( 3, "css info: request AGID %d", i );
        auth_info.type = DVD_LU_SEND_AGID;
        auth_info.lsa.agid = 0;
        i_error =  dvd_ioctl( i_fd, DVD_AUTH, &auth_info );
        if( i_error != -1 )
        {
            /* No error during ioctl: we know if device
             * is authenticated */
            break;
        }

        intf_ErrMsg( "css error: AGID N/A, invalidating" );
        auth_info.type = DVD_INVALIDATE_AGID;
        auth_info.lsa.agid = 0;
        dvd_ioctl( i_fd, DVD_AUTH, &auth_info );
    }

    /* Unable to authenticate without AGID */
    if( i_error == -1 )
    {
        intf_ErrMsg( "css error: could not get AGID" );
        free( p_css );
        return NULL;
    }

    for( i = 0 ; i < 10; ++i )
    {
        p_css->disc.pi_challenge[i] = i;
    }

    /* Send AGID to host */
    auth_info.type = DVD_HOST_SEND_CHALLENGE;

    /* Get challenge from host */
    for( i = 0 ; i < 10 ; ++i )
    {
        auth_info.hsc.chal[9-i] = p_css->disc.pi_challenge[i];
    }
    /* Returning data, let LU change state */
    p_css->i_agid = auth_info.lsa.agid;

    /* Send challenge to LU */
    if( dvd_ioctl( i_fd, DVD_AUTH, &auth_info )<0 )
    {
        intf_ErrMsg( "css error: failed sending challenge to LU" );
        free( p_css );
        return NULL;
    }

    /* Get key1 from LU */
    if( dvd_ioctl( i_fd, DVD_AUTH, &auth_info ) < 0)
    {
        intf_ErrMsg( "css error: failed getting key1 from LU" );
        free( p_css );
        return NULL;
    }

    /* Send key1 to host */
    for( i = 0 ; i < KEY_SIZE ; i++ )
    {
        p_css->disc.pi_key1[i] = auth_info.lsk.key[4-i];
    }

    for( i = 0 ; i < 32 ; ++i )
    {
        CSSCryptKey( 0, i, p_css->disc.pi_challenge,
                           p_css->disc.pi_key_check );

        if( memcmp( p_css->disc.pi_key_check,
                    p_css->disc.pi_key1, KEY_SIZE ) == 0 )
        {
            intf_WarnMsg( 3, "css info: drive authentic, using variant %d", i);
            p_css->disc.i_varient = i;
            auth_info.type = DVD_LU_SEND_CHALLENGE;
            break;
        }
    }

    if( i == 32 )
    {
        intf_ErrMsg( "css error: drive would not authenticate" );
        auth_info.type = DVD_AUTH_FAILURE;
        free( p_css );
        return NULL;
    }

    /* Get challenge from LU */
    if( dvd_ioctl( i_fd, DVD_AUTH, &auth_info ) < 0 )
    {
        intf_ErrMsg( "css error: failed getting challenge from LU" );
        free( p_css );
        return NULL;
    }

    /* Send challenge to host */
    for( i = 0 ; i < 10 ; ++i )
    {
        p_css->disc.pi_challenge[i] = auth_info.hsc.chal[9-i];
    }

    CSSCryptKey( 1, p_css->disc.i_varient, p_css->disc.pi_challenge,
                                                    p_css->disc.pi_key2 );
    auth_info.type = DVD_HOST_SEND_KEY2;

    /* Get key2 from host */
    for( i = 0 ; i < KEY_SIZE ; ++i )
    {
        auth_info.hsk.key[4-i] = p_css->disc.pi_key2[i];
    }
    /* Returning data, let LU change state */

    /* Send key2 to LU */
    if( dvd_ioctl( i_fd, DVD_AUTH, &auth_info ) < 0 )
    {
        intf_ErrMsg( "css error: failed sending key2 to LU (expected)" );
        free( p_css );
        return NULL;
    }

    if( auth_info.type == DVD_AUTH_ESTABLISHED )
    {
        intf_WarnMsg( 3, "css info: authentication established" );
    }
    else if( auth_info.type == DVD_AUTH_FAILURE )
    {
        intf_ErrMsg( "css error: DVD authentication failed" );
        free( p_css );
        return NULL;
    }

    memcpy( p_css->disc.pi_challenge, p_css->disc.pi_key1, KEY_SIZE );
    memcpy( p_css->disc.pi_challenge+KEY_SIZE, p_css->disc.pi_key2, KEY_SIZE );
    CSSCryptKey( 2, p_css->disc.i_varient,
                    p_css->disc.pi_challenge,
                    p_css->disc.pi_key_check );

    intf_WarnMsg( 1, "css info: received Session Key" );

    if( p_css->i_agid < 0 )
    {
        free( p_css );
        return NULL;
    }

    /* Test authentication success */
    switch( CSSGetASF( i_fd ) )
    {
    case -1:
        free( p_css );
        return NULL;
    case 1:
        return p_css;
    case 0:
        intf_WarnMsg( 3, "css info: getting disc key" );
    }

    /* Get encrypted disc key */
    dvd.type = DVD_STRUCT_DISCKEY;
    dvd.disckey.agid = p_css->i_agid;
    memset( dvd.disckey.value, 0, 2048 );

    if( dvd_ioctl( i_fd, DVD_READ_STRUCT, &dvd ) < 0 )
    {
        intf_ErrMsg( "css error: could not read Disc Key" );
        free( p_css );
        return NULL;
    }
#if 1
    /* Unencrypt disc key using bus key */
    for( i = 0 ; i < sizeof(dvd.disckey.value) ; i++ )
    {
        dvd.disckey.value[i] ^= p_css->disc.pi_key_check[4 - (i % KEY_SIZE)];
    }
    memcpy( p_css->disc.pi_key_check, dvd.disckey.value, 2048 );
#endif
    /* Test authentication success */
    switch( CSSGetASF( i_fd ) )
    {
    case -1:
    case 0:
        free( p_css );
        return NULL;
    case 1:
        return p_css;
    }

    return p_css;

#else /* HAVE_CSS */
    intf_ErrMsg( "css error: CSS decryption is disabled in this module" );

    return NULL;
#endif /* HAVE_CSS */
}

/*****************************************************************************
 * CSSEnd : frees css structure
 *****************************************************************************/
void CSSEnd( css_t * p_css )
{
#ifdef HAVE_CSS
    free( p_css );
#else /* HAVE_CSS */
    ;
#endif /* HAVE_CSS */
}

/*****************************************************************************
 * CSSGetKey : get title key.
 *****************************************************************************
 * The DVD should have been opened and authenticated before.
 *****************************************************************************/
int CSSGetKey( css_t * p_css )
{
#ifdef HAVE_CSS
    /*
     * Title key cracking method from Ethan Hawke,
     * with Frank A. Stevenson algorithm.
     * Does not use any player key table and ioctls.
     */
    u8          pi_buf[0x800];
    dvd_key_t   pi_key;
    title_key_t p_title_key[10];
    off_t       i_pos;
    boolean_t   b_encrypted;
    boolean_t   b_stop_scanning;
    int         i_title;
    int         i_bytes_read;
    int         i_best_plen;
    int         i_best_p;
    int         i_registered_keys;
    int         i_total_keys_found;
    int         i_highest;
    int         i,j,k;

    memset( p_title_key, 0, 10 );
    memset( &pi_key, 0, 10 );
    b_encrypted = 0;
    b_stop_scanning = 0;
    i_registered_keys = 0 ;
    i_total_keys_found = 0 ;
    i_highest = 0;

    /* Position of the title on the disc */
    i_title = p_css->i_title;
    i_pos = p_css->i_title_pos;

//fprintf( stderr, "CSS %d start pos: %lld\n", i_title, i_pos );

    do {
    i_pos = lseek( p_css->i_fd, i_pos, SEEK_SET );
    i_bytes_read = read( p_css->i_fd, pi_buf, 0x800 );

    /* PES_scrambling_control */
    if( pi_buf[0x14] & 0x30 )
    {
        b_encrypted = 1;
        i_best_plen = 0;
        i_best_p = 0;

        for( i = 2 ; i < 0x30 ; i++ )
        {
            for( j = i ; ( j < 0x80 ) &&
                   ( pi_buf[0x7F - (j%i)] == pi_buf[0x7F-j] ) ; j++ );
            {
                if( ( j > i_best_plen ) && ( j > i ) )
                {
                    i_best_plen = j;
                    i_best_p = i;
                }
            }
        }

        if( ( i_best_plen > 20 ) && ( i_best_plen / i_best_p >= 2) )
        {
            i = CSSCracker( 0,  &pi_buf[0x80],
                    &pi_buf[0x80 - ( i_best_plen / i_best_p) *i_best_p],
                    (dvd_key_t*)&pi_buf[0x54],
                    &pi_key );
            while( i>=0 )
            {
                k = 0;
                for( j=0 ; j<i_registered_keys ; j++ )
                {
                    if( memcmp( &(p_title_key[j].pi_key),
                                &pi_key, sizeof(dvd_key_t) ) == 0 )
                    {
                        p_title_key[j].i_occ++;
                        i_total_keys_found++;
                        k = 1;
                    }
                }

                if( k == 0 )
                {
                    memcpy( &(p_title_key[i_registered_keys].pi_key),
                                            &pi_key, sizeof(dvd_key_t) );
                    p_title_key[i_registered_keys++].i_occ = 1;
                    i_total_keys_found++;
                }
                i = CSSCracker( i, &pi_buf[0x80],
                    &pi_buf[0x80 - ( i_best_plen / i_best_p) *i_best_p],
                    (dvd_key_t*)&pi_buf[0x54], &pi_key);
            }

            /* Stop search if we find one occurance of the key 
             * I have never found a DVD for which it is not enough
             * but we should take care of that */
            if( i_registered_keys == 1 && p_title_key[0].i_occ >= 1 )
            {
                b_stop_scanning = 1;
            }
        }
    }

    i_pos += i_bytes_read;
    } while( i_bytes_read == 0x800 && !b_stop_scanning);

    if( b_stop_scanning)
    {
        intf_WarnMsg( 1,
            "css info: found enough occurencies of the same key." );
    }

    if( !b_encrypted )
    {
        intf_WarnMsg( 3, "css warning: this file was _NOT_ encrypted!" );
        return(0);
    }

    if( b_encrypted && i_registered_keys == 0 )
    {
        intf_ErrMsg( "css error: unable to determine keys from file" );
        return(1);
    }

    for( i = 0 ; i < i_registered_keys - 1 ; i++ )
    {
        for( j = i + 1 ; j < i_registered_keys ; j++ )
        {
            if( p_title_key[j].i_occ > p_title_key[i].i_occ )
            {
                memcpy( &pi_key, &(p_title_key[j].pi_key), sizeof(dvd_key_t) );
                k = p_title_key[j].i_occ;

                memcpy( &(p_title_key[j].pi_key),
                        &(p_title_key[i].pi_key), sizeof(dvd_key_t) );
                p_title_key[j].i_occ = p_title_key[i].i_occ;

                memcpy( &(p_title_key[i].pi_key),&pi_key, sizeof(dvd_key_t) );
                p_title_key[i].i_occ = k;
            }
        }
    }

#ifdef STATS
    intf_WarnMsg( 1, "css info: key(s) & key probability" );
    intf_WarnMsg( 1, "----------------------------------" );
#endif
    for( i=0 ; i<i_registered_keys ; i++ )
    {
#ifdef STATS
        intf_WarnMsg( 1, "%d) %02X %02X %02X %02X %02X - %3.2f%%", i,
                      p_title_key[i].pi_key[0], p_title_key[i].pi_key[1],
                      p_title_key[i].pi_key[2], p_title_key[i].pi_key[3],
                      p_title_key[i].pi_key[4],
                      p_title_key[i].i_occ * 100.0 / i_total_keys_found );
#endif
        if( p_title_key[i_highest].i_occ * 100.0 / i_total_keys_found
                           <= p_title_key[i].i_occ*100.0 / i_total_keys_found )
        {
            i_highest = i;
        }
    }


    /* The "find the key with the highest probability" code
     * is untested, as I haven't been able to find a VOB that
     * produces multiple keys (RT)
     */
    intf_WarnMsg( 3, "css info: title %d, key %02X %02X %02X %02X %02X",
                  i_title, p_title_key[i_highest].pi_key[0],
                           p_title_key[i_highest].pi_key[1],
                           p_title_key[i_highest].pi_key[2],
                           p_title_key[i_highest].pi_key[3],
                           p_title_key[i_highest].pi_key[4] );

    memcpy( p_css->pi_title_key,
            p_title_key[i_highest].pi_key, KEY_SIZE );

    return 0;
#else /* HAVE_CSS */
    return 1;
#endif /* HAVE_CSS */
}

/*****************************************************************************
 * CSSDescrambleSector
 *****************************************************************************
 * sec : sector to descramble
 * key : title key for this sector
 *****************************************************************************/
int CSSDescrambleSector( dvd_key_t pi_key, u8* pi_sec )
{
#ifdef HAVE_CSS
    unsigned int    i_t1, i_t2, i_t3, i_t4, i_t5, i_t6;
    u8*             pi_end = pi_sec + 0x800;

    /* PES_scrambling_control */
    if( pi_sec[0x14] & 0x30)
    {
        i_t1 = ((pi_key)[0] ^ pi_sec[0x54]) | 0x100;
        i_t2 = (pi_key)[1] ^ pi_sec[0x55];
        i_t3 = (((pi_key)[2]) | ((pi_key)[3] << 8) |
               ((pi_key)[4] << 16)) ^ ((pi_sec[0x56]) |
               (pi_sec[0x57] << 8) | (pi_sec[0x58] << 16));
        i_t4 = i_t3 & 7;
        i_t3 = i_t3 * 2 + 8 - i_t4;
        pi_sec += 0x80;
        i_t5 = 0;

        while( pi_sec != pi_end )
        {
            i_t4 = pi_css_tab2[i_t2] ^ pi_css_tab3[i_t1];
            i_t2 = i_t1>>1;
            i_t1 = ( ( i_t1 & 1 ) << 8 ) ^ i_t4;
            i_t4 = pi_css_tab5[i_t4];
            i_t6 = ((((((( i_t3 >> 3 ) ^ i_t3 ) >> 1 ) ^
                                         i_t3 ) >> 8 ) ^ i_t3 ) >> 5) & 0xff;
            i_t3 = (i_t3 << 8 ) | i_t6;
            i_t6 = pi_css_tab4[i_t6];
            i_t5 += i_t6 + i_t4;
            *pi_sec++ = pi_css_tab1[*pi_sec] ^( i_t5 & 0xff );
            i_t5 >>= 8;
        }
    }

    return 0;
#else /* HAVE_CSS */
    return 1;
#endif /* HAVE_CSS */
}

#ifdef HAVE_CSS
/*
 * Following functions are local
 */

/*****************************************************************************
 * CSSGetASF : Get Authentification success flag
 *****************************************************************************
 * Returns :
 *  -1 on ioctl error,
 *  0 if the device needs to be authenticated,
 *  1 either.
 *****************************************************************************/
static int CSSGetASF( int i_fd )
{
    dvd_authinfo    auth_info;

    auth_info.type = DVD_LU_SEND_ASF;
    auth_info.lsasf.asf = 0;

    for( auth_info.lsasf.agid = 0 ; auth_info.lsasf.agid < 4 ;
                                                    auth_info.lsasf.agid++ )
    {
        if( !( dvd_ioctl( i_fd, DVD_AUTH, &auth_info ) ) )
        {
            intf_WarnMsg( 3, "css info: %sauthenticated",
                          auth_info.lsasf.asf ? "" : "not " );
            return auth_info.lsasf.asf;
        }
    }

    /* The ioctl process has failed */
    intf_ErrMsg( "css error: GetASF fatal error" );
    return -1;
}

/*****************************************************************************
 * CSSCryptKey : shuffles bits and unencrypt keys.
 *****************************************************************************
 * Used during authentication and disc key negociation in CSSInit.
 * i_key_type : 0->key1, 1->key2, 2->buskey.
 * i_varient : between 0 and 31.
 *****************************************************************************/
static void CSSCryptKey( int i_key_type, int i_varient,
                         u8 const * pi_challenge, u8* pi_key )
{
    /* Permutation table for challenge */
    u8      ppi_perm_challenge[3][10] =
            { { 1, 3, 0, 7, 5, 2, 9, 6, 4, 8 },
              { 6, 1, 9, 3, 8, 5, 7, 4, 0, 2 },
              { 4, 0, 3, 5, 7, 2, 8, 6, 1, 9 } };

    /* Permutation table for varient table for key2 and buskey */
    u8      ppi_perm_varient[2][32] =
            { { 0x0a, 0x08, 0x0e, 0x0c, 0x0b, 0x09, 0x0f, 0x0d,
                0x1a, 0x18, 0x1e, 0x1c, 0x1b, 0x19, 0x1f, 0x1d,
                0x02, 0x00, 0x06, 0x04, 0x03, 0x01, 0x07, 0x05,
                0x12, 0x10, 0x16, 0x14, 0x13, 0x11, 0x17, 0x15 },
              { 0x12, 0x1a, 0x16, 0x1e, 0x02, 0x0a, 0x06, 0x0e,
                0x10, 0x18, 0x14, 0x1c, 0x00, 0x08, 0x04, 0x0c,
                0x13, 0x1b, 0x17, 0x1f, 0x03, 0x0b, 0x07, 0x0f,
                0x11, 0x19, 0x15, 0x1d, 0x01, 0x09, 0x05, 0x0d } };

    u8      pi_varients[32] =
            {   0xB7, 0x74, 0x85, 0xD0, 0xCC, 0xDB, 0xCA, 0x73,
                0x03, 0xFE, 0x31, 0x03, 0x52, 0xE0, 0xB7, 0x42,
                0x63, 0x16, 0xF2, 0x2A, 0x79, 0x52, 0xFF, 0x1B,
                0x7A, 0x11, 0xCA, 0x1A, 0x9B, 0x40, 0xAD, 0x01 };

    /* The "secret" key */
    u8      pi_secret[5] = { 0x55, 0xD6, 0xC4, 0xC5, 0x28 };

    u8      pi_bits[30];
    u8      pi_scratch[10];
    u8      pi_tmp1[5];
    u8      pi_tmp2[5];
    u8      i_lfsr0_o;  /* 1 bit used */
    u8      i_lfsr1_o;  /* 1 bit used */
    u32     i_lfsr0;
    u32     i_lfsr1;
    u8      i_css_varient;
    u8      i_cse;
    u8      i_index;
    u8      i_combined;
    u8      i_carry;
    u8      i_val = 0;
    int     i_term = 0;
    int     i_bit;
    int     i;

    for (i = 9; i >= 0; --i)
        pi_scratch[i] = pi_challenge[ppi_perm_challenge[i_key_type][i]];

    i_css_varient = ( i_key_type == 0 ) ? i_varient :
                    ppi_perm_varient[i_key_type-1][i_varient];

    /*
     * This encryption engine implements one of 32 variations
     * one the same theme depending upon the choice in the
     * varient parameter (0 - 31).
     *
     * The algorithm itself manipulates a 40 bit input into
     * a 40 bit output.
     * The parameter 'input' is 80 bits.  It consists of
     * the 40 bit input value that is to be encrypted followed
     * by a 40 bit seed value for the pseudo random number
     * generators.
     */

    /* Feed the secret into the input values such that
     * we alter the seed to the LFSR's used above,  then
     * generate the bits to play with.
     */
    for( i = 5 ; --i >= 0 ; )
    {
        pi_tmp1[i] = pi_scratch[5 + i] ^ pi_secret[i] ^ pi_crypt_tab2[i];
    }

    /*
     * We use two LFSR's (seeded from some of the input data bytes) to
     * generate two streams of pseudo-random bits.  These two bit streams
     * are then combined by simply adding with carry to generate a final
     * sequence of pseudo-random bits which is stored in the buffer that
     * 'output' points to the end of - len is the size of this buffer.
     *
     * The first LFSR is of degree 25,  and has a polynomial of:
     * x^13 + x^5 + x^4 + x^1 + 1
     *
     * The second LSFR is of degree 17,  and has a (primitive) polynomial of:
     * x^15 + x^1 + 1
     *
     * I don't know if these polynomials are primitive modulo 2,  and thus
     * represent maximal-period LFSR's.
     *
     *
     * Note that we take the output of each LFSR from the new shifted in
     * bit,  not the old shifted out bit.  Thus for ease of use the LFSR's
     * are implemented in bit reversed order.
     *
     */
    
    /* In order to ensure that the LFSR works we need to ensure that the
     * initial values are non-zero.  Thus when we initialise them from
     * the seed,  we ensure that a bit is set.
     */
    i_lfsr0 = ( pi_tmp1[0] << 17 ) | ( pi_tmp1[1] << 9 ) |
              (( pi_tmp1[2] & ~7 ) << 1 ) | 8 | ( pi_tmp1[2] & 7 );
    i_lfsr1 = ( pi_tmp1[3] << 9 ) | 0x100 | pi_tmp1[4];

    i_index = sizeof(pi_bits);
    i_carry = 0;

    do
    {
        for( i_bit = 0, i_val = 0 ; i_bit < 8 ; ++i_bit )
        {

            i_lfsr0_o = ( ( i_lfsr0 >> 24 ) ^ ( i_lfsr0 >> 21 ) ^
                        ( i_lfsr0 >> 20 ) ^ ( i_lfsr0 >> 12 ) ) & 1;
            i_lfsr0 = ( i_lfsr0 << 1 ) | i_lfsr0_o;

            i_lfsr1_o = ( ( i_lfsr1 >> 16 ) ^ ( i_lfsr1 >> 2 ) ) & 1;
            i_lfsr1 = ( i_lfsr1 << 1 ) | i_lfsr1_o;

            i_combined = !i_lfsr1_o + i_carry + !i_lfsr0_o;
            /* taking bit 1 */
            i_carry = ( i_combined >> 1 ) & 1;
            i_val |= ( i_combined & 1 ) << i_bit;
        }
    
        pi_bits[--i_index] = i_val;
    } while( i_index > 0 );

    /* This term is used throughout the following to
     * select one of 32 different variations on the
     * algorithm.
     */
    i_cse = pi_varients[i_css_varient] ^ pi_crypt_tab2[i_css_varient];

    /* Now the actual blocks doing the encryption.  Each
     * of these works on 40 bits at a time and are quite
     * similar.
     */
    i_index = 0;
    for( i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_scratch[i] )
    {
        i_index = pi_bits[25 + i] ^ pi_scratch[i];
        i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;

        pi_tmp1[i] = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;
    }
    pi_tmp1[4] ^= pi_tmp1[0];

    for( i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_tmp1[i] )
    {
        i_index = pi_bits[20 + i] ^ pi_tmp1[i];
        i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;

        pi_tmp2[i] = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;
    }
    pi_tmp2[4] ^= pi_tmp2[0];

    for( i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_tmp2[i] )
    {
        i_index = pi_bits[15 + i] ^ pi_tmp2[i];
        i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;
        i_index = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;

        pi_tmp1[i] = pi_crypt_tab0[i_index] ^ pi_crypt_tab2[i_index];
    }
    pi_tmp1[4] ^= pi_tmp1[0];

    for( i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_tmp1[i] )
    {
        i_index = pi_bits[10 + i] ^ pi_tmp1[i];
        i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;

        i_index = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;

        pi_tmp2[i] = pi_crypt_tab0[i_index] ^ pi_crypt_tab2[i_index];
    }
    pi_tmp2[4] ^= pi_tmp2[0];

    for( i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_tmp2[i] )
    {
        i_index = pi_bits[5 + i] ^ pi_tmp2[i];
        i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;

        pi_tmp1[i] = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;
    }
    pi_tmp1[4] ^= pi_tmp1[0];

    for(i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_tmp1[i] )
    {
        i_index = pi_bits[i] ^ pi_tmp1[i];
        i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;

        pi_key[i] = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;
    }

    return;
}

/*****************************************************************************
 * CSSCracker : title key decryption by cracking
 *****************************************************************************
 * This function is called by CSSGetKeys to find a key
 *****************************************************************************/
static int CSSCracker( int i_start,
                       unsigned char * p_crypted,
                       unsigned char * p_decrypted,
                       dvd_key_t * p_sector_key,
                       dvd_key_t * p_key )
{
    unsigned char pi_buffer[10];
    unsigned int i_t1, i_t2, i_t3, i_t4, i_t5, i_t6;
    unsigned int i_try;
    unsigned int i_candidate;
    unsigned int i, j;
    int i_exit = -1;


    for( i = 0 ; i < 10 ; i++ )
    {
        pi_buffer[i] = pi_css_tab1[p_crypted[i]] ^ p_decrypted[i];
    }

    for( i_try = i_start ; i_try < 0x10000 ; i_try++ )
    {
        i_t1 = i_try >> 8 | 0x100;
        i_t2 = i_try & 0xff;
        i_t3 = 0;               /* not needed */
        i_t5 = 0;

        /* iterate cipher 4 times to reconstruct LFSR2 */
        for( i = 0 ; i < 4 ; i++ )
        {
            /* advance LFSR1 normaly */
            i_t4 = pi_css_tab2[i_t2] ^ pi_css_tab3[i_t1];
            i_t2 = i_t1 >> 1;
            i_t1 = ( ( i_t1 & 1 ) << 8 ) ^ i_t4;
            i_t4 = pi_css_tab5[i_t4];
            /* deduce i_t6 & i_t5 */
            i_t6 = pi_buffer[i];
            if( i_t5 )
            {
                i_t6 = ( i_t6 + 0xff ) & 0x0ff;
            }
            if( i_t6 < i_t4 )
            {
                i_t6 += 0x100;
            }
            i_t6 -= i_t4;
            i_t5 += i_t6 + i_t4;
            i_t6 = pi_css_tab4[ i_t6 ];
            /* feed / advance i_t3 / i_t5 */
            i_t3 = ( i_t3 << 8 ) | i_t6;
            i_t5 >>= 8;
        }

        i_candidate = i_t3;

        /* iterate 6 more times to validate candidate key */
        for( ; i < 10 ; i++ )
        {
            i_t4 = pi_css_tab2[i_t2] ^ pi_css_tab3[i_t1];
            i_t2 = i_t1 >> 1;
            i_t1 = ( ( i_t1 & 1 ) << 8 ) ^ i_t4;
            i_t4 = pi_css_tab5[i_t4];
            i_t6 = ((((((( i_t3 >> 3 ) ^ i_t3 ) >> 1 ) ^
                                         i_t3 ) >> 8 ) ^ i_t3 ) >> 5 ) & 0xff;
            i_t3 = ( i_t3 << 8 ) | i_t6;
            i_t6 = pi_css_tab4[i_t6];
            i_t5 += i_t6 + i_t4;
            if( ( i_t5 & 0xff ) != pi_buffer[i] )
            {
                break;
            }

            i_t5 >>= 8;
        }

        if( i == 10 )
        {
            /* Do 4 backwards steps of iterating t3 to deduce initial state */
            i_t3 = i_candidate;
            for( i = 0 ; i < 4 ; i++ )
            {
                i_t1 = i_t3 & 0xff;
                i_t3 = ( i_t3 >> 8 );
                /* easy to code, and fast enough bruteforce
                 * search for byte shifted in */
                for( j = 0 ; j < 256 ; j++ )
                {
                    i_t3 = ( i_t3 & 0x1ffff) | ( j << 17 );
                    i_t6 = ((((((( i_t3 >> 3 ) ^ i_t3 ) >> 1 ) ^
                                   i_t3 ) >> 8 ) ^ i_t3 ) >> 5 ) & 0xff;
                    if( i_t6 == i_t1 )
                    {
                        break;
                    }
                }
            }

            i_t4 = ( i_t3 >> 1 ) - 4;
            for( i_t5 = 0 ; i_t5 < 8; i_t5++ )
            {
                if( ( ( i_t4 + i_t5 ) * 2 + 8 - ( (i_t4 + i_t5 ) & 7 ) )
                                                                      == i_t3 )
                {
                    (*p_key)[0] = i_try>>8;
                    (*p_key)[1] = i_try & 0xFF;
                    (*p_key)[2] = ( ( i_t4 + i_t5 ) >> 0) & 0xFF;
                    (*p_key)[3] = ( ( i_t4 + i_t5 ) >> 8) & 0xFF;
                    (*p_key)[4] = ( ( i_t4 + i_t5 ) >> 16) & 0xFF;
                    i_exit = i_try + 1;
                }
            }
        }
    }

    if( i_exit >= 0 )
    {
        (*p_key)[0] ^= (*p_sector_key)[0];
        (*p_key)[1] ^= (*p_sector_key)[1];
        (*p_key)[2] ^= (*p_sector_key)[2];
        (*p_key)[3] ^= (*p_sector_key)[3];
        (*p_key)[4] ^= (*p_sector_key)[4];
    }

    return i_exit;
}
#endif /* HAVE_CSS */