Signal Protocol Post Quantum Security - Revision history

Wolfm at 08:33, 3 September 2025

2025-09-03T08:33:17Z

← Older revision		Revision as of 08:33, 3 September 2025
Line 22:		Line 22:
	==Required Keys==		==Required Keys==
	For the protocol, each participant requires two and a set of key-pairs. The public keys are uploaded to the server.		For the protocol, each participant requires two and a set of key-pairs. The public keys are uploaded to the server.
	* Identity Key <math>^{\mathrm{pre}}\mathrm{IK}_{\mathrm{X}}</math>		* Identity Key <math>{}^{\mathrm{pre}}\mathrm{IK}_{\mathrm{X}}</math>
	** Used for authentication, can be checked before or after handshake		** Used for authentication, can be checked before or after handshake
	* (Signed) Prekey <math>^{\mathrm{pre}}\mathrm{SPK}_{\mathrm{X}}</math>		* (Signed) Prekey <math>{}^{\mathrm{pre}}\mathrm{SPK}_{\mathrm{X}}</math>
	** Used for forward secrecy		** Used for forward secrecy
	* Set of one-time pre-keys <math>^{\mathrm{pre}}\mathrm{OPK}_{\mathrm{X}}</math>		* Set of one-time pre-keys <math>{}^{\mathrm{pre}}\mathrm{OPK}_{\mathrm{X}}</math>
	** Used for (better) forward secrecy		** Used for (better) forward secrecy

Line 33:		Line 33:

	<math>		<math>
	^{\mathrm{pre}}k_\mathrm{1} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{IK}_{\mathrm{A;priv}}, ^{\mathrm{pre}}\mathrm{SPK}_{\mathrm{B;pub}})		{}^{\mathrm{pre}}k_\mathrm{1} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{IK}_{\mathrm{A;priv}}, ^{\mathrm{pre}}\mathrm{SPK}_{\mathrm{B;pub}})
	</math>		</math>

	<math>		<math>
	^{\mathrm{pre}}k_\mathrm{2} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{IK}_{\mathrm{B; pub}})		{}^{\mathrm{pre}}k_\mathrm{2} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{IK}_{\mathrm{B; pub}})
	</math>		</math>

	<math>		<math>
	^{\mathrm{pre}}k_\mathrm{3} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{SPK}_{\mathrm{B; pub}})		{}^{\mathrm{pre}}k_\mathrm{3} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{SPK}_{\mathrm{B; pub}})
	</math>		</math>

Line 61:		Line 61:

	===SI-X3DH===		===SI-X3DH===
	The proposed protocol is a slight modification of standard X3DH. Instead of Diffie-Hellman SIDH is employed. At the time of publishing it was known, that SIDH was susceptible to adaptive key attacks. Thus the protocol applies methods of ensuring honest key generation. The ephemeral key used is generated through the Fujisaki-Okamoto (FO) transformation. <math>\pi</math> can be used by the recipient for an FO-proof. For each identity the owner uploads a non-interactive zero-knowledge proof to the server, ensuring the owner is in possession of the private key. Since this proof is apparently resource intensive, this proof is omitted for <math>^{\mathrm{post}}\mathrm{SPK}_{\mathrm{X}}</math>. Thus the <math>k_1</math> calculation needs to be modified, replacing <math>^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B;pub}}</math> with <math>^{\mathrm{post}}\mathrm{IPK}_{\mathrm{B;pub}}</math>. This change slightly weakens forward security, since now <math>k_1</math> is static between two users and a breach of an identity key would be more severe. The protocol relied solely on SIDH, without any classical security.		The proposed protocol is a slight modification of standard X3DH. Instead of Diffie-Hellman SIDH is employed. At the time of publishing it was known, that SIDH was susceptible to adaptive key attacks. Thus the protocol applies methods of ensuring honest key generation. The ephemeral key used is generated through the Fujisaki-Okamoto (FO) transformation. <math>\pi</math> can be used by the recipient for an FO-proof. For each identity the owner uploads a non-interactive zero-knowledge proof to the server, ensuring the owner is in possession of the private key. Since this proof is apparently resource intensive, this proof is omitted for <math>{}^{\mathrm{post}}\mathrm{SPK}_{\mathrm{X}}</math>. Thus the <math>k_1</math> calculation needs to be modified, replacing <math>{}^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B;pub}}</math> with <math>{}^{\mathrm{post}}\mathrm{IPK}_{\mathrm{B;pub}}</math>. This change slightly weakens forward security, since now <math>k_1</math> is static between two users and a breach of an identity key would be more severe. The protocol relied solely on SIDH, without any classical security.

	<math>^{\mathrm{post}}k_\mathrm{1} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{IK}_{\mathrm{A;priv}}, ^{\mathrm{post}}\mathrm{IK}_{\mathrm{B;pub}})</math>		<math>{}^{\mathrm{post}}k_\mathrm{1} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{IK}_{\mathrm{A;priv}}, ^{\mathrm{post}}\mathrm{IK}_{\mathrm{B;pub}})</math>

	<math>^{\mathrm{post}}k_\mathrm{2} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{IK}_{\mathrm{B; pub}})</math>		<math>{}^{\mathrm{post}}k_\mathrm{2} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{IK}_{\mathrm{B; pub}})</math>

	<math>^{\mathrm{post}}k_\mathrm{3} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B; pub}})</math>		<math>{}^{\mathrm{post}}k_\mathrm{3} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B; pub}})</math>

	<math>\big[^{\mathrm{post}}k_\mathrm{4} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{OPK}_{\mathrm{B; pub}})\big]</math>		<math>\big[^{\mathrm{post}}k_\mathrm{4} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{OPK}_{\mathrm{B; pub}})\big]</math>
