From: Stefan Kangas <stefankangas@gmail.com>
To: Paul Eggert <eggert@cs.ucla.edu>, Matt Armstrong <matt@rfc20.org>
Cc: 58472@debbugs.gnu.org
Subject: bug#58472: [PATCH] Make `message-unique-id' less prone to collisions
Date: Mon, 17 Oct 2022 08:14:03 +0000 [thread overview]
Message-ID: <CADwFkm=DHt_AtwHrqBUvdFQP420SzvmM4bj8Mgdn5Cy+e3jC8g@mail.gmail.com> (raw)
In-Reply-To: <cf192c87-5a72-9da1-759b-f9d3053d0d38@cs.ucla.edu>
[-- Attachment #1: Type: text/plain, Size: 1680 bytes --]
Paul Eggert <eggert@cs.ucla.edu> writes:
> I've been looking into this and have several patches along these lines.
> None of them address message-unique-id directly yet (I plan to tackle
> this soon) but they do address the general problem area. The basic idea
> is to use a new make-nonce primitive.
Thanks! I have read your patchset, which looks good to me.
I have also attached my latest patch for `message-unique-id', but I'm
not married to it if you have something better in mind. It could easily
be updated to use `make-nonce' though.
> (defun math-init-random-base ()
[...snip...]
> + (declare (obsolete nil "29.1")))
This is a nit, but perhaps this could be simplified to:
(declare-obsolete-function-alias 'math-init-random-base
#'ignore "29.1)
> diff --git a/src/sysdep.c b/src/sysdep.c
> index 4786c8fa4f..5117460fc0 100644
> --- a/src/sysdep.c
> +++ b/src/sysdep.c
> @@ -2159,6 +2159,22 @@ seed_random (void *seed, ptrdiff_t seed_size)
> set_random_seed (arg);
> }
>
> +/* Set BUF, of size BUFSIZE, to random data derived from system entropy. */
> +
> +void
> +get_entropy (void *buf, ptrdiff_t bufsize)
> +{
> + char *p = buf, *lim = p + bufsize;
> + while (p < lim)
> + {
> + ssize_t gotten = getrandom (p, lim - p, 0);
> + if (0 <= gotten)
> + p += gotten;
> + else if (errno != EINTR)
> + report_file_error ("Getting random data", Qnil);
> + }
> +}
If we claim that the random data is suitable for cryptographic purposes,
should we be using the GRND_RANDOM flag here?
On Linux, flags 0 and GRND_RANDOM are equivalent (I read the most recent
kernel code to verify this). But I have no idea about other platforms.
[-- Attachment #2: 0001-Make-message-unique-id-less-prone-to-collisions.patch --]
[-- Type: text/x-diff, Size: 5465 bytes --]
From 811c7e70b55e7aeace792ffbf19203ef36f30bd2 Mon Sep 17 00:00:00 2001
From: Stefan Kangas <stefankangas@gmail.com>
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. (Bug#58472)
(message-number-base36): Make obsolete in favor of...
(message--number-base62): ...this new function.
(message-unique-id-char): Make unused variable obsolete.
* test/lisp/gnus/message-tests.el (message-unique-id-test)
(message-number-base62-test): New tests.
---
lisp/gnus/message.el | 79 ++++++++++++++++-----------------
test/lisp/gnus/message-tests.el | 10 +++++
2 files changed, 49 insertions(+), 40 deletions(-)
diff --git a/lisp/gnus/message.el b/lisp/gnus/message.el
index a714e31876..1590a8b289 100644
--- a/lisp/gnus/message.el
+++ b/lisp/gnus/message.el
@@ -5886,50 +5886,36 @@ message-make-message-id
"_-_" ""))
"@" (message-make-fqdn) ">"))
-(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)))
+ "Return a generated string suitable for using as a unique Message-ID."
+ (let ((random-num
+ (seq-reduce (lambda (a i) (+ (ash a 8) i))
+ (secure-hash 'md5 'iv-auto 128 nil t) 0)))
+ ;; Use the PRNG to set an extra couple of bits, to avoid having
+ ;; every Message-Id start with "A-F".
+ (setq random-num (logior random-num (ash (random 16) 128)))
(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")))
-
-(defun message-number-base36 (num len)
+ ;; We used to base this on time, euid, etc., but now just use 128
+ ;; bits of random data. The main requirements are that collisions
+ ;; are unlikely, and that the alphabet is limited. Note that the
+ ;; random data will be securely generated by getrandom() in Gnulib.
+ (message--number-base62 random-num 22)
+ ;; Append ".gnu" to advertise that we're GNU Emacs.
+ ".gnu")))
+
+(defun message--number-base62 (num len)
+ "Return a string similar to Base64, but include only alpha-numerics.
+NUM is the number to convert.
+LEN is the length of the string (or -1 for no limit)."
(if (if (< len 0)
- (<= num 0)
- (= len 0))
+ (<= num 0)
+ (= len 0))
""
- (concat (message-number-base36 (/ num 36) (1- len))
- (char-to-string (aref "zyxwvutsrqponmlkjihgfedcba9876543210"
- (% num 36))))))
+ (concat (message--number-base62 (/ num 62) (1- len))
+ (char-to-string (aref (concat "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+ "abcdefghijklmnopqrstuvwxyz"
+ "0123456789")
+ (% num 62))))))
(defun message-make-organization ()
"Make an Organization header."
@@ -8998,6 +8984,19 @@ message-mailto-1
(message-goto-body)
(message-goto-subject))))
+(make-obsolete-variable 'message-unique-id-char nil "29.1")
+(defvar message-unique-id-char nil)
+
+(defun message-number-base36 (num len)
+ (declare (obsolete message--number-base62 "29.1"))
+ (if (if (< len 0)
+ (<= num 0)
+ (= len 0))
+ ""
+ (concat (message-number-base36 (/ num 36) (1- len))
+ (char-to-string (aref "0123456789abcdefghijklmnopqrstuvwxyz"
+ (% num 36))))))
+
(provide 'message)
(make-obsolete-variable 'message-load-hook
diff --git a/test/lisp/gnus/message-tests.el b/test/lisp/gnus/message-tests.el
index a724428ecb..851e07b7ae 100644
--- a/test/lisp/gnus/message-tests.el
+++ b/test/lisp/gnus/message-tests.el
@@ -31,6 +31,16 @@
(require 'cl-lib)
+(ert-deftest message-unique-id-test ()
+ (should (stringp (message-unique-id)))
+ (should (= (length (message-unique-id)) 26))
+ (should (string-match (rx ".gnu" eos) (message-unique-id))))
+
+(ert-deftest message--number-base62-test ()
+ (should (equal (message--number-base62 10 -1) "K"))
+ (should (equal (message--number-base62 1 2) "AB"))
+ (should (equal (message--number-base62 (expt 62 5) -1) "BAAAAA")))
+
(ert-deftest message-mode-propertize ()
(with-temp-buffer
(unwind-protect
--
2.35.1
next prev parent reply other threads:[~2022-10-17 8:14 UTC|newest]
Thread overview: 32+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-10-12 16:07 bug#58472: [PATCH] Make `message-unique-id' less prone to collisions Stefan Kangas
2022-10-12 18:08 ` Paul Eggert
2022-10-13 2:46 ` Stefan Kangas
2022-10-13 4:53 ` Matt Armstrong
2022-10-13 12:10 ` Stefan Kangas
2022-10-13 16:35 ` Matt Armstrong
2022-10-13 16:38 ` Paul Eggert
2022-10-14 9:22 ` Stefan Kangas
2022-10-13 16:21 ` Paul Eggert
2022-10-14 9:22 ` Stefan Kangas
2022-10-16 7:32 ` Stefan Kangas
2022-10-16 17:05 ` Stefan Kangas
2022-10-16 15:19 ` Matt Armstrong
2022-10-16 16:49 ` Stefan Kangas
2022-10-17 6:17 ` Matt Armstrong
2022-10-17 7:30 ` Paul Eggert
2022-10-17 8:14 ` Stefan Kangas [this message]
2022-10-17 8:23 ` Eli Zaretskii
2022-10-17 18:47 ` Matt Armstrong
2022-10-17 8:16 ` Eli Zaretskii
2022-10-17 8:29 ` Lars Ingebrigtsen
2022-10-17 8:34 ` Eli Zaretskii
2022-10-17 9:30 ` Stefan Kangas
2022-10-17 11:22 ` Lars Ingebrigtsen
2022-10-17 15:40 ` Stefan Kangas
2022-11-25 1:26 ` Stefan Kangas
2022-10-17 18:40 ` Matt Armstrong
2022-10-18 1:38 ` Paul Eggert
2022-10-18 14:05 ` Eli Zaretskii
2022-10-13 11:45 ` Lars Ingebrigtsen
2022-10-13 12:10 ` Stefan Kangas
2022-10-13 19:15 ` Lars Ingebrigtsen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CADwFkm=DHt_AtwHrqBUvdFQP420SzvmM4bj8Mgdn5Cy+e3jC8g@mail.gmail.com' \
--to=stefankangas@gmail.com \
--cc=58472@debbugs.gnu.org \
--cc=eggert@cs.ucla.edu \
--cc=matt@rfc20.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.