derivepassphrase.git

1) # SPDX-FileCopyrightText: 2024 Marco Ricci <m@the13thletter.info>
2) #
3) # SPDX-License-Identifier: MIT

4) 

5) """Work-alike of vault(1) – a deterministic, stateless password manager"""  # noqa: RUF002

6) 
7) from __future__ import annotations
8) 

9) import base64

10) import collections
11) import hashlib
12) import math

13) import unicodedata

14) from collections.abc import Callable
15) from typing import TypeAlias

16) 

17) from typing_extensions import assert_type

18) 
19) import sequin
20) import ssh_agent_client
21) 

22) __author__ = 'Marco Ricci <m@the13thletter.info>'

23) __version__ = '0.1.2'

24) 

25) 

26) class AmbiguousByteRepresentationError(ValueError):
27)     """The object has an ambiguous byte representation."""

28) 
29)     def __init__(self) -> None:

30)         super().__init__('text string has ambiguous byte representation')
31) 

32) 

33) _CHARSETS = collections.OrderedDict([
34)     ('lower', b'abcdefghijklmnopqrstuvwxyz'),
35)     ('upper', b'ABCDEFGHIJKLMNOPQRSTUVWXYZ'),
36)     ('alpha', b''),  # Placeholder.
37)     ('number', b'0123456789'),
38)     ('alphanum', b''),  # Placeholder.
39)     ('space', b' '),
40)     ('dash', b'-_'),
41)     ('symbol', b'!"#$%&\'()*+,./:;<=>?@[\\]^{|}~-_'),
42)     ('all', b''),  # Placeholder.
43) ])
44) _CHARSETS['alpha'] = _CHARSETS['lower'] + _CHARSETS['upper']
45) _CHARSETS['alphanum'] = _CHARSETS['alpha'] + _CHARSETS['number']

46) _CHARSETS['all'] = (
47)     _CHARSETS['alphanum'] + _CHARSETS['space'] + _CHARSETS['symbol']
48) )
49) 

50) 

51) class Vault:
52)     """A work-alike of James Coglan's vault.
53) 
54)     Store settings for generating (actually: deriving) passphrases for
55)     named services, with various constraints, given only a master
56)     passphrase.  Also, actually generate the passphrase.  The derivation
57)     is deterministic and non-secret; only the master passphrase need be
58)     kept secret.  The implementation is compatible with [vault][].
59) 
60)     [James Coglan explains the passphrase derivation algorithm in great
61)     detail][ALGORITHM] in his blog post on said topic: A principally
62)     infinite bit stream is obtained by running a key-derivation function
63)     on the master passphrase and the service name, then this bit stream

64)     is fed into a [Sequin][sequin.Sequin] to generate random numbers in
65)     the correct range, and finally these random numbers select
66)     passphrase characters until the desired length is reached.

67) 
68)     [vault]: https://getvau.lt
69)     [ALGORITHM]: https://blog.jcoglan.com/2012/07/16/designing-vaults-generator-algorithm/
70) 
71)     """

72) 

73)     _UUID = b'e87eb0f4-34cb-46b9-93ad-766c5ab063e7'
74)     """A tag used by vault in the bit stream generation."""

75)     _CHARSETS = _CHARSETS

76)     """
77)         Known character sets from which to draw passphrase characters.
78)         Relies on a certain, fixed order for their definition and their
79)         contents.
80) 
81)     """
82) 
83)     def __init__(

84)         self,
85)         *,
86)         phrase: bytes | bytearray | str = b'',
87)         length: int = 20,
88)         repeat: int = 0,
89)         lower: int | None = None,
90)         upper: int | None = None,
91)         number: int | None = None,
92)         space: int | None = None,
93)         dash: int | None = None,

