Thanks for pointing me at ProxyCommand. This is pretty close to JavaFan's suggestion, only wrapped into perl code vs ssh config.

One thing I've been wondering about is why one can't pass -L port:host:port to the master ssh. I've tried it with Net::OpenSSH and -L was not passed to the master ssh. Besides a small security concern with that open forwarded port I feel it would be cleaner than proxying via ssh and having to install netcat.

If you have tunnels enabled on the gateway, you can use Net::OpenSSH tunnel methods to create a connection to some remote machine accesible from the gateway without the need to create a local listener.

For instance:

my $ssh_g = Net::OpenSSH->new($gateway);
my $proxy_command = $ssh_g->make_remote_command({tunnel => 1}, $host, 
+22);
my $ssh = Net::OpenSSH->new($host, master_opts => [-o => "ProxyCommand
+=$proxy_command"]);
[download]

From the top of your head - do you know why would Net::OpenSSH->new() hang forever after getting "Permission denied, please try again." ?

Also I found that some characters in the passwords have to be escaped. Like @ and !. Otherwise it does not even get that "Permission denied, please try again." error. I'm not sure if I did escape ! the right way. May be that contributes to that hanging problem I am having.

I've tried $Net::OpenSSH::debug and all I see is :

Permission denied, please try again.
# file object not yet found at ....
[download]

The problem I'm stuck with is : first I'm trying public key auth which fails because there is no key yet. Then I try ssh with password and get "Permission denied". But new call never returns...

Also I found that some characters in the passwords have to be escaped

You shouldn't need to quote the password. Actually the "Permission denied, please try again" error indicates a bad password. In any case, could you post your code? otherwise is difficult to guess what can be failing.

Also, run your script with $Net::OpenSSH::debug = -1 and post here the full output.

What versions of the Net::OpenSSH, perl, OpenSSH and operating system are you using?

And specific issue I *think* is that it adds "PreferredAuthentications=keyboard-interactive,password" which probably results in not being able to auth against "relay" host with public key auth. If both relay and dest hosts had same type auth - either both pub key or both password then this would not be a problem.

# call args: ['ssh','-o','CheckHostIP no','-o','ConnectionAttempts 2',
+'-o','ForwardAgent yes','-o','HashKnownHosts no','-o','StrictHostKeyC
+hecking=no','-o','VerifyHostKeyDNS no','-o','UserKnownHostsFile /dev/
+null','-o','ConnectTimeout 15','-o','HostbasedAuthentication no','-o'
+,'ChallengeResponseAuthentication no','-o','RhostsRSAAuthentication n
+o','-o','GSSAPIAuthentication no','-vvv','-o','PasswordAuthentication
+ yes','-o','PubkeyAuthentication yes','-o','PreferredAuthentications=
+publickey,password','-o','NumberOfPasswordPrompts=2','-o','ProxyComma
+nd=ssh root@192.168.1.1 nc %h 22','-o','ServerAliveInterval=30','-x2M
+N','-o','NumberOfPasswordPrompts=1','-o','PreferredAuthentications=ke
+yboard-interactive,password','-S','/root/.libnet-openssh-perl/root-XX
+XXX','-l','root','10.20.30.40','--']
[download]

After editing OpenSSH.pm to not disable publickey and not getting anywhere while being able to run same ssh command manually I got stuck. The problem is public key authentication (key is coming from ssh-agent, NOT the local file) to the gateway host. Here is what happens with one called from perl :

# call args: ['ssh','-o','CheckHostIP no','-o','HashKnownHosts no','-o
+','StrictHostKeyChecking no','-o','VerifyHostKeyDNS no','-o','UserKno
+wnHostsFile /dev/null','-o','HostbasedAuthentication no','-o','Challe
+ngeResponseAuthentication no','-o','RhostsRSAAuthentication no','-o',
+'GSSAPIAuthentication no','-o','ProxyCommand=ssh -o "PasswordAuthenti
+cation no" -o "GSSAPIAuthentication no" -vvv -k root@192.168.1.1 nc %
+h 22','-o','PasswordAuthentication yes','-o','PubkeyAuthentication ye
+s','-o','ServerAliveInterval=30','-x2MN','-o','NumberOfPasswordPrompt
+s=1','-o','PreferredAuthentications=publickey,keyboard-interactive,pa
+ssword','-S','/root/.libnet-openssh-perl/root-10.20.30.40-16309-99228
+','-l','root','10.20.30.40','--']
[download]

Output from perl:

debug1: Authentications that can continue: publickey,gssapi-with-mic,p
+assword
debug3: start over, passed a different list publickey,gssapi-with-mic,
+password
debug3: preferred publickey,keyboard-interactive
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Trying private key: /root/.ssh/id_rsa
debug3: no such identity: /root/.ssh/id_rsa
debug1: Trying private key: /root/.ssh/id_dsa
debug3: no such identity: /root/.ssh/id_dsa
debug2: we did not send a packet, disable method
debug1: No more authentication methods to try.
Permission denied (publickey,gssapi-with-mic,password).
[download]

And this one is manual :

ssh -o "CheckHostIP no" -o "HashKnownHosts no" -o "StrictHostKeyChecki
+ng no" -o "VerifyHostKeyDNS no" -o "UserKnownHostsFile /dev/null" -o 
+"PasswordAuthentication yes" -o "PubkeyAuthentication yes" -o "ProxyC
+ommand=ssh -vvv root@192.168.1.1 nc %h 22" -o "ServerAliveInterval=30
+" -x2MN -o "NumberOfPasswordPrompts=1" -o "PreferredAuthentications=p
+ublickey,keyboard-interactive,password" -S /tmp/zzz -l root 10.20.30.
+40
[download]

Output:

debug3: remaining preferred: publickey,keyboard-interactive,password
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive,password
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Offering DSA public key: /HOME/MY_KEY.DSA
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug1: Server accepts key: pkalg ssh-dss blen 432
[download]

I think the root of my issues is no clear understanding of how authentication works along with ProxyCommand. In my setup I have public key auth with host that I use in ProxyCommand to run nc. And the destination host needs password auth. So when I supply username/password - which host does it apply to ? One that is serving as a relay and running nc or the final destination ?

Here is relevant part of my code. May be I need properly destroy $ssh before opening new connection too. To not stumble upon remains of the previous failed public key attempt.

while ( GO OVER ALL HOSTS I HAVE ) {

        // FIGURE OUT IF CAN BE REACHED DIRECT

        my $ssh;

        my @pw_opts = (
                -o      => "CheckHostIP no",
                -o      => "ConnectionAttempts 1",
                -o      => "ForwardAgent yes",
                -o      => "HashKnownHosts no",
                -o      => "StrictHostKeyChecking=no",
                -o      => "VerifyHostKeyDNS no",
                -o      => "UserKnownHostsFile /dev/null",
                -o      => "ConnectTimeout 5",
                -o      => "HostbasedAuthentication no",
                -o      => "ChallengeResponseAuthentication no",
                -o      => "RhostsRSAAuthentication no",
                -o      => "GSSAPIAuthentication no",
        );

        my @pubkey_opts = @pw_opts;

        push @pubkey_opts, ( -o => "PasswordAuthentication no");
        push @pubkey_opts, ( -o => "PubkeyAuthentication yes");
        push @pubkey_opts, ( -o => "PreferredAuthentications publickey
+");

        push @pw_opts, ( -o => "PreferredAuthentications=password");
        push @pw_opts, ( -o => "NumberOfPasswordPrompts=1");


        if( NOT REACHABLE DIRECT ) {
                push @pw_opts, (-o => 'ProxyCommand=ssh root@'.$sshgw.
+' nc %h 22');
                push @pubkey_opts, (-o => 'ProxyCommand=ssh root@'.$ss
+hgw.' nc %h 22');
        }

        $ssh = Net::OpenSSH->new(
                $user.'@'.$host,
                master_opts             => \@pubkey_opts,
                master_stdout_discard   => 1,
                master_stderr_discard   => 1,
        );

        if($ssh->error) {

                print "SSH key auth didn't work for $host, will try pa
+sswords...\n";

                foreach my $pass (@passwords) {

                        $ssh = Net::OpenSSH->new(
                                $user.'@'.$host,
                                password                => $pass,
                                master_opts             => \@pw_opts,
                                kill_ssh_on_timeout     => 1,
                        #       master_stdout_discard   => 1,
                        #       master_stderr_discard   => 1,
                        );

                        if(!$ssh->error) {
                                print "Authenticated with password to 
+$host\n" if($debug);
                                last;
                        } else {
                                print "SSH returned : ".$ssh->error."\
+n" if($debug);
                        }
                }

                if($ssh->error) {
                        print "Can not login into $host : ".$ssh->erro
+r."\n";
                        next;
                }

        } else {
                print "SSH key accepted at $host\n";
        }
}
[download]