Milenage authentication algorithm


35.206
Specification of the MILENAGE Algorithm Set

PHP program listing

class Milenage
{
  var $op, $opc, $key, $rand, $sqn, $amf, $op_choice;
  var $ak = 12;

  function milenage($op = '', $opc = '', $key = '', $rand = '', $sqn = '', $amf = '', $op_choice = '') {
    $this->op   = $this->split_hexa(preg_replace('/\s+/', '', $op)  ,16);
    $this->opc  = $this->split_hexa(preg_replace('/\s+/', '', $opc) ,16);
    $this->key  = $this->split_hexa(preg_replace('/\s+/', '', $key) ,16);
    $this->rand = $this->split_hexa(preg_replace('/\s+/', '', $rand),16);
    $this->sqn  = $this->split_hexa(preg_replace('/\s+/', '', $sqn) ,6);
    $this->amf  = $this->split_hexa(preg_replace('/\s+/', '', $amf) ,2);

    $this->op_choice = $op_choice;
  }

  function split_hexa($str, $max) {
    $arr = array();
    $ls = strlen($str);
    for ($i=$max-1; $i>=0; $i--) {
      if ($ls >= 2) {
        $arr[$i] = intval(substr($str,$ls-2,2), 16);
        $ls-=2;
      } elseif ($ls == 1) {
        $arr[$i] = intval(substr($str,0,1), 16);
        $ls-=1;
      } else {
        $arr[$i] = intval('0');
      }
    }
    return $arr;
  }

  /*--------- Operator Variant Algorithm Configuration Field --------*/
  var $roundKeys = array();

  /*--------------------- Rijndael S box table ----------------------*/
  var $S = array(
   99,124,119,123,242,107,111,197, 48,  1,103, 43,254,215,171,118,
  202,130,201,125,250, 89, 71,240,173,212,162,175,156,164,114,192,
  183,253,147, 38, 54, 63,247,204, 52,165,229,241,113,216, 49, 21,
    4,199, 35,195, 24,150,  5,154,  7, 18,128,226,235, 39,178,117,
    9,131, 44, 26, 27,110, 90,160, 82, 59,214,179, 41,227, 47,132,
   83,209,  0,237, 32,252,177, 91,106,203,190, 57, 74, 76, 88,207,
  208,239,170,251, 67, 77, 51,133, 69,249,  2,127, 80, 60,159,168,
   81,163, 64,143,146,157, 56,245,188,182,218, 33, 16,255,243,210,
  205, 12, 19,236, 95,151, 68, 23,196,167,126, 61,100, 93, 25,115,
   96,129, 79,220, 34, 42,144,136, 70,238,184, 20,222, 94, 11,219,
  224, 50, 58, 10, 73,  6, 36, 92,194,211,172, 98,145,149,228,121,
  231,200, 55,109,141,213, 78,169,108, 86,244,234,101,122,174,  8,
  186,120, 37, 46, 28,166,180,198,232,221,116, 31, 75,189,139,138,
  112, 62,181,102, 72,  3,246, 14, 97, 53, 87,185,134,193, 29,158,
  225,248,152, 17,105,217,142,148,155, 30,135,233,206, 85, 40,223,
  140,161,137, 13,191,230, 66,104, 65,153, 45, 15,176, 84,187, 22 );

  /*------- This array does the multiplication by x in GF(2^8) ------*/
  var $Xtime = array(
    0,  2,  4,  6,  8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30,
   32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62,
   64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94,
   96, 98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,
  128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,
  160,162,164,166,168,170,172,174,176,178,180,182,184,186,188,190,
  192,194,196,198,200,202,204,206,208,210,212,214,216,218,220,222,
  224,226,228,230,232,234,236,238,240,242,244,246,248,250,252,254,
   27, 25, 31, 29, 19, 17, 23, 21, 11,  9, 15, 13,  3,  1,  7,  5,
   59, 57, 63, 61, 51, 49, 55, 53, 43, 41, 47, 45, 35, 33, 39, 37,
   91, 89, 95, 93, 83, 81, 87, 85, 75, 73, 79, 77, 67, 65, 71, 69,
  123,121,127,125,115,113,119,117,107,105,111,109, 99, 97,103,101,
  155,153,159,157,147,145,151,149,139,137,143,141,131,129,135,133,
  187,185,191,189,179,177,183,181,171,169,175,173,163,161,167,165,
  219,217,223,221,211,209,215,213,203,201,207,205,195,193,199,197,
  251,249,255,253,243,241,247,245,235,233,239,237,227,225,231,229 );

