GNU bug report logs - #58472
[PATCH] Make `message-unique-id' less prone to collisions

Previous Next

Full log

View this message in rfc822 format

From: Stefan Kangas <stefankangas <at> gmail.com>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 58472 <at> debbugs.gnu.org, Matt Armstrong <matt <at> rfc20.org>
Subject: bug#58472: [PATCH] Make `message-unique-id' less prone to collisions
Date: Sun, 16 Oct 2022 00:32:58 -0700

Stefan Kangas <stefankangas <at> gmail.com> writes:

>> If that's a concern, we should be using more-random data, e.g., with
>>
>>     (base64-encode-string
>>      (secure-hash 'md5 'iv-auto 128 nil t))
>>
>> if we want 128 bits of randomness (this yields a string like
>> "B8a3usyu5QSE/rTLu0nIHg==").
>
> Sounds good to me, but:

Looking at the implementation of `secure-hash', doesn't this run the
random number through the MD5 function?  I guess that will reduce
entropy, as AFAIU hash functions like MD5 are not really bijective
functions f: ℕ → ℕ.  (In other words, it does not give you a permutation
of the set of all natural numbers.)

I don't think it matters for generating a Message-ID, but I thought it
was worth pointing out.  So if I'm right, you might not want to use this
particular method for generating cryptographic keys, if anyone happens
to be doing stuff like that in ELisp.

In any case, I do think we should add an easy way of directly accessing
the getrandom(2) syscall [or equivalent].

>> As an aside, it's weird that there's no easy way to ask Emacs for an
>> N-bit random integer, where the randomness is taken from system entropy.
>> Shouldn't we extend Emacs to support that? E.g., (make-string 128
>> 'iv-auto) could give you an N-byte entropy-derived random string, or
>> (random -N) could give you an N-bit entropy-derived random nonnegative
>> integer, or something like that. Then we could write something like this:
>>
>>    (base64-encode-string (make-string 16 'iv-auto))
>>
>> to get a Message-ID component with 16 bytes (128 bits) of entropy.
>
> Yes, we should find a better interface here.

How about `secure-random' (named in analogy with `secure-hash')?

    (secure-random 8)
    => <8 byte number>

This is the same interface as the Linux getrandom(2) system call, and
the portable function in Gnulib, so it's easy enough to implement.

BTW, we currently call getrandom with flags 0 in
extract_data_from_object.  Should we consider using GRND_RANDOM?  The
Linux kernel uses the same code path for /dev/random and /dev/urandom
these days, IIUC, so maybe it doesn't matter.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.