AppA-Crypto

Appendix A: Introduction to cryptographic algorithms and protocols: 

Appendix A: Introduction to cryptographic algorithms and protocols symmetric and asymmetric key encryption; hash functions; MAC functions; digital signatures; key establishment protocols; advanced authentication techniques;

Chapter outline: 

2 /80 Chapter outline A.1 Introduction A.2 Encryption A.3 Hash functions A.4 Message authentication codes A.5 Digital signatures A.6 Session key establishment protocols A.7 Pseudo-random number generators A.8 Advanced authentication techniques

Introduction : 

3 /80 Introduction security is about how to prevent attacks, or -- if prevention is not possible -- how to detect attacks and recover from them an attack is a a deliberate attempt to compromise a system; it usually exploits weaknesses in the system’s design, implementation, operation, or management attacks can be passive attempts to learn or make use of information from the system but does not affect system resources examples: eavesdropping message contents, traffic analysis difficult to detect, should be prevented active attempts to alter system resources or affect their operation examples: masquerade (spoofing), replay, modification (substitution, insertion, destruction), denial of service difficult to prevent, should be detected A.1 Introduction

Main security services: 

4 /80 Main security services authentication aims to detect masquerade provides assurance that a communicating entity is the one that it claims to be access control aims to prevent unauthorized access to resources confidentiality aims to protect data from unauthorized disclosure usually based on encryption integrity aims to detect modification and replay provides assurance that data received are exactly as sent by the sender non-repudiation provides protection against denial by one entity involved in a communication of having participated in all or part of the communication two basic types: non-repudiation of origin and non-repudiation of delivery A.1 Introduction

Some security mechanisms: 

5 /80 Some security mechanisms encryption symmetric key, asymmetric (public) key digital signature access control schemes access control lists, capabilities, security labels, ... data integrity mechanisms message authentication codes, sequence numbering, time stamping, cryptographic chaining authentication protocols passwords, cryptographic challenge-response protocols, biometrics traffic padding, route control, … A.1 Introduction

Chapter outline: 

6 /80 Chapter outline A.1 Introduction A.2 Encryption A.3 Hash functions A.4 Message authentication codes A.5 Digital signatures A.6 Session key establishment protocols A.7 Pseudo-random number generators A.8 Advanced authentication techniques

Classical model of encryption: 

7 /80 E D m plaintext K encryption key K’ decryption key E K (m) ciphertext D K’ (E K (m)) = m eavesdropping adversary Classical model of encryption goal of the adversary: to systematically recover plaintexts from ciphertexts to deduce the (decryption) key Kerckhoff’s principle: we must assume that the adversary knows all details of E and D security of the system should be based on the protection of the decryption key A.2 Encryption

Adversary models: 

8 /80 Adversary models ciphertext-only attack the adversary can only observe ciphertexts produced by the same encryption key known-plaintext attack the adversary can obtain corresponding plaintext-ciphertext pairs produced with the same encryption key (adaptive) chosen-plaintext attack the adversary can choose plaintexts and obtain the corresponding ciphertexts (adaptive) chosen-ciphertext attack the adversary can choose ciphertexts and obtain the corresponding plaintexts related-key attack the adversary can obtain ciphertexts, or plaintext-ciphertext pairs that are produced with different encryption keys that are related in a known way to a specific encryption key A.2 Encryption

Security of encryption schemes: 

9 /80 Security of encryption schemes an encryption scheme is secure in a given adversary model if it is computationally infeasible for the adversary to determine the target decryption key under the assumptions of the given model for many encryption schemes used in practice, no proof of security exists these schemes are used, nevertheless, because they are efficient and they resist all known attacks some encryption schemes are provably secure, however these schemes are often inefficient A.2 Encryption

Basic classification encryption schemes: 

10 /80 Basic classification encryption schemes symmetric-key encryption it is easy to compute K’ from K (and vice versa) usually K’ = K two main types: stream ciphers – operate on individual characters of the plaintext block ciphers – process the plaintext in larger blocks of characters asymmetric-key encryption it is hard (computationally infeasible) to compute K’ from K K can be made public (  public-key cryptography) A.2 Encryption

Block ciphers: 

11 /80 Block ciphers an n bit block cipher is a function E: {0, 1} n x {0, 1} k  {0, 1} n , such that for each K Î {0, 1} k , E (x, K) = E K (x) is an invertible mapping from {0, 1} n to {0, 1} n E … … … n bit input n bit output k bit key A.2 Encryption Block ciphers

Block cipher design criteria: 

12 /80 Block cipher design criteria completeness each bit of the output block should depend on each bit of the input block and on each bit of the key avalanche effect changing one bit in the input block should change approximately half of the bits in the output block similarly, changing one key bit should result in the change of approximately half of the bits in the output block statistical independence input and output should appear to be statistically independent A.2 Encryption Block ciphers

