Cryptography Reading

Question 1

What is the non-mathematical definition for the following cryptographic terms?

1. cryptography
2. cryptanalysis
3. cryptology
4. plaintext
5. ciphertext
6. cryptographic primitives
7. block ciphers
8. stream ciphers
9. hash functions
10. shared-key
11. secret-key
12. symmetric
13. public-key
14. asymmetric
15. digital signature scheme

Answer 1

1. the science and art of designing ciphers
2. the science and art of breaking them
3. aka crypto, the study of both cryptography and cryptanalysis
4. the input to an encryption process is plaintext
5. the output to the encryption process
6. basic building blocks such as block ciphers, stream ciphers, and hash functions
7. block ciphers may have either one key for both encryption and decryption or separate keys
8. shared-key is when a block ciphers have one key for both encryption and decryption
9. another name for shared-key
10. another name for shared-key
11. public-key is when block ciphers has= separate keys for both encryption and decryption
12. another name for public-key
13. a special type of asymmetric crypto primitive

Question 2

Caesar cipher

Answer 2

• cipher is alphabet shifted over - was Caesar’s imperial cipher system - ex. ‘C’ was ‘A’, ‘D’ for ‘B’ or ‘4’ for ‘a’, ‘5’ for b

Question 3

Monoalphabetic substituion

Answer 3

• Arab generalization of the Caesar cipher – the arabs used a keyword to permute the cipher alphabet - now, it just means any one character maps to another letter of the alphabet

Question 4

Why are monoalphabetic ciphers straightforward to break?

Answer 4

• some letters and combinations are more common than others - this is made possible by the one to one mapping of cipher characters to plaintext character

Question 5

How do you make a stronger cipher?

Answer 5

• use a stream cipher or a block cipher

Question 6

What is a stream cipher?

Answer 6

• make the encryption rule depend on a plaintext symbol’s position in the stream of plaintext symbols

Question 7

What is a block cipher?

Answer 7

• encrypt several plaintext symbols at once in a block

Question 8

What is the Vigenere?

Answer 8

• an early stream cipher by Vigenere - an early polyalphabetic substitution cipher - works by adding a key repeatedly into the plain text using the convention ‘A’ = 0, ‘B’=1,…‘Z’ = 25, and addition is mod 26 - C = P + K mod 26 - ex. Plain tobeornottobethatisthequestion Key runrunrunrunrunrunrunrunrunrun Cipher KIOVIEEIGKIOVNURNVJNUVKHVMGZIA

Question 9

How can you break a polyalphabetic substition cipher like the Vigenere?

Answer 9

• first published solution was in 1863 by Friedrich Kasiski, a Prussian infantry officer [695]. - given a long enough piece of ciphertext, repeated patterns will appear at multiples of the keyword length.

Question 10

What is the one-time pad?

Answer 10

• the solution from pattern finding attacks on stream ciphers - make the key sequence the same length as the plain text and have it never repeat - has perfect secrecy

Question 11

What is perfect secrecy?

Answer 11

• Claude Shannon proved that a cipher has perfect secrecy if and only if there are as many possible keys as possible plaintexts, and every key is equally likely

Question 12

What is the disadvantage of one-time pad?

Answer 12

• too expensive for most applications, consumes as much key material as there is traffic

Question 13

What is a more popular solution to stream cipher attacks?

Answer 13

• use a suitable pseudorandom number generator to expand a short key into a long keystream - then xor the keystream, one bit at a time with the plaintext

Question 14

What is the Playfair?

Answer 14

• an early block cipher

Question 15

What happens if the output of a block cipher just looks intuitibely random?

Answer 15

Again, it’s not enough for the output of a block cipher to just look intuitively ‘random’. Playfair ciphertexts look random; but they have the property that if you change a single letter of a plaintext pair, then often only a single letter of the ciphertext will change.

Question 16

How do you improve the security of a cipher block?”

Answer 16

The security of a block cipher can be greatly improved by choosing a longer block length than two characters

• Unless the cipher block is as large as the message, the ciphertext will contain more than one block and we will usually need some way of binding the blocks together.
• an eight byte or sixteen byte block size is not enough of itself. For example, if a bank account number always appears at the same place in a transaction, then it’s likely to produce the same ciphertext every time a transaction involving it is encrypted with the same key
• This might allow an opponent to cut and paste parts of two different ciphertexts in order to produce a seemingly genuine but unauthorized transaction.

