If you look at RFC 1510, (an overview and specification of Version 5 of the Kerberos network authentication system), the initial exchange involves the client (Bob) sending its own identity, and the identity of the server (Alice) for which it is requesting credentials in cleartext. The response contains a ticket for the client to present to the server, and a session key that will be shared by the client and server. The session key and additional information are encrypted using the client's secret key (which is stored on the Authentication Server).
The request message contains the client's principal name as well as the server's principal name, the time and a nonce to prevent replays. The reply message contains information which can be used to detect replays, and to associate it with the message to which it replies.
In the normal case, the authentication server does not know whether or not the client is actually the principal named in the request. It simply sends a reply without knowing or caring whether or not they are the same. This is acceptable since nobody but the requesting principal (client) will be able to decode the reply.
For further information, have a look at Section 3 - Message Exchange of RFC 1510.