Misc

Question 1

Modular inverse e.g 3^(-1) mod 7 means solving…

Answer 1

3 • x == 1 mod 7

Question 2

Euler phi function phi(n) counts …

Answer 2

Number of integers between 1 and n that are relatively prime to n.

Question 3

Chinese remainder theorem can be used to solve…

Answer 3

System of congruences with different moduli

Question 4

Substitution cipher is vulnerable to …

Answer 4

1. Frequency analysis attack (analysis of frequency of characters in ciphertext and matching to known letter frequency)
2. Known plaintext attack (if the attacker knows part of plaintext e.g ‘May this email find you well’)
3. Chosen ciphertext attack (same as known, achieved through social engineering)

Question 5

Shift cipher is most vulnerable to…

Answer 5

Brute force (exhaustive search) because of very small key space

Question 6

In a One-Time pad, the key must be at least as long as the message.

Answer 6

True

Question 7

4 goals of cryptography

Answer 7

1. Confidentiality (data only to authorized users)
2. Integrity (guarantee that data is untampered during transmission/storage)
3. Authentication (sender/receiver are who they claim to be)
4. Non-repudiation (prevents denial of involvement in transaction with proof of origin or receipt that cannot be disputed, forced accountability)

Question 8

Passive attacker threatens which goal?

Answer 8

Confidentiality

Question 9

Active attacker threatens which goal?

Answer 9

All of them

Question 10

What are pros and cons of symmetric key cryptosystems?

Answer 10

Pro: very fast
Cons: key management (ever user pair needs key O(n^2)

Question 11

What is Kerckhoff’s Principle?

Answer 11

Security should only depend on the key itself. Assume attacker knows what algorithm is being used.

Question 12

What is Square and Multiply used for?

Answer 12

Solve a^b mod n for a large exponent b

Question 13

What is the concept of diffusion?

Answer 13

One character change in plaintext should affect as much ciphertext characters as possible

Question 14

What is the concept of confusion?

Answer 14

The key/plaintext shouldn’t relate to ciphertext in a simple way

Question 15

An affine cipher can be broken with 2 plaintexts.

Answer 15

True

Question 16

Solving -21 mod 26 means…

Answer 16

Adding 26 to -21 until we get a positive result [0, 25]

Question 17

RSA is secure under assumption that …

Answer 17

Factorization is hard

Question 18

Diffie-Helman is secure under the assumption that …

Answer 18

Discrete log problem is hard

Question 19

Rabin cryptosystem is secure under the assumption that …

Answer 19

Factorization is hard (factoring large composites)

Question 20

Rabin is secure against passive adversary.

Answer 20

True

Question 21

What are timing attacks?

Answer 21

By measuring time required to perform decryption, an attacker can figure out the private key

Question 22

Name 2 countermeasures to timing attacks

Answer 22

1. Constant exponentiation time
2. Random delays

Question 23

2 ways to break RSA without factoring n

Answer 23

1. Low exponent attack
2. Common modulus attack

Question 24

Describe forward search attack

Answer 24

If message space is small, attacker can create dictionary of encrypted messages (since pk is known, encrypt all possible messages and store). When attacker seems a message, it can compare to encrypted and find out the message.

Question 25

RSA and Rabin both susceptible to …

Answer 25

Chosen ciphertext attack

Question 26

MAC ensures…. BUT NOT …

Answer 26

Authenticity and integrity BUT NOT non-repudiation

Question 27

Purpose of ‘salt’ in hashing?

Answer 27

Identical x’s will result in different hashes due to salt

Question 28

Describe offline dictionary attack

Answer 28

Attacker retrieves hashed password database, go offline and compute hash (with same algorithm used by system) for common passwords to compare with db records

Question 29

Which is better for confidentiality: H(M) or MACk2(M)

Answer 29

MAC because H(M) is unkeyed so attacker can guess M

Question 30

Name 3 adversarial goals:

Answer 30

1. Total break (attacker finds secret for signing, so can forge any signature) 2. Selective forgery (attacker able to create valid signatures on message chosen by someone else) 3. Existential forgery (attacker can create a pair message, signature such that the signature of message is valid)

Question 31

Does a Hash provide 1. Integrity, 2. Authentication 3. Non-repudiation. Which type of key is used?

Answer 31

Yes to integrity. No to authentication and non-repudiation. Unkeyed.

Question 32

Does a MAC provide 1. Integrity, 2. Authentication 3. Non-repudiation. Which type of key is used?

Answer 32

Yes to integrity and authentication, no to non-repudiation. Symmetric keys.

Question 33

Does a Digital Signature provide 1. Integrity, 2. Authentication 3. Non-repudiation. Which type of key is used?

Answer 33

Yes to integrity, authentication and non-repudiation. Asymmetric keys.

Question 34

Digital signatures prevent replay attacks

Answer 34

False

Question 35

Describe a replay attack

Answer 35

1. Attacker intercepts valid communication 2. Attacker replays message/request (e.g login attempt, payment authorization, command) at later time to impersonate sender 3. System treats replayed message as legitimate and performs intended action

Question 36

Rabin and RSA are examples of …

Answer 36

Public-key cryptosystems that provide encryption and digital signatures

Question 37

In crowds, jondos know the final destination of messages

Answer 37

True

Question 38

In RSA, key setup operations are performed by the sender

Answer 38

False

Question 39

Weak collision

Answer 39

Given an arbitrary x1, it is hard to find an x2 such that h(x1) = h(x2)

Question 40

Strong collision property

Answer 40

There exists no x1 and x2 such that h(x1) = h(x2)