Line 90:		Line 90:

	===PQXDH===		===PQXDH===
	In May 2023 Signal published the first revision of the PQXDH protocol, intended to replace X3DH. Similar to Tutanota's proposal it's a hybrid protocol. Currently, it is only a slight modification of X3DH. As of September 2023, Signal added PQXDH to all Signal apps, enabling some quantum secure handshakes. As KEM Kyber-1024 is used. Each user generates a set of one-time PQ-secure keys <math>^{\mathrm{post}}\textrm{PQOPK}_{X}^i</math> including signatures and a last resort (semi-)static <math>^{\mathrm{post}}\textrm{PQSPK}_{X}</math>. The server hands out one-time keys until they are exhausted. During the handshake, Alice encapsulates a secret using Bob's public key:		In May 2023 Signal published the first revision of the PQXDH protocol, intended to replace X3DH. Similar to Tutanota's proposal it's a hybrid protocol. Currently, it is only a slight modification of X3DH. As of September 2023, Signal added PQXDH to all Signal apps, enabling some quantum secure handshakes. As KEM Kyber-1024 is used. Each user generates a set of one-time PQ-secure keys <math>{}^{\mathrm{post}}\textrm{PQOPK}_{X}^i</math> including signatures and a last resort (semi-)static <math>{}^{\mathrm{post}}\textrm{PQSPK}_{X}</math>. The server hands out one-time keys until they are exhausted. During the handshake, Alice encapsulates a secret using Bob's public key:

	<math>(c_\textrm{pq}, ^{\mathrm{post}}k_\textrm{pq}) = \textrm{encaps}(^{\mathrm{post}}\textrm{PQPK}_{B; pub})</math>		<math>(c_\textrm{pq}, ^{\mathrm{post}}k_\textrm{pq}) = \textrm{encaps}(^{\mathrm{post}}\textrm{PQPK}_{B; pub})</math>

Wolfm: /* Intiate Handshake */

2023-10-24T13:56:29Z

Intiate Handshake

← Older revision		Revision as of 13:56, 24 October 2023
Line 30:		Line 30:

	==Intiate Handshake==		==Intiate Handshake==
	Assuming Alice wants to write Bob. She first downloads a key bundle including, if available, a one-time key as well. She verifies the signature of SPK and then generates an ephemeral key pair EK. With these keys, she performs three or [four] DH calculations:		Assuming Alice wants to write Bob. She first downloads a key bundle including, if available, a one-time key as well. She verifies the signature of SPK and then generates an ephemeral key pair EK. With these keys, she performs three or <math>\big[</math>four<math>\big]</math> DH calculations:

	<math>		<math>

Wolfm: /* Intiate Handshake */

2023-10-24T13:53:44Z

Intiate Handshake

← Older revision		Revision as of 13:53, 24 October 2023
Line 30:		Line 30:

	==Intiate Handshake==		==Intiate Handshake==
	Assuming Alice wants to write Bob. She first downloads a key bundle including, if available, a one-time key as well. She verifies the signature of SPK and then generates an ephemeral key pair EK. With these keys, she performs three or four DH calculations:		Assuming Alice wants to write Bob. She first downloads a key bundle including, if available, a one-time key as well. She verifies the signature of SPK and then generates an ephemeral key pair EK. With these keys, she performs three or [four] DH calculations:

	<math>		<math>

Wolfm: /* PQXDH */

2023-10-24T13:52:56Z

PQXDH

