DSHS Information Technology Security Awareness Training for Contractors
DSHS offers an annual IT Security Awareness Training course for employees and contractors to understand the importance of safeguarding information. The training emphasizes individual responsibility in protecting DSHS information to comply with state and federal laws. Through interactive lessons and quizzes, participants learn about security responsibilities and potential consequences of unauthorized disclosure. Take the course to enhance your security knowledge and contribute to a secure work environment at DSHS.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CIS 5371 Cryptography 3b. Pseudorandomness Based on: Jonathan Katz and Yehuda Lindell Introduction to Modern Cryptography 1
Pseudorandomness An introduction A distribution D is pseudorandom if no PPT distinguisher can detect if it a string sampled according to D or chosen uniformly at random. This is formalized by requiring that every PPT algorithm outputs 1 with almost the same probability when given a truly random string as when given a pseudorandom string. 2
Pseudorandomness An introduction A pseudorandom generator is a deterministic algorithm that given a short truly random seed of length nwill stretch it to into a longer string of length ?(?) that is pseudorandom. 3
Existence of pseudorandom generators We cannot prove that pseudorandom generators exist! We believe that such generators can be constructed from one-way functions. There are some long-standing problems that have no efficient solution and it is believed that they are unsolvable in polynomial time. 4
Pseudorandom generators informal definition A distribution D is pseudorandom if no PPT distinguisher can detect if it is given a string sampled according to D or a string chosen uniformly at random. This can be formalized by requiring that a PPT distinguisher D outputs 1 with almost the same probability when given a truly random string and when given a pseudorandom string. 5
Pseudorandom generator Definition Let ?( ) be a polynomial and ? a deterministic polynomial-time algorithm that for any ? and any input ? ? {0,1}?will output string of length ?(?). ? is a pseudorandom generator if: ? ? > ? PPT algorithm (distinguisher) ?, ? negl function with: |Pr ? ? = 1 Pr ? ? ? = 1 negl(n) where ? is uniform random string of length ? ? ,? ?? is uniform random of length ? and the probabilities are taken over the coins used by ? and the choices of ?,?. 6
Stream Ciphers A stream cipher is a deterministic algorithm (Init, GetBits) where, Init takes as input a seed ? and an optional initialization vector ?? and outputs a state ??0. GetBits takes as input ???and outputs a bit ? and state ???+1. 7
Algorithm 3.16 Construct ?? from (Init, GetBits) Input: Seed ? and optional ??. Output: ?1, ,?? ??0 Init(?,??) for? = 1 to ?: ??,??? GetBits ??? 1 return?1, ,??. This can easily be modified to get a variable output pseudorandom generator ? = ? ?,1?. 8
Discussion We use the term stream cipher forthe PR stream generator, not the encryption algorithm. There are a number of practical constructions of stream ciphers that are extraordinarily fast, such as the stream cipher RC4. 9
Discussion The WEP encryption protocol for 802.11 used RC4 and was broken. But since then it is fixed---and the standard updated. If RC4 has to be used the first 1024 bits or so should be discarded. 10
Discussion From a security point of view it is advocated to use block cipher constructions for constructing secure encryption schemes. This disadvantage is that this approach is less efficient when compared to using a dedicated stream cipher. 11
A secure fixed length encryption scheme ? ???????????? ????????? ??? ??? ??? ?????? ????????? 12
Secure fixed length encryption Protocol Let ? be a pseudorandom generator with expansion factor ?. Define a private-key encryption scheme for messages of length ? as follows Gen: on input 1? choose ? {0,1}? uniformly at random and output ? as key. Enc: on input a key ? {0,1}? and a message ? {0,1}?(?) output the ciphertext ? G ? ? . Dec: on input a key ? {0,1}? and a ciphertext c {0,1}?(?) output the plaintext ? G ? ? . 13
Secure fixed length encryption Theorem If G be a pseudorandom generator then protocol is a fixed-length private-key encryption scheme that has indistinguishable encryptions in the presence of an eavesdropper. 14
A secure fixed length encryption reduction: is secure if G is a pseudorandom generator Adversary A (Distinguisher D) Adversary A (Protocol ) 1? 1?,? is?random or pseudorandom? ?0,?1 Suppose that A succeeds with probability ?(?) choose a random bit ? compute??:=w ?? ?? 1 if ? = ? 0 if ? ? ? Distinguish Break 15
A secure fixed length encryption Proof when ? is uniform random we have 1 2. eav(?) = 1 = Pr ? ? = 1 = Pr PrivKA, when ? = ?(?) we have eav(?) = 1] Since ? is a pseudorandom generator | Pr ? ? = 1 - Pr ? ? ? Therefore |1 2 Pr[PrivKA, Pr ? ? ? = 1 = Pr[PrivKA, = 1 | negl(?) eav(?) = 1]| negl(?), or 1 2 + negl(?) |Pr[PrivKA, eav(?) = 1]| 16
Multi-message eavesdropping experiment PrivKA, mult(?) The adversary ? is given input 1? and outputs a pair of vectors of messages ?0 wit |?0 2. A key ? is generated runnng ??? 1?and a random bit ? 0,1 is chosen.For all ? the ciphertext ?? is computed and the vector of ciphertexts ?? is given to ?. 3. .? outputs a bit ? . 4. The output of the experiment i? 1 if ? = ? and 0 otherwise. 1. ? and ?1 ? 1, ,?0 1, ,?1 ?= |?1 ? for all ?. ? En???? 1, ,?? ? ? 17
Multiple encryptions security Definition A private-key encryption scheme =(Gen,Enc,Dec) that has indistinguishable multiple encryptions in the presence of an eavesdropper satisfies: PPT Adversary ?, a negligible function negl: 1 2+ negl ? , Pr[PrivKmult(?, ) ? = 1] where the probability is taken over the random coins of ?, and the experiment. 18
Indistinguishable single encryptions vs indistinguishable multiple encryptions The secure fixed length encryption Protocol presented earlier is deterministic and cannot be used as a construction for indistinguishable multiple encryptions. To see why use the experiment PrivKmult for the pair of vector messages (0?,0?) and 0?,1?. There is a private-key single encryption scheme that has indistinguishable single encryptions but distinguishable multiple encryptions. 19
Secure multiple encryptions using a stream-cipher mode of operation Synchronized mode Communicating parties use a different part of the stream cipher output to encrypt a message. ????? ? ?,1|?| ? Useful for parties communicating in the same session. Communicating parties must maintain state between encryptions. 20
Secure multiple encryptions stream-cipher mode of operation Unsynchronized mode Encryptions are carried out independently of one another. Communicating parties are not required to maintain state between encryptions. ????? ??,? ?,??,1|?| ? where the initial vector ?? {0,1}? is chosen at random. 21
Security against Chosen-Plaintext Attacks (CPA) We now consider a more powerful adversary that is active. The adversary can ask for the encryptions of some specific plaintext messages, as well as eavesdrop. 22
The CPA indistinguishability experiment PrivKA, cpa(?) A key ? is generated runnng Gen 1?. 1. The adversary ? is given input 1? and oracle access to En?? , and outputs a pair of messages ?0,?1 of equal length. 2. 3. A uniform bit ? ? 0,1 is chosen and a ciphertext c En???? is computed and given to ?. 4. Adversary ? continues to have oracle access to En?? ,and outputs a bit ? . 5. The output of the experiment i? 1 if ? = ? and 0 otherwise. 23
Indistinguishable encryptions under CPA Definition A private-key encryption scheme = Gen,Enc,Dec has indistinguishable encryptions under CPA if PPT adversaries ?, a negl function such that, 1 2 + negl ? , cpa(?) = 1] Pr[PrivKA, where the probability is taken over the coins of A and those of the experiment. 24
CPA security for multiple encryptions As for single encryption, extend the experiment to PrivKA, pair of vectors of plaintext. cpa(?) in which the adversary outputs a Any private-key encryption scheme that has indistinguishable encryptions under CPA also has indistinguishable multiple encryptions under CPA. 25
APPENDIX, RC4 Designed in 1987 by Ron Rivest for RSA Security Variable key size stream cipher with byte-oriented operations Based on the use of a random permutation Eight to sixteen machine operations are required per output byte and the cipher can be expected to run very quickly in software Used in the Secure Sockets Layer/Transport Layer Security (SSL/TLS) standards for communication between Web browsers and servers Used in the Wired Equivalent Privacy (WEP) protocol and the newer WiFi Protected Access (WPA) protocol (IEEE 802.11 wireless LAN standard) 26
RC4 Generates a pseudorandom stream (keystream) that can be used for encryption by XOR-ing it with the plaintext. The internal state of the cipher has two parts: a permutation of 256 bytes (S) two 8-bit pointers: i, j RC4: byte K is output 27
RC4, protocol (KSA) Key scheduling algorithm (KSA) (initialize S, using key, 1 keylength 256) for i from 0 to 255 (S is initialized) S[i] := i endfor j := 0 for i from 0 to 255 (initial permutation is performed) j := (j + S[i] + key[i mod keylength]) mod 256 swap values of S[i] and S[j] endfor 28
RC4, protocol (PRGA) Pseudo-random generation algorithm i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile 29
Simple RC4 example Instead of the full 256 bytes, use 8 3-bits. Assume we use a 4 x 3-bit key: K = [1 2 3 6] Initialization of S: S = [0 1 2 3 4 5 6 7] Initial permutation: j := 0 for i from 0 to 7 j := (j + S[i] + key[i mod 3) mod 8 swap values of S[i] and S[j] endfor 30
Simple RC4 example K = [1 2 3 6], S = [0 1 2 3 4 5 6 7] We go through for each iteration of i: For i = 0: j = (0 + 0 + 1) mod 8 = 1 Swap(S[0],S[1]); S = [1 0 2 3 4 5 6 7] For i = 1: j = (1+0+2) mod 8 = 3 Swap(S[1],S[3]) S = [1 3 2 0 4 5 6 7]; 31
Simple RC4 example K = [1 2 3 6], S = [1 3 2 0 4 5 6 7] For i = 2: j = (3+2+3) mod 8 = 0 Swap(S[2],S[0]); S = [2 3 1 0 4 5 6 7] For i = 3: j = (0+0+6) mod 8 = 6 Swap(S[3],S[6]) S = [2 3 1 6 4 5 0 7]; 32
Simple RC4 example K = [1 2 3 6], S = [2 3 1 6 4 5 0 7] For i = 4: j = (6+4+1) mod 8 = 3 Swap(S[4],S[3]); S = [2 3 1 4 6 5 0 7] For i = 5: j = (3+5+2) mod 8 = 2 Swap(S[5],S[2]) S = [2 3 5 4 6 1 7]; 33
Simple RC4 example K = [1 2 3 6], S = [2 3 5 4 6 1 0 7] For i = 6: j = (2+0+3) mod 8 = 5 Swap(S[6],S[5]); S = [2 3 5 4 6 0 1 7] For i = 7: j = (5+7+6) mod 8 = 2 Swap(S[7],S[2]) S = [2 3 7 4 6 0 1 5]; 34
RC4, protocol (PRGA) Now we run PRGA for S = [2 3 7 4 6 0 1 5], i = 0, j = 0 while GeneratingOutput: i := (i + 1) mod 8 j := (j + S[i]) mod 8 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 8] output K endwhile 35
RC4, generating output First iteration S = [2 3 7 4 6 0 1 5], i=0, j=0 i := (0 + 1) mod 8 = 1 j := (0 + S[1]) mod 8 = 3 swap values of S[1] and S[3]: S = [2 4 7 3 6 0 1 5] K := S[(S[1] + S[3]) mod 8] = S[7] = 5 output K = 5 36
RC4, generating output 2nd iteration, S = [2 4 7 3 6 0 1 5], i=1, j=3 i := (1 + 1) mod 8 = 2 j := (3 + S[2]) mod 8 = 2 swap values of S[2] and S[2]: S = [2 4 7 3 6 0 1 5] K := S[(S[2] + S[2]) mod 8] = S[6] = 1 output K = 1 3nd iteration, S = [2 4 7 3 6 0 1 5], i=2, j=2 i := (2 + 1) mod 8 = 3 j := (2 + S[3]) mod 8 = 5 swap values of S[3] and S[5]: S = [2 4 7 0 6 3 1 5] K := S[(S[3] + S[5]) mod 8] = S[3] = 0 output K = 0 37
