Mnemonic Password Generation Algorithm for QWERTY Keyboards

Question

I've a "mnemonic" password generation function that goes something like this:

function Mnemonic($mnemonic)
{
    $result = null;
    $charset = array(str_split('aeiou', 1), str_split('bcdfghjklmnpqrstvwxyz', 1));

    for ($i = 1; $i <= $mnemonic; $i++)
    {
        $result .= $charset[$i % 2][array_rand($charset[$i % 2])];
    }

    return $result;
}

Basically this generates a string with $mnemonic length where every odd character is a consonant and every even character is a vowel. While I understand this reduces the password complexity it's usually much more easier to remember. Now I want to improve it by generating strings that are easy to type.

For instance, while a *nix newbie I always prefer RHEL based distributions over Debian ones, the main reason is the ease of typing yum versus the ease of typing apt[-get], just try it for yourself.

How should I implement the logic to generate strings that are easy to type on QWERTY keyboards?

Ramah

Define "easier to type." I usually find that the words I can most easily type are the ones I can pronounce - so your method would work perfectly for that. – Brause

@Alix Axel, I actually find apt easier to type than yum specifically because you can alternate hands while typing. – Tenebrific

@BlueRaja: Try typing yum and try typing apt; yum should be way easier to type (specially with just one hand). As additional easy to type examples try typing serverde or begreen; or yii vs zend. – Ramah

@avakar: That's odd, I feel otherwise. – Ramah

Those are all just about as easy as one another for me to type, except for "begreen" and "yii," which I type a bit slower because of the double letters. I too type "apt" slightly faster tham "yum," because of the alternating hands, and the fact that sometimes use only two fingers for "yum" – Brause

I agree that apt is easier to type than yum. Yum requires me to type two adjacent letters with the same finger – Hamford

I must add that apt is easier than yum for me as well. Hopefully with enough supporters we can convince that easy-to-type is ambiguous to the typing style of the individual. Some people poke at the keyboard with one finger; some use strict typing techniques as taught in class; some use their self-grown method. I do not believe you can find any algorithm that produces easy-to-type passwords for all people. – Aideaidedecamp

This is a really fascinating question... – Scouring

Answer 1

You may wanna take a look at the principles used in the Dvorak keyboard,

Those principles applied in a password-generating algorithm would be:

• Letters should be typed by altering hands.
• Use easy to type combinations. Take a look at the Dvorak layout and see the common digraphs and the positions of their letters.
• Use only one letter from the bottom row, or not. Make it random!
• You can make the ratio 2 to 1 (2 letters typed by the right hand to 1 letter typed by the left hand).
• Since the ratio is 2 to 1, you're gonna have 2 consecutive letters typed by the same hand so you're gonna have to make sure they are typed from the outside of the keyboard to the inside. This principle is applied to the digraphs.

I know you said it's a QWERTY keyboard but using these principles on a QWERTY keyboard can give you some very good results, like:

ktrd,ogkdo ("typewriter" in dvorak)

kjg;g;akd;k (using only the home row)

pjedoildupsk (just a random password following the principles)

All Dvorak haters, shush it!

I hope this helps.

Sheathe

You suggestion is similar to the suggestion provided by @superUntitled, the problem with alternating hands is that I can only use "ae" or "uio" in my even letters (see my original function). How would you solve this? – Ramah

@Alix Axel: Well, my method is more flexible than that of @Beguin because I'm suggesting you use a 2 to 1 ratio instead of 1 to 1, and it doesn't have to be exactly RRLRRLRRL, look at the random password sample, that follows my principles (not the vowels, though). It's RRLLRRLRRLR which makes it possible to use any of the 5 vowels. – Sheathe

pjedoildupsk doesn't follow your guidelines. u and p are typed from the inside out by the right hand, as are o and i. – Hamford

Answer 2

Carpalx has a lot of research on calculating typing effort, which incorporates:

• finger travel distance
• hand, finger and row penalties
• stroke path

The outcome of their research is the Colemak keyboard layout, which claims to be better than Dvorak.

However, it's written backward from what you want - their goal is to find a better keyboard layout based on input, but you're trying to find easy input based on the keyboard layout.

So - even though you might not be able to use it directly, I thought you might find it interesting (and who knows, if your Perl-fu is strong, you might be able to extract and reverse the algorithm, since it's GPL'd).

Staal

My Perl'fu isn't that strong, but I really appreciate the link, thanks, – Ramah

This answer is the only relevant answer based on some research. All the rest is just guesswork. Without an objective measure, "harder to type" just makes no sense and is very subjective. – Bloodline

