1 12b-DeniableForwardSecure

Previous: 12a-AppliedCryptoSystems.html

“Lots of people working in cryptography have no deep concern with real application issues.
They are trying to discover things clever enough to write papers about.”

- https://en.wikipedia.org/wiki/Whitfield_Diffie
(Whose revolutionary work these below methods were built upon)

1.1 What about OpenPGP?


1.1.1 What works well

If Alice and Bob are using OpenPGP messaging,
authentication and encryption enables the two users to trust both:
the source of the messages,
and privacy of the message contents.

Alice and bob can prove past agreements in writing.
What you said is provably attributable to your private key.

1.1.2 Problems

If either end-point has physical or digital compromise,
and secret keys are still on the device,
as they would need to be to see messages,
All messages from the past can be decrypted.
All messages going forward can be decrypted, or faked.
Alice or Bob can not deny what was written,
and their messages are provably theirs (non-repudiation).

Discussion question:
What are basic human assumptions of privacy in a personal conversation?
In informal terms?
In formal terms?
If both individuals care to keep the secret?
If one or both does not intend to keep the secrets?

1.2 Casual conversation in person

Alice and Bob talk in a room.
No one else can hear,
unless Alice or Bob record.
No one else knows what they say,
unless Alice or Bob tell them.
No one can prove what was actually said,
not even Alice or Bob.
These conversations are “off-the-record”.

Two goals:
1. Deniable authentication
2. Forward and reverse security

1.3 Goal 1: Deniable authentication

Trust without a provable record.

1.3.1 Problem

For privacy goals, we don’t want signatures on data:
Those are not deniable, as we covered previously:

Instead, we merely want to know we are talking to the right person,
and that the messages can’t reasonably be faked.
Yet, we want to be able to deny what was said.

Plausible deniability is the ability of people,
typically senior officials in a formal or informal chain of command,
to deny knowledge of or responsibility for any damnable actions,
committed by members of their organizational hierarchy.
They may do so because of a lack or absence of evidence that can confirm their participation,
even if they were personally involved in or at least willfully ignorant of the actions.
If illegal or otherwise disreputable and unpopular activities become public,
high-ranking officials may deny any awareness of such acts to insulate themselves,
and shift the blame onto the agents who carried out the acts,
as they are confident that their doubters will be unable to prove otherwise.
The lack of evidence to the contrary ostensibly makes the denial plausible (credible),
but sometimes, it makes any accusations only un-actionable.
The term typically implies forethought,
such as intentionally setting up the conditions for the plausible avoidance of responsibility,
for one’s future actions or knowledge.

Deniable authentication refers to message authentication between a set of participants,
where the participants themselves can be confident in the authenticity of the messages,
but content cannot be proved to a third party after the event (another cool trick!).

1.3.2 One general solution

Authenticate a ratcheted DH key exchange,
but not the messages!
What about message integrity?

Deniable authentication between two parties can be achieved by:
sharing message authentication keys between each party,
usually derived from a session key generated via DH.
We use message authentication codes (MACs),
making sure that if an attacker is able to decrypt the messages,
they would also know the MAC key as part of the protocol,
and would thus be able to forge authentic-looking messages.
Despite revealing the MAC key,
we don’t reveal the encryption keys.
We’ll come back to this later.

For now, let’s just focus on the secrecy part:

1.4 Goal 2: Forward secrecy/security (FS) protects the past

Also known as perfect forward secrecy (PFS).
“Perfect” is a misnomer,
which should be reserved for the OTP.

Forward secrecy is a feature of specific key agreement protocols,
that provides assurances your past session keys will not be compromised,
even if a current private key is compromised.
FS protects past sessions against future compromises of secret keys or passwords.

By generating a unique session key for every session a user initiates,
even the compromise of a single session key,
will not affect any past data,
compromising only that exchanged in the specific session,
protected by that particular key.

We will cover various attempts to solve this problem:
1. Symmetric forward secrecy
2. Asymmetric forward secrecy
3. OTR
4. Double-Ratchet / Axolotl / MLS

1.4.1 General idea of symmetric forward secrecy/security

Protects the past, but not the future.
Uses a master key and key derivation function (KDF) to generate a chain of new keys:
KDF is one-way, initialized with master key as the seed. What works well

If current session key is compromised,
old conversations are not compromised. Problems?

If current session key is compromised,
new conversations can be decrypted by adversary,
because session key generation is deterministic.

If the master key is compromised,
in some implementations,
then all conversations are decrypted.

Session/round keys must be kept around to decrypt messages,
and thus are vulnerable to stealing and future compromise. Solutions?

To improve future secrecy in the event of session key compromise,
add a secret root key (constant below).

