Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for updating shared keys. In one aspect, a method includes generating, at a first server and using a first key associated with a current period of time on the first server, a first piece of information based on a first request received from a first client device; receiving, at a second server, a second request from the first client device, the second request including the generated first piece of information; and validating, at the second server and using the first key, the first piece of information, wherein the validating is performed during the current period of time on the second server and wherein to generate information the second server uses a second key different from the first key.