Basics of Cryptography

Question 1

What does a symmetric encryption scheme contain?

Answer 1

• Plaintext: the message that should be securely transmitted
• Encryption Algorithm: the algorithm which scrambles the plaintext
• Secret Key: additional input to the encryption, used to control the scrambling
• Ciphertext: the result of applying the encryption algorithm (with the secret key) to the plaintext
• Decryption Algorithm: inverse of Encryption Algorithm, turning Ciphertext and Secret Key back to the Plaintext

Question 2

What is the Kerckhoff’s principle?

Answer 2

• Security of a cryptographic algorithm must rely only on secrecy of the key, not the secrecy of the algorithm
• We must assume that the algorithm is public knowledge or can be reconstructed

Question 3

Caesar Cipher

Answer 3

Encryption rotates all characters three forward
Decryption rotates characters three backward

Not secure by any standard, secret is in the algorithm

Question 4

General Shift Cipher

Answer 4

Generalization of Caesar’s cipher, k is shift width

-> crack brute force

Question 5

Substitution Cipher

Answer 5

Key k is substitution table
Encryption of plaintext through lookup in table
Decryption via inverse lookup in table
-> crack through Letter frequencies in English text
-> crack brute force

Question 6

Vigenère Cipher

Answer 6

Uses a random key of length n
- for each i-th character, shift it by i % n’th position in key (mod 26)
Crack:
- determine key length
-> pick n, conduct frequency analysis for every n-th character
use frequency analysis for each offset in the n-long key

Question 7

Stream ciphers vs. block ciphers

Answer 7

§ Stream cipher encrypts/decrypt continuous stream of data

• requires a continuous key stream (either OTP or with a generator)
• requires significant amount of state to be exchanged (or kept)

§ Block cipher splits plaintext into fixed-size blocks

• requires single key
• permutes input based on key
• continues with next block

Question 8

ECB - single bit failure in c(decryption), single bit failure in IV(Decryption), encrypted parallel, random read access

Answer 8

A single corrupted bit in the ciphertext will lead to a complete failure in the same block, because the key will be used on it afterwards. But this will not affect the others.

Nothing will happen since it is not using an IV.

Every block is encrypted with the same key, therefore all of them can be encrypted in parallel. Because the decryption operates the same way, it can also be fully parallel.

Encryption parallelizable: Yes
Decryption parallelizable: Yes
Random read access: Yes

Question 9

CBC - single bit failure in c(decryption), single bit failure in IV(Decryption), encrypted parallel, random read access

Answer 9

A single corrupted bit in the ciphertext will lead to a complete failure in the same block and will affects one bit in the next plaintext block. Because the key will be used on the ciphertext with the bit failure, as it is only used to XOR after key usage in the next block. The following ones will remain unaltered.

Just a single bit will fail in the first block, because it only effects the XOR and the XOR is only affecting 1 bit. All the other blocks are decrypted without the usage of the IV.

Just one block can be encrypted in the same instance, because the previous encrypted message block is needed in the next message block for the encryption. However, the decryption can be fully parallelised, since only the ciphertext from the previous block is needed for the XOR in the next block and all ciphertexts are known. The key is the same for all blocks.

Encryption parallelizable: No
Decryption parallelizable: Yes
Random read access: Yes

Question 10

CTR - single bit failure in c(decryption), single bit failure in IV(Decryption), encrypted parallel, random read access

Answer 10

A single corrupted bit in the ciphertext will lead to single bit failure in the same block, as it is just being XORed with the key. All other blocks will remain unaltered.

Every block will break completely since every IV affects the key used in its block.

The encryption can be parallel, since the IV for every block can be generated at the same time. The counter added to each following IV is a known constant and can therefore be calculated. Each IV is then encrypted and used to XOR the message. The same applies to the decryption, because it operates the same way as the encryption.

Encryption parallelizable: Yes
Decryption parallelizable: Yes
Random read access: Yes

Question 11

Collision Resistant Hash Function (CRHF)

Answer 11

A hash function H is collision resistant if no “efficient” algorithm is known that finds a collision for H in suitable time.
A collision for H is a tuple (m1, m2) with
H(m1) = H(m2) ∧m1 ≠ m2

Question 12

Hash functions

Answer 12

informally: take as input data of arbitrary length and output data of fixed length n

Question 13

Preimage resistance (one-way property)

Answer 13

Given a hash value h, it is computationally infeasible to find any m, for which H(m) = h

Question 14

Second preimage resistance

Answer 14

Given any message m1, it is computationally infeasible to find a message m2 such that m1 ≠ m2 with H(m1) = H(m2)

Question 15

Avalanche effect in cryptography

Answer 15

A minimal change in the input should result in a significant change in the output
- Strict Avalanche Criterion (SAC): Flip a single bit in the input, every bit in the output should be flipped with 50% probability

Not all cryptographic algorithms have avalanche effect
- Shift and substitution ciphers: only single character is modified in output

When searching for AES, SAC had to be fulfilled by all contestants

Question 16

Merkle-Damgård Construction

Answer 16

Message M ->
Message M + Padding (so it fits the blocks of the hash)
Block b0 + Block b1 + Block bn
IV –h0(with Block b0)–>f–h1(with Block b1)–>f–hn(with Block bn)–>HASH h

