derivepassphrase.git

1) # SPDX-FileCopyrightText: 2025 Marco Ricci <software@the13thletter.info>

2) #

3) # SPDX-License-Identifier: Zlib

4) 

5) """Python port of the vault(1) password generation scheme."""

6) 
7) from __future__ import annotations
8) 
9) import base64
10) import collections
11) import hashlib
12) import math

13) import types

14) from typing import TYPE_CHECKING

15) 

16) from typing_extensions import TypeAlias, assert_type

17) 
18) from derivepassphrase import sequin, ssh_agent
19) 

20) if TYPE_CHECKING:

21)     import socket

22)     from collections.abc import Callable
23) 

24) __author__ = 'Marco Ricci <software@the13thletter.info>'

25) 
26) 
27) class Vault:
28)     """A work-alike of James Coglan's vault.
29) 
30)     Store settings for generating (actually: deriving) passphrases for
31)     named services, with various constraints, given only a master
32)     passphrase.  Also, actually generate the passphrase.  The derivation
33)     is deterministic and non-secret; only the master passphrase need be
34)     kept secret.  The implementation is compatible with [vault][].
35) 
36)     [James Coglan explains the passphrase derivation algorithm in great
37)     detail][ALGORITHM] in his blog post on said topic: A principally
38)     infinite bit stream is obtained by running a key-derivation function
39)     on the master passphrase and the service name, then this bit stream

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

43) 

44)     [vault]: https://www.npmjs.com/package/vault

45)     [ALGORITHM]: https://blog.jcoglan.com/2012/07/16/designing-vaults-generator-algorithm/
46) 
47)     """
48) 
49)     _UUID = b'e87eb0f4-34cb-46b9-93ad-766c5ab063e7'
50)     """A tag used by vault in the bit stream generation."""

51)     _CHARSETS = types.MappingProxyType(
52)         collections.OrderedDict([
53)             ('lower', b'abcdefghijklmnopqrstuvwxyz'),
54)             ('upper', b'ABCDEFGHIJKLMNOPQRSTUVWXYZ'),
55)             (
56)                 'alpha',
57)                 (
58)                     # _CHARSETS['lower']
59)                     b'abcdefghijklmnopqrstuvwxyz'
60)                     # _CHARSETS['upper']
61)                     b'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
62)                 ),
63)             ),
64)             ('number', b'0123456789'),
65)             (
66)                 'alphanum',
67)                 (
68)                     # _CHARSETS['lower']
69)                     b'abcdefghijklmnopqrstuvwxyz'
70)                     # _CHARSETS['upper']
71)                     b'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
72)                     # _CHARSETS['number']
73)                     b'0123456789'
74)                 ),
75)             ),
76)             ('space', b' '),
77)             ('dash', b'-_'),
78)             ('symbol', b'!"#$%&\'()*+,./:;<=>?@[\\]^{|}~-_'),
79)             (
80)                 'all',
81)                 (
82)                     # _CHARSETS['lower']
83)                     b'abcdefghijklmnopqrstuvwxyz'
84)                     # _CHARSETS['upper']
85)                     b'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
86)                     # _CHARSETS['number']
87)                     b'0123456789'
88)                     # _CHARSETS['space']
89)                     b' '
90)                     # _CHARSETS['symbol']
91)                     b'!"#$%&\'()*+,./:;<=>?@[\\]^{|}~-_'
92)                 ),
93)             ),
94)         ])
95)     )

96)     """
97)         Known character sets from which to draw passphrase characters.
98)         Relies on a certain, fixed order for their definition and their
99)         contents.
100) 
101)     """
102) 