Question 17

What is the one-way function?

Answer 17

• makes block ciphers ones way by adding code groups together into a number called a test key (so hash value or message authentication code)
• made such test key systems into one-way functionsin that although given knowledge of the key it was possible to compute a test from a message, it was not possible to reverse the process and recover a message from a test — the test just did not contain enough information

Question 18

How strong are test keys?

Answer 18

They aren’t very strong, but they worked for banks until the 1980’s. The tables can be reconstructed with enough tested messages.

Question 19

What are the digital signature?

Answer 19

• A type of assymmetric application of cryptography.
• The idea here is that I can sign a message using a private signature key and then anybody can check this using my public signature verification key.

Question 20

What is pseudorandom?

Answer 20

A cryptographic primitive is pseudorandom if it passes all the statistical and other tests which a random function of the appropriate type would pass, in whatever model of computation we are using.

Question 21

What is the random oracle model?

Answer 21

We can visualize a random oracle as an elf sitting in a black box with a source of physical randomness and some means of storage (see Figure 5.9) — represented in our picture by the dice and the scroll. The elf will accept inputs of a certain type, then look in the scroll to see whether this query has ever been answered before. If so, it will give the answer it finds there; if not, it will generate an answer at random by throwing the dice. We’ll further assume that there is some kind of bandwidth limitation — that the elf will only answer so many queries every second

Question 22

What is a random function?

Answer 22

• a type of random oracle
• A random function accepts an input string of any length and outputs a random string of fixed length, say n bits long.
• Random functions are our model for one-way functions, also known as cryptographic hash functions

Question 23

What are message digests?

Answer 23

In messaging applications, hashes are often known as message digests; given a message M we can pass it through a pseudorandom function to get a digest, say h(M), which can stand in for the message in various applications. One example is digital signature: signature algorithms tend to be slow if the message is long, so it’s usually convenient to sign a message digest rather than the message itself.

Question 24

What are the properties of a random function?

Answer 24

1. one-wayness
   - Given knowledge of an input x we can easily compute the hash value h(x), but it is very difficult given the hash value h(x) to find a corresponding preimage x if one is not already known.
2. the output will not give any info at all about even part of the input
   - Thus a one-way encryption of the value x can be accomplished by concatenating it with a secret key k and computing h(x, k).
3. it is hard to find collisions, that is, different messages M1 != M2 with h(M1) = h(M2).

Question 25

What is the birthday theorem?

Answer 25

• . Suppose there are N fish in a lake and you catch m of them, ring them and throw them back, then when you first catch a fish you’ve ringed already, m should be ‘about’ the square root of N. The intuitive reason why this holds is that once you have √N samples, each could potentially match any of the others, so the number of possible matches is about √N x √N or N, which is what you need2.
• in a class of 30 pupils, 2 of them will probably have the same birthday

Question 26

How is the birthday theorem useful in computer security?

Answer 26

• helps you understand the likelihoo dof collisions
• a pseudorandom function is also often referred to as being collision free or collision intractable. This doesn’t mean that collisions don’t exist — they must, as the set of possible inputs is larger than the set of possible outputs — just that you will never find any of them.
• Why? - In a digital signature application, if it were possible to find collisions with h(M1) = h(M2) but M1 != M2, then a Mafia owned bookstore’s web site might get you to sign a message M1 saying something like ‘I hereby order a copy of Rubber Fetish volume 7 for $32.95’ and then present the signature together with an M2 saying something like ‘I hereby mortgage my house for $75,000 and please make the funds payable to Mafia Holdings Inc., Bermuda’.

Question 27

What is a random generator?

Answer 27

• a basic cryptographic primitive
• aka keystream generator or stream cipher
• also a random function, but unlike in the hash function case it has a short input and a long output.
• can be used quite simply to protect the confidentiality of backup data: we go to the keystream generator, enter a key, get a long file of random bits, and exclusive-or it with our plaintext data to get ciphertext, which we then send to our backup contractor.
• If we need to recover the data, we go back to the generator, enter the same key, get the same long file of random data, and exclusive-or it with our ciphertext to get our plaintext data back again. Other people with access to the keystream generator won’t be able to generate the same keystream unless they know the key

