Post-quantum perfect forward+backward secrecy

[damip]

Intro

Goal: create a decentralized on-blockchain post quantum secure chat without out-of-band connection,
that provides both forward and backward secrecy.

All serializations are encoded with a length-prefixed binary encoding that:

• avoids length extension attacks
• avoids unsafe telescoping of multiple variable-length inputs

All crypto operations are constant-time, errors are handled.

Primitives used:

• hash: blake3
• HKDF: blake3 in derive_key mode
• KEM: Kyber-768
• AEAD: AES-256-GCM-SIV

RNG is cryptographically secure, sensitive data is zeroed when dropped, sensitive crypto is constant time.

Initiation

The goal of this part is to establish a conversation between two entities: Alice establishes a conversation towards Bob.
We assume that Alice and Bob know each other's static Kyber public keys AlicePk and BobPk, associated to secret keys AliceSk and BobSk.

Alice requests an initiation

Alice initializes a message towards Bob:

msg.dir = 0x01  // would be 0x02 if it was Bob, but here Alice is always the one initiating

Alice encapsulates Bob's public Kyber key:

msg.ct, msg.ss = kyberKEM.encaps(BobPk)

Alice draws a random number that will be used for derivation:

msg.rand = RNG(L=32)

Note that is impractical to use counters here as persisted on-chain state might not be trusted.

Alice derives:
msg.MK, msg.encK, msg.nonce = HKDF([BobPk, msg.ss, msg.rand], domain="Init1MasterKey|v1", L = [32,32,12])
Here, both outputs are derived from fresh randomness (msg.rand), a shared secret (msg.ss) and a binding specific to Bob's identity (BobPk):

• MK is the Master Key of the message
• encK is the AES-256-GCM-SIV AEAD encryption key of the message, with nonce reuse resistance
  Now Alice can delete msg.ss.

msg.pkNext, msg.skNext = kyberKEM.keyGen()
A brand new random Kyber KEM keypair is generated by Alice.

Add a few metadata:
msg.version = 0x01
msg.type = 0x01 // indicates an initiation message

msg.innerK = HKDF([msg.MK, msg.pkNext, msg.type, msg.version, AlicePk], domain = "Init1InnerK|v1", L = [32])
This is the integrity key that is stored inside the encrypted message.
It also brings extra entropy from the random pkNext.
It is also an input for the next parents so that any altered message breaks ancestry.

This is what will be encrypted:

msg.plaintext = {
    version = msg.version,
    type = msg.type,
    innerK = msg.innerK,
    pkNext = msg.pkNext,
    senderPk = AlicePk
}

This is the AEAD encryption:

msg.ciphertext = aesAEAD.encrypt(
    key = msg.encK,
    nonce = msg.nonce,
    plaintext = msg.plaintext
)

From here, Alice can delete msg.plaintext, msg.encK, msg.nonce.
No cleartext authenticated data is added on purpose: to not leak any information about what is happening.

Finally, Alice formulates the message post:

msg.postData = {
    ct = msg.ct,
    rand = msg.rand,
    ciphertext = msg.ciphertext
}

Then Alice simply posts msg.postData on the Bulletin smart contract.

At this point, Alice is convinced that only someone who owns the secret associated to Bob's public Kyber key can read this message.

Bob receives the initiation request

Bob scans all the msg.postData entries in the Bulletin that he has not scanned yet.
For each one of them, he tries the following, and ignores the message if any of it fails.

Bob sets:

msg.dir = 0x01 // Alice

First he reads msg.ct = msg.postData.ct to find:
msg.ss = kyberKEM.decaps(BobSk, msg.ct)

He can now read msg.rand = msg.postData.rand and compute:
msg.MK, msg.encK, msg.nonce = HKDF([BobPk, msg.ss, msg.rand], domain="Init1MasterKey|v1", L = [32,32,12])
Here Bob can delete msg.ss.

And decrypt msg.ciphertext = msg.postData.ciphertext:

