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

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

10. shared-key is when a block ciphers have one key for both encryption and decryption

11. another name for shared-key

12. another name for shared-key

13. public-key is when block ciphers has= separate keys for both encryption and decryption

14. another name for public-key

15. a special type of asymmetric crypto primitive

Caesar cipher

- 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

Monoalphabetic substituion

- 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

Why are monoalphabetic ciphers straightforward to break?

- 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

How do you make a stronger cipher?

- use a stream cipher or a block cipher

What is a stream cipher?

- make the encryption rule depend on a plaintext symbol's position in the stream of plaintext symbols

What is a block cipher?

- encrypt several plaintext symbols at once in a block

What is the Vigenere?

- 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

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

- 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.

What is the one-time pad?

- 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

What is perfect secrecy?

- 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

What is the disadvantage of one-time pad?

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

What is a more popular solution to stream cipher attacks?

- 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

What is the Playfair?

- an early block cipher

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

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.

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

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.

What is the one-way function?

- 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

How strong are test keys?

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

What are the digital signature?

- 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.

What is pseudorandom?

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.

What is the random oracle model?

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

What is a random function?

- 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**

What are message digests?

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.

What are the properties of a random function?

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).

What is the birthday theorem?

- . 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

How is the birthday theorem useful in computer security?

- 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’.

What is a random generator?

- 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

What is unconditional or statistical security?

- 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.

What is the problem with keystream generators?

- 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.

What is a seed used for?

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.

What is a block cipher?

- 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.

What is the input and output of Playfair?

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.)

How does a block cipher work?

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

What is the notation for a block cipher?

C = {M}_{k}

What is a known plaintext attack?

- 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

What is a chosen plaintext attack?

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

What is a chosen plaintext/ciphertext attack?

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

What is a related key attack?

- 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

What is the objective of attacks on block ciphers?

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)

What are certificational attacks?

- attacks that are of great scientific importance, but their practical engineering effect are zero

- ex. Data Encryption Standard algorithm

-- originally would take 2^{47} chosen plaintexts to recover the key, after the attack, 2^{43} were known, and no practical systems make enough known so it was fine

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

chosen-plaintext attacks

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

- someone who gets temporary access to some cryptographic equipment while its authorized user is out.

- Chosen plaintext/ciphertext attacks

When are related-key attacks a concern?

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

What is a public-key encryption algorithm?

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

What is a common way of implementing public key encryption?

trapdoor one-way permutation

What is trapdoor one-way permutation?

- 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.

Formally explain a public key encryption.

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}

What is a digital signature?

- 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

What is a deterministic signature scheme?

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

What is a randomized signature scheme?

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

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

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

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

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

What is the formal definition of a signature scheme?

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.

How can we model a simple digittal signature algorithm?

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.

What are the two forms of signature verification?

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).

What are the advantages to signature scheme with message recovery?

- 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

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

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.

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

- 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

Do block ciphers need confusion or diffusion?

They need both.

What are SP-networks?

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

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

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.

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

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^{8 }blocks

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

- 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)

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

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.

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

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

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.

What is linear crptanalysis?

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.

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

. 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^{2} known texts. If the value of M^{2} for the best linear relationship is greater than the total possible number of known texts (namely 2^{n} where the inputs and outputs are n bits wide), then we consider the cipher to be secure against linear cryptanalysis.