A method of providing a protocol for rekeying between two stations is disclosed. The method can include providing a first set of messages for computing a new key and reserving an auxiliary storage area for the new key. The first set of messages comprises an enable exchange. The method also includes providing a second set of messages to obsolete an old key and switch to the new key. The second set of messages comprises a transition exchange. In one embodiment, the protocol includes rekeying between multiple stations, and the rekey coordinator sends the first set of messages to a plurality of rekey participants. The auxiliary storage area allows multiplexing in both the enable and transition exchanges, thereby facilitating an efficient and safe rekey operation.