Problem 2 Password Counts (20 marks plus 5 bonus marks)

In each question below, provide a brief explanation, a formula and the (exact or approximate) numerical value for your answer. There are 94 printable characters on a standard North American keyboard, comprised of the 26 upper case letters A-Z, the 26 lower case letters a-z, the 10 numerical digits 0-9 and the 32 special characters ".,;:!?~@#$%^&*_-+=(){}[]<>\/|. Passwords are strings consisting of printable characters.

(a) (2 marks) What is the total number of passwords of length 8?

(b) (4 marks) Suppose a user has a password of length 8 whose first four characters are the first four letters of their childs name (all in either lower or upper case) and the second four characters are the childs birthday in the format DDMM. Intelligence gathering on your part reveals that the childs first name starts with L and that the child was born in 2008. Making no further assumption about a reasonable first name (e.g., for all you know, the kids name could be Lxqscdx), what is the minimal number of candidates that our lazy user could potentially be using as their password?

(c) (5 marks) To guard against dictionary attacks (where a password cracker checks if a password is a common word or phrase), passwords are typically required to contain at least one numerical digit and at least one special character. What is the total number of passwords of length 8 that satisfy this requirement? (Hint: It is easier to characterize the number of passwords that violate this rule and subtract that count from the total number of 8-character passwords. But be carefully that you dont subtract some passwords twice.)

(d) (2 marks) What is the percentage of 8-character passwords that satisfy the rule of part (c)?

(e) (Bonus Question, 5 marks) A more stringent complexity rule requires passwords to contain at least one upper case letter, at least one numerical digit and at least one special character. What is the total number of passwords of length 8 that satisfy this rule?

(f) (3 marks) Assuming that each permissable character in a password is chosen equally likely² , what is the entropy of the password space of

part (a)?

part (c)?

(g) (4 marks) Suppose we want a password space with entropy 128, assuming that keys are chosen equally likely, i.e. a total of 2¹²⁸ passwords (this number is typical for key space sizes of modern cryptosystems). Assuming no restrictions on the characters appearing in passwords (i.e. the scenario of part (a)), what is the minimum password length that guarantees a password space with entropy 128?

²This assumption may be appropriate for passwords chosen by computer systems with good random number generators, but it is utterly false for passwords chosen by humans. So in practice, the minimum password length computed in part (g) is a significant underestimate.