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
6) 
7) """
8) 
9) from __future__ import annotations
10) 
11) import collections
12) import hashlib
13) import math
14) import warnings
15) 
16) from typing import assert_type, reveal_type
17) 
18) import sequin
19) import ssh_agent_client
20) 

21) __author__ = "Marco Ricci <m@the13thletter.info>"
22) __version__ = "0.1.0"
23) 

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

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

40) 
41)     [vault]: https://getvau.lt
42)     [ALGORITHM]: https://blog.jcoglan.com/2012/07/16/designing-vaults-generator-algorithm/
43) 
44)     """
45)     _UUID = b'e87eb0f4-34cb-46b9-93ad-766c5ab063e7'
46)     """A tag used by vault in the bit stream generation."""
47)     _CHARSETS: collections.OrderedDict[str, bytes]
48)     """
49)         Known character sets from which to draw passphrase characters.
50)         Relies on a certain, fixed order for their definition and their
51)         contents.
52) 
53)     """
54)     _CHARSETS = collections.OrderedDict([
55)         ('lower', b'abcdefghijklmnopqrstuvwxyz'),
56)         ('upper', b'ABCDEFGHIJKLMNOPQRSTUVWXYZ'),
57)         ('alpha', b''),  # Placeholder.
58)         ('number', b'0123456789'),
59)         ('alphanum', b''),  # Placeholder.
60)         ('space', b' '),
61)         ('dash', b'-_'),
62)         ('symbol', b'!"#$%&\'()*+,./:;<=>?@[\\]^{|}~-_'),
63)         ('all', b''),  # Placeholder.
64)     ])
65)     _CHARSETS['alpha'] = _CHARSETS['lower'] + _CHARSETS['upper']
66)     _CHARSETS['alphanum'] = _CHARSETS['alpha'] + _CHARSETS['number']
67)     _CHARSETS['all'] = (_CHARSETS['alphanum'] + _CHARSETS['space']
68)                         + _CHARSETS['symbol'])
69) 
70)     def __init__(
71)         self, *, phrase: bytes | bytearray = b'', length: int = 20,
72)         repeat: int = 0, lower: int | None = None,
73)         upper: int | None = None, number: int | None = None,
74)         space: int | None = None, dash: int | None = None,
75)         symbol: int | None = None,
76)     ) -> None:
77)         """Initialize the Vault object.
78) 
79)         Args:
80)             phrase:
81)                 The master passphrase from which to derive the service
82)                 passphrases.
83)             length:
84)                 Desired passphrase length.
85)             repeat:
86)                 The maximum number of immediate character repetitions
87)                 allowed in the passphrase.  Disabled if set to 0.
88)             lower:
89)                 Optional constraint on lowercase characters.  If
90)                 positive, include this many lowercase characters
91)                 somewhere in the passphrase.  If 0, avoid lowercase
92)                 characters altogether.
93)             upper:
94)                 Same as `lower`, but for uppercase characters.
95)             number:
96)                 Same as `lower`, but for ASCII digits.
97)             space:
98)                 Same as `lower`, but for the space character.
99)             dash:
100)                 Same as `lower`, but for the hyphen-minus and underscore
101)                 characters.
102)             symbol:
103)                 Same as `lower`, but for all other hitherto unlisted
104)                 ASCII printable characters (except backquote).
105) 
106)         """
107)         self._phrase = bytes(phrase)
108)         self._length = length
109)         self._repeat = repeat
110)         self._allowed = bytearray(self._CHARSETS['all'])
111)         self._required: list[bytes] = []
112)         def subtract_or_require(
113)             count: int | None, characters: bytes | bytearray
114)         ) -> None:
115)             if not isinstance(count, int):
116)                 return
117)             elif count <= 0:
118)                 self._allowed = self._subtract(characters, self._allowed)
119)             else:
120)                 for _ in range(count):
121)                     self._required.append(characters)
122)         subtract_or_require(lower, self._CHARSETS['lower'])
123)         subtract_or_require(upper, self._CHARSETS['upper'])
124)         subtract_or_require(number, self._CHARSETS['number'])
125)         subtract_or_require(space, self._CHARSETS['space'])
126)         subtract_or_require(dash, self._CHARSETS['dash'])
127)         subtract_or_require(symbol, self._CHARSETS['symbol'])

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

129)             raise ValueError('requested passphrase length too short')
130)         if not self._allowed:
131)             raise ValueError('no allowed characters left')
132)         for _ in range(len(self._required), self._length):
133)             self._required.append(bytes(self._allowed))
134) 
135)     def _entropy_upper_bound(self) -> int:
136)         """Estimate the passphrase entropy, given the current settings.
137) 
138)         The entropy is the base 2 logarithm of the amount of
139)         possibilities.  We operate directly on the logarithms, and round
140)         each summand up, overestimating the true entropy.
141) 
142)         """
143)         factors: list[int] = []
144)         for i, charset in enumerate(self._required):
145)             factors.append(i + 1)
146)             factors.append(len(charset))
147)         return sum(int(math.ceil(math.log2(f))) for f in factors)
148) 
149)     @classmethod
150)     def create_hash(

151)         cls, phrase: bytes | bytearray, service: bytes | bytearray, *,

