All things crypto

Question 1

What is the high level goal of cryptography? How is this split this into sub-examples?

Answer 1

The common goal: don’t let the attacker learn anything about the contents of the messages and don’t let them tamper with them either.

1) Protecting data in motion (from client to server or vice versa)
2) Protecting files at rest

Question 2

What are the 3 main security goals of cryptography?

Answer 2

1) Confidentiality: Attacker cannot know or learn about the contents of the data
2) Integrity: the attacker cannot modify data
3) Authentication: the attacker cannot spoof/make someone believe the message was sent by someone else

Question 2

What is Symmetric encryption?

Answer 2

Symmetric encryption uses the same key for encrypting and decrypting data. This key must be pre-shared to both parties

Question 2

Explain what a Cipher is

Answer 2

A form of symmetric encryption. There is encryption and decryption algorithm that uses the same key (K) to turn plaintext message (m) to ciphertext message (c).

Encrypt(K, m) = c
Decrypt(K, c) = m

Question 3

What is the difference between a passive attacker and active attacker in cryptography? What might their goals be?

Answer 3

Passive: can see the ciphertexts but cannot modify them. Goal: learn something, anything about the plaintext simply from the ciphertexts
Active: Everything that a passive attacker can do, but they can also modify the ciphertexts!! (inject their own ciphertexts, reorder + delete) , AKA, MITM attacker (man in the middle)

Question 4

What are the requirements of a secure cipher?

Answer 4

1) Correctness: the decrypt algorithm must reveal the same, original plaintext message
2) confidentiality: the ciphertext on its own will reveal nothing about its plaintext (besides maybe the message length)

Question 5

What is the ROT13 (aka “Caesar cipher”)?

Answer 5

Encrypt(K, m): shift each letter of plaintext over by K positions in the alphabet

Ex: Plaintext: “DEFGH” becomes ciphertext: “FGHKL”

Question 6

What is the Substitution Cipher? Is it secure?

Answer 6

Encrypt(K, m): K is a permutation on the alphabet. Apply this permutation on each letter

This is not secure because the distribution of English letters is uneven (vowels appear more, etc) so (given a long enough message) you can easily guess what each corresponding letter is based on the frequencies.

Question 6

What is Kerckhoff’s Principle?

Answer 6

To evaluate the secrurity of crypto algorithms: Assumes the attacker knows all the algorithms and how they are implemented. The only thing unknown is the key

Question 6

What is a OTP? What are its properties? Is it secure?

Answer 6

Where the plaintext m is length L, the key k is also a bitstring of length L.

Encrypt(K, m) : output k ^ m = c
Decrypt(K, c) : output k ^ c = m

proof: k ^ c = k ^ (k ^ m) = (k ^ k) ^ m = m

OTP in itself is very secure (only thing attacker knows is the length of message), but hard in practice for very long messages

Question 7

What are 2 techniques we have adopted to use OTPs in practice?

Answer 7

Stream cipher and nonces

Question 7

How do we define our SECURE encryption goal?

Answer 7

The enryption must hide all partial information about plaintexts. If an attack succeeds without a key, the encryption algorithm is INSECURE

Question 7

Why is it insecure to re-use a OTP? Are there any real-life examples?

Answer 7

Let’s say we have m1, m2 that both turn into c1, c2 using the SAME OTP K.

c1 ^ c2 = m1 ^ m2… we can use crib-dragging to slowly obtain pieces of the messages! Once we have one full message, we can get a full break.

Real attack: Project Venona in the 1940s on Soviet encryption via US

Question 8

Explain how Stream Ciphers work and what OTP issue they solve. What is its security goal? Is it secure? What are possible attacks?

Answer 8

Take a small secret key k, and plug it into the stream function: G(). G(k) = large key stream. Essentially use G(small key) = OTP.

This solves the OTP issue of keys being too long. Now we can encrypt long messages with small key.

G(small key) needs to look random. Stronger requirment: passes statistical tests

Brute force attack: given our “OTP” from G(small key), try to plug in all values of k to try and get our “OTP”. then decrypt it with small key

Question 9

