Question

Assume that passwords are selected from four-character combinations of 26 alphabeticcharacters. Assume that an adversary is able to attempt passwords at a rate ofone per second.
a. Assuming no feedback to the adversary until each attempt has been completed,what is the expected time to discover the correct password?
b. Assuming feedback to the adversary flagging an error as each incorrect character is entered, what is the expected time to discover the correct password?

Answer 1

Answer:

for a) the time required is 228488.5 seconds= 63.469 hours

for b) the time required is 54 seconds

Explanation:

for a) since each combination is equally probable , then the number of possible combinations is

CT=Combinations = number of characters^length of password = 26⁴

then the number of combinations at time t will be the total , less the ones already tried:

Ct = CT - (n-1) , since n=α*t  → Ct=CT-α*t  

since each combination is equally probable , then the probability to succeed  

pt = 1/Ct = 1/ (CT- α*t +1)

but the probability of having a success in time t , means also not succeeding in the previous trials , then

Pt = pt*П(1-pk), for k=1 to t-1

Pt = 1/ (CT- α*t +1) П[1-1/ (CT- α*k +1)] = 1/ (CT- α*t +1) П[(CT- α*k )] /(CT- α*k +1)]  

since α=1 ,  

Pt = 1/ (CT- t +1) П[(CT- k )] /(CT- k +1)] = 1/ (CT- t +1)  * [CT- (t-1) ]/CT  =  1/CT

then the expected value of the random variable t= time to discover the correct password is

E(t) = ∑ t* Pt = ∑ t *1/CT , for t=1 until t=CT/α =CT

E(t) = ∑ t *(1/CT) = (1/CT) ∑ t = (1/CT) * CT*(CT+1)/2 = (CT+1)/2

therefore

E(t) = (CT+1)/2 = (26⁴ +1)/2 = 228488.5 seconds = 63.469 hours

for b)

time required = time to find character 1 + time to find character 2 +time to find character 3 +time to find character 4 = 4*time to find character

since the time to find a character is the same case as before but with CT2=Combinations = 26 ,then

t= 4*tc

E(t) = 4*E(tc) = 4*(CT2+1)/2 = 4*(26+1)/2 = 54 seconds