  /*  Algorithm f1
   *  Computes network authentication code MAC-A from key K, random
   *  challenge RAND, sequence number SQN and authentication management
   *  field AMF */
/* ------------------------------------------------------------------------------ */
  function f1($k, $rand, $sqn, $amf, &$mac_a) {
    $op_c = array(); $rijndaelInput = array(); $temp = array(); $in1 = array(); $out1 = array();

    $this->RijndaelKeySchedule($k);
    $this->ComputeOPc($op_c);

    for ($i=0; $i<16; $i++)
      $rijndaelInput[$i] = $rand[$i] ^ $op_c[$i];
    $this->RijndaelEncrypt($rijndaelInput, $temp);

    for ($i=0; $i<6; $i++) {
      $in1[$i]    = $sqn[$i];
      $in1[$i+8]  = $sqn[$i];
    }
    for ($i=0; $i<2; $i++) {
      $in1[$i+6]  = $amf[$i];
      $in1[$i+14] = $amf[$i];
    }

    /* XOR op_c and in1, rotate by r1=64, and XOR *
     * on the constant c1 (which is all zeroes)   */
    for ($i=0; $i<16; $i++)
      $rijndaelInput[($i+8) % 16] = $in1[$i] ^ $op_c[$i];

    /* XOR on the value temp computed before */
    for ($i=0; $i<16; $i++)
      $rijndaelInput[$i] ^= $temp[$i];

    $this->RijndaelEncrypt($rijndaelInput, $out1);
    for ($i=0; $i<16; $i++)
      $out1[$i] ^= $op_c[$i];

    for ($i=0; $i<8; $i++)
      $mac_a[$i] = $out1[$i];
  }

  /*   Algorithms f2-f5
   *  Takes key K and random challenge RAND, and returns response RES,
   *  confidentiality key CK, integrity key IK and anonymity key AK.
   */
/* ------------------------------------------------------------------------------ */
  function f2345($k, $rand, &$res, &$ck, &$ik, &$ak) {
    $op_c = array(); $rijndaelInput = array(); $temp = array(); $out = array();

    $this->RijndaelKeySchedule($k);
    $this->ComputeOPc($op_c);

    for ($i=0; $i < 16; $i++)
      $rijndaelInput[$i] = $rand[$i] ^ $op_c[$i];
    $this->RijndaelEncrypt($rijndaelInput, $temp);

    /* To obtain output block OUT2: XOR OPc and TEMP,    *
     * rotate by r2=0, and XOR on the constant c2 (which *
     * is all zeroes except that the last bit is 1).     */
    for ($i=0; $i < 16; $i++)
      $rijndaelInput[$i] = $temp[$i] ^ $op_c[$i];
    $rijndaelInput[15] ^= 1;

    $this->RijndaelEncrypt($rijndaelInput, $out);
    for ($i=0; $i < 16; $i++)
      $out[$i] ^= $op_c[$i];

    for ($i=0; $i < 8; $i++)
      $res[$i] = $out[$i+8];
    for ($i=0; $i < 6; $i++)
      $ak[$i] = $out[$i];

    /* To obtain output block OUT3: XOR OPc and TEMP,        *
     * rotate by r3=32, and XOR on the constant c3 (which    *
     * is all zeroes except that the next to last bit is 1). */
    for ($i=0; $i < 16; $i++)
      $rijndaelInput[($i+12) % 16] = $temp[$i] ^ $op_c[$i];
    $rijndaelInput[15] ^= 2;

    $this->RijndaelEncrypt($rijndaelInput, $out);
    for ($i=0; $i < 16; $i++)
      $out[$i] ^= $op_c[$i];

    for ($i=0; $i < 16; $i++)
      $ck[$i] = $out[$i];

    /* To obtain output block OUT4: XOR OPc and TEMP,         *
     * rotate by r4=64, and XOR on the constant c4 (which     *
     * is all zeroes except that the 2nd from last bit is 1). */
    for ($i=0; $i < 16; $i++)
      $rijndaelInput[($i+8) % 16] = $temp[$i] ^ $op_c[$i];
    $rijndaelInput[15] ^= 4;

    $this->RijndaelEncrypt($rijndaelInput, $out);
    for ($i=0; $i < 16; $i++)
      $out[$i] ^= $op_c[$i];

    for ($i=0; $i < 16; $i++)
      $ik[$i] = $out[$i];
  }

