CAB340: Stream ciphers, Block ciphers, Modes of Operation, Applications - Engineering Assignment Help

Assignment Task:

1 LFSRs found in real systems 

The Content Scrambling System (CSS) is a protocol that 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 long, and one 25 bits long. The 40-bit key is loaded directly into the LFSRs, 2 bytes into the first LFSR, 3 bytes into the second LFSR, with the one remaining bit in each register then set to 1 (thereby preventing the all-zero state from which an LFSR can’t escape). The outputs of the LFSRs are then combined to 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) Hint: how many states each LFSR can possibly be in, minus any state(s) that cannot possibly be part of a long “cycle”. 

b. If we have two periodic functions f(t) and g(t) and consider the function h(t)=(f(t),g(t)), then h will have period pq gcd(p, q) where p and q are the period of f and g, respectively, and gcd is the greatest common divisor. Apply this principle 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. CSS was an “epic failure” of security! Do some reading and write one sentence or short paragraph about some decision(s) around CSS which led to its eventual break. (1 mark) 

e. Discuss in one paragraph why the very concept of Digital Rights/Restrictions Management (DRM) is in- herently flawed from a cryptographic point of view. Reason in general terms, or in relation to movie/music distribution if you prefer—but not specifically about the CSS cipher. You may find it useful to contrast what DRM is trying to do with Kerkhoffs’ principles for sound cryptographic design. (1 bonus mark) 

2 Do common block modes protect against cipher linearity? 

In this task, we shall study how inherent weaknesses of block ciphers, such as linearity, manage to affect or not affect the security of their use in otherwise secure modes of operation. 

Remember the Hill cipher: the Hill cipher is essentially a block cipher operating on plaintext and ciphertext blocks of length d, and where the key is a d × d matrix. Encryption and decryption are linear, given by the equations 

c = K · p (mod N) 

and 

p = K−1 · c (mod N) 

where p and c respectively represent one block (i.e., a vector of d alphabet symbols) of plaintext and ciphertext, and K is some secret d × d invertible matrix serving as the key. For convenience the Hill cipher alphabet is written as the set of integers modulo N, so all computations are done modulo N. 

Historically the Hill cipher was used to encrypt each block of plaintext separately, which amounts to the ECB mode of operation. This is to say that the known-plaintext attacks against the Hill cipher seen in the first lecture and the first assignment (where knowing d blocks of plaintext and ciphertext allows us to solve for and recover K) were really attacks against the Hill cipher operating in ECB mode, or against “Hill-ECB” for short. 

In principle the Hill cipher could be used in other modes, and it could be used on a binary alphabet. In this question we’ll see that other modes of operation hardly make the Hill cipher harder to break. In this question we’ll be using the d-bit binary Hill cipher (i.e., a Hill cipher operating on a binary alphabet with blocks as vectors of d bits) as the core cipher algorithm, and operate it in other modes as indicated. 

a. Consider using this cipher as a block cipher in CTR mode. Write out the explicit formulas for the first three ciphertext blocks (call them c1, c2, c3) in terms of the key (some d × d invertible binary matrix K) and of the first three plaintext blocks (call them p1, p2, p3). Assume that d is even, and that the nonce and counter both are vectors of d/2 bits. (1 mark) 

Hint: if the nonce is r and counter t, you may have a use for their concatenated d-vector (n t)T = (nt). 

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) Hint: “reducing” an attack on Hill-CTR to an attack on Hill-ECB simply means that you should show how to break Hill-CTR assuming you already have a working algorithm that breaks Hill-ECB (here under a known-plaintext attack)—i.e., you need to figure out a way to “feed” that algorithm you have. 