To solve the above storage issue,
use a KDF to generate a chain key,
and from that chain key,
generate (one-way) a derivative key (message key below).
12b-DeniableForwardSecure/Set0_1.png Problems?

If a combination of the root key (constant) and either:
any session key (chain key),
or master key are compromised,
then all future messages are decrypted

What about authentication?
Can check independent asymmetric keys, or:

1.4.2 General idea of asymmetric forward secrecy/security

Protects the past and the future.
The following is a hypothetical example of a simple instant messaging protocol that employs forward secrecy:

  1. Alice and Bob each generate a pair of long-term, asymmetric public and private keys,
    then verify public-key fingerprints in person or over an already-authenticated channel.
    The only thing these keys will be used for is authentication,
    including signing messages, and signing things during session key exchange.
    These keys will not be used for encryption of message data of any kind.

  2. Next, Alice and Bob use a key exchange algorithm such as Diffie-Hellman,
    to securely agree on an ephemeral session key.
    They use the keys from step 1,
    only to authenticate one another during this process.

  3. Alice sends Bob a message,
    encrypting it with a symmetric cipher,
    using the session key negotiated in step 2.

  4. Bob decrypts Alice’s message using the key negotiated in step 2.

  5. The process repeats for each new message sent,
    starting from step 2.
    (and switching Alice and Bob’s roles as sender/receiver as appropriate).
    Step 1 is never repeated.

Even if one of the keys generated in an iteration of step 2 is compromised,
this forward secrecy ensures that past communications cannot be decrypted.
We generate new session keys for each message,
and such a key is only used to encrypt a single message.
In the event of a session key compromise,
what about future messages?

Even if the long-term private keys from step 1 are compromised,
this form of forward secrecy also ensures that past communications cannot be decrypted.
However, masquerading as Alice or Bob would be possible going forward if this occurred,
possibly compromising authenticity of all future messages.
Is secrecy of future encrypted data still in tact?
If the adversary can physically be an active man in the middle?
If the adversary can merely observe? Formalization of DH ratchet

To implement the above “DH ratchet”,
each party generates a DH key pair,
a Diffie-Hellman public key (public DH product) and private key (secret exponent),
which becomes their current ratchet key pair.

DH terminology is a little different here.
Private key is just the private DH exponent.
Public key is the broadcast DH product.

Every message from either party begins with a header,
which contains the sender’s current ratchet public key.
When a new ratchet public key is received from the remote party,
a DH ratchet step is performed,
which replaces the local party’s current ratchet key pair with a new key pair.
This results in a “ping-pong” behavior,
as the parties take turns replacing ratchet key pairs.

An eavesdropper who briefly compromises one of the parties might learn the value of a current ratchet private key,
but that private key will eventually be replaced with an un-compromised one.
At that point, the Diffie-Hellman calculation between ratchet key pairs will define a DH output unknown to the attacker.

The following diagrams show how the DH ratchet derives a shared sequence of DH outputs:

Alice is initialized with Bob’s ratchet public key.
Alice’s ratchet public key isn’t yet known to Bob.
As part of initialization,
Alice performs a DH calculation between her ratchet private key and Bob’s ratchet public key:
Alice’s initial messages advertise her ratchet public key.
Once Bob receives one of these messages,
Bob performs a DH ratchet step.
He calculates the DH output between Alice’s ratchet public key and his ratchet private key,
which equals Alice’s initial DH output.
Bob then replaces his ratchet key pair and calculates a new DH output:
Messages sent by Bob advertise his new public key.
Eventually, Alice will receive one of Bob’s messages and perform a DH ratchet step,
replacing her ratchet key pair and deriving two DH outputs,
one that matches Bob’s latest and a new one:
Messages sent by Alice advertise her new public key.
Bob will receive one of these messages and perform a second DH ratchet step,
and so on:

1.4.3 What works well?

If session key is compromised,
past conversations are fine
If session key is compromised,
future conversations are fine (self-healing!)

1.4.4 Problems?

What about message integrity/authentication?
We need long-term asymmetric signing keys for that!

1.5 “Off-the-Record Communication, or, Why Not To Use PGP”

Was the title of the original paper:

Off-the-Record Messaging (OTR) is a cryptographic protocol.
It provides encryption for instant messaging conversations.
OTR uses a combination of some basic methods:

DSA assymetric keys for signing,
AES symmetric-key algorithm with 128 bits key length for encrypting,
the Diffie-Hellman key exchange with 1536 bits group size for ratcheted keys,
and a SHA hash function with HMAC for authentication.

In addition to authentication and encryption,
OTR provides forward secrecy and malleable encryption.
It provides deniable authentication for the conversation participants,
while keeping conversations confidential,
like a private conversation in real life,
or genuine off the record in journalism sourcing.