@Vinko. What are you talking about? This is probably the most irrelevant answer. This answer answers a totally different question. So what if they did 'objective research' and determined an optimal keyboard layout based on some corpus of words? How does that help the questioner figure out how to generate passwords for better typing on a QWERTY keyboard? – Clotho

@Moron: I'm talking about that everybody is inventing heuristics without any research whatsoever, that is as good as (or even worse than) the original algorithm, we can never know because it's just guesswork without a background or even consensus about terms. This answer provides a framework to build on an actual solution, see mkweb.bcgsc.ca/carpalx/?model_parameters and mkweb.bcgsc.ca/carpalx/?typing_effort. That the model was used to derive a new layout doesn't mean is useless to find letter combinations that are less stressful on a fixed layout. – Bloodline

@Vinko: If you look at the link you described, they have no supporting data for the heuristic they chose and in fact they themselves say that some of the parameters are subjective. Determining the best heuristic is subjective (to the problem at hand(no pun intended)). Any research you do won't change that fact. In fact the more research you do, the more irrelevant it might be to the OP. That said, I agree that the typing effort page should be useful and so is not irrelevant, but I don't see how this is more relevant than any other suggestion of a heuristic model. – Clotho

@Moron: For example, which of the heuristics stated represent a complete model which can be tuned according to the subjective parameters? Are those subjective parameters even defined in any of the answers? Saying "research" was wrong, but I guess what I'm trying to say is that carpalx has a lot more work behind than any answer here and it shows. – Bloodline

@Vinko:Of course they have done a lot more work, but most of the work was done after they pulled a heuristic out of thin air. I would say that suggesting a way to come up with a heuristic model is more valuable than giving a heuristic itself, as the question itself if quite subjective. If they had trained the heuristic on say a large sample of people and then come up with what they suggest, then it might have been more relevant and more useful to OP, I agree. In any case, since it wasn't clear what the OP wanted, I guess our discussion about which answer is better is kind of pointless. – Clotho

@Moron: That this discussion is pointless I fully agree with. I just have a knack for pointless discussions. – Bloodline

Answer 3

You could eliminate all characters that are typed with the ring and pinky finger (q,w,x,z,p), then spit the characters that are typed by the left and the right hands and alternate between these letters.

Beguin

+1, That's a pretty good and easy to implement suggestion, thanks! – Ramah

I tried implementing this but I realized that by switching between the left and right finger keys my mnemonic function kinda loses the point, because I will only have either "ae" or "(y)uio" as vowels. – Ramah

randomly, bit with <50% chance per key keep the same side, I suspect about 25% chance of swap will lead to reasonable to type but still distributed. Also ensure your generated password have a 50/50 chance of starting either side (and consonant/vowel). this will significantly reduce your vulnerability to brute force attacks. – Archon

Answer 4

Perhaps you can use some heuristic to measure the 'ease of typing'.

For instance, consider the cost of moving a finger when going to the next character. This can be a function of how far the finger needs to move, which direction etc.

You could also add extra costs, when it is required to switch fingers, or hands.

After playing around with the costs a bit, you will probably hit upon a satisfactory solution.

Hope that helps.

Clotho

That is my idea, but I'm having trouble figuring out how I would implement such heuristics. – Ramah

Is the problem figuring out the weights or you actually have a problem writing code to figure out costs of moving etc? – Clotho

@Moron: Figuring out the cost of moving from char to char + 1 is my main concern... – Ramah

One easy way is for every pair of letters you compute a cost. For instance (j,k) = 1, (j,l) = 2, (m,y) = 3 etc store that in a table, and just lookup. For simplicity, you could lay out the characters on a grid and compute the manhattan distance for instance. – Clotho

For every 26 letters, computing a pair cost would be pretty tedious to do manually. Can I speed up the generation of the lookup table automatically? – Ramah

Yes, like I said, using the 'Manhattan' distance you can compute the table, but you don't need to maintain a table for that, if you already have the code to calculate the table :) – Clotho

Answer 5

Great question - taking the above suggestions, here's a formulae for the distance from key i to key j:

Weight = distance * a + switch * b + same * c + shift * d + weird * e + start * f

Distance is a value, the others are 0/1 values.

Distance - get by superimposing a fine grid over a QWERTY keyboard, lookup the x,y and calculate the distance. Distance has a positive weight. If the letter combination is with the use of different hands (e.g aj, sk, wu...), the distance is zero.

Switch - negative weight; switching is good

Same - aq, qa, az, za use the same finger. Same is positive

Shift - anything with a shift is positive and real bad

Weird - I dunno $ or ~ is bad because you have to look at the keyboard.

