What is the non-mathematical definition for the following cryptographic terms?
6. cryptographic primitives
7. block ciphers
8. stream ciphers
9. hash functions
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
- 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
- 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 . - 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?
- 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.