A console-based multi-user authentication process allows multiple users of a game console to be authenticated together in a single request/reply exchange with an authentication entity. The results of which is the possession of a single ticket that can be used to prove authenticity of multiple authentication principals to one or more online services. Also described is a handshake process that can be used to initially establish an authentication account for each game console, in which the account creation server can trust that a genuine game console is making the request.