The Chain Sum Primitive and Its Applications to MACs and Stream Ciphers,” EUROCRYPT’98.pdf

The chain sum primitive and its applicationsto MACs and stream ciphersMariusz H. Jakubowski1 and Ramarathnam Venkatesan21 Princeton University, mj@2 Microsoft Research, Redmond, WA 98052, USA, venkie@Abstract. We present a new scheme called universal block chaining withsum (or chain sum primitive (CS) for short), and show its applicationto the problem of combined encryption and authentication of data. Theprimitive is a weak CBC-type encryption along with a summing step,and can be used as a front end to stream ciphers to encrypt pages orblocks of data (e.g., in an encrypted le system or in a video stream).Under standard assumptions, the resulting encryption scheme provablyacts as a random permutation on the blocks, and has message integrityfeatures of standard CBC encryption. The primitive also yields a very fastmessage authentication code (MAC), which is a multivariate polynomialevaluation hash. The multivariate feature and the summing aspect arenovel parts of the design. Our tests show that the chain sum primitiveadds approximately 20 percent overhead to the fastest stream ciphers.1 IntroductionFor combined encryption and authentication of data, one often uses stream ci-phers because of their speed in comparison to block ciphers; one then appendsa separately computed MAC value. However, in some applications, data mustbe accessed in pages or blocks, and stored encrypted, as in some encrypted lesystems or video streams. For this purpose, it is customary to use CBC en-cryption on the blocks, and compute an integrity check for the entire streamseparately from these individual encrypted blocks. Alternately, one may com-pute and store one MAC value separately per block, but this causes the size ofthe MAC data to expand in proportion to the number of blocks, and is thusundesirable. Certain applications, such as encrypted le systems and video, taxthe CPU rather harshly, and using a block cipher can cause a noticeable per-formance hit. For backward compatibility and m