Start - asdfjkl starting or ending. Probably negative & good since your fingers are there at rest.

Coefficients - just make 'em up to start as long as the relative values seem reasonable. If you REALLY want to get fancy - get someone to type in several dozen sets of numbers, use a stop watch and fit a regression model.

Implementation - say we have a six character password.

Now I need the lowest value for six characters starting with each letter. Imagine an array of your N keys in a columns. Now imagine six columns. Your shortest password is the shortest path through the six columns (with cycles allowed). You might need to add some logic to eliminate cycles, but this should be a good first pass. (I'm getting lazy here - there's probably a graph theoretic formulation that handles this problem.)

I'll bet someone has done this before - especially the keystroke part.

Knipe

Answer 6

I smashed together the following. It's a hack job but it seems to work pretty good.

<?
function Mnemonic($mnemonic)
{
    $result = null;
    $charset = array(str_split('@a3e!1i0ou', 1), str_split('#$*bcdfghjklmnpqrstvwxyz', 1));

    $lastchar = ' ';
    for ($i = 1; $i <= $mnemonic; $i++)
    {
      do {
        $char = $charset[$i % 2][array_rand($charset[$i % 2])];
      } while (!nextkey($lastchar, $char));
      $result .= $char;
    }

    return $result;
}

function nextkey($lastchar, $requestchar)
{
  $map = array();
  $map[] = '!qaz'; // ll
  $map[] = @#wsx1'; // lr
  $map[] = 'ed23'; // lm
  $map[] = '$%^rtfgcvb456'; // li
  $map[] = '&yhnujm7'; // ri
  $map[] = '*()ik89'; // rm
  $map[] = 'olp,.'; // rr
  $map[] = ';[]'; // rl
  $map[] = '!@#$%^&*()[]'; // special chars, don't follow
  $map[] = 'pbvcnmq'; // consonant clusters, don't follwo

  if($lastchar == $requestchar) return true;
  foreach($map as $string)
    if(strpos($string, $requestchar) && strpos($string, $lastchar)) return false;
  return true;
}

printf("%s\n", Mnemonic(8));
?>

Barbera

Answer 7

Build a data structure that represents a keyboard and codes the row, column, hand, and finger used to type each character. Write a function that, when presented with a character, provides a list of "easy to type next" characters, based on flexible rules that you develop. It could rely on another function that calculates the distance between keys.

Personally, I don't find typing letters with the same hand twice to be slow: only if a previous letter used a finger that was too close is it difficult. For example, XQ is hard to type because my hand has to move upward to handle the adjacent fingers required to type them. But I don't find BQ hard to type at all, because while my forefinger is still working on the B, my pinkie finger can head for the Q.

It is also much easier to type AW than QS, because the ring finger is longer and so naturally fits on the W while the pinkie is on A, in a near-resting position, while QS requires a stretch of the pinkie and a simultaneous, conflicting muscular crunch of the ring finger.

If you start to build up a map of each letter against each other letter, you will soon find a reasonable way to represent various aspects of ease or difficulty. Generalizing my XQ/BQ example, you could make one-row changes require a distance of 2 or more fingers, 2-row changes require a distance of 3 fingers, and 3-row changes (numbers, perhaps) require alternate hands.

I'm also noticing that the slightly longer distance between WD and IL than SE and KO also alters difficulty, because of the slightly jagged placement of keys.

With some analysis (I recommend using Excel to "map out" typing difficulty) I'm sure you can come up with an algorithm that helps you construct easy-to-type words.

If possible, try throwing in at least one number, and consider using spaces as well.

Hamford

Answer 8

If you implement this, please take the user's locale into account when determining the "cost" of moving from one character to another. An easy-to-type password might become rather cumbersome if the user is using a different keyboard layout. Some keys that might be easy to access on one language's keyboard might not be available on another language's keyboard without requiring extra modifier keys (shift, meta, etc).

To keep this idea universal, I would recommend ignoring what character belongs to what key and instead treating the keys as an array with rows and columns. Each row is typically offset from the previous by roughly 1/3 of a key width. With this in mind, it shouldn't be difficult to calculate the distance between any two arbitrary keys:

# Key at top left corner is {0, 0}
key1 @ {x1, y1}
key2 @ {x2, y2}

xdistance = absolute_value(x2 - x1)
ydistance = absolute_value(y2 - y1)

if y1 > y2
  xdistance += (1/3 * ydistance)
else
  xdistance -= (1/3 * ydistance)

total_distance = square_root(xdistance^2 + ydistance^2)

Generate a series of key positions meeting your length and "ease of typing" requirements, then use the user's current keymap to re-map those indices into characters.

Holladay