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.

Judging by the algorithm on the Blowfish Wikipedia article, there is no way for the process to fail with an error. How then does GnuPG know when to tell you your password is correct when decrypting a file, rather than proceeding to decrypt meaningless data?

share|improve this question
3  
It could use the key it generates to check a MAC on the ciphertext. If the MAC doesn't verify you either have the wrong password or your ciphertext has been modified; in either case you don't decrypt. –  pg1989 Apr 29 at 22:10
1  
Did you see this question: crypto.stackexchange.com/questions/5921/… –  Thomas Apr 30 at 18:57

2 Answers 2

up vote 3 down vote accepted

An important property of a ciphertext is that it has to be indistinguishable from truly random data. This allows the encryption cipher to produce ciphertext that reveals no information about the plaintext (other than size) or the encryption key. In fact, this property even allows encryption algorithms to act as pseudorandom byte generators by simply making them generate a stream of random ciphertext.

In the case of stream ciphers, decryption is the result of XORing each ciphertext byte with its corresponding keystream byte in sequence. If the keystream byte corresponding to the ciphertext byte is correct, the result of the XOR will yield the original plaintext byte. Since ciphertext cannot be made to provide any information regarding the plaintext, it follows that it also cannot be made to reveal whether the XOR of a certain keystream byte yielded a correct plaintext for the byte or not. Otherwise, the cipher would be clearly broken and allow us to basically query it for information regarding the plaintext.

A similar principle applies to block ciphers such as Blowfish, except those ciphers operate on entire blocks of bytes instead of individual bytes, and also employ other operations such as substitution in tandem with XORs, organized in structures such as Feistel networks.

Therefore, when it's important to be able to inform the user whether a decryption operation has succeeded in yielding the expected data, cryptography engineers use Message Authentication Codes. Hash-based MACs allow a candidate plaintext to be compared against an authenticated hash value. If the check passes, then we know that it is the correct plaintext and are then able to notify the user that the decryption function was successful as intended.

Generally, if you want to verify the integrity of encrypted data as it goes through the wire to reach someone, you would generate a MAC for the ciphertext. But if you also want to verify that the decrypted plaintext is correct (as seems to be your case here,) then you would generate another MAC for the plaintext and send it along with the ciphertext.

While hash-based MACs are probably the preferred way to do this, they aren't the only way to verify successful decryption. For example, TrueCrypt will check the first four bytes of the volume header in order to see if decryption is successful. This approach is likely to be more error-prone than HMACs in most applications, however.

Finally, there are block cipher modes of operation (such as Galois Counter Mode) that grant block ciphers such as Blowfish or AES the ability to self-authenticate. This pretty much allows a ciphertext to verify its own integrity without the need for an external check. Depending on what you're trying to accomplish, you may want to investigate both HMACs and Galois Counter Mode and decide which offers the verification properties you're looking for.

share|improve this answer
1  
Thanks. I've been wondering about this for some time. And thanks for the coursera link. So essentially in MAC, a few bytes are prepended to the plaintext before encryption, and and these are known during decryption? –  Vortico Apr 30 at 0:43
    
An HMAC is a hash value (such as a SHA1 hash) that is generated by evaluating the plaintext in conjunction with an authentication key. The authentication key is necessary to prevent the modification of the HMAC itself. During verification, the same HMAC procedure is performed on the plaintext to be verified using the same authentication key. If the same final HMAC is obtained, we know we have the plaintext we're looking for. –  kaepora Apr 30 at 0:53

As a security measure, the processing time given to crafted encrypted messages and benignly encrypted messages must be the same. So I think in both cases the algorithm does the same, for example checks the MAC and decrypts the message.

share|improve this answer

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.