PGP 5.0 Key Generation Flaw

    Date24 May 2000
    CategoryCryptography
    3066
    Posted ByAnthony Pell
    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 . . . 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.


    SECURITY FLAW IN PGP 5.0
    ========================



    EXECUTIVE SUMMARY
    -----------------

    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.




    WHO IS AFFECTED?
    ----------------

    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.


    Versions 2.* and 6.5 of PGP do NOT share this problem.

    PGP versions ported to other platforms do NOT share this problem.


    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.


    However, 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



    WHAT TO DO?
    -----------

    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.



    DETAILS
    -------

    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. We have not researched the effects of this in detail.

    However, we believe 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 This email address is being protected from spambots. You need JavaScript enabled to view it. 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 .



    GORY DETAILS
    ------------

    1. Code

    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);


    2. "Random" data

    A dump of random data gathered during an interactive key generation
    session is available at .
    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 ("This email address is being protected from spambots. You need JavaScript enabled to view it.") 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.


    3. Some estimates

    We give a back-of-the-envelope upper estimate of the amount of
    random bits PGP may gather during interactive key generation. We
    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.




    CONCLUSIONS
    -----------

    Public code review is a good thing - if it happens.





    CREDITS
    -------

    This problem was found by Germano Caronni , and
    verified by Thomas Roessler and Marcel Waldvogel
    .

    |-Per Kangru--http://kangru.org-+46-(0)This email address is being protected from spambots. You need JavaScript enabled to view it.|
    |Lasercooling @ Stockholm Univ. +46-(0)8-161136 This email address is being protected from spambots. You need JavaScript enabled to view it. |
    |Consultant @ Roxen IS AB +46-(0)709-153939 This email address is being protected from spambots. You need JavaScript enabled to view it.|
    |-PGP-fingerprint-672C8-5632-7DC49-CFECC-E0EE-3DA4-E82E-A036F-59A1|
    You are not authorised to post comments.

    LinuxSecurity Poll

    Has your email account ever been pwned in a data breach?

    No answer selected. Please try again.
    Please select either existing option or enter your own, however not both.
    Please select minimum 0 answer(s) and maximum 2 answer(s).
    /component/communitypolls/?task=poll.vote
    12
    radio
    [{"id":"53","title":"Yes","votes":"8","type":"x","order":"1","pct":88.89,"resources":[]},{"id":"54","title":"No","votes":"1","type":"x","order":"2","pct":11.11,"resources":[]}]["#ff5b00","#4ac0f2","#b80028","#eef66c","#60bb22","#b96a9a","#62c2cc"]["rgba(255,91,0,0.7)","rgba(74,192,242,0.7)","rgba(184,0,40,0.7)","rgba(238,246,108,0.7)","rgba(96,187,34,0.7)","rgba(185,106,154,0.7)","rgba(98,194,204,0.7)"]350
    bottom200

    We use cookies to provide and improve our services. By using our site, you consent to our Cookie Policy.