Post-Compromise Security

From CryptoWiki
Jump to: navigation, search

A protocol between Alice and Bob provides Post-Compromise Security (PCS) if Alice has a security guarantee about communication with Bob, even if Bob’s secrets have already been compromised.

This property is aimed primarily at adversaries who do not have sufficient resources to attack individually for each user on the network, but can obtain information about long-term keys in order to compromise traffic. An example of such adversaries may be Internet providers, government agencies, or network administrators in the company.


Post-Compromise Security Conditions

In [2] some conditions of PCS were given.

Figure 1. A Signed Diffie-Hellman key exchange protocol.
  • Post-compromise security is not achievable after unrestricted compromise of the intended peer.
  • If the adversary is not granted the key itself, but instead limited access to it that is revoked during the

secure session, then PCS can still be achieved.

  • If the adversary can compromise all but one exchange of messages before the secure session, then PCS

can still be achieved.

  • No stateless protocol is secure in KE-PCS, where KE-PCS is a model where adversary can observe all the communications between parties, and obtain any long-term key when the protocol isn't running.
  • No correct one-round protocol which is secure in KE-PCS is post-network robust, where it is post-network robust if protocol induces a pair of matching sessions which derive the same session key when executed sequentially after any network adversary, where network adversary is any passive eavesdropper.
  • The signed Diffie-Hellman key exchange protocol with existentially unforgeable under adaptive chosen message attack signature scheme (shown on Figure 1) is secure under decisional Diffie-Hellman assumption, if adversary cannot obtain session keys and randomnesses of any session and long-term keys of participants of active session.

Generic transformation of key agreement protocols to achieve PCS

Generic transformation of key agreement protocols to achieve PCS was presented in [2]. it taskes for example three-message protocol between A and B.

Figure 2. Example trace of a transformed protocol..

Assume that public DH keys are distributed for all participants, and that protocol computes a pre-master secret from which session keys are derived. New protocol defines as a modification of that protocol as follows:

  • For each agent B new global state variables IS(B,A) and st_potential are defined (for each communication partner A). The first stores a single value and the second a possibly empty list of values. Initially, IS(A,B) = 𝑔𝑎𝑏 for all A, B.
  • In a session s between parties A and B, each message 𝑚𝑗 from A to B is replaced by <𝑚𝑗, 𝜇𝑗> where 𝜇𝑗 = MAC(𝑚𝑗; IS(A,B)), and each from B to A is replaced by <𝑚𝑗, 𝜇𝑗> where 𝜇𝑗 = MAC(𝑚𝑗; IS(B,A))
  • Upon receiving <𝑚1, 𝜇1> acts as follows:
    • If 𝜇1 = MAC(𝑚1; IS(B,A)) continues to the next step.
    • If not, B checks for each value 𝑖𝑠 ∈ st_potential whether µ1 = MAC(m1; 𝑖𝑠). If this holds for some value is, B replaces IS(B,A) ← 𝑖𝑠, empties st_potential ← ∅, and continues to the next step.
    • Otherwise, B rejects.
  • The new value IS(B,A)new ← KDF(σ,IS(B,A),1) is appended to st_potential where KDF is key derivation function.
  • The pre-master secret pms ← KDF(σ) is replaced by pms′ ← KDF(σ,IS(B,A),0).
  • B computes and sends <𝑚2, 𝜇2>
  • A verifies 𝜇2 using its intermediate secret, and rejects if the verification fails. Otherwise, it updates IS(A,B) ← IS(A,B)new = KDF(σ,IS(A,B),1), and sends <𝑚3, 𝜇3>
  • B verifies 𝜇3 against the potential value from the current session, and if the verification passes and it would accept then it first sets IS(B,A) ← IS(B,A)new and st_potential ← ∅.

Example trace of a transformed protocol is displayed on Figure 2. There are w two sessions between Alice and Bob: in the first, the final message is dropped so Bob does not update to IS′. In the second, Bob recalls IS′ from earlier (represented by the dotted line) and performs the earlier missed update.


In [3] the protocol DECIM (Detecting Endpoint Compromise In Messaging) was presented, providing Post-Compromise Security. It was also used in the messenger of the same name.

The protocol uses a publicly accessible record database into which each user who wants to receive messages puts his certificate signed on a long-term key and stores the identifier and public key. It is assumed that the user also checks the record database for the presence of fake records and, if found, learns that his long-term key has been compromised. The messages are transmitted as follows:

  • The sender asks for the recipient's certificate in the record database
  • The sender checks the received certificate
  • If the check is successful, then the sender encrypts the message on the public key used in the certificate and sends it to the recipient.
  • The recipient decrypts the message using his secret key
  • The recipient checks the database for duplicates.

The persistence of this protocol is based on a publicly accessible records database and that an attacker will need to enter a fake certificate of the recipient in order to be able to introduce himself to it, which can not be done secretly because the database is publicly available.



Go to literature list

Return to the main page

Bogatyrev D.V., 2018