Cryptography

Question 1

What is SSL/TLS ?

Answer 1

It’s a protocol used to establish secure communications on the web

Question 2

How does SSL/TLS establish secure communication ?

Answer 2

TLS establishes secure comms in two parts:
1. It uses a handshake protocol to create a shared secret key using public key cryptography
2. A record layer to securely transmit the data using the shared secret key

Question 3

What are some applications of cryptography ?

Answer 3

• SSL/TLS
• File encryption
• Digital signatures
• Anonymous communication
• Multi-party communication
• Zero knowledge (proof of knowledge)

Question 4

What are the 3 steps when introducing new cryptographic primitives ?

Answer 4

1. Define the threat model
2. Propose a construction
3. Proof that breaking the construction under the given threat model will solve an underlying hard problem

Question 5

What is a cipher ?

Answer 5

A pair of algorithms used to encrypt and decrypt data

Question 6

What is perfect secrecy of a cipher ?

Answer 6

Its property of ciphers which states that a given cipher-text should reveal no information about its plaintext

Question 7

What does Shannon’s bad news lemma prove ?

Answer 7

It shows that every cipher with perfect secrecy has a key length which is greater than or equal to the length of the message

Question 8

What is a stream cipher ?

Answer 8

A cipher that uses a pseudo random generator to generate a much shorter key which is used to encrypt and decrypt messages. The drawback is that such a cipher cannot achieve perfect secrecy, due to Shannon’s proof.

Question 9

What should a programmer keep in mind with stream ciphers ?

Answer 9

The same key should not be used more than once
* For network sessions always negotiate a new key
* Stream ciphers should typically not be used for disk encryption

Question 10

What do we mean when we say a PRG is indistinguishable from random, what does this prove ?

Answer 10

Indistinguishable from random is a property that proves just how secure a PRG is. We say a PRG is IFR, if the output of the PRG (derived from a subset K) cannot be distinguished from the output of a uniform distribution (derived from a larger set which contains K).

Question 11

What is a secure prg ?

Answer 11

A PRG is said to be secure if for all efficient statistical tests the advantage is negligible. ie no efficient statistical tests exists that can distinguish the output of the PRG from random.

Question 12

What is a semantically secure cipher ?

Answer 12

A cipher is said to be semantically secure if for all efficient adversaries the advantage is negligible.
   

Question 13

What is perfect secrecy (Shannon Cipher)

Answer 13

Its a property of a cipher such that it is difficult to guess a message from its given cipher-text

Question 14

What is a block cipher ?

Answer 14

Its a cipher that takes in n bits of input at a time and maps that to exactly n bits of output (cipher text). Hence the term block (a set of n bit strings)

Question 15

What is the intuition behind security in a block cipher ?

Answer 15

Simply put a block cipher is secure if it is computationally indistinguishable from a random permutation

Question 16

List some attacks on block ciphers

Answer 16

1. Side channel attacks - which measure the time taken by the enc/dec algorithm. Can also measure the amount of electrical power consumed
2. Fault attack - work by inducing errors in the encryption/decryption algorithm.
3. Linear / differential attacks - exploit linearity in the operations of the cipher

Question 17

What is a Chosen Plaintext Attack ?

Answer 17

A CPA is a kind of cryptanalysis attack where the adversary has the ability to choose and encrypt plain text messages of their choice and recover the corresponding ciphertext

Question 18

How can a cipher protect against CPA attacks ?

Answer 18

There are 2 ways:
1. Using a randomized algorithm; this works by choosing a random string r from a space R, and this string is used to encrypt the plaintext. The only security requirement for this method is that the space R be significantly large enough, so that there are no repetitions.

2. Using nonce based encryption: in this process the cipher uses a unique non repeating value called a nonce as an additional input to the key and message, to carry out encryption or decryption.

Question 19

When using Cipher Block Chaining mode, what are two ways to guarantee CP (Chosen Plaintext) security

