Crypto Flashcards
What is a symmetric encryption system?
One in which two parties share a private key
What is correctness, in the context of a cipher?
D(k, E(k, m)) = m
That is, the decryption of an encryption must be the original message for every message and key.
What defines perfect secrecy?
If for any two messages, it is impossible to distinguish between the two just by looking at their ciphertexts.
In other words, for any two messages m1 and m2 and their corresponding ciphertexts c1 and c2, it is impossible for an algorithm to determine which ciphertext corresponds to which message.
Said yet another way, the probability that an arbitrary ciphertext is the encryption of a message must be uniform.
Finally, there is no information leaked about the plaintext by the ciphertext.
What is the downside of the One-Time Pad?
The key must be as long as the message, and, if you have a way to securely transmit something that long, just securely transmit the message.
What is a Stream Cipher?
A cipher which encrypts one bit at a time.
These use their key as a seed for a generator in order to create a much larger, pseudorandom key, which is then used to encrypt the original message. In this way, they are a more practical (but less secure) form of the One-Time Pad.
What does it mean for a Pseudo-Random Generator to be predictable?
There is an algorithm A and a position i such that if we generate a random value using the generator, the probability that the algorithm can predict the next bit, given the first i bits, is non-negligibly greater than 1/2.
One common cutoff for negligibility is 1/2^30.
Put more simply, a PRG is predictable if the algorithm can ever guess the next value that is generated reliably.
Why is it bad to use the same One-Time Pad key twice?
It’s insecure.
c1 = m1 XOR k c2 = m2 XOR k
c1 XOR c2 = m1 XOR m2
This leaks information about the plaintext.
What does a One-Time Pad fail to guarantee?
Data integrity – messages encrypted with the OTP are still malleable.
For example, say an adversary intercepts the encrypted message m XOR k.
Although they cannot decipher its contents, they can change them by XORing them with another value, p.
They then send the new message, m XOR k XOR p, to the original target, who decrypts it and receives m XOR p, not simply m.
What is a nonce?
A value that has a very low probability of repeating (e.g. system clock, atmospheric data).
With a nonce r, it becomes possible to reuse a key so long as the pair (k, r) never repeats.
What is advantage, in the context of generators?
The ability of an algorithm to distinguish between the generator’s output and truly random output.
An advantage close to 1 means that the algorithm was readily able to differentiate between the two’s output; a value close to 0 indicates it was significantly harder. Any non-negligible value is bad.
What does it mean for a PRG to be secure?
The advantage of every efficient algorithm is negligible.
Note that the definition is unsatisfiable if we fail to restrict ourselves to “efficient” adversaries.
What is Yao’s Theorem?
A secure PRG is unpredictable; an unpredictable PRG is secure.
What does it mean for two distributions to be computationally indistinguishable?
The advantage of every efficient statistical test is negligible. In other words, the two cannot be differentiated between in polynomial time.
What does it mean for a cipher to be semantically secure?
The advantage of every efficient algorithm against the encryption function is negligible.
Note that this is Shannon’s definition of perfect secrecy, but restricted to efficient algorithms to set realistic expectations.
What is a Block Cipher?
A cipher which takes an n-bit message and creates an n-bit ciphertext.
By expanding the key, it is able to be used for multiple rounds of encryption.
What is a Pseudo-Random Function?
A pseudo-random generator which is defined over a keyspace, inputspace, and outputspace.
F: K x X -> Y
What is a Pseudo-Random Permutation?
A pseudo-random function which is also invertible. Thus, it is only defined over a keyspace and an inputspace.
F: K x X -> X
A PRP must be both one-to-one and invertible.
What is a Feistel System?
A system for taking an arbitrary function or set of functions, which don’t have to be invertible, and creating an invertible encryption scheme from them.
By the Luby-Rackoff Theorem, a Feistel System composed of three rounds of a secure PRF is sufficient to create a secure cipher.
What is a Power Attack?
An attack which looks at the power usage during encryption and decryption in order to figure out the key used.
What is a Fault Attack?
An attack which causes the processor to fault during the final stage of encryption, potentially compromising information about the secret key.
What is Linear Cryptanalysis?
An attack which approximates the relations between CTs and PTs linearly in order to predict the key’s bits.
This requires a massive amount of input/output pairs; to crack DES, 2^43 chosen PT/CT pairs are necessary. However, this is still a huge upgrade over brute force!
What is a Quantum Attack?
An attack which uses quantum computers to crack a cipher. A quantum computer can find k in time O(|K|^1/2).
What is AES?
An encryption scheme which is quite secure.
Key size: 128, 192, 256
Block size: 128
It uses a substitution and permutation network (not a Feistel System) to encrypt and decrypt.
The best attack known so far takes time 2^126.
What three methods does AES use?
Byte Substitution – swapping bytes based on s-boxes
Shift Rows – left shift each row by a fixed amount
Mix Columns – apply a linear transformation to each column (independently)
