We define a new mode of operation for block encryption which in addition to assuring confidentiality also assures message integrity. In contrast, previously for message integrity a separate pass was required to compute a cryptographic message authentication code (MAC). The new mode of operation, called Integrity Aware CBC (IACBC), requires a total of m + log m block encryptions on a plain-text of length m blocks. The well known CBC (cipher block chaining) mode requires m block encryptions. The second pass of computing the CBC-MAC essentially requires additional m block encryptions. A new highly parallelizable mode (IAPM) is also shown to be secure for both encryption and message integrity. We also show a lower bound of Omega(log m) additional block encryptions for any reasonably modeled (linear) scheme which assures message integrity along with confidentiality.
Gates 4B, 12/7/00, 4:15 PM