Crypto Flashcards

1
Q

What is a symmetric encryption system?

A

One in which two parties share a private key

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is correctness, in the context of a cipher?

A

D(k, E(k, m)) = m

That is, the decryption of an encryption must be the original message for every message and key.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What defines perfect secrecy?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the downside of the One-Time Pad?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a Stream Cipher?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What does it mean for a Pseudo-Random Generator to be predictable?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Why is it bad to use the same One-Time Pad key twice?

A

It’s insecure.

c1 = m1 XOR k
c2 = m2 XOR k

c1 XOR c2 = m1 XOR m2

This leaks information about the plaintext.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does a One-Time Pad fail to guarantee?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a nonce?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is advantage, in the context of generators?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What does it mean for a PRG to be secure?

A

The advantage of every efficient algorithm is negligible.

Note that the definition is unsatisfiable if we fail to restrict ourselves to “efficient” adversaries.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is Yao’s Theorem?

A

A secure PRG is unpredictable; an unpredictable PRG is secure.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does it mean for two distributions to be computationally indistinguishable?

A

The advantage of every efficient statistical test is negligible. In other words, the two cannot be differentiated between in polynomial time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What does it mean for a cipher to be semantically secure?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a Block Cipher?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a Pseudo-Random Function?

A

A pseudo-random generator which is defined over a keyspace, inputspace, and outputspace.

F: K x X -> Y

17
Q

What is a Pseudo-Random Permutation?

A

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.

18
Q

What is a Feistel System?

A

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.

19
Q

What is a Power Attack?

A

An attack which looks at the power usage during encryption and decryption in order to figure out the key used.

20
Q

What is a Fault Attack?

A

An attack which causes the processor to fault during the final stage of encryption, potentially compromising information about the secret key.

21
Q

What is Linear Cryptanalysis?

A

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!

22
Q

What is a Quantum Attack?

A

An attack which uses quantum computers to crack a cipher. A quantum computer can find k in time O(|K|^1/2).

23
Q

What is AES?

A

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.

24
Q

What three methods does AES use?

A

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)

25
Q

What is a mode of operation?

A

A technique for improving or adapting a crypto scheme, primarily block ciphers.

26
Q

What is an Electronic Codebook?

A

A mode of operation that uses the same key to encode plaintext blocks. Note that this is only acceptable for short messages, because otherwise identical blocks produce identical ciphertext portions!

27
Q

What is Cipher Block-Chaining?

A

A mode of operation similar to ECB that uses the same key for each block, but also XORs each block with its predecessor to avoid repetition.

The first block is XOR’d with a special Initialization Vector.

28
Q

What is Cipher Feedback Mode?

A

A mode of operation that can be used to convert a block cipher into a stream cipher, thus allowing real-time operation.

With this, there is no need to pad input. It is capable of encrypting s-bit blocks, where s < b.

29
Q

What is Output Feedback Mode?

A

A mode of operation similar to CFB, but one that operates on full blocks and does not allow bit errors to propagate.

Note that this requires a nonce for an initialization vector.

30
Q

What is Counter Mode?

A

A mode of operation that foregoes chaining and instead counts as it goes.

This is parallelizable and allows for significant preprocessing to occur, while still being secure.

The initial counter value must be known for decryption.