In this paper, we present a security weakness of a forward secure authentication protocol proposed by Tri Van Le et al. called O-FRAP which stands for Optimistic Forward secure RFID Authentication Protocol. In particular, we point out that in the O-FRAP protocol, the server can be subject to a denial-of-service attack due to a flaw in the database querying procedure. Our attack also applies to a simplified version of O-FRAP called O-RAP (Optimistic RFID Authentication Protocol) which is essentially O-FRAP but without a secret key updating procedure (and thus forward security). We then propose two improved protocols called O-FRAP. and O-RAP. which prevent the said denial-of-service attack. In addition, the O-FRAP* protocol also addresses two security weaknesses of O-FRAP pointed out earlier by Khaled and Raphael. In terms of performance, comparing to O-FRAP, O-FRAP(+) requires a few more computational steps but much less storage at the back-end server. (C) 2010 Elsevier B.V. All rights reserved.