Debian Codegraph @

x3dh/base_state.py

raw
1 from __future__ import annotations
2
3 from abc import ABC, abstractmethod
4 import json
5 import time
6 import secrets
7 from typing import FrozenSet, Optional, Set, Tuple, Type, TypeVar, cast
8
9 import xeddsa
10
11 from .crypto_provider import HashFunction
12 from .crypto_provider_cryptography import CryptoProviderImpl
13 from .identity_key_pair import IdentityKeyPair, IdentityKeyPairSeed
14 from .migrations import parse_base_state_model
15 from .models import BaseStateModel
16 from .pre_key_pair import PreKeyPair
17 from .signed_pre_key_pair import SignedPreKeyPair
18 from .types import Bundle, IdentityKeyFormat, Header, JSONObject
19
20
21 __all__ = [
22 "KeyAgreementException",
23 "BaseState"
24 ]
25
26
27 class KeyAgreementException(Exception):
28 """
29 Exception raised by :meth:`BaseState.get_shared_secret_active` and
30 :meth:`BaseState.get_shared_secret_passive` in case of an error related to the key agreement operation.
31 """
32
33
34 BaseStateTypeT = TypeVar("BaseStateTypeT", bound="BaseState")
35
36
37 class BaseState(ABC):
38 """
39 This class is the core of this X3DH implementation. It offers methods to manually manage the X3DH state
40 and perform key agreements with other parties.
41
42 Warning:
43 This class requires manual state management, including e.g. signed pre key rotation, pre key
44 hiding/deletion and refills. The subclass :class:`~x3dh.state.State` automates those
45 management/maintenance tasks and should be preferred if external/manual management is not explicitly
46 wanted.
47 """
48
49 def __init__(self) -> None:
50 # Just the type definitions here
51 self.__identity_key_format: IdentityKeyFormat
52 self.__hash_function: HashFunction
53 self.__info: bytes
54 self.__identity_key: IdentityKeyPair
55 self.__signed_pre_key: SignedPreKeyPair
56 self.__old_signed_pre_key: Optional[SignedPreKeyPair]
57 self.__pre_keys: Set[PreKeyPair]
58 self.__hidden_pre_keys: Set[PreKeyPair]
59
60 @classmethod
61 def create(
62 cls: Type[BaseStateTypeT],
63 identity_key_format: IdentityKeyFormat,
64 hash_function: HashFunction,
65 info: bytes,
66 identity_key_pair: Optional[IdentityKeyPair] = None
67 ) -> BaseStateTypeT:
68 """
69 Args:
70 identity_key_format: The format in which the identity public key is included in bundles/headers.
71 hash_function: A 256 or 512-bit hash function.
72 info: A (byte) string identifying the application.
73 identity_key_pair: If set, use the given identity key pair instead of generating a new one.
74
75 Returns:
76 A configured instance of :class:`~x3dh.base_state.BaseState`. Note that an identity key pair and a
77 signed pre key are generated, but no pre keys. Use :meth:`generate_pre_keys` to generate some.
78 """
79
80 self = cls()
81 self.__identity_key_format = identity_key_format
82 self.__hash_function = hash_function
83 self.__info = info
84 self.__identity_key = identity_key_pair or IdentityKeyPairSeed(secrets.token_bytes(32))
85 self.__signed_pre_key = self.__generate_spk()
86 self.__old_signed_pre_key = None
87 self.__pre_keys = set()
88 self.__hidden_pre_keys = set()
89
90 return self
91
92 ####################
93 # abstract methods #
94 ####################
95
96 @staticmethod
97 @abstractmethod
98 def _encode_public_key(key_format: IdentityKeyFormat, pub: bytes) -> bytes:
99 """
100 Args:
101 key_format: The format in which this public key is serialized.
102 pub: The public key.
103
104 Returns:
105 An encoding of the public key, possibly including information about the curve and type of key,
106 though this is application defined. Note that two different public keys must never result in the
107 same byte sequence, uniqueness of the public keys must be preserved.
108 """
109
110 raise NotImplementedError("Create a subclass of BaseState and implement `_encode_public_key`.")
111
112 #################
113 # serialization #
114 #################
115
116 @property
117 def model(self) -> BaseStateModel:
118 """
119 Returns:
120 The internal state of this :class:`BaseState` as a pydantic model. Note that pre keys hidden using
121 :meth:`hide_pre_key` are not considered part of the state.
122 """
123
124 return BaseStateModel(
125 identity_key=self.__identity_key.model,
126 signed_pre_key=self.__signed_pre_key.model,
127 old_signed_pre_key=None if self.__old_signed_pre_key is None else self.__old_signed_pre_key.model,
128 pre_keys=frozenset(pre_key.priv for pre_key in self.__pre_keys)
129 )
130
131 @property
132 def json(self) -> JSONObject:
133 """
134 Returns:
135 The internal state of this :class:`BaseState` as a JSON-serializable Python object. Note that pre
136 keys hidden using :meth:`hide_pre_key` are not considered part of the state.
137 """
138
139 return cast(JSONObject, json.loads(self.model.model_dump_json()))
140
141 @classmethod
142 def from_model(
143 cls: Type[BaseStateTypeT],
144 model: BaseStateModel,
145 identity_key_format: IdentityKeyFormat,
146 hash_function: HashFunction,
147 info: bytes
148 ) -> BaseStateTypeT:
149 """
150 Args:
151 model: The pydantic model holding the internal state of a :class:`BaseState`, as produced by
152 :attr:`model`.
153 identity_key_format: The format in which the identity public key is included in bundles/headers.
154 hash_function: A 256 or 512-bit hash function.
155 info: A (byte) string identifying the application.
156
157 Returns:
158 A configured instance of :class:`BaseState`, with internal state restored from the model.
159
160 Warning:
161 Migrations are not provided via the :attr:`model`/:meth:`from_model` API. Use
162 :attr:`json`/:meth:`from_json` instead. Refer to :ref:`serialization_and_migration` in the
163 documentation for details.
164 """
165
166 self = cls()
167 self.__identity_key_format = identity_key_format
168 self.__hash_function = hash_function
169 self.__info = info
170 self.__identity_key = IdentityKeyPair.from_model(model.identity_key)
171 self.__signed_pre_key = SignedPreKeyPair.from_model(model.signed_pre_key)
172 self.__old_signed_pre_key = (
173 None
174 if model.old_signed_pre_key is None
175 else SignedPreKeyPair.from_model(model.old_signed_pre_key)
176 )
177 self.__pre_keys = { PreKeyPair(pre_key) for pre_key in model.pre_keys }
178 self.__hidden_pre_keys = set()
179
180 return self
181
182 @classmethod
183 def from_json(
184 cls: Type[BaseStateTypeT],
185 serialized: JSONObject,
186 identity_key_format: IdentityKeyFormat,
187 hash_function: HashFunction,
188 info: bytes
189 ) -> Tuple[BaseStateTypeT, bool]:
190 """
191 Args:
192 serialized: A JSON-serializable Python object holding the internal state of a :class:`BaseState`,
193 as produced by :attr:`json`.
194 identity_key_format: The format in which the identity public key is included in bundles/headers.
195 hash_function: A 256 or 512-bit hash function.
196 info: A (byte) string identifying the application.
197
198 Returns:
199 A configured instance of :class:`BaseState`, with internal state restored from the serialized
200 data, and a flag that indicates whether the bundle needs to be published. The latter was part of
201 the pre-stable serialization format.
202 """
203
204 model, bundle_needs_publish = parse_base_state_model(serialized)
205
206 self = cls.from_model(
207 model,
208 identity_key_format,
209 hash_function,
210 info
211 )
212
213 return self, bundle_needs_publish
214
215 #################################
216 # key generation and management #
217 #################################
218
219 def __generate_spk(self) -> SignedPreKeyPair:
220 """
221 Returns:
222 A newly generated signed pre key.
223 """
224
225 # Get the own identity key in the format required for signing, forcing the sign bit if necessary to
226 # comply with XEdDSA
227 identity_key = self.__identity_key.as_priv().priv
228 if self.__identity_key_format is IdentityKeyFormat.CURVE_25519:
229 identity_key = xeddsa.priv_force_sign(identity_key, False)
230
231 # Generate the private key of the new signed pre key
232 priv = secrets.token_bytes(32)
233
234 # Sign the encoded public key of the new signed pre key
235 sig = xeddsa.ed25519_priv_sign(
236 identity_key,
237 self._encode_public_key(IdentityKeyFormat.CURVE_25519, xeddsa.priv_to_curve25519_pub(priv))
238 )
239
240 # Add the current timestamp
241 return SignedPreKeyPair(priv=priv, sig=sig, timestamp=int(time.time()))
242
243 @property
244 def old_signed_pre_key(self) -> Optional[bytes]:
245 """
246 Returns:
247 The old signed pre key, if there is one.
248 """
249
250 return None if self.__old_signed_pre_key is None else self.__old_signed_pre_key.pub
251
252 def signed_pre_key_age(self) -> int:
253 """
254 Returns:
255 The age of the signed pre key, i.e. the time elapsed since it was last rotated, in seconds.
256 """
257
258 return int(time.time()) - self.__signed_pre_key.timestamp
259
260 def rotate_signed_pre_key(self) -> None:
261 """
262 Rotate the signed pre key. Keep the old signed pre key around for one additional rotation period, i.e.
263 until this method is called again.
264 """
265
266 self.__old_signed_pre_key = self.__signed_pre_key
267 self.__signed_pre_key = self.__generate_spk()
268
269 @property
270 def hidden_pre_keys(self) -> FrozenSet[bytes]:
271 """
272 Returns:
273 The currently hidden pre keys.
274 """
275
276 return frozenset(pre_key.pub for pre_key in self.__hidden_pre_keys)
277
278 def hide_pre_key(self, pre_key_pub: bytes) -> bool:
279 """
280 Hide a pre key from the bundle returned by :attr:`bundle` and pre key count returned by
281 :meth:`get_num_visible_pre_keys`, but keep the pre key for cryptographic operations. Hidden pre keys
282 are not included in the serialized state as returned by :attr:`model` and :attr:`json`.
283
284 Args:
285 pre_key_pub: The pre key to hide.
286
287 Returns:
288 Whether the pre key was visible before and is hidden now.
289 """
290
291 hidden_pre_keys = frozenset(filter(lambda pre_key: pre_key.pub == pre_key_pub, self.__pre_keys))
292
293 self.__pre_keys -= hidden_pre_keys
294 self.__hidden_pre_keys |= hidden_pre_keys
295
296 return len(hidden_pre_keys) > 0
297
298 def delete_pre_key(self, pre_key_pub: bytes) -> bool:
299 """
300 Delete a pre key.
301
302 Args:
303 pre_key_pub: The pre key to delete. Can be visible or hidden.
304
305 Returns:
306 Whether the pre key existed before and is deleted now.
307 """
308
309 deleted_pre_keys = frozenset(filter(
310 lambda pre_key: pre_key.pub == pre_key_pub,
311 self.__pre_keys | self.__hidden_pre_keys
312 ))
313
314 self.__pre_keys -= deleted_pre_keys
315 self.__hidden_pre_keys -= deleted_pre_keys
316
317 return len(deleted_pre_keys) > 0
318
319 def delete_hidden_pre_keys(self) -> None:
320 """
321 Delete all pre keys that were previously hidden using :meth:`hide_pre_key`.
322 """
323
324 self.__hidden_pre_keys = set()
325
326 def get_num_visible_pre_keys(self) -> int:
327 """
328 Returns:
329 The number of visible pre keys available. The number returned here matches the number of pre keys
330 included in the bundle returned by :attr:`bundle`.
331 """
332
333 return len(self.__pre_keys)
334
335 def generate_pre_keys(self, num_pre_keys: int) -> None:
336 """
337 Generate and store pre keys.
338
339 Args:
340 num_pre_keys: The number of pre keys to generate.
341 """
342
343 for _ in range(num_pre_keys):
344 self.__pre_keys.add(PreKeyPair(priv=secrets.token_bytes(32)))
345
346 @property
347 def bundle(self) -> Bundle:
348 """
349 Returns:
350 The bundle, i.e. the public information of this state.
351 """
352
353 identity_key = self.__identity_key.as_priv().priv
354
355 return Bundle(
356 identity_key=(
357 xeddsa.priv_to_curve25519_pub(identity_key)
358 if self.__identity_key_format is IdentityKeyFormat.CURVE_25519
359 else xeddsa.priv_to_ed25519_pub(identity_key)
360 ),
361 signed_pre_key=self.__signed_pre_key.pub,
362 signed_pre_key_sig=self.__signed_pre_key.sig,
363 pre_keys=frozenset(pre_key.pub for pre_key in self.__pre_keys)
364 )
365
366 #################
367 # key agreement #
368 #################
369
370 async def get_shared_secret_active(
371 self,
372 bundle: Bundle,
373 associated_data_appendix: bytes = b"",
374 require_pre_key: bool = True
375 ) -> Tuple[bytes, bytes, Header]:
376 """
377 Perform an X3DH key agreement, actively.
378
379 Args:
380 bundle: The bundle of the passive party.
381 associated_data_appendix: Additional information to append to the associated data, like usernames,
382 certificates or other identifying information.
383 require_pre_key: Use this flag to abort the key agreement if the bundle does not contain a pre
384 key.
385
386 Returns:
387 The shared secret and associated data shared between both parties, and the header required by the
388 other party to complete the passive part of the key agreement.
389
390 Raises:
391 KeyAgreementException: If an error occurs during the key agreement. The exception message will
392 contain (human-readable) details.
393 """
394
395 # Check whether a pre key is required but not included
396 if len(bundle.pre_keys) == 0 and require_pre_key:
397 raise KeyAgreementException("This bundle does not contain a pre key.")
398
399 # Get the identity key of the other party in the format required for signature verification
400 other_identity_key = bundle.identity_key
401 if self.__identity_key_format is IdentityKeyFormat.CURVE_25519:
402 other_identity_key = xeddsa.curve25519_pub_to_ed25519_pub(other_identity_key, False)
403
404 # Verify the signature on the signed pre key of the other party
405 if not xeddsa.ed25519_verify(
406 bundle.signed_pre_key_sig,
407 other_identity_key,
408 self._encode_public_key(IdentityKeyFormat.CURVE_25519, bundle.signed_pre_key)
409 ):
410 raise KeyAgreementException("The signature of the signed pre key could not be verified.")
411
412 # All pre-checks successful.
413
414 # Choose a pre key if available
415 pre_key = None if len(bundle.pre_keys) == 0 else secrets.choice(list(bundle.pre_keys))
416
417 # Generate the ephemeral key required for the key agreement
418 ephemeral_key = secrets.token_bytes(32)
419
420 # Get the own identity key in the format required for X25519
421 own_identity_key = self.__identity_key.as_priv().priv
422
423 # Get the identity key of the other party in the format required for X25519
424 other_identity_key = bundle.identity_key
425 if self.__identity_key_format is IdentityKeyFormat.ED_25519:
426 other_identity_key = xeddsa.ed25519_pub_to_curve25519_pub(other_identity_key)
427
428 # Calculate the three to four Diffie-Hellman shared secrets that become the input of HKDF in the next
429 # step
430 dh1 = xeddsa.x25519(own_identity_key, bundle.signed_pre_key)
431 dh2 = xeddsa.x25519(ephemeral_key, other_identity_key)
432 dh3 = xeddsa.x25519(ephemeral_key, bundle.signed_pre_key)
433 dh4 = b"" if pre_key is None else xeddsa.x25519(ephemeral_key, pre_key)
434
435 # Prepare salt and padding
436 salt = b"\x00" * self.__hash_function.hash_size
437 padding = b"\xFF" * 32
438
439 # Use HKDF to derive the final shared secret
440 shared_secret = await CryptoProviderImpl.hkdf_derive(
441 self.__hash_function,
442 32,
443 salt,
444 self.__info,
445 padding + dh1 + dh2 + dh3 + dh4
446 )
447
448 # Build the associated data for further use by other protocols
449 associated_data = (
450 self._encode_public_key(self.__identity_key_format, self.bundle.identity_key)
451 + self._encode_public_key(self.__identity_key_format, bundle.identity_key)
452 + associated_data_appendix
453 )
454
455 # Build the header required by the other party to complete the passive part of the key agreement
456 header = Header(
457 identity_key=self.bundle.identity_key,
458 ephemeral_key=xeddsa.priv_to_curve25519_pub(ephemeral_key),
459 pre_key=pre_key,
460 signed_pre_key=bundle.signed_pre_key
461 )
462
463 return shared_secret, associated_data, header
464
465 async def get_shared_secret_passive(
466 self,
467 header: Header,
468 associated_data_appendix: bytes = b"",
469 require_pre_key: bool = True
470 ) -> Tuple[bytes, bytes, SignedPreKeyPair]:
471 """
472 Perform an X3DH key agreement, passively.
473
474 Args:
475 header: The header received from the active party.
476 associated_data_appendix: Additional information to append to the associated data, like usernames,
477 certificates or other identifying information.
478 require_pre_key: Use this flag to abort the key agreement if the active party did not use a pre
479 key.
480
481 Returns:
482 The shared secret and the associated data shared between both parties, and the signed pre key pair
483 that was used during the key exchange, for use by follow-up protocols.
484
485 Raises:
486 KeyAgreementException: If an error occurs during the key agreement. The exception message will
487 contain (human-readable) details.
488 """
489
490 # Check whether the signed pre key used by this initiation is still available
491 signed_pre_key: Optional[SignedPreKeyPair] = None
492
493 if header.signed_pre_key == self.__signed_pre_key.pub:
494 # The current signed pre key was used
495 signed_pre_key = self.__signed_pre_key
496
497 if self.__old_signed_pre_key is not None and header.signed_pre_key == self.__old_signed_pre_key.pub:
498 # The old signed pre key was used
499 signed_pre_key = self.__old_signed_pre_key
500
501 if signed_pre_key is None:
502 raise KeyAgreementException(
503 "This key agreement attempt uses a signed pre key that is not available any more."
504 )
505
506 # Check whether a pre key is required but not used
507 if header.pre_key is None and require_pre_key:
508 raise KeyAgreementException("This key agreement attempt does not use a pre key.")
509
510 # If a pre key was used, check whether it is still available
511 pre_key: Optional[bytes] = None
512 if header.pre_key is not None:
513 pre_key = next((
514 pre_key.priv
515 for pre_key
516 in self.__pre_keys | self.__hidden_pre_keys
517 if pre_key.pub == header.pre_key
518 ), None)
519
520 if pre_key is None:
521 raise KeyAgreementException(
522 "This key agreement attempt uses a pre key that is not available any more."
523 )
524
525 # Get the own identity key in the format required for X25519
526 own_identity_key = self.__identity_key.as_priv().priv
527
528 # Get the identity key of the other party in the format required for X25519
529 other_identity_key = header.identity_key
530 if self.__identity_key_format is IdentityKeyFormat.ED_25519:
531 other_identity_key = xeddsa.ed25519_pub_to_curve25519_pub(other_identity_key)
532
533 # Calculate the three to four Diffie-Hellman shared secrets that become the input of HKDF in the next
534 # step
535 dh1 = xeddsa.x25519(signed_pre_key.priv, other_identity_key)
536 dh2 = xeddsa.x25519(own_identity_key, header.ephemeral_key)
537 dh3 = xeddsa.x25519(signed_pre_key.priv, header.ephemeral_key)
538 dh4 = b"" if pre_key is None else xeddsa.x25519(pre_key, header.ephemeral_key)
539
540 # Prepare salt and padding
541 salt = b"\x00" * self.__hash_function.hash_size
542 padding = b"\xFF" * 32
543
544 # Use HKDF to derive the final shared secret
545 shared_secret = await CryptoProviderImpl.hkdf_derive(
546 self.__hash_function,
547 32,
548 salt,
549 self.__info,
550 padding + dh1 + dh2 + dh3 + dh4
551 )
552
553 # Build the associated data for further use by other protocols
554 associated_data = (
555 self._encode_public_key(self.__identity_key_format, header.identity_key)
556 + self._encode_public_key(self.__identity_key_format, self.bundle.identity_key)
557 + associated_data_appendix
558 )
559
560 return shared_secret, associated_data, signed_pre_key