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