103)     def __init__(  # noqa: PLR0913

104)         self,
105)         *,
106)         phrase: bytes | bytearray | str = b'',
107)         length: int = 20,
108)         repeat: int = 0,
109)         lower: int | None = None,
110)         upper: int | None = None,
111)         number: int | None = None,
112)         space: int | None = None,
113)         dash: int | None = None,
114)         symbol: int | None = None,
115)     ) -> None:
116)         """Initialize the Vault object.
117) 
118)         Args:
119)             phrase:
120)                 The master passphrase from which to derive the service

121)                 passphrases.  If a string, then the UTF-8 encoding of
122)                 the string is used.

123)             length:
124)                 Desired passphrase length.
125)             repeat:
126)                 The maximum number of immediate character repetitions
127)                 allowed in the passphrase.  Disabled if set to 0.
128)             lower:
129)                 Optional constraint on ASCII lowercase characters.  If
130)                 positive, include this many lowercase characters
131)                 somewhere in the passphrase.  If 0, avoid lowercase
132)                 characters altogether.
133)             upper:
134)                 Same as `lower`, but for ASCII uppercase characters.
135)             number:
136)                 Same as `lower`, but for ASCII digits.
137)             space:
138)                 Same as `lower`, but for the space character.
139)             dash:
140)                 Same as `lower`, but for the hyphen-minus and underscore
141)                 characters.
142)             symbol:
143)                 Same as `lower`, but for all other hitherto unlisted
144)                 ASCII printable characters (except backquote).
145) 

146)         Raises:
147)             ValueError:
148)                 Conflicting passphrase constraints.  Permit more
149)                 characters, or increase the desired passphrase length.
150) 

151)         Warning:
152)             Because of repetition constraints, it is not always possible
153)             to detect conflicting passphrase constraints at construction
154)             time.
155) 

156)         """
157)         self._phrase = self._get_binary_string(phrase)
158)         self._length = length
159)         self._repeat = repeat
160)         self._allowed = bytearray(self._CHARSETS['all'])
161)         self._required: list[bytes] = []
162) 
163)         def subtract_or_require(
164)             count: int | None, characters: bytes | bytearray
165)         ) -> None:
166)             if not isinstance(count, int):
167)                 return
168)             if count <= 0:
169)                 self._allowed = self._subtract(characters, self._allowed)
170)             else:
171)                 for _ in range(count):
172)                     self._required.append(characters)
173) 
174)         subtract_or_require(lower, self._CHARSETS['lower'])
175)         subtract_or_require(upper, self._CHARSETS['upper'])
176)         subtract_or_require(number, self._CHARSETS['number'])
177)         subtract_or_require(space, self._CHARSETS['space'])
178)         subtract_or_require(dash, self._CHARSETS['dash'])
179)         subtract_or_require(symbol, self._CHARSETS['symbol'])
180)         if len(self._required) > self._length:
181)             msg = 'requested passphrase length too short'
182)             raise ValueError(msg)
183)         if not self._allowed:
184)             msg = 'no allowed characters left'
185)             raise ValueError(msg)
186)         for _ in range(len(self._required), self._length):
187)             self._required.append(bytes(self._allowed))
188) 
189)     def _entropy(self) -> float:
190)         """Estimate the passphrase entropy, given the current settings.
191) 
192)         The entropy is the base 2 logarithm of the amount of
193)         possibilities.  We operate directly on the logarithms, and use
194)         sorting and [`math.fsum`][] to keep high accuracy.
195) 
196)         Note:
197)             We actually overestimate the entropy here because of poor
198)             handling of character repetitions.  In the extreme, assuming
199)             that only one character were allowed, then because there is
200)             only one possible string of each given length, the entropy
201)             of that string `s` is always be zero.  However, we calculate
202)             the entropy as `math.log2(math.factorial(len(s)))`, i.e. we
203)             assume the characters at the respective string position are
204)             distinguishable from each other.
205) 
206)         Returns:
207)             A valid (and somewhat close) upper bound to the entropy.
208) 
209)         """
210)         factors: list[int] = []
211)         if not self._required or any(not x for x in self._required):
212)             return float('-inf')
213)         for i, charset in enumerate(self._required):
214)             factors.extend([i + 1, len(charset)])
215)         factors.sort()
216)         return math.fsum(math.log2(f) for f in factors)
217) 
218)     def _estimate_sufficient_hash_length(
219)         self,
220)         safety_factor: float = 2.0,
221)     ) -> int:
222)         """Estimate the sufficient hash length, given the current settings.
223) 

224)         Using the entropy (via [`_entropy`][]) and a safety factor, give
225)         an initial estimate of the length to use for [`create_hash`][]
226)         such that using a [`sequin.Sequin`][] with this hash will not
227)         exhaust it during passphrase generation.

228) 
229)         Args:
230)             safety_factor: The safety factor.  Must be at least 1.
231) 
232)         Returns:
233)             The estimated sufficient hash length.
234) 

235)         Raises:
236)             ValueError: The safety factor is less than 1, or not finite.
237) 

238)         Warning:
239)             This is a heuristic, not an exact computation; it may
240)             underestimate the true necessary hash length.  It is
241)             intended as a starting point for searching for a sufficient
242)             hash length, usually by doubling the hash length each time
243)             it does not yet prove so.
244) 

245)         """  # noqa: DOC501

