One embodiment of the present invention includes an approach for efficient start-up for secured connections and related services. A client machine receives, via an application program, a request to send a secure message to a server machine. The client machine transmits a plurality of messages to the server machine that includes a first message comprising at least two of user authentication data, entity authentication data, key exchange data, and encrypted message data. The client machine receives, from the server machine, a second message that includes a first master token comprising a first set of session keys for encrypting and authenticating messages exchanged with the server machine.