Subject: bug#58472: closed (Re: bug#58472: [PATCH] Make `message-unique-id' less prone to collisions)

From: [email-masked] (GNU bug Tracking System)
Date: Fri, 25 Nov 2022 01:27:02 +0000

Your bug report

#58472: [PATCH] Make `message-unique-id' less prone to collisions

which was filed against the emacs package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
58472: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=58472
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#58472: [PATCH] Make `message-unique-id' less prone to collisions
From: Stefan Kangas <[email-masked]>
To: Lars Ingebrigtsen <[email-masked]>
Cc: [email-masked], Eli Zaretskii <[email-masked]>, Paul Eggert <[email-masked]>, [email-masked]
Date: Thu, 24 Nov 2022 17:26:31 -0800
List-Id: <debbugs-submit.debbugs.gnu.org>

I'm guessing that none of this is happening, so I'm closing this bug
report.

Subject: [PATCH] Make `message-unique-id' less prone to collisions
From: Stefan Kangas <[email-masked]>
To: [email-masked]
Date: Wed, 12 Oct 2022 09:07:53 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

This is a proposal to make `message-unique-id' less prone to collisions.

For the first 1-2 characters, it uses the return value `user-uid', which
on most single-user systems is a fixed value (for example, this gives us
"87" on almost any single-user Debian machine).[1]  It's also
unnecessarily leaky of potentially privacy sensitive information.

The next 8 characters are the current time, with some gymnastics to
emulate support for a fractional part to seconds.  This seems
unnecessary now that, AFAIU, `time-convert' can do that for us portably
(please correct me if I'm wrong, Paul).

I suggest that we instead base the left-hand side of the Message-ID on:

  1. (time-convert nil (expt 10 9))
  2. 2^N bits of pseudo random data (e.g. N=32)

We can then ignore the effective user id, while significantly decreasing
the risk of a Message-ID collision.[2]

Currently, we get values like:

    (message-unique-id)
    => "87o7uhi3at.fsf"            ; length 10

With the attached patch, we have instead:

    (message-unique-id)
    => "cnk29wgg1a4nvrpqcy.fsf"   ; length ~22

Note also that `message-number-base36' uses a Caesar cipher for some
reason:

    (message-number-base36 5 -1)
    => "u"    ; expect "5"
    (message-number-base36 (expt 36 3) -1)
    => "yzzz" ; expect "1000"

The patch fixes this also.

I don't know if this change should be in NEWS or not.

Footnotes:
[1]  Just for fun, you can search for 87 on
     https://en.wikipedia.org/wiki/Message-ID

[2]  See also: https://www.jwz.org/doc/mid.html
From 5eedf88bb85e5b4a8a1bb556d856324aa9333042 Mon Sep 17 00:00:00 2001
From: Stefan Kangas <[email-masked]>
Date: Wed, 12 Oct 2022 17:29:04 +0200
Subject: [PATCH] Make `message-unique-id' less prone to collisions

* lisp/gnus/message.el (message-unique-id): Make less prone to
collisions.
(message-unique-id-char): Make unused variable obsolete.
* test/lisp/gnus/message-tests.el (message-unique-id-test)
(message-number-base36-test): New tests.
---
 lisp/gnus/message.el            | 42 +++++++--------------------------
 test/lisp/gnus/message-tests.el |  9 +++++++
 2 files changed, 18 insertions(+), 33 deletions(-)

diff --git a/lisp/gnus/message.el b/lisp/gnus/message.el
index 67ec0531fa..bdc9a5b2ad 100644
--- a/lisp/gnus/message.el
+++ b/lisp/gnus/message.el
@@ -5889,41 +5889,17 @@ message-make-message-id
 		"_-_" ""))
 	  "@" (message-make-fqdn) ">"))
 
+(make-obsolete-variable 'message-unique-id-char nil "29.1")
 (defvar message-unique-id-char nil)
 
-;; If you ever change this function, make sure the new version
-;; cannot generate IDs that the old version could.
-;; You might for example insert a "." somewhere (not next to another dot
-;; or string boundary), or modify the "fsf" string.
 (defun message-unique-id ()
-  ;; Don't use fractional seconds from timestamp; they may be unsupported.
-  ;; Instead we use this randomly inited counter.
-  (setq message-unique-id-char
-	;; 2^16 * 25 just fits into 4 digits i base 36.
-	(let ((base (* 25 25)))
-	  (if message-unique-id-char
-	      (% (1+ message-unique-id-char) base)
-	    (random base))))
-  (let ((tm (time-convert nil 'integer)))
-    (concat
-     (if (or (eq system-type 'ms-dos)
-	     ;; message-number-base36 doesn't handle bigints.
-	     (floatp (user-uid)))
-	 (let ((user (downcase (user-login-name))))
-	   (while (string-match "[^a-z0-9_]" user)
-	     (aset user (match-beginning 0) ?_))
-	   user)
-       (message-number-base36 (user-uid) -1))
-     (message-number-base36 (+ (ash tm -16)
-			       (ash (% message-unique-id-char 25) 16))
-			    4)
-     (message-number-base36 (+ (logand tm #xffff)
-			       (ash (/ message-unique-id-char 25) 16))
-			    4)
-     ;; Append a given name, because while the generated ID is unique
-     ;; to this newsreader, other newsreaders might otherwise generate
-     ;; the same ID via another algorithm.
-     ".fsf")))
+  (concat
+   (message-number-base36 (car (time-convert nil (expt 10 9))) -1)
+   (message-number-base36 (random (expt 2 32)) -1)
+   ;; Append a given name, because while the generated ID is unique
+   ;; to this newsreader, other newsreaders might otherwise generate
+   ;; the same ID via another algorithm.
+   ".fsf"))
 
 (defun message-number-base36 (num len)
   (if (if (< len 0)
@@ -5931,7 +5907,7 @@ message-number-base36
 	(= len 0))
       ""
     (concat (message-number-base36 (/ num 36) (1- len))
-	    (char-to-string (aref "zyxwvutsrqponmlkjihgfedcba9876543210"
+            (char-to-string (aref "0123456789abcdefghijklmnopqrstuvwxyz"
 				  (% num 36))))))
 
 (defun message-make-organization ()
diff --git a/test/lisp/gnus/message-tests.el b/test/lisp/gnus/message-tests.el
index a724428ecb..e43fb1c1c4 100644
--- a/test/lisp/gnus/message-tests.el
+++ b/test/lisp/gnus/message-tests.el
@@ -31,6 +31,15 @@
 
 (require 'cl-lib)
 
+(ert-deftest message-unique-id-test ()
+  (should (stringp (message-unique-id)))
+  (should (< 10 (length (message-unique-id)))))
+
+(ert-deftest message-number-base36-test ()
+  (should (equal (message-number-base36 10 -1) "a"))
+  (should (equal (message-number-base36 1 -1) "1"))
+  (should (equal (message-number-base36 (expt 36 5) -1) "100000")))
+
 (ert-deftest message-mode-propertize ()
   (with-temp-buffer
     (unwind-protect
-- 
2.35.1