How to satisfy the design criteria?: 

13 /80 How to satisfy the design criteria? complex encryption function can be built by composing several simple operations which offer complementary – but individually insufficient – protection simple operations: elementary arithmetic operations logical operations (e.g., XOR) modular multiplication transpositions substitutions ... combine two or more transformations in a manner that the resulting cipher is more secure than the individual components A.2 Encryption Block ciphers

Example: DES (Data Encryption Standard): 

14 /80 Example: DES (Data Encryption Standard) input size: 64 output size: 64 key size: 56 16 rounds Feistel structure Initial Permutation F + F + F + F + … Initial Permutation -1 (64) (64) (32) (32) (48) (48) (48) (48) Key Scheduler (56) K K 1 K 2 K 16 K 3 X Y A.2 Encryption Block ciphers

Example: the DES round function F: 

15 /80 Example: the DES round function F Si – substitution box (S-box) P – permutation box (P-box ) + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + S1 S2 S3 S4 S5 S6 S7 S8 P key injection A.2 Encryption Block ciphers

Example: the DES key scheduler: 

16 /80 Example: the DES key scheduler each key bit is used in around 14 out of 16 rounds Permuted Choice 1 Permuted Choice 2 Left shift(s) Left shift(s) Permuted Choice 2 Left shift(s) Left shift(s) … (28) (56) K (28) (28) (28) (48) (48) K 1 K 2 A.2 Encryption Block ciphers

Exhaustive key search attack: 

17 /80 Exhaustive key search attack given a small number of plaintext-ciphertext pairs encrypted under a key K, K can be recovered by exhaustive key search with 2 k-1 processing complexity (expected number of operations) input: (X, Y), (X’, Y’), … progress through the entire key space, and for each candidate key K’, do the following: decrypt Y with K’ if the result is not X, then throw away K’ if the result is X, then check the other pairs (X’, Y’), … if K’ does not work for at least one pair, then throw away K’ and take another key if K’ worked for all pairs (X, Y), (X’, Y’), …, then output K’ as the target key on average, the target key is found after searching half of the key space if the plaintexts are known to contain redundancy, then ciphertext-only exhaustive key search is possible with a relatively small number of ciphertexts  in practice, key size should be at least 128 bits A.2 Encryption Block ciphers

Algebraic attacks: 

18 /80 Algebraic attacks having a large key size is only a necessary condition for the security of a block cipher a block cipher can be broken due to the weaknesses in its internal (algebraic) structure, even if it uses large keys example: naïve exhaustive key search against DES: 2 55 attack using the complementation property of DES: 2 54 Y = DES K (X) implies Y* = DES K* (X*), where X* denotes the bitwise complement of X differential cryptanalysis of DES: 2 47 linear cryptanalysis of DES: 2 43 A.2 Encryption Block ciphers

Block cipher modes of operation: 

19 /80 Block cipher modes of operation ECB – Electronic Codebook used to encipher a single plaintext block (e.g., a DES key) CBC – Cipher Block Chaining repeated use of the encryption algorithm to encipher a message consisting of many blocks CFB – Cipher Feedback used to encipher a stream of characters, dealing with each character as it comes OFB – Output Feedback another method of stream encryption, used on noisy channels CTR – Counter simplified OFB with certain advantages A.2 Encryption Block cipher modes of operation

ECB mode: 

20 /80 ECB mode encrypt decrypt E P 1 C 1 K E P 2 C 2 K E P N C N K … D C 1 P 1 K D C 2 P 2 K D C N P N K … A.2 Encryption Block cipher modes of operation

Properties of the ECB mode: 

21 /80 Properties of the ECB mode identical plaintext blocks result in identical ciphertext blocks (under the same key, of course) messages to be encrypted often have very regular formats repeating fragments, special headers, string of 0s, etc. are quite common blocks are encrypted independently of other blocks reordering ciphertext blocks result in correspondingly reordered plaintext blocks ciphertext blocks can be cut from one message and pasted in another, possibly without detection error propagation: one bit error in a ciphertext block affects only the corresponding plaintext block (results in garbage) overall: not recommended for messages longer than one block, or if keys are reused for more than one block A.2 Encryption Block cipher modes of operation

CBC mode: 

22 /80 CBC mode encrypt decrypt E P 1 C 1 K + E P 2 C 2 K + E P 3 C 3 K + E P N C N K + IV C N-1 … D C 1 P 1 K + IV D C 2 P 2 K + D C 3 P 3 K + D C N P N K + C N-1 A.2 Encryption Block cipher modes of operation

Properties of the CBC mode: 