94)         symbol: int | None = None,
95)     ) -> None:
96)         """Initialize the Vault object.
97) 
98)         Args:
99)             phrase:
100)                 The master passphrase from which to derive the service

101)                 passphrases.  If a text string, then the byte
102)                 representation must be unique.

103)             length:
104)                 Desired passphrase length.
105)             repeat:
106)                 The maximum number of immediate character repetitions
107)                 allowed in the passphrase.  Disabled if set to 0.
108)             lower:

109)                 Optional constraint on ASCII lowercase characters.  If

110)                 positive, include this many lowercase characters
111)                 somewhere in the passphrase.  If 0, avoid lowercase
112)                 characters altogether.
113)             upper:

114)                 Same as `lower`, but for ASCII uppercase characters.

115)             number:
116)                 Same as `lower`, but for ASCII digits.
117)             space:
118)                 Same as `lower`, but for the space character.
119)             dash:
120)                 Same as `lower`, but for the hyphen-minus and underscore
121)                 characters.
122)             symbol:
123)                 Same as `lower`, but for all other hitherto unlisted
124)                 ASCII printable characters (except backquote).
125) 

126)         Raises:
127)             AmbiguousByteRepresentationError:
128)                 The phrase is a text string with differing NFC- and
129)                 NFD-normalized UTF-8 byte representations.
130) 

131)         """

132)         self._phrase = self._get_binary_string(phrase)

133)         self._length = length
134)         self._repeat = repeat
135)         self._allowed = bytearray(self._CHARSETS['all'])
136)         self._required: list[bytes] = []

137) 

138)         def subtract_or_require(
139)             count: int | None, characters: bytes | bytearray
140)         ) -> None:
141)             if not isinstance(count, int):
142)                 return

143)             if count <= 0:

144)                 self._allowed = self._subtract(characters, self._allowed)
145)             else:
146)                 for _ in range(count):
147)                     self._required.append(characters)

148) 

149)         subtract_or_require(lower, self._CHARSETS['lower'])
150)         subtract_or_require(upper, self._CHARSETS['upper'])
151)         subtract_or_require(number, self._CHARSETS['number'])
152)         subtract_or_require(space, self._CHARSETS['space'])
153)         subtract_or_require(dash, self._CHARSETS['dash'])
154)         subtract_or_require(symbol, self._CHARSETS['symbol'])

155)         if len(self._required) > self._length:

156)             msg = 'requested passphrase length too short'
157)             raise ValueError(msg)

158)         if not self._allowed:

159)             msg = 'no allowed characters left'
160)             raise ValueError(msg)

161)         for _ in range(len(self._required), self._length):
162)             self._required.append(bytes(self._allowed))
163) 

164)     def _entropy(self) -> float:

165)         """Estimate the passphrase entropy, given the current settings.
166) 
167)         The entropy is the base 2 logarithm of the amount of

168)         possibilities.  We operate directly on the logarithms, and use
169)         sorting and [`math.fsum`][] to keep high accuracy.
170) 
171)         Note:
172)             We actually overestimate the entropy here because of poor
173)             handling of character repetitions.  In the extreme, assuming
174)             that only one character were allowed, then because there is
175)             only one possible string of each given length, the entropy
176)             of that string `s` is always be zero.  However, we calculate
177)             the entropy as `math.log2(math.factorial(len(s)))`, i.e. we
178)             assume the characters at the respective string position are
179)             distinguishable from each other.
180) 
181)         Returns:
182)             A valid (and somewhat close) upper bound to the entropy.

183) 
184)         """
185)         factors: list[int] = []

186)         if not self._required or any(not x for x in self._required):
187)             return float('-inf')

188)         for i, charset in enumerate(self._required):

189)             factors.extend([i + 1, len(charset)])

190)         factors.sort()
191)         return math.fsum(math.log2(f) for f in factors)
192) 
193)     def _estimate_sufficient_hash_length(

194)         self,
195)         safety_factor: float = 2.0,

196)     ) -> int:
197)         """Estimate the sufficient hash length, given the current settings.
198) 
199)         Using the entropy (via `_entropy`) and a safety factor, give an
200)         initial estimate of the length to use for `create_hash` such
201)         that using a `Sequin` with this hash will not exhaust it during
202)         passphrase generation.
203) 
204)         Args:
205)             safety_factor: The safety factor.  Must be at least 1.
206) 
207)         Returns:
208)             The estimated sufficient hash length.
209) 
210)         Warning:
211)             This is a heuristic, not an exact computation; it may
212)             underestimate the true necessary hash length.  It is
213)             intended as a starting point for searching for a sufficient
214)             hash length, usually by doubling the hash length each time
215)             it does not yet prove so.
216) 
217)         """
218)         try:
219)             safety_factor = float(safety_factor)
220)         except TypeError as e:

221)             msg = f'invalid safety factor: not a float: {safety_factor!r}'
222)             raise TypeError(msg) from e

