From: "Dmitry V. Levin" <ldv@altlinux.org>
To: devel@lists.altlinux.org
Subject: Re: [devel] hash collision in rpm
Date: Wed, 5 May 2021 16:10:04 +0300
Message-ID: <20210505131003.GB18368@altlinux.org> (raw)
In-Reply-To: <CA+qzen=zsq3au7q_6r4bpigQUeMFFy66jR3x6wo3N=cYNZaODQ@mail.gmail.com>
On Wed, May 05, 2021 at 08:40:27AM +0300, Alexey Tourbin wrote:
[...]
> By the way, there's a clever way to detect collisions at a higher
> level, even though low-level collisions are unavoidable, subject to
> implacable math. We can take advantage of the fact that the build
> system synchronizes package builds across a few architectures.
> Currently, if a missing symbol goes undetected due to a hash
> collision, it does so on all architectures simultaneously. To change
> that, we need to hash symbols differently, depending on the target
> architecture (we can pass seed=hash(arch) to the hash function, or use
> different initialization vectors IV=hash(arch)). The desired outcome
> is that when a missing symbol goes undetected, it does so, with an
> overwhelming probability, on only one target. Roughly speaking, if
> the probability of an undetected missing symbol is 10^-3 on a single
> target, it must be 10^-6 on two targets, 10^-9 on thee targets, etc.
This looks very promising indeed. I suppose the gain would justify
the necessary rebuilding of all packages with set-versions in their
arch-specific dependencies.
--
ldv
next prev parent reply other threads:[~2021-05-05 13:10 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-05-01 9:04 ` [devel] rust-1:1.50.0-alt1: Sisyphus/x86_64 test rebuild failed Alexey Gladkov
2021-05-04 10:32 ` [devel] hash collision in rpm Anton Farygin
2021-05-04 10:45 ` Alexey Gladkov
2021-05-04 12:50 ` Alexey Tourbin
2021-05-05 5:40 ` Alexey Tourbin
2021-05-05 13:10 ` Dmitry V. Levin [this message]
2021-05-05 14:11 ` Vladimir D. Seleznev
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=20210505131003.GB18368@altlinux.org \
--to=ldv@altlinux.org \
--cc=devel@lists.altlinux.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
ALT Linux Team development discussions
This inbox may be cloned and mirrored by anyone:
git clone --mirror http://lore.altlinux.org/devel/0 devel/git/0.git
# If you have public-inbox 1.1+ installed, you may
# initialize and index your mirror using the following commands:
public-inbox-init -V2 devel devel/ http://lore.altlinux.org/devel \
devel@altlinux.org devel@altlinux.ru devel@lists.altlinux.org devel@lists.altlinux.ru devel@linux.iplabs.ru mandrake-russian@linuxteam.iplabs.ru sisyphus@linuxteam.iplabs.ru
public-inbox-index devel
Example config snippet for mirrors.
Newsgroup available over NNTP:
nntp://lore.altlinux.org/org.altlinux.lists.devel
AGPL code for this site: git clone https://public-inbox.org/public-inbox.git