23 /80 Properties of the CBC mode encrypting the same plaintexts under the same key, but different IVs result in different ciphertexts ciphertext block C j depends on P j and all preceding plaintext blocks rearranging ciphertext blocks affects decryption however, dependency on the preceding plaintext blocks is only via the previous ciphertext block C j-1 proper decryption of a correct ciphertext block needs a correct preceding ciphertext block only error propagation: one bit error in a ciphertext block C j has an effect on the j-th and (j+1)-st plaintext block P j ’ is complete garbage and P j+1 ’ has bit errors where C j had an attacker may cause predictable bit changes in the (j+1)-st plaintext block error recovery: recovers from bit errors (self-synchronizing) cannot, however, recover from frame errors (“lost” bits) A.2 Encryption Block cipher modes of operation

Integrity of the IV in the CBC mode: 

24 /80 Integrity of the IV in the CBC mode the IV need not be secret, but its integrity should be protected malicious modification of the IV allows an attacker to make predictable changes to the first plaintext block recovered one solution is to send the IV in an encrypted form at the beginning of the CBC encrypted message A.2 Encryption Block cipher modes of operation

Padding: 

25 /80 Padding the length of the message may not be a multiple of the block size of the cipher one can add some extra bytes to the short end block until it reaches the correct size – this is called padding usually the last byte indicates the number of padding bytes added – this allows the receiver to remove the padding 05 short end block padding A.2 Encryption Block cipher modes of operation

CFB mode: 

26 /80 CFB mode encrypt decrypt E P i C i K + shift register (n) (n) select s bits (n) (s) (s) (s) (s) initialized with IV E C i P i K + shift register (n) (n) select s bits (n) (s) (s) (s) (s) initialized with IV A.2 Encryption Block cipher modes of operation

Properties of the CFB mode: 

27 /80 Properties of the CFB mode encrypting the same plaintexts under the same key, but different IVs result in different ciphertexts the IV can be sent in clear ciphertext block C j depends on P j and all preceding plaintext blocks rearranging ciphertext blocks affects decryption proper decryption of a correct ciphertext block needs the preceding n/s ciphertext blocks to be correct error propagation: one bit error in a ciphertext block C j has an effect on the decryption of that and the next n/s ciphertext blocks (the error remains in the shift register for n/s steps) P j ’ has bit errors where C j had, all the other erroneous plaintext blocks are garbage an attacker may cause predictable bit changes in the j-th plaintext block error recovery: self synchronizing, but requires n/s blocks to recover A.2 Encryption Block cipher modes of operation

OFB mode: 

28 /80 OFB mode encrypt decrypt E P i C i K + shift register (n) (n) select s bits (n) (s) (s) (s) (s) initialized with IV E C i P i K + shift register (n) (n) select s bits (n) (s) (s) (s) (s) initialized with IV A.2 Encryption Block cipher modes of operation

Properties of the OFB mode: 

29 /80 Properties of the OFB mode a different IV should be used for every new message, otherwise messages will be encrypted with the same key stream the IV can be sent in clear however, if the IV is modified by the attacker, then the cipher will never recover (unlike CFB) ciphertext block C j depends on P j only (does not depend on the preceding plaintext blocks) however, rearranging ciphertext blocks affects decryption error propagation: one bit error in a ciphertext block C j has an effect on the decryption of only that ciphertext block P j ’ has bit errors where C j had an attacker may cause predictable bit changes in the j-th plaintext block error recovery: recovers from bit errors never recovers if bits are lost or the IV is modified A.2 Encryption Block cipher modes of operation

CTR mode: 

30 /80 CTR mode encrypt decrypt E P i C i K + (n) (n) (n) counter + i (n) E C i P i K + (n) (n) (n) counter + i (n) A.2 Encryption Block cipher modes of operation

Properties of the CTR mode: 

31 /80 Properties of the CTR mode similar to OFB cycle length depends on the size of the counter (typically 2 n ) the i-th block can be decrypted independently of the others parallelizable (unlike OFB) random access the values to be XORed with the plaintext can be pre-computed at least as secure as the other modes note1 : in CFB, OFB, and CTR mode only the encryption algorithm is used (decryption is not needed), that is why some ciphers (e.g., AES) is optimized for encryption note2 : the OFB and CTR modes essentially make a synchronous stream cipher out of a block cipher, whereas the CFB mode converts a block cipher into a self-synchronizing stream-cipher A.2 Encryption Block cipher modes of operation

Stream ciphers: 

