How does Kerberos work with SSH?

First login:

• L sends username and SSH authentication request to S1
• S1 returns available SSH authentication mechanisms, with "password" as one of them
• L picks "password" and sends the plain password to S1
• S1 gives username and password to PAM stack.
• On S1, PAM (usually pam_krb5 or pam_sss) requests a TGT (ticket-granting ticket) from the Kerberos KDC.
  1. S1 obtains a TGT.
     • Old style (without preauth): S1 sends an AS-REQ and receives a AS-REP containing the TGT.
     • New style (with preauth): S1 uses your password to encrypt the current time stamp, and attaches it to the AS-REQ. The server decrypts the timestamp and verifies that it is within the allowed time skew; if decryption fails, the password is immediately rejected. Otherwise, a TGT is returned in the AS-REP.
  2. S1 attempts to decrypt the TGT using a key generated from your password. If the decryption succeeds, the password is accepted as correct.
  3. The TGT is stored to a newly created credential cache. (You can inspect the $KRB5CCNAME environment variable to find the ccache, or use klist to list its contents.)
• S1 uses PAM to perform authorization checks (configuration-dependent) and open the session.
  • If pam_krb5 is called in authorization stage, it checks whether ~/.k5login exists. If it does, it must list the client Kerberos principal. Otherwise, the only allowed principal is username@DEFAULT-REALM.

Second login:

• S1 sends username and SSH authn request to S2
• S2 returns available auth mechs, one of them being "gssapi-with-mic" ¹
• S1 requests a ticket for host/s2.example.com@EXAMPLE.COM, by sending a TGS-REQ with the TGT to the KDC, and receiving a TGS-REP with the service ticket from it.
• S1 generates an "AP-REQ" (authentication request) and sends it to S2.
• S2 attempts to decrypt the request. If it succeeds, authentication is done. (PAM is not used for authentication.)
  • Other protocols such as LDAP may choose to encrypt further data transmission with a "session key" that was included with the request; however, SSH has already negotiated its own encryption layer.
• If authentication succeeds, S2 uses PAM to perform authorization checks and open the session, same as S1.
• If credential forwarding was enabled and the TGT has the "forwardable" flag, then S1 requests a copy of the user's TGT (with the "forwarded" flag set) and sends it to S2, where it gets stored to a new ccache. This allows recursive Kerberos-authenticated logins.

Note that you can obtain TGTs locally as well. On Linux, you can do this using kinit, then connect using ssh -K. For Windows, if you are logged in to a Windows AD domain, Windows does that for you; otherwise, MIT Kerberos can be used. PuTTY 0.61 supports using both Windows (SSPI) and MIT (GSSAPI), although you must enable forwarding (delegation) manually.

¹ gssapi-keyex is also possible but was not accepted into official OpenSSH.

To put the long story short: ideally, Kerberos tickets should be obtained on your terminal (L), either with kinit command or as part of the local login sequence in a so-called "single sign-on" setup. The remote systems (S1, S2) would then be accessible without password prompts. A chained access (L→S1→S2) would be possible by employing a technique known as "ticket forwarding". Such a setup requires, in particular, the KDC to be directly accessible from the terminal (L).

The other answer by grawity explains this approach in details.

The only non-obvious step here would be that there is a PAM module on S1 that used your credentials to perform a kinit and gets you a ticket granting ticket from K (client authentication). Then, when you SSH to S2 using Kerberos authentication, an client service authentication takes place. I don't see the benefit of going through all the tedious exchanges message by message.

Throw a -vvv on your ssh command if you want to see every message and read the Wikipedia description of Kerberos.