Question 28

What is unconditional or statistical security?

Answer 28

• security that doesn’t depend on the computing power available to the opponent, or on there being no future advances in mathematics which provide a shortcut attack on the cipher
• ex. one-time pad, and Shannon’s result that a cipher has perfect secrecy if and only if there are as many possible keys as possible plaintexts, and every key is equally likely.

Question 29

What is the problem with keystream generators?

Answer 29

• we want to prevent the same keystream being used more than once
• this is because if reused, like it was during WW2 w/ the Russians,

If M1 + K = C1 and M2 + K = C2, then the opponent can combine the two ciphertexts to get a combination of two messages: C1 − C2 = M1 − M2, and if the messages Mi have enough redundancy then they can be recovered.

Question 30

What is a seed used for?

Answer 30

Exactly the same consideration (not reusing the key) holds for any stream cipher, and the normal engineering practice when using an algorithmic keystream generator is to have a seed as well as a key. Each time the cipher is used, we want it to generate a different keystream, so the key supplied to the cipher should be different.

Question 31

What is a block cipher?

Answer 31

• a type of cryptographic primitive
• most important in modern commercial cryptography
• we model itr as a random permutation
• the function is invertible, and the input plaintext and the output ciphertext are of a fixed size
• is a keyed family of pseudorandom permutations
• • For each key, we have a single permutation which is independent of all the others.

Question 32

What is the input and output of Playfair?

Answer 32

With Playfair, both input and output are two characters; with DES, they’re both bit strings of 64 bits. Whatever the number of symbols and the underlying alphabet, encryption acts on a block of fixed length. (So if you want to encrypt a shorter input, you have to pad it as with the final ‘z’ in our Playfair example.)

Question 33

How does a block cipher work?

Answer 33

We can visualize block encryption as follows. As before, we have an elf in a box with dice and a scroll. This has on the left a column of plaintexts and on the right a column of ciphertexts. When we ask the elf to encrypt a message, it checks in the left hand column to see if it has a record of it. If not, it uses the dice to generate a random ciphertext of the appropriate size (and which doesn’t appear yet in the right hand column of the scroll), and then writes down the plaintext/ciphertext pair in the scroll. If it does find a record, it gives us the corresponding ciphertext from the right hand column. When asked to decrypt, the elf does the same, but with the function of the columns reversed: he takes the input ciphertext, checks it (this time on the right hand scroll) and if he finds it he gives the message with which it was previously associated. If not, he generates a message at random (which does not already appear in the left column) and notes it down

Question 34

What is the notation for a block cipher?

Answer 34

C = {M}_k

Question 35

What is a known plaintext attack?

Answer 35

• an attack on block ciphers where the opponent is just given a number of randomly chosen inputs and outputs from the oracle corresponding to a target key

Question 36

What is a chosen plaintext attack?

Answer 36

• an attack on block ciphers where the opponent is allowed to put a certain number of plaintext queries and get the corresponding ciphertexts.

Question 37

What is a chosen plaintext/ciphertext attack?

Answer 37

• an attack on block ciphers where the attacker is allowed to make queries of eitehr type

Question 38

What is a related key attack?

Answer 38

• an attack on block ciphers where an opponent can make queries that will be answerred using keys related to the target key k, such as K+1, K+2

Question 39

What is the objective of attacks on block ciphers?

Answer 39

Thje objective of that attacker may be either to deduce the answer to a query he hasn’t already made (a foregery attack), or recover the key (key recovery attack)

Question 40

What are certificational attacks?

Answer 40

• attacks that are of great scientific importance, but their practical engineering effect are zero
• ex. Data Encryption Standard algorithm
• • originally would take 2⁴⁷ chosen plaintexts to recover the key, after the attack, 2⁴³ were known, and no practical systems make enough known so it was fine

Question 41

What type of attacks should you be worried about if the opponent can insert any kind of message into your system?

Answer 41

chosen-plaintext attacks

Question 42

What is a lunchtime attacker? What kind of attacks do they launch?

Answer 42

• someone who gets temporary access to some cryptographic equipment while its authorized user is out.
• Chosen plaintext/ciphertext attacks

