git.sesse.net Git - vlc/blob - plugins/dvd/dvd_css.c

   1 /*****************************************************************************
   2  * dvd_css.c: Functions for DVD authentification and unscrambling
   3  *****************************************************************************
   4  * Copyright (C) 1999-2001 VideoLAN
   5  * $Id: dvd_css.c,v 1.21 2001/04/06 09:15:47 sam Exp $
   6  *
   7  * Author: Stéphane Borel <stef@via.ecp.fr>
   8  *
   9  * based on:
  10  *  - css-auth by Derek Fawcus <derek@spider.com>
  11  *  - DVD CSS ioctls example program by Andrew T. Veliath <andrewtv@usa.net>
  12  *  - The Divide and conquer attack by Frank A. Stevenson <frank@funcom.com>
  13  *  - DeCSSPlus by Ethan Hawke
  14  *  - DecVOB
  15  *  see http://www.lemuria.org/DeCSS/ by Tom Vogt for more information.
  16  *
  17  * This program is free software; you can redistribute it and/or modify
  18  * it under the terms of the GNU General Public License as published by
  19  * the Free Software Foundation; either version 2 of the License, or
  20  * (at your option) any later version.
  21  *
  22  * This program is distributed in the hope that it will be useful,
  23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  25  * GNU General Public License for more details.
  26  *
  27  * You should have received a copy of the GNU General Public License
  28  * along with this program; if not, write to the Free Software
  29  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA.
  30  *****************************************************************************/
  31
  32 /*****************************************************************************
  33  * Preamble
  34  *****************************************************************************/
  35 #include "defs.h"
  36
  37 #include <stdio.h>
  38 #include <stdlib.h>
  39 #include <unistd.h>
  40 #include <string.h>
  41
  42 #include "common.h"
  43
  44 #include "intf_msg.h"
  45
  46 #include "dvd_css.h"
  47 #ifdef HAVE_CSS
  48 #include "dvd_csstables.h"
  49 #endif /* HAVE_CSS */
  50 #include "dvd_ioctl.h"
  51 #include "dvd_ifo.h"
  52
  53 #include "input_dvd.h"
  54
  55 /*****************************************************************************
  56  * Local prototypes
  57  *****************************************************************************/
  58 #ifdef HAVE_CSS
  59 static int  CSSGetASF    ( css_t *p_css );
  60 static void CSSCryptKey  ( int i_key_type, int i_varient,
  61                            u8 const * pi_challenge, u8* pi_key );
  62 static int  CSSCracker   ( int i_start, unsigned char * p_crypted,
  63                            unsigned char * p_decrypted,
  64                            dvd_key_t * p_sector_key, dvd_key_t * p_key );
  65 #endif /* HAVE_CSS */
  66
  67 /*****************************************************************************
  68  * CSSTest : check if the disc is encrypted or not
  69  *****************************************************************************/
  70 int CSSTest( int i_fd )
  71 {
  72     int i_ret, i_copyright;
  73
  74     i_ret = ioctl_ReadCopyright( i_fd, 0 /* i_layer */, &i_copyright );
  75
  76     if( i_ret < 0 )
  77     {
  78         return i_ret;
  79     }
  80
  81     return i_copyright;
  82 }
  83
  84 /*****************************************************************************
  85  * CSSInit : CSS Structure initialisation and DVD authentication.
  86  *****************************************************************************
  87  * It simulates the mutual authentication between logical unit and host.
  88  * Since we don't need the disc key to find the title key, we just run the
  89  * basic unavoidable commands to authenticate device and disc.
  90  *****************************************************************************/
  91 int CSSInit( css_t * p_css )
  92 {
  93 #ifdef HAVE_CSS
  94     /* structures defined in cdrom.h or dvdio.h */
  95     char p_buffer[2048 + 4 + 1];
  96     int  i_ret = -1;
  97     int  i;
  98
  99     p_css->i_agid = 0;
 100
 101     /* Test authentication success */
 102     switch( CSSGetASF( p_css ) )
 103     {
 104         case -1:
 105             return -1;
 106
 107         case 1:
 108             intf_WarnMsg( 3, "css info: already authenticated" );
 109             return 0;
 110
 111         case 0:
 112             intf_WarnMsg( 3, "css info: need to authenticate" );
 113     }
 114
 115     /* Init sequence, request AGID */
 116     for( i = 1; i < 4 ; ++i )
 117     {
 118         intf_WarnMsg( 3, "css info: requesting AGID %d", i );
 119
 120         i_ret = ioctl_LUSendAgid( p_css );
 121
 122         if( i_ret != -1 )
 123         {
 124             /* No error during ioctl: we know the device is authenticated */
 125             break;
 126         }
 127
 128         intf_ErrMsg( "css error: AGID N/A, invalidating" );
 129
 130         p_css->i_agid = 0;
 131         ioctl_InvalidateAgid( p_css );
 132     }
 133
 134     /* Unable to authenticate without AGID */
 135     if( i_ret == -1 )
 136     {
 137         intf_ErrMsg( "css error: could not get AGID" );
 138         return -1;
 139     }
 140
 141     for( i = 0 ; i < 10; ++i )
 142     {
 143         p_css->disc.pi_challenge[i] = i;
 144     }
 145
 146     /* Get challenge from host */
 147     for( i = 0 ; i < 10 ; ++i )
 148     {
 149         p_buffer[9-i] = p_css->disc.pi_challenge[i];
 150     }
 151
 152     /* Send challenge to LU */
 153     if( ioctl_HostSendChallenge( p_css, p_buffer ) < 0 )
 154     {
 155         intf_ErrMsg( "css error: failed sending challenge to LU" );
 156         return -1;
 157     }
 158
 159     /* Get key1 from LU */
 160     if( ioctl_LUSendKey1( p_css, p_buffer ) < 0)
 161     {
 162         intf_ErrMsg( "css error: failed getting key1 from LU" );
 163         return -1;
 164     }
 165
 166     /* Send key1 to host */
 167     for( i = 0 ; i < KEY_SIZE ; i++ )
 168     {
 169         p_css->disc.pi_key1[i] = p_buffer[4-i];
 170     }
 171
 172     for( i = 0 ; i < 32 ; ++i )
 173     {
 174         CSSCryptKey( 0, i, p_css->disc.pi_challenge,
 175                            p_css->disc.pi_key_check );
 176
 177         if( memcmp( p_css->disc.pi_key_check,
 178                     p_css->disc.pi_key1, KEY_SIZE ) == 0 )
 179         {
 180             intf_WarnMsg( 3, "css info: drive authentic, using variant %d", i);
 181             p_css->disc.i_varient = i;
 182             break;
 183         }
 184     }
 185
 186     if( i == 32 )
 187     {
 188         intf_ErrMsg( "css error: drive would not authenticate" );
 189         return -1;
 190     }
 191
 192     /* Get challenge from LU */
 193     if( ioctl_LUSendChallenge( p_css, p_buffer ) < 0 )
 194     {
 195         intf_ErrMsg( "css error: failed getting challenge from LU" );
 196         return -1;
 197     }
 198
 199     /* Send challenge to host */
 200     for( i = 0 ; i < 10 ; ++i )
 201     {
 202         p_css->disc.pi_challenge[i] = p_buffer[9-i];
 203     }
 204
 205     CSSCryptKey( 1, p_css->disc.i_varient, p_css->disc.pi_challenge,
 206                                                p_css->disc.pi_key2 );
 207
 208     /* Get key2 from host */
 209     for( i = 0 ; i < KEY_SIZE ; ++i )
 210     {
 211         p_buffer[4-i] = p_css->disc.pi_key2[i];
 212     }
 213
 214     /* Send key2 to LU */
 215     if( ioctl_HostSendKey2( p_css, p_buffer ) < 0 )
 216     {
 217         intf_ErrMsg( "css error: failed sending key2 to LU" );
 218         return -1;
 219     }
 220
 221     intf_WarnMsg( 3, "css info: authentication established" );
 222
 223     memcpy( p_css->disc.pi_challenge, p_css->disc.pi_key1, KEY_SIZE );
 224     memcpy( p_css->disc.pi_challenge+KEY_SIZE, p_css->disc.pi_key2, KEY_SIZE );
 225     CSSCryptKey( 2, p_css->disc.i_varient, p_css->disc.pi_challenge,
 226                                                p_css->disc.pi_key_check );
 227
 228     intf_WarnMsg( 1, "css info: received Session Key" );
 229
 230     if( p_css->i_agid < 0 )
 231     {
 232         return -1;
 233     }
 234
 235     /* Test authentication success */
 236     switch( CSSGetASF( p_css ) )
 237     {
 238         case -1:
 239             return -1;
 240
 241         case 1:
 242             intf_WarnMsg( 3, "css info: already authenticated" );
 243             return 0;
 244
 245         case 0:
 246             intf_WarnMsg( 3, "css info: need to get disc key" );
 247     }
 248
 249     /* Get encrypted disc key */
 250     if( ioctl_ReadKey( p_css, p_buffer ) < 0 )
 251     {
 252         intf_ErrMsg( "css error: could not read Disc Key" );
 253         return -1;
 254     }
 255
 256     /* Unencrypt disc key using bus key */
 257     for( i = 0 ; i < 2048 ; i++ )
 258     {
 259         p_buffer[ i ] ^= p_css->disc.pi_key_check[ 4 - (i % KEY_SIZE) ];
 260     }
 261     memcpy( p_css->disc.pi_key_check, p_buffer, 2048 );
 262
 263     /* Test authentication success */
 264     switch( CSSGetASF( p_css ) )
 265     {
 266         case -1:
 267             return -1;
 268
 269         case 1:
 270             intf_WarnMsg( 3, "css info: successfully authenticated" );
 271             return 0;
 272
 273         case 0:
 274             intf_WarnMsg( 3, "css info: no way to authenticate" );
 275     }
 276
 277 #else /* HAVE_CSS */
 278     intf_ErrMsg( "css error: CSS decryption is disabled in this module" );
 279
 280 #endif /* HAVE_CSS */
 281     return -1;
 282
 283 }
 284
 285 /*****************************************************************************
 286  * CSSEnd : frees css structure
 287  *****************************************************************************/
 288 void CSSEnd( css_t * p_css )
 289 {
 290 #ifdef HAVE_CSS
 291     free( p_css );
 292 #else /* HAVE_CSS */
 293     ;
 294 #endif /* HAVE_CSS */
 295 }
 296
 297 /*****************************************************************************
 298  * CSSGetKey : get title key.
 299  *****************************************************************************
 300  * The DVD should have been opened and authenticated before.
 301  *****************************************************************************/
 302 int CSSGetKey( css_t * p_css )
 303 {
 304 #ifdef HAVE_CSS
 305     /*
 306      * Title key cracking method from Ethan Hawke,
 307      * with Frank A. Stevenson algorithm.
 308      * Does not use any player key table and ioctls.
 309      */
 310     u8          pi_buf[0x800];
 311     dvd_key_t   pi_key;
 312     title_key_t p_title_key[10];
 313     off_t       i_pos;
 314     boolean_t   b_encrypted;
 315     boolean_t   b_stop_scanning;
 316     int         i_title;
 317     int         i_bytes_read;
 318     int         i_best_plen;
 319     int         i_best_p;
 320     int         i_registered_keys;
 321     int         i_total_keys_found;
 322     int         i_highest;
 323     int         i,j,k;
 324
 325     memset( p_title_key, 0, 10 );
 326     memset( &pi_key, 0, 10 );
 327     b_encrypted = 0;
 328     b_stop_scanning = 0;
 329     i_registered_keys = 0 ;
 330     i_total_keys_found = 0 ;
 331     i_highest = 0;
 332
 333     /* Position of the title on the disc */
 334     i_title = p_css->i_title;
 335     i_pos = p_css->i_title_pos;
 336
 337 //fprintf( stderr, "CSS %d start pos: %lld\n", i_title, i_pos );
 338
 339     do {
 340     i_pos = lseek( p_css->i_fd, i_pos, SEEK_SET );
 341     i_bytes_read = read( p_css->i_fd, pi_buf, 0x800 );
 342
 343     /* PES_scrambling_control */
 344     if( pi_buf[0x14] & 0x30 )
 345     {
 346         b_encrypted = 1;
 347         i_best_plen = 0;
 348         i_best_p = 0;
 349
 350         for( i = 2 ; i < 0x30 ; i++ )
 351         {
 352             for( j = i ; ( j < 0x80 ) &&
 353                    ( pi_buf[0x7F - (j%i)] == pi_buf[0x7F-j] ) ; j++ );
 354             {
 355                 if( ( j > i_best_plen ) && ( j > i ) )
 356                 {
 357                     i_best_plen = j;
 358                     i_best_p = i;
 359                 }
 360             }
 361         }
 362
 363         if( ( i_best_plen > 20 ) && ( i_best_plen / i_best_p >= 2) )
 364         {
 365             i = CSSCracker( 0,  &pi_buf[0x80],
 366                     &pi_buf[0x80 - ( i_best_plen / i_best_p) *i_best_p],
 367                     (dvd_key_t*)&pi_buf[0x54],
 368                     &pi_key );
 369             while( i>=0 )
 370             {
 371                 k = 0;
 372                 for( j=0 ; j<i_registered_keys ; j++ )
 373                 {
 374                     if( memcmp( &(p_title_key[j].pi_key),
 375                                 &pi_key, sizeof(dvd_key_t) ) == 0 )
 376                     {
 377                         p_title_key[j].i_occ++;
 378                         i_total_keys_found++;
 379                         k = 1;
 380                     }
 381                 }
 382
 383                 if( k == 0 )
 384                 {
 385                     memcpy( &(p_title_key[i_registered_keys].pi_key),
 386                                             &pi_key, sizeof(dvd_key_t) );
 387                     p_title_key[i_registered_keys++].i_occ = 1;
 388                     i_total_keys_found++;
 389                 }
 390                 i = CSSCracker( i, &pi_buf[0x80],
 391                     &pi_buf[0x80 - ( i_best_plen / i_best_p) *i_best_p],
 392                     (dvd_key_t*)&pi_buf[0x54], &pi_key);
 393             }
 394
 395             /* Stop search if we find one occurence of the key
 396              * I have never found a DVD for which it is not enough
 397              * but we should take care of that */
 398             if( i_registered_keys == 1 && p_title_key[0].i_occ >= 1 )
 399             {
 400                 b_stop_scanning = 1;
 401             }
 402         }
 403     }
 404
 405     i_pos += i_bytes_read;
 406     } while( i_bytes_read == 0x800 && !b_stop_scanning);
 407
 408     if( b_stop_scanning)
 409     {
 410         intf_WarnMsg( 1,
 411             "css info: found enough occurencies of the same key." );
 412     }
 413
 414     if( !b_encrypted )
 415     {
 416         intf_WarnMsg( 3, "css warning: this file was _NOT_ encrypted!" );
 417         return(0);
 418     }
 419
 420     if( b_encrypted && i_registered_keys == 0 )
 421     {
 422         intf_ErrMsg( "css error: unable to determine keys from file" );
 423         return(1);
 424     }
 425
 426     for( i = 0 ; i < i_registered_keys - 1 ; i++ )
 427     {
 428         for( j = i + 1 ; j < i_registered_keys ; j++ )
 429         {
 430             if( p_title_key[j].i_occ > p_title_key[i].i_occ )
 431             {
 432                 memcpy( &pi_key, &(p_title_key[j].pi_key), sizeof(dvd_key_t) );
 433                 k = p_title_key[j].i_occ;
 434
 435                 memcpy( &(p_title_key[j].pi_key),
 436                         &(p_title_key[i].pi_key), sizeof(dvd_key_t) );
 437                 p_title_key[j].i_occ = p_title_key[i].i_occ;
 438
 439                 memcpy( &(p_title_key[i].pi_key),&pi_key, sizeof(dvd_key_t) );
 440                 p_title_key[i].i_occ = k;
 441             }
 442         }
 443     }
 444
 445 #ifdef STATS
 446     intf_WarnMsg( 1, "css info: key(s) & key probability" );
 447     intf_WarnMsg( 1, "----------------------------------" );
 448 #endif
 449     for( i=0 ; i<i_registered_keys ; i++ )
 450     {
 451 #ifdef STATS
 452         intf_WarnMsg( 1, "%d) %02X %02X %02X %02X %02X - %3.2f%%", i,
 453                       p_title_key[i].pi_key[0], p_title_key[i].pi_key[1],
 454                       p_title_key[i].pi_key[2], p_title_key[i].pi_key[3],
 455                       p_title_key[i].pi_key[4],
 456                       p_title_key[i].i_occ * 100.0 / i_total_keys_found );
 457 #endif
 458         if( p_title_key[i_highest].i_occ * 100.0 / i_total_keys_found
 459                            <= p_title_key[i].i_occ*100.0 / i_total_keys_found )
 460         {
 461             i_highest = i;
 462         }
 463     }
 464
 465
 466     /* The "find the key with the highest probability" code
 467      * is untested, as I haven't been able to find a VOB that
 468      * produces multiple keys (RT)
 469      */
 470     intf_WarnMsg( 3, "css info: title %d, key %02X %02X %02X %02X %02X",
 471                   i_title, p_title_key[i_highest].pi_key[0],
 472                            p_title_key[i_highest].pi_key[1],
 473                            p_title_key[i_highest].pi_key[2],
 474                            p_title_key[i_highest].pi_key[3],
 475                            p_title_key[i_highest].pi_key[4] );
 476
 477     memcpy( p_css->pi_title_key,
 478             p_title_key[i_highest].pi_key, KEY_SIZE );
 479
 480     return 0;
 481
 482 #else /* HAVE_CSS */
 483     return 1;
 484
 485 #endif /* HAVE_CSS */
 486 }
 487
 488 /*****************************************************************************
 489  * CSSDescrambleSector
 490  *****************************************************************************
 491  * sec : sector to descramble
 492  * key : title key for this sector
 493  *****************************************************************************/
 494 int CSSDescrambleSector( dvd_key_t pi_key, u8* pi_sec )
 495 {
 496 #ifdef HAVE_CSS
 497     unsigned int    i_t1, i_t2, i_t3, i_t4, i_t5, i_t6;
 498     u8*             pi_end = pi_sec + 0x800;
 499
 500     /* PES_scrambling_control */
 501     if( pi_sec[0x14] & 0x30)
 502     {
 503         i_t1 = ((pi_key)[0] ^ pi_sec[0x54]) | 0x100;
 504         i_t2 = (pi_key)[1] ^ pi_sec[0x55];
 505         i_t3 = (((pi_key)[2]) | ((pi_key)[3] << 8) |
 506                ((pi_key)[4] << 16)) ^ ((pi_sec[0x56]) |
 507                (pi_sec[0x57] << 8) | (pi_sec[0x58] << 16));
 508         i_t4 = i_t3 & 7;
 509         i_t3 = i_t3 * 2 + 8 - i_t4;
 510         pi_sec += 0x80;
 511         i_t5 = 0;
 512
 513         while( pi_sec != pi_end )
 514         {
 515             i_t4 = pi_css_tab2[i_t2] ^ pi_css_tab3[i_t1];
 516             i_t2 = i_t1>>1;
 517             i_t1 = ( ( i_t1 & 1 ) << 8 ) ^ i_t4;
 518             i_t4 = pi_css_tab5[i_t4];
 519             i_t6 = ((((((( i_t3 >> 3 ) ^ i_t3 ) >> 1 ) ^
 520                                          i_t3 ) >> 8 ) ^ i_t3 ) >> 5) & 0xff;
 521             i_t3 = (i_t3 << 8 ) | i_t6;
 522             i_t6 = pi_css_tab4[i_t6];
 523             i_t5 += i_t6 + i_t4;
 524             *pi_sec = pi_css_tab1[*pi_sec] ^( i_t5 & 0xff );
 525             pi_sec++;
 526             i_t5 >>= 8;
 527         }
 528     }
 529
 530     return 0;
 531
 532 #else /* HAVE_CSS */
 533     return 1;
 534
 535 #endif /* HAVE_CSS */
 536 }
 537
 538 #ifdef HAVE_CSS
 539
 540 /* Following functions are local */
 541
 542 /*****************************************************************************
 543  * CSSGetASF : Get Authentification success flag
 544  *****************************************************************************
 545  * Returns :
 546  *  -1 on ioctl error,
 547  *  0 if the device needs to be authenticated,
 548  *  1 either.
 549  *****************************************************************************/
 550 static int CSSGetASF( css_t *p_css )
 551 {
 552     int i_oldagid = p_css->i_agid, i_asf = 0;
 553
 554     for( p_css->i_agid = 0 ; p_css->i_agid < 4 ; p_css->i_agid++ )
 555     {
 556         if( ioctl_LUSendASF( p_css, &i_asf ) == 0 )
 557         {
 558             intf_WarnMsg( 3, "css info: %sauthenticated", i_asf ? "":"not " );
 559
 560             p_css->i_agid = i_oldagid;
 561             return i_asf;
 562         }
 563     }
 564
 565     /* The ioctl process has failed */
 566     intf_ErrMsg( "css error: GetASF fatal error" );
 567
 568     p_css->i_agid = i_oldagid;
 569     return -1;
 570 }
 571
 572 /*****************************************************************************
 573  * CSSCryptKey : shuffles bits and unencrypt keys.
 574  *****************************************************************************
 575  * Used during authentication and disc key negociation in CSSInit.
 576  * i_key_type : 0->key1, 1->key2, 2->buskey.
 577  * i_varient : between 0 and 31.
 578  *****************************************************************************/
 579 static void CSSCryptKey( int i_key_type, int i_varient,
 580                          u8 const * pi_challenge, u8* pi_key )
 581 {
 582     /* Permutation table for challenge */
 583     u8      ppi_perm_challenge[3][10] =
 584             { { 1, 3, 0, 7, 5, 2, 9, 6, 4, 8 },
 585               { 6, 1, 9, 3, 8, 5, 7, 4, 0, 2 },
 586               { 4, 0, 3, 5, 7, 2, 8, 6, 1, 9 } };
 587
 588     /* Permutation table for varient table for key2 and buskey */
 589     u8      ppi_perm_varient[2][32] =
 590             { { 0x0a, 0x08, 0x0e, 0x0c, 0x0b, 0x09, 0x0f, 0x0d,
 591                 0x1a, 0x18, 0x1e, 0x1c, 0x1b, 0x19, 0x1f, 0x1d,
 592                 0x02, 0x00, 0x06, 0x04, 0x03, 0x01, 0x07, 0x05,
 593                 0x12, 0x10, 0x16, 0x14, 0x13, 0x11, 0x17, 0x15 },
 594               { 0x12, 0x1a, 0x16, 0x1e, 0x02, 0x0a, 0x06, 0x0e,
 595                 0x10, 0x18, 0x14, 0x1c, 0x00, 0x08, 0x04, 0x0c,
 596                 0x13, 0x1b, 0x17, 0x1f, 0x03, 0x0b, 0x07, 0x0f,
 597                 0x11, 0x19, 0x15, 0x1d, 0x01, 0x09, 0x05, 0x0d } };
 598
 599     u8      pi_varients[32] =
 600             {   0xB7, 0x74, 0x85, 0xD0, 0xCC, 0xDB, 0xCA, 0x73,
 601                 0x03, 0xFE, 0x31, 0x03, 0x52, 0xE0, 0xB7, 0x42,
 602                 0x63, 0x16, 0xF2, 0x2A, 0x79, 0x52, 0xFF, 0x1B,
 603                 0x7A, 0x11, 0xCA, 0x1A, 0x9B, 0x40, 0xAD, 0x01 };
 604
 605     /* The "secret" key */
 606     u8      pi_secret[5] = { 0x55, 0xD6, 0xC4, 0xC5, 0x28 };
 607
 608     u8      pi_bits[30];
 609     u8      pi_scratch[10];
 610     u8      pi_tmp1[5];
 611     u8      pi_tmp2[5];
 612     u8      i_lfsr0_o;  /* 1 bit used */
 613     u8      i_lfsr1_o;  /* 1 bit used */
 614     u32     i_lfsr0;
 615     u32     i_lfsr1;
 616     u8      i_css_varient;
 617     u8      i_cse;
 618     u8      i_index;
 619     u8      i_combined;
 620     u8      i_carry;
 621     u8      i_val = 0;
 622     int     i_term = 0;
 623     int     i_bit;
 624     int     i;
 625
 626     for (i = 9; i >= 0; --i)
 627         pi_scratch[i] = pi_challenge[ppi_perm_challenge[i_key_type][i]];
 628
 629     i_css_varient = ( i_key_type == 0 ) ? i_varient :
 630                     ppi_perm_varient[i_key_type-1][i_varient];
 631
 632     /*
 633      * This encryption engine implements one of 32 variations
 634      * one the same theme depending upon the choice in the
 635      * varient parameter (0 - 31).
 636      *
 637      * The algorithm itself manipulates a 40 bit input into
 638      * a 40 bit output.
 639      * The parameter 'input' is 80 bits.  It consists of
 640      * the 40 bit input value that is to be encrypted followed
 641      * by a 40 bit seed value for the pseudo random number
 642      * generators.
 643      */
 644
 645     /* Feed the secret into the input values such that
 646      * we alter the seed to the LFSR's used above,  then
 647      * generate the bits to play with.
 648      */
 649     for( i = 5 ; --i >= 0 ; )
 650     {
 651         pi_tmp1[i] = pi_scratch[5 + i] ^ pi_secret[i] ^ pi_crypt_tab2[i];
 652     }
 653
 654     /*
 655      * We use two LFSR's (seeded from some of the input data bytes) to
 656      * generate two streams of pseudo-random bits.  These two bit streams
 657      * are then combined by simply adding with carry to generate a final
 658      * sequence of pseudo-random bits which is stored in the buffer that
 659      * 'output' points to the end of - len is the size of this buffer.
 660      *
 661      * The first LFSR is of degree 25,  and has a polynomial of:
 662      * x^13 + x^5 + x^4 + x^1 + 1
 663      *
 664      * The second LSFR is of degree 17,  and has a (primitive) polynomial of:
 665      * x^15 + x^1 + 1
 666      *
 667      * I don't know if these polynomials are primitive modulo 2,  and thus
 668      * represent maximal-period LFSR's.
 669      *
 670      *
 671      * Note that we take the output of each LFSR from the new shifted in
 672      * bit,  not the old shifted out bit.  Thus for ease of use the LFSR's
 673      * are implemented in bit reversed order.
 674      *
 675      */
 676
 677     /* In order to ensure that the LFSR works we need to ensure that the
 678      * initial values are non-zero.  Thus when we initialise them from
 679      * the seed,  we ensure that a bit is set.
 680      */
 681     i_lfsr0 = ( pi_tmp1[0] << 17 ) | ( pi_tmp1[1] << 9 ) |
 682               (( pi_tmp1[2] & ~7 ) << 1 ) | 8 | ( pi_tmp1[2] & 7 );
 683     i_lfsr1 = ( pi_tmp1[3] << 9 ) | 0x100 | pi_tmp1[4];
 684
 685     i_index = sizeof(pi_bits);
 686     i_carry = 0;
 687
 688     do
 689     {
 690         for( i_bit = 0, i_val = 0 ; i_bit < 8 ; ++i_bit )
 691         {
 692
 693             i_lfsr0_o = ( ( i_lfsr0 >> 24 ) ^ ( i_lfsr0 >> 21 ) ^
 694                         ( i_lfsr0 >> 20 ) ^ ( i_lfsr0 >> 12 ) ) & 1;
 695             i_lfsr0 = ( i_lfsr0 << 1 ) | i_lfsr0_o;
 696
 697             i_lfsr1_o = ( ( i_lfsr1 >> 16 ) ^ ( i_lfsr1 >> 2 ) ) & 1;
 698             i_lfsr1 = ( i_lfsr1 << 1 ) | i_lfsr1_o;
 699
 700             i_combined = !i_lfsr1_o + i_carry + !i_lfsr0_o;
 701             /* taking bit 1 */
 702             i_carry = ( i_combined >> 1 ) & 1;
 703             i_val |= ( i_combined & 1 ) << i_bit;
 704         }
 705
 706         pi_bits[--i_index] = i_val;
 707     } while( i_index > 0 );
 708
 709     /* This term is used throughout the following to
 710      * select one of 32 different variations on the
 711      * algorithm.
 712      */
 713     i_cse = pi_varients[i_css_varient] ^ pi_crypt_tab2[i_css_varient];
 714
 715     /* Now the actual blocks doing the encryption.  Each
 716      * of these works on 40 bits at a time and are quite
 717      * similar.
 718      */
 719     i_index = 0;
 720     for( i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_scratch[i] )
 721     {
 722         i_index = pi_bits[25 + i] ^ pi_scratch[i];
 723         i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;
 724
 725         pi_tmp1[i] = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;
 726     }
 727     pi_tmp1[4] ^= pi_tmp1[0];
 728
 729     for( i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_tmp1[i] )
 730     {
 731         i_index = pi_bits[20 + i] ^ pi_tmp1[i];
 732         i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;
 733
 734         pi_tmp2[i] = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;
 735     }
 736     pi_tmp2[4] ^= pi_tmp2[0];
 737
 738     for( i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_tmp2[i] )
 739     {
 740         i_index = pi_bits[15 + i] ^ pi_tmp2[i];
 741         i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;
 742         i_index = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;
 743
 744         pi_tmp1[i] = pi_crypt_tab0[i_index] ^ pi_crypt_tab2[i_index];
 745     }
 746     pi_tmp1[4] ^= pi_tmp1[0];
 747
 748     for( i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_tmp1[i] )
 749     {
 750         i_index = pi_bits[10 + i] ^ pi_tmp1[i];
 751         i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;
 752
 753         i_index = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;
 754
 755         pi_tmp2[i] = pi_crypt_tab0[i_index] ^ pi_crypt_tab2[i_index];
 756     }
 757     pi_tmp2[4] ^= pi_tmp2[0];
 758
 759     for( i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_tmp2[i] )
 760     {
 761         i_index = pi_bits[5 + i] ^ pi_tmp2[i];
 762         i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;
 763
 764         pi_tmp1[i] = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;
 765     }
 766     pi_tmp1[4] ^= pi_tmp1[0];
 767
 768     for(i = 5, i_term = 0 ; --i >= 0 ; i_term = pi_tmp1[i] )
 769     {
 770         i_index = pi_bits[i] ^ pi_tmp1[i];
 771         i_index = pi_crypt_tab1[i_index] ^ ~pi_crypt_tab2[i_index] ^ i_cse;
 772
 773         pi_key[i] = pi_crypt_tab2[i_index] ^ pi_crypt_tab3[i_index] ^ i_term;
 774     }
 775
 776     return;
 777 }
 778
 779 /*****************************************************************************
 780  * CSSCracker : title key decryption by cracking
 781  *****************************************************************************
 782  * This function is called by CSSGetKeys to find a key
 783  *****************************************************************************/
 784 static int CSSCracker( int i_start,
 785                        unsigned char * p_crypted,
 786                        unsigned char * p_decrypted,
 787                        dvd_key_t * p_sector_key,
 788                        dvd_key_t * p_key )
 789 {
 790     unsigned char pi_buffer[10];
 791     unsigned int i_t1, i_t2, i_t3, i_t4, i_t5, i_t6;
 792     unsigned int i_try;
 793     unsigned int i_candidate;
 794     unsigned int i, j;
 795     int i_exit = -1;
 796
 797
 798     for( i = 0 ; i < 10 ; i++ )
 799     {
 800         pi_buffer[i] = pi_css_tab1[p_crypted[i]] ^ p_decrypted[i];
 801     }
 802
 803     for( i_try = i_start ; i_try < 0x10000 ; i_try++ )
 804     {
 805         i_t1 = i_try >> 8 | 0x100;
 806         i_t2 = i_try & 0xff;
 807         i_t3 = 0;               /* not needed */
 808         i_t5 = 0;
 809
 810         /* iterate cipher 4 times to reconstruct LFSR2 */
 811         for( i = 0 ; i < 4 ; i++ )
 812         {
 813             /* advance LFSR1 normaly */
 814             i_t4 = pi_css_tab2[i_t2] ^ pi_css_tab3[i_t1];
 815             i_t2 = i_t1 >> 1;
 816             i_t1 = ( ( i_t1 & 1 ) << 8 ) ^ i_t4;
 817             i_t4 = pi_css_tab5[i_t4];
 818             /* deduce i_t6 & i_t5 */
 819             i_t6 = pi_buffer[i];
 820             if( i_t5 )
 821             {
 822                 i_t6 = ( i_t6 + 0xff ) & 0x0ff;
 823             }
 824             if( i_t6 < i_t4 )
 825             {
 826                 i_t6 += 0x100;
 827             }
 828             i_t6 -= i_t4;
 829             i_t5 += i_t6 + i_t4;
 830             i_t6 = pi_css_tab4[ i_t6 ];
 831             /* feed / advance i_t3 / i_t5 */
 832             i_t3 = ( i_t3 << 8 ) | i_t6;
 833             i_t5 >>= 8;
 834         }
 835
 836         i_candidate = i_t3;
 837
 838         /* iterate 6 more times to validate candidate key */
 839         for( ; i < 10 ; i++ )
 840         {
 841             i_t4 = pi_css_tab2[i_t2] ^ pi_css_tab3[i_t1];
 842             i_t2 = i_t1 >> 1;
 843             i_t1 = ( ( i_t1 & 1 ) << 8 ) ^ i_t4;
 844             i_t4 = pi_css_tab5[i_t4];
 845             i_t6 = ((((((( i_t3 >> 3 ) ^ i_t3 ) >> 1 ) ^
 846                                          i_t3 ) >> 8 ) ^ i_t3 ) >> 5 ) & 0xff;
 847             i_t3 = ( i_t3 << 8 ) | i_t6;
 848             i_t6 = pi_css_tab4[i_t6];
 849             i_t5 += i_t6 + i_t4;
 850             if( ( i_t5 & 0xff ) != pi_buffer[i] )
 851             {
 852                 break;
 853             }
 854
 855             i_t5 >>= 8;
 856         }
 857
 858         if( i == 10 )
 859         {
 860             /* Do 4 backwards steps of iterating t3 to deduce initial state */
 861             i_t3 = i_candidate;
 862             for( i = 0 ; i < 4 ; i++ )
 863             {
 864                 i_t1 = i_t3 & 0xff;
 865                 i_t3 = ( i_t3 >> 8 );
 866                 /* easy to code, and fast enough bruteforce
 867                  * search for byte shifted in */
 868                 for( j = 0 ; j < 256 ; j++ )
 869                 {
 870                     i_t3 = ( i_t3 & 0x1ffff) | ( j << 17 );
 871                     i_t6 = ((((((( i_t3 >> 3 ) ^ i_t3 ) >> 1 ) ^
 872                                    i_t3 ) >> 8 ) ^ i_t3 ) >> 5 ) & 0xff;
 873                     if( i_t6 == i_t1 )
 874                     {
 875                         break;
 876                     }
 877                 }
 878             }
 879
 880             i_t4 = ( i_t3 >> 1 ) - 4;
 881             for( i_t5 = 0 ; i_t5 < 8; i_t5++ )
 882             {
 883                 if( ( ( i_t4 + i_t5 ) * 2 + 8 - ( (i_t4 + i_t5 ) & 7 ) )
 884                                                                       == i_t3 )
 885                 {
 886                     (*p_key)[0] = i_try>>8;
 887                     (*p_key)[1] = i_try & 0xFF;
 888                     (*p_key)[2] = ( ( i_t4 + i_t5 ) >> 0) & 0xFF;
 889                     (*p_key)[3] = ( ( i_t4 + i_t5 ) >> 8) & 0xFF;
 890                     (*p_key)[4] = ( ( i_t4 + i_t5 ) >> 16) & 0xFF;
 891                     i_exit = i_try + 1;
 892                 }
 893             }
 894         }
 895     }
 896
 897     if( i_exit >= 0 )
 898     {
 899         (*p_key)[0] ^= (*p_sector_key)[0];
 900         (*p_key)[1] ^= (*p_sector_key)[1];
 901         (*p_key)[2] ^= (*p_sector_key)[2];
 902         (*p_key)[3] ^= (*p_sector_key)[3];
 903         (*p_key)[4] ^= (*p_sector_key)[4];
 904     }
 905
 906     return i_exit;
 907 }
 908
 909 #endif /* HAVE_CSS */
 910