What are the steps that occur during a ssh connection establishment on a machine that does use password based authentication?

I want to know what happens behind the scenes in establishing a ssh connection, i mean till we land on the shell in a Linux from a Linux machine. I know that password is not sent in plain text in a ssh connection. So what do they do to encrypt the connection. Here i am assuming that i have not generated my public/private keys. I use password for authentication. So i think there cant be a exchange of keys before securing the connection. I searched on google and in serverfault but no hits. The closest i got to in serverfault was this post What exactly does ssh send when performing key negotiation? .
The above post assumes the user is connecting via pubic key exchange. But i am looking for a case of securing the connection without the public/private keys. How does it encrypt the connection even before i enter the password. What does it use to secure the connection so that password is not send plain text ?

Solution 1:

When you install SSH and start it for the first time, it will generate public and private keys for the machine, which are the same for every user. Upon connection, both machines will exchange their public key parts (in plain text) and use them to encrypt the communication between the hosts. After the key exchange, the communication will switch to encrypted mode.

In every users ~/.ssh/known_hosts file the keys will then be stored and compared against the one send upon the next connection. This is the reason you will get an error if you try to connect to a machine you have recently reinstalled: While doing so you have generated a new machine key pair, and this doesn't match the cached version, which also could mean an attempted attack.

Solution 2:

RFC 4252 explains how authentication using SSH works and which steps are involved in it. Of course, the specification is cumbersome to read, so the easiest way might be running ssh with one or more verbose (-v) flags since it them prints out all the debug output explaining what it is doing.

This is what it looks like for a sample case (I changed user and host names). Using ssh -vv instead of ssh -v will provide even more detail:

[user@gromp ~]$ ssh -v [email protected] 
OpenSSH_5.5p1 Debian-6, OpenSSL 0.9.8o 01 Jun 2010
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Connecting to example.org [1.2.3.4] port 22.
debug1: Connection established.
debug1: identity file /home/user/.ssh/id_rsa type -1
debug1: identity file /home/user/.ssh/id_rsa-cert type -1
debug1: identity file /home/user/.ssh/id_dsa type -1
debug1: identity file /home/user/.ssh/id_dsa-cert type -1
debug1: Remote protocol version 1.99, remote software version OpenSSH_5.8
debug1: match: OpenSSH_5.8 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.5p1 Debian-6
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'example.org' is known and matches the RSA host key.
debug1: Found key in /home/user/.ssh/known_hosts:1
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password,keyboard-interactive,hostbased
debug1: Next authentication method: publickey
debug1: Trying private key: /home/user/.ssh/id_rsa
debug1: Trying private key: /home/user/.ssh/id_dsa
debug1: Next authentication method: keyboard-interactive
debug1: Authentications that can continue: publickey,password,keyboard-interactive,hostbased
debug1: Next authentication method: password
[email protected]'s password: 
debug1: Authentication succeeded (password).
debug1: channel 0: new [client-session]
debug1: Requesting [email protected]
debug1: Entering interactive session.
debug1: Sending environment.
debug1: Sending env LANG = en_US.UTF-8
[[email protected]~]$