Question 17

Diffie-Hellman Key Exchange

Answer 17

agree on common prime p and generator g
pick random a < p (private key), calculate A=g^a mod p (public key)
pick random b < p, calculate B=g^b mod p
A and B are exchanged
=> A calculates k=B^a mod p
=> B calculates k=A^b mod p

=> based on the discrete logarithm problem

Question 18

Assuming an active Man-in-the- Middle, i.e., an attacker who can modify messages, is Diffie- Hellman a secure way of establishing a shared key?

Answer 18

No, because he can then intercept and modify the public keys!

Question 19

Elgamal Crypto System

Answer 19

• also discrete logarithm problem

- randomizes messages similar to IV in block ciphers

Question 20

HMAC

Answer 20

• HMAC treats the hash function as a “black box.”

HMAC(K, M) = H[(K’ (+)􏱄 opad) || H[(K’ (+)􏱄 ipad) || M]]

1. Append zeros to the left end of K to create a b-bit string K’
2. XOR K’ with ipad to produce the b-bit block S_i
3. Append M to S_i
4. Apply H to the stream generated in step 3.
5. XOR K’ with opad to produce the b-bit block S_o.
6. Append the hash result from step 4 to S_o.
7. Apply H to the stream generated in step 6 and output the result.

Question 21

Elgamal Encryption

Answer 21

Bob:
Step 1:
1.  Pick random n-bit prime p
2. Pick random generator g 
3. Pick random x calculate h = g^x
Step 2
publish public key pk := ( p, g, h )
store private key sk := (p, g, x)

Alice picks random y and computes
K = h^y mod p (one time)
C1=g^y mod p
C2=K*M mod p
send pair (C1, C2)

Bob:
K = C1 ^x mod p
M = C2 * k^-1 mod p

Question 22

For any function H : {0, 1}^∗ → {0, 1}^n that takes arbitrary length inputs and returns outputs of length n, where n ∈ N is fixed, how many collisions are there, i.e. how many pairs of inputs x1,x2 ∈ {0,1}^∗ exist such that H(x1) = H(x2), but x1=/x2?

Answer 22

There is an infinite amount of collisions, since the length of the input may be infinite.

Question 23

Which gives a stronger guarantee: Second-preimage resistance or collision- resistance?

Answer 23

Collision-resistance gives the stronger guarantee, since the attacker has complete freedom in the way it may chose the collision. This means a single collision that is known to the attacker is enough for the attack to be considered successful. If this is ruled out, we know that an attacker will not be able to find even a single collision.
A successful second-preimage attacker must be able to find collisions with high probability for any input m1 that is given to the attacker. If the attacker fails to find collisions for a small fraction of all inputs, second-preimage resistance would still hold, even though the attacker will be be successful in finding a collision for most of the inputs.

Question 24

The RSA Algorithm

Answer 24

Step 1:

• Pick two random n-bit primes p and q, compute composite modulus N = p ∗ q
• Choose an arbitrary value e, sich that gcd(“Phi”(N), e) = 1
• Compute d = e^-1 mod “Phi”N

Step 2: publish public key pk := (N, e)
pk:=(p, q, d)

C = M^e mod N
M = C^d mod N

Question 25

Digital Signatures naïve RSA

Answer 25

Goal: Bob wants to sign message M for Alex
- Bob computes signatures as S = M^d mod N
(Bob’s public key is pk := (N,e) and the signature for M is S)
Goal: Alice wants to verify message’s signature
- Knows that M = M^(de) mod N since ed = 1 mod “Phi” (N)
- computes M’ = S^e mod N
- checks if M’ = M

Question 26

Digital Signatures: who do you trust?

Answer 26

Chain of Trust and Certificates

• > Building block: Certificates (it binds a public key to an identity)
• > Trusted Third Party referred to as Certificate Authority

Obtaining and distributing certificates

• CA verifies Bob’s identity and public key
• Bob transmit his certificate to Alex
• Alex must know CA’s public key (and trust it)
• Alex knows he can in the legitimacy of Bob’s public key due his trusting the Certificate Authority

Centralized PKI in Practice

• Certificate Authorities can authorize other parties to issue certificates
• To verify certificate, traverse up the chain of certificates

Web of Trust
- Bob knows Alice
- Alex knows Charlie and, after having checked his identity, attests
that Charlie’s public key is genuine
- Bob can establish a trusted path to Charlie (over Alex), so can decide based on that if he wants to trust Charlie

Question 27

Symmetric vs. asymmetric cryptography

Answer 27

Symmetric Cryptography
- Fast (2048 bit block decrypted in 0.000002s) - good
- 2^^(n −1) keys for n users - bad
- need to establish key securely - bad
Asymmetric Cryptography
- Slow (2048 bit message decrypted in 0.025s) - bad
- n keys for n users - good
- public keys are meant to be publicly known - good

Question 28

Hybrid encryption schemes

Answer 28

1. generate random session key K
2. Encrypt session key K with pk_bob –> RSAenc(pk_bob,K) –> Decrypts session key K with sk_bob
3. Encrypt data with session key K –> AESenc(K,data) –> Decrypt data with session key K
4. Other way around also possible