← Older revision		Revision as of 13:52, 24 October 2023
Line 90:		Line 90:

	===PQXDH===		===PQXDH===
	In May 2023 Signal published the first revision of the PQXDH protocol, intended to replace X3DH. Similar to Tutanota's proposal it's a hybrid protocol. Currently, it is only a slight modification of X3DH. As of September 2023, Signal added PQXDH to all Signal apps, enabling some quantum secure handshakes. As KEM Kyber-1024 is used. Each user generates a set of one-time PQ-secure keys <math>^{post}\textrm{PQOPK}_{X}^i</math> including signatures and a last resort (semi-)static <math>^{post}\textrm{PQSPK}_{X}</math>. The server hands out one-time keys until they are exhausted. During the handshake, Alice encapsulates a secret using Bob's public key:		In May 2023 Signal published the first revision of the PQXDH protocol, intended to replace X3DH. Similar to Tutanota's proposal it's a hybrid protocol. Currently, it is only a slight modification of X3DH. As of September 2023, Signal added PQXDH to all Signal apps, enabling some quantum secure handshakes. As KEM Kyber-1024 is used. Each user generates a set of one-time PQ-secure keys <math>^{\mathrm{post}}\textrm{PQOPK}_{X}^i</math> including signatures and a last resort (semi-)static <math>^{\mathrm{post}}\textrm{PQSPK}_{X}</math>. The server hands out one-time keys until they are exhausted. During the handshake, Alice encapsulates a secret using Bob's public key:

	<math>(c_\textrm{pq}, ^{\mathrm{post}}k_\textrm{pq}) = \textrm{encaps}(^{post}\textrm{PQPK}_{B; pub})</math>		<math>(c_\textrm{pq}, ^{\mathrm{post}}k_\textrm{pq}) = \textrm{encaps}(^{\mathrm{post}}\textrm{PQPK}_{B; pub})</math>

	The additional key is added to the KDF. This construction enables protection against passive quantum adversaries and prevents "harvest-now-decrypt-later" approaches. However, the protocol adds no PQ-secure mutual authentication, and thus would be susceptible to an active quantum adversary. This decision is very deliberate since this simple construction keeps a high level of deniability.		The additional key is added to the KDF. This construction enables protection against passive quantum adversaries and prevents "harvest-now-decrypt-later" approaches. However, the protocol adds no PQ-secure mutual authentication, and thus would be susceptible to an active quantum adversary. This decision is very deliberate since this simple construction keeps a high level of deniability.

Wolfm: /* Tutanota's Proposal */

2023-10-24T13:51:11Z

Tutanota's Proposal

← Older revision		Revision as of 13:51, 24 October 2023
Line 85:		Line 85:
	<math>(c_\mathrm{3}, ^{\mathrm{post}}k_\mathrm{3}) = \mathrm{encaps}(^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B; pub}})</math>		<math>(c_\mathrm{3}, ^{\mathrm{post}}k_\mathrm{3}) = \mathrm{encaps}(^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B; pub}})</math>

	<math>((c_\mathrm{4}, ^{\mathrm{post}}k_\mathrm{4}) = \mathrm{encaps}(^{\mathrm{post}}\mathrm{OPK}^i_{\mathrm{B; pub}}))</math>		<math>\big[(c_\mathrm{4}, ^{\mathrm{post}}k_\mathrm{4}) = \mathrm{encaps}(^{\mathrm{post}}\mathrm{OPK}^i_{\mathrm{B; pub}})\big]</math>

	All resulting keys are then combined using the KDF. Since it is not possible to calculate a PQ-secure pendant to ^{\mathrm{pre}}k_\mathrm{1}, the authentication of Alice is missing. To overcome this the authors proposed for Alice to sign the handshake message to Bob. While this enables mutual authentication, the deniability is weakened. It can be cryptographically proven, that Alice sent the handshake message to Bob. To improve deniability, Hashimoto et al proposed ring signatures to be used, enabling anonymous signing of the data. However, a PQ-secure instantiation appears to be very complex and needs more research.		All resulting keys are then combined using the KDF. Since it is not possible to calculate a PQ-secure pendant to ^{\mathrm{pre}}k_\mathrm{1}, the authentication of Alice is missing. To overcome this the authors proposed for Alice to sign the handshake message to Bob. While this enables mutual authentication, the deniability is weakened. It can be cryptographically proven, that Alice sent the handshake message to Bob. To improve deniability, Hashimoto et al proposed ring signatures to be used, enabling anonymous signing of the data. However, a PQ-secure instantiation appears to be very complex and needs more research.

Wolfm: /* Intiate Handshake */

2023-10-24T13:50:24Z

Intiate Handshake

