Increasing the Security of Memorized Passwords

--------------------------------------------

Abstract

The security of digital information typically relies on a memorized password. Assuming an individual has taken the usual precautions of not writing the password down or otherwise storing it insecurely, it is still easily retrievable under duress. To reduce this risk, a scheme is proposed which will—at a minimum—increase the cost to an adversary of extracting a password by increasing the difficulty for the possessor to reconstruct it. The scheme relies on memories of the possessor, embedded in a combinatorial puzzle. The scheme has the added benefit of being usable even if the possessor of the password does not have access to computing resources.

--------------------------------------------

Introduction

For most information security scenarios today, human beings are the weakest link in the security chain. From choosing weak passwords, to writing them on notes taped to a monitor, people have bad habits that make many passwords trivial to recover. In circumstances where higher security is encouraged or required, a sufficiently long, random, memorized password is still a weak link, as it can be extracted under duress. In general (and short of storing the password in a self-destructing module of some sort), anything stored in the mind can be retrieved and given away if the person chooses to do so. To make it more difficult to give the secret away, one must put cognitive distance (and hence time) between what they know in an immediate sense, and the password itself.

In what follows, we shall speak of the possessor of a password. The adversary is the individual or organization wishing to extract the password, or a secret encrypted by the password. The adversary may have full access to the secret in its encrypted form.

Not every security scenario requires a strong password, nor do many circumstances call for great effort at security. But there are cases where the maximum achievable security may be warranted:

- Someone holding a key that secures financial information, yet that does not need to be entered regularly. Perhaps it is only used to secure backups, and would thus only be needed if a restore had to be performed.

- A key custodian, who must keep a fragment of a key secure, and who does not want to be compelled to give it to an adversary.

- Someone wishing to keep a secret from those with great resources at their disposal, such as a government.

- An individual responsible for a large number of passwords, who must store them in a password "safe" of some sort. (See [1] for an example.)

To increase the margin of safety for the possessor, several conventional approaches can be employed:

* Use of security questions. It is possible to store a password in the form of a set of security questions, the answers which are then combined by some algorithm to reconstruct the password. The security questions do not have to be memorized, but can be written down. (This assumes the questions have been chosen to be esoteric enough so that only the possessor will know the answers.) This is the approach employed in [2], and is a step in the right direction, but adds little, as it gives the adversary the set of questions that the possessor must be forced to answer.

* Splitting the password mathematically into "shadows", and storing the parts in different physical locations. This will increase the cost to an adversary, but if one is coerced into revealing the locations of the shadows, the password can be easily reconstructed. An example of this is the "Password Matrix" idea of Mike Naylor, posted to sci.crypt [3].


Requirements of a Better Approach

A scheme that would significantly increase the difficulty for an adversary should have the following characteristics:

1. Giving up the password should require the full cooperation of the possessor for an extended period of time. This gives the possessor time to reconsider a decision to divulge the password, or time to intentionally produce one or more incorrect passwords, which will increase the cost to an adversary.

2. Divulging the password should require extended mental concentration. This will make it more difficult for an adversary to succeed with any form of duress that impedes clear thought.

3. It should be difficult for the possessor to carry out the password reconstruction via verbal/aural means. In particular, it should require the use of the possessor's visual sense.

4. The reconstructed password should possess sufficient entropy to prevent brute force attack by computer.

5. It should be possible to reconstruct the password without the aid of computing resources.

6. It should rely on memories known only to the possessor.

The scheme described below meets these requirements, but has some inevitable drawbacks, particularly that reconstructing the password when not under duress also takes a non-trivial amount of time. The scheme's drawbacks are discussed further below.


The Basic Scheme

This scheme relies on related sets of memories known only to the possessor, which are woven into a puzzle, the solution to which reveals the password. The memories need merely be sufficiently cohesive to allow their re-aggregation and re-ordering when studied. A unique 4-digit random number is associated with each memory. (The random numbers should be unique; otherwise, swapping two memories might make no difference in the outcome, thus reducing the number of combinations an adversary would need to try.) When the memories are correctly re-ordered, the series of random numbers is read off and hashed by a simple algorithm to give the password.

For instance, the sets of memories could be related to a residence where one spent significant time as a child. The arrangement of noteworthy objects in the various rooms is a well-ingrained set of memories, but the house itself no longer stands. (Thus it cannot be visited by the adversary.) We choose 3 rooms, and record a cue for each, to aid in recall:

1. hearth room, from west, clockwise
2. dining room, from north, clockwise
3. upstairs bedroom, from door, clockwise

We then write down 3 * 8 = 24 object descriptions, in the stated order:

1. {torsion pendulum clock, gold tree, fireplace, small statue, carved bookends, window, engraving, hat tree}
2. {Max Parrish litho, green chair, red lamp, cuckoo clock, pair of windows, buffet, radiator, curio cabinet}
3. {granddad's picture, graduation picture, grandmother's picture, Currier & Ives litho, bed, trunk, dresser, mirror}

