I found this thread. Maybe it's the bug of md5deep.
linux - md5deep ubuntu install - command not found - Stack Overflow
The suggested solution is to upgrade Ubuntu to above 16. How did you circumvent the problem back in Ubuntu 16?
Added:
I solved the problem. Just do a "sudo ln -s /usr/bin/hashdeep /usr/bin/md5deep".