Modern Cryptography ECS 227
Popular in Course
verified elite notetaker
verified elite notetaker
Ms. Schuyler Kozey
verified elite notetaker
Ms. Schuyler Kozey
verified elite notetaker
Ms. Schuyler Kozey
verified elite notetaker
verified elite notetaker
Popular in Engineering Computer Science
This 12 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 227 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 33 views. For similar materials see /class/191685/ecs-227-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Modern Cryptography
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/08/15
Authenticated Encryption J BLACK November 12 2003 1 Introduction Often when two parties communicate over a network they have two main security goals privacy and authentication In fact there is compelling evidence that one should never use encryption without also providing authentication 814 any solutions for the privacy and authentication problems have existed for decades and the traditional approach to solving both simultaneously has been to combine them in a straightforward manner using socalled generic compositioni However recently there have been a number of new constructions which achieve both privacy and authenticity simultaneously often much faster than any solution which uses generic composition In this article we will explore the various approaches to achieving both privacy and authenticity the socalled Authenticated Encryption problemi We will often abbreviate this as simply AEi We will start with generic composition methods and then explore the newer combined methodsi BACKGROUND Throughout this article we will consider the AE problem in the symmetrickey model This means that we assume our two communicating parties traditionally called Alice and Bob share a copy of some bitstring K called the key This key is typically chosen at random and then distributed to Alice and Bob via one of various methods This is the starting point for our work We now wish to provide Alice and Bob with an AB algorithm such that Alice can select a message M from a prede ned messagespace process it with the AE algorithm along with the key and possibly a nonce Nia counter or random value and then send the resulting output to Bob m output will be the ciphertext C the nonce N and a short message authentication tag a Bob should be able to recover M just given C N and his copy of the key Ki He should also be able to certify that Alice was the originator by computing a veri cation algorithm using the above values along with the tag a w at makes an AB algorithm good We may have many requirements and the relative importance of these requirements may vary according to the problem domain Certainly one requirement is that the AE algorithm be secure We will speak more about what this means in a moment But many other attributes of the algorithm may be important for us as well performance portability simplicityelegance parallelizability availability of reference implementations or freedom from patents we will pay attention to each of these concerns to varying levels as well SECURITYi Certainly an AB scheme is not going to serve our needs unless it is secure An AE scheme has two goals privacy and authenticity And each of these goals has a precise mathematical meaning 2 3 19 In addition there is a precise de nition for authenticated encryption the combination of both goals 5 6 26 It would take us too far a eld to carefully de ne each notion but we will give a brief intuitive idea of what is meant In our discussion we will use the term adversary to mean someone who is trying to subvert the security of the AE scheme who knows the de nition of the AE scheme but who does not possess the key Ki Privacy means intuitively that a passive adversary who views the ciphertext C and the nonce N cannot understand the content of the message Mi ne way to achieve this is to make C indistinguishable from random bits and indeed this is one de nition of security for an encryption scheme that is sometimes used although it is quite a strong one Department of Computer Science 430 UCB Boulder Colorado 80309 USA Email jrblack csvcoloradoedu WWW wwwcs Colorado edu erblack Scheme Passes Provably Secure Assoc Data Parallelizable On line Patent Free IAPM 1 J J J XECB 1 J J J OCB 1 J J J COM 2 J J J EAX 2 J J J J CWC 2 J J J J J Helix 1 J J J SOBER 128 1 J J J Figure 1 A comparison of the various AE schemes Generic composition is omitted since answers would depend on the particular instantiation For the schemes which do not support associated data subsequent methods have been suggested to remedy this for example see 32 Authenticity means intuitively that an active adversary cannot successfully fabricate a ciphertext C a nonce N and a tag a in such a way that Bob will believe that Alice was the originator in the formal security model we allow the adversary to generate tags for messages of his choice as if he were Alice for some period of time and then he must attempt a forgery We do not give him credit for simply replaying a previouslygenerated message and tag of course he must construct a new value If he does so with any signi cant probability of success the authentication scheme is considered insecurel ASSOCIATED DATAl in many application settings we wish not only to encrypt and authenticate message M but we wish also to include auxiliary data H which should be authenticated but left unencrypted An example might be a network packet where the payload should be encrypted and authenticated but the header should be unencrypted and authenticated The reason being that routers must be able to read the headers of packets in order to know how to properly route theml This need spurred some designers of AE schemes to allow associated data to be included as input to their schemesl Such schemes have been termed AEAD schemes Authenticated Encryption with Associated Data a notion which was rst formalized by Rogaway 32 As we will see the AEAD problem is easily solved in the generic composition setting but can become challenging when designing the more complex schemes in his paper Rogaway describes a few simple but limited ways to include associated data in any AE scheme and then presents a speci c method to ef ciently add associated data to the OCR scheme which we discuss belowl PROVABLE SECURITYi One unfortunate aspect of most cryptographic schemes is that we cannot prove that any scheme meets the formal goals required of it However we can prove some things related to security but it depends on the type of cryptographic object we are analyzing If the object is a primitive such as a block cipher no proof of security is possible so instead we hope for security once we have shown that no known attacks eg differential cryptanalysis seem to work However for algorithms which are built on top of these primitives called modes we can prove some things about their security namely that they are as secure as the primitives which underlie theml Almost all of the AE schemes we will describe here are modes only two of them are primitivesl AE SCHEMES The remainder of this article is devoted to the description and discussion of various AE algorithms For convenience we list them in Figure ll Note that we omit generic composition from the table since this approach comprises a class of schemes rather than a particular schemel CONVENTIONS Let 6 denote the empty string Let 2 denote the set of all n bit strings in general if S is a set we write 5 to mean 1 or more repetitions of elements from S that is the set 3132 3m i m gt 0 3i 6 S 1 S i S Thus En is the set of all binary strings whose lengths are a positive multiple of mi If we write 5 we mean zero or more repetitions of elements from 5 in other words 5 5 U We write A69 B to mean the exclusiveor of strings A and Bi Many of our schemes use a block cipherl Throughout n will be understood to be the blocksize of the underlying block cipher and k will be the size of its key For block cipher E we will write EK P to indicate invocation of block cipher E using the 16bit key K on the nbit plaintext block P In order to process a message M E Gin r we will often wish to break M into m strings M1 Mm each having nbits such that M M1M2 Mm For brevity we will say write M M1 Mm77 and understand it to mean the above 2 Generic Composition Although AE did not get a formal de nition until recently the goal has certainly been implicit for decades The traditional way of achieving both authenticity and privacy was to simply nd an algorithm which yields each one and then use the combination of these two algorithms on our message lntuitively it seems that this approach is obvious straightforward and completely safe Unfortunately there are many pitfalls accidentally discovered77 by wellmeaning protocol designers One commonlymade mistake is the assumption that AE can be achieved by using a noncryptographic nonkeyed hash function h and a good encryption scheme like CBC mode Cipher Block Chaining mode see CBCMAC and variants with key K and initialization vector N One produces CBCKNMhM and hopes this yields a secure AE scheme However these schemes are virtually always broken Perhaps the bestknown example is the Wired Equivalent Privacy protocol WEP used with 80211 wireless net works This protocol instantiates h as a Cyclic Redundancy Code CRC and then uses a stream cipher to encrypt Borisov Goldberg and Wagner showed among other things that it was easy to circumvent the authentication mechanism 15 Another common pitfall is key reuse77 In other words using some key K both for the encryption scheme and the MAC scheme This approach appliedly blindly almost always fails We will later see that all of our combined modes77 listed after this section do in fact use a single key but they are carefully designed to retain security in spite of this It is now clear to researchers that one needs to use a keyed hash ie a MAC with some appropriate key Kl along with a secure encryption scheme with an independent key K2 However it is unclear in what order these modes should be applied to a message M in order to achieve authenticated encryption There are three obvious choices o Mth MACthen Encrypt We rst MAC M under key Kl to yield tag a and then encrypt the resulting pair Ma under key K2 o Eth EncryptthenMAC We rst encrypt M under key K2 to yield ciphertext C and then compute a lt7 MACK1C to yield the pair C a o EampM EncryptandMAC We rst encrypt M under key K2 to yield ciphertext C and then compute a lt7 MACKl to yield the pair C 0 Also note that decryption and veri cation are straightforward for each approach above for MtE decrypt rst then verify For EtM and EampM verify rst then decrypt SECURITY In 2000 Bellare and Namprempre gave formal de nitions for AB 5 and then systematically examined each of the three approaches described above in this formal setting Their results show that if the MAC has a property called strongly unforgeable77 then it possible to achieve the strongest de nition of security for AE only via the EtM approach They further show that some knowngood encryption schemes fail to provide privacy in the AE setting when using the EampM approach and fail to provide a slightly stronger notion of privacy with the MtE approach These theoretical results generated a great deal of interest since three major preexisting protocols SSLTLS lPSec and SSH each used a different one of these three approaches the SSLTLS protocol uses MtE lPSec uses EtM and SSH uses EampM One might think that perhaps security aws exist in SSLTLS and SSH because of the results of Bellare and Namprempre however concurrent with their work Krawczyk showed that SSLTLS was in fact secure because of the encoding used alongside the MtE mechanism 29 And later Bellare Kohno and Namprempre showed that despite some identi ed security aws in SSH it could be made provablysecure via a number of simply modi cations despite its EampM approach The message here is that EtM with a provably secure encryption scheme and a provablysecure MAC each with independent keys is the best approach for achieving AET Although MtE and EampM can be secure security will often depend on subtle details of how the data are encoded and on the particular MAC and encryption schemes usedi PERFORMANCE Simple methods for doing very fast encryption have been known for quite some time For example CBC mode encryption has very little overhead beyond the calls to the block cipheri Even more attractive is CTR mode CounTeR mode see counter mode which similarly has little overhead and in addition is parallelizablei However MACing quickly is not so simple The CBC MAC Cipher Block Chaining Message Authentication Code see CBCMAC and variants is quite simple and just as fast as CBC mode encryption but there are wellknown ways to go faster The fastest software MAC in common use today is HMAC 120 HMAC uses a cryptographic hash function to process the message M and this is faster than processing M blockby block with a block cipheri However even faster approaches have been invented using the Wegman Carter construction 34 This approach involves using a noncryptographic hash function to process M and then uses a cryptographic function to process the hash output The noncryptographic hash is randomly selected from a carefullydesigned family of hash functions all with a common domain and range The goal is to produce a family such that distinct messages are unlikely to hash to the same value when the hash function is randomly chosen from that family This is the socalled universal hash family 16 The fastest known MACs are based on the Wegman Carter approach The speed champions are UMAC 11 and hash127 10 though neither of these are in common use yet ASSOCIATED DATAT As we mentioned in the introduction it is a common requirement in cryptographic protocols that we allow authenticated but nonencrypted data to be included in our message Although the singlepass modes we describe next do not naturally allow for associated data due to the fact that their encryption and authentication methods are intricately interwoven we do not have this problem with genericallycomposed schemesi Since the encryption and MAC schemes are entirely independent we simply run the MAC on all the data and run the encryption scheme only on the data to be kept private CAN WE DO BETTER One obvious question when considering genericallycomposed AE schemes is can we do better In other words might there be a way of achieving AE without using two different algorithms with two different keys and making two separate passes over the message The answer is yes and a discussion of these results comprise the remainder of this article 3 SinglePass Combined Modes It had long been a goal of cryptographers to nd a mode of operation which achieved AE using only a single pass over the message Mi any attempts were made at such schemes but all were broken Therefore until the year 2000 people still used generic composition to achieve AE which as we have seen requires two passes over M i 31 IAPM In 2000 Jutla of IBM invented two schemes which were the rst correct singlepass AE modes 25 He called these modes lACBC IntegrityAware Cipher Block Chaining and IAPM IntegrityAware Parallelizable Mode The rst mode somewhat resembles CBCmode encryption however offsets were added in before and after each blockcipher invocation a technique known as whiteningi However as we know CBCmode encryption is inherently serial we cannot begin computation for the k lst blockcipher invocation until we have the result of the kth invocationi Therefore more interest has been generated around the second mode IAPM which does not have this disadvantagei Let7s look at how IAPM worksi IAPM accepts a message M E EMT a nonce N E E and a key pair KLKQ each selected from Z for use with the underlying block cipher E The key pair is set up and distributed in advance between the communicating parties the keys are reused for a large number of messages However N and usually M vary with each transmissioni First we break M into M1 Mm1 and proceed as follows There are two main steps 1 offsetgeneration and 2 encryptiontag generation For offset generation we encipher N to get a seed value and then encipher sequential seed values to get the remaining seed values In other words set W1 lt7 EK2 N and then set Wi lt7 EK2 W1 i 7 2 for 2 S i S t where t lgm21 Here lg means log2 so if we had a message M with 256 n bit blocks we would require lg2591 9 block cipher invocations to generate the Wi values Finally to derive our m 1 offsets from the seed values for i from 1 to m 1 we compute 521 lt7 Wj where is the jth bit of 239 Armed with 50 through Sm we are now ready to process M First we encrypt each block of M by computing C lt7 EK1MlGB Si EB 51 for 1 S i S m 7 1 This xoring of 539 before and after the blockcipher invocation is the whitening we spoke of previously and is the main idea in all schemes discussed in this section Next we compute the authentication tag a set a lt7 EK1SmEB EB 50 Notice that we are whitening the simple sum of the plaintext blocks with two di erent offset values 50 and Sm Finally output N C1 Cm71 a as the authenticated ciphertext Note that the output length is two n bit blocks longer than M This ciphertext expansion77 comparable to what we saw with generic composition is quite minimal Given the K1 K2 and some output N C1 Cm71 a it is fairly straightforward to recover M and check the authenticity of the transmission Notice that N is sent in the c ear and so using K2 we can compute the Wi values and therefore the S values We compute Mi lt7 Ci 69 Si EB 51 for 1 S i S 72171 to recover M Then we check EK1Sm B 6950 to ensure it matches 0 If we get a match we accept the transmission as authentic and if not we reject the transmission as an attempted forgery COMMENTS ON IAPM Compared to generic composition where we needed about 2m blockcipher invo cations per message assuming our encryption and authentication modes were blockcipher based we are now using only around mlgm invocations Further re nements to IAPM reduce this even more so the number of blockcipher invocations is nearly m in these optimized versions meaning that one can achieve AE at nearly the same cost of encryption alone Proving a scheme like IAPM secure is not a simple task and indeed we cannot present such a proof here The interested reader is encouraged to read Halevils article which contains a rigorous proof that if the underlying block cipher is secure then so are lACBC and IAPM 21 32 XCBC and OCB Quickly after announcement of lACBC and IAPM other researchers went to work on nding similar single pass AE schemes Soon two other parties announced similar schemes Gligor and Donescu produced a host of schemes each with various advantages and disadvantages 18 and Rogaway Bellare Black and Krovetz announced their OCB scheme 33 which is similar to IAPM but with a long list of added optimizations Gligor and Donescu presented two classes of schemes XCBC and XECB XCBC is similar to CBC mode encryption just as lACBC was above and XECB is similar to ECB mode encryption which allows parallelism to be exploited much like the IAPM method presented above Since many practitioners desire parallelizable modes the largest share of attention has been paid to XECB Similar to IAPM XECB uses an offset to each message block applied before and after a block cipher invocation However XECB generates these offsets in a very ef cient manner using arithmetic mod 2 which is very fast on most commodity processors Once again both schemes are highlyoptimized and provide AE at a cost very close to that of encryption alone Proofs of security are included in the paper using the reductionist approach we described above Rogaway Bellare Black and Krovetz produced a single scheme called OCB Offset CodeBook This work was a followon to Jutla s IAPM scheme designed to be fullyparallelizable along with a long list of other improvements In comparison to IAPM OCB uses a single blockcipher key provides a message space of 2 so we never have to pad and is nearly endianneutral Once again a full detailed proof of security is included in the paper demonstrating that the security of OCB is directly related to the security of the underlying block cipher OCB is nodoubt the most aggressivelyoptimized scheme of those discussed in this section Perfor mance tests indicate that OCB is about 64 slower than CBC mode encryption and this is without exploiting the parallelism that OCB offers up For more information one can nd an indepth FAQ all relevant publications reference code test vectors and performance gures on the OCR web page at http www cs ucdavis edu rogawayocb ASSOCIATED DATAI In many settings the ability to handle associated data is crucial Rogaway 32 suggests methods to handle associated data in all three of the singlepass schemes mentioned above and for O B gives an extension which uses PMAC 13 to give a particularly ef cient variant of OCB which handles associated data INTELLECTUAL PROPERTY Given the importance of these new highlyef cient AE algorithms all of the authors decided to le for patents Therefore IBM Gligor and Rogaway all have intellectual property claims for their algorithms and perhaps on some of the overriding ideas involvedi To date none of these patents has been tested in court so the extent to which they are conflicting or interrelated is unclear One effect however is that many wouldbe users of this new technology are worried that the possible legal entanglements are not worth the bene ts offered by this technology Despite this OCB has appeared in the 802111 draft standard as an alternate mode and has been licensed several times However without I claims it is possible all of these algorithms would be in common use to ayi It was the complications engendered by the IP claims which spurred new teams of researchers to nd further ef cient AE algorithms which would not be covered by patentsi Although not as fast as the single pass modes described here they still offer signi cant performance improvements over generic composition schemes These schemes include CCM CWC and EAX the latter invented in part by two researchers from the OCB teami We discuss these schemes next 4 TwoPass Combined Modes If we have highlyef cient singlepass AE modes why would researchers subsequently work to develop less ef cient multipass AE schemes Well as we just discussed this work was entirely motivated by the desire to provide patentfree AE schemes The rst such scheme proposed was CCM CBC MAC with Counter Mode by Ferguson Housley and Whiting Citing several drawbacks to CCM Bellare Rogaway and Wagner proposed EAX another patentfree mode which addresses these drawbacks And independently Kohno Viega and Whiting proposed the CWC mode CarterWegman with Counter mode encryptioni CWC is also patentfree and unlike the previous two modes is fully parallelizablei We now discuss each of these modes in turn 41 CCM Mode CCM was designed with AES speci cally in mind It therefore is hardcoded to assume a 128bit block size though it could be recast for other block sizes Giving all the details of the mode would be cumbersome so we will just present the overriding ideas For complete details see the CCM speci cation 35 CCM is parameterizedi It requires that you specify a 128bit blockcipher eg AES a tag length which must be one of 4 6 8 10 12 14 or 16 and the messagelength eld7s size which induces an upperbound on the message lengthi Like all other schemes we mention CCM uses a nonce N each time it is invoked and the size of N depends on the the parameters chosen above speci cally if we choose a longer maximum messagelength we must accept a shorter noncei It is left to the user to decide which parameters to use but typical values might be to limit the maximum message length to 16 MBytes and then use a 96bit noncei Once the parameters are decided we invoke CCM by providing four inputs the key K which will be used with AES the nonce N of the proper size associated data H which will be authenticated but not encrypted and the plaintext M which will be authenticated and encrypted CCM operates in two passes rst we encode the above parameters into an initial block prepend this block to H and M and then run CBC MAC over this entire bytestring using Ki This yields the authentication tag a The precise details of how the above concatenation is done are important for the security of CCM but are omitted here Next we form a countervalue using one of the schemes parameters along with N and any necessary padding to reach 128 bits This counter is then used with CTR mode encryption on a M under K to produce the ciphertext The rst 128 bits are the authentication tag and we return the appropriate number of bytes according to the taglength parameter The subsequent bytes are the encryption of M and are always included in the output Decryption and veri cation are quite straightforward N produces the countervalue and allows the recovery of Mi Re running CBC MAC on the same input used above allows veri cation of the tag COMMENTS ON CCM It would seem that CCM is not much better than simple generic composition after all it uses a MAC scheme the CBC MAC and an encryption scheme CTR mode encryption which are both wellknown and provably secure modes But CCM does offer advantages over the straightforward use of these two primitives generically composed in particular it uses the same key K for both the MAC and the encryption steps Normally this practice would be very dangerous and unlikely to work but the designers were careful to ensure the security of CCM despite this normallyrisky practice The CCM specification does not include performance data or a proof of security However a rigorous proof was published by Jonsson 24 CCM is currently the mandatory mode for the 80211 wireless standard as well as currently being considered by NIST as a FIPS standard 42 EAX Mode A to the A quot quot and A popularity of CCM three researchers decided to examine the shortcomings of CCM and see if they could be remedied Their offering is called EAX 7 and addresses several perceived problems with CCM including the following 1 1f the associated data field is fixed from message to message CCM does not take advantage of this but rather reprocesses this data anew with each invocation E0 Message lengths must be known in advance because the length is encoded into the first block before processing begins This is not a problem in some settings but in many applications we do not know the message length in advance 3 The parameterization is awkward and in particular the tradeoff between maximum message length and the size of the nonce seems unnatura H The definition of CCM especially the encodings of the parameters and length information in the message before it is processed is complex and difficult to understand Moreover the correctness of CCM strongly depends on the details of this encoding Like CCM EAX is a combination of a type of CBC MAC and CTR mode encryption However unlike CCM the MAC used is not raw CBC MAC but rather a variant Two wellknown problems exist with CBC MAC 1 all messages must be of the same fixed length and 2 that length must be a positive multiple of n If we violate the first property security is lost Several variants to the CBC MAC have been proposed to address these problems EMAC 931 adds an extra blockcipher call to the end of CBC MAC to solve problem Not to be confused with the AE mode of the same name above XCBC 12 solves both problems 1 and 2 without any extra blockcipher invocations but requires k 2n key bits Finally OMAC 23 improves XCBC so that only k bits of key are needed The EAX designers chose to use OMAC with an extra input called a tweak which allows them to essentially get several different MACs by using distinct values for this tweak input This is closelyrelated to an idea of Liskov Rivest and Wagner who introduced tweakable block ciphers 30 We now describe EAX at a high level Unlike CCM the only EAX parameters are the choice of block cipher which may have any block size n and the number of authentication tag bits to be output 739 To invoke EAX we pass in a nonce N E E a header H E 2 which will be authenticated but not encrypted and the message M E 2 which will be authenticated and encrypted and finally the key K appropriate for the chosen block cipher We will be using OMAC under key K three times each time with a different tweak written OMAC OMAC and OMACi it7s conceptually easiest to think of these three OMAC invocations as three separate MACs although this is not strictly true First we compute ctr lt7 OMACN to obtain the counter value we will use with CTR mode encryption Then we compute 0H lt7 OMACH to get an authentication tag for H Then we encrypt and authenticate M with C lt7 OMAC CTRrM And finally we output the rst 739 bits of a ctrEB CGBUH as the authentication tag We also output the nonce N the associated data H and the ciphertext C The decryption and verification steps are quite straightforward Note that each of the problem areas cited above have been addressed by the EAX mode no restriction on message length no interdependence between the tag length and maximum message length a performance savings when there is static header data and no need for message length to be known up front Also EAX is arguably simpler to specify and implement Once again proving EAX secure is more dif cult than just appealing to proofs of security for genericallycomposed schemes since the key K is reused in several contexts which is normally not a safe practice 43 CWC Mode The CWC Mode 28 is also a twopass mode it uses a Wegman Carter MAC along with CTR mode encryption under a common key K Its main advantage over CCM and EAX is that it is parallelizable whereas the prior two are not due to their use of the inherentlysequential CBC MAC type algorithms Also CWC strives to be very fast in hardware a consideration which was not given nearly as much attention in the design of the other modes In fact the CWC designers claim that CWC should be able to encrypt and authenticate data at lOGbps in hardware whereas CCM and EAX will be limited to about 2Gbps because of their serial constraints As we discussed above in the section on generic composition Wegman Carter MACs require one specify a family of hash functions on a common domain and range Typically we want these functions to 1 be fasttocompute and 2 have a low collision probability The CWC designers also looked for a family with additional properties 3 parallelizability and 4 good performance in hardware The function family they settled on is the wellknown polynomialhash Here a function from the family is named by choosing a value for z in some speci ed range and then the polynomial leiY2zH YizYi1 is computed modulo some integer typically a prime The speci c family chosen by the CWC designers xes Y1 Y to be 96bit integers and Yg1 to be a 127bit integer their values are determined by the message being hashed The modulus is set to the prime 2127 7 1 Although it is possible to evaluate this polynomial quickly on a serial machine using Hornerls Method and in fact this may make sense in some cases it is also possible to exploit parallelism in the computation of this polynomial Assume n is odd and set m n 7 1 and y 12 mod 2127 7 1 Then we can rewrite the function above as Ylym Ysym l Yi 1 Y2ym Y4ym 1 Yul mod 2127 71 This means that we can subdivide the work for evaluating this polynomial and then recombine the results using addition modulo 2127 7 1 Building a MAC from this hash family is fairly straightforward and therefore CWC yields a parallelizable scheme since CTR is clearly parallelizable The CWC designers go on to provide benchmark data to compare CCM EAX and CWC on a Pentium III showing that the speed differences are not that signi cant However this is without exploiting any parallelism available with CWC They do not compare the speed of CWC with that of OCB where we would expect OCB to be faster even in parallel implementations WC comes with a rigorous proof of security via a reduction to the underlying 128bit block cipher typically ABS and the paper includes a readable discussion of why the various design choices were made In particular it does not suffer from any of the abovementioned problems with CCM 5 AE Primitives Every scheme discussed to this point has been a mode of operation In fact with the possible exception of some of the MAC schemes every mode has used a block cipher as its underlying primitive In this section we consider two recentlydeveloped modes which are stream ciphers which provide authentication in addition to privacy That is to say these are primitives which provide AE This immediately means there is no proof of their security nor is there likely to ever be one The security of primitives is usually a matter of opinion does the object withstand all known attacks Has it been in use for a long enough time Have good cryptanalysts examined it ith new objects it is often hard to know how much trust to place in their security Sometimes the schemes break and sometimes they do not We will discuss two schemes in this section Helix and SOBER 128 Both were designed by teams of experienced cryptographers who paid close attention to their security as well as to their ef ciency 51 Helix Helix was designed by Ferguson Whiting Schneier Kelsey Lucks and Kohno 17 Their goal was to produce a fast simple patentfree stream cipher which also provided authentication The team claims speeds of about 7 cycles per byte on a Pentium 11 which is quite a bit faster than the fastestknown implementations of ABS which run at about 15 cycles per byte At rst glance this might be quite surprising after all AES does about 160 table lookups and 160 32bit XORs to encipher 16 bytes This means AES uses about 10 lookups and 10 XORs per byte As we will see in a moment Helix uses more operations than this perbyte But a key difference is that AES does memory lookups from large tables which perhaps are not in cache whereas Helix con nes its work to the register le Helix takes a key K up to 32 bytes in length and a 16byte nonce N and a message M 6 28 As usual K will allow the encryption of a large amount of data before it needs to be changed and N will be issued anew with each message encrypted never to repeat throughout the life of K Helix uses only a few simple operations addition modulo 232 exclusiveor of 32bit strings and bitwise rotations However each iteration of Helix called a block uses 11 XORs 12 modular additions and 20 bitwise rotations by xed amounts on 32bit words So Helix is not simple to specify instead we give a highlevel description Helix keeps its state in ve 32bit registers the designers were thinking ofthe lntel family of processors The ith block of Helix emits one 32bit word of keystream Si requires two 32bit words scheduled from K and N and also requires the ith plaintext word Mi It is highlyunusual for a stream cipher to use the plaintext stream as part of its keystream generation but this feature is what allows Helix to achieve authentication as well as generating a keystream As usual the keystream is used as a onetime pad to encrypt the plaintext In other words the ith ciphertext block Ci is simply Mi 69 Si The 5word state resulting from block 239 is then fed into block i 1 and the process continues until we have a long enough keystream to encrypt M At this point a constant is XORed into one of the words of the resulting state twelve more blocks are generated using a xed plaintext word based on the length of M with the keystream of the four last blocks yielding the 128bit authentication tag 52 SOBER 128 A competitor to Helix is an offering from Hawkes and Rose called SOBER 128 22 This algorithm evolved from a family of simple stream ciphers ie ciphers which did not attempt simultaneous authentication called the SOBER family the rst of which was introduced in 1998 by Rose SOBER128 retains many of the characteristics of its ancestors but introduces a method for authenticating messages as well We will not describe the internals of SOBER128 but rather describe a few of its attributes at a higher level BER128 uses a linearfeedback shift register in 39 39 with several nonlinear components in particular a carefullydesigned Sbox which lies at its heart To use SOBER 128 for AE one rst generates a keystream used to XOR with the message M and then uses a separate API call maconly to process the associated data The method of feeding back plaintext into the keystream generator is modeled after Helix and the authors are still evaluating whether this change to SOBER 128 might introduce weaknesses Tests by Hawkes and Rose indicate that SOBER 128 is comparable in speed to Helix however both are quite new and are still undergoing cryptanalytic scrutinyia crucial process when designing primitives Time will help us determine their security 6 Beyond AE and AEAD Real protocols often require more than just an AB scheme or an AEAD scheme perhaps they require something that more resembles a network transport protocol Desirable properties might include resistance to replay and prevention against packet loss or packet reordering In fact protocols like SSH aim to achieve precisely this Work is currently underway to extend AE notions to encompass a broader range of such goals 27 This is an extension to the SSH analysis referred to above 4 but considers the various EtM MtE and EampM approaches rather than focusing on just one Such research is another step in closing the gap between what cryptographers produce and what consumers of cryptographic protocols require The hope is that we will reach the point where methods will be available to practitioners which relieve them from inventing cryptography which as we have seen is a subtle area with many insidious pitfalls and yet allow them easy access to provablysecure cryptographic protocolsi We anticipate further work in this area 7 Notes on the Bibliography Note that AE and its extensions continue to be an active area of research Therefore many of the biblio graphic references are currently to unpublished preprints of works in progress It would be prudent for the reader to look for more mature versions of many of these research reports to obtain the latest revisionsi References 1 BELLARE Mi CANETTI Ri AND KRAWCZYK Hi Keying hash functions for message authentication 1n Advances in Cryptology 7 CRYPTO 96 1996 vol 1109 of Lecture Notes in Computer Science SpringerVerlag pp 1715 E BELLARE Mi DESAI Al POINTCHEVAL D AND ROGAWAY Pi Relations among notions of security for publickey encryption schemes In Advances in Cryptology 7 CRYPTO 98 1998 Hi Krawczyk Edi vol 1462 of LNCS SpringerVerlag ppi 2327249 E BELLARE Mi KILIAN Ji AND ROGAWAY Pi The security of the cipher block chaining message authentication coder Journal of Computer and System Sciences JCSS 61 3 Dec 2000 3627399 Earlier version in CRYPTO 794 See www cs ucdavis edu rogawayi E BELLARE Mi KOHNO Ti AND NAMPREMPRE Ci Authenticated encryption in SSH Provably xing the SSH binary packet protocoli 1n ACM Conference on Computer and Communications Security CCS 9 2002 ACM Press pp 1711 u l E BELLARE Mi AND NA n ma u E C A t euci ptiulli Relations among notions and analysis of the generic composition paradigmi 1n Advances in Cryptology 7 ASIACRYPT 00 2000 vol 1976 of Lecture Notes in Computer Science SpringerVerlagi E BELLARE Mi AND ROGAWAY Pi Encodethen encipher encryption How to exploit nonces or redun dancy in plaintexts for ef cient encryptioni 1n Advances in Cryptology 7 ASIACRYPT 00 2000 T Okamoto Edi vol 1976 of Lecture Notes in Computer Science SpringerVerlag ppi 3177330 See wwwcsucdavisedu rogawayi E BELLARE Mi ROGAWAY Pi AND WAGNER Di EAX A conventional authenticatedencryption model Cryptology ePrint archive reference number 2003069 submitted Apr 13 2003 revised Sep 9 2003 2003 See eprint iacrorgi E BELLOVIN Si Problem areas for the 11 security protocols In Proceedings of the Sixth USENIX Security Symposium July 1996 pp 1716 BERENDSCHOT Al DEN BOER Bi BOLY Jr BOSSELAERS At BRANDT Jr CHAUM Di DAMGARD L DICHTL Mi FUMY We VAN DER HAM Mi JANSEN Ci LANDROCK Pi PRE NEEL Bi ROELOFSEN Gr DE Room R AND VANDEWALLE Jr Final Report of Race Integrity Primitives vol 1007 of Lecture Notes in Computer Science SpringerVerlag 1995 E 10 BERNSTEIN Di Floatingpoint arithmetic and message authentication Available from httpcryptohash127htmli H 5 BLACK Jr HALEVI Si KRAWCZYK Hi KROVETZ To AND ROGAWAY Pi UMAC Fast and secure message authentication 1n Advances in Cryptology 7 CRYPTO 99 1999 Lecture Notes in Computer Science SpringerVerlagi 121 131 141 l H E l H 2 171 l H E l H 3 201 211 221 231 241 261 2 71 BLACK I AND ROGAWAY P CBC MACs for arbitrarylength messages The threekey constructions In Advances in Cryptology 7 CRYPTO 00 2000 Lecture Notes in Computer Science SpringerVerlag BLACK I AND ROGAWAY P A blockcipher mode of operation for parallelizable message authenti cation In Advances in Cryptology i EUROCRYPT 2002 2002 L Knudsen Ed vol 2332 of Lecture Notes in Computer Science SpringerVerlag pp 3847397 BLACK I AND URTUBIA H Sidechannel attacks on symmetric encryption schemes The case for authenticated encryption In Proceedings of the Eleventh USENIX Security Symposium Aug 2002 D Boneh Ed pp 3277338 BORISOV N GOLDBERG I AND WAGNER D Intercepting mobile communications The insecurity of 80211 In MOBICOM 2001 ACM pp 1807189 CARTER E AND WEGMAN M Universal hash functions J of Computer and System Sciences 18 1979 1437154 FERGUSON N WHITING D SCHNEIER B KELSEY J LUCKS S AND KOHNO T Helix Fast encryption and authentication in a single cryptographic primitive In Fast Software Encryption 10th International Workshop FSE 2005 2003 T Johansson Ed Lecture Notes in Computer Science SpringerVerlag GLIGOR V AND DONESCU P Fast encryption and authentication XCBC encryption and XECB authentication modes In Fast Software Encryption 8th International Workshop FSE 2001 2002 M Matsui Ed vol 2355 of Lecture Notes in Computer Science SpringerVerlag pp 927108 See wwweceumdedu gligor GOLDWASSER S MICALI 8 AND RIVEST R A digital signature scheme secure against adaptive chosenmessage attacks SIAM Journal of Computing 17 2 Apr 1988 2817308 H KRAWCZYK M B AND CANETTI R HMAC Keyed hashing for message authentication IETF RFC2104 1997 HALEVI S An observation regarding Jutlals modes of operation Cryptology ePrint archive reference number 2001015 submitted Feb 22 2001 revised Apr 2 2001 2001 See eprint iacr org HAWKES 13 AND ROSE G Primitive speci cation for SOBER 128 httpwwwqua1commcomauSober128htm1 Available from IWATA T AND KUROSAWA K OMAC Onekey CBC MAC In Fast Software Encryption 2003 T Johansson Ed vol 2887 of Lecture Notes in Computer Science SpringerVerlag JONSSON J On the security of CTR CBCMAC In Selected Areas in CryptographyiSAC 2002 2002 K Nyberg and H M Heys Eds vol 2595 of Lecture Notes in Computer Science Springer Verlag pp 76793 JUTLA C Encryption modes With almost free message integrity In Advances in Cryptology 7 EU ROCRYPT 2001 2001 B P tzmann Ed vol 2045 of Lecture Notes in Computer Science Springer Verlag pp 5297544 KATZ I AND YUNG M Complete characterization of security notions for probabilistic privatekey encryption In Proceedings of the 32nd Annual Symposium on the Theory of Computing STOC 2000 ACM Press KOHNO T PALACIO A AND BLACK J Building secure cryptographic transforms or how to encrypt and MAC Cryptology ePrint archive reference number 2003177 submitted Aug 28 2003 See eprint iacr org 281 291 301 311 321 KOHNO Ti VIEGA Ji AND WHITING Di Highspeed encryption and authentication A patentfree solution for 10 Gbps network devices Cryptology ePrint archive reference number 2003106 submitted May 27 2003 revised Sep 1 2003 2003 See eprint iacrorgi KRAWCZYK Hi The order of encryption and authentication for protecting communications or How secure is SSL 1n Advances in Cryptology 7 CRYPTO 2001 2001 vol 2139 of Lecture Notes in Computer Science SpringerVerlag ppi 31331i LISKOV Mi RIVEST Ri AND WAGNER Di Tweakable block ciphersi 1n Advances in Cryptology 7 CRYPTO 02 2002 Mr Yung Edi vol 2442 of Lecture Notes in Computer Science SpringerVerlag pp 317461 PETRANK El AND RACKOFF Ci CBC MAC for realtime data sources Journal of Cryptology 15 3 2000 31573380 ROGAWAY Pi Authenticatedencryption With associateddata 1n ACM Conference on Computer and Communications Security CCS Q 2002 ACM Press pp 1967205 ROGAWAY Pi BELLARE Mi AND BLACK Jr OCB A blockcipher mode of operation for ef cient authenticated encryptioni ACM Transactions on Information and System Security TISSEC 6 3 Aug 2003 3657403 WEGMAN Mi AND CARTER Li New hash functions and their use in authentication and set equality In J of Comp and System Sciences 1981 vol 22 pp 2657279 WHITING Di HOUSLEY R AND FERGUSON Ni Counter with CBCMAC COM June 2002 Available from csrc nist govencrypt ionmodesproposedmodesi
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'