In order to make sense of some of the things we mentioned in class, it is useful to see them in action on image files; for we, as humans, are quite good at visually detecting patterns in an array of pixels. This "cloud" interface to Sage is somewhat similar to the regular "notebook" one; use SHIFT+ENTER (or the green "Run" button above) to evaluate a cell.

In order to make sense of some of the things we mentioned in class, it is useful to see them in action on image files; for we, as humans, are quite good at visually detecting patterns in an array of pixels. This \"cloud\" interface to Sage is somewhat similar to the regular \"notebook\" one; use SHIFT+ENTER (or the green \"Run\" button above) to evaluate a cell.

\n\nInternally, it's just a $288 \times 460$ matrix of pixels, each of which is colored according to a RGB triple of integers between 0 and 255:

︡c9bb0a9e-5910-4c22-a685-aff163f13caa︡{"html": "Internally, it's just a $288 \\times 460$ matrix of pixels, each of which is colored according to a RGB triple of integers between 0 and 255:

"}︡ ︠ec14659c-5703-4e0e-b6aa-552610609e8e︠ m.size() ︡aa98e83e-f4d1-4ce0-8135-854bad25ba51︡{"stdout":"(288, 460)\n"}︡ ︠5f9e5c7d-ea6c-4305-8b1f-627c9074970d︠ m.data ︡ab1dfa30-d7fe-4b8a-abde-05c16099c73b︡{"stdout":"array([[[126, 157, 186],\n [200, 231, 255],\n [169, 199, 233],\n ..., \n [ 33, 49, 20],\n [ 83, 98, 59],\n [ 72, 88, 43]],\n\n [[ 94, 125, 154],\n [145, 176, 207],\n [143, 173, 207],\n ..., \n [128, 143, 114],\n [ 19, 34, 0],\n [140, 155, 112]],\n\n [[ 28, 59, 90],\n [ 18, 49, 80],\n [ 25, 55, 89],\n ..., \n [ 47, 62, 33],\n [ 70, 84, 48],\n [202, 217, 176]],\n\n ..., \n [[163, 195, 94],\n [164, 196, 95],\n [170, 202, 101],\n ..., \n [162, 197, 97],\n [162, 197, 97],\n [156, 191, 91]],\n\n [[168, 200, 99],\n [166, 198, 97],\n [173, 205, 104],\n ..., \n [152, 187, 87],\n [154, 189, 89],\n [152, 187, 87]],\n\n [[154, 186, 85],\n [152, 184, 83],\n [164, 196, 95],\n ..., \n [161, 196, 96],\n [162, 197, 97],\n [159, 194, 94]]], dtype=uint8)\n"}︡ ︠0944be6f-6fb2-4e70-8028-885e8e7254dfi︠ %htmlRecall that the goal of encryption would be to reversibly make it look like a random image of the same size just like this one:

︡d223176d-980c-463c-9276-3331a7ec030c︡{"html":"Recall that the goal of encryption would be to reversibly make it look like a random image of the same size just like this one:

\n\n"}︡ ︠019c3de0-4945-4738-af17-257f59c26ed0︠ RandomImage(288,460) ︡b3093352-f0ce-4a93-8ab0-0ef7e65e2002︡{"once":false,"file":{"show":true,"uuid":"d5c13118-dff2-45e4-9878-0d1cc4e63a73","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠3d7ef8f4-a16d-4818-b8df-2050963ae49ai︠ %htmlAs a single pixel is encoded on $3 \times 8 = 24$ bits, a $4 \times 4$ block of pixels is encoded on $16 \times 24 = 384$ bits, which give us more than enough room to store a secure symmetric encryption key.

︡305cf135-eaf0-4261-a68a-96eec1a53948︡{"html":"As a single pixel is encoded on $3 \\times 8 = 24$ bits, a $4 \\times 4$ block of pixels is encoded on $16 \\times 24 = 384$ bits, which give us more than enough room to store a secure symmetric encryption key.

\n\n"}︡ ︠35bfa487-df15-42b4-9cc2-add172c5846b︠ k = RandomImage(4,4); k ︡57f3f616-c465-4c5c-8d1b-49b749201950︡{"once":false,"file":{"show":true,"uuid":"95cb6359-11c9-42d1-a832-9d27c2796456","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠4f5f1694-0b10-4f35-bebc-4772b2120449︠ pad = Image(numpy.tile(k.data, (288/4,460/4,1))) pad ︡0bbf4997-59de-4265-a2fc-89a35ccad388︡{"once":false,"file":{"show":true,"uuid":"f5d7c1fc-fc23-4594-b85f-75276bf4490e","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠957b8d9e-1ff1-4df9-908f-323eabfabdb5i︠ %htmlEt voilà! Here's the picture, encrypted by a 384-bit key:

︡21d97014-f5ce-4384-8ea0-dc3f781db581︡{"html":"Et voilà! Here's the picture, encrypted by a 384-bit key:

\n\n"}︡ ︠4118d419-318f-4f3e-8fb7-640e5ab70691︠ m + pad # pixel values are xor-ed together ︡b062a9b8-e0cf-4812-8819-130d6bd11d2e︡{"once":false,"file":{"show":true,"uuid":"eff4d992-41d7-4c10-a268-212a7f03819a","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠1b2893c4-aa37-4276-9bab-c1904460bd6bi︠ %htmlDiscuss the result. Would you say that this cipher provides perfect secrecy?

︡04ed01da-2d5f-4073-81e9-54c4100dc780︡{"html":"Discuss the result. Would you say that this cipher provides perfect secrecy?

\n\n\n\n\n\n\n\n"}︡ ︠41c5fd8c-10b2-4d2d-9edd-a1a804370ee5i︠ %htmlThis scheme certainly does not provide perfect secrecy, as we cleary recognize some features of the original image leaking into the ciphertext (structure of the mansion, patches of grass and sky...). In particular, note that repeating blocks in the plaintext yield repeating blocks in the ciphertext, thus breaking semantic security.

The problem is that the $\color{blue} 4 \times 4$ key is a perfectly good one-time pad that provides 384 bits of security if used to mask a *single* $\color{blue} 4 \times 4$ image block; but it is used here to encrypt $\color{blue} 72 \times 115 = 8280$ such blocks, thus providing (*cf.* discussion of the many-time pad) an effective $\color{blue} 384/8280 \approx 0.05$ bit of security...

This scheme certainly does not provide perfect secrecy, as we cleary recognize some features of the original image leaking into the ciphertext (structure of the mansion, patches of grass and sky...). In particular, note that repeating blocks in the plaintext yield repeating blocks in the ciphertext, thus breaking semantic security.

\n\nThe problem is that the $\\color{blue} 4 \\times 4$ key is a perfectly good one-time pad that provides 384 bits of security if used to mask a *single* $\\color{blue} 4 \\times 4$ image block; but it is used here to encrypt $\\color{blue} 72 \\times 115 = 8280$ such blocks, thus providing (*cf.* discussion of the many-time pad) an effective $\\color{blue} 384/8280 \\approx 0.05$ bit of security...

\n

Go through the same process, this time with a genuine randomly generated one-time pad. What's the key-length this time? Verify that the cipher decrypts correctly, *i.e.* play both the roles of Alice and Bob to see that everything works as it should. Also make sure to take a look at what Eve actually sees on the insecure channel.

Here's the one-time pad that we'll use:

︡fa47189c-2554-44e0-8a5a-b2de60dd1d8b︡{"html":"Here's the one-time pad that we'll use:

\n"}︡ ︠ea5f2fda-1311-4cb3-9437-058b56304830︠ k = RandomImage(288,460); k ︡9636c2ab-8267-4ec8-9e69-fb43d6ff284f︡{"once":false,"file":{"show":true,"uuid":"3192c890-79f3-4744-8916-5e5a9df84c11","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠20f1e8c2-0cfe-40d3-8498-8191f46f7d1ai︠ %htmlThe effective key length (assuming perfect strength of the random number generation) is the actual number of bits needed to specify this image:

︡64e2791c-6913-4df5-ac90-add4fb8e46ff︡{"html":"The effective key length (assuming perfect strength of the random number generation) is the actual number of bits needed to specify this image:

\n"}︡ ︠f3cb2cce-2227-4f08-b74a-4b42aabcf8b1︠ 288 * 460 * 3 * 8 # quite large! ︡298ba368-a9ad-4da0-a24a-c0463202031a︡{"stdout":"3179520\n"}︡ ︠ac6baa4c-b60b-4a94-b933-005d02bf6490i︠ %htmlTo encrypt the image, Alice applies this random key as a mask:

︡866d21fd-2977-4bda-b242-fbb447bca8ac︡{"html":"To encrypt the image, Alice applies this random key as a mask:

\n"}︡ ︠27e1af59-66a4-4cf7-bb3a-bf29ab5ecd6f︠ c = m + k ︡f0f18d5b-f03b-40e4-b168-1653a6c86a89︡ ︠978909b0-ca1e-4172-873f-db7fed03da2di︠ %htmlOnly the resulting ciphertext transits on the insecure communication channel; what Eve sees looks just like random noise.

︡9e5d1814-8a51-413b-b27a-59f95b75560c︡{"html":"Only the resulting ciphertext transits on the insecure communication channel; what Eve sees looks just like random noise.

\n"}︡ ︠1bb09a09-d309-4115-ba63-296a8b737f22︠ c ︡b12dc2b1-2976-4e53-91ae-9975a6b39c59︡{"once":false,"file":{"show":true,"uuid":"b5b78ce7-8e63-4871-9c93-222d8e1238f6","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠7776bf7b-4727-42aa-b31c-49cf439bd49fi︠ %htmlTo decrypt, Bob removes (i.e. reapplies) the pad:

︡707bf7e5-ddc8-4df6-9daf-ff86f58b4cc6︡{"html":"To decrypt, Bob removes (i.e. reapplies) the pad:

\n"}︡ ︠d33cde55-596f-4861-86cd-85559bc0166c︠ mm = c + k; mm ︡7fb99262-89bc-4bc7-a179-3fce2dfc11a2︡{"once":false,"file":{"show":true,"uuid":"a4e4b9bb-10ed-43eb-841c-e989f0a31172","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠0211eba5-5497-49e8-8c1f-e184534c9e1fi︠ %htmlYou may check that the actual pixel values of the decrypted image are actually identical to the original ones:

︡e16bf5df-d06d-41ef-8078-2785c0651561︡{"html":"You may check that the actual pixel values of the decrypted image are actually identical to the original ones:

\n"}︡ ︠39c60a22-ea25-40e0-8b45-4b5249e5b178︠ (m.data == mm.data).all() ︡de3ae035-ae8c-4c6a-8f30-6e6428a0476d︡{"stdout":"True\n"}︡ ︠5070d268-20a4-4edf-8781-b7433e78b694i︠ %htmlWow, this works well. In the excitation of the moment, I started encrypting all my images... but forgot to apply one of the most important usage rules of the one-time pad when I encrypted the following two images. Can you find out what they were?

︡701c9257-14e6-4acb-89f3-9f24993b8329︡{"html":"\n

Wow, this works well. In the excitation of the moment, I started encrypting all my images... but forgot to apply one of the most important usage rules of the one-time pad when I encrypted the following two images. Can you find out what they were?

\n\n"}︡ ︠29511115-7fe2-451e-8c15-777138853f23︠ c1 = LoadImage("c1.tiff"); c1 ︡c5f22c05-01b6-4f82-a4d2-1dbd696e7f6f︡{"once":false,"file":{"show":true,"uuid":"b1f5203d-174a-4d20-8bf3-862dd0b4e5d9","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠d14d4d51-4813-4123-8160-4e9da2ef9961︠ c2 = LoadImage("c2.tiff"); c2 ︡6d4e9120-8b98-4323-95dc-3b7717fe63de︡{"once":false,"file":{"show":true,"uuid":"5f546bf3-ca72-4ea3-a529-e442d85a0cd2","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠d44577ab-adcf-4ebf-aba5-b9fa0512e527i︠ %htmlThe single most important thing to remember with the one-time pad is to use it only once... One may suspect that the same encryption key was used twice, and this would enable an attacker to access the sum (xor) or the plaintexts by xoring the ciphertexts:

︡486974d3-9852-4130-b96e-1cc9996dc137︡{"html":"The single most important thing to remember with the one-time pad is to use it only once... One may suspect that the same encryption key was used twice, and this would enable an attacker to access the sum (xor) or the plaintexts by xoring the ciphertexts:

\n"}︡ ︠b3bd4300-1908-4d69-88f1-23f4485d4377︠ c1 + c2 ︡884535e2-6b4d-487c-9966-54668678e77d︡{"once":false,"file":{"show":true,"uuid":"1044026e-2f83-4f8e-9638-a70b5e912161","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠567c82da-0f11-478f-a151-5c47ad3cefe0i︠ %htmlIndeed! We clearly recognize Alice and Bob, semantic security is completely broken.

︡af29502f-d651-464c-85df-1595b8596e81︡{"html":"Indeed! We clearly recognize Alice and Bob, semantic security is completely broken.

\n"}︡ ︠ead71d97-ae17-4693-9862-34c234aa5322i︠ %htmlAfter realizing my mistake, I decided to generate pads from a 128-bit key by using it as a seed for a linear congruence generator modulo the following 128-bit prime:

︡3958ef8c-171d-40f8-94da-866e822b39d9︡{"html":"\n

After realizing my mistake, I decided to generate pads from a 128-bit key by using it as a seed for a linear congruence generator modulo the following 128-bit prime:

\n\n"}︡ ︠a18e9768-7de3-49d6-823c-d6f4a5cb9dd4︠ p = 340282366920938463463374607431768211507 is_prime(p) ︡3f8ca1fb-f3ed-4d20-88b8-dc895156daa3︡{"stdout":"True\n"}︡ ︠400aa835-4638-4076-b9e4-2d6d613cadd6i︠ %htmlSince such a PRNG is characterized by two 128-bit integers $a$ and $b$ which were chosen at random, there should be more than enough entropy to protect my 128-bit key, right? Prove me wrong by finding out what the seed used to produce the first few outputs from the LCG was:

217692597915196650809181220736554072509,

101697276836279744146238049998237762682,

265181937610212296333751058245677871006,

84171444745593992579687306707926595136,

12455596861516498286468598807461112654,

...︡bd89fb62-fdf1-4d86-99dd-cc35e75d5c67︡{"html":"

Since such a PRNG is characterized by two 128-bit integers $a$ and $b$ which were chosen at random, there should be more than enough entropy to protect my 128-bit key, right? Prove me wrong by finding out what the seed used to produce the first few outputs from the LCG was:

\n217692597915196650809181220736554072509,\n

101697276836279744146238049998237762682,\n

265181937610212296333751058245677871006,\n

84171444745593992579687306707926595136,\n

12455596861516498286468598807461112654,\n

...\n\n"}︡ ︠3ae47e0a-5a53-4e32-8a52-600ad6ad922di︠ %html

Recall that a linear congruence generator works by iterating a simple affine function modulo $\color{blue} p$: $$ \color{blue} x_{n+1} \equiv a \cdot x_n + b \ \mathrm{mod} \ p. $$ By substrating the formula for $\color{blue} x_n$ from the formula for $\color{blue} x_{n+1}$, one sees that: $$ \color{blue} x_{n+1} - x_n \equiv a \cdot (x_n - x_{n-1}) \ \mathrm{mod} \ p; $$ that is, the differences between successive outputs form a geometric progression.

︡f5da0418-fde4-4ee5-948a-b8d6dc9f23e0︡{"html":"Recall that a linear congruence generator works by iterating a simple affine function modulo $\\color{blue} p$:\n $$ \\color{blue} x_{n+1} \\equiv a \\cdot x_n + b \\ \\mathrm{mod} \\ p. $$\n \n By substrating the formula for $\\color{blue} x_n$ from the formula for $\\color{blue} x_{n+1}$, one sees that:\n $$ \\color{blue} x_{n+1} - x_n \\equiv a \\cdot (x_n - x_{n-1}) \\ \\mathrm{mod} \\ p; $$\n that is, the differences between successive outputs form a geometric progression.

\n"}︡ ︠52a5fbcd-1231-4277-9bb5-3c1575f1481f︠ x = [ "seed", 217692597915196650809181220736554072509, 101697276836279744146238049998237762682, 265181937610212296333751058245677871006, 84171444745593992579687306707926595136, 12455596861516498286468598807461112654 ] ︡c87a3924-1726-48e0-b9c4-a90fff00732a︡ ︠fef97d3b-9c70-49c7-b8c1-522f9de78f3bi︠ %htmlTo perform division mod $\color{blue} p$, we use the extended Euclidean algorithm to a modular inverse (or just regular integer division followed by the remainder operator since Sage is permissive):

︡b0a9a2e3-4cd0-4399-8770-cd35bce7abf5︡{"html":"To perform division mod $\\color{blue} p$, we use the extended Euclidean algorithm to a modular inverse (or just regular integer division followed by the remainder operator since Sage is permissive):

\n"}︡ ︠7ae5fcbe-fb2e-486a-a03b-b2aedcd133f7︠ a = (x[3] - x[2])/(x[2] - x[1]) % p a ︡22a7207e-f8b5-4208-8c85-dbbac26cc1f1︡{"stdout":"29879779137056188643413695637347256028\n"}︡ ︠d2b89d98-b8e1-4f11-ba93-fbc19db9adbai︠ %htmlNow the value of $\color{blue} b$ is easily recovered: ︡35547fe7-2202-4ad5-86e6-a7b12e0451ff︡{"html":"

Now the value of $\\color{blue} b$ is easily recovered:\n"}︡ ︠6cd60f81-11ed-4b42-9fd6-2ac568aa927b︠ b = (x[2] - a*x[1]) % p b ︡1c793d44-3e43-4487-abd3-62470a14254b︡{"stdout":"261355376501628057578013110734163562795\n"}︡ ︠4f35def6-fa3d-47cc-8950-ee881433d21ei︠ %html

And we can even go backwards in time:

︡bdd3db1d-b01f-4b04-8d56-2bbfd7da09d0︡{"html":"And we can even go backwards in time:

\n"}︡ ︠fb649273-8a38-4120-a94d-fe159020a4ad︠ x[0] = (x[1] - b) / a % p x[0] ︡2884abe9-d33e-43af-aaf1-2cec9e7d9013︡{"stdout":"116262181799952103953797009259690012116\n"}︡ ︠4915adff-2dbf-44a7-9fc7-7ec774ef4b4bi︠ %htmlWe verify that we are able to recover the given terms (three of them were actually enough to completely reverse engineer the LGC) by using $\color{blue} x_0$ as a seed (as well as predict future values):

︡abb18eaa-961a-4423-be95-a4e99992b794︡{"html":"We verify that we are able to recover the given terms (three of them were actually enough to completely reverse engineer the LGC) by using $\\color{blue} x_0$ as a seed (as well as predict future values):

\n"}︡ ︠78c4d3fc-191d-403f-aa3b-e57552af51ca︠ y = x[0] for i in range(10): y = (a * y + b) % p print y print "..." ︡2b956a41-7720-4324-96aa-a1aeacbea3d7︡{"stdout":"217692597915196650809181220736554072509\n101697276836279744146238049998237762682\n265181937610212296333751058245677871006\n84171444745593992579687306707926595136\n12455596861516498286468598807461112654\n105106464186866804329444885409649936144\n144019025603440397490230044970459472584\n265139309434915765374704941432985644451\n289642631303735312067300979134840749521\n119205904360883294127743631089967565464\n"}︡{"stdout":"...\n"}︡ ︠5e8e22ff-f8c3-4adb-a892-dcec590f9741i︠ %htmlLinear congruence generators (and linear shift feedback registers) were not designed to be *secure* pseudo-random number generators, and should never be used as such.

Linear congruence generators (and linear shift feedback registers) were not designed to be *secure* pseudo-random number generators, and should never be used as such.

\nOk, now it's time to start doing things properly. We will use the still-standard-albeit-somewhat-deprecated RC4 pseudo-random number generator to generate a key-stream from a 128-bit key. We first aquire 128 bits of \"real\" random data from the entropy pool of the system.\nx[1]"}︡ ︠7dedc60e-ccbf-4611-9186-bc3726b31e25︠ k = os.urandom(16) # 16 bytes of entropy coming from /dev/urandom k.encode('hex') ︡03547162-5df7-43fe-9169-26a018133720︡{"stdout":"'42d03204f3581f4671f73463c788c1c0'\n"}︡ ︠b7ad5ae3-639d-4e51-9110-479d030af28f︠ load("RC4.sage") prng = RC4(k) ︡d9e2223b-eb1c-4eae-8505-1ce5968f1bfe︡ ︠5824c054-8a06-4e5b-a8bf-aabb5ed9e160︠ ︡6e1d6307-26d6-43c9-a911-b8bde21e542d︡{"html":"\nUse this to generate of pseudo-random pad from $k$, and then encrypt the Bletchley Park picture with it. Make sure that Bob will be able to decrypt it knowing only $k$.\n"}︡ ︠17cf18b3-cd0e-4303-8915-02e9323ea6c4i︠ %html

Alice generates a pseudo-random pad of the required size by using the pixel values supplied by the PRNG: ︡e65f884b-6da8-4b6c-bf08-f9edac07fea5︡{"html":"

Alice generates a pseudo-random pad of the required size by using the pixel values supplied by the PRNG:\n"}︡ ︠4a519e97-d150-4703-8f54-80f6d5fcac26︠ pad = Image([ [ [prng.next(), prng.next(), prng.next()] for j in range(460) ] for i in range(288) ]) pad ︡bbe19d83-4307-425e-b673-d128a0670d58︡{"once":false,"file":{"show":true,"uuid":"bba5e9c8-c98e-4814-b191-dafee81196a8","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠3052c07a-5169-43bd-86de-ac5c0d1220ffi︠ %html

and then applies it to the image to encrypt it:

︡6f46984e-bf06-4c06-b411-ac0519fd11d4︡{"html":"and then applies it to the image to encrypt it:

\n"}︡ ︠c967aee8-43b1-4d9a-bcbc-7e267a77d8c2︠ c = m + pad c ︡ae05b72a-d2ef-4a8c-95f1-175642704067︡{"once":false,"file":{"show":true,"uuid":"bdcf8024-1516-4b5e-a1cd-aea5bc41ed9e","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠fb7aae86-9a90-4d62-8707-1a74e24e0a2bi︠ %htmlUpon reception of the ciphertext, Bob initializes his own PRNG with the secret key $\color{blue} k$ to compute the exact same pad in order to remove it: ︡77934f5c-a3db-464b-bd88-d875aa5d508d︡{"html":"

Upon reception of the ciphertext, Bob initializes his own PRNG with the secret key $\\color{blue} k$ to compute the exact same pad in order to remove it:\n"}︡ ︠ab9c610e-f9c0-45d3-8bba-8ce110475b5a︠ prng = RC4(k) pad = Image([ [ [prng.next(), prng.next(), prng.next()] for j in range(460) ] for i in range(288) ]) c + pad ︡ab4b6bcb-2636-416a-9c3c-e8ca22d7b697︡{"once":false,"file":{"show":true,"uuid":"a4e4b9bb-10ed-43eb-841c-e989f0a31172","filename":"temp.png"}}︡{"stdout":"\n"}︡ ︠853ea58f-da3d-4a3b-8718-93cdf3b46c91i︠