Oracle Attack Immunity
An oracle attack is a powerful technique used to discover information about the internal state of some system. The system is tested in some way, usually repetitively, and the response is analyzed.
My single point here is that when PGP is used in a unidirectional application like email, oracle attacks are impossible simply because there is no response available. I suppose in theory the attacker could try to get the recipient to manually send back the error messages, but that would only cause the sort of confusion that would not advance anything. A successful attack that depended on the actions of the users would involve social engineering at a high enough level to make messing around with the cryptography unnecessary. The desired information could be obtained directly from the users.
This immunity to oracle attacks comes from the simplicity of PGP. There are no low level automated subsystems to interact with. You are always interacting with a person.
This might seem to be a trivial observation and that I am giving PGP credit for something intrinsic to the application but this is a common source of confusion. It is often incorrectly assumed that oracle attacks applicable to online, connection oriented media are also relevant for the offline, non-connection oriented media where PGP is used.
But there is a reference to an oracle attack right in the OpenPGP standard!
Why yes, there is. See: An Attack on CFB Mode Encryption As Used By OpenPGP. This academic paper provides an excellent example that leads to a more detailed discussion.
The OpenPGP standard has a feature to allow a user to be informed that they have entered the wrong key. Using the GnuPG command line oriented OpenPGP implementation as an example this is what that would look like:
┌──────────────────────────────────────────────────────┐ │ Please enter the passphrase for decryption. │ │ │ │ Passphrase: ******************************__________ │ │ │ │ <OK> <Cancel> │ └──────────────────────────────────────────────────────┘ gpg: decryption failed: Bad session key
I can't help remarking in passing that there is a minor usability issue here. The user was asked to enter something called a “passphrase” but is then told that there is a bad “session key”. Even so handicapped, the user should still be able to figure out that the stuff they typed in was wrong and that they should try again. Without the passphrase check GnuPG would only know that something went wrong and would say this instead:
gpg: WARNING: encrypted message has been manipulated!
… which is actively misleading and provides the user no idea of what to do next. So the passphrase check is an important and required feature.
This is what normal PGP usage looks like:
First the sender and receiver agree on a key somehow. Then the sender uses that key to encrypt a message/file. At the point of encryption, the key can't be wrong so no error is possible. The encrypted message/file is then transferred to the custody of the receiver. The receiver uses the key to decrypt the message/file. Now a key error is possible. This error obviously would go to the receiver as they are the one that entered the incorrect key for decryption.
The passphrase check is based on the unencrypted data. Generally, in such a case it might be possible to learn things about the unencrypted data with some sort of oracle attack. The paper shows that this is possible.
So what do we need to set up this oracle? If we give the attacker direct access to the decryption program then we would have to give them access to the key so they could use it. Giving the attacker access to the key would make the oracle pointless; the attacker would just use the key to decrypt the entire thing. We have to somehow give the attacker access to the passphrase error without giving them access to either the key or the decrypted message. So we need to run the decryption program for the attacker which means we need to produce some sort of internet protocol or API to allow the attacker use the program in this specifically limited way. Since the oracle attack involves tens of thousands of guesses, that means that this process will need to be automated. The automatic process also justifies sending the error to the sender rather than the receiver; the sender in this case initiated the operation.
The result looks like this for “normal” operation:
The actual attack looks like this:
The “Attacking Sender” repeatedly modifies the encrypted message they wish to gain information about and sends it to the “Automated Receiver”. Some modifications will result in a “Passphrase Error” and some will not. The pattern of responses can be used to determine the unencrypted value of 2 bytes out of a 16 byte block after thousands of transmissions.
I would like to draw attention to the question of how the receiver knows how to send the passphrase error to the sender. Obviously as part of the protocol/API enough information must be maintained to allow this to be possible. This information would normally be referred to as connection information in the case of a network protocol. In other words, we have established a connection between sender and receiver.
I am claiming in this article that the offline non-connection oriented media that OpenPGP is used with are inherently immune to oracle attacks. This attack, if anything, supports my point by showing that it would be necessary to go to some significant amount of trouble to create a connection to make the attack work. It seems fairly obvious that it is unlikely that this would be done accidentally.
Note that this is an attack against the behaviour of particular OpenPGP implementations when used in unexpected ways, not the OpenPGP standard itself. If someone really wanted to use OpenPGP messages for a online connection oriented medium, OpenPGP provides a simple but effective modification detection code (MDC) that could be used to prevent oracle attacks under that sort of use.
There are other error conditions that could potentially be used to leak information about the unencrypted message using this sort of oracle. Examples:
- Data compression errors.
- Packet structure errors.
- Incorrect packet length.
- Unexpected packet order.
- Unexpected message length.
The same discussion applies…