Re: Paper & pencil password algorithm

Maaartin <grajcar1@xxxxxxxxx> wrote:

A couple of questions for James:

Are you ready to switch to base 11 for the whole computation?

I would be reluctant to do that for two reasons: Firstly, I appear to
have a workable system based only on permutation and addition mod 10,
which everyone I've asked finds easy. Mod 11 arithmetic got me burnt
once already. And secondly, even *I* find mod 10 addition so much
quicker to perform.

I would consider mod 11 again if it can be shown that my mod 10 method
has a fatal flaw. Actually, it's well overdue for me to discuss my
method here. I keep delaying because I haven't yet ironed out the
wrinkles in the post-hash step of my process. I think I should give up
on being able to publish the whole thing at once, and instead pick it
apart for you right here and now. (See below.)

I promise there'll be no multiplication (so your girlfriend doesn't
get angry with you:D), just additions and counting to at most ten.

I thought you suggested mod 11 originally because it avoided zero
divisors in the multiplication. I am doubtful of its value in an
addition process, but I'd be curious to see what you have in mind
anyway.

Pls, try if you can perform computations like
5+7 = 1 mod 11
4+6 = A mod 11
A + A = 9 mod 11
with no more errors than in decimal.

I previously tried your mod 11 multiplication process and found it quite
a bit slower to do in my head. The additions look like they would be a
little easier than multiplication (in my mind I'd do the addition like
in mod 10, then subtract one if it was more than 10) but mistakes seem
likely.

I (after some training) can do it, if you can as well,
than I'll describe my idea. Can you?

I am sure that with a few hours practice I could learn the direct answer
for each pair of operands, and get fairly quick at it. I doubt that I
would ever be as quick as I am at mod 10 addition, and there is always
the risk of slipping into mod 10 by mistake as that is so much more
natural. All the mental arithmetic people do in their daily lives is
base ten, and mod ten is just ignoring all but the units. It's difficult
to break that habit.

Also, although it seems to us easy to comprehend mod 11 arithmetic, I
doubt that I could teach any non mathematicians to do it. They might do
it while I watched them, but they'd soon tire of it and this would be a
contributory factor in them abandoning the whole password algorithm I
think.

Can you transform the input (URL and username or whatever) to digits
easily?

Yes, currently I am using a 10x10 Polybius square. This allows direct
lookup of all the base 10 digit pairs that result from the hashing step.

Can you transform a string of base 11 digits to password easily, too?

I guess you could extend the Polybius square to 11x11, but finding
universally keyboard-accessible characters to fill the extra space might
be tricky.

Would a string of decimal digits be any better for you here?

How would you convert base 11 digits to base 10 digits with uniform
distribution?

Actually, the 10x10 square was also tricky to fill. That's 100
characters to find on the keyboard. As a traveller I am aware that
different countries have quite different keyboard layouts, and they
don't all share the same set of punctuation characters for example. In
fact the Polybius square I'm using in my testing will probably need
revising when I discover keyboards missing some of the characters I'm
using.

Do you want to use some additional key or do you consider your
Polybius square to be large enough? How large is it?

Ok, so it's time I involved you in my current design and discovery
process. Here is my password algorithm so far. Start with a 10x10
Polybius square to use as the key, for example:

0 1 2 3 4 5 6 7 8 9
+---------------------+
0 | e t a o i n @ s h r | 0
1 | : a 0 w v u t s A d | 1
2 | , b 1 x X W V r B l | 2
3 | & c 2 y Y - U q C u | 3
4 | $ d 3 z Z . T p D ! | 4
5 | % e 4 P Q R S o E 0 | 5
6 | # f 5 6 7 8 9 n F 1 | 6
7 | ? g h i j k l m G 2 | 7
8 | = O N M L K J I H 3 | 8
9 | / * _ + 9 8 7 6 5 4 | 9
+---------------------+
0 1 2 3 4 5 6 7 8 9

As I was having trouble finding enough unique characters to fill 10x10,
my solution was to fill the central 8x8 portion uniquely, and then allow
duplication of some of those characters in the surrounding box (the box
made of rows and columns 0 and 9). When I translate a site name to
digits, I must give the central 8x8 portion priority if there is a
duplicate in the surrounding box, but when I translate digits back to
password characters I can use the character that the digits indicate
without restriction.

Because I wanted the key to be memorable, I have used certain patterns
in its construction. The pattern used in the example above is easy to
spot, but there are many such patterns and rules that can be used in
combination (diagonals, spirals, alternating, different step sizes,
keywords, etc) so the variation is endless and yet the keys are easy to
regenerate from memory by following the same filling pattern or rule.

My development of the "Maaartin hash" is to use a permutation I nickname
"fold" and then a "sum" operation at least twice: fold, sum, fold, sum.
Twice is enough to get quite good results, and three times is even
better. Beyond three times the paper working involved outweighs the
benefit, and it is doubtful whether even three times is worthwhile, but
I'm undecided on whether it should be 2 or 3 foldsums. I guess each user
of the algorithm can decide for themselves as long as they are
consistent.

The "sum" operation is basically the same as the one you suggested with
the modification that the first digit in the row is incremented (as if
there were an invisible 1 to its left). You used a zero there, but I
found that rows of even numbers would get trapped as even numbers, and
it's worse for rows of zeros. Adding the one at the beginning of the row
is a small price to pay for correcting this.

The "fold" operation can be visualised as folding the string of digits
in half and interleaving the digits of each half together. So if we
started with the digit string 0123456789, it would look like this:

0123456789 --> 0 1 2 3 4 --> 0 1 2 3 4 --> 9081726354
5 9 8 7 6 5
6
7
8
9

In practice, on paper it is simpler just to copy the row of digits into
every other space and when you get to the end of the space taken up by
the row above:

