Let's say your DNS is not working. You have the IPs of a number of running machines. Some of those expose SSH as a service, but you don't know which IP corresponds to the machine you are searching for. How can you find it? If your answer is «Fix the DNS» you win a prize.
SSH no-brainers
You might have noticed that the first time you connect to a machine, you
are required to accept its public key. Usually people don't compare it
with the one stored in /etc/ssh/ server-side, but it would be a best
practice, since this is the only moment in which a bad guy could try to
mount a Man in the Middle and pretend to be your server.
As you collect your server's key, it gets stored in the known_hosts
file of your user (~/.ssh/known_hosts), which is simply a textfile with
a EOL separated list of hosts and their public key. After that point you
can simply connect to the server, and SSH will run the key verification
under the hood, against the stored keys.
Finding your machine
Your friend nmap
The nmap scanner is really impressive. If you ever happened to go through the manual, you might know about the NSE scripting system, which allow you to write service-specific scripts in Lua. You can find on YouTube interesting videos about this feature.
Script scanning can be activated using the --script or the -A flags.
If your target machine has a SSH server the dedicated script will output
dump the public key of the server. For each server you scan.
Your other friend, ssh-keygen
The ssh-keygen command is generally used to generate the SSH keys. But
if you look at the manpage you will find useful options like -l, which
dumps the key fingerprints inside a known_hosts file:
ssh-keygen -l -f ~/.ssh/known_hosts
You can use the -F flag to filter the DNS name of your lost machine (or
just use grep, actually).
Find your stuff
At this point it gets trivial.
Now it's time to change your crappy DNS.