passwords

From CDS 130

Jump to: navigation, search
Passwords

Contents

  1. Introduction
  2. Preparation
  3. Problem Overview
  4. Questions
    1. Clarification on what to post
    2. Hint
    3. Single-letter
    4. Two-letter
    5. Three-letter +
    6. Counting Tries
    7. Number of tries
  5. Solution
  6. Advanced
    1. while
    2. break
    3. tic/toc

1. Introduction

Many of the fundamental issues related to IT security involve passwords. In this problem you will learn one way in which a password is "cracked" that involves the use of the so-called brute-force approach. You will implement a brute-force password cracking program and explore how it works.

A brute-force approach for cracking passwords is trying all possible passwords. On a luggage lock (see image) with three dials, each with 10 digits, the brute-force approach is to try all combinations. How many combinations are there? How long would a brute-force approach take (on average)?

From media.uxcell.com on August 16 2017 21:19:52.

2. Preparation

Note: I have changed the instructions slightly from the one you used in class. As before each student will get a different answer, but now the answer will be the same on all computers the student uses.

  • Start MATLAB
  • On the command line (you only need to do this once every time you start MATLAB), enter
urlwrite('http://cds130.org/images/isbobspassword.m','isbobspassword.m');

then enter (after replacing FunnyName with your wiki username)

correctguess = isbobspassword(96,'FunnyName')

After entering the second command, you should see

correctguess =

     0

3. Problem Overview

In the preparation step, you downloaded a file. The program in the file isbobspassword is called a function and it performs a simple task: It tells you if you guessed one of the passwords that Bob uses.

You may ask the function if the letter a is one of the passwords by first looking up the ASCII code for this letter (97) and then entering

correctguess = isbobspassword([97])

If your guess is correct, then the variable correctguess will be assigned the value of 1 and you will see

correctguess =

        1

If your guess was incorrect, then correctguess will be assigned the value of 0 and you will see

correctguess =

        0

Suppose you want to determine if one of Bob's passwords is ab. The ASCII code for b is 98, so you would enter

correctguess = isbobspassword([97,98])

and, as was the case for the single-letter guess, if your guess was correct you will see

correctguess =

       1

4. Questions

(40 points - copy your code and answers onto your wiki page)

Background

  • Bob has six passwords that he uses for various purposes.
  • All passwords are lower case letters.
  • One password is one letter, one password is two letters, one password is three letters, etc.
  • The function isbobspassword will return a 1 if you guessed any of the passwords correctly.