223)         if not math.isfinite(safety_factor) or safety_factor < 1.0:

224)             msg = f'invalid safety factor {safety_factor!r}'
225)             raise ValueError(msg)

226)         # Ensure the bound is strictly positive.
227)         entropy_bound = max(1, self._entropy())
228)         return int(math.ceil(safety_factor * entropy_bound / 8))

229) 

230)     @staticmethod
231)     def _get_binary_string(s: bytes | bytearray | str, /) -> bytes:
232)         """Convert the input string to a read-only, binary string.
233) 
234)         If it is a text string, then test for an unambiguous UTF-8
235)         representation, otherwise abort.  (That is, check whether the
236)         NFC and NFD forms of the string coincide.)
237) 
238)         Args:
239)             s: The string to (check and) convert.
240) 
241)         Returns:
242)             A read-only, binary copy of the string.
243) 
244)         Raises:
245)             AmbiguousByteRepresentationError:
246)                 The text string has differing NFC- and NFD-normalized
247)                 UTF-8 byte representations.
248) 
249)         """
250)         if isinstance(s, str):
251)             norm = unicodedata.normalize
252)             if norm('NFC', s) != norm('NFD', s):

253)                 raise AmbiguousByteRepresentationError

254)             return s.encode('UTF-8')
255)         return bytes(s)
256) 

257)     @classmethod
258)     def create_hash(

259)         cls,
260)         phrase: bytes | bytearray | str,
261)         service: bytes | bytearray,
262)         *,
263)         length: int = 32,

264)     ) -> bytes:

265)         r"""Create a pseudorandom byte stream from phrase and service.
266) 
267)         Create a pseudorandom byte stream from `phrase` and `service` by
268)         feeding them into the key-derivation function PBKDF2
269)         (8 iterations, using SHA-1).

270) 
271)         Args:

272)             phrase:
273)                 A master passphrase, or sometimes an SSH signature.
274)                 Used as the key for PBKDF2, the underlying cryptographic
275)                 primitive.

276) 
277)                 If a text string, then the byte representation must be
278)                 unique.

279)             service:
280)                 A vault service name.  Will be suffixed with
281)                 `Vault._UUID`, and then used as the salt value for
282)                 PBKDF2.

283)             length:
284)                 The length of the byte stream to generate.
285) 
286)         Returns:
287)             A pseudorandom byte string of length `length`.
288) 

289)         Raises:
290)             AmbiguousByteRepresentationError:
291)                 The phrase is a text string with differing NFC- and
292)                 NFD-normalized UTF-8 byte representations.
293) 

294)         Note:
295)             Shorter values returned from this method (with the same key
296)             and message) are prefixes of longer values returned from
297)             this method.  (This property is inherited from the
298)             underlying PBKDF2 function.)  It is thus safe (if slow) to
299)             call this method with the same input with ever-increasing
300)             target lengths.
301) 

302)         Examples:

303)             >>> # See also Vault.phrase_from_key examples.

304)             >>> phrase = bytes.fromhex('''
305)             ... 00 00 00 0b 73 73 68 2d 65 64 32 35 35 31 39
306)             ... 00 00 00 40
307)             ... f0 98 19 80 6c 1a 97 d5 26 03 6e cc e3 65 8f 86
308)             ... 66 07 13 19 13 09 21 33 33 f9 e4 36 53 1d af fd
309)             ... 0d 08 1f ec f8 73 9b 8c 5f 55 39 16 7c 53 54 2c
310)             ... 1e 52 bb 30 ed 7f 89 e2 2f 69 51 55 d8 9e a6 02
311)             ... ''')
312)             >>> Vault.create_hash(phrase, b'some_service', length=4)
313)             b'M\xb1<S'
314)             >>> Vault.create_hash(phrase, b'some_service', length=16)
315)             b'M\xb1<S\x827E\xd1M\xaf\xf8~\xc8n\x10\xcc'
316)             >>> Vault.create_hash(phrase, b'NOSUCHSERVICE', length=16)
317)             b'\x1c\xc3\x9c\xd9\xb6\x1a\x99CS\x07\xc41\xf4\x85#s'
318) 

319)         """

320)         phrase = cls._get_binary_string(phrase)
321)         assert not isinstance(phrase, str)

322)         salt = bytes(service) + cls._UUID

