[Announce] Security fixes for Libgcrypt and GnuPG 1.4 [CVE-2016-6316]

[Werner Koch]

On Thu, 18 Aug 2016 13:38, pgut001 at cs.auckland.ac.nz said:

> So I think I've managed to reverse-engineer what the code is doing (there are
> no code comments explaining it).  It's not at all what I described in my PRNG

No need to reverse engineer the code.  Well, unless you are looking at
that 18 year old code from 1.4.  Here is the description from Libgcrypt
before the fix:

 * Mix the 600 byte pool.  Note that the 64 byte scratch area directly
 * follows the pool.  The numbers in the diagram give the number of
 * bytes.
 *         <................600...............>   <.64.>
 * pool   |------------------------------------| |------|
 *         <..44..>                        <20>
 *            |                             |
 *            |                             +-----+
 *            +-----------------------------------|--+
 *                                                v  v
 *                                               |------|
 *                                                <hash>
 *                                                  |
 *          +---------------------------------------+
 *          v
 *         <20>
 * pool'  |------------------------------------|
 *         <20><20><..44..>
 *          |         |
 *          |         +------------------------------+
 *          +-------------------------------------+  |
 *                                                v  v
 *                                               |------|
 *                                                <hash>
 *                                                  |
 *              +-----------------------------------+
 *              v
 *             <20>
 * pool'' |------------------------------------|
 *         <20><20><20><..44..>
 *              |         |
 *              |         +--------------------------+
 *              +---------------------------------+  |
 *                                                v  v
 *                                               |------|
 *                                                <hash>
 *
 * and so on until we did this for all 30 blocks.
 *
 * To better protect against implementation errors in this code, we
 * xor a digest of the entire pool into the pool before mixing.

Earlier versions had the same comment but using a different markup; see
end of the mail.  I updated the comment while looking at the research
paper.

> there are no code comments.  What the GnuPG code does is mix the next 64 bytes
> and then overwrite the preceding 20 bytes with the mixed output, however this
> doesn't propagate any entropy along through the buffer.  Quoting the original

We have 30 slots of 20 bytes and for each slot we take the previous 20
bytes and the next 44 bytes, hash them and put them into the current
slot.  Thus the state is carried along _except for the last slot_, which
nobody figured out in the last 18 years.  Despite several code audits,
including one by an German random pope.  Only a few weeks ago there was
an audit and the guy who worked on this produced pretty diagrams showing
the operation as they should be; i.e. derived from the code and not from
the above comment.  He didn't noticed the hole either and I looked at
his documents only after I received the paper.

> The GnuPG code however only hashes the next 64 bytes, and then uses the output
> to overwrite the current 20 bytes (it uses RMD160, not MD5, since it's a bit
> newer than the original paper).  No state is carried along.

Nope.  We recently switched from RMD160 to SHA1 for other reasons but
that does not matter.

The reason why only 64 bytes are hashed is that it allows the use of the
bare transform function.  IIRC, old Cryptlib versions did the same but I
guess you changed that to the full hash machinery in the course of your
doctoral work.

I _might_ have introduced the hole to mix in more bytes in each step.
Or it was a plain bug.

Here is the description for the fixed code:

 *         <................600...............>   <.64.>
 * pool   |------------------------------------| |------|
 *         <20><.24.>                      <20>
 *          |     |                         +-----+
 *          +-----|-------------------------------|-+
 *                +-------------------------------|-|-+
 *                                                v v v
 *                                               |------|
 *                                                <hash>
 *          +---------------------------------------+
 *          v
 *         <20>
 * pool'  |------------------------------------|
 *         <20><20><.24.>
 *          +---|-----|---------------------------+
 *              +-----|---------------------------|-+
 *                    +---------------------------|-|-+
 *                                                v v v
 *                                               |------|
 *                                                <hash>
 *                                                  |
 *              +-----------------------------------+
 *              v
 *             <20>
 * pool'' |------------------------------------|
 *         <20><20><20><.24.>
 *              +---|-----|-----------------------+
 *                  +-----|-----------------------|-+
 *                        +-----------------------|-|-+
 *                                                v v v
 *



Salam-Shalom,

   Werner



p.s.
Here is the old comment on how the pool is mixed (libgcrypt 1.7.2)
 * Mix the pool:
 *
 * |........blocks*20byte........|20byte|..44byte..|
 * <..44byte..>           <20byte>
 *      |                    |
 *      |                    +------+
 *      +---------------------------|----------+
 *                                  v          v
 * |........blocks*20byte........|20byte|..44byte..|
 *                               <.....64bytes.....>
 *                                       |
 *    +----------------------------------+
 *   Hash
 *    v
 * |.............................|20byte|..44byte..|
 * <20byte><20byte><..44byte..>
 *    |                |
 *    |                +---------------------+
 *    +-----------------------------+        |
 *                                  v        v
 * |.............................|20byte|..44byte..|
 *                               <.....64byte......>
 *                                      |
 *            +-------------------------+
 *           Hash
 *            v
 * |.............................|20byte|..44byte..|
 * <20byte><20byte><..44byte..>

--
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.
 /* Join us at OpenPGP.conf  <https://openpgp-conf.org> */
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 162 bytes
Desc: not available
URL: </pipermail/attachments/20160818/95ffec52/attachment.sig>