Answer 19

1. Using CBC with an Initialization Vector (IV): here the IV needs to be unpredictable and by extension random, else the cipher is vulnerable to CP attacks
2. Using CBC with a non-random unique nonce, but the nonce must be encrypted using a separate key. This means the cipher will require two purpose keys. One for encrypting the message blocks and the other for encrypting the nonce.

Question 20

When is a MAC (Message Authentication Code) secure ?

Answer 20

A MAC is secure when it is unforgeable under a chosen message attack

Question 21

Briefly describe the Carter-Wegman MAC

Answer 21

The Carter-Wegman MAC is a construction that builds a many time mac from a one time mac. It does so by using a random nonce

Question 22

What is the Merkle Damgard Paradigm ?

Answer 22

The Merkle Damgard paradigm is a mathematical construct that allows us design a hash function for large messages from a hash function for small messages.

Question 23

Briefly describe the Davies-Meyer compression function

Answer 23

The Davies-Meyer compression function provides a construct that allows one build a secure hash function from a block cipher. It takes as input some message m and a chaining function H and encrypts the result of the chaining function using the message block as a key. The final output is Xored with the output of the chaining function. H(m,h).= E(m, H) Xor H

Question 24

What guarantee does CPA-Secure (Chosen Plain Text Security) encryption provide ?

Answer 24

CPA-Secure encryption only provides confidentiality and not integrity. Security is only guaranteed provided an adversary is only eavesdropping. It is broken when the adversary can tamper with the ciphertext enroute.

Question 25

Briefly describe authenticated encryption ?

Answer 25

Authenticated encryption is a cipher with efficient algorithms for encryption and decryption, where the decryption algorithm outputs an additional value called bottom the absence of which indicates that the ciphertext has been tampered with and should be rejected.

Question 26

What two properties must an authenticated cipher satisfy ?

Answer 26

1. The cipher should be secure under a chosen plaintext attack (CPA)
2. It has ciphertext integrity

Question 27

What two properties must an authenticated cipher satisfy ?

Answer 27

1. The cipher should be secure under a chosen plaintext attack (CPA)
2. It has ciphertext integrity

Question 28

What are the limitations of a CCA secure cipher ?

Answer 28

1. It doesn’t protect against replay attacks
2. It doesn’t protect against side channel attacks (etc timing attacks)

Question 29

What’s the best approach to achive CCA security given a CPA secure cipher and a secure MAC ?

Answer 29

Encrypt-then-Mac. This means that the message (plaintext) should first be encrypted and resulting cipher text signed with the MAC algorithm. This gurantees CCA security

Question 30

What is the the distinction between a Shanon cipher and a computational cipher ?

Answer 30

Any deterministic cipher is a Shannon cipher; however, a computational cipher
need not be a Shannon cipher (if it has a probabilistic encryption algorithm), and a Shannon
cipher need not be a computational cipher (if its encryption or decryption operations have no
efficient implementations).

Question 31

The Password Based Key Derivation Function is susceptible to dictionary attacks, why is this is so.

Answer 31

This is because the user’s passwords have a low degree of entropy, making it quite feasible to carry out a dictionary attack.

Note that HKDF cannot be used for KD using passowrds for the same reason

Question 32

Explain the concept of expansion under Key derivation where the keyspace is not uniformly distributed.

Answer 32

For a PRF to be secure the keyspace must be uniformly random, this gurantees that the output of our PRF is indistinguishable from truly random outputs. To derive keys from a key space that isn’t uniform, we have to use an extractor function. The purpose of this function is to introduce entropy into the key space. This is done by using a random salt, along with the input key. The output of this function is one that is indistinguishable from uniform

Question 33

What is deterministic encryption and what are some usecases for it ?

Answer 33

An encryption scheme that always outputs the same ciphertext for a plaintext. Useful in providing security in database applications; eg the encryption of database indexes.