This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

Loading...

From the course by University of Maryland, College Park

Cryptography

417 ratings

This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

From the lesson

Week 3

Private-Key Encryption

- Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center

Maryland Cybersecurity Center

[SOUND] In the last lecture,

Â we saw an example of a CPA-secure encryption

Â scheme based on any block cipher or PRF.

Â And just to remind you of what that scheme looked like.

Â There we had the encryption of a message m, using a key k,

Â being done by having the sender first choose a random value r,

Â and then send r, along with Fk of r, XORed with m.

Â And note here that m, is a one block plain text where the block here refers

Â to the block length of the pseudorandom function F, and this results in

Â a two-block ciphertext, that is, if we let the block length of F be n bits,

Â then the message m is an n-bit string, and the ciphertext is a 2n-bit string.

Â And in fact, as we defined it encryption was only defined for n-bit messages.

Â Now, in general, we'd like to have a scheme that can support encryption of

Â messages of arbitrary length, not just n-bit messages.

Â And we can do that very easily.

Â So remember that CPA-security, implies secrecy for

Â the encryption of multiple messages.

Â This is something that we stated in a previous lecture,

Â even though we didn't prove it.

Â Now, what that means is that we can encrypt a long message,

Â by simply breaking it up into a sequence of n-bit chunks, and

Â then applying the encryption scheme from the previous slide to each chunk.

Â That is, we'll take our message, and we'll split it into a sequence of blocks m1,

Â m2 et cetera up to mt.

Â And then we take each block, and encrypt it using the CPA secure encryption scheme

Â from last time, and it follows because the encryption scheme is CPA secure.

Â And therefore, is secure even when used to encrypt multiple messages.,

Â using the same key, that this new encryption scheme defined now for

Â arbitrary length messages is also CPA secure.

Â It might be easier to think about what's going on by looking at a figure.

Â So here, we have our sender and receiver sharing a key k,

Â and the way I've depicted it here, we have the sender sending different messages

Â m1 through mt by encrypting each one using the encryption scheme, and

Â then sending the corresponding cypher text c1 through ct.

Â And again, because the encryption scheme is CPA secure, that means that

Â the encryption scheme is also secure when used to encrypt multiple messages,.

Â And therefore that an attacker, who observes all the cypher texts being sent

Â across the channel, doesn't learn any information about m1 through mt.

Â Now all we need to do here is to change our viewpoint.

Â And rather than viewing the m1 through mt as messages in their own right,

Â we view them simply as blocks that comprise one longer message,

Â composed of the blocks m1 through mt.

Â And then the cipher text that the attacker sees now becomes just one

Â long cipher text containing t cipher text blocks, rather than t different cipher

Â texts each corresponding to a different underlying message.

Â But intuitively this still hides all information about m1 through mt,

Â and is therefore secure as an arbitrary lang-,

Â encryption scheme, that is,

Â as an encryption scheme, that can encrypt arbitrary length messages.

Â Now we can do that to encrypt messages as long as we like, but there's a drawback.

Â So remember that in the underlying encryption scheme, the one that's applied

Â to each block of plaintext, the ciphertext is twice the length of a plaintext.

Â And what that means,

Â is that when we encrypt this longer message, composed of these many blocks,

Â we get a ciphertext twice the length of the underlying plaintext.

Â That is, the ciphertext expansion, with the amount by

Â which the ciphertext is longer than the plaintext is a factor of two.

Â The ciphertext is twice as long as the plaintext.

Â And the natural question is, can we do better?

Â And this brings us to the topic of modes of operation,

Â which are more efficient mechanisms for encrypting arbitrary-length messages.

Â Now just to be clear on the terminology, there are stream cipher modes of

Â operation that are based on an underlying stream cipher, or pseudorandom generator.

Â There are two flavors of stream cipher modes of operation

Â synchronized and unsynchronized.

Â But unfortunately due to lack of time we're not going to cover any of these,

Â instead we're going to just look at block cipher modes of operation.

