2. Cryptography - Control Questions Flashcards
What is the basic model of (conventional) encryption? (figure)
ábra
How does the Caesar cipher work?
○ 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
What do we mean by the key space of a cipher?
What type of attack is possible if the key space is small?
○ An algorithm’s key space refers to the set of all possible permutations of a key.
○ key space small → brute force attack
How does the monoalphabetic substitution cipher work?
○ generalization of the Caesar cipher
○ replacement of letters is determined by a permutation
○ the key is the permutation
○ the key space is huge
Why having a large key space is only a necessary (but not sufficient) condition for a cipher to be
secure?
○ 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
How does the Diffie-Hellman key agreement protocol work?
○ 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
Which hard mathematical problem is the DH protocol related to?
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
Which hard mathematical problem is the RSA scheme related to?
○ 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
List a few practical applications of cryptography today!
○ 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)
How does the one-time work?
○ 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 )
What does perfect secrecy mean intuitively?
○ informally: observing the encrypted message provides no information (in an information
theoretic sense) about the original message
What are the disadvantages of the one-time pad?
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
What are the two main types of modern ciphers?
What are their basic operating principles?
○ 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
What are the block size and the key size of AES?
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
How do the following block encryption modes work: ECB, CBC, CTR?
ábrák (3. diasor)
What is the Kerckhoffs’ principle? What attacker models do you know?
○ 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
What is the average complexity of the exhaustive key search attack?
average complexity is 2 k-1 , if key length is k bits
What is a cryptographic hash function?
○ 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)
What are the desired security properties of hash functions?
○ 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)
What is the birthday paradox, and how is it related to hash functions?
○ 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
What services do MAC functions provide and how?
○ 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
What is the main idea of public key encryption?
typically, the plaintext (and the ciphertext) consists of a few thousands bits → operation is
similar to symmetric-key block ciphers
Why do we use a hybrid approach for
encrypting large messages instead of pure
public key encryption? How does it work?
○ 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)
What services do digital signature schemes provide and how?
○ 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
What is the hash-and-sign paradigm?
○ 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
Why are the advantages of using a crypto library (instead of developing your own crypto
implementations)?
○ 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…