4.1. Clarification on what to post

  • Post your answer to the question of "If I collected the answer to the previous question [how many guesses to get the 1-letter password] from each student, what would be the average (assume that the students don't talk to each other)?
  • Post your program for determining the four-letter password (you don't need to post code for all passwords).
  • Post a filled-in table

4.2. Hint

The program was discussed in class (except for the tic/toc part). This program checks all two-letter passwords. You must replace "Weigel" with your wiki username!.

Also noted in class: There may not be enough time to run the program for the six-letter password before the due date. However, it is possible to figure out the six-letter password by looking for patterns in the other passwords.

urlwrite('http://cds130.org/images/isbobspassword.m','isbobspassword.m');
tic;
counter = 0;
for i = [97:122]
  for j = [97:122]
    correct_password = isbobspassword([i,j],'Weigel');
    counter = counter + 1;
    if (correct_password == 1)
      i
      j
      counter
      toc
    end
  end
end

4.3. Single-letter

Use any of the programming techniques covered previously in this course to figure out ("crack") Bob's one-letter password.

  1. What is the password?
  2. How many tries did it take you to guess it?
  3. If I collected the answer to the previous question from each student, what would be the average (assume that the students don't talk to each other This parenthetical note is not needed; it was written when the all students would find the same one-letter password.)?

4.4. Two-letter

Answer the same questions as above except for a two-letter password.

4.5. Three-letter +

Answer the same questions as above except for three-letter, four-letter, and five-letter, and six-letter passwords. You only need to post your program for the four-letter password only.

4.6. Counting Tries

If you used a for loop in the previous problem, modify the program so that it tells you how many tries were required before the correct password was guessed. If you guess the password without a for loop, you may skip this problem.

4.7. Number of tries

Fill in the following table. To place in your wiki, select "view source" or "edit" to reveal the table syntax; copy the table onto your page and replace the question marks with numbers. In the last column, put a rough estimate of time in seconds.

If you were not able to crack a password before the homework is due, put an estimate of how long you think it would take to crack (along with the logic behind your estimate).

Password length Password Number of tries Time to crack
1  ?  ?  ?
2  ?  ?  ?
3  ?  ?  ?
4  ?  ?  ?
5  ?  ?  ?
6  ?  ?  ?

5. Solution

In the programs below, you will see lines that start with 1., 2.<code>, etc. to indicate lines that were added to the previous program.

If you want to follow along in this solution, you must first enter the command:

urlwrite('http://cds130.org/images/isbobspassword.m','isbobspassword.m');

This command downloads a file containing the function <code>isbobspassword. In principle, you can figure out how the passwords are generated by reading this program, but this is not the intended approach for this problem.

Most students initially tried repeatedly entering the command

>> isbobspasssword([97],'Weigel')
 0

>> isbobspasssword([98],'Weigel')

ans =
 0

until they were successful and saw

>> isbobspasssword([108],'Weigel')
 ans =
 1

Many students tried to get the two-letter password using the same approach, that is by repeatedly entering commands as in

>> isbobspasssword([97,97],'Weigel')
>> isbobspasssword([97,98],'Weigel')
>> isbobspasssword([97,99],'Weigel')
>> isbobspasssword([97,100],'Weigel')

Ideally, you would realize that you were repeating a command over and over, and this is related to iteration.

To see how this is related to iteration, try the following approach for guessing the 1-letter password:

i = 97;
isbobspassword([i],'Weigel')
i = 98;
isbobspassword([i],'Weigel')
i = 99;
isbobspassword([i],'Weigel')
i = 100;
isbobspassword([i],'Weigel')

etc. Recall the pattern for commands that can be re-written as a for loop. In the above, the lines with isbobspassword([i],'Weigel') is the DO SOMETHING, so the above can be re-written as

for i = [97:122]
 isbobspassword([i],'Weigel')
end

Now, how would you get the two-letter password? One option is to use

j = 97;
for i = [97:122]
 isbobspassword([i,j],'Weigel')
end
j = 98;
for i = [97:122]
 isbobspassword([i,j],'Weigel')
end
j = 99;
for i = [97:122]
 isbobspassword([i,j],'Weigel')
end 

etc. This also fits the pattern of something that can be re-written short-hand as a for loop. In this case, the DO SOMETHING is three lines as indicated below.

   for j = [97:122]
1.    for i = [97:122]
2.      isbobspassword([i,j],'Weigel')
3.    end
   end

When this program is run, you will see

 ans = 
  0

printed 26*26 - 1 times with a single

ans =
  1

somewhere in between, indicating that one of the passwords was correct.

You could figure out how many tries before ans=1 was displayed to determine how many guesses were required. There is an easier way. First, suppress the output by placing a semi-colon after the password check line (the line containing isbobspassword) and assign the output of isbobspassword to a variable, as in

   for j = [97:122]
    for i = [97:122]
1.    correct_password = isbobspassword([i,j],'Weigel');
    end
   end

Now, for every iteration, correct_password will be assigned a value of 0 or 1. With the above modification nothing will appear on the screen when the program is run because of the semi-colon. To have something appear on the screen when correct_password is 1, add an if statement along with i and j to so that their values are displayed if correct_password is equal to 1:

for j = [97:122]
  for i = [97:122]
     correct_password = isbobspassword([i,j],'Weigel');
1.    if (correct_password == 1)
2.      i
3.      j
4.    end
   end
end

When the above is run, you will only see

i =
114
j =
99

These are the values of i and j when correct_password was 1. To verify that this is indeed a correct password, enter the following on the command line

isbobspassword([114,99],'Weigel')

you should see

ans =
 0

The next step is to modify the program so that when correct_password is 1, then the number of tries is displayed. (Alternatively, you can figure this out manually given the value of i and j.) To display the number of tries it took to get a correct guess, add a variable that keeps track of the number of times isbobspassword was executed. This can be done by incrementing a variable (which I have chosen to have the name counter, but I could have named it, for example, a or b) right after every password try.

1. counter = 0; 
   for j = [97:122]
    for i = [97:122]
      correct_password = isbobspassword([i,j],'Weigel');
2.    counter = counter + 1;
      if (correct_password == 1)
3.      counter
        i
        j
      end
    end
 end

The final step is to add a timer that tells us how much time elapsed between the start of the program and the correct guess (Alternatively, you could estimate this by using a stopwatch). This is done using the tic and toc functions as shown on lines 1 and 2.

1. tic;
   counter = 0; 
   for j = [97:122]
    for i = [97:122]
      correct_password = isbobspassword([i,j],'Weigel');
      counter = counter + 1;
      if (correct_password == 1)
2.     toc
       counter
       i
       j
     end
   end
end

For most students, the 5-letter password program took about 30 minutes. (If you ever want to have MATLAB stop executing a long-running program, enter CTRL-C.) The 6-letter password would take 30 minutes to 13 hours. But there is a pattern in the passwords that allows this time to be reduced. Consider the passwords for the user named 'Weigel'. They were (time in seconds)

Time: 0.003116 Password: 108 
Time: 0.068547 Password: 110 118 
Time: 0.159879 Password: 112 120 98 
Time: 2.455693 Password: 114 122 100  98 
Time: 62.63367 Password: 116  98 102 100 98 

The pattern is that the numbers in each column increment by two (almost) every time. The top password in the first column is 108, the next is 110, the next 112, etc. The top password in the second column is 118, followed by 120 (corresponding to the letter 'x'), 122 (corresponding to the letter 'z'). Because there are no more letters after 'z', the numbers must start over at 97 (corresponding to the letter 'a'). Adding 1 to 122 gives 97, adding 2 to 122 give 98.

Because there is a pattern, you don't need to try all possible six-letter passwords. Instead, you can use the pattern to guess the first 5 letters and then iterate over the last unknown letter:

for m = [97:122]
  correct_password = isbobspassword([118,100,104,102,100,m],'Weigel');
  if (correct_password == 1)
    m
  end
end

Advanced topics. The following discussion covers topics that are not expected to be understood by all students.

If you think about how this program works, you may realized that it continues guessing even after a correct guess was found. There are a number of ways to stop the guessing when a correct answer is found. Here is an example that uses a while loop:

  correct_password = 0;
  i = 97;
  while (correct_password == 0)
    correct_password = isbobspassword([i],'Weigel')
    i = i+1;
  end

To determine longer passwords, add more while loops.

A more advanced approach is to place the for loops in a function. Create a file named guess2.m and enter function [i,j] = guess2()

for j = [97:122]
  for i = [97:122]
     correct_password = isbobspassword([i,j],'Weigel');
     if (correct_password == 1)
       return;
     end
   end
end

If you enter

>> [i,j] = guess2()

the program in the file will be executed. The return statement is a special statement that can be used inside of a function. It means "stop executing the commands in this function". For more on functions and the return statement, see functions.

Previously, the answers given required one for loop for the 1-letter password, two for loops to get the two-letter password, etc. The result is a very long program. There is a way to check all passwords with a single loop. Here it is without explanation:

function [p,t,i] = brute(n,name)
% Call using [p,t,n] = brute()
  
if (nargin == 0)  
  name = 'Weigel';
  urlwrite('http://cds130.org/images/isbobspassword.m','isbobspassword.m');
  for i = 1:6
    [p,t,tries] = brute(i,name);
    t(i) = t;
    tries(i) = tries;
    fprintf('Tries: %7d Time (sec): %f ',tries(i),t(i));
    fprintf('Pass: ');
    fprintf('%d ',p(:));
    fprintf('\n');
  end
  return;
end

tic;
correct = 0;
sz = repmat(26,1,n);
for i = 1:26^n
  [p(1),p(2),p(3),p(4),p(5),p(6)] = ind2sub(sz,i);
  correct = isbobspassword(96+p(1:n),name);
  if (correct == 1)
    break
  end
end
t = toc;
tries = i;
p = 96+p(1:n);

Copy the above into a file named brute.m and then enter brute() on the command line. You should see (times will vary): >> brute() Tries: 12 Time (sec): 0.005374 Pass: 108 Tries: 560 Time (sec): 0.069942 Pass: 110 118 Tries: 1290 Time (sec): 0.157634 Pass: 112 120 98 Tries: 20272 Time (sec): 2.469198 Pass: 114 122 100 98 Tries: 513130 Time (sec): 62.78672 Pass: 116 98 102 100 98 Can you modify the above program so that it uses the pattern to reduce the number of guesses?

6. Advanced

The commands tic, toc, and break may be useful for this assignment. Use of these functions is not required or necessary to solve the problem.

These commands are placed here because at some point a student will ask "Is there a way to stop a for loop when a password is found?" and "Is there a way to measure the time for a for loop to execute other than using a stopwatch?.

6.1. while

Similar to the for loop, the while can be used to iteration.

while (test)
  Execute these commands
end

Means if the statement of test is correct (true) then execute the commands between the while and end. These two programs are equivalent:

i = 1;
while (i < 3)
  i = i+1;
  Do Something
end
for i = [1,2]
  Do Something
end

A while loop can be unrolled:

i = 1;
if (i < 3)
  i = i+1;
  Do Something
end
if (i < 3)
  i = i+1;
  Do Something
end

6.2. break

The break statement

For some problems, you will not want to write a program that always executes every iteration in a for loop. For example, suppose that you are told to execute the following program and that you know that the value of z will always be assigned to be a zero or one because the function isspecial only specifies a zero or one.

g = 3;
for i = [1:100]
   z = isspecial(g);
   if (z == 1)
      DO SOMETHING
   end
end
MORE COMMANDS

If you think about how this program works, you will realize that once z was assigned the value of one and DO SOMETHING is executed no more iterations are needed because DO SOMETHING will never be executed again.

g = 3;
for i = [1:100]
   z = isspecial(g);
   if (z == 1)
      DO SOMETHING
      break;
   end
end
MORE COMMANDS

If you add a break statement right after DO SOMETHING, you indicate that once DO SOMETHING is executed, then no more iterations are needed - the program can just jump (or "break out of the loop") to the line that says MORE COMMANDS.

6.3. tic/toc

The tic and toc statements.

To test how long it takes (in seconds) to DO SOMETHING, place the commands tic (means "start timer") and toc (means "tell me what the timer reads now") before and after the commands:

tic;
DO SOMETHING;
toc

As always, DO SOMETHING may be anything. For example try

tic;
count = 0;
for i = [1:10]
  count = count+1;
end
toc

and then try again by replacing the 10 with 100, 10000, etc.

Consider the following program:

tic;
count = 0;
for i = [1:2]
  count = count + 1;
  toc
end

The "unrolled" version of this loop is

tic;
count = 0;
i = 1;
  count = count + 1;
  toc
i = 2
  count = count + 1;
  toc

Execute the above commands and explain the interpretation of the time that the second toc command reports.

Personal tools