323)         return hashlib.pbkdf2_hmac(
324)             hash_name='sha1',
325)             password=phrase,
326)             salt=salt,
327)             iterations=8,
328)             dklen=length,
329)         )

330) 
331)     def generate(

332)         self,
333)         service_name: str | bytes | bytearray,
334)         /,
335)         *,

336)         phrase: bytes | bytearray | str = b'',

337)     ) -> bytes:
338)         r"""Generate a service passphrase.

339) 
340)         Args:
341)             service_name:
342)                 The service name.
343)             phrase:
344)                 If given, override the passphrase given during
345)                 construction.
346) 

347)                 If a text string, then the byte representation must be
348)                 unique.
349) 
350)         Returns:
351)             The service passphrase.
352) 
353)         Raises:
354)             AmbiguousByteRepresentationError:
355)                 The phrase is a text string with differing NFC- and
356)                 NFD-normalized UTF-8 byte representations.
357) 

358)         Examples:
359)             >>> phrase = b'She cells C shells bye the sea shoars'
360)             >>> # Using default options in constructor.
361)             >>> Vault(phrase=phrase).generate(b'google')
362)             b': 4TVH#5:aZl8LueOT\\{'
363)             >>> # Also possible:
364)             >>> Vault().generate(b'google', phrase=phrase)
365)             b': 4TVH#5:aZl8LueOT\\{'
366) 

367)         """

368)         hash_length = self._estimate_sufficient_hash_length()
369)         assert hash_length >= 1

370)         # Ensure the phrase is a bytes object.  Needed later for safe
371)         # concatenation.
372)         if isinstance(service_name, str):
373)             service_name = service_name.encode('utf-8')
374)         elif not isinstance(service_name, bytes):
375)             service_name = bytes(service_name)
376)         assert_type(service_name, bytes)

377)         if not phrase:
378)             phrase = self._phrase

379)         phrase = self._get_binary_string(phrase)

380)         # Repeat the passphrase generation with ever-increasing hash
381)         # lengths, until the passphrase can be formed without exhausting
382)         # the sequin.  See the guarantee in the create_hash method for
383)         # why this works.
384)         while True:
385)             try:
386)                 required = self._required[:]

387)                 seq = sequin.Sequin(
388)                     self.create_hash(
389)                         phrase=phrase, service=service_name, length=hash_length
390)                     )
391)                 )

392)                 result = bytearray()
393)                 while len(result) < self._length:
394)                     pos = seq.generate(len(required))
395)                     charset = required.pop(pos)
396)                     # Determine if an unlucky choice right now might
397)                     # violate the restriction on repeated characters.
398)                     # That is, check if the current partial passphrase
399)                     # ends with r - 1 copies of the same character
400)                     # (where r is the repeat limit that must not be
401)                     # reached), and if so, remove this same character
402)                     # from the current character's allowed set.

403)                     if self._repeat and result:
404)                         bad_suffix = bytes(result[-1:]) * (self._repeat - 1)
405)                         if result.endswith(bad_suffix):

406)                             charset = self._subtract(
407)                                 bytes(result[-1:]), charset
408)                             )

409)                     pos = seq.generate(len(charset))

410)                     result.extend(charset[pos : pos + 1])

411)             except sequin.SequinExhaustedError:

412)                 hash_length *= 2
413)             else:

414)                 return bytes(result)

415) 

416)     @staticmethod
417)     def _is_suitable_ssh_key(key: bytes | bytearray, /) -> bool:
418)         """Check whether the key is suitable for passphrase derivation.
419) 
420)         Currently, this only checks whether signatures with this key
421)         type are deterministic.
422) 
423)         Args:
424)             key: SSH public key to check.
425) 
426)         Returns:
427)             True if and only if the key is suitable for use in deriving
428)             a passphrase deterministically.
429) 
430)         """

431)         TestFunc: TypeAlias = Callable[[bytes | bytearray], bool]
432)         deterministic_signature_types: dict[str, TestFunc]

433)         deterministic_signature_types = {

434)             'ssh-ed25519': lambda k: k.startswith(
435)                 b'\x00\x00\x00\x0bssh-ed25519'
436)             ),
437)             'ssh-ed448': lambda k: k.startswith(b'\x00\x00\x00\x09ssh-ed448'),
438)             'ssh-rsa': lambda k: k.startswith(b'\x00\x00\x00\x07ssh-rsa'),

