Re: dpkg MD5

[Jeffrey Walton <noloader@gmail.com>]

On Thu, Nov 7, 2024 at 7:22 PM Jeremy Stanley <fungi@yuggoth.org> wrote:
>
> On 2024-11-07 16:45:54 -0500 (-0500), David Campbell wrote:
> [...]
> > dpkg currently uses MD5 to verify packages, but MD5 is considered
> > insecure, why not switch to SHA256 (and also update lintian)?
> [...]
>
> MD5 is considered insecure to collision attacks, but mounting one
> would require that the creator of the original file intentionally
> pick content that can hash to the same value as some malicious
> content (and even that is nontrivial, but let's set that aside for
> the moment).
>
> https://en.wikipedia.org/wiki/Collision_attack

I think Marc Stevens' work on Chosen-Prefix Collisions is of interest.
MD5 is currently around 2^39, which is well within reach of
adversaries.

>From <https://marc-stevens.nl/research/papers/StLdW%20-%20Chosen-Prefix%20Collisions%20for%20MD5%20and%20Applications.pdf>:

   We present a novel, automated way to find differential paths
   for MD5. As an application we have shown how, at an approximate
   expected cost of 2^39 calls to the MD5 compression function, for any
   two chosen message prefixes P and P' suffixes S and S' can be con-
   structed such that the concatenated values P||S and P'||S' collide under
   MD5. The practical attack potential of this construction of chosen-prefix
   collisions is of greater concern than the MD5-collisions that were pub-
   lished before. This is illustrated by a pair of MD5-based X.509 certifi-
   cates one of which was signed by a commercial Certification Authority
   (CA) as a legitimate website certificate, while the other one is a cer-
   tificate for a rogue CA that is entirely under our control (cf. http://
   www.win.tue.nl/hashclash/rogue-ca/). Other examples, such as MD5-
   colliding executables, are presented as well. More details can be found
   on http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/

(Marc is also the author of HashClash, <https://marc-stevens.nl/p/hashclash/>).

> What you're probably worried about is preimage resistance of the
> algorithm (and in particular, second preimage resistance, which is
> what keeps some random attacker from creating a file which hashes to
> the same value as a known good file).
>
> https://en.wikipedia.org/wiki/Preimage_attack
>
> MD5's preimage resistance is not in question presently, that I've
> heard, and it would be pretty big news in the cryptography community
> if it were.
>
> > Please, include my email address in the CC if you respond to this
> > message. I am not subscribed to the mailing list.
> [...]
>
> Sorry, GMail doesn't accept messages from my mailserver, and I'm not
> going to bother jumping through hoops just to appease them. Anyone
> who's interested in Debian security matters should subscribe to the
> mailing list or read its archives in a Web browser at the very
> least.

Jeff