What is RC4 (Ron’s Cipher #4)?

Answer 9

RC4 is a stream cipher from 1987. It is INSECURE.

Question 10

What is ChaCha20?

Answer 10

A stream cipher from 2007. supports nonces. SECURE

Question 11

Can you reuse a pad with Stream Ciphers?

Answer 11

NO. Insecure

Question 12

Explain what nonces are.

Answer 12

To support pad reusing, we can use stream cipher + nonce. Now, our G(key) algorithm takes G(key, nonce) = OTP. Nonce is very small, we only have to replace this.

Again, G(nonce, key) needs to look “random” especially in the context of the nonce

Reusing nonce = reusing pad.

Question 13

Explain what happened with the pad re-use of WEP? What were the solutions created from this?

Answer 13

IEEE 802.11b WEP was the wifi standard a bit ago. However, its nonce repeats after 16mil frames. Also when you reset power cycle, the nonce resets to 0. Essentially, the pad was being reused over and over again!

Now, we use a larger nonce space and force re-keying more often. We can also set the nonce to be a combination of packet number, address, etc so that it is always different.

Question 14

What type of attacker do MACs protect against + security goal do they satisfy?

Answer 14

aka= Message Authentication Codes. They satisfy integrity goal by protecting against active attackers who can tamper with the data.

Question 15

Why do OTP & Stream Ciphers not provide integrity?

Answer 15

There is no way of being able to tell if the cipher text was modified. Once could modify the cipher text so that it decodes from (original: “pay alice”) to modified: “pay david” for instance. Essentially, on its own, encryption does not provide integrity.

Question 16

Explain how a MAC works.

Answer 16

You append a special tag t to the end of message m.

MAC() algorithm takes in key k, message m, outputs an unpredictable tag t. then you send over this message + tag and can verify using secret key to check if tag is the same. If it is different, the message has been modified!!

Question 16

What is the main security goal of MAC?

Answer 16

Unforgeability: basically, you cannot create (Forge) a tag yourself.

Question 16

What are the best MACs to use in practice?

Answer 16

HMAC or Poly1305-AES

Question 17

What is Authenticated Encryption? What are algorithm combos that support this?

Answer 17

Basically encryption that provides both confidentiality and integrity via using a good stream cipher + MAC.

Ex: Combo of Salsa20 + HMAC-SHA2, OR better yet: AES-GCM is an algorithm that is built in with both

Question 17

What are Hash functions? What are the 3 properites of a secure hash function?

Answer 17

Hash function takes in a message M (of arbitrary length) and outputs H(M) of fixed length.

**1) One-way: ** given H(M) we cannot determine M!
**2) Collision resistant: ** we cannot find two messages M and M’ that will hash to the same thing!! (important)
3) Second-preimage resistance: Given H(M), we cannot find an M’ so that H(M) = H(M’)

I don’t understand Second-preimage resistance, but I don’t htink it’s important

Question 18

Why are hash collisions bad?

Answer 18

An attacker can take advantage of this. If one message M and M’ both hash to the same thing, the attacker can use M’ to forge!

Question 19

State the secureness of these hash functions: MD5, SHA-1, SHA-256, SHA-512, SHA-3

Answer 19

MD5 is extremely broken. SHA-1 is also broken. The rest are secure and still used

Question 20

What are the similarities and differences between Hash functions and MACs?

Answer 20

Similarities: both map long input -> short output.
Differences: Hash function do NOT use keys. Anyone can compute the hash of anything they want, and they do not preserve integrity

Question 21

What is the standard hash + MAC algorithm used?

Answer 21

HMAC

Question 22

Describe how a length extention attack works

Answer 22

Attacker can bypass integrity by forging a message. Essentially, can hash their own message with an extra bit of length added to a an already hashed message. This message will pass the authentication check!

Question 23

Explain the 4 quadrants of the cyrpto matrix

Answer 23

Symmetric Encryption (ciphers): Pre-shared key, preserves confidentiality
MAC: Pre-shared key, preserves authenticity and integrity
Public Key Encryption: Asymmetric key generation, preserves confidentiality
**Digital Signatures: ** Asymmetric key generation, preserves integrity

