Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

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_{16} = 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.