To this is added another set of 40 fake objects, making sure that they were not in any of the rooms, to avoid confusion. These, along with the random 4-digit numbers, are placed into a grid in scrambled order:

+----------------+----------------+----------------+----------------+
|torsion pendulum|front door      |bed             |candlestick     |
| clock          |                |                |                |
|                |                |                |                |
|      0185      |      2556      |      2643      |      1709      |
+----------------+----------------+----------------+----------------+
|wood box        |trunk           |Max Parrish lith|dead electrical |
|                |                |o               |outlet          |
|                |                |                |                |
|      7278      |      3025      |      9855      |      1627      |
+----------------+----------------+----------------+----------------+
|kerosene lamp   |stove pipe      |gold tree       |hat tree        |
|                |                |                |                |
|                |                |                |                |
|      7389      |      9253      |      7217      |       8189     |
+----------------+----------------+----------------+----------------+
|coat closet     |dresser         |cuckoo clock    |fireplace       |
|                |                |                |                |
|                |                |                |                |
|      2099      |      9801      |      6940      |      0373      |
+----------------+----------------+----------------+----------------+
|key to door     |Currier & Ives l|stove           |troublesome ligh|
|                |itho            |                |t fixture       |
|                |                |                |                |
|      4010      |      1685      |      5341      |      1106      |
+----------------+----------------+----------------+----------------+
|Bible           |buffet          |curio cabinet   |removed shoes   |
|                |                |                |                |
|                |                |                |                |
|      2045      |      2879      |      9907      |      7830      |
+----------------+----------------+----------------+----------------+
|carved bookends |history book    |tool box        |small statue    |
|                |                |                |                |
|                |                |                |                |
|      4995      |      8352      |      7622      |      6073      |
+----------------+----------------+----------------+----------------+
|matches         |mousetrap       |broom and dustpa|cat window      |
|                |                |n               |                |
|                |                |                |                |
|      3768      |      0898      |      7460      |      5326      |
+----------------+----------------+----------------+----------------+
|balcony door    |large electric c|ash tray        |brush           |
|                |lock            |                |                |
|                |                |                |                |
|      4085      |      1248      |      8605      |      0095      |
+----------------+----------------+----------------+----------------+
|camera          |back of pantry  |umbrella stand  |screen door     |
|                |                |                |                |
|                |                |                |                |
|      9041      |      9941      |      1529      |      0109      |
+----------------+----------------+----------------+----------------+
|deck of cards   |red lamp        |blue lamp       |engraving       |
|                |                |                |                |
|                |                |                |                |
|      7923      |      2468      |      7400      |      9549      |
+----------------+----------------+----------------+----------------+
|television      |magazine basket |pair of windows |shelf of games  |
|                |                |                |                |
|                |                |                |                |
|      9852      |      2522      |      0496      |      6416      |
+----------------+----------------+----------------+----------------+
|where dog slept |stairway to base|granddad's pictu|boot scraper    |
|                |ment            |re              |                |
|                |                |                |                |
|      2432      |      1011      |      5354      |      6657      |
+----------------+----------------+----------------+----------------+
|window          |green chair     |Webster's dictio|furnace register|
|                |                |nary            |                |
|                |                |                |                |
|      5607      |      2737      |      1935      |      7674      |
+----------------+----------------+----------------+----------------+
|coin jar        |mirror          |grandmothers pic|vacuum tube radi|
|                |                |ture            |o               |
|                |                |                |                |
|      7259      |      1572      |      6027      |      7185      |
+----------------+----------------+----------------+----------------+
|radiator        |graduation pictu|red sofa        |small round tabl|
|                |re              |                |e               |
|                |                |                |                |
|      5773      |      6847      |      8107      |      3466      |
+----------------+----------------+----------------+----------------+

To arrive at the password, the random digits from the correctly-ordered memories are read off, giving the following digit sequence:

0185 7217 0373 6073 4995 5607 9549 8189
9855 2737 2468 6940 0496 2879 5773 9907
5354 6847 6027 1685 2643 3025 9801 1572

Picking 24 elements from a set of 64 provides for approximately 10^41 possible permutations, or around 136 bits of entropy. But a password of 96 digits would be unwieldy due to its length, and does not have anywhere near the maximum possible entropy. To remedy this, a grid such as the following should be generated, and printed out at the same time as the grid of memories and random numbers. This grid has 6 rows of 32 columns, and in each column exactly 3 cells are blocked out:

