A design for passwords with system-assigned randomness and user choice
by Stephen Hewitt | Published
This article describes a way of providing passwords to users of a computer system so that the responsibility for making the password secure is separated from the conflicting goal of making it memorable. The system is responsible for making the password secure and the user is responsible for making it memorable.
At first registration or upon resetting a password the system allocates the user a secret random number or seed. The seed must be kept secret. The entropy of this seed has been set by the system administrator according to the security level required.
The security principle of the design is that the original seed can always be recovered from the password, meaning that the entropy of the password is at least that of the seed.
For example if 40 bits were considered an adequate security level then the seed might simply be a hexadecimal string of 10 characters such as “a3bf9d33f1”. However, in general the system should provide the number in whatever base or format will be convenient to the user for the next step, as explained next. The user writes the seed down temporarily and must keep it secure.
The user is then given a period off-line to create a mnemonic password or pass phrase that represents the seed with instructions on how to do this. Systems for this have been described in previous articles [PW1][PW2] and are an integral part of this design.
In the system described in [PW2] for example, words or abbreviations of words are split into 256 different partitions [256PARTS], and each partition represents a possible value of a byte. These partitions are public. For each byte in the seed, the user is free to choose at that point in the password any word from the correct partition for that byte value. Using that system, the user could see directly from hexadecimal digits in the example above which partition is indicated. For another system described in [PW1], there are 225 partitions rather than 256 and so the seed would be presented to the user in a base 225 representation.
The user chooses a preferred word from each of the indicated partitions, resulting in a sequence of words or their abbreviations. The words can be chosen for memorability in a mnemonic system such as the method of locii or a link system or to make a story.
At the second registration step (for example the next day) the user logs in using the seed. The system then prompts for entry of the new user-created password and stores it in the usual way, after checking that it does indeed represent the seed.
From this point the original seed is no longer needed and the user should securely destroy any written trace of it.
Implementation in existing systems
The system could work on top of a typical existing password storage system that stores the user password as a cryptographic hash. There would be no need to change the storage system, providing that the login system can distinguish between a seed and a password. One way of distinguishing might be by requiring a certain character in the stored seed that is prohibited in the password, (for example a prefix of '#', where '#' is not allowed in a password) or by making them guaranteed different lengths.
At the first registration session, the seed is hashed and stored just like a password. When someone logs in using a seed the login system prompts them to change it to a password as described above, and then stores the hashed password in place of the seed.
The login system never allows a user to create a seed, but only to receive a randomly-generated one, so the presence of a seed in the password database means that the system generated it earlier and the user should be permitted to change it to any password which represents it.
See below for links.
- How to remember a provably strong password: a new way using ‘constrained choice’, Stephen Hewitt, Cambridge Clarion, July 2018.
- How to remember a 128-bit key using ‘constrained choice’, August 2018.
- A 256-part list for memorising 128-bit keys by constrained choice, Version 1, Stephen Hewitt, August 2018.