c. Imagine using a Hill cipher as a block cipher in CBC mode. Write out the explicit formulas for all the ciphertext blocks in terms of the key and plaintext blocks, if the plaintext consists of three full blocks (p1,p2,p3). (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 functions 

Recall the Merkle-Damgård construction, which uses a compression function f : A × A → A for some set A, such as A = {0,1}l for a compression with 2l bits of input and l bits of output. A basic version is given by: 

W0 = IV W1 = 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 here is a constant. 

a. Write down the simplest way you can think of to use AES-128 as the compression function in this construction. (Hint: use one AES-128 encryption with no additional functions or operators.) (1 mark) 

b. To achieve security, f must be a one-way function, meaning that given f(m1,m2) it should be very difficult to find any new information about (m1,m2). For example, if m1 is known, it should still be difficult to find m2 and vice versa. Does your suggestion for the previous question satisfy this requirement? Why or why not? (1 mark) 

c. Modern hash functions have 256-bit outputs or more. Discuss how the security of your construction from AES-128 compares to modern hash functions with regards to collision resistance. (1 mark) 4 Message authentication codes 

a. It is in principle possible to create a hash function by using a block cipher in CBC-MAC mode with (published) fixed IV and fixed key. 

i. Discuss how to find a single-block message m that hashes to a given digest d. In other words, show that this hash function is not preimage resistant. (Hint: explicitly write out the hash formula for a single-block message m, and try to “solve” for m given the hash output d.) (1 mark) ii. Extend your attack to find a preimage of a given digest d, as a message m of any specified length n. 

(1 mark) 

b. Padding can affect cryptography in surprising and subtle ways. Consider the following padding scheme for a CBC-MAC. We are given a message m1m2 ...mn where mj is a full block for j<n, and the length of 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’s to the end of mn until it is a full block. In either situation we apply CBC-MAC (the real CBC-MAC, not as above) to the resulting (padded) message. 

i. Suppose that an adversary obtains a message and the CBC-MAC tag for that message. The message is not an integer number of blocks in length, so let’s assume that the above padding scheme was used when creating the tag. Explain how the adversary can then easily construct another message which will givee the same tag for the same key. (1 mark) 

ii. Now suppose that the adversary is instead given a message which is an integer number of blocks in length. Explain a similar attack to the one above, and state any additional conditions that the message has to satisfy for the attack to succeed. (1 mark) iii. Suggest a different padding method that is secure against attacks similar to those you have given above. (1 bonus mark) 

c. The block cipher mode XCBC has been proposed to defeat the length extension attacks against CBC-MAC discussed in the tutorial. XCBC is defined by: 

m n = {mn ⊕ k2 when |mn| = d P(mn) ⊕ k3 when |mn| < d tag = 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/to Part b of Exercise 4 (CBC-MAC) of Tutorial #5 (“Cryptographic Hashing and MACs”). Feel free to refer directly to or copy the relevant part from the tutorial’s written solutions, and modify as needed. (1 mark) ii. Explain what would happen to security if instead of distinct k2 and k3 we had k2 = k3, so that mn ended up being modified in the same way regardless of whether it was padded. (1 mark) 

5 Proofs of Work 

Bitcoin uses a proof-of-work (PoW) mechanism to adjudicate which participant or “miner” gets to publish the next block of transactions on the blockchain and claim the reward for doing so. Having verified and packaged a set of new transactions to form a new block, a miner would search for an arbitrary string Nonce, such that, 

H(previousBlock, newT ransactions, N once) = 00...0 } {{ } δ bits 

xy...z 

for a specified “difficulty” parameter δ given a hash function with l bits of output. The difficulty parameter δ is intended to require 2δ distinct attempts on average before satisfying the condition. 

a. Express in function of δ the minimum and/or maximum hash output size l that is required for such PoW to work as intended. (1 mark) In words, provide a brief justification for your answer. (1 bonus mark) Hint: if this helps, think of H as a magic function that outputs a truly random value every time it is called on a new input, and remembers all its answers so it can answer consistently on repeated inputs. (Cryptographers often use this idealisation of hash functions, which is known by the technical name of “random oracle”.) 

b. Now suppose that there is a mistake in the design of H, that make it easy to construct collisions—but not to find second preimages or invert the hash, which are still hard. Could such H still possibly work for the PoW application? (1 mark) 

c. Same question, except that this time we assume that H is not a cryptographic hash, but a linear function (such as the CRC used in WEP). Could such H still possibly work for the PoW application? (1 mark) 

This Engineering Assignment has been solved by our Engineering Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.