Debian – Check all debian binaries against the checksum of the original

Well, the base package list (assuming this is a desktop system) is built by the combination of the ubuntu-minimal and ubuntu-desktop packages. These are metapackages that exist solely to depend on other packages. The problem, of course, is that their dependency list is not the complete package list. The packages they depend on may have other dependencies.

So... I would suggest playing around in aptitude. Perhaps try flagging all installed packages for removal, then specifically selecting your active kernel, ubuntu-minimal, and ubuntu-desktop to be installed. With a little finagling, you should be able to reach a point where the only packages flagged to be removed are the ones not required by the two metapackages.

I haven't tried this. I haven't even experimented with it. You may hose your system by following my suggestions.

Have fun!

I just used the command "yum provides /path/binary" on a 64bit CentOS box I have here and all of those binaries are part of the util-linux package. Which is listed in your recent updates.