The cipher and mac selection according to this are in some sort of order in a config file. How do the client and server know that they are using the same ones though? Is this information exchanged in the beginning? Another question: was SSH v1 vulnerable to MiM attacks? From what I've been reading there is no certification authority involved.
In the first messages between client and server, both send their list of supported algorithms, in order of preference. Then the algorithm that will be used is the first one on the client list that also appears somewhere in the server list. This is specified in RFC 4253, section 7.1:
encryption_algorithms A name-list of acceptable symmetric encryption algorithms (also known as ciphers) in order of preference. The chosen encryption algorithm to each direction MUST be the first algorithm on the client's name-list that is also on the server's name-list. If there is no such algorithm, both sides MUST disconnect. (...) mac_algorithms A name-list of acceptable MAC algorithms in order of preference. The chosen MAC algorithm MUST be the first algorithm on the client's name-list that is also on the server's name-list. If there is no such algorithm, both sides MUST disconnect.
In other words, the protocol is such that the client's preferences take precedence over the server's preferences.
The normal SSH model (for both SSH v1 and v2) is that the client remembers the server's public key. When the client first connects to a given server, the client displays the hash of the apparent server public key to the user; the user is then supposed to check that hash with regards to some reference value provided by a trusted sysadmin (e.g. the user might phone the server's sysadmin to get the expected hash value, and compare). The client software will then remember that public key (e.g. in the
.ssh/known_hosts file), and further connections will check the server key by simply comparing it with the remembered value.
This model is vulnerable to MitM only if the attacker acts during the very first connection, and if the human user is lazy and does not check the hash value as he should (in practice, 99% of human users are lazy).
This model has not changed between SSH v1 and v2. However, modern SSH v2 implementations also optionally (but not commonly) dabble in certificates, allowing the use of a CA-based model instead of the traditional model explained above. I have yet to see that kind of certificates-for-SSH really used in practice, though.