The protection of message integrity is a fundamental requirement of communication security. It represents the ability to detect modified or spurious messages, and is an equally important concern for both confidential and non-confidential messages. Both national and international security standards require integrity assurance in distributed systems, creating a need for designing and analyzing the integrity of messages in a wide variety of protocols. To date, general methods for the analysis and design of message integrity in cryptographic protocols have not been available.