This is in contrast with pre-existing cryptography tools,
that produced output which can be later used as a verifiable record of:
the communication event,
and the identities of the participants.

It provides solutions to both our goals above:
1. Forward secrecy
2. Deniable authentication

1.5.1 Forward secrecy

Messages are only encrypted with temporary per-message AES keys,
negotiated using a ratcheted Diffie-Hellman key exchange protocol.
The compromise of any long-lived cryptographic keys does not compromise any previous conversations,
even if an attacker is in possession of ciphertexts.
Temporary session key compromise is also self-healing.

1.5.2 Deniable authentication

Messages themselves do not have digital signatures,
and after a conversation session is complete,
anyone who can decrypt that session is able to forge a message,
to appear to have come from one of the participants in the conversation.
This insures that it is impossible to prove that a specific message came from a specific person.
Within the conversation,
the recipient can be sure that a message is coming from the person they have identified.

Asymmetric DSA is used for signatures of DH ratchet.
Signed DH key per session.
Derive MAC key (MK) from each DH key (via one-way KDF).
Each MK is available to each party.
Alice and Bob have access to every MK.
The MK + message is used to compute a MAC.
Bob cannot prove that Alice generated a particular MAC.
He could have done so as well.
Anyone who can verify a message, can also forge a MAC.

1.5.3 Overview of protocol

OTR assumes a network model which provides in-order delivery of messages,
but that some messages may not get delivered at all,
for example, if the user disconnects.
There may be an active attacker,
who is allowed to perform a Denial of Service attack,
but not to learn the contents of messages.
It is often implemented over XMPP or IRC (synchronous chat systems).

  1. Alice signals to Bob, using an OTR Query Message,
    that she would like to use OTR to communicate.
    She also conveys the version(s) of OTR that Alice is willing to use.

  2. Bob initiates the authenticated key exchange (AKE) with Alice.
    Versions 2 and 3 of OTR use a variant of the SIGMA protocol as its AKE.

  3. Alice and Bob exchange Data Messages to send information to each other. Step 0: Long term DSA signing keys

Alice and bob generate and authenticate long-term DSA signing keys.
OTR users have long-lived public keys that they use for authentication (but not encryption).
The current version of the OTR protocol supports DSA public keys,
and there is a key type marker for future extensibility. Step 1: Authenticated DH Step 2: Message transmission

Encryption Key (EK)
MAC key (MK) Step 3: Re-key

This results in forward secrecy! Step 4: Publish MK

Alice and Bob do not need to “forget MK.
They no longer use it for authentication.
In fact, they publish the old MK along with the next message.
This lets anyone forge messages,
but only past ones.
Provides extra deniability. Detailed spec


1.5.4 What works well?

If session key is compromised,
past conversations are fine

If session key is compromised,
future conversations are fine (self-healing!)

1.5.5 Problems?

If long term DSA private key is compromised,
future conversations are vulnerable to MITM.

How long does session key material stay around?
For a single DH ratchet session.

What about slow or asynchronous messaging?
This can delay DH exchanges.
If a session key is compromised,
some moderate (though limited) number of messages may be decrypted.


1.6 Further advances (solution to last two points above)

When DH ratcheting must be slower,
due to asynchronous communications,
the double ratchet helps allow key material to be deleted more quickly,
and to cycle symmetric key material.

It combines the symmetric and asymmetric examples above,
to improve the between-DH-exchange security of OTR,
and keep keys on the disk for shorter time.
See full spec here:

1.7 Further reading

FS (or partial FS) deniability for personal communications
* https://en.wikipedia.org/wiki/Off-the-Record_Messaging
* https://otr.cypherpunks.ca/
* https://otr.cypherpunks.ca/Protocol-v3-4.1.1.html
* https://en.wikipedia.org/wiki/Forward_secrecy
* https://en.wikipedia.org/wiki/Transport_Layer_Security#Key_exchange_or_key_agreement
* https://en.m.wikipedia.org/wiki/Socialist_millionaires
* https://en.wikipedia.org/wiki/Deniable_encryption
* https://en.wikipedia.org/wiki/Deniable_authentication
* https://en.m.wikipedia.org/wiki/Authenticated_encryption
* https://en.wikipedia.org/wiki/Double_Ratchet_Algorithm
* https:_messaginglayersecurity.rocks/ (https:_wire.com version)
* https://signal.org/blog/advanced-ratcheting/
* https://signal.org/docs/
* https://en.wikipedia.org/wiki/Signal_Protocol (signal’s version)
* https://en.wikipedia.org/wiki/OMEMO (XMPP version)
* https://en.m.wikipedia.org/wiki/ZRTP (FS for voice/video)

Next: 13b-ReverseEngineering.html