knownhosts recover

A CLI tool that recovers the IPv4 hostnames behind a hashed OpenSSH known_hosts file, brute-forcing them on an NVIDIA GPU (CUDA, tuned for a GTX 1070 / Pascal sm_61).

History

Back when HashKnownHosts was introduced, hiding the hosts you had connected to seemed like a sensible privacy measure. This repo is a proof-of-concept that the protection it offers is quite limited, and that a old GPU can sweep the entire IPv4 space in seconds to recover any hashed entries. The tool is intended for recovering your own anonymised known_hosts file, for incident-response/forensics on a host you control, and for demonstrating why hashing alone gives only modest protection against host enumeration.

What it does (and why it works)

When SSH is configured with HashKnownHosts yes, host entries are stored as:

|1|<base64 salt>|<base64 hash>  ssh-ed25519 AAAA...

where hash = HMAC-SHA1(key = salt, message = hostname) and the salt is 20 random bytes per entry. this is a one-way hash, so there is no decryption. The only way to learn the original hostname is to hash candidate hostnames until one matches. For IPv4 the candidate space is small (at most 2³² strings), so a GPU sweeps it in seconds.

This is teh same idea as cracking a hashed password list, applied to the addresses you have connected to on your own machine. Useful for recovering your own anonymised known_hosts, for incident-response/forensics on a host you control, and for demonstrating why hashing alone gives only modest protection against host enumeration.

Modes

Mode	Range scanned	Size
local	10/8, 172.16/12, 192.168/16, 127/8, 169.254/16	~17.9 M
public	globally routable unicast only (private/reserved/multicast skipped)	~3.7 B
all	the entire 0.0.0.0 – 255.255.255.255 space	2³² ≈ 4.29 B

Caching (skip-on-rerun)

Every recovered entry is appended to a cache file (./recovered.cache by default) as <hash_b64> <ip>. On the next run, any entry already in the cache is printed immediately and never re-brute-forced; the tool moves straight on to the remaining unknown entries.

Build

Requires the CUDA toolkit (nvcc) and a CUDA-supported host compiler. On my machine CUDA 12.0's nvcc rejects gcc-13, so device code is compiled with clang-13 while the plain C is compiled with gcc, anyway the Makefile handles this.

make       # GPU build if nvcc is present, else CPU-only
make cpu   # force a portable CPU (OpenMP) build
make test  # build + OpenSSH cross-check (uses real ssh-keygen -H)

Override the GPU arch or host compiler if needed:

make ARCH=sm_75 NVCC_CCBIN=clang-14

Usage

knownhosts_recover [options]
  -m, --mode <local|public|all>   IPv4 space to search (default: local)
  -i, --in <path>                 known_hosts (default: ~/.ssh/known_hosts)
  -c, --cache <path>              recovery cache (default: ./recovered.cache)
      --cpu                       force the CPU back-end
  -v, --verbose                   show scan progress
      --selftest                  self-check the HMAC/crack pipeline
  -h, --help

Examples:

# Recover private-range hosts from your own known_hosts
knownhosts_recover -m local -v

# Sweep the full public Internet range for the unknown entries, with progress
knownhosts_recover -m public -i ~/.ssh/known_hosts -v

# Exhaustive 2^32 sweep
knownhosts_recover -m all -v

Output legend: [plain] already-visible IPv4, [cached] served from the cache, [found] newly recovered, [miss] not present in the scanned range.

Performance

On a GTX 1070, with the HMAC ipad/opad pad-block states precomputed per entry (so each candidate costs just two SHA-1 compressions per outstanding target):

Mode	Entries	Time
local	a few	~0.1 s
public	1–2	~3 s
all	1	~3.2 s (≈1.3 billion candidates/s)

Time scales roughly linearly with the number of uncached entries, and the search early-exits as soon as every entry has been recovered.