246)         try:
247)             safety_factor = float(safety_factor)
248)         except TypeError as e:
249)             msg = f'invalid safety factor: not a float: {safety_factor!r}'

250)             raise TypeError(msg) from e

251)         if not math.isfinite(safety_factor) or safety_factor < 1.0:
252)             msg = f'invalid safety factor {safety_factor!r}'

253)             raise ValueError(msg)

254)         # Ensure the bound is strictly positive.
255)         entropy_bound = max(1, self._entropy())

256)         return math.ceil(safety_factor * entropy_bound / 8)

257) 
258)     @staticmethod
259)     def _get_binary_string(s: bytes | bytearray | str, /) -> bytes:
260)         """Convert the input string to a read-only, binary string.
261) 

262)         If it is a text string, return the string's UTF-8
263)         representation.

264) 
265)         Args:
266)             s: The string to (check and) convert.
267) 
268)         Returns:
269)             A read-only, binary copy of the string.
270) 
271)         """
272)         if isinstance(s, str):
273)             return s.encode('UTF-8')
274)         return bytes(s)
275) 
276)     @classmethod
277)     def create_hash(
278)         cls,
279)         phrase: bytes | bytearray | str,

280)         service: bytes | bytearray | str,

281)         *,
282)         length: int = 32,
283)     ) -> bytes:
284)         r"""Create a pseudorandom byte stream from phrase and service.
285) 
286)         Create a pseudorandom byte stream from `phrase` and `service` by
287)         feeding them into the key-derivation function PBKDF2
288)         (8 iterations, using SHA-1).
289) 
290)         Args:
291)             phrase:
292)                 A master passphrase, or sometimes an SSH signature.
293)                 Used as the key for PBKDF2, the underlying cryptographic

294)                 primitive.  If a string, then the UTF-8 encoding of the
295)                 string is used.

296)             service:
297)                 A vault service name.  Will be suffixed with
298)                 `Vault._UUID`, and then used as the salt value for

299)                 PBKDF2.  If a string, then the UTF-8 encoding of the
300)                 string is used.

301)             length:
302)                 The length of the byte stream to generate.
303) 
304)         Returns:
305)             A pseudorandom byte string of length `length`.
306) 
307)         Note:
308)             Shorter values returned from this method (with the same key
309)             and message) are prefixes of longer values returned from
310)             this method.  (This property is inherited from the
311)             underlying PBKDF2 function.)  It is thus safe (if slow) to
312)             call this method with the same input with ever-increasing
313)             target lengths.
314) 
315)         Examples:
316)             >>> # See also Vault.phrase_from_key examples.
317)             >>> phrase = bytes.fromhex('''
318)             ... 00 00 00 0b 73 73 68 2d 65 64 32 35 35 31 39
319)             ... 00 00 00 40
320)             ... f0 98 19 80 6c 1a 97 d5 26 03 6e cc e3 65 8f 86
321)             ... 66 07 13 19 13 09 21 33 33 f9 e4 36 53 1d af fd
322)             ... 0d 08 1f ec f8 73 9b 8c 5f 55 39 16 7c 53 54 2c
323)             ... 1e 52 bb 30 ed 7f 89 e2 2f 69 51 55 d8 9e a6 02
324)             ... ''')

325)             >>> Vault.create_hash(phrase, 'some_service', length=4)

326)             b'M\xb1<S'
327)             >>> Vault.create_hash(phrase, b'some_service', length=16)
328)             b'M\xb1<S\x827E\xd1M\xaf\xf8~\xc8n\x10\xcc'
329)             >>> Vault.create_hash(phrase, b'NOSUCHSERVICE', length=16)
330)             b'\x1c\xc3\x9c\xd9\xb6\x1a\x99CS\x07\xc41\xf4\x85#s'
331) 
332)         """
333)         phrase = cls._get_binary_string(phrase)
334)         assert not isinstance(phrase, str)

