bug#44944: Unable to log into X session via gdm

[Maxime Devos]

On 16-09-2022 21:00, Maxim Cournoyer wrote:
> That'd be cool, but how would you implement such a hash, that returns
> something fixed between 0 and 1024?  That doesn't sound feasible,
> although I'm no hash function expert.

Remember that any function from X to a finite set Y is a hash function 
-- this included very simple ones like e.g. X={1,...,N}, Y={1,...,N}, 
map every number \(k\) to \(k\).

You can't implement such a hash without hash collisions, due to the 
pigeonhole principle, as there are more inputs (user names) that outputs 
(numbers between 0 and 1024).

Users can't share uids, so hash collisions are unacceptable.
As collisions are unacceptable (and not just tolerable but disliked), 
the 'uniformity' property of some hash functions is unneeded.

If we limit ourselves to only having 1025 users in total, then with some 
care there aren't any hash collisions (see proposal by bokr) (*), but 
that would place a limit on how many services can be written for Guix.

Of course, an individual system might only have < 1025 users as not all 
services are enabled, but then the hash function would depend on the 
system in question.  However, Guix cannot tell in advance what usernames 
will be used in the future, so it would need to gradually build up its 
hash function (state!) and remember old 'deleted' users (state!).

But if you have to remember the old users anyway and gradually build up 
a hash function, then you might as well simplify things by not going for 
a classically "good" hash function but rather a simple table that is 
gradually build up (technically a hash function), as I've tried out in 
<https://issues.guix.gnu.org/36508#21> (currently limited to uids, gid 
not yet supported, also largely untested).

(*) Implementation:

(define (hash username)
  (define %table
    `(("root" . 0)
      ("foo" . 1)
      ("bar" . 2)
      ; <insert entries for all other (system) usernames in Guix here>
      [...]))
  (or (assoc-ref %table username)
      (error "doesn't exist")))

Greetings,
Maxime.

OpenPGP_0x49E3EE22191725EE.asc
Description: OpenPGP public key

OpenPGP_signature
Description: OpenPGP digital signature