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 grid) to
indicate the number of repetitions, although in principle a password
consisting of more than 5 repetitions of something on a
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 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 used in Klein's
password-cracking studies [12]. As a point of comparison,
even just tracing the outermost cells of a 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.