335)         salt = cls._get_binary_string(service) + cls._UUID

336)         return hashlib.pbkdf2_hmac(
337)             hash_name='sha1',
338)             password=phrase,
339)             salt=salt,
340)             iterations=8,
341)             dklen=length,
342)         )
343) 
344)     def generate(
345)         self,

346)         service_name: bytes | bytearray | str,

347)         /,
348)         *,
349)         phrase: bytes | bytearray | str = b'',
350)     ) -> bytes:
351)         r"""Generate a service passphrase.
352) 
353)         Args:
354)             service_name:

355)                 The service name.  If a string, then the UTF-8 encoding
356)                 of the string is used.

357)             phrase:
358)                 If given, override the passphrase given during

359)                 construction.  If a string, then the UTF-8 encoding of
360)                 the string is used.

361) 
362)         Returns:
363)             The service passphrase.
364) 

365)         Raises:
366)             ValueError:
367)                 Conflicting passphrase constraints.  Permit more
368)                 characters, or increase the desired passphrase length.
369) 

370)         Examples:
371)             >>> phrase = b'She cells C shells bye the sea shoars'
372)             >>> # Using default options in constructor.
373)             >>> Vault(phrase=phrase).generate(b'google')
374)             b': 4TVH#5:aZl8LueOT\\{'
375)             >>> # Also possible:
376)             >>> Vault().generate(b'google', phrase=phrase)
377)             b': 4TVH#5:aZl8LueOT\\{'
378) 

379)             Conflicting constraints are sometimes only found during
380)             generation.
381) 
382)             >>> # Note: no error here...
383)             >>> v = Vault(
384)             ...     lower=0,
385)             ...     upper=0,
386)             ...     number=0,
387)             ...     space=2,
388)             ...     dash=0,
389)             ...     symbol=1,
390)             ...     repeat=2,
391)             ...     length=3,
392)             ... )
393)             >>> # ... but here.
394)             >>> v.generate(
395)             ...     '0', phrase=b'\x00'
396)             ... )  # doctest: +IGNORE_EXCEPTION_DETAIL
397)             Traceback (most recent call last):
398)                 ...
399)             ValueError: no allowed characters left
400) 
401) 

402)         """
403)         hash_length = self._estimate_sufficient_hash_length()
404)         assert hash_length >= 1

405)         # Ensure the phrase and the service name are bytes objects.
406)         # This is needed later for safe concatenation.
407)         service_name = self._get_binary_string(service_name)

408)         assert_type(service_name, bytes)
409)         if not phrase:
410)             phrase = self._phrase
411)         phrase = self._get_binary_string(phrase)

412)         assert_type(phrase, bytes)

