O mesmo problema no Ubuntu 16.04
$ apt-cache policy libssl1.0.0
libssl1.0.0:
Installed: 1.0.2g-1ubuntu4.5
Candidate: 1.0.2g-1ubuntu4.5
Version table:
*** 1.0.2g-1ubuntu4.5 100
100 /var/lib/dpkg/status
1.0.2g-1ubuntu4.1 500
500 http://mirror.uoregon.edu/ubuntu xenial-updates/main amd64 Packages
500 http://mirror.uoregon.edu/ubuntu xenial-security/main amd64 Packages
1.0.2g-1ubuntu4 500
500 http://mirror.uoregon.edu/ubuntu xenial/main amd64 Packages
$ apt-cache policy libssl-dev
libssl-dev:
Installed: (none)
Candidate: 1.0.2g-1ubuntu4.1
Version table:
1.0.2g-1ubuntu4.1 500
500 http://mirror.uoregon.edu/ubuntu xenial-updates/main amd64 Packages
500 http://mirror.uoregon.edu/ubuntu xenial-security/main amd64 Packages
1.0.2g-1ubuntu4 500
500 http://mirror.uoregon.edu/ubuntu xenial/main amd64 Packages
Então corri com
sudo apt-get install libssl1.0.0=1.0.2g-1ubuntu4.1