msg.plaintext = aesAEAD.decrypt(
    key = msg.encK,
    nonce = msg.nonce,
    ciphertext = msg.ciphertext
)

Here, Bob can delete msg.encK.

From there Bob can extract:

msg.version = msg.plaintext.version
assert(msg.version is supported)
msg.type = msg.plaintext.type
assert(msg.type is 0x01)
msg.innerK = msg.plaintext.innerK
msg.pkNext = msg.plaintext.pkNext
msg.senderPk = msg.plaintext.senderPk

Then Bob can delete msg.plaintext.

Bob performs a quick integrity check:

msg.innerK = HKDF([msg.MK, msg.pkNext, msg.type, msg.version, msg.senderPk], domain = "Init1InnerK|v1", L = [32])

Here Bob is confident that the message is directed to him and claims to be from Alice,
but he doesn't know yet whether it was actually sent from Alice or by an impersonator.

Bob confirms channel initiation

If Bob is OK with what he sees so far, he confirms the channel initiation by proceeding as follows.

msg.dir = 0x02 // sent by Bob
This is the direction of the message.

No conversation ID or sequence counters are added to the message so that on compromission,
no information is revealed which avoids correlations on multiple compromissions.

We call p1 Alice's init message that Bob just finished reading (see above).

Bob computes the following for his message:
msg.outerKey, msg.locator = HKDF([p1.innerK, msg.dir], domain = "Init2OuterKey|v1", L = [32,32])
Where:

• key derivation is specific to both the latest secrets of the chosen parents and to their ancestry chain
• outerKey will be used for mixing the current message master key with the parent message's secrets and ancestry chain
• locator will be the tag at which the message will be published on the blockchain, so that Alice can find it immediately without scanning the whole blockchain

msg.ct, msg.ss = kyberKEM.encaps(AlicePk)
Where:

• ct is the KEM ciphertext deduced from Alice's key published in the latest message of Bob
• ss is the shared secret that was deduced from this decapsulation

msg.MK, msg.encK, msg.nonce = HKDF([msg.outerKey, msg.ss], domain="Init2MasterKey|v1", L = [32,32,12])
Here:

• MK is the Master Key of the message
• encK is the AES-256-GCM-SIV AEAD encryption key of the message, with nonce reuse resistance
• nonce is the unique nonce for that encryption. Unicity is guaranteed by both hash chain security outerKey and fresh secret randomness ss.
  Now Bob can delete msg.ss and msg.outerKey.

msg.pkNext, msg.skNext = kyberKEM.keyGen()
A brand new random Kyber KEM keypair is generated by Bob.

Add a few metadata:
msg.version = 0x01
msg.type = 0x02 // for an init response

msg.innerK = HKDF([msg.MK, msg.pkNext, msg.type, msg.version], domain = "Init2InnerK|v1", L = [32])
This is the integrity key that is stored inside the encrypted message.
It also brings extra entropy from the random pkNext, and ensures chained hashes.
It is also an input for the next parents so that any altered message breaks ancestry.

This what will be encrypted:

msg.plaintext = {
    version = msg.version,
    type = msg.type,
    innerK = msg.innerK,
    pkNext = msg.pkNext
}

This is the AEAD encryption:

msg.ciphertext = aesAEAD.encrypt(
    key = msg.encK,
    nonce = msg.nonce,
    plaintext = msg.plaintext
)

From here, Bob can delete msg.encK, msg.nonce.
No cleartext authenticated data is added on purpose: to not leak any information about what is happening.

Finally, Bob formulates the message post:

msg.postData = {
    ct = msg.ct,
    ciphertext = msg.ciphertext
}

Then Bob simply posts msg.postData at the tag msg.locator on the MessageBoard smart contract.

Here Bob knows that only Alice will be able to read his response and only if she was indeed the originator of the init message.
But for now, Bob still doesn't know if it is the case or not.
He will only be convinced once he receives the first normal message from Alice (see below).
However, Bob can safely send normal messages to Alice from now on without any risk (see below).

