LEAKYTAP released - is a proof-of-concept GPG backdoor.

LEAKYTAP released – is a proof-of-concept GPG backdoor.

LEAKYTAP is a proof-of-concept GPG backdoor that aims to leak the target user’s private key by using the GPG session key as a subliminal channel. The backdoor is currently limited to targeting RSA public keys only but can be modified to support other GPG public key types as well. The backdoor was designed with a certain degree of covertness with respect to the average GPG user in mind but does not provide strong properties such as confidentiality with forward-secrecy or deniability to the attacker in the face of a more advanced user. The use-case i had in mind when designing the backdoor was an attacker intercepting some security-related embedded device en-route to the target modifying its firmware to include the backdoored GPG executable (hence the choice for writing the patch for GnuPG classic) in order to learn the target user’s private key but it is certainly not limited to such a scenario.

Consider a n-bit public modulus N (with n/2-bit prime factors p and q) and a 256-bit (the standard and maximum in GPG) symmetric session key, an attacker Mallory and a target Alice. The backdoor works as follows:
– Mallory seeks to obtain the private key corresponding to Alice’s public key and manages to backdoor Alice’s GPG executable with her backdoor.
– Mallory triggers the backdoor by sending a message with a specially crafted session key (see below) encrypted with Alice’s public key to Alice
– When Alice decrypts Mallory’s message, the private key corresponding to the public key it was encrypted with becomes accessible to GPG. A fragment (the size of the channel bandwith) of the prime factor p is extracted and encrypted by the attacker’s symmetric key embedded in the backdoor, using an IV derived from Mallory’s session key. This encrypted fragment is stored in a temporary file.
– When Alice sends a response message (to anyone, not only Mallory), the backdoor retrieves the currently stored encrypted fragment and sets the session key to it. Thus, once Alice responds to Mallory the latter can extract a leaked fragment of the prime factor p.
– Mallory repeats this process as many times as necessary (depending on channel bandwith and prime factor size) until she can recover Alice’s private key.

Mallory’s trigger session keys
Mallory’s session keys are formatted as follows:

[I|IV|G]

Where I is an index byte, IV the randomized 128-bit IV and 120 bits of random garbage G. The index byte indicates what fragment of the prime factor is to be leaked next and does so by falling in one of several ‘buckets’ (ie. byte ranges) determined by the prime factor size and channel bandwith. For example, assume we have 1024-bit prime factors and 256-bit session keys, then we need to leak p in 4 fragments hence we can express the indexes {0,..,3} as the ranges {{0x00,..,0x3F},{0x40,..,0x7F},..}. Hence if mallory wants to leak the 256 uppermost bits of p she sets I = random(0x00,0x3F).
Alice’s response session keys
When there is an ‘unretrieved leak’ (ie. Mallory has sent a trigger message but Alice has not responded to Mallory yet) Alice’s response session keys consist of fragments of prime factor p encrypted using AES-256 in CBC mode with the attacker’s embedded symmetric key and the IV specified by the last trigger message from Mallory. A 3rd party Bob communicating with Alice has a chance of backdoor discovery if there is an unretrieved leak and Alice sends more than one message to Bob. This is the case since as long as the leak goes unretrieved (ie. Mallory sends no new trigger message), the session key chosen by alice is static and Bob will notice identical session keys for different messages. This could be addressed by the attacker by including a random nonce (at the cost of reduced channel bandwith) with the leaked fragment and encrypting it right before sending it instead of before storage.
Partial leaking and key reconstruction

Should Alice break of communication with Mallory (or Mallory choose to limit backdoor interaction) before the entire prime factor is recovered it is still possible for Mallory to reconstruct Alice’s private key from partial prime factor exposure. It is known from reseach regarding partial key exposure attacks [1] [2] that efficient reconstruction of the private key is possible given access to the n/4 (where n is the modulus bitsize) most or least significant bits of a modulus prime factor (or possibly less using eg. techniques proposed in [3]) or ~27% of any of the private exponent bits at random. This can be used by Mallory by reducing the protocol run to an exchange of 2 (for 2048-bit keys) or 4 (for 4096-bit keys) GPG messages.
Example protocol run, Below is an example backdoor protocol run:

Mallory: session_key = [I0|IV0|G0]
Alice: session_key = E(p[0:256], K, IV0)
Mallory: session_key = [I1|IV1|G1]
Alice: session_key = E(p[256:512], K, IV1)
Mallory: session_key = [I2|IV2|G2]
Alice: session_key = E(p[512:768], K, IV2)
Mallory: session_key = [I3|IV3|G3]
Alice: session_key = E(p[768:1024], K, IV3)

Design Rationale
The backdoor was designed with the average GPG user in mind (as a target) and as such focuses on the following:
+ Avoiding suspicious ‘out of context’ passphrase queries or long-term keylogging by the backdoored GPG in order to access encrypted private keys
+ Avoiding modifications to public keys
+ Avoiding Low-bandwith channels requiring intensive interaction
+ Guaranteeing exclusive backdoor usage by the attacker

Obviously, the backdoor does not achieve such properties as undetectability and deniability but is probably still sufficiently covert to bypass average scrutiny.

Confidentiality
While Alice broadcasts leaked data to all parties she communicates with, only those parties in posession of both the IVs and attacker’s embedded secret key can use the backdoor. Given that access to the secret key is predicated upon access to the backdoor and access to the IVs predicated upon either access to the backdoor or Alice’s private key this guarantees exclusive backdoor usage to the attacker.