152)         length: int = 32,
153)     ) -> bytes:

154)         r"""Create a pseudorandom byte stream from phrase and service.
155) 
156)         Create a pseudorandom byte stream from `phrase` and `service` by
157)         feeding them into the key-derivation function PBKDF2
158)         (8 iterations, using SHA-1).

159) 
160)         Args:

161)             phrase:
162)                 A master passphrase, or sometimes an SSH signature.
163)                 Used as the key for PBKDF2, the underlying cryptographic
164)                 primitive.
165)             service:
166)                 A vault service name.  Will be suffixed with
167)                 `Vault._UUID`, and then used as the salt value for
168)                 PBKDF2.

169)             length:
170)                 The length of the byte stream to generate.
171) 
172)         Returns:
173)             A pseudorandom byte string of length `length`.
174) 
175)         Note:
176)             Shorter values returned from this method (with the same key
177)             and message) are prefixes of longer values returned from
178)             this method.  (This property is inherited from the
179)             underlying PBKDF2 function.)  It is thus safe (if slow) to
180)             call this method with the same input with ever-increasing
181)             target lengths.
182) 

183)         Examples:
184)             >>> # See also Vault.phrase_from_signature examples.
185)             >>> phrase = bytes.fromhex('''
186)             ... 00 00 00 0b 73 73 68 2d 65 64 32 35 35 31 39
187)             ... 00 00 00 40
188)             ... f0 98 19 80 6c 1a 97 d5 26 03 6e cc e3 65 8f 86
189)             ... 66 07 13 19 13 09 21 33 33 f9 e4 36 53 1d af fd
190)             ... 0d 08 1f ec f8 73 9b 8c 5f 55 39 16 7c 53 54 2c
191)             ... 1e 52 bb 30 ed 7f 89 e2 2f 69 51 55 d8 9e a6 02
192)             ... ''')
193)             >>> Vault.create_hash(phrase, b'some_service', length=4)
194)             b'M\xb1<S'
195)             >>> Vault.create_hash(phrase, b'some_service', length=16)
196)             b'M\xb1<S\x827E\xd1M\xaf\xf8~\xc8n\x10\xcc'
197)             >>> Vault.create_hash(phrase, b'NOSUCHSERVICE', length=16)
198)             b'\x1c\xc3\x9c\xd9\xb6\x1a\x99CS\x07\xc41\xf4\x85#s'
199) 

200)         """

201)         salt = bytes(service) + cls._UUID
202)         return hashlib.pbkdf2_hmac(hash_name='sha1', password=phrase,
203)                                    salt=salt, iterations=8, dklen=length)

204) 
205)     def generate(

206)         self, service_name: str | bytes | bytearray, /, *,
207)         phrase: bytes | bytearray = b'',
208)     ) -> bytes:
209)         r"""Generate a service passphrase.

210) 
211)         Args:
212)             service_name:
213)                 The service name.
214)             phrase:
215)                 If given, override the passphrase given during
216)                 construction.
217) 

218)         Examples:
219)             >>> phrase = b'She cells C shells bye the sea shoars'
220)             >>> # Using default options in constructor.
221)             >>> Vault(phrase=phrase).generate(b'google')
222)             b': 4TVH#5:aZl8LueOT\\{'
223)             >>> # Also possible:
224)             >>> Vault().generate(b'google', phrase=phrase)
225)             b': 4TVH#5:aZl8LueOT\\{'
226) 

227)         """
228)         entropy_bound = self._entropy_upper_bound()
229)         # Use a safety factor, because a sequin will potentially throw
230)         # bits away and we cannot rely on having generated a hash of
231)         # exactly the right length.
232)         safety_factor = 2
233)         hash_length = int(math.ceil(safety_factor * entropy_bound / 8))

234)         # Ensure the phrase is a bytes object.  Needed later for safe
235)         # concatenation.
236)         if isinstance(service_name, str):
237)             service_name = service_name.encode('utf-8')
238)         elif not isinstance(service_name, bytes):
239)             service_name = bytes(service_name)
240)         assert_type(service_name, bytes)

241)         if not phrase:
242)             phrase = self._phrase
243)         # Repeat the passphrase generation with ever-increasing hash
244)         # lengths, until the passphrase can be formed without exhausting
245)         # the sequin.  See the guarantee in the create_hash method for
246)         # why this works.
247)         while True:
248)             try:
249)                 required = self._required[:]
250)                 seq = sequin.Sequin(self.create_hash(

251)                     phrase=phrase, service=service_name, length=hash_length))

