A method and apparatus for protecting against a replay attack in a database system makes use of customer records including a counter, and freshness records that include the customer counters and a freshness record counter. The counter from the customer records, the customer records in the freshness records, and the freshness record counter are used by a cryptographic device together with a cryptographic device counter to verify the freshness of the customer record prior to updating the customer record with respect to a recent transaction.