Question 43

When are related-key attacks a concern?

Answer 43

When the block cipher is used as a building block in the construction of a hash function.

Question 44

What is a public-key encryption algorithm?

Answer 44

A public-key encryption algorithm is a special kind of block cipher in which the elf will perform the encryption corresponding to a particular key for anyone who requests it, but will do the decryption operation only for the key’s owner.

• The user might give a secret name to the scroll that only she and the elf know, use the elf’s public one-way function to compute a hash of this secret name, publish the hash, and instruct the elf to perform the encryption operation for anybody who quotes this hash.
• A principal, say Alice, can publish a key and if Bob wants to, he can now encrypt a message and send it to her, even if they have never met. All that is necessary is that they have access to the oracle. There are some more details that have to be taken care of, such as how Alice’s name can be bound to the key, and indeed whether it means anything to Bob
• for practical purposes, we willw ant the oracle to be replicated at both ends of the communications channel, and this means either using tamper-resistant hardware or (more commonly) implementing its functions using mathematics rather than metal

Question 46

What is a common way of implementing public key encryption?

Answer 46

trapdoor one-way permutation

Question 47

What is trapdoor one-way permutation?

Answer 47

• a computation which anyone can perform, but which can be reversed only by someone who knows a trapdoor such as a secret key
• this model is like the ‘one-way function’ model of a cryptographic hash function.

Question 48

Formally explain a public key encryption.

Answer 48

a public key encryption primitive consists of a function which given a random input R will return two keys, KR (the public encryption key) and KR^-1 (the private decryption key) with the properties that

1. Given KR, it is infeasible to comput KR^-1 (so it’s not possible to compute R either);
2. There is an encryption function {…} which, applied to message M using the encryption key KR, will produce a ciphertext C = {M}_KR; and
3. There is a decryption function which, applied to a ciphertext C using the decryption key KR^-1 will produce the original message M = {C}_KR^-1

Question 49

What is a digital signature?

Answer 49

• a cryptographic primitive
• the basic idea is that a signature on a message can be created by only one person, but checked by anyone.
• signarute schemes can be deterministic or randomized
• signature schemes may or may not support message recovery

Question 50

What is a deterministic signature scheme?

Answer 50

• when computing a signature on a message will always give the same result

Question 51

What is a randomized signature scheme?

Answer 51

when computing a signature on a message will always give a different result (this is more like handwritten signatures)

Question 52

What does it mean when a signature scheme supports message recovery?

Answer 52

• given the signature, anyone can recover the message on which it was generated

Question 53

What does it mean if a signature scheme does not support message recovery?

Answer 53

the verifier needs to know or guess the message before he can perform the verification

Question 54

What is the formal definition of a signature scheme?

Answer 54

Formally, a signature scheme, like public key encryption scheme, has a keypair generation function which given a random input R will return two keys, σR (the private signing key) and VR (the public signature verification key) with the properties that

1. Given the public signature verification key VR, it is infeasible to compute the private signing key σR;
2. There is a digital signature function which given a message M and a private signature key σR, will produce a signature Sig_σR(M); and
3. There is a signature verification function which, given the signature Sig_σR(M) and the public signature verification key VR will output TRUE if the signature was computed correctly with σR and otherwise output FALSE.

Question 55

How can we model a simple digittal signature algorithm?

Answer 55

We can model a simple digital signature algorithm as a random function that reduces any input message to a one-way hash value of fixed length, followed by a special kind of block cipher in which the elf wil perform the operation in one direction, known as signature, for only one principal, while in the other direction, it will perform verification for anybody.

Question 56

What are the two forms of signature verification?

Answer 56

1. in the basic scheme, the signature verification alg only outputs TRUE or FALSE depending on whether the signature is good.
2. In a scheme with message recovery, anyone can input a signature and get back the message corresponding to it. So if the elf has seen the signature before, it will give the message corresponding to it on the scroll, otehrwise it will give a random value (and record the input and the random output as a signature and message pair).

Question 57

What are the advantages to signature scheme with message recovery?

Answer 57

• when sending short messages over a low bandwidth channel, it can save space if only the signature has to be sent rather than the signature plus the message.
• ex. machine-printed postage stamps, or indicia

Question 59

