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)
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.
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,
then:
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?
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
Trust without a provable record.
For privacy goals, we don’t want signatures on
data:
Those are not deniable, as we covered previously:
https://en.wikipedia.org/wiki/Non-repudiation
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.
https://en.wikipedia.org/wiki/Plausible_deniability
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.
https://en.wikipedia.org/wiki/Deniable_authentication
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!).
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:
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
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.
If current session key is compromised,
old conversations are not compromised.
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.
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).
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:
Protects the past and the future.
The following is a hypothetical example of a simple instant messaging
protocol that employs forward secrecy:
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.
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.
Alice sends Bob a message,
encrypting it with a symmetric cipher,
using the session key negotiated in step 2.
Bob decrypts Alice’s message using the key negotiated in step 2.
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?
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.
Note:
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.
Eventually,
Bob will receive one of these messages and perform a second DH ratchet
step,
and so on:
If session key is compromised,
past conversations are fine
If session key is compromised,
future conversations are fine (self-healing!)
What about message integrity/authentication?
We need long-term asymmetric signing keys for that!
Was the title of the original paper:
https://otr.cypherpunks.ca/otr-wpes.pdf
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
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.
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.
Mechanism:
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.
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).
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.
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.
https://en.wikipedia.org/wiki/Proof_of_knowledge#Sigma_protocols
Alice and Bob exchange Data Messages to send information to each other.
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.
Encryption Key (EK)
MAC key (MK)
This results in forward secrecy!
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.
https://otr.cypherpunks.ca/Protocol-v3-4.1.1.html
If session key is compromised,
past conversations are fine
If session key is compromised,
future conversations are fine (self-healing!)
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.
+++++++++++++++++++++
Cahoot-12b.1
https://en.wikipedia.org/wiki/Double_Ratchet_Algorithm
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:
https://signal.org/docs/specifications/doubleratchet/
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)