2. Cryptography - Control Questions

Question 1

What is the basic model of (conventional) encryption? (figure)

Answer 1

ábra

Question 2

How does the Caesar cipher work?

Answer 2

○ substitution cipher (replaces letters of the plaintext)
○ each letter is replaced by the letter at some fixed number of positions (e.g., 3) down the alphabet
○ the key is the value of the shift (of the alphabet)
○ what is the size of the key space? size of the key space is 26-1 = 25 easy to break

Question 3

What do we mean by the key space of a cipher?

What type of attack is possible if the key space is small?

Answer 3

○ An algorithm’s key space refers to the set of all possible permutations of a key.
○ key space small → brute force attack

Question 4

How does the monoalphabetic substitution cipher work?

Answer 4

○ generalization of the Caesar cipher
○ replacement of letters is determined by a permutation
○ the key is the permutation
○ the key space is huge

Question 5

Why having a large key space is only a necessary (but not sufficient) condition for a cipher to be
secure?

Answer 5

○ azért mert hiába nagy a key-space ha az értékek nem randomak, pl. ha a cipher ugyanazt a 2
számot generálja mindig a lehetséges 1millióból akkor semmit nem ér. ábécés példa ugyanez,
kiszámíthatóak az értékek..
○ every language has its own letter statistics
○ in case of monoalphabetic substitution, the ciphertext preserves the letter statistics of the original
plaintext!
■ after decoding the most frequent and least frequent letters, the rest of the text can be
figured out much like solving a crossword puzzle

Question 6

How does the Diffie-Hellman key agreement protocol work?

Answer 6

○ if an attacker can only eavesdrop the communications between Alice and Bob, then he has only
g x mod p and g y mod p
○ to compute g xy mod p, he would need x or y

Question 7

Which hard mathematical problem is the DH protocol related to?

Answer 7

it is hard to compute x from g x mod p
■ this is the so called ”discrete logarithm” problem
■ no polynomial time algorithm is known to solve it
■ if p is large, then computing discrete logarithm (mod p) is practically infeasible

Question 8

Which hard mathematical problem is the RSA scheme related to?

Answer 8

○ key-pair generation algorithm:
■ choose two large primes p and q (easy)
■ n = pq, 𝚽(n) = (p-1)(q-1) (easy)
■ choose e, such that 1 < e < 𝚽(n) and gcd(e, 𝚽(n)) = 1 (easy)
■ compute the inverse d of e mod f(n), i.e., d such that ed mod 𝚽(n) = 1 (easy if p and q are
known)
■ output public key: (e, n) — public exponent and modulus
■ keep private key: d (and p, q) — private exponent (and the primes)
○ encryption algorithm:
■ represent the plaintext message as an integer m 𝟄 [0, n-1]
■ compute the ciphertext c = m e mod n decryption algorithm:
■ compute the plaintext from the ciphertext c as m = c d mod n

Question 9

List a few practical applications of cryptography today!

Answer 9

○ secure communication over public channels / networks »
■ WWW (https / TLS)
■ GSM/…/4G
■ WiFi (WPA, WPA2)
■ Bluetooth
○ secure data storage
■ disk encryption (TrueCrypt, BitLocker, …)
■ encrypted cloud strage (Tresorit, CipherCloud, …)
○ authentication
■ smart cards (e.g., bank cards)
■ ignition keys of cars
■ electronic tickets in public transport (automated fare collection systems)
○ software authentication and integrity protection
■ digitally signed code (e.g., drivers, applets, Android packages)

Question 10

How does the one-time work?

Answer 10

○ encryption
■ represent the message as a sequence of bytes: m 1 m 2 … m L –
■ take a sequence of true random bytes: k 1 k 2 … k L
■ obtain the encrypted message by XOR-ing them together:
● m 1 m 2 … m L + k 1 k 2 … k L = c 1 c 2 … c L where c i = m i + k i for all i = 1, …, L
○ decryption
■ XOR the same stream of key bytes to the encrypted message:
● c 1 c 2 … c L + k 1 k 2 … k L = m 1 m 2 … m L (because c i + k i = m i + k i + k i = m i )

Question 11

What does perfect secrecy mean intuitively?

Answer 11

○ informally: observing the encrypted message provides no information (in an information
theoretic sense) about the original message

Question 12

What are the disadvantages of the one-time pad?

Answer 12

how to send the key in a secure way to the recipient?
■ in practice, the only possibility is to exchange a large amount of truly random key
material in an out-of-band manner (e.g., by physical meeting) before the communication
takes place
■ we have to do this with all potential communication partners
■ key management becomes cumbersome

Question 13

What are the two main types of modern ciphers?

What are their basic operating principles?

Answer 13

○ Stream ciphers
■ idea: simulate the truly random key stream of the one-time pad with a pseudo-random
sequence generated from a random seed
■ terminology:
● mi – plaintext character (byte)
● ci – ciphertext character (byte)
● zi – key-stream character (byte)
● K – key/seed (vector of bytes)
● G – key-stream generator
■ application :
● encryption of data → confidentiality services
● PRNG (Pseudo-Random Number Generator)
■ examples: LFSR based (typically hardware), RC4 (software)
○ Block ciphers
■ block ciphers operate on blocks of bits (typical block size is n = 128 bits)
■ they are stateless (unlike stream ciphers)
■ they cannot be efficiently distinguished from a random permutation –
● if K is unknown, the output is unpredictable (even parts of it, and even when
some input-output pairs are known)
● notation: – E(K, X) or E K (X) for encryption
● E K
-1 (Y) or D K (Y) for decryption terminology
● X – plaintext block (bit vector of length n)
● Y – ciphertext block (bit vector of length n)
● K – key (bit vector of length k)
● E – encryption/encoding algortihm
● D – decryption/decoding algorithm