Â These are modes of operation that of course are built on some underlying block

Â cipher, or pseudorandom function.

Â The first one I want to introduce you to, is called counter mode, or CTR mode.

Â We're going to assume for simplicity, that all messages we want to encrypt,

Â are exact multiples of the block length of our block cipher.

Â And in practice, they may, that may not need, that may not be the case, and

Â it can be handled, but we're just assuming that for simplicity here.

Â So counter mode is defined in the following way.

Â To encrypt a message composed of a sequence of blocks, m1 thought mt,

Â what we do is we first choose a uniform n bit string as a counter.

Â And we set c0, which is going to be the initial block of our ciphertext,

Â equal to that initial counter value.

Â Then, for i equals 1 to t, where t denotes the number of blocks of plaintext that we

Â have, we compute the ith block of the ciphertext to be equal to,

Â the XOR of the ith block of plaintext with fk evaluated on counter plus i.

Â So basically what we're doing is we're simply incrementing this counter, and

Â applying our PRF F sub k, to the values counter plus

Â 1 counter plus 2 et cetera, all the way up to counter plus t.

Â And then taking those results and

Â XORing each of those with a corresponding block of plain text.

Â The ciphertext that we output, contains all the blocks C0 though CT.

Â Note that the ciphertext expansion here, is just a single block.

Â So rather than doubling the length of the plain text,

Â we simply increase the length of the plain text, by n bits.

Â It may be easier to think about counter mode by looking at a picture, and

Â here I've depicted such, such a, the operation of counter mode.

Â Where, at the top I've listed the value that

Â are passed into the pseudorandom function that is counter one

Â through counter sorry counter plus one through counter plus t.

Â Each of those values has passed its input to the pseudorandom function, and

Â the output is then XORed with the corresponding message block,

Â to give the cypher text block.

Â In addition, we include the value c0,

Â which is equal to the initial counter value, to allow the receiver to decrypt.

Â What can we say about the security of Counter mode?

Â Well in fact, it's possible to prove that if F is a pseudorandom function,

Â then Counter mode is CPA-secure.

Â We could actually give a quick proof sketch of this.

Â I'm not going to go through the details of the proof,

Â but the proof sketch is actually very similar to what we've seen before, for

Â the proof of CPA security of this scheme last time.

Â So, for simplicity in the proof,

Â let's just assume that all messages that are being encrypted have length t.

Â This is not at all necessary, it just simplifies the exposition here.

Â Now, when we encrypt the ith message, what the sender does is to choose a counter,

Â that I'll refer to as counter i, and then use the values counter i

Â plus 1 up to counter i plus t, as inputs to the pseudorandom function.

Â And what you can observe is that the sequence of outputs,

Â the values Fk of counter i plus 1 up to Fk of counter i plus t,

Â that sequence is pseudorandom, when looked at in isolation.

Â And this is just because we're applying the pseudorandom function to a sequence of

Â distinct inputs.

Â Note here that it's important that the length of our counter is n bits, and so

Â it can support up to two to the n values,

Â ranging from zero up to two to the n minus 1.

Â And so because t is going to be much, much smaller than two to the t,

Â we're not going to get any wrap around so we're not going to

Â get any two equal values being passed as input to the pseudorandom function.

Â Now the important thing to note here, is that this pseudo random sequence is

Â going to be independent for every message being encrypted.

Â Unless it happens to be the case, that there are two inputs to

Â the pseudorandom function that happen to be equal.

Â That will occur if and

Â only if counter i plus j is equal to counter i prime, the counter chosen for

Â some other message plus j prime, for some values i, j, i prime j prime.

Â You can do the calculation and

Â show that that will occur only with negligible probability.

Â And again here, it's important for that that our block length if n gets long, and

Â so the probability of such a collision occurring,

Â is going to be exponentially small in n.

Â Another mode that's quite popular and used a lot in the real world is CBC mode.

Â This stands for cipher block chaining mode.