32 /80 Stream ciphers while block ciphers simultaneously encrypt groups of characters, stream ciphers encrypt individual characters may be better suited for real time applications stream ciphers are usually faster than block ciphers in hardware (but not necessarily in software) limited or no error propagation may be advantageous when transmission errors are probable note : the distinction between stream ciphers and block ciphers is not definitive stream ciphers can be built out of block ciphers using CFB, OFB, or CTR modes a block cipher in ECB or CBC mode can be viewed as a stream cipher that operates on large characters A.2 Encryption Stream ciphers

Synchronous stream ciphers: 

33 /80 Synchronous stream ciphers the key stream is generated independently of the plaintext and of the ciphertext needs synchronization between the sender and the receiver if a character is inserted into or deleted from the ciphertext stream then synchronization is lost and the plaintext cannot be recovered additional techniques must be used to recover from loss of synch. no error propagation a ciphertext character that is modified during transmission affects only the decryption of that character  an attacker can make changes to selected ciphertext characters and know exactly what effect these changes have on the plaintext (if h = XOR) s i g k h f k s i+1 z i p i c i A.2 Encryption Stream ciphers

Self-synchronizing stream ciphers: 

34 /80 Self-synchronizing stream ciphers the key stream is generated as a function of a fixed number of previous ciphertext characters self-synchronizing since the size t of the register is fixed, a lost ciphertext character affects only the decryption of the next t ciphertext characters limited error propagation if a ciphertext character is modified, then decryption of the next t ciphertext characters may be incorrect ciphertext characters depend on all previous plaintext characters better diffusion of plaintext statistics g k h z i p i c i … register A.2 Encryption Stream ciphers

The Vernam cipher and the one-time pad: 

35 /80 The Vernam cipher and the one-time pad Vernam cipher c i = p i Å k i for i = 1, 2, … where p i are the plaintext digits, k i are the key stream digits, c i are the ciphertext digits, and Å is the bitwise XOR operation one-time pad a Vernam cipher where the key stream digits are generated independently and uniformly at random the one-time pad is unconditionally secure [Shannon, 1949] I(P; C) = H(P) - H(P|C) = 0 a necessary condition for a symmetric key cipher to be unconditionally secure is that H(K) ³ H(P) [Shannon, 1949] practically, the key must have as many bits as the compressed plaintext impractical because of key management problems A.2 Encryption Stream ciphers

Asymmetric-key encryption: 

36 /80 Asymmetric-key encryption asymmetric-key encryption it is hard (computationally infeasible) to compute K’ from K K can be made public (public-key cryptography) no need for key setup before communication public-keys are not confidential but they must be authentic ! the security of asymmetric-key encryption schemes is usually based on some well-known or widely believed hard problems E D m plaintext K (public) encryption key K’ (private) decryption key E K (m) ciphertext D K’ (E K (m)) = m attacker A.2 Encryption A.2.2 Asymmetric-key encryption

Examples for hard problems : 

37 /80 Examples for hard problems factoring problem given a positive integer n, find its prime factors true complexity is unknown it is believed that it does not belong to P discrete logarithm problem given a prime p, a generator g of Z p * , and an element y in Z p * , find the integer x, 0 £ x £ p-2, such that g x mod p = y true complexity is unknown it is believed that it does not belong to P Diffie-Hellman problem given a prime p, a generator g of Z p * , and elements g x mod p and g y mod p, find g xy mod p true complexity is unknown it is believed that it does not belong to P A.2 Encryption A.2.2 Asymmetric-key encryption

The RSA encryption scheme: 

38 /80 The RSA encryption scheme key generation select p, q large primes (about 500 bits each) n = pq, f (n) = (p-1)(q-1) select e such that 1 < e < f (n) and gcd(e, f (n)) = 1 compute d such that ed mod f (n) = 1 (this is easy if f (n) is known) the public key is (e, n) the private key is d encryption represent the message as an integer m in [0, n-1] compute c = m e mod n decryption compute m = c d mod n A.2 Encryption A.2.2 Asymmetric-key encryption

Relation to factoring: 

39 /80 Relation to factoring the problem of computing d from (e, n) is computationally equivalent to the problem of factoring n if one can factor n, then one can easily compute d if one can compute d, then one can efficiently factor n the problem of computing m from c and (e, n) (called the RSA problem) is believed to be computationally equivalent to factoring if one can factor n, then one can easily compute m from c and (e, n) there’s no formal proof for the other direction A.2 Encryption A.2.2 Asymmetric-key encryption

The need for salting: 

40 /80 The need for salting let us assume that the adversary observes a ciphertext c = E K (m) let the set of possible plaintexts be M if M is small, then the adversary can try to encrypt every message in M with the publicly known key K until she finds the message m that maps into c the usual way to prevent this attack is to randomize the encryption some random bytes are added to the plaintext message before encryption through the application of the PKCS #1 formatting rules when the message is decrypted, the recipient can recognize and discard these random bytes A.2 Encryption A.2.2 Asymmetric-key encryption