  /*  Rijndael key schedule function. Takes 16-byte key and creates
   *  all Rijndael's internal subkeys ready for encryption. */
/* ------------------------------------------------------------------------------ */
  function RijndaelKeySchedule($key) {
    /* first round key equals key */
    for ($i=0; $i<16; $i++)
      $this->roundKeys[0][$i & 0x03][$i>>2] = $key[$i];

    $roundConst = 1;

    /* now calculate round keys */
    for ($i=1; $i<11; $i++) {
      $this->roundKeys[$i][0][0] = $this->S[$this->roundKeys[$i-1][1][3]] ^ $this->roundKeys[$i-1][0][0] ^ $roundConst;
      $this->roundKeys[$i][1][0] = $this->S[$this->roundKeys[$i-1][2][3]] ^ $this->roundKeys[$i-1][1][0];
      $this->roundKeys[$i][2][0] = $this->S[$this->roundKeys[$i-1][3][3]] ^ $this->roundKeys[$i-1][2][0];
      $this->roundKeys[$i][3][0] = $this->S[$this->roundKeys[$i-1][0][3]] ^ $this->roundKeys[$i-1][3][0];

      for ($j=0; $j<4; $j++) {
        $this->roundKeys[$i][$j][1] = $this->roundKeys[$i-1][$j][1] ^ $this->roundKeys[$i][$j][0];
        $this->roundKeys[$i][$j][2] = $this->roundKeys[$i-1][$j][2] ^ $this->roundKeys[$i][$j][1];
        $this->roundKeys[$i][$j][3] = $this->roundKeys[$i-1][$j][3] ^ $this->roundKeys[$i][$j][2];
      }

      /* update round constant */
      $roundConst = $this->Xtime[$roundConst];
    }
  }

/* Round key addition function */
/* ------------------------------------------------------------------------------ */
  function KeyAdd(&$state, $roundKeys, $round) {
    for ($i=0; $i<4; $i++)
      for ($j=0; $j<4; $j++)
        $state[$i][$j] ^= $roundKeys[$round][$i][$j];
  }

/* Byte substitution transformation */
/* ------------------------------------------------------------------------------ */
  function ByteSub(&$state) {
    for ($i=0; $i<4; $i++)
      for ($j=0; $j<4; $j++)
        $state[$i][$j] = $this->S[$state[$i][$j]];
  }

/* Row shift transformation */
/* ------------------------------------------------------------------------------ */
  function ShiftRow(&$state) {
    /* left rotate row 1 by 1 */
    $temp = $state[1][0];
    $state[1][0] = $state[1][1];
    $state[1][1] = $state[1][2];
    $state[1][2] = $state[1][3];
    $state[1][3] = $temp;

    /* left rotate row 2 by 2 */
    $temp = $state[2][0];
    $state[2][0] = $state[2][2];
    $state[2][2] = $temp;
    $temp = $state[2][1];
    $state[2][1] = $state[2][3];
    $state[2][3] = $temp;

    /* left rotate row 3 by 3 */
    $temp = $state[3][0];
    $state[3][0] = $state[3][3];
    $state[3][3] = $state[3][2];
    $state[3][2] = $state[3][1];
    $state[3][1] = $temp;
  }

/* MixColumn transformation */
/* ------------------------------------------------------------------------------ */
  function MixColumn(&$state) {
    /* do one column at a time */
    for ($i=0; $i<4;$i++) {
      $temp = $state[0][$i] ^ $state[1][$i] ^ $state[2][$i] ^ $state[3][$i];
      $tmp0 = $state[0][$i];

      /* Xtime array does multiply by x in GF2^8 */
      $tmp = $this->Xtime[$state[0][$i] ^ $state[1][$i]];
      $state[0][$i] ^= $temp ^ $tmp;

      $tmp = $this->Xtime[$state[1][$i] ^ $state[2][$i]];
      $state[1][$i] ^= $temp ^ $tmp;

      $tmp = $this->Xtime[$state[2][$i] ^ $state[3][$i]];
      $state[2][$i] ^= $temp ^ $tmp;

      $tmp = $this->Xtime[$state[3][$i] ^ $tmp0];
      $state[3][$i] ^= $temp ^ $tmp;
    }
  }

/* RijndaelEncrypt */
/* ------------------------------------------------------------------------------ */
  function RijndaelEncrypt($input, &$output) {
    $state = array();

    /* initialise state array from input byte string */
    for ($i=0; $i<16; $i++)
      $state[$i & 0x3][$i>>2] = $input[$i];

    /* add first round_key */
    $this->KeyAdd($state, $this->roundKeys, 0);

    /* do lots of full rounds */
    for ($r=1; $r<=9; $r++) {
      $this->ByteSub($state);
      $this->ShiftRow($state);
      $this->MixColumn($state);
      $this->KeyAdd($state, $this->roundKeys, $r);
    }

    /* final round */
    $this->ByteSub($state);
    $this->ShiftRow($state);
    $this->KeyAdd($state, $this->roundKeys, $r);

    /* produce output byte string from state array */
    for ($i=0; $i<16; $i++)
      $output[$i] = $state[$i & 0x3][$i>>2];
  }

/* ComputeOPc */
/* ------------------------------------------------------------------------------ */
  function ComputeOPc(&$op_c) {
    switch ($this->op_choice) {
      case '1':
        $this->RijndaelEncrypt($this->op, $op_c);
        for ($i=0; $i<16; $i++) {
          $op_c[$i] ^= $this->op[$i];
          $this->opc[$i] = $op_c[$i];
        }
        break;
      case '2':
        for ($i=0; $i<16; $i++)
          $op_c[$i] = $this->opc[$i];
        break;
    }
  }

/* ------------------------------------------------------------------------------ */
  function display_auth() {
    $xautn = array(); $xres = array(); $ck = array(); $ik = array(); $ak = array(); $mac_a = array();

    // Milenage f2-f5
    $this->f2345($this->key, $this->rand, $xres, $ck, $ik, $ak);

    if (1 == $this->op_choice) {
      echo "op = ";
      for ($i=0; $i < 16; $i++) {
        $vh = sprintf("%02x ", $this->op[$i]);
        echo "$vh";
      }
    }

    echo "opc = ";
    for ($i=0; $i < 16; $i++) {
      $vh = sprintf("%02x ", $this->opc[$i]);
      echo "$vh";
    }

    echo "key = ";
    for ($i=0; $i < 16; $i++) {
      $vh = sprintf("%02x ", $this->key[$i]);
      echo "$vh";
    }

    echo "rand = ";
    for ($i=0; $i < 16; $i++) {
      $vh = sprintf("%02x ", $this->rand[$i]);
      echo "$vh";
    }

    echo "sqn = ";
    for ($i=0; $i < 6; $i++) {
      $vh = sprintf("%02x ", $this->sqn[$i]);
      echo "$vh";
    }

    echo "amf = ";
    for ($i=0; $i < 2; $i++) {
      $vh = sprintf("%02x ", $this->amf[$i]);
      echo "$vh";
    }

    echo "-- Milenage --";

    echo "res = ";
    for ($i=0; $i < 8; $i++) {
      $vh = sprintf("%02x ", $xres[$i]);
      echo "$vh";
    }
    echo "ck = ";
    for ($i=0; $i < 16; $i++) {
      $vh = sprintf("%02x ", $ck[$i]);
      echo "$vh";
    }
    echo "ik = ";
    for ($i=0; $i < 16; $i++) {
      $vh = sprintf("%02x ", $ik[$i]);
      echo "$vh";
    }
    echo "ak = ";
    for ($i=0; $i < 6; $i++) {
      $vh = sprintf("%02x ", $ak[$i]);
      echo "$vh";
    }

    // XAUTN = SQN xor AK || AMF || MAC
    for ($i=0; $i<6; $i++)
      $xautn[$i] = $this->sqn[$i] ^ $ak[$i];

    // AMF
    for ($i=0; $i<2; $i++)
      $xautn[$i+6] = $this->amf[$i];

    // MAC-A
    $this->f1($this->key, $this->rand, $this->sqn, $this->amf, $mac_a);
    for ($i=0; $i<8; $i++)
      $xautn[$i+8] = $mac_a[$i];

    echo "autn = ";
    for ($i=0; $i < 16; $i++) {
      $vh = sprintf("%02x ", $xautn[$i]);
      echo "$vh";
    }
  }
}