Â And this mode works in the following way.

Â So now to encrypt a message consisting of blocks m1 through mt as before,

Â what the sender then does is choose a random value, c0,

Â that's sometimes also called the IV, or initialization vector.

Â And then for i equals 1 to t, the sender computes the ith block of the cipher text,

Â to be equal to F K, applied to the next message block,

Â mi, XORed with the previous ciphertext blocks, ci minus 1.

Â The resulting ciphertext consists of the t plus 1 blocks, c0 through ct.

Â And note that the ciphertext expansion again, here,

Â is just a single block, so we've only increased our plaintext by end bits.

Â One thing to note here, is that decryption requires F to be invertible.

Â This was not the case for counter mode, where the receiver only needed to

Â evaluate F in the forward direction to decrypt for CBC mode,

Â the receiver is also required to evaluate F in the reverse direction as well.

Â Fortunately blockcyphers are invertible and

Â so they can be run in the reverse direction, and so

Â CBC mode can be decrypted when using a pseudorandom permutation.

Â Here it is in pictures, which especially for

Â CBC mode, makes things easier to understand.

Â So I've just indicated here that we choose this random IV, or initialization vector,

Â and that becomes the first block of the cypher text, and then we simply

Â chain every preceding cipher text block, and XORed with the next message block.

Â So you can see that C0 for example is XORed with M1, and

Â the result is then passed as input to Fk to give the cipher text block C1.

Â And so on up through the final block of plaintext.

Â The theorem that we can show about CBC mode,

Â is that if F is a pseudorandom function, then CBC mode is CPA-secure.

Â I will say that the proof here is much more complicated than for the case of

Â counter mode, nevertheless, this is something that we can that can be shown.

Â Now I wanted to look next at an example of an insecure mode of

Â encrypt by mode of operation, and that's ECB mode or electronic code book mode.

Â I mentioned this one because it's a mode that was standardized in 1977, before

Â people really had a good idea of the security notions that are used nowadays.

Â Never the less, you, sometimes you want to counter this mode in proactice and,

Â I want to warn you agaisnt using it.

Â So in ECB mode, the encription of a message again consisting of blogs and

Â one to m t, is done by simply applying the pseudorandom function,

Â to each message block individualy.

Â That is, the encription of m-1 through mt, is just given by Fk of m1 up to Fk of mt.

Â Now this might look great because there's no cypher text expansion at all, but

Â of course we know, that because this scheme is deterministic, right?

Â There's no randomness here, this scheme cannot possibly be CPA secure.

Â In fact it's even worse than that, right?

Â If you look at the way encryption is done,

Â you can see very clearly that if two plain text blocks, mi and

Â mj are equal, then that will show up as two equal blocks of ciphertext.

Â That is, given a long ciphertext,

Â an attacker can tell when there are repeated blocks in the plain text.

Â So that means that ECB mode encryption will not even

Â satisfy our original notion of indistinguishable encryptions, that is,

Â it won't even be secure for the encryption of a single message.

Â Now you might wonder whether this is just an academic issue and

Â whether perhaps ECB mode is okay, if used in practice.

Â I'll warn you now that that's not the case.

Â And here's a really great demonstration of that.

Â So here we have an image that we're going to encrypt using ECB mode.

Â Each pixel of that image is going to be represented

Â by a a one block value, that is, what we're going to be doing to encrypt this,

Â is we're going to be flattening the image, and taking each pixel as it were and

Â viewing that as a block.

Â And then passing that block through our,

Â through our pseudorandom function to give us a cypher text block.

Â If we do that we get something like the following.

Â Now, you'll notice that although parts of the image are obscured, and

Â you certainly could not reconstruct the entire image from the ciphertext, you can

Â also clearly see that the image itself is not being hidden completely, there's

Â a lot of information about the original image being revealed in a ciphertext.

Â And this is just an indication of the problems that can arise from the fact that

Â repeated blocks of plain text, can be detected as repeated blocks of ciphertext.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.