413)         # Repeat the passphrase generation with ever-increasing hash
414)         # lengths, until the passphrase can be formed without exhausting
415)         # the sequin.  See the guarantee in the create_hash method for
416)         # why this works.
417)         while True:
418)             try:
419)                 required = self._required[:]
420)                 seq = sequin.Sequin(
421)                     self.create_hash(
422)                         phrase=phrase, service=service_name, length=hash_length
423)                     )
424)                 )
425)                 result = bytearray()
426)                 while len(result) < self._length:
427)                     pos = seq.generate(len(required))
428)                     charset = required.pop(pos)
429)                     # Determine if an unlucky choice right now might
430)                     # violate the restriction on repeated characters.
431)                     # That is, check if the current partial passphrase
432)                     # ends with r - 1 copies of the same character
433)                     # (where r is the repeat limit that must not be
434)                     # reached), and if so, remove this same character
435)                     # from the current character's allowed set.
436)                     if self._repeat and result:
437)                         bad_suffix = bytes(result[-1:]) * (self._repeat - 1)
438)                         if result.endswith(bad_suffix):
439)                             charset = self._subtract(
440)                                 bytes(result[-1:]), charset
441)                             )
442)                     pos = seq.generate(len(charset))
443)                     result.extend(charset[pos : pos + 1])

444)             except ValueError as exc:
445)                 msg = 'no allowed characters left'
446)                 raise ValueError(msg) from exc

447)             except sequin.SequinExhaustedError:
448)                 hash_length *= 2
449)             else:
450)                 return bytes(result)
451) 
452)     @staticmethod

453)     def is_suitable_ssh_key(
454)         key: bytes | bytearray,
455)         /,
456)         *,
457)         client: ssh_agent.SSHAgentClient | None = None,
458)     ) -> bool:

459)         """Check whether the key is suitable for passphrase derivation.
460) 

461)         Some key types are guaranteed to be deterministic.  Other keys
462)         types are only deterministic if the SSH agent supports this
463)         feature.

464) 
465)         Args:

466)             key:
467)                 SSH public key to check.
468)             client:
469)                 An optional SSH agent client to check for additional
470)                 deterministic key types.  If not given, assume no such
471)                 types.

472) 
473)         Returns:

474)             True if and only if the key is guaranteed suitable for use
475)             in deriving a passphrase deterministically (perhaps
476)             restricted to the indicated SSH agent).

477) 
478)         """

479)         TestFunc: TypeAlias = 'Callable[[bytes | bytearray], bool]'

480)         deterministic_signature_types: dict[str, TestFunc]
481)         deterministic_signature_types = {
482)             'ssh-ed25519': lambda k: k.startswith(
483)                 b'\x00\x00\x00\x0bssh-ed25519'
484)             ),
485)             'ssh-ed448': lambda k: k.startswith(b'\x00\x00\x00\x09ssh-ed448'),
486)             'ssh-rsa': lambda k: k.startswith(b'\x00\x00\x00\x07ssh-rsa'),
487)         }

488)         dsa_signature_types = {
489)             'ssh-dss': lambda k: k.startswith(b'\x00\x00\x00\x07ssh-dss'),
490)             'ecdsa-sha2-nistp256': lambda k: k.startswith(
491)                 b'\x00\x00\x00\x13ecdsa-sha2-nistp256'
492)             ),
493)             'ecdsa-sha2-nistp384': lambda k: k.startswith(
494)                 b'\x00\x00\x00\x13ecdsa-sha2-nistp384'
495)             ),
496)             'ecdsa-sha2-nistp521': lambda k: k.startswith(
497)                 b'\x00\x00\x00\x13ecdsa-sha2-nistp521'
498)             ),
499)         }
500)         criteria = [
501)             lambda: any(
502)                 v(key) for v in deterministic_signature_types.values()
503)             ),
504)         ]
505)         if client is not None:
506)             criteria.append(
507)                 lambda: (
508)                     client.has_deterministic_dsa_signatures()
509)                     and any(v(key) for v in dsa_signature_types.values())
510)                 )
511)             )
512)         return any(crit() for crit in criteria)