439)         }
440)         return any(v(key) for v in deterministic_signature_types.values())
441) 

442)     @classmethod

443)     def phrase_from_key(cls, key: bytes | bytearray, /) -> bytes:

444)         """Obtain the master passphrase from a configured SSH key.
445) 
446)         vault allows the usage of certain SSH keys to derive a master
447)         passphrase, by signing the vault UUID with the SSH key.  The key
448)         type must ensure that signatures are deterministic.
449) 
450)         Args:
451)             key: The (public) SSH key to use for signing.
452) 
453)         Returns:

454)             The signature of the vault UUID under this key, unframed but
455)             encoded in base64.

456) 
457)         Raises:
458)             ValueError:
459)                 The SSH key is principally unsuitable for this use case.
460)                 Usually this means that the signature is not
461)                 deterministic.
462) 

463)         Examples:

464)             >>> import base64
465)             >>> # Actual Ed25519 test public key.

466)             >>> public_key = bytes.fromhex('''
467)             ... 00 00 00 0b 73 73 68 2d 65 64 32 35 35 31 39
468)             ... 00 00 00 20
469)             ... 81 78 81 68 26 d6 02 48 5f 0f ff 32 48 6f e4 c1
470)             ... 30 89 dc 1c 6a 45 06 09 e9 09 0f fb c2 12 69 76
471)             ... ''')

472)             >>> expected_sig_raw = bytes.fromhex('''

473)             ... 00 00 00 0b 73 73 68 2d 65 64 32 35 35 31 39
474)             ... 00 00 00 40
475)             ... f0 98 19 80 6c 1a 97 d5 26 03 6e cc e3 65 8f 86
476)             ... 66 07 13 19 13 09 21 33 33 f9 e4 36 53 1d af fd
477)             ... 0d 08 1f ec f8 73 9b 8c 5f 55 39 16 7c 53 54 2c
478)             ... 1e 52 bb 30 ed 7f 89 e2 2f 69 51 55 d8 9e a6 02
479)             ... ''')

480)             >>> # Raw Ed25519 signatures are 64 bytes long.
481)             >>> signature_blob = expected_sig_raw[-64:]
482)             >>> phrase = base64.standard_b64encode(signature_blob)
483)             >>> Vault.phrase_from_key(phrase) == expected  # doctest:+SKIP

484)             True
485) 

486)         """

487)         if not cls._is_suitable_ssh_key(key):

488)             msg = (
489)                 'unsuitable SSH key: bad key, or '
490)                 'signature not deterministic'
491)             )

492)             raise ValueError(msg)

493)         with ssh_agent_client.SSHAgentClient() as client:

494)             raw_sig = client.sign(key, cls._UUID)

495)         _keytype, trailer = client.unstring_prefix(raw_sig)

496)         signature_blob = client.unstring(trailer)
497)         return bytes(base64.standard_b64encode(signature_blob))

498) 

499)     @staticmethod

500)     def _subtract(

501)         charset: bytes | bytearray,
502)         allowed: bytes | bytearray,

503)     ) -> bytearray:
504)         """Remove the characters in charset from allowed.
505) 
506)         This preserves the relative order of characters in `allowed`.
507) 
508)         Args:

509)             charset:
510)                 Characters to remove.  Must not contain duplicate
511)                 characters.
512)             allowed:
513)                 Character set to remove the other characters from.  Must
514)                 not contain duplicate characters.

515) 
516)         Returns:

517)             The pruned "allowed" character set.

518) 
519)         Raises:

520)             ValueError:
521)                 `allowed` or `charset` contained duplicate characters.

522) 
523)         """

524)         allowed = (
525)             allowed if isinstance(allowed, bytearray) else bytearray(allowed)
526)         )

527)         assert_type(allowed, bytearray)

528)         msg_dup_characters = 'duplicate characters in set'

529)         if len(frozenset(allowed)) != len(allowed):

530)             raise ValueError(msg_dup_characters)

531)         if len(frozenset(charset)) != len(charset):

532)             raise ValueError(msg_dup_characters)

533)         for c in charset:
534)             try:
535)                 pos = allowed.index(c)

536)             except ValueError:

537)                 pass
538)             else:

539)                 allowed[pos : pos + 1] = []