Vulnerability

    PIX Private Link key length issue

Affected

    Cisco with all PIX Private Link software through version 4.1.6.

Description

    PIX Private Link is an  optional feature that can be  installed in
    Cisco PIX firewalls.  PIX Private Link creates IP virtual  private
    networks  over  untrusted  networks,  such  as the Internet, using
    tunnels  encrypted  with  Data  Encryption  Standard  (DES) in ECB
    ("electronic   codebook")   mode.    An   error   in   parsing  of
    configuration file commands reduces  the effective key length  for
    the PIX Private Link DES encryption to 48 bits from the nominal 56
    bits.

    If attackers know the details of the key-parsing error in the  PIX
    Private Link software, they will know  8 bits of the key ahead  of
    time.  This reduces the  effective key length from the  attacker's
    point of view from 56 to 48 bits.  This reduction of the effective
    key length reduces  the work involved  in a brute-force  attack on
    the  encryption  by  a  factor  of  256.  That  is,  knowledgeable
    attackers  can,  on  the  average,  find  the  right key 256 times
    faster than they would be able to find it with a true 56-bit key.

    CISCO PIX Private Link feature uses  DES key that is only 48  bits
    in  length.   It  is  not  obvious  straight  away  since  key  is
    internally expanded from 7-bytes  (as entered in command  line) to
    8-bytes  that  is  used  by  DES.  If  you dig into that expansion
    algorithm you'll find that third byte, counting from the right, is
    not used at all. This is how key is expanded:

        #!/usr/local/bin/perl
        # Key used by DES
        @key_data=( 0, 0, 0, 0, 0, 0, 0, 0 );
        # Key entered in LINK statement
        @key_in = ( 0x00, 0x00, 0x00, 0x00, 0x00, 0xda, 0xaa );

        # Key expansion algorithm
        $byte = ($key_in[6] & 0x3F) << 2;
        $key_data[6] |= $byte;
        $byte = ($key_in[6] & 0xC0) >> 5;
        $key_data[5] |= $byte;

        $byte = ($key_in[5] & 0x7F) << 1;
        $key_data[7] = $byte;
        $byte = ($key_in[5] & 0x80) >> 6;
        $key_data[6] |= $byte;
        #
        # Byte 4 (from left) seems to be ignored
        #
        $byte = ($key_in[3] & 0x01) << 7;
        $key_data[1] |= $byte;
        $key_data[0] = ($key_in[3] & 0xFE );

        $byte = $key_in[2] & 0x03;
        $key_data[2] |= ($byte << 6);
        $byte = ($key_in[2] & 0xFC) >> 1;
        $key_data[1] |= $byte;

        $byte = $key_in[1] & 0x07;
        $key_data[3] |= ($byte << 5 );
        $byte = $key_in[1] & 0xF8;
        $key_data[2] |= ($byte >> 2);

        $byte = $key_in[0] & 0x0F;
        $key_data[4] |= ($byte << 4);
        $byte = $key_in[0] & 0xF0;
        $key_data[3] |= ($byte >> 3);
        #
        # Now you can use key in @key_data for encryption

    Although the use of ECB mode is intentional, ECB is not  generally
    considered to be the best mode in which to employ DES, because  it
    tends to simplify  certain forms of  cryptanalysis and may  permit
    certain replay attacks.  Technical details of the relative  merits
    of various encryption modes are beyond the scope of this document.

    What's  worse  is  that  this  has  a  nasty  interaction with the
    weakening of the key down to 48 bits.  In export-weakened SSL, one
    adds  some  public  salt  to  the  40-bit  secret  key,  to   stop
    precomputation attacks;  but note  that CISCO's  algorithm adds no
    salt, so there are  all sorts of precomputation  attacks possible.
    The simplest attack  (``the Exabyte attack'')  is to encrypt  some
    common plaintext block (e.g. "\nlogin: ") under all 2^48  possible
    keys, and store the 2^48 ciphertext results on a big Exabyte tape;
    then each subsequent link-encryption  key can be broken  with O(1)
    effort.   Thanks to  the ECB  mode, such  a common plaintext block
    should be easy to find.  (With a real chaining mode, these attacks
    are not possible under  a ciphertext-only assumption, because  the
    chaining vector serves as a kind of salt.)  A much more  practical
    approach would  use Hellman's  time-space tradeoff.   There, you'd
    need only about 2^32  space (e.g. $100 at  Fry's for a cheap  hard
    disk), plus  you'd need  to do  a 2^48  precomputation.  After the
    precomputation, each subsequent link-encryption key can be  broken
    with about 2^32 trial encryptions.

    The really nasty problem with ECB mode is that the data stream  is
    vulnerable  to  trivial  substitution  attacks.   If the encrypted
    traffic consists of administrative commands, it won't be that hard
    to   collect   a    modest   but    interesting   dictionary    of
    plaintext/ciphertext pairs.  Then  the attacker can forge  command
    strings without ever having to brute force the key itself.

Solution

    There is no configuration  workaround.  The first  regular release
    containing a fix for this problem will be version 4.2.1, which  is
    tentatively scheduled for release in late June 1998. This schedule
    is subject to change. Fixes for the 4.1 software release have  not
    yet been scheduled.  This fix extends the effective DES key length
    to a full 56 bits; ECB mode is still used.