Problem Set 1 cryptographic protocol

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?
$50 million spent on ASIC chips →
$50 · 106
$10 = 5·106
chips
(5·106
chips)(1·109
passwords
second ) = 5·1015 passwords
sec
Hal's password is 8 characters:
lowercase (a-z) = 26 possibilities for each character
→ 268 password possibilities
1
268
5 · 1015 = .000041765 seconds
Lee's password is 12 characters:
lowercase (a-z) = 26 possibilities for each character
→ 2612 password possibilities
2612
5 · 1015 = 19.085791332 seconds
Pat's password is 16 characters:
lowercase (a-z) = 26 possibilities for each character
→ 2616 password possibilities
2616
5 · 1015 = 8.72 · 106
seconds
(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.)
Hal's password:
Uppercase (A-Z): 26 possibilities · 8 locations
Digit (0-9): 10 possibilities · 7 locations
Lowercase (a-z): 266 possibilities · 6! arrangements
(26 · 8) · (10 · 7) · (266
· 6!)
5 · 1015 = 2.22 · 1011 passwords
2.22 · 1011
5 · 1015 = 4.44 · 10−5
seconds
Lee's password:
2
Uppercase (A-Z): 26 possibilities · 12 locations
Digit (0-9): 10 possibilities · 11 locations
Lowercase (a-z): 2610 possibilities · 10! arrangements
(26 · 12) · (10 · 11) · (2610
· 10!)
5 · 1015 = 5.12 · 1020 passwords
5.12 · 1020
5 · 1015 = 102453.4313 seconds
Pat's password:
Uppercase (A-Z): 26 possibilities · 16 locations
Digit (0-9): 10 possibilities · 15 locations
Lowercase (a-z): 2614 possibilities · 14! arrangements
(26 · 16) · (10 · 15) · (2614
· 14!)
5 · 1015 = 5.62 · 1030 passwords
5.62 · 1030
5 · 1015 = 1.1215 seconds
These changes were more effective in stopping Neds as seen by the increase in
times to crack the passwords. For the passwords of shorter lengths, such as Neds
password, we do not see as much of an increase in difficulty as the longer passwords.
(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.)
100 msec computation time = 0.100 seconds per password
→ computes 10 passwords per second
(5 · 106
chips)(100 passwords
second ) = 5 · 107
passwords
second
Hal's password is 8 characters:
3
lowercase (a-z) = 26 possibilities for each character
→ 268 password possibilities
268
5 · 107
= 4176.541292 seconds
Lee's password is 12 characters:
lowercase (a-z) = 26 possibilities for each character
→ 2612 password possibilities
2612
5 · 107
= 1.90 · 109
seconds
Pat's password is 16 characters:
lowercase (a-z) = 26 possibilities for each character
→ 2616 password possibilities
2616
5 · 107
= 8.72 · 1014 seconds
This change is effective in stopping Ned since the ASICs are not able to test as
many passwords per second. By testing fewer passwords per second, the time
needed for Ned to crack the password takes significantly longer.
(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.)
single chip computes → 109
passwords
second
(5·106
chips)(109
passwords
second ) = 5 ·1015 passwords
second
2
128 possible passwords
2
128
5 · 1015 = 6.80 ·1022 seconds
4
This is effective in stopping Ned once again because although the rate at which
passwords are tested is fast, the sample space is so large that a significant amount
of time is needed for computation. This time needed for computation proved to
be much larger than the previous designs.
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.
Alice can always win when she plays first against Bob. The approach she would need
to take in order to win is to vary her placement of pennies depending on the available
space left on the table. Since pennies cannot overlap one another, the placement and
distance between pennies is crucial because once there is no longer enough space for
a single penny, the following player loses. To accomplish this, Alice would begin by
placing pennies as close to each other as possible and take note of the remaining space
on the table following each of Bob’s turns. On each of her turns, if there is enough
room for ≥ 3 pennies, she will continue to place her pennies close enough to each
other to maximize the remaining space. However, if there is room for ≤ 2 pennies, she
will place her penny in the space such that it takes up enough room to where Bob has
nowhere to place his penny. Since Bob cannot place his penny, Alice wins.
5