(Un)detectability
The idea is that while public keys are commonly scrutinized by the average security-conscious user this does not go for the, essentially ‘throwaway’, session keys. Embedding our subliminal channel in the session keys has the added benefit of being able to retroactively copromise preexisting public keys rather than, for example, only those generated with a backdoored key generation mechanism (such as many of the so-called SETUP attacks). Similarly opting for a high-bandwith channel by leaking as much of the private key as we can per backdoor interaction limits the total amount of interaction (translating to eg. fewer GPG e-mails requiring a response) which might arouse suspicion in the average user.

Mallory’s triggering session keys are virtually indistinguishable from random session keys since 248 out of 256 bits (IV + garbage) are randomly generated and while the 8 most significant bit indicate the fragment to leak they do so in a rather inconspcious fashion (see above).

More problematic are Alice’s leaking session keys. It should be noted that anyone can ‘trigger’ the backdoor insofar that the session key of any party communicating with Mallory is treated as a ‘trigger’ and subsequently Alice’s session keys are derived from this leak. The temp storage used to hold a leak triggered by the last message received by Alice only gets updated upon decrypting new messages. Hence any messages sent by Alice without intermittent decryption (of messages by any party, not just Mallory) result in identical session keys, something that might be noticed by any party (or collaborating parties) receiving multiple messages from Alice in such a case. The attacker could mitigate this by including a nonce (in the fashion noted above) at the price of reduced channel bandwith.

Finally, the rather blunt way used to store encrypted leaked fragments (in a temporary file) might arouse some suspicion as well though modifying this part to achieve additional covertness should not prove difficult.

Deniability
The backdoor offers some deniability to Mallory since instead of leaking exclusively to Mallory the backdoor leaks to all communicating parties. In order to prove Mallory was the party interacting with the backdoor Alice would have to retain a backarchive of Mallory’s GPG messages to her so that upon discovery of the backdoor she could extract the encrypted leak fragment from the temporary storage, try all candidate IVs in Mallory’s trigger session keys (in combination with the extracted backdoor secret key) and check whether the result is part of a prime factor of her private key. While this is certainly plausible and requires relatively little effort, it at least complicates matters for those users who practice ‘burn after reading’ or in those setups where GPG usage is automated and merely the plaintext content is processed/stored while the original ciphertext is discarded.

Reliability
The backdoor suffers from some reliability issues arising from the fact that any session key is treated as a trigger key and hence there is the possibility that Alice decrypts a 3rd party’s message between decrypting Mallory’s trigger and sending a response, thus leading to Mallory retrieving corrupted plaintext. This can be addressed by, upon detecting corruption, executing several protocol iterations and recombining the recovered pieces (with some possible redundancy). The number of re-tries depends on Alice’s communication practices (immediate response or not, etc.), number of parties Alice is in communication with and communication frequency. All in all this does not seem to be a major obstacle to backdoor usability.
Modifications to the GPG source

The backdoor patch was designed for the latest GnuPG classic release (1.4.19) but can be trivially (back)ported to either older GnuPG classic versions or GnuPG stable and modern releases.

Server
The backdoor modifies two functions:
+ make_session_key in g10/seskey.c
+ get_session_key in g10/pubkey-enc.c

The modifications in make_session_key consist of replacing the session key generation functionality with functionality that reads the contents of the temporary storage file (up to the session key size) and simply sets the session key to these contents. Should this fail, it reverts back to the original functionality and generates a regular session key.

The modifications in get_session_key consist of checking whether the private key is of the correct type (currently RSA 2048 & 4096 only), confirms the session key contains a trigger message, extracts the IV and determines what fragment of the private key to leak. The leaked fragment is then encrypted with AES-256 in CBC mode using the attackers embedded key and the extracted IV and stored in a temporary file for later retrieval by make_session_key.

Finally, the backdoor contains some attacker-definable configuration data in backdoor.h.
Client
Due to time constraints, rather than writing GPG packet building functionality into the python client from scratch i decided to make a quick & (very) dirty patch for the GPG client to allow for user-specified session keys, it modifies:

encode_crypt in g10/encode.c

The modification in encode_crypt consists of replacing the call to make_session_key with a simple call that reads the session key from a predefined filename (/tmp/session_key.dek).

Using the backdoor
Consider the scenario where Mallory manages to intercept Alice’s embedded security device en-route and modifies the firmware to include our LEAKYTAP backdoor. Alice has a 2048-bit RSA public key and so does Mallory.
Mallory applies backdoor_client.patch to her GPG source and applies backdoor_server.patch to the GPG installation in the intercepted device. She then obtains Alice and Mallory’s public keys:

Mallory starts by crafting trigger keys:

Mallory now sends the first message (the content of which is irrelevant but should entice Alice to respond) using the first session key, to which Alice responds and to which Mallory responds again and so on until Mallory has collected 4 responses from Alice (while 2 will suffice using partial key exposure attacks the backdoor client does not contain code to automate this so i will demonstrate a full protocol run instead). For example, Mallory crafts the first message:

Which Alice decrypts and to which she responds

From these responses Mallory extracts the session keys:

And couples them (in-order) to the IVs and feeds them into the backdoor client to obtain Alice’s leaked private key:

The following few lines of python show this private key corresponds to Alice’s public key (though not in proper GPG format but that would require implementing additional proper GPG formatting functionality which i didn’t have the time for):

When executed:

Download : Leakytap.zip  | Clone Url
Source : https://github.com/samvartaka