In general, we don’t need message recovery. Why is that?

Answer 59

in the general case, we do not need message recovery, as the message to be signed may be of arbitrary length and so we will first pass it through a hash function and then sign the hash value. As hash functions are one-way, the resulting compound signature scheme does not have message recovery – although if the underlying signature scheme does, then the hash of the message can be recovered from the signature.

Question 60

Claude Shannon describes the properties of a cipher as being confusion and diffusion. What does that mean?

Answer 60

• adding unknown key values will confuse an attacker about the value of a plaintext symbol,
• while diffusion means spreading the plaintext information through the ciphertext

Question 61

Do block ciphers need confusion or diffusion?

Answer 61

They need both.

Question 62

What are SP-networks?

Answer 62

The earliest block ciphers were simple networks which combined substitution and permutation circuits, and so were called SP-networks.

Question 63

What are the three things that need to be done to make SP-networks design secure?

Answer 63

1. the cipher needs to be ‘‘wide’’ enough
2. it needs to have enough rounds, and
3. the S-boxes need to be suitably chosen.

Question 64

What size is a practical block cipher for an S -box and why?

Answer 64

1. a practical block cipher will usually deal with plaintexts and ciphertexts of 64 bits, 128 bits or even more. So if we are using four-bit to four-but S-boxes, we may have 16 of them (for 64 bit block size) or 32 of them (for 128 bit block size)
2. the birthday theorem: a block cipher which operated on 16 bit blocks would have rather limited applicability, as an opponent could just build a dictionary of plaintext and ciphertext blocks as he ovserved them. The birthday theorem tells us that even if the input plaintexts were random, he’d expect to find a match as soona s he had seen a little over 2⁸ blocks

Question 65

Why do we need to have enough rounds to make SP-network design secure?

Answer 65

• The two rounds in Figure 5.10 are completely inadequate, as an opponent can deduce the values of the S-boxes by tweaking input bits in suitable patterns. For example, he could hold the rightmost 12 bits constant and try tweaking the leftmost four bits, to deduce the values in the top left S-box. ( a little bit more complicated if input bit doesn’t produce change, but still simple)

Question 66

How do we know how many number of rounds in SP-networking needs to be secure?

Answer 66

The number of rounds we require depends on the speed with which data diffuse through the cipher. In the above simple example, diffusion is very slow because each output bit from one round of S-boxes is connected to only one input bit in the next round. Instead of having a simple permutation of the wires, it is more efficient to have a linear transformation in which each input bit in one round is the exclusive-or of several output bits in the previous round. Of course, if the block cipher is to be used for decryption as well as encryption, this linear transformation will have to be invertible.

Question 67

What does a simple 16-bit SP-network block cipher look like?

Answer 67

Question 68

Why do the S-boxes need to be suitably chosen in order the the SP-network design to be secure?

Answer 68

The design of the S-boxes also affects the number of rounds required for security, and studying bad choices gives us our entry into the deeper theory of block ciphers. Suppose that the S-box were the permutation that maps the inputs (0,1,2,… ,15) to the outputs(5,7,0,2,4,3,1,6,8,10,15,12,9,11,14,13). Then the most significant bit of the input would come through unchanged as the most significant bit of the output. If the same S-box were used in both rounds in the above cipher, then the most significant bit of the input would pass through to become the most significant bit of the output. This would usually be a bad thing; we certainly couldn’t claim that our cipher was pseudorandom.

Question 69

What is linear crptanalysis?

Answer 69

Linear cryptanalysis proceeds by collecting a number of relations such as ‘bit 2 plus bit 5 of the input to the first S-box is equal to bit 1 plus bit 8 of the output, with probability 13/16’ and then searching for ways to glue them together into an algebraic relation between input bits, output bits and key bits that holds with a probability different from one half.

Question 70

How do we consider a cipher to be secure against linear cryptanalysis?

Answer 70

. If we can find a linear relationship that holds over the whole cipher with probability p = 0.5 + 1/M, then according to probability theory we can expect to start recovering keybits once we have about M² known texts. If the value of M² for the best linear relationship is greater than the total possible number of known texts (namely 2ⁿ where the inputs and outputs are n bits wide), then we consider the cipher to be secure against linear cryptanalysis.