Alice receives Bob's init response

Alice now seeks Bob's init response in the MessageBoard using its locator.
We call p1 Alice's original init message.

Alice sets

msg.dir = 0x02 // message sent by Bob

Alice first computes:

msg.outerKey, msg.locator = HKDF([p1.innerK, msg.dir], domain = "Init2OuterKey|v1", L = [32,32])

and looks for a message at tag msg.locator.

When she succeeds, she tries to load the message msg form the post data msg.postData.
If anything fails, she ignores the message and continues her search, trying to process the next find.
If nothing is found, she assumes there is no response from Bob and tries later with a timeout.

First she reads msg.ct = msg.postData.ct to find:
msg.ss = kyberKEM.decaps(AliceSk, msg.ct)

She can now compute:
msg.MK, msg.encK, msg.nonce = HKDF([msg.outerKey, msg.ss], domain="Init2MasterKey|v1", L = [32,32,12])
Here Alice can delete msg.ss and msg.outerKey.

And decrypt msg.ciphertext = msg.postData.ciphertext:

msg.plaintext = aesAEAD.decrypt(
    key = msg.encK,
    nonce = msg.nonce,
    ciphertext = msg.ciphertext
)

Here, Alice can delete msg.encK, msg.nonce, msg.ciphertext.

From there Alice can extract:

msg.version = msg.plaintext.version
assert(msg.version is supported)
msg.type = msg.plaintext.type
assert(msg.type == 0x02) // init response
msg.innerK = msg.plaintext.innerK
msg.pkNext = msg.plaintext.pkNext

Here Alice can delete msg.plaintext.

Alice performs a quick integrity check:

assert msg.innerK == HKDF([msg.MK, msg.pkNext, msg.type, msg.version], domain = "Init2InnerK|v1", L = [32])

Here Alice can delete msg.MK.

Now Alice is convinced that she can trust the previous and next messages she reads in this session actually come from Bob and not an impersonator, and that any message she sends can only be read by Bob.

Post-quantum perfect forward + backward secrecy

Once the Initiation process above has happened, we focus on message exchange.

Alice sends a message to Bob

When one of the two participants in the chat emits a message, say we are on the "Alice" side:

msg.dir = 0x01 if Alice or 0x02 if Bob
This is the direction of the message: sent from Alice if msg.dir == 0x01.

No conversation ID or sequence counters are added to the message so that on compromission,
no information is revealed which avoids correlations on multiple compromissions.

Alice chooses two parent messages:

• the latest message she sent: p1
• the latest message from the other participant (Bob) that she saw so far: p2

Alice computes the following for her message msg:
msg.outerKey, msg.locator = HKDF([p1.innerK, p2.innerK, msg.dir], domain = "outerKey|v1", L = [32,32])
Where:

• key derivation is specific to both the latest secrets of the chosen parents and to their ancestry chain
• outerKey will be used for mixing the current message master key with the parent message's secrets and ancestry chain
• locator will be the tag at which the message will be published on the blockchain, so that Bob can find it immediately without scanning the whole blockchain

msg.ct, msg.ss = kyberKEM.encaps(p2.pkNext)
Where:

• ct is the KEM ciphertext deduced from the latest public Kyber key published in the latest message of Bob
• ss is the shared secret that was deduced from this decapsulation

msg.MK, msg.encK, msg.nonce = HKDF([msg.outerKey, msg.ss], domain="masterKey|v1", L = [32,32,12])
Here:

• MK is the Master Key of the message
• encK is the AES-256-GCM-SIV AEAD encryption key of the message, with nonce reuse resistance
• nonce is the unique nonce for that encryption. Unicity is guaranteed by both hash chain security outerKey and fresh secret randomness ss.
  Now Alice can delete msg.ss and msg.outerKey.

msg.pkNext, msg.skNext = kyberKEM.keyGen()
A brand new random Kyber KEM keypair is generated by Alice.