0123456789
.0.1.2.3.4

then you know it is time to turn around and continue copying the digits
down into the spaces between the others:

0123456789
.0.1.26354
and so on until:
9081726354

As an example, let's put "google" through the entire process. I will
write the digit pairs with the left side co-ordinate first, followed by
the top side co-ordinate:

g o o g l e
71 57 57 71 76 51

715757717651 (orig)
175165771577 (fold)
294516301630 (sum)
023964150136 (fold)
136515611251 (sum)

13 65 15 61 12 51
w 8 u f 0 e w8uf0e

Small modifications in the input name produce completely different
passwords, as required:

71575771765122 (orig) google1
27211557657717 (fold)
30234941729674 (sum)
43706293247914 (fold)
58551325718782 (sum) ERwWgIN

71575771765132 (orig) google2
27311557657717 (fold)
30345052830785 (sum)
53807304358025 (fold)
69774771497794 (sum) 1mpg!m9

71575771765142 (orig) google3
27411557657717 (fold)
30456163941896 (sum)
63908415469136 (fold)
70997127176706 (sum) ?4grsn@

This fold+sum hash method is quick and easy to do, and produces good
results, so I'll stick with it unless someone can see any cryptographic
weaknesses in the foldsum technique (or maybe suggest an even quicker
and better method). The worst cases are when there is only a
transposition of two letters in the centre of the name:

With 2 foldsums: google --> w8uf0e
gogole --> wb0f0e

But this is probably an infrequent occurrence in practise, so maybe
you'd just live with it, or you can improve the situation by using more
foldsum rounds:

With 3 foldsums: google --> xOunnC
gogole --> xO-nM5

With 4 foldsums: google --> *p33pl
gogole --> *o7xo9

With 5 foldsums: google --> lYu702
gogole --> QYm?uu

That's not to suggest I believe it's worth doing that many foldsums by
hand to squeeze every last fraction of a bit of entropy out of the name,
I don't. In fact I ran a test program to compare the passwords generated
by the 234,000 English words in my /usr/share/dict/words file and
truncated the passwords to certain lengths in order to compare and count
the collisions (ie. how many words produced the same password). The
results depended slightly on my choice of initial Polybius key square,
of course, but for the example key above, with 8 char passwords and 2
foldsum rounds, there were 25 passwords generated by three different
words, 787 by two different words, and all the other 233288 words
produced unique passwords. The colliding words look like this sample:

Password Words that mapped to that password
-------- ----------------------------------
wbFIad#r megacephalic mesocephalic
DM,brle? appreciatingly appreciatively appreciatorily
gt+4?z9d incondensability indispensability
F@jD&DS1 pharmacomania pharmacopoeia
Jb9n27r$ unbudgeableness untraceableness
=rq!*8hY glucolipine glycolipine
+n7Mt2bt statistically stylistically
a_l-pQ0Y unapostrophized unstroked

Notice that they are all long words, and in fact the hashes do differ,
just not after truncation to 8 chars. The situation improves if I do
more foldsums. For instance, with 3 foldsums those collision stats
become just 71 passwords generated by two different words, and all the
other 234795 words produce a unique password. Even with just 2 foldsums
(which I prefer for speed on paper) it gets better as I do less severe
truncation of the password length. Here is the table of password length
against number of colliding word sets:

Pwd Len Unique Two Three Four Five words
6 227185 3432 244 34 4
7 231237 1699 94 5
8 233288 787 25
9 234042 434 9
10 234717 110
11 234845 46
12 234913 12
13 234919 9
14 234937

So when the password truncation point reaches 14, all 234937 words
produce unique passwords even though many of the words are longer than
14 themselves. Here are the same password collision stats when using 3
foldsums:

Pwd Len Unique Two Three words
6 234263 334 2
7 234677 130
8 234795 71
9 234867 35
10 234901 18
11 234911 13
12 234931 3
13 234933 2
14 234935 1
15 234935 1
16 234937

As you can see, doing 3 foldsums certainly mixes better overall, but it
doesn't get you to a unique password for every input any quicker than 2
foldsums does. In this case it takes 16 char passwords before uniqueness
is achieved, but this may be an artefact of the particular set of
duplicate characters that the example Polybius square happens to have.
Maybe I'm worrying too much, as the performance of the foldsum hash is
already more than good enough for the purpose at hand. What do you
think?

Now on to the next step: Extension of short passwords. This is the step
I need a bit of mathematical insight and help with. As this posting is
already very long I will describe my extension method in the follow up
posting.

--
James Taylor
.

Relevant Pages

  • Re: Question for the math wizards...
    ... string of characters that isn't too long, ... bits per character with base-32 encoding, then we are limited to shipping ... to know if it was possible given m to map m via a function Fto an m' ... In real world terms, say n is 100 digits, m is 50 digits, and I want to ...
    (sci.crypt)
  • Re: Invariant with DIGIT-CHAR-P and the reader.
    ... should appear to the Lisp reader as a number. ... >> reading of the standard makes me believe the Lisp reader should ... > Why a new CL could not accept more forms for unicode digits? ... a..z, characters chosen by the implementation, and not from some higher ...
    (comp.lang.lisp)
  • Re: Calling Bob Phillips - Please
    ... The cell can hold test strings of up to 32k characters. ... cell display. ... Therefore the maximum number of digits ... This works from row 1 to the last row and concatenates values from ...
    (microsoft.public.excel.programming)
  • Re: heard on 40m yesterday at twilight CQ DX DE G2MT EMMA TOCK cq dx in the future
    ... Radio Callsigns. ... "Identification of Stations". ... digits in the cases specified below, may be used to form call signs. ... characters or in certain cases the first character of a call sign constitute ...
    (uk.radio.amateur)