(a) Describe the underlying sample space S . Ans : Let a represent the correct m -bit pattern. Then S = { ( x 1 ,..., x n , a ) } (3) where x i 6 = a , i = 1 ,...,n , and n = 0 , 1 ,..., 2 m . The m -bit pattern x i is the i -th pattern tried by the hacker. So assuming he keeps track of the patterns tried, we also have that x i not equal to xj i.e i not equal to j ( b) Show the mapping from S to S X . Ans : The mapping is X (( x 1 ,..., x n , a )) = n + 1 , with S X = { 1 , 2 ,..., 2 m } (c) Find the PMF of X . Ans : For convenience, let A k = “ k -th attempt is correct”. Then p X ( n ) = P " A n n - 1 \ i =1 A c i # . It should be clear that p X (1) = P [ A 1 ] = 2 - m , since there are 2 m possible passwords, and the hacker tries them randomly. We also have p X (2) = P [ A 2 | A c 1 ] P [ A c 1 ] (4) = 1 2 m - 1 2 m - 1 2 m (5) = 1 = 2 m Similarly, p X (3) = P [ A 3 | A c 2 A c 1 ] P [ A c 2 | A c 1 ] P [ A c 1 ] (7) = 1 2 m - 2 2 m - 2 2 m - 1 2 m - 1 2 m (8) = 1 2 m . (9) Proceeding in this way, we quickly see that X is in fact uniformly distributed in S X = { 1 , 2 ,..., 2 m } . The average number of attempts needed to break an m -bit password is thus 2 m - 1 . For a typical password of ten 8-bit ASCII characters, i.e. 80 bits, it will take 2 79 = 6 . 04 × 10 23 attempts on average
