- May 15, 2020

CAB340 Assessment 2Stream ciphers, block ciphers and hash functions1 LFSRsThe Content Scrambling System (CSS) is a protocol which was used for digital rights/restrictions management(DRM) for DVDs. Its design consists of a synchronous stream cipher built from two LFSRs, one 17 bits longand one 25 bits long. The 40-bit key is loaded directly into the LFSRs, 2 bytes into the first LFSR and 3 bytesinto the second LFSR with the remaining bits in each set to 1. The outputs of the LFSRs are then combinedto produce the keystream. (Note: some details are left out which are not important for this discussion.)a. What is the maximum possible period of each LFSR? (1 mark)b. If we have two periodic functions f(t) and g(t) and consider the function h(t) = (f(t), g(t)), then h willhave periodpqgcd(p, q)where p and q are the period of f and g, respectively, and gcd is the greatest common divisor. Apply thisprinciple to explain why CSS was chosen to have different lengths for the two LFSRs. (1 mark)c. What is the brute force attack complexity for this cipher? (1 mark)d. Imagine a similar cipher which uses the same method of loading the key and simply XORs the outputsof each LFSR to produce the keystream. Explain how this fictitious cipher leaks easy information aboutthe key into the keystream (1 mark) and suggest a known-plaintext attack that retrieves the key withcomplexity around 224 or less (1 mark).e. CSS was an epic security fail. Do some reading and write one paragraph about the decisions around CSSwhich led to its eventual break. Alternatively, discuss in one paragraph why the very concept of DRM isinherently flawed from a cryptographic point of view. (1 mark)2 Linearity in block ciphersIn this task, we shall study how inherent weaknesses of block ciphers, such as linearity, manage to affect or notaffect the security of their use in otherwise secure modes of operation.The Hill cipher is essentially a block cipher operating on blocks of length d where the Hill cipher key is a d× dmatrix. The known plaintext attacks considered in the previous assignment are essentially attacks on the Hillcipher operating in ECB mode, but in principle the Hill cipher could be used in other modes, and it could beused on a binary alphabet.a. Imagine using such a Hill cipher (binary alphabet, d-bit blocks), as a block cipher in CTR mode. Writeout the explicit formulas for the first three ciphertext blocks (call them c0, c1, c2) in terms of the key (thed × d-matrix M) and first three plaintext blocks (call them p0, p1, p2). Assume that d is even and thenonce (call it n) and counter (call it c) both have length d/2 (i.e., consist of d/2 bits each). (1 mark)b. Explain how to launch a known plaintext attack against a Hill cipher used in CTR mode. More specifically,show how you can reduce this problem to the known-plaintext attack against Hill cipher in ECB mode.(1 mark)c. Imagine using a Hill cipher as a block cipher in CBC mode. Write out the explicit formulas for the firstthree ciphertext blocks in terms of the key and first three plaintext blocks. (1 mark)d. Explain how to launch a known plaintext attack against a Hill cipher used in CBC mode. More specifically,show how you can reduce this problem to the known-plaintext attack against Hill cipher in ECB mode.(1 mark)3 Using block ciphers in hash functionsRecall the Merkle-Damgard construction, which uses a compression function f : A×A→ A. A basic version isgiven by:W0 = IVW1 = f(W0,m1)W2 = f(W1,m2)…Wn = f(Wn−1,mn)where Wn is the output of the hash function, m1m2 . . .mn is the message and IV is a constant.a. Discuss the simplest way you can think of to use AES-128 as a compression function in such a construction.(1 mark)b. To achieve security, f must be a one-way function, meaning that given f(m1,m2) it should be very difficultto find any new information about (m1,m2). For example, if m1 is known, it should still be difficult tofind m2 and vice versa. Does your suggestion for the previous question satisfy this requirement? Why orwhy not? (1 mark)c. Modern hash functions have 256-bit outputs. Discuss how the security of your construction compares tomodern hash functions with regards to collision resistance. (1 mark)4 Message authentication codesa. It is in principle possible to create a hash function by using CBC-MAC with a constant, public key.i. Discuss how to find a single-block message m that hashes to a given digest d. I.e. show that thishash function is not pre-image resistant. (1 mark)ii. Extend your attack to find a message of a given length n. (1 mark)b. Padding can affect cryptography in surprising and subtle ways. Consider the following padding schemefor a CBC-MAC. We are given a message m1m2 . . .mn where mj is a full block for j < n, and the lengthPage 2of mn is at most the length of a full block. If mn is a full block then it is left alone. Otherwise we add 0’sto the end of mn until it is a full block. In either situation we apply CBC-MAC to the resulting (padded)message.i. Suppose that an adversary obtains a message, which is not an integer number of blocks in length,and the CBC-MAC tag for that message assuming the above padding scheme. Explain how it ispossible to easily construct another message which gives the same tag for the same key. (1 marks)ii. Now suppose that the adversary is instead given a message which is an integer number of blocks inlength. Explain a similar attack to above, and state any additional conditions that the message hasto satisfy for the attack to succeed. (1 mark)iii. Suggest a different padding method that is secure against attacks similar to those you have givenabove. (1 mark)c. The block cipher mode XCBC was proposed to defeat the length attacks against CBC-MAC discussed inthe tutorial. XCBC is defined by:m′n ={mn ⊕ k2 when |mn| = dP (mn)⊕ k3 when |mn| < dtag = CBC-MAC(m1m2 . . .m′n, k1)where the message is m1m2 . . .mn, P is a padding function, |mn| the is number of bits in the last block,d is the size of the blocks for the block cipher, and k1, k2, k3 are secret keys.i. Explain why this modification defeats the attack outlined/explained in the question/solution of Ex-ercise 3b of the week 06 tutorial (on “Cryptographic Hashing and MACs”). (1 mark)ii. Explain what would happen to security of we instead had k2 = k3, so that mn was modified in thesame way, regardless of whether it was padded. (1 mark)Page 3