Vulnerability

    PGP

Affected

    PGP 5.0

Description

    This problem was found by Germano Caronni, and verified by  Thomas
    Roessler  and  Marcel  Waldvogel.   A  flaw  has been found in the
    randomness gathering  code of  PGP 5.   PGP 5  will, under certain
    well-defined circumstances, generate public/private key pairs with
    no or only a small amount of randomness.  Such keys are  insecure.
    Chances are very high that you have no problem.  So, don't panic.

    The flaw has been found in the PGP 5.0i code base.  It is specific
    to Unix systems such as Linux or various BSD dialects with a
    /dev/random device.

    The  problem  affects  you  in  the  worst  possible manner if you
    started  from  scratch  with  pgp  5  on  a  Unix  system  with  a
    /dev/random device,  and created  your key  pair non-interactively
    with a command line like this one:

        pgpk -g <DSS or RSA> <key-length> <user-id> <timeout> <pass-phrase>

    If you have generated your key non-interactively, you may wish  to
    revoke it, and create a new key using a version of PGP which works
    correctly.

    In  order  to  generate  secure  cryptographic  keys, PGP needs to
    gather  random  numbers  from  reliable  sources, so keys can't be
    predicted by  attackers.   Randomness sources  PGP generally  uses
    include:

        - a seed file with random data from previous sessions
        - user input and input timing

    Additionally, certain  Unix systems  such as  OpenBSD, Linux,  and
    others,  offer  a  stream  of  random  data over a central service
    typically  called  /dev/random  or  the  like.   If  present, this
    service is used by PGP as a source of random data.

    PGP 5.0i's reading of these random numbers does not work.  Instead
    of random numbers, a stream of  bytes with the value "1" is  read.
    In practice, this implies two things:

        1. PGP5 will generally  overestimate the amount of  randomness
           available.   Authors  of  advisory  did  not researched the
           effects of this  in detail.   However, it is  believed that
           the amount of randomness  gathered from input data,  timing
           information, and  old random  data will  be sufficient  for
           most applications (See below for a detailed estimate).

        2. In  situations  in  which  no other randomness sources  are
           available, PGP relies on the /dev/random service, and  thus
           uses predictable instead of random numbers.  This is not  a
           flaw of the random service, but of the PGP5 implementation.

    One particular example of such a situation is non-interactive  key
    generation with a virgin PGP 5 installation, like described above.
    Example:

        $ mkdir /tmp/pgp5test
        $ PGPPATH=/tmp/pgp5test
        $ pgpk -g RSA 1024 foo@bar.com 0 "passphrase string"

    In fact,  RSA keys  generated this  way are  entirely predictable,
    which  can   easily  be   verified  by   comparing  key   IDs  and
    fingerprints.  When using DSA/ElGamal keys, the DSA signature  key
    is predictable,  while the  ElGamal encryption  subkey will  vary.
    Note that  fingerprints and  key IDs  of the  predictable DSA keys
    depend  on  a  time  stamp,  and  are  themselves not predictable.
    Proof of concept key rings  generated with pgp 5.0i are  available
    from

        http://olymp.org/~caronni/pgpbug-keyrings.tgz

    Here's the flawed code from src/lib/ttyui/pgpUserIO.c:

         1314	static unsigned
         1315	pgpDevRandomAccum(int fd, unsigned count)
         1316	{
         1317	    char RandBuf;
         1318	    unsigned short i = 0;
         1319
         1320	    pgpAssert(count);
         1321	    pgpAssert(fd >= 0);
         1322
         1323	    for(i = 0; i <= count; ++i) {
        >1324		RandBuf = read(fd, &RandBuf, count);
         1325		pgpRandomAddBytes(&pgpRandomPool, (byte *)&RandBuf, sizeof(RandBuf));
         1326		pgpRandPoolAddEntropy(256);
         1327	    }
         1328
         1329	    return(i);
         1330	}

    The count parameter is  always set to the  value 1 by the  calling
    code.  The byte read from the file descriptor fd into the  RandBuf
    buffer  is  subsequently  overwritten  with  the read() function's
    return value, which  will be 1.   The actual random  data are  not
    used.

    This can be fixed by replacing line 1324 by the following line  of
    code:

           read (fd, &RandBuf, 1);

    A  dump  of  random  data  gathered  during  an  interactive   key
    generation session is available at

        http://olymp.org/~caronni/randlog-keygen

    This was dumped as passed to the pgpRandomAddByte() function,  one
    byte at a time.  Note the streams of bytes with the value 1  which
    should actually contain data gathered from /dev/random.  Also note
    that the pass phrase ("asdf") and the user ID ("roessler@guug.de")
    are  clearly  visible,  but  mixed  with  timing  data  from   the
    individual key presses.

    No  random  data  occuring  after  the  second stream of ones were
    generated from external events prior to the generation of the  DSA
    key in question.

    Authors of advisory give a back-of-the-envelope upper estimate  of
    the amount of  random bits PGP  may gather during  interactive key
    generation.  They assume  that /dev/random reading is  flawed, and
    that no seed file exists prior to running PGP.  Timing is  assumed
    to have a resolution of 1 us (gettimeofday()).

    During  a  PGP  session  of  one  minute,  we can get at most 2^28
    different time stamps (2^28 ~ 60*10^6).

    Note  that  one  time  stamp  close  to  the  point of time of key
    generation is known to attackers from the time stamp PGP leaves on
    the key.  So the  intervals between individual key presses  remain
    as a source of randomness.

    Assuming that the user types at a rate of about 120 characters per
    minute, we have an  interval of approximately 0.5  seconds between
    two  key  presses.   Dropping  the  upmost  non-random  bit of the
    interval length, we get about 18 bits of random timing information
    per  key  press.   This  estimate  gets  worse for experienced and
    fast-typing users.

    With a user ID of 20 characters, and no pass phrase, PGP will have
    gathered roughly 300-400 random bits interactively.  While this is
    not bad, it is not sufficient by PGP's own standards.

    This vulnerability stands for:

        - PGP 5.0 for Linux, US Commercial and Freeware editions
        - PGP 5.0 for Linux, Source code book (basis for PGP 5.0i for Linux)


Solution

    The  problem  does  NOT   manifest  itself  under  the   following
    circumstances:

        - You  typed  in  a  lot  of  data while generating your  key,
          including long user ID and pass phrase strings.
        - A random seed  file PGP 5 could  use existed on your  system
          before you generated the key.

    This can be fixed by replacing line 1324 by the following line  of
    code:

           read (fd, &RandBuf, 1);

    Users  who  generated  keys  in  the  manner  described  above are
    strongly urged to do the following:

        - Revoke and no longer use keys suspected to have this problem
        - Generate new public/private keypairs with entropy  collected
          from users' typing and/or mouse movements
        - Re-encrypt any data  with the newly generated  keypairs that
          is  currently  encrypted  with  keys  suspected to have this
          problem
        - Re-sign  any  data  with  the  newly generated keypairs,  if
          required

    Users are also urged to upgrade to the latest releases of PGP,  as
    PGP 5.0  products have  not been  officially supported  by Network
    Associates since early 1999, or distributed by Network  Associates
    since June 1998.