Memorability based on short algorithms

The second set of passwords that we describe is suggested by the discussion of text-based graphical passwords in Section 2, which pointed toward a different definition of memorability. There, a memorable sequence of positions seemed characterized by the fact that there existed a short algorithm to describe the sequence. It is this definition of memorable that we wish to apply here, since it can be characterized in precise terms. We do not argue that every memorable password has a short algorithm to describe it, but that passwords describable by short algorithms are memorable. We will show that the cardinality of this subset of memorable passwords is already larger than the dictionary of character sequences from which users most often draw their passwords, and that therefore, following the argument above, the DAS password scheme should be harder to crack in practice than the conventional textual scheme.

In order to characterize the ``complexity'' of the algorithm required to generate a DAS password, we define a very simple language suited to the task of describing DAS passwords. Then, we generate all programs in this language whose complexity is at most a chosen maximum. In order to avoid counting different programs that produce the same password twice, we then execute the generated programs to output the passwords, which are then bucketed, and distinct passwords counted. The result is the number of DAS passwords generated by programs of complexity at most the chosen maximum.

Before describing the results of this endeavor, we give some details of the language in which we generated the programs. The grammar of the language is as follows:

program	:	digit digit block
block	:	statement block
statement	:	instr | repeat digit block end
instr	:	up | down | right | left | penup | pendown
digit	:	1 | 2 | 3 | 4 | 5

The first two digits represent a starting position. The instructions up, down, left, and right move the pen one square in the indicated direction. If the pen is currently in the down position, then moving in the specific direction will draw a line. Otherwise, the direction statement will merely move the pen location. The pen begins in the up position. The repeat statement is our iterator. We allow digit values up to the number of grid squares on each axis (i.e., 5 on a $5 \times 5$ grid) to indicate the number of repetitions, although in principle a password consisting of more than 5 repetitions of something on a $5 \times 5$ grid are possible (e.g., ten dots in the same position).

To calculate the complexity for a given program, we assign a complexity to each literal in our language. We assign every statement and digit complexity one, except for the end marker, which has complexity zero. This means that repeat loops have a complexity of two (one for the repeat statement, and one for the integer indicating the number of repetitions) plus the complexity of the repeated block. In addition, the last penup statement of a program is assigned a complexity of zero (lifting one's pen from the surface at the end of entering a password is difficult to forget). So, for example, there are no programs of complexity only two, since the integers describing the starting position of the program already consume a complexity of two without allowing any pendown statements. The first complexity of which there are any programs is three--the two digits describing the initial starting position, followed by a pendown--and the passwords generated by programs of complexity three are simply those consisting of a single tap on one of the grid squares. Note that our complexity calculations for programs are very conservative, in the sense that even pen movements between strokes (i.e., while the pen is raised) are counted in the complexity of a program.

The results of using the above described procedure for counting the number of DAS passwords of a given complexity on a $5 \times 5$ grid are shown in Figure 4. As expected, this data shows that the number of DAS passwords grows exponentially as a function of the maximum complexity of the program. What is more interesting, however, is that by extrapolation we see that the number of DAS passwords generated by programs of only complexity 12 far surpasses the dictionary size of approximately $3 \times 10^6$ used in Klein's password-cracking studies [12]. As a point of comparison, even just tracing the outermost cells of a $5 \times 5$ grid to make a square already requires a program of complexity at least fifteen in our simple language. And, obviously this design and many other, more complex ones will fall in the realm of memorable for most users. We believe that this is compelling evidence that DAS passwords, of which those generated by programs of complexity at most twelve are but a very small subset, will be significantly harder to crack in practice than textual passwords. Example DAS passwords and the shortest programs that generate them are given in Appendix B.

  

Figure: Number of DAS passwords generated by programs of small complexity on a $5 \times 5$ grid.