Foi um pouco difícil, mas eu achei olhando a man page:
Fornecido por: libb2-dev_0.97-2_i386
Mas você provavelmente não quer o pacote -dev, então procurar por libb2 me levou
então
sudo apt install libb2-1 #I assume, could be libb2
Se você não está executando zesty, eu recomendo que você compile a partir da fonte:
Veja o link
ATUALIZAÇÃO: Depois de mais pesquisas ...
O blake2 foi incorporado ao coreutils, consulte o link
Então o b2sum faz parte do coreutils
De FEDORA
bodhi@daemon:~$which b2sum
/usr/bin/b2sum
bodhi@daemon:~$dnf provides /usr/bin/b2sum
coreutils-single-8.27-5.fc26.x86_64 : coreutils multicall binary
Repo : fedora
Matched from:
Filename : /usr/bin/b2sum
Depois de pesquisar mais pacotes do Ubuntu:
b2sum está disponível em coreutils começando em zesty (17.04) mas não em xenial.