Cryptography-Problem Set 1

Problem 1
When a user i uses a password K in some cryptographic protocol, system flows will
usually reveal a pair (X, Y) where Y = F(K, X, i). Here F is some known, fixed function
associated to the protocol. Consider a user i's password to be cracked if an adversary,
given (X, Y), can find some key K for which Y = F(K, X, i).
Attacker Ned has built a large password-cracking machine. Ned used a budget of $100
million for this project, spending half the money on custom chips (ASICs) that, given
(X, Y, i), test, for a candidate K, if Y = F(K, X, i). (The other half of Ned's budget was
used for circuit boards, assembly, power, and cooling). The ASICs cost Ned $10 each
and, for some particular F, each chip can test 109 different passwords per second.
(a) Hal, Leo, and Pat have passwords that are reasonably modelled as uniformly
random strings of 8, 12, and 16 characters, respectively, each character being a
lowercase letter (a-z). Attacker Ned gets hold of an (X, Y) pair for each user i.
How long will it take Ned to crack each user's password?

(b) A system administrator comes in and demands that users select passwords that
include one uppercase letter (A-Z), one lowercase letter (a-z), and one digit
(0-9). Hal, Leo, and Pat change their passwords so that they are now well modelled as having one uppercase letter, one digit, and the rest lowercase letters
(same lengths as before). How effective was this change in stopping Ned? (Recompute the attack times.)

(c) A cryptographer comes in and redesigns the function F such that $10 ASICs will
now need 100 msec to compute it. Hal, Leo, and Pat use their original passwords.
How effective is this change in stopping Ned? (Recompute the attack times.)

(d) Another cryptographers comes in and modifies the design so that, for every user,
the key K wonâA˘ Zt be a password but a 128-bit random string. How effective is ´
this change in stopping Ned? (Recompute the attack time.)

PROBLEM 2
Alice has a pretty penny. Unfortunately, it may not be “fair” penny: it might, when
flipped, land heads with some probability p 6= 0.5. Alice wants to generate a uniform
random bit b: the bit should be 1 with probability 0.5 and zero with probability 0.5.
Describe a strategy Alice can use to achieve this result using her possibly-biased coin.

PROBLEM 3
Alice and Bob have an infinite pile of pennies. They take turns placing their pennies on
a perfectly round table, beginning with Alice. A penny may be placed anywhere on the
table so long as all of the penny fits fully on top of the table and no part of the penny
is on top of any other penny. Pennies must be placed flat on their heads or tails side. A
party loses if he has nowhere to put his penny. Show that Alice can always win