The ElGamal encryption scheme: 

41 /80 The ElGamal encryption scheme key generation generate a large random prime p and choose generator g of the multiplicative group Z p * = {1, 2, …, p-1} select a random integer a, 1 £ a £ p-2, and compute A = g a mod p the public key is (p, g, A) the private key is a encryption represent the message as an integer m in [0, p-1] select a random integer r, 1 £ r £ p-2, and compute R = g r mod p compute C = m × A r mod p the ciphertext is the pair (R, C) decryption compute m = C × R p-1-a mod p proof of decryption C × R p-1-a º m × A r × R p-1-a º m × g ar × g r(p-1-a) º m ×( g p-1 ) r º m (mod p) A.2 Encryption A.2.2 Asymmetric-key encryption

Relation to hard problems: 

42 /80 Relation to hard problems security of the ElGamal scheme is said to be based on the discrete logarithm problem in Z p * , although equivalence has not been proven yet recovering m given p, g, A, R, and C is equivalent to solving the Diffie-Hellman problem A.2 Encryption A.2.2 Asymmetric-key encryption

Digital enveloping: 

43 /80 Digital enveloping plaintext message symmetric-key cipher (e.g., in CBC mode) public key of the receiver asymmetric-key cipher digital envelop generate random symmetric key bulk encryption key most popular public-key encryption methods are several orders of magnitude slower than the best known symmetric key schemes  public-key encryption is used together with symmetric-key encryption; the technique is called digital enveloping A.2 Encryption A.2.2 Asymmetric-key encryption

Chapter outline: 

44 /80 Chapter outline A.1 Introduction A.2 Encryption A.3 Hash functions A.4 Message authentication codes A.5 Digital signatures A.6 Session key establishment protocols A.7 Pseudo-random number generators A.8 Advanced authentication techniques

Hash functions: 

45 /80 Hash functions a hash function maps bit strings of arbitrary finite length to bit strings of fixed length (n bits) many-to-one mapping  collisions are unavoidable however, finding collisions are difficult  the hash value of a message can serve as a compact representative image of the message (similar to fingerprints) message of arbitrary length fix length hash value / message digest / fingerprint hash function A.3 Hash functions

Desirable properties of hash functions: 