← Older revision		Revision as of 13:50, 24 October 2023
Line 45:		Line 45:

	<math>		<math>
	^{\mathrm{pre}}k_\mathrm{4} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{OPK}_{\mathrm{B; pub}})		\big[^{\mathrm{pre}}k_\mathrm{4} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{OPK}_{\mathrm{B; pub}})\big]
	</math>		</math>

Wolfm: /* SI-X3DH */

2023-10-24T13:49:01Z

SI-X3DH

← Older revision		Revision as of 13:49, 24 October 2023
Line 69:		Line 69:
	<math>^{\mathrm{post}}k_\mathrm{3} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B; pub}})</math>		<math>^{\mathrm{post}}k_\mathrm{3} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B; pub}})</math>

	<math>^{\mathrm{post}}k_\mathrm{4} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{OPK}_{\mathrm{B; pub}})</math>		<math>\big[^{\mathrm{post}}k_\mathrm{4} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{OPK}_{\mathrm{B; pub}})\big]</math>

	<math>\mathrm{SK = KDF(^{post}k_1 \|\|^{post}k_2 \|\| ^{post}k_3 ~~(\|\|~~ ^{post}k_4))} </math>		<math>\mathrm{SK} = \mathrm{KDF}\left(^{\mathrm{post}}k_1 \mathbin{\Vert} ^{\mathrm{post}}k_2 \mathbin{\Vert} ^{\mathrm{post}}k_3 \big[\mathbin{\Vert} ^{\mathrm{post}}k_4\big]\right) </math>

	<math>\pi = s \oplus H_2(^{\mathrm{post}}~~\mathrm{~~k_1}) \oplus H_2(^{\mathrm{post}}~~\mathrm{~~k_2}) \oplus H_2(^{\mathrm{post}}~~\mathrm{~~k_3}) (\oplus H_2(^{\mathrm{post}}~~\mathrm{~~k_4}))</math>		<math>\pi = s \oplus H_2(^{\mathrm{post}}k_1) \oplus H_2(^{\mathrm{post}}k_2) \oplus H_2(^{\mathrm{post}}k_3) \big[\oplus H_2(^{\mathrm{post}}k_4)\big]</math>

	==KEM-based approaches==		==KEM-based approaches==

Wolfm: /* SI-X3DH */

2023-10-24T13:09:28Z

SI-X3DH

← Older revision		Revision as of 13:09, 24 October 2023
Line 69:		Line 69:
	<math>^{\mathrm{post}}k_\mathrm{3} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B; pub}})</math>		<math>^{\mathrm{post}}k_\mathrm{3} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B; pub}})</math>

	<math>(^{\mathrm{post}}k_\mathrm{4} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{OPK}_{\mathrm{B; pub}}))</math>		<math>^{\mathrm{post}}k_\mathrm{4} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{OPK}_{\mathrm{B; pub}})</math>

	<math>\mathrm{SK = KDF(^{post}k_1 \|\|^{post}k_2 \|\| ^{post}k_3 (\|\| ^{post}k_4))} </math>		<math>\mathrm{SK = KDF(^{post}k_1 \|\|^{post}k_2 \|\| ^{post}k_3 (\|\| ^{post}k_4))} </math>

Wolfm: /* Intiate Handshake */

2023-10-24T13:08:53Z

Intiate Handshake

← Older revision		Revision as of 13:08, 24 October 2023
Line 45:		Line 45:

	<math>		<math>
	(^{\mathrm{pre}}k_\mathrm{4} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{OPK}_{\mathrm{B; pub}}))		^{\mathrm{pre}}k_\mathrm{4} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{OPK}_{\mathrm{B; pub}})
	</math>		</math>

Ehlertto at 10:01, 21 October 2023

2023-10-21T10:01:41Z

← Older revision		Revision as of 10:01, 21 October 2023
Line 76:		Line 76:

	==KEM-based approaches==		==KEM-based approaches==
	KEMs seem to be the most promising path for creating a PQ-secure Signal protocol. NIST already announced a winning KEM from their competition: CRYSTALS-Kyber. The algorithm uses lattices as its security anchor. For a great explanation of Kyber see the following video: https://~~www~~.~~youtube~~.~~com~~/~~watch?~~v~~=FUb75AUXMvw~~		KEMs seem to be the most promising path for creating a PQ-secure Signal protocol. NIST already announced a winning KEM from their competition: CRYSTALS-Kyber. The algorithm uses lattices as its security anchor. For a great explanation of Kyber see the following video: https://media.ccc.de/v/rc3-2021-cwtv-230-kyber-and-post-quantum

	===Tutanota's Proposal===		===Tutanota's Proposal===