Question 24

What are block ciphers?

Answer 24

Easy definition: a substitution cipher with a very large alphabet and a very small key.

Question 25

What is AES?

Answer 25

(Advanced Encryption Standard)
In 1997 NIST ran a competition to develop the best standard encryption algorithms. Rijndael was chosen and standardized as the block cipher. It breaks message M into blocks and encrypts each block

Question 26

How is AES secure?

Answer 26

It upholds confidentiality because all of the outputs look very random and independent

Question 27

What are the various modes of AES? Which are secure to use?

Answer 27

ECB: INSECURE!!
CTR & CBC: fine, but no integrity is provided
GCM: is fully authenticated encryption (provides both confidentiality and integrity)

Question 28

What is Asymmetric (Public) Key Crypto? How does it work?

Answer 28

Basically: no shared key. there are 2 separate keys that are mathematically related

3 algorithms:
KeyGen() = PK (public key), SK (secret key)
Encrypt (PK, m) = ciphertext c
Decrypt(SK, c) = message m

Question 29

How does the Key Generation work behind public key encryption?

Answer 29

RSA is the standard used.
1) pick p and q as large random prime numbers (HUGE HUGE numbers)
2) compute N = p times q
3) e is typically a default value (e = 3 or e = 65537 are common)
4) compute ed with a very fancy equation that uses both p and q, and mod stuff.
5) (N, e) = public key, (N, d) = private key

Via number theory, it is VERY difficult to find the secret key?

Question 30

What is the best known attack on RSA? What is the recommended length of N?

Answer 30

You can try to factor N to get the secret key. (hard because factoring algorithms are very hard but they do exist nonetheless). This does work, but against very large values of N, it is very difficult (p and q should be very large then for RSA to be secure). Recommended length of N is 2048.

Question 31

What are Digital Signatures? and how do they work? What is its main security goal?

Answer 31

A way to preserve authenticity/integrity with asymmetric key generation:

KeyGen() = PK, SK
Sign(SK, M) = signature
Verify(PK, M + signature) = yes or no

Main security goal: Unforgeability- they cannot forge a digital signature on the message!

Question 32

What are some potential attacks on Plain RSA digital signatures?

Answer 32

1) you can forge signature on M = 1
2) You can forge a signature n any messages that are perfect cubes (M= 8 for example)

3) Malleability weakness

Not sure what malleability weakness is (how is it different from 2?)

Question 33

What are RSA signautres with encodings?

Answer 33

After the Sign() function, you run encode(M) and after the verify function you run encode(M). encode maps bit strings to a number between 0 and N

Question 34

What are digitial signatures most commonly used for?

Answer 34

Authentication! here is the flow:

Blase with PK, SK goes to server. Server says prove it! here are some random bytes r. Blase goes, okay! I’ll sign it with my secret Key. Then Blase uses the corresponding public key to verify if the signature is correct.

Question 35

Why can’t we simply use asymmetric crypto for everything?

Answer 35

Symmetric key crypto algorithms are MUCH faster because producing a PK and SK using RSA takes a lot of computational power (need to use extremely huge values of N)

Question 36

What is Hybrid Encryption?

Answer 36

Asymmetric: Key exchange!
Symmetric: encrypting and decrypting all the rest of the data

Question 37

What are the 4 steps of Public Key Exchange? (Hybrid encryption)

Answer 37

1) Server uses KeyGen to create a PK and SK.
2) Server sends PK to client
3) Client picks a random K (key) message and encrypts it using their PK : Encrypt(PK, K) = C
4) Server Decrypt(SK, C) = K. Now K is the shared symmetric key

Question 38

How can an active attacker infilatrate key exchange process? (in hybrid encryption)

Answer 38

1) Active attacker will intercept the PK that is sent from Server to client and replace with a PK they KNOW, PK’.
2) When the attacker sends over C, it is encrypted with the fake PK’. The attacker can figure out K by decrypting it with their corresponding fake SK’. Now they have the key K!
3) They send over the C encrypted with the original PK so that now the server still thinks the connection is secure