In this paper we discuss the often overlooked timeliness property of fair exchange protocols. We gather different available definitions of this property, and propose a new and stronger interpretation for timeliness in the context of security protocols. We discuss common timeliness-related pitfalls in fair exchange protocol design, and show a particular timeliness attack effective in several optimistic protocols proposed in the literature. Finally, we provide guidelines that may help to avoid common mistakes in protocol design, and propose our own protocol that ensures both fairness and timeliness. © 2009 ESRGroups France. Asokan, A., Fairness in electronic commerce, (1998), Ph.D. dissertation, University of WaterlooGärtner, F.C., Pagnia, H., Vogt, H., Approaching a formal definition of fairness in electronic commerce (1999) Symposium on Reliable Distributed Systems, pp. 354-359Kremer, S., Markowitch, O., Zhou, J., An intensive survey of fair non-repudiation protocols (2002) Computer Communications, 25 (17), pp. 1606-1621Louridas, P., Some guidelines for non-repudiation protocols (2000) SIG-COMM Comput. Commun. Rev, 30 (5), pp. 29-38Abadi, M., Needham, R., Prudent engineering practice for cryptographic protocols (1996) IEEE Transactions on Software Engineering, 22 (1), pp. 6-15Woo, T.Y.C., Lam, S.S., A lesson on authentication protocol design (1994) Operating Systems Review, 28 (3), pp. 24-37. , citeseer.ist.psu.edu/woo94lesson.html, Online, AvailableMarkowitch, O., Roggeman, Y., Probabilistic non-repudiation without trusted third party (1999) Second Workshop on Security in Communication Network, 99. , citeseer.ist.psu.edu/markowitch99probabilistic.html, Online, AvailablePagnia, H., Vogt, H., Gaertner, F.C., Fair Exchange (2003) The Computer Journal, 46 (1), p. 55Onieva, J., Zhou, J., Lopez, J., Enhancing certified email service for timeliness and multicasting (2004) Proceedings of the Fourth International Network Conference, INC'04, pp. 327-335. , Steven M. Furnell and Paul S. Dowland Eds, 6-9 July, Plymouth, UK, OctAnderson, R.J., Liability and computer security: Nine principles (1994) Springer LNCS, 94, pp. 231-245. , Computer Security, ESORICS, 875. SpringerVerlagPagnia, H., Gärtner, F.C., (1999) On the impossibility of fair exchange without a trusted third party, , citeseer.ist.psu.edu/pagnia99impossibility.html, Darmstadt, Germany, Tech. Rep. TUD-BS-1999-02, Online, AvailablePiva, F.R., Monteiro, J.R.M., Devegili, A.J., Dahab, R., Applying strand spaces to certified delivery proofs (2006) Anais do VI SBSeg, Simpósio Brasileiro em Segurança da Informaç ão e de Sistemas Com-putacionais, , UFRJ/NCE, SeptemberPiva, F.R., Monteiro, J.R.M., Dahab, R., Strand spaces and fair exchange: More on how to trace attacks and security problems (2007) Anais do VII SBSeg, Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, pp. 80-93. , UFRJ/NCE, SeptemberThayer, F.J., Herzog, J.C., Guttman, J.D., Strand spaces: Proving security protocols correct (1999) Journal of Computer Security, 7 (2-3), pp. 191-230Micali, S., Simple and fast optimistic protocols for fair electronic exchange (2003) PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing, pp. 12-19. , New York, NY, USA: ACM PressZhou, J., Deng, R.H., Bao, F., Evolution of fair non-repudiation with ttp (1999) ACISP '99: Proceedings of the 4th Australasian Conference on Information Security and Privacy, pp. 258-269. , London, UK: Springer-VerlagZuo, M., Li, J., Constructing fair-exchange p2p file market (2005) Proceedings of the 4th International Conference on Grid and Cooperative Computing, pp. 941-946. , SpringerPayeras-Capellà, M., Ferrer-Gomila, J.L., Huguet-Rotger, L., Achieving fairness and timeliness in a previous electronic contract signing protocol (2006) ARES, pp. 717-722. , IEEE Computer SocietyBao, F., Wang, G., Zhou, J., Zhu, H., Analysis and improvement of Micali's fair contract signing protocol (2004) LNCS, 3108, pp. 176-187. , In: Information Security and Privacy ACISP'04, Springer-VerlagFerrer-Gomila, J.L., Payeras-Capellà, M., Rotger, L., An efficient protocol for certified electronic mail (2000) ser. Lecture Notes in Computer Science, 1975, pp. 237-248. , Third International Workshop-ISW 2000, Berlin: Springer-VerlagAnderson, R.J., Needham, R.M., Robustness principles for public key protocols (1995) CRYPTO '95: Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, pp. 236-247. , London, UK: Springer-VerlagAsokan, N., Shoup, V., Waidner, M., Optimistic fair exchange of digital signatures (1999) IEEE Journal on Selected Areas in Communications, 18 (4), pp. 593-610. , citeseer.ist.psu.edu/article/asokan98optimistic.html, Online, AvailableNenadic, A., Zhang, N., Barton, S.K., Fides: A middleware ecommerce security solution (2004) The 3rd European Conference on Information Warfare and Security, pp. 295-304. , JunNenadic, A., Zhang, N., Barton, S.K., A security protocol for certified e-goods delivery (2004) Information Assurance and Security, pp. 22-28. , IEEE Computer Society, AprGärtner, F., (2002) The problem of fair exchange, its formalization, and its relation to other problems in distributed computing, , citeseer.ist.psu.edu/717251.html, Online, Available