msg.payload = "Hello I am Alice"
This is the payload that Alice wants to send to Bob.

Add a few metadata:
msg.version = 0x01
msg.type = 0x03 // for a payload message

msg.innerK = HKDF([msg.MK, hash(msg.payload), msg.pkNext, msg.type, msg.version], domain = "innerK|v1", L = [32])
This is the integrity key that is stored inside the encrypted message.
It also brings extra entropy from the random pkNext, and ensures chained hashes for the whole history of both chosen parents.
It is also an input for the next parents so that any altered message breaks ancestry.

This what will be encrypted:

msg.plaintext = {
    version = msg.version,
    type = msg.type,
    innerK = msg.innerK,
    pkNext = msg.pkNext,
    payload = msg.payload
}

Here Alice can delete msg.payload.

This is the AEAD encryption:

msg.ciphertext = aesAEAD.encrypt(
    key = msg.encK,
    nonce = msg.nonce,
    plaintext = msg.plaintext
)

From here, Alice can delete msg.plaintext, msg.encK, msg.nonce.
No cleartext authenticated data is added on purpose: to not leak any information about what is happening.

Finally, Alice formulates the message post:

msg.postData = {
    ct = msg.ct,
    ciphertext = msg.ciphertext
}

Then Alice simply posts msg.postData at the tag msg.locator on the MessageBoard smart contract.

Bob reads Alice's message

Bob tries to seek for various parent combinations to find Alice's next message using the locator.
He sets p1 to be Alice's last message he has seen, and tries various p2 from Bob's posts that came after the one acknowledged by Alice's last post.
Search is capped by the numbe rof Messages Bob sent since Alice's message parent on Bob's side.

For each attempt he computes:

msg.outerKey, msg.locator = HKDF([p1.innerK, p2.innerK, msg.dir], domain = "outerKey|v1", L = [32,32])` where `msg.dir = 0x01 // Alice

and looks for a message at tag msg.locator.

When he succeeds, he tries to load the message msg form the post data msg.postData.
If anything fails, he ignores the message and continues his search, trying to process the next find.
If nothing is found, he assumes there are no awaiting messages from Alice.

First he reads msg.ct = msg.postData.ct to find:
msg.ss = kyberKEM.decaps(p2.skNext, msg.ct)

He can now compute:
msg.MK, msg.encK, msg.nonce = HKDF([msg.outerKey, msg.ss], domain="masterKey|v1", L = [32,32,12])
Here Bob can delete msg.ss and msg.outerKey.

And decrypt msg.ciphertext = msg.postData.ciphertext:

msg.plaintext = aesAEAD.decrypt(
    key = msg.encK,
    nonce = msg.nonce,
    ciphertext = msg.ciphertext
)

Here, Bob can delete msg.encK, msg.nonce, msg.ciphertext.

From there Bob can extract:

msg.version = msg.plaintext.version
assert(msg.version is supported)
msg.type = msg.plaintext.type
assert(msg.type is supported)
msg.innerK = msg.plaintext.innerK
msg.pkNext = msg.plaintext.pkNext
msg.payload = msg.plaintext.payload  // this is Alice's message that was sent to Bob ! 

Here Bob can delete msg.plaintext.

Bob performs a quick integrity check:

assert msg.innerK == HKDF([msg.MK, hash(msg.payload), msg.pkNext, msg.type, msg.version], domain = "innerK|v1", L = [32])

Here Bob an delete msg.MK.

As soon as Bob reads an Alice message that acknowledges a given message msg from Bob in its ancestry,
Bob can safely delete msg and all its ancestors on Bob's side.
Bob can also delete all the messages of Alice before the latest one he has observed.
The opposite applies as well for Alice.

If Bob sees many Alice's messages for a while but Bob's user does not respond,
Bob will automatically issue an empty message just to perform key healing and liveness check.

TODOs

• protect against front-running of locators
• file transfer