How does GPG verify succesful decryption?

Question

How does GPG (or other programs using the OpenPGP file format) verify that it has succeeded with decryption (for symmetrically encrypted data)?

Is something appended to the clear text so there exist some expected data?

For example, I'm using these command lines:

gpg -c test.txt
gpg -d test.txt.gpg

The second command outputs

gpg: decryption failed: bad key

when a wrong key is entered.

How can the program know that it is a bad key? Why doesn't it simply return the random data generated by decrypting with a wrong key?

First I thought that maybe it used letter density to determine if it was plaintext, but then it manages to decrypt binary files too (and complain about wrong keys), and specially key files which should be completely random.

Answer 1

This is hidden well in RFC 4880, the OpenPGP message format specification.

Section 5.7 explains how message data is encrypted. (I'm using the values for a 16-byte block cipher like AES.)

• A random block of data is created: $p_{1} \dots p_{16}$
• The last two bytes of this block are repeated: $(p_{17}, p_{18}) := (p_{15}, p_{16})$.

These 18 bytes (in case of AES or another similar block cipher) are encrypted in CFB mode (with a zero initialization vector), _{i.e. $(c_{1} \dots c_{16}) = E_K(0, \dots 0) \oplus (p_{1} \dots p_{16})$, and $(c_{17}, c_{18}) = \text{first 2 bytes of}(E_K(c_{1} \dots c_{16})) \oplus (p_{17}, p_{18})$.}

When decrypting, we just have to decrypt these 18 bytes $c_1 \dots c_{18}$ _{(i.e. we calculate $p_1 \dots p_{16} = E_K(0) \oplus (c_{1} \dots c_{16})$, $(p_{17}, p_{18}) = \text{first 2 bytes of}(E_K(c_{1} \dots c_{16})) \oplus (c_{17}, c_{18})$)} and check $p_{15} = p_{17}$ and $p_{16} = p_{18}$. If these are not the same, we throw the "bad key" error message.

Of course, this is only a heuristic check: One in each $2^{16}$ keys will still look right.

If you need a more certain check of the right key, use either a digital signature (in the encrypted package), or use a "Symmetrically Encrypted Integrity Protected Data Packet" (section 5.13) instead of a plain encrypted packet.