derivepassphrase.git

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

2) #
3) # SPDX-License-Identifier: MIT
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)         Warning:
236)             This is a heuristic, not an exact computation; it may
237)             underestimate the true necessary hash length.  It is
238)             intended as a starting point for searching for a sufficient
239)             hash length, usually by doubling the hash length each time
240)             it does not yet prove so.
241) 
242)         """
243)         try:
244)             safety_factor = float(safety_factor)
245)         except TypeError as e:
246)             msg = f'invalid safety factor: not a float: {safety_factor!r}'

247)             raise TypeError(msg) from e  # noqa: DOC501

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

250)             raise ValueError(msg)  # noqa: DOC501

251)         # Ensure the bound is strictly positive.
252)         entropy_bound = max(1, self._entropy())
253)         return int(math.ceil(safety_factor * entropy_bound / 8))
254) 
255)     @staticmethod
256)     def _get_binary_string(s: bytes | bytearray | str, /) -> bytes:
257)         """Convert the input string to a read-only, binary string.
258) 

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

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

277)         service: bytes | bytearray | str,

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

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

293)             service:
294)                 A vault service name.  Will be suffixed with
295)                 `Vault._UUID`, and then used as the salt value for

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

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

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

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

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

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

343)         service_name: bytes | bytearray | str,

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

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

354)             phrase:
355)                 If given, override the passphrase given during

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

358) 
359)         Returns:
360)             The service passphrase.
361) 

362)         Raises:
363)             ValueError:
364)                 Conflicting passphrase constraints.  Permit more
365)                 characters, or increase the desired passphrase length.
366) 

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

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

399)         """
400)         hash_length = self._estimate_sufficient_hash_length()
401)         assert hash_length >= 1

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

405)         assert_type(service_name, bytes)
406)         if not phrase:
407)             phrase = self._phrase
408)         phrase = self._get_binary_string(phrase)

409)         assert_type(phrase, bytes)

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

441)             except ValueError as exc:
442)                 msg = 'no allowed characters left'
443)                 raise ValueError(msg) from exc

444)             except sequin.SequinExhaustedError:
445)                 hash_length *= 2
446)             else:
447)                 return bytes(result)
448) 
449)     @staticmethod

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

456)         """Check whether the key is suitable for passphrase derivation.
457) 

458)         Some key types are guaranteed to be deterministic.  Other keys
459)         types are only deterministic if the SSH agent supports this
460)         feature.

461) 
462)         Args:

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

469) 
470)         Returns:

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

474) 
475)         """

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

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

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

510) 
511)     @classmethod

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

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

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

525) 
526)         Args:

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

532) 
533)         Returns:
534)             The signature of the vault UUID under this key, unframed but
535)             encoded in base64.
536) 
537)         Raises:

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

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

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

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

579)                 msg = (
580)                     'unsuitable SSH key: bad key, or '
581)                     'signature not deterministic under this agent'
582)                 )
583)                 raise ValueError(msg)

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

585)         _keytype, trailer = ssh_agent.SSHAgentClient.unstring_prefix(raw_sig)
586)         signature_blob = ssh_agent.SSHAgentClient.unstring(trailer)