|~|~|~| |~|~| | |~|~| | |~| |~|~|~|~| | | | |~| |~|~| | |~|~|~| |
|~|~| |~|~| |~|~|~| |~| |~|~| | | |~|~|~| |~| |~| | |~|~| | |~| |
| | | | | |~|~|~| |~| |~| |~|~| | | |~|~|~|~| | |~| | |~|~| | | |
|~| |~|~| | |~|~| | |~| | |~| |~| |~|~|~|~| | |~|~|~|~|~|~|~| |~|
| | |~|~| |~| | | | |~|~|~| |~| |~| | | |~| |~|~| | |~| | | | |~|
| |~| | |~| | | |~|~| |~| | | |~|~| | | | |~|~| | |~| | | |~|~|~|

The empty cells of this grid are filled in with the random digits from the above sequence, left-to-right, top-to-bottom, giving this:

|~|~|~|0|~|~|1|8|~|~|5|7|~|2|~|~|~|~|1|7|0|3|~|7|~|~|3|6|~|~|~|0|
|~|~|7|~|~|3|~|~|~|4|~|9|~|~|9|5|5|~|~|~|6|~|0|~|7|9|~|~|5|4|~|9|
|8|1|8|9|9|~|~|~|8|~|5|~|5|~|~|2|7|3|~|~|~|~|7|2|~|4|6|~|~|8|6|9|
|~|4|~|~|0|0|~|~|4|9|~|6|2|~|8|~|7|~|~|~|~|9|5|~|~|~|~|~|~|~|7|~|
|7|3|~|~|9|~|9|0|7|5|~|~|~|3|~|5|~|4|6|8|~|4|~|~|7|6|~|0|2|7|1|~|
|6|~|8|5|~|2|6|4|~|~|3|~|3|0|2|~|~|5|9|8|0|~|~|1|1|~|5|7|2|~|~|~|

The non-empty cells are then added with carry, giving the following sum:

2 0 4 5 8 6 7 4 0 9 5 3 0 7 0 4 0 3 8 3 7 7 3 1 7 0 5 4 1 0 5 8

(Any carry out of the highest digit column is ignored.) This produces a 32-digit number, which can form the final password. As one would expect, simulations of this approach show that its one- and two-digit frequencies are indistinguishable from uniformly sampled random digits.

The cues should be printed out, along with the scrambled grid of memories. The grid cells may be cut apart for easier resequencing and reading off of the digits. (Note that if the cells were printed out in their original order, merely cutting them apart with scissors would allow them to be trivially resequenced by matching up edges. Therefore, they should never be printed out in their original order.)

Reconstructing the password merely repeats the above steps, starting from the correctly sequenced memories.

The final summation step is not equivalent to a secure, cryptographic hash. However, it does guarantee that a change in the selection of one cell from the cue grid will affect at least 4 digits in the final password. This will make it more difficult (but not necessarily impossible) for an adversary to discover which memories were used in forming a particular password, should the password become known.

Memories other than spatial memories regarding objects could also be used. Some possibilities include the order of people you have dated, or the order in which various vacations were taken. It is crucial that nobody else be able to remember or discover the facts used in creating the puzzle.


Further Improvements

If it is desired to produce a password using all available printable characters, then triplets of digits can be read off of the above grid, perhaps going down the columns. Each triplet can then be used in conjunction with a lookup table to produce a character drawn from the set of all printable characters.

The cues could be omitted, and figuring them out from the listed objects could be part of the puzzle.

It would also be possible, using software, to take a pre-existing password and assign random numbers to memories in such a way that re-assembling them would produce that specific password. This approach would enable existing passwords to be encoded into a puzzle.


Discussion

The drawbacks of this scheme appear to be unavoidable consequences of the very requirements we are trying to meet. The following are apparent:

1. The cues and memories have to be written down. This gives the adversary something to work with.

2. The cues and memories can be lost. This risk can be mitigated by making copies and dispersing them physically.

3. It takes a non-trivial amount of time to construct such a puzzle and to ensure that the memories are not ambiguous, and won't likely be forgotten. Software will aid in creating the puzzle, however.

4. As a memorized password can be forgotten, so can the exact lists of objects, events, people, etc., that the possessor chooses to use in the puzzle. Periodic review of the puzzle may be necessary to ensure that the correct cues can still be spotted. (But it should not be reviewed so frequently that the solution becomes rote.) This could also be ameliorated by employing the shadowing scheme described in [2].

5. It takes a non-trivial amount of time to reconstruct the password, even when not under duress. Without the aid of software, experiments show that a password can be reconstructed in about an hour. Software would shorten this time considerably.


References

1. See http://keepass.info/ for an open-source password safe.

2. Carl Ellison, Chris Hall, Randy Milbert, and Bruce Schneier. “Protecting Secret Keys with Personal Entropy”, available at http://www.schneier.com/paper-personal-entropy.html.

3. http://groups.google.com/group/alt.security/browse_thread/thread/8a9ebc09fd1d590a/d43097730177aee8?hl=en&q=sci.crypt+grille+password#d43097730177aee8