A hostbased authentication request contains the name of the client host as
supplied by the client. OpenSSH normally compares this against a reverse
lookup on the client IP address, and fails authentication if they don't
match. There's little point to this behavior, since the real security
lies in the hostname/key match and signature verification. And it causes
breakage in your situation, where many hosts are coming through a NAT
gateway with the same IP address.

You can turn off the DNS check with the undocumented sshd option:

HostbasedUsesNameFromPacketOnly yes

However... this feature has a bug. OpenSSH normally strips the trailing
dot from the supplied hostname. It fails to do this if this option is
set, causing it to cease matching any hostnames in the known-hosts file
(which of course do not have the technically-correct trailing dots).
Here's a diff for fixing it:

--------------------------------------------------------------------------------
--- auth2-hostbased.c.~1.1.1.2~ 2006-10-01 00:00:03.247144000 -0400
+++ auth2-hostbased.c.~1.2~ 2006-09-30 23:58:23.255270000 -0400
@@ -142,15 +142,25 @@
debug2("userauth_hostbased: chost %s resolvedname %s ipaddr %s",
chost, resolvedname, ipaddr);

+ /* DESCO local mod
+
+ This stanza was mistakenly inside the following "else" clause,
+ with the result that setting hostbased_uses_name_from_packet_only
+ would actually cause hostbased authentication to cease working,
+ since no one has domain names with dots on the end in their
+ known_hosts files.
+
+ */
+ if (((len = strlen(chost)) > 0) && chost[len - 1] == '.') {
+ debug2("stripping trailing dot from chost %s", chost);
+ chost[len - 1] = '\0';
+ }
+
if (options.hostbased_uses_name_from_packet_only) {
if (auth_rhosts2(pw, cuser, chost, chost) == 0)
return 0;
lookup = chost;
} else {
- if (((len = strlen(chost)) > 0) && chost[len - 1] == '.') {
- debug2("stripping trailing dot from chost %s", chost);
- chost[len - 1] = '\0';
- }
if (strcasecmp(resolvedname, chost) != 0)
logit("userauth_hostbased mismatch: "
"client sends %s, but we resolve %s to %s",
--------------------------------------------------------------------------------

--
Richard Silverman
res@qoxp.net