From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Kangas Newsgroups: gmane.emacs.bugs Subject: bug#58472: [PATCH] Make `message-unique-id' less prone to collisions Date: Wed, 12 Oct 2022 19:46:14 -0700 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="0000000000005b6ff705eae18353" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="19354"; mail-complaints-to="usenet@ciao.gmane.io" Cc: 58472@debbugs.gnu.org To: Paul Eggert Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Thu Oct 13 04:47:15 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oioFf-0004p8-LN for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 13 Oct 2022 04:47:15 +0200 Original-Received: from localhost ([::1]:45486 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oioFe-0000T1-Dk for geb-bug-gnu-emacs@m.gmane-mx.org; Wed, 12 Oct 2022 22:47:14 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:47708) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oioFS-0000Ss-Ue for bug-gnu-emacs@gnu.org; Wed, 12 Oct 2022 22:47:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:59643) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oioFS-0006AP-AB for bug-gnu-emacs@gnu.org; Wed, 12 Oct 2022 22:47:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oioFR-0003LC-UJ for bug-gnu-emacs@gnu.org; Wed, 12 Oct 2022 22:47:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Kangas Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 13 Oct 2022 02:47:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 58472 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 58472-submit@debbugs.gnu.org id=B58472.166562918412793 (code B ref 58472); Thu, 13 Oct 2022 02:47:01 +0000 Original-Received: (at 58472) by debbugs.gnu.org; 13 Oct 2022 02:46:24 +0000 Original-Received: from localhost ([127.0.0.1]:58721 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oioEp-0003KF-Mu for submit@debbugs.gnu.org; Wed, 12 Oct 2022 22:46:24 -0400 Original-Received: from mail-oi1-f174.google.com ([209.85.167.174]:36394) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oioEn-0003K3-Pw for 58472@debbugs.gnu.org; Wed, 12 Oct 2022 22:46:22 -0400 Original-Received: by mail-oi1-f174.google.com with SMTP id y72so452542oia.3 for <58472@debbugs.gnu.org>; Wed, 12 Oct 2022 19:46:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:mime-version:references:in-reply-to :from:from:to:cc:subject:date:message-id:reply-to; bh=1GYc8hh3U8rQAECxkqZcgoHbwXjYQyB9dS5ZvWpjREY=; b=NP3riUD3oAmmq6ElsBJjwEGe1YoVESJ0+fyJFEZk91tYL8zQMol4K8oKG7MI+9HBO2 XYsd7MkA+HssFuZNL2pf7Z9N0ZQMInajwyv9K31e/p69Yu2k1da4CfWv2fG2TpopKUHR H/lT1iZuOUPWrRfb5ha8pFXcImi9g0iD+7O5EDmlr3oO1164G/hOSASMdrKdIt1oD1cO XvyGBFW9nDnMo7kcOMRj75CWg0fPzXan3eyR8BAizy75zYE9/bbdIk7+eANVr0+UT1PB Mif4UfWmxi8vK+Ca8E0M9Na9lVFkx8M32wMenZdo6EUfGCj9ZxYWQcW1HJVW41yhvf3/ khKg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:mime-version:references:in-reply-to :from:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=1GYc8hh3U8rQAECxkqZcgoHbwXjYQyB9dS5ZvWpjREY=; b=SB1Uze+1TgdbFYJSVEjpNMWBOzWEUgutNDS7XTm7Jo6jOV3kUUUvN7AfMKb04tdTaf YawYt/OcocXjlYPAFQCdPaI2jcNV9/kKnEu8uzXG6iB7EA1/9lRXSBkO/IVfyBgVZ1/b 8V1cxgykbSuWcj6MfntjkIda0J40kbZIH4fMAipPpCHJNnc4qnmMNNPRvHdnxXoJmMVe quLQvWCQ1zY22xGxRlWxH3CODMbHgOOquUkecH6o+htk8O+gr1MNtxTHb8iXvSYYwydx V1cAfeLTP/5eS8sUhD+MuYtBOF4FU3AGzHj680nUTrhCaU2uvlU58HXtNXpCecBF7LFN HNYA== X-Gm-Message-State: ACrzQf3FYLszqHVudT/U+vfYZTHJ1T0EAAdZmOvPXuewbCovzGYo3n78 alghuhemNCgVHNGjr1BNOuOsLkayO1bSpY1Te2k= X-Google-Smtp-Source: AMsMyM6aebfjeUhTK8ppKDzVrzQDTWtjWIOB9OogTVUgOCebmf9KnCtY37v28lOjAbiZoTB+XWsc5mJpp9FNVcwpeag= X-Received: by 2002:a05:6808:d51:b0:354:fecd:6d11 with SMTP id w17-20020a0568080d5100b00354fecd6d11mr445231oik.92.1665629175886; Wed, 12 Oct 2022 19:46:15 -0700 (PDT) Original-Received: from 753933720722 named unknown by gmailapi.google.com with HTTPREST; Wed, 12 Oct 2022 19:46:14 -0700 In-Reply-To: X-Hashcash: 1:20:221013:58472@debbugs.gnu.org::qzd3Y88pU+1mkz7r:3O+G X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:245260 Archived-At: --0000000000005b6ff705eae18353 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Paul Eggert writes: > If the goal is to avoid collisions, though, wouldn't it be better to > avoid the time entirely? time is not very random in the high order bits. The main goal is to avoid collisions, but using the time also gives an idea of when the message was sent, which is kind of nice. Time also guarantees a somewhat unique value even if the user has happened to set the random seed. If we limit the length of the time string to 12 characters, and the total length to 25 characters (including the ".gnu" part), we still have a guaranteed 9 characters of random data, or 46 bits of entropy. =E2=8C=8Alog=E2=82=82 36=E2=81=B9=E2=8C=8B =3D 46 If we want to guarantee 62 bits of entropy, we could do a total length of 28 characters instead, but that might be overkill. > Also, the comment about ".fsf" and other newsreaders is wrong [...] > And if we're changing the algorithm perhaps we should change ".fsf" to > something else. Changing it to ".gnu" makes sense to me. > Something like this, perhaps, where you can choose LEN as you like: > > (concat > (let ((len 18)) > ;; Pass LEN, not -1, to message-number-base36 so that it never > ;; returns "" which would make the message-ID nonconforming. > (message-number-base36 (random (expt 36 len)) len)) > ;; Append ".gnu" to advertise that we're GNU Emacs. > ".gnu") I think making sure it is always the same length is a good idea. How about the attached? --0000000000005b6ff705eae18353 Content-Type: text/x-diff; charset="US-ASCII"; name="0001-Make-message-unique-id-less-prone-to-collisions.patch" Content-Disposition: attachment; filename="0001-Make-message-unique-id-less-prone-to-collisions.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: d98e873d8a45a9be_0.1 RnJvbSA4ODk2NjdlMzMyZmU3NmZjNjcwY2IxZDQ2MjBjNDc1MjVkOWE3MGJmIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBTdGVmYW4gS2FuZ2FzIDxzdGVmYW5rYW5nYXNAZ21haWwuY29t PgpEYXRlOiBXZWQsIDEyIE9jdCAyMDIyIDE3OjI5OjA0ICswMjAwClN1YmplY3Q6IFtQQVRDSF0g TWFrZSBgbWVzc2FnZS11bmlxdWUtaWQnIGxlc3MgcHJvbmUgdG8gY29sbGlzaW9ucwoKKiBsaXNw L2dudXMvbWVzc2FnZS5lbCAobWVzc2FnZS11bmlxdWUtaWQpOiBNYWtlIGxlc3MgcHJvbmUgdG8K Y29sbGlzaW9ucy4gIChCdWcjNTg0NzIpCihtZXNzYWdlLXVuaXF1ZS1pZC1jaGFyKTogTWFrZSB1 bnVzZWQgdmFyaWFibGUgb2Jzb2xldGUuCiogdGVzdC9saXNwL2dudXMvbWVzc2FnZS10ZXN0cy5l bCAobWVzc2FnZS11bmlxdWUtaWQtdGVzdCkKKG1lc3NhZ2UtbnVtYmVyLWJhc2UzNi10ZXN0KTog TmV3IHRlc3RzLgotLS0KIGxpc3AvZ251cy9tZXNzYWdlLmVsICAgICAgICAgICAgfCA0MyArKysr KysrKy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KIHRlc3QvbGlzcC9nbnVzL21lc3NhZ2UtdGVz dHMuZWwgfCAgOSArKysrKysrCiAyIGZpbGVzIGNoYW5nZWQsIDE5IGluc2VydGlvbnMoKyksIDMz IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL2xpc3AvZ251cy9tZXNzYWdlLmVsIGIvbGlzcC9n bnVzL21lc3NhZ2UuZWwKaW5kZXggNjdlYzA1MzFmYS4uOWI4NWYxYzVmZCAxMDA2NDQKLS0tIGEv bGlzcC9nbnVzL21lc3NhZ2UuZWwKKysrIGIvbGlzcC9nbnVzL21lc3NhZ2UuZWwKQEAgLTQ3LDcg KzQ3LDcgQEAKIChyZXF1aXJlICdyZmMyMDQ3KQogKHJlcXVpcmUgJ3B1bnkpCiAocmVxdWlyZSAn cm1jKSAgICAgICAgICAgICAgICAgICAgICAgICAgOyByZWFkLW11bHRpcGxlLWNob2ljZQotKHJl cXVpcmUgJ3N1YnIteCkKKyhyZXF1aXJlICdzdWJyLXgpICAgICAgICAgICAgICAgICAgICAgICA7 IHN0cmluZy1saW1pdAogKHJlcXVpcmUgJ3lhbmstbWVkaWEpCiAocmVxdWlyZSAnbWFpbGNhcCkK IChyZXF1aXJlICdzZW5kbWFpbCkKQEAgLTU4ODksNDEgKzU4ODksMTggQEAgbWVzc2FnZS1tYWtl LW1lc3NhZ2UtaWQKIAkJIl8tXyIgIiIpKQogCSAgIkAiIChtZXNzYWdlLW1ha2UtZnFkbikgIj4i KSkKIAorKG1ha2Utb2Jzb2xldGUtdmFyaWFibGUgJ21lc3NhZ2UtdW5pcXVlLWlkLWNoYXIgbmls ICIyOS4xIikKIChkZWZ2YXIgbWVzc2FnZS11bmlxdWUtaWQtY2hhciBuaWwpCiAKLTs7IElmIHlv dSBldmVyIGNoYW5nZSB0aGlzIGZ1bmN0aW9uLCBtYWtlIHN1cmUgdGhlIG5ldyB2ZXJzaW9uCi07 OyBjYW5ub3QgZ2VuZXJhdGUgSURzIHRoYXQgdGhlIG9sZCB2ZXJzaW9uIGNvdWxkLgotOzsgWW91 IG1pZ2h0IGZvciBleGFtcGxlIGluc2VydCBhICIuIiBzb21ld2hlcmUgKG5vdCBuZXh0IHRvIGFu b3RoZXIgZG90Ci07OyBvciBzdHJpbmcgYm91bmRhcnkpLCBvciBtb2RpZnkgdGhlICJmc2YiIHN0 cmluZy4KIChkZWZ1biBtZXNzYWdlLXVuaXF1ZS1pZCAoKQotICA7OyBEb24ndCB1c2UgZnJhY3Rp b25hbCBzZWNvbmRzIGZyb20gdGltZXN0YW1wOyB0aGV5IG1heSBiZSB1bnN1cHBvcnRlZC4KLSAg OzsgSW5zdGVhZCB3ZSB1c2UgdGhpcyByYW5kb21seSBpbml0ZWQgY291bnRlci4KLSAgKHNldHEg bWVzc2FnZS11bmlxdWUtaWQtY2hhcgotCTs7IDJeMTYgKiAyNSBqdXN0IGZpdHMgaW50byA0IGRp Z2l0cyBpIGJhc2UgMzYuCi0JKGxldCAoKGJhc2UgKCogMjUgMjUpKSkKLQkgIChpZiBtZXNzYWdl LXVuaXF1ZS1pZC1jaGFyCi0JICAgICAgKCUgKDErIG1lc3NhZ2UtdW5pcXVlLWlkLWNoYXIpIGJh c2UpCi0JICAgIChyYW5kb20gYmFzZSkpKSkKLSAgKGxldCAoKHRtICh0aW1lLWNvbnZlcnQgbmls ICdpbnRlZ2VyKSkpCisgIChsZXQqICgodGltZSAoY2FyICh0aW1lLWNvbnZlcnQgbmlsIHQpKSkK KyAgICAgICAgICh0aW1lLXN0cmluZyAoc3RyaW5nLWxpbWl0IChtZXNzYWdlLW51bWJlci1iYXNl MzYgdGltZSAtMSkgMTIpKQorICAgICAgICAgKGxlbiAoLSAyMSAobGVuZ3RoIHRpbWUtc3RyaW5n KSkpKQogICAgIChjb25jYXQKLSAgICAgKGlmIChvciAoZXEgc3lzdGVtLXR5cGUgJ21zLWRvcykK LQkgICAgIDs7IG1lc3NhZ2UtbnVtYmVyLWJhc2UzNiBkb2Vzbid0IGhhbmRsZSBiaWdpbnRzLgot CSAgICAgKGZsb2F0cCAodXNlci11aWQpKSkKLQkgKGxldCAoKHVzZXIgKGRvd25jYXNlICh1c2Vy LWxvZ2luLW5hbWUpKSkpCi0JICAgKHdoaWxlIChzdHJpbmctbWF0Y2ggIlteYS16MC05X10iIHVz ZXIpCi0JICAgICAoYXNldCB1c2VyIChtYXRjaC1iZWdpbm5pbmcgMCkgP18pKQotCSAgIHVzZXIp Ci0gICAgICAgKG1lc3NhZ2UtbnVtYmVyLWJhc2UzNiAodXNlci11aWQpIC0xKSkKLSAgICAgKG1l c3NhZ2UtbnVtYmVyLWJhc2UzNiAoKyAoYXNoIHRtIC0xNikKLQkJCSAgICAgICAoYXNoICglIG1l c3NhZ2UtdW5pcXVlLWlkLWNoYXIgMjUpIDE2KSkKLQkJCSAgICA0KQotICAgICAobWVzc2FnZS1u dW1iZXItYmFzZTM2ICgrIChsb2dhbmQgdG0gI3hmZmZmKQotCQkJICAgICAgIChhc2ggKC8gbWVz c2FnZS11bmlxdWUtaWQtY2hhciAyNSkgMTYpKQotCQkJICAgIDQpCi0gICAgIDs7IEFwcGVuZCBh IGdpdmVuIG5hbWUsIGJlY2F1c2Ugd2hpbGUgdGhlIGdlbmVyYXRlZCBJRCBpcyB1bmlxdWUKLSAg ICAgOzsgdG8gdGhpcyBuZXdzcmVhZGVyLCBvdGhlciBuZXdzcmVhZGVycyBtaWdodCBvdGhlcndp c2UgZ2VuZXJhdGUKLSAgICAgOzsgdGhlIHNhbWUgSUQgdmlhIGFub3RoZXIgYWxnb3JpdGhtLgot ICAgICAiLmZzZiIpKSkKKyAgICAgdGltZS1zdHJpbmcKKyAgICAgKG1lc3NhZ2UtbnVtYmVyLWJh c2UzNiAocmFuZG9tIChleHB0IDM2IGxlbikpIGxlbikKKyAgICAgOzsgQXBwZW5kICIuZ251IiB0 byBhZHZlcnRpc2UgdGhhdCB3ZSdyZSBHTlUgRW1hY3MuCisgICAgICIuZ251IikpKQogCiAoZGVm dW4gbWVzc2FnZS1udW1iZXItYmFzZTM2IChudW0gbGVuKQogICAoaWYgKGlmICg8IGxlbiAwKQpA QCAtNTkzMSw3ICs1OTA4LDcgQEAgbWVzc2FnZS1udW1iZXItYmFzZTM2CiAJKD0gbGVuIDApKQog ICAgICAgIiIKICAgICAoY29uY2F0IChtZXNzYWdlLW51bWJlci1iYXNlMzYgKC8gbnVtIDM2KSAo MS0gbGVuKSkKLQkgICAgKGNoYXItdG8tc3RyaW5nIChhcmVmICJ6eXh3dnV0c3JxcG9ubWxramlo Z2ZlZGNiYTk4NzY1NDMyMTAiCisgICAgICAgICAgICAoY2hhci10by1zdHJpbmcgKGFyZWYgIjAx MjM0NTY3ODlhYmNkZWZnaGlqa2xtbm9wcXJzdHV2d3h5eiIKIAkJCQkgICglIG51bSAzNikpKSkp KQogCiAoZGVmdW4gbWVzc2FnZS1tYWtlLW9yZ2FuaXphdGlvbiAoKQpkaWZmIC0tZ2l0IGEvdGVz dC9saXNwL2dudXMvbWVzc2FnZS10ZXN0cy5lbCBiL3Rlc3QvbGlzcC9nbnVzL21lc3NhZ2UtdGVz dHMuZWwKaW5kZXggYTcyNDQyOGVjYi4uZThjMDY1NTU0MyAxMDA2NDQKLS0tIGEvdGVzdC9saXNw L2dudXMvbWVzc2FnZS10ZXN0cy5lbAorKysgYi90ZXN0L2xpc3AvZ251cy9tZXNzYWdlLXRlc3Rz LmVsCkBAIC0zMSw2ICszMSwxNSBAQAogCiAocmVxdWlyZSAnY2wtbGliKQogCisoZXJ0LWRlZnRl c3QgbWVzc2FnZS11bmlxdWUtaWQtdGVzdCAoKQorICAoc2hvdWxkIChzdHJpbmdwIChtZXNzYWdl LXVuaXF1ZS1pZCkpKQorICAoc2hvdWxkICg9IChsZW5ndGggKG1lc3NhZ2UtdW5pcXVlLWlkKSkg MjUpKSkKKworKGVydC1kZWZ0ZXN0IG1lc3NhZ2UtbnVtYmVyLWJhc2UzNi10ZXN0ICgpCisgIChz aG91bGQgKGVxdWFsIChtZXNzYWdlLW51bWJlci1iYXNlMzYgMTAgLTEpICJhIikpCisgIChzaG91 bGQgKGVxdWFsIChtZXNzYWdlLW51bWJlci1iYXNlMzYgMSAtMSkgIjEiKSkKKyAgKHNob3VsZCAo ZXF1YWwgKG1lc3NhZ2UtbnVtYmVyLWJhc2UzNiAoZXhwdCAzNiA1KSAtMSkgIjEwMDAwMCIpKSkK KwogKGVydC1kZWZ0ZXN0IG1lc3NhZ2UtbW9kZS1wcm9wZXJ0aXplICgpCiAgICh3aXRoLXRlbXAt YnVmZmVyCiAgICAgKHVud2luZC1wcm90ZWN0Ci0tIAoyLjM1LjEKCg== --0000000000005b6ff705eae18353--