46 /80 Desirable properties of hash functions ease of computation given an input x, the hash value h(x) of x is easy to compute weak collision resistance (2 nd 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 s.t. h(x) = y A.3 Hash functions

The Birthday Paradox: 

47 /80 The Birthday Paradox Given a set of N elements, from which we draw k elements randomly (with replacement). What is the probability of encountering at least one repeating element? first, compute the probability of no repetition: the first element x 1 can be anything when choosing the second element x 2 , the probability of x 2 ¹ x 1 is 1-1/N when choosing x 3 , the probability of x 3 ¹ x 2 and x 3 ¹ x 1 is 1-2/N … when choosing the k-th element, the probability of no repetition is 1-(k-1)/N the probability of no repetition is (1 - 1/N)(1 - 2/N)…(1 – (k-1)/N) when x is small, (1-x) » e -x (1 - 1/N)(1 - 2/N)…(1 – (k-1)/N) = e -1/N e -2/N … e -(k-1)/N = e -k(k-1)/2N the probability of at least one repetition after k drawing is 1 – e -k(k-1)/2N A.3 Hash functions

The Birthday Paradox (cont’d): 

48 /80 The Birthday Paradox (cont’d) How many drawings do you need, if you want the probability of at least one repetition to be e ? solve the following for k: e = 1 – e -k(k-1)/2N k(k-1) = 2N ln(1/1- e ) k » sqrt(2N ln(1/1- e )) examples: e = ½  k » 1.177 sqrt(N) e = ¾  k » 1.665 sqrt(N) e = 0.9  k » 2.146 sqrt(N) origin of the name “Birthday Paradox”: elements are dates in a year (N = 365) among 1.177 sqrt(365) » 23 randomly selected people, there will be at least two that have the same birthday with probability ½ A.3 Hash functions

Choosing the output size of a hash function: 

49 /80 Choosing the output size of a hash function the Birthday Paradox have a profound impact on the design of hash functions (and other cryptographic algorithms and protocols)! let n be the output size of a hash function among ~sqrt(2 n ) = 2 n/2 randomly chosen messages, with high probability, there will be a collision pair it is easier to find collisions than to find preimages or 2 nd preimages for a given hash value  in order to resist birthday attacks, 2 n/2 should be sufficiently large (e.g., n = 160 bits) A.3 Hash functions

Iterated hash functions: 

50 /80 Iterated hash functions input is divided into fixed length blocks x 1 , x 2 , …, x L last block is padded if necessary Merkle-Damgard strengthening: padding contains the length of the message each input block is processed according to the following scheme f is called the compression function can be based on a block cipher, or can be a dedicated compression function x 1 CV 0 (b) (n) (n) CV 1 f x 2 (b) (n) CV 2 f x 3 (b) (n) CV 3 f x L (b) (n) h(x) = CV L f CV L-1 … A.3 Hash functions

Chapter outline: 

51 /80 Chapter outline A.1 Introduction A.2 Encryption A.3 Hash functions A.4 Message authentication codes A.5 Digital signatures A.6 Session key establishment protocols A.7 Pseudo-random number generators A.8 Advanced authentication techniques

Message authentication codes (MACs): 

52 /80 Message authentication codes (MACs) MAC functions can be viewed as hash functions with two functionally distinct inputs: a message and a secret key they produce a fixed size output (say n bits) called the MAC practically it should be infeasible to produce a correct MAC for a message without the knowledge of the secret key MAC functions can be used to implement data integrity and message origin authentication services message of arbitrary length fix length MAC MAC function secret key A.4 Message authentication codes

MAC generation and verification: 

53 /80 MAC generation and verification MAC message MAC generation secret key MAC message MAC verification secret key compare yes/no A.4 Message authentication codes

Desirable properties of MAC functions: 

54 /80 Desirable properties of MAC functions ease of computation given an input x and a secret key k, it is easy to compute MAC k (x) key non-recovery it is computationally infeasible to recover the secret key k, given one or more text-MAC pairs (x i , MAC k (x i )) for that k computation resistance given zero or more text-MAC pairs (x i , MAC k (x i )), it is computationally infeasible to find a text-MAC pair (x, MAC k (x)) for any new input x ¹ x i computation resistance implies key non-recovery but the reverse is not true in general A.4 Message authentication codes

CBC MAC: 

55 /80 CBC MAC CBC MAC is secure for messages of a fixed number of blocks (adaptive chosen-text existential) forgery is possible if variable length messages are allowed  it is recommended to involve the length of the message in the CBC MAC computation E x 1 k + E x 2 k + E x 3 k + E x N c N k + 0 c N-1 … c 1 c 2 c 3 E -1 E k’ k MAC optional A.4 Message authentication codes

HMAC: 

56 /80 HMAC k + Å ipad CV 0 f x 1 f x L |padding 1 f k + Å opad CV 0 f M|padding 2 f M CV 1 inner CV 1 outer HMAC k (x) … hash fn hash fn HMAC k (X) = H( k’’|H( k’|X )) A.4 Message authentication codes

Chapter outline: 

57 /80 Chapter outline A.1 Introduction A.2 Encryption A.3 Hash functions A.4 Message authentication codes A.5 Digital signatures A.6 Session key establishment protocols A.7 Pseudo-random number generators A.8 Advanced authentication techniques

Digital signatures: 

58 /80 Digital signatures similar to MACs but unforgeable by the receiver verifiable by a third party used for message authentication and non-repudiation (of message origin) based on public-key cryptography private key defines a signing transformation S A S A (m) = s public key defines a verification transformation V A V A (m, s ) = true if S A (m) = s V A (m, s ) = false otherwise A.5 Digital signatures

Attacks on digital signature schemes: 

59 /80 Attacks on digital signature schemes key-only attack only the public key is available to the adversary known-message attack the adversary has signatures for a set of messages known to her but not chosen by her chosen-message attack the adversary obtains signatures for messages chosen by her before attempting to break the signature scheme adaptive chosen-message attack the adversary is allowed to use the signer as an oracle she may request signatures for messages which depend on previously obtained signatures A.5 Digital signatures

“Hash-and-sign” paradigm: 

60 /80 “Hash-and-sign” paradigm public/private key operations are slow hash the message first and apply public/private key operations to the hash value only h enc private key of sender message hash signature h message hash dec public key of sender signature compare yes/no generation verification A.5 Digital signatures

Examples of digital signature scheme: 

61 /80 Examples of digital signature scheme RSA essentially identical to the RSA encryption scheme signature = decryption with private key typical signature length is 1024 bits DSA (Digital Signature Algorithm) based on the ElGamal signature scheme typical signature length is 1024 bits ECDSA (Elliptic Curve DSA) same as DSA but works over elliptic curves reduced signature length (typically 320 bits) A.5 Digital signatures

Chapter outline: 

62 /80 Chapter outline A.1 Introduction A.2 Encryption A.3 Hash functions A.4 Message authentication codes A.5 Digital signatures A.6 Session key establishment protocols A.7 Pseudo-random number generators A.8 Advanced authentication techniques

Session key establishment protocols: 

63 /80 Session key establishment protocols goal of session key establishment protocols to setup a shared secret between two (or more) parties it is desired that the secret established by a fixed pair of parties varies on subsequent executions of the protocol (dynamicity) established shared secret is used as a session key to protect communication between the parties motivation for use of session keys to limit available ciphertext for cryptanalysis to limit exposure caused by the compromise of a session key to avoid long-term storage of a large number of secret keys (keys are created on-demand when actually required) to create independence across communication sessions or applications A.6 Session key establishment protocols

Basic classification: 

64 /80 Basic classification key transport protocols one party creates or otherwise obtains a secret value, and securely transfers it to the other party key agreement protocols a shared secret is derived by the parties as a function of information contributed by each, such that no party can predetermine the resulting value A.6 Session key establishment protocols

Further services : 

65 /80 Further services entity authentication implicit key authentication one party is assured that no other party aside from a specifically identified second party (and possibly some trusted third parties) may gain access to the established session key key confirmation one party is assured that a second (possibly unidentified) party actually possesses the session key possession of a key can be demonstrated by producing a one-way hash value of the key or encryption of known data with the key explicit key authentication implicit key authentication + key confirmation key freshness one party is assured that the key is new (never used before) A.6 Session key establishment protocols

Further protocol characteristics: 

66 /80 Further protocol characteristics reciprocity guarantees are provided unilaterally guarantees are provided mutually efficiency number of message exchanges (passes) required total number of bits transmitted (i.e., bandwidth used) complexity of computations by each party possibility of precomputations to reduce on-line computational complexity third party requirements on-line, off-line, or no third party at all degree and type of trust required in the third party system setup distribution of initial keying material A.6 Session key establishment protocols

The Wide-Mouth-Frog protocol: 

67 /80 The Wide-Mouth-Frog protocol Alice Bob Server generate k A, E Kas ( B, k, T a ) E Kbs ( A, k, T s ) summary: a simple key transport protocol that uses a trusted third party Alice generates the session key and sends it to Bob via the trusted third party characteristics: implicit key authentication for Alice explicit key authentication for Bob key freshness for Bob with timestamps (flawed) unilateral entity authentication of Alice on-line third party (Server) trusted for secure relaying of keys and verification of freshness, in addition A is trusted for generating good keys initial long-term keys between the parties and the server are required A.6 Session key establishment protocols

A flaw in the Wide-Mouth-Frog protocol: 

68 /80 A flaw in the Wide-Mouth-Frog protocol summary: after observing one run of the protocol, Trudy can continuously use the Server as an oracle until she wants to bring about re-authentication between Alice and Bob B, E K bs ( A, k, T s ) E K as ( B, k, T s (1) ) A, E K as ( B, k, T s (1) ) E K bs ( A, k, T s (2) ) ... E K bs ( A, k, T s (n) ) Bob Trudy Server A.6 Session key establishment protocols

Signed encrypted keys: 

69 /80 Signed encrypted keys Bob Alice A, E Kb (k), T a , S Ka (B,E Kb (k),T a ) generate k summary: Alice generates a session key, encrypts it with Bob’s public key, then sings it, and sends it to Bob characteristics: unilateral entity authentication (of Alice), mutual implicit key authentication, no key confirmation, key freshness with timestamp, clock synchronization, off-line third party for issuing public key certificates may be required, initial exchange of public keys between the parties may be required, Alice is trusted to generate keys, non-repudiation guarantee for Bob A.6 Session key establishment protocols

The Diffie-Hellman protocol: 

70 /80 The Diffie-Hellman protocol Bob Alice select random x compute g x mod p select random y compute g y mod p g x mod p g y mod p compute k = (g y ) x mod p compute k = (g x ) y mod p summary: a key agreement protocol based on one-way functions; in particular, security of the protocol is based on the hardness of the discrete logarithm problem and that of the Diffie-Hellman problem characteristics: NO AUTHENTICATION, key freshness with randomly selected exponents, no party can control the key, no need for a trusted third party assumptions: p is a large prime, g is a generator of Z p * , both are publicly known system parameters A.6 Session key establishment protocols

Chapter outline: 

71 /80 Chapter outline A.1 Introduction A.2 Encryption A.3 Hash functions A.4 Message authentication codes A.5 Digital signatures A.6 Session key establishment protocols A.7 Pseudo-random number generators A.8 Advanced authentication techniques

Pseudo-random number generators (PRNGs): 

72 /80 Pseudo-random number generators (PRNGs) a random number is a number that cannot be predicted by an observer before it is generated if the number is generated within the range [0, N-1], then its value cannot be predicted with any better probability than 1/N the above is true even if the observer is given all previously generated numbers a cryptographic pseudo-random number generator (PRNG) is a mechanism that processes somewhat unpredictable inputs and generates pseudo-random outputs if designed, implemented, and used properly, then even an adversary with enormous computational power should not be able to distinguish the PRNG output from a real random sequence A.7 Pseudo-random number generators

General operation of PRNGs: 

73 /80 General operation of PRNGs A.7 Pseudo-random number generators internal state unpredictable input samples (from physical processes) pseudo-random bits indistinguishable from real random bits … one-way fn entropy pool re-keying state update

Desirable properties of PRNGs: 

74 /80 Desirable properties of PRNGs the adversary cannot compute the internal state of the PRNG, even if she has observed many outputs of the PRNG the adversary cannot compute the next output of the PRNG, even if she has observed many previous outputs of the PRNG if the adversary can observe or even manipulate the input samples that are fed in the PRNG, but she does not know the internal state of the PRNG, then the adversary cannot compute the next output and the next internal state of the PRNG if the adversary has somehow learned the internal state of the PRNG, but she cannot observe the input samples that are fed in the PRNG, then the adversary cannot figure out the internal state of the PRNG after the re-keying operation A.7 Pseudo-random number generators

Chapter outline: 

75 /80 Chapter outline A.1 Introduction A.2 Encryption A.3 Hash functions A.4 Message authentication codes A.5 Digital signatures A.6 Session key establishment protocols A.7 Pseudo-random number generators A.8 Advanced authentication techniques

Hash chains: 

76 /80 Hash chains a hash chain is a sequence of hash values that are computed by iteratively calling a one-way hash function on an initial value v 0 properties: given v i , it is easy to compute any v j for j > i (v j = h (j-i) (v i )) but it is difficult to compute v k for k < i (one-way property of h) hash chains can be used for repeated authentications at the cost of a single digital signature Alice computes a hash chain and commits to it by signing v n and distributing it to potential verifiers later on, Alice can authenticate herself repeatedly (at most n times) by revealing the elements of the hash chain in reverse order when v n-i is revealed, verifiers can check if h (i) (v n-i ) = v n (or h(v n-i ) = v n-i+1 if they remember the last revealed element) each hash chain element can be used only once for authenticating Alice verifiers are assured that only Alice could have released the next hash chain element hash chains can be stored efficiently with a storage complexity that is logarithmic in the length of the hash chain A.8 Advanced authentication techniques v 0 v 1 v 2 v 3 v n-1 v n h h h h h …

Merkle-trees: 

77 /80 Merkle-trees the limitation of hash chains is that elements can only be revealed sequentially Merkle-trees overcome this problem by allowing for the pre-authentication of a set of values with a single digital signature (on the root u 0 of the tree) and for the revelation of those values in any order when revealing a value v i , Alice must also reveal all the values assigned to the sibling vertices on the path from v i ’ to the root (e.g., v 3 is revealed together with v 4 ’, u 12 , u 5678 ) verifiers hash the revealed values appropriately and check if the result is u 0 A.8 Advanced authentication techniques

TESLA: 

78 /80 TESLA a broadcast authentication mechanism based on symmetric key cryptographic primitives main idea: asymmetry through delayed disclosure of authentication keys Alice wants to broadcast a message m Alice computes a MAC on m with a key unknown to the verifiers verifiers receive message m with the MAC, but they cannot immediately verify authenticity later, Alice discloses the key used to compute the MAC verifiers can now verify the MAC; if it is correct, they know that the message was sent by Alice, because at the time of reception nobody else knew the key assumptions: loose time synchronization between the participants each party knows an upper bound on the maximum synchronization error initial secret between the parties to bootstrap the whole mechanism A.8 Advanced authentication techniques

TESLA (cont’d): 

79 /80 TESLA (cont’d) MAC keys are consecutive elements in a one-way key chain: K 0  K 1  …  K n K i = h(K i-1 ) protocol operation: setup: Alice sends K n to each verifier in an authentic manner time is divided into epochs each message sent in epoch i is authenticated with key K n-i K n-i is disclosed in epoch i+d, where d is a system parameter K n-i is verified by checking h(K n-i ) = K n-i+1 example: K n-1 K n-2 K n-3 K n-4 P 1 P 2 P 3 P 4 P 5 P 6 P 7 time K n-1 K n-2 K n-3 key disclosure schedule K n A.8 Advanced authentication techniques

Conclusions: 

80 /80 Conclusions security services are implemented by using security mechanisms many security mechanisms are based on cryptography (e.g., encryption, digital signature, message authentication codes, …) but be cautious: “If you think cryptography is going to solve your problem, you don't understand cryptography and you don't understand your problem.” -- Roger Needham other important aspects are physical protection procedural rules education