252)                 result = bytearray()
253)                 while len(result) < self._length:
254)                     pos = seq.generate(len(required))
255)                     charset = required.pop(pos)
256)                     # Determine if an unlucky choice right now might
257)                     # violate the restriction on repeated characters.
258)                     # That is, check if the current partial passphrase
259)                     # ends with r - 1 copies of the same character
260)                     # (where r is the repeat limit that must not be
261)                     # reached), and if so, remove this same character
262)                     # from the current character's allowed set.

263)                     if self._repeat and result:
264)                         bad_suffix = bytes(result[-1:]) * (self._repeat - 1)
265)                         if result.endswith(bad_suffix):
266)                             charset = self._subtract(bytes(result[-1:]),
267)                                                      charset)

268)                     pos = seq.generate(len(charset))
269)                     result.extend(charset[pos:pos+1])

270)             except sequin.SequinExhaustedException:  # pragma: no cover

271)                 hash_length *= 2
272)             else:

273)                 return bytes(result)

274) 
275)     @classmethod
276)     def phrase_from_signature(
277)         cls, key: bytes | bytearray, /
278)     ) -> bytes | bytearray:
279)         """Obtain the master passphrase from a configured SSH key.
280) 
281)         vault allows the usage of certain SSH keys to derive a master
282)         passphrase, by signing the vault UUID with the SSH key.  The key
283)         type must ensure that signatures are deterministic.
284) 
285)         Args:
286)             key: The (public) SSH key to use for signing.
287) 
288)         Returns:
289)             The signature of the vault UUID under this key.
290) 
291)         Raises:
292)             ValueError:
293)                 The SSH key is principally unsuitable for this use case.
294)                 Usually this means that the signature is not
295)                 deterministic.
296) 

297)         Examples:
298)             >>> # Actual test public key.
299)             >>> public_key = bytes.fromhex('''
300)             ... 00 00 00 0b 73 73 68 2d 65 64 32 35 35 31 39
301)             ... 00 00 00 20
302)             ... 81 78 81 68 26 d6 02 48 5f 0f ff 32 48 6f e4 c1
303)             ... 30 89 dc 1c 6a 45 06 09 e9 09 0f fb c2 12 69 76
304)             ... ''')
305)             >>> expected_sig = bytes.fromhex('''
306)             ... 00 00 00 0b 73 73 68 2d 65 64 32 35 35 31 39
307)             ... 00 00 00 40
308)             ... f0 98 19 80 6c 1a 97 d5 26 03 6e cc e3 65 8f 86
309)             ... 66 07 13 19 13 09 21 33 33 f9 e4 36 53 1d af fd
310)             ... 0d 08 1f ec f8 73 9b 8c 5f 55 39 16 7c 53 54 2c
311)             ... 1e 52 bb 30 ed 7f 89 e2 2f 69 51 55 d8 9e a6 02
312)             ... ''')
313)             >>> Vault.phrase_from_signature(public_key) == expected_sig  # doctest:+SKIP
314)             True
315) 

316)         """
317)         deterministic_signature_types = {
318)             'ssh-ed25519':
319)                 lambda k: k.startswith(b'\x00\x00\x00\x0bssh-ed25519'),

320)             'ssh-ed448':
321)                 lambda k: k.startswith(b'\x00\x00\x00\x09ssh-ed448'),

322)             'ssh-rsa':
323)                 lambda k: k.startswith(b'\x00\x00\x00\x07ssh-rsa'),
324)         }
325)         if not any(v(key) for v in deterministic_signature_types.values()):
326)             raise ValueError(
327)                 'unsuitable SSH key: bad key, or signature not deterministic')
328)         with ssh_agent_client.SSHAgentClient() as client:
329)             ret = client.sign(key, cls._UUID)
330)         return ret
331) 

332)     @staticmethod

333)     def _subtract(

334)         charset: bytes | bytearray, allowed: bytes | bytearray,

335)     ) -> bytearray:
336)         """Remove the characters in charset from allowed.
337) 
338)         This preserves the relative order of characters in `allowed`.
339) 
340)         Args:

341)             charset:
342)                 Characters to remove.  Must not contain duplicate
343)                 characters.
344)             allowed:
345)                 Character set to remove the other characters from.  Must
346)                 not contain duplicate characters.

347) 
348)         Returns:

349)             The pruned "allowed" character set.

350) 
351)         Raises:

352)             ValueError:
353)                 `allowed` or `charset` contained duplicate characters.

354) 
355)         """
356)         allowed = (allowed if isinstance(allowed, bytearray)
357)                    else bytearray(allowed))
358)         assert_type(allowed, bytearray)

359)         if len(frozenset(allowed)) != len(allowed):
360)             raise ValueError('duplicate characters in set')

361)         if len(frozenset(charset)) != len(charset):
362)             raise ValueError('duplicate characters in set')
363)         for c in charset:
364)             try:
365)                 pos = allowed.index(c)

366)             except ValueError: