O pacote "debsums" é o que você deseja instalar para executar verificações de hash nos pacotes instalados.
Por exemplo, para verificar arquivos alterados:
sudo debsums -c
Observe que nem todos os pacotes são enviados com listas de arquivos md5sum. Você pode ver uma lista daqueles no seu sistema com:
sudo debsums -l