Question 14

What are the block size and the key size of AES?

Answer 14

Az AES a Rijndael kódolás olyan változata, ahol a blokkméret szigorúan 128 bit, a kulcs pedig 128,
192 vagy 256 bit.
// https://hu.wikipedia.org/wiki/Advanced_Encryption_Standard

Question 15

How do the following block encryption modes work: ECB, CBC, CTR?

Answer 15

ábrák (3. diasor)

Question 16

What is the Kerckhoffs’ principle? What attacker models do you know?

Answer 16

○ Kerckhoff’s principle – it is assumed that the encryption algorithm is known to the attacker
○ attack models
■ ciphertext-only attack
■ known-plaintext attack
■ (adaptive) chosen-plaintext attack
■ (adaptive) chosen-ciphertext attack

Question 17

What is the average complexity of the exhaustive key search attack?

Answer 17

average complexity is 2 k-1 , if key length is k bits

Question 18

What is a cryptographic hash function?

Answer 18

○ a hash function is a function that maps arbitrary long messages into a fixed length output (n bits)
○ notation and terminology:
■ x – (input) message
■ y = H(x) – hash value, message digest, fingerprint
○ typical applications:
■ the hash value of a message can serve as a compact representative image of the message
(similar to fingerprints)
■ increase the efficiency of digital signatures by signing the hash instead of the message
(expensive operation is performed on small data)

Question 19

What are the desired security properties of hash functions?

Answer 19

○ weak collision resistance (2nd preimage resistance)
■ given an input x, it is computationally infeasible to find a second input x’ such that H(x’)
= H(x)
○ strong collision resistance (collision resistance)
■ it is computationally infeasible to find any two distinct inputs x and x’ such that H(x) =
H(x’)
○ one-way property (preimage resistance)
■ given a hash value y (for which no preimage is known), it is computationally infeasible to
find any input x such that H(x) = y
○ collision resistant hash functions can typically be modeled as a random function (similar to block
ciphers)

Question 20

What is the birthday paradox, and how is it related to hash functions?

Answer 20

○ when drawing elements randomly (with replacement) from a set of N elements, a repeated
element will be encountered with high probability after ~sqrt(N) selections
○ Birthday attack on hash functions
■ brute force attack (similar to exhaustive key search in case of ciphers)
■ generate inputs randomly and hash them
■ after about ~sqrt(2 n ) = 2 n/2 randomly chosen inputs, a collision pair will occur with high
probability
■ in order to resist birthday attacks, n/2 should be large enough

Question 21

What services do MAC functions provide and how?

Answer 21

○ Message Authentication Code (MAC)
○ a MAC function is a function that maps an arbitrary long
message and a key (k bits) into a fixed length output (n bits)
○ can be viewed as a hash function with an additional input (the
key)
○ services:
■ message authentication and integrity protection: after
successful verification of the MAC value, the receiver is
assured that the message has been generated by the sender
and it has not been altered in transit

Question 22

What is the main idea of public key encryption?

Answer 22

typically, the plaintext (and the ciphertext) consists of a few thousands bits → operation is
similar to symmetric-key block ciphers

Question 23

Why do we use a hybrid approach for
encrypting large messages instead of pure
public key encryption? How does it work?

Answer 23

○ public key crypto is slower than
symmetric key crypto and require
longer (e.g. 2048 bits) keys for
similar security
○ the speed problem can be solved with
hybrid encryption: (ábra)

Question 24

What services do digital signature schemes provide and how?

Answer 24

○ similar to MACs but they are
■ unforgeable by the receiver
■ verifiable by a third party
○ services:
■ message authentication and integrity protection: after successful verification of the
signature, the receiver is assured that the message has been generated by the sender and it
has not been altered
■ non-repudiation of origin: the receiver can prove this to a third party (hence the sender
cannot repudiate)
■ examples: RSA, DSA, ECDSA

Question 25

What is the hash-and-sign paradigm?

Answer 25

○ public/private key operations are slow
○ increase efficiency by signing the hash of the message instead of the message
○ it is essential that the hash function is collision resistant

Question 26

Why are the advantages of using a crypto library (instead of developing your own crypto
implementations)?

Answer 26

○ implementation time
■ can take years
■ while you can spend that time on your actual product
○ implementation bugs
■ can cause major security failures (e.g., HeartBleed attack on OpenSSL)
■ sometimes bugs can be subtle, and it may take a long time to identify their cause
○ pitfalls of random number generation
■ security flaws in random generators are really easy to accidently create…
■ and really hard to discover after the fact (e.g., random number bug in Debian)
○ naive implementations allow for side-channel attacks
○ performance optimization can be critical to your application
○ compliance issues
○ additional features in libraries come as bonus…