513) 
514)     @classmethod

515)     def phrase_from_key(
516)         cls,
517)         key: bytes | bytearray,
518)         /,
519)         *,
520)         conn: ssh_agent.SSHAgentClient | socket.socket | None = None,
521)     ) -> bytes:

522)         """Obtain the master passphrase from a configured SSH key.
523) 
524)         vault allows the usage of certain SSH keys to derive a master
525)         passphrase, by signing the vault UUID with the SSH key.  The key

526)         type must ensure that signatures are deterministic (perhaps only
527)         in conjunction with the given SSH agent).

528) 
529)         Args:

530)             key:
531)                 The (public) SSH key to use for signing.
532)             conn:
533)                 An optional connection hint to the SSH agent.  See
534)                 [`ssh_agent.SSHAgentClient.ensure_agent_subcontext`][].

535) 
536)         Returns:
537)             The signature of the vault UUID under this key, unframed but
538)             encoded in base64.
539) 
540)         Raises:

541)             KeyError:
542)                 `conn` was `None`, and the `SSH_AUTH_SOCK` environment
543)                 variable was not found.
544)             NotImplementedError:
545)                 `conn` was `None`, and this Python does not support
546)                 [`socket.AF_UNIX`][], so the SSH agent client cannot be
547)                 automatically set up.
548)             OSError:
549)                 `conn` was a socket or `None`, and there was an error
550)                 setting up a socket connection to the agent.

551)             ValueError:
552)                 The SSH key is principally unsuitable for this use case.
553)                 Usually this means that the signature is not
554)                 deterministic.
555) 
556)         Examples:
557)             >>> import base64
558)             >>> # Actual Ed25519 test public key.
559)             >>> public_key = bytes.fromhex('''
560)             ... 00 00 00 0b 73 73 68 2d 65 64 32 35 35 31 39
561)             ... 00 00 00 20
562)             ... 81 78 81 68 26 d6 02 48 5f 0f ff 32 48 6f e4 c1
563)             ... 30 89 dc 1c 6a 45 06 09 e9 09 0f fb c2 12 69 76
564)             ... ''')
565)             >>> expected_sig_raw = bytes.fromhex('''
566)             ... 00 00 00 0b 73 73 68 2d 65 64 32 35 35 31 39
567)             ... 00 00 00 40
568)             ... f0 98 19 80 6c 1a 97 d5 26 03 6e cc e3 65 8f 86
569)             ... 66 07 13 19 13 09 21 33 33 f9 e4 36 53 1d af fd
570)             ... 0d 08 1f ec f8 73 9b 8c 5f 55 39 16 7c 53 54 2c
571)             ... 1e 52 bb 30 ed 7f 89 e2 2f 69 51 55 d8 9e a6 02
572)             ... ''')
573)             >>> # Raw Ed25519 signatures are 64 bytes long.
574)             >>> signature_blob = expected_sig_raw[-64:]
575)             >>> phrase = base64.standard_b64encode(signature_blob)
576)             >>> Vault.phrase_from_key(phrase) == expected  # doctest:+SKIP
577)             True
578) 
579)         """

580)         with ssh_agent.SSHAgentClient.ensure_agent_subcontext(conn) as client:

581)             if not cls.is_suitable_ssh_key(key, client=client):

582)                 msg = (
583)                     'unsuitable SSH key: bad key, or '
584)                     'signature not deterministic under this agent'
585)                 )
586)                 raise ValueError(msg)

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

588)         _keytype, trailer = ssh_agent.SSHAgentClient.unstring_prefix(raw_sig)
589)         signature_blob = ssh_agent.SSHAgentClient.unstring(trailer)