Re: Paper & pencil password algorithm
 From: Maaartin <grajcar1@xxxxxxxxx>
 Date: Fri, 20 Feb 2009 12:50:51 0800 (PST)
I would consider mod 11 again if it can be shown that my mod 10 method
has a fatal flaw.
I'm afraid, nobody does, even in case it's entirelly broken.
The problem is that such an analysis is too much work for somebody
doing it just for fun.
But for the attacker it may be worth it.
This is IMHO the most general problem of cryptography.
I thought you suggested mod 11 originally because it avoided zero
divisors in the multiplication.
Switching from a nelement ring to a (n+1)element field for
multiplication is a good idea 
but not mine, it's used this way in the MARS cipher.
I am doubtful of its value in an
addition process, but I'd be curious to see what you have in mind
anyway.
Even without using the multiplication, a field is much better than a
ring. In base 11 you can do operations like
(c, d) = f(a, b) = (a+b, a+2*b)
which is easy to do (just two additions using d=a+b) and which is a
function given by a
http://en.wikipedia.org/wiki/MDS_matrix
It has the nice property that given any two of the numbers, you can
uniquely compute the others.
This is something you can never do this way in base 10, since it is no
field.
In fact, you can do it in base 10, but it far from obvious
http://buzzard.ups.edu/squares.html
If you were to use something like that you'd need to memorize quite a
large table.
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.
I see, this is a good argument.
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 keyboardaccessible characters to fill the extra space might
be tricky.
It wouldn't be necessary  I found a simple method for getting rid of
the "A":
In case you go for a password of up to 15 characters, you need
normally 30 digits.
Using my method you need 32. At the end there may be some "A" you
don't want.
If there exactly two of them, just drop them. If there are less, drop
the last digit or two.
If there are more, find the largest digit d occurring at most twice,
switch d and "A" and process as above.
The dropping of the two digits means you need to do slightly more
work, but it adds some confusion as well.
How would you convert base 11 digits to base 10 digits with uniform
distribution?
The most direct way would be converting the base 11 represantation in
a base 10 represantation,
but it would be a lot of work.
The method described above is much easier and performs about equally
well.
The resulting distribution can't be exactly uniform, but I think
there's only very slight bias.
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.
I suppose, my method could be used here as follows:
Do it once for the left half (so you get 9 possibilities) and twice
for the right one (leading to 8 possibilities).
Combining them gives you 8*9=72 characters which is about what you
need.
I suppose the bias to be much smaller than when duplicating
characters.
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.
I'm quite sure you'll like my new rounds much better.
They can be used with base 10, but it makes them weaker.
I can't say how much weaker, but I'll show you what I mean.
The "sum" operation is basically the same as the one you suggested with
There's the problem I mentioned already:
It looks like making nice mixing in the forward direction, but it
doesn't do much when computed backward.
See below for my new proposal.
the modification that the first digit in the row is incremented (as if
there were an invisible 1 to its left).
Do whatever you want to the first digit (as long as it stays
bijective)
increment it, let it be, add a secret digit, or use a secret
substitution.
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.
Sure, it's nearly for free, but it doesn't give you much.
The "fold" operation can be visualised as folding the string of digits
in half and interleaving the digits of each half together.
This was one of the rounds I considered recently, but abandoned in
favor of others.
It's like
http://en.wikipedia.org/wiki/Faro_shuffle
but not the same.
In practice, on paper it is simpler just to copy the row of digits into...Exactly this was my way...
I wanted to combine it with a nonlinear substitution as well; both
can be done in one step.
Here are some trivial substitution I considered:
 add 2 to every even digit, leave the odd ones alone.
 multiply every even digit by two, leave the odd ones alone.
 compute the checksum of (2*d), i.e., d<5 ? 2*d : 2*d9
But I'd probably go for a secret substitution.
I wouldn't start with fold. Fold is nice to bring distant digits to
each other, so they can interact.
Mixing digits coming from different character seems to be better but I
don't think it's worth it.
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 problem is, it's entirelly linear.
I would never stand as a hash for computer use.
I think, even I could break it given some thousands or millions
messagehash pairs.
For you use case it might suffice, who knows...
The worst cases are when there is only a
transposition of two letters in the centre of the name:
Some nonlinearity would help a lot.
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.
It's not a problem as such, but it's somehow too much.
Simple estimation for using something like md5 truncated to the same
size:
There're nearly 100**8 = 1e16 possibilities, so there should be no
collisions until about 1e8 words.
Notice that they are all long words, and in fact the hashes do differ,
just not after truncation to 8 chars.
I see.
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?
A cryptographic primitive for computer use is considered broken in
case you find any bias.
It's considered broken even in case you find out there's a probably
working way to find it any faster than by brute force.
The reason is nobody knows what methods come out in a couple of
years...
Your use case in completely different, but I'd try to improve it.
Your Polybius square is quite large but only a very small portion of
it gets used when encoding the message.
This could be a problem.
If you do the hashing the way you described, there's no reason for
using base 11.
I tried to invent some stronger rounds where it matters.
** addSubstAddRight
Use a secret bijective nonlinear substitution table f like this:
0123456789
5781604293
Do whatever you want (but bijectively) to the leftmost digit, then
repeat the following:
In a situation like (x denotes a digit, underscore denotes a blank):
x x x x x x
x x x _ _ _
denote the digits as follows
x x P Q x x
x x p q _ _
Compute q using the formula
q = Q + f(P+2*p)
where all the computation gets performed mod 10.
Reason: The inverse formula is
Q = q  f(P+2*p)
so computing backwards is no easier than forwards.
Consider the following simpler formulae:
1. q = f(P) + Q
Here obviously P has no influence to anything except p and q. it is a
http://en.wikipedia.org/wiki/Finite_impulse_response
function.
2. q = Q + f(p)
Here P propagates to the end (it's a IIR function), but the inverse
function given by
Q = q + f(p)
has obviously a finite response.
3. q = Q + f(P+p)
Here adding 5 to P gives the same results as p grows also by 5. Here
base 11 wouldn't have the problem.
4. q = Q + P+2*p
You need some nonlinearity somewhere,
otherwise the whole mixing can be described by a single matrix making
any attack much easier.
In the linear case, each known messagehash pair gives you some more
linear equations,
and once you'll come to the point where some part of you square can be
computed.
5. q = f(Q+P+2*p)
This is no simpler than what I proposed but has a problem: In the next
step you compute
r = f(R+Q+2*q) = f(R+Q+f(Q+P+2*p))
For most bijective functions f the function Q > Q+f(Q+P+2*p) is not
bijective, so you'd propagate less information.
If you really need to simplify the round, than go for 3; it seems to
me to be the least problem.
An example (computed manually while writing on the computer, so there
may be errors):
Substitution table f as above:
0123456789
5781604293
Let's start with a row and apply the substitution to the leftmost
digit:
1 5 4 8 9 1 4 4 9 0
7 _ _ _ _ _ _ _ _ _
now P=1, p=7, Q=5, q = Q + f(P+2*p) = 5 + f(1+2*7) = 5 + f(5) = 5 + 0
= 5 where everything was modulo 10, so you get
1 5 4 8 9 1 4 4 9 0
7 5 _ _ _ _ _ _ _ _
and continue with P=5, p=5, Q=4, q = Q + f(P+2*p) = 4 + f(5+2*5) = 4 +
f(5) = 4, that's funny but just an accident
1 5 4 8 9 1 4 4 9 0
7 5 4 _ _ _ _ _ _ _
and finally you get
1 5 4 8 9 1 4 4 9 0
7 5 4 6 4 3 6 8 4 2
** addJumpLeft
Do whatever you want (but bijectively) to the rightmost digit, then
repeat the following:
Remember the position the last digit was written, let the digit in the
old and new rows be again P and p, respectivelly.
Compute
n = abs(Pp)
and locate the nth blank from the current position (counting from 0
to n), wrapping over as necessary.
Denote again the digit in the old row by Q and compute
q = Q + p
Alternatives:
1. n = abs(Pp), q = Q + P
Because of n being influenced by both P and p, you get an IIR function
anyway.
2. n = P, q = Q + p
It's simpler and could work maybe even better.
But you'd need to count more (on the average 4.5 instead of 2.85), and
the counting would consume more time.
3. n = p, q = Q + P
About the same as above.
4. n = min(P, p), q = Q + P
Here you'd get n=q with a probability of 50%, that's why I don't like
it.
The same for n = min(P, p), q = Q + p.
5. n = min(P, p), q = Q + max(P, p)
Here you'd restrict the addend to the interval 5..9, that's why I
don't like it.
6. n = min(P, p), q = Q + P + p
This looks fine, but is more work and as above, adding 5 to P gives
the same results.
7. n = abs(Pp), q = Q + P + p
About the same as 6. When using base 11 I'd go for it.
An example: Start with a row and copy the rightmost digit obtaining
7 5 4 6 4 3 6 8 4 2
_ _ _ _ _ _ _ _ _ 2
now is P=2, p=2, n = abs(Pp) = abs(22) = 0, so you skip no blank,
Q=4, q = Q+p = 4+2 = 6
7 5 4 6 4 3 6 8 4 2
_ _ _ _ _ _ _ _ 6 2
now is P=4, p=6, n = abs(Pp) = abs(46) = 2, so you skip two blanks,
Q=3, q = Q+p = 3+6 = 9
7 5 4 6 4 3 6 8 4 2
_ _ _ _ _ 9 _ _ 6 2
You really need a sort of marker for the current position, striking or
underlining used up digits should do.
7 5 4 6 4 3 6 8 4 2
_ _ _ _ _ 9 5 _ 6 2
7 5 4 6 4 3 6 8 4 2
_ _ _ 1 _ 9 5 _ 6 2
7 5 4 6 4 3 6 8 4 2
_ _ 5 1 _ 9 5 _ 6 2
7 5 4 6 4 3 6 8 4 2
2 _ 5 1 _ 9 5 _ 6 2
7 5 4 6 4 3 6 8 4 2
2 7 5 1 _ 9 5 _ 6 2
7 5 4 6 4 3 6 8 4 2
2 7 5 1 _ 9 5 5 6 2
7 5 4 6 4 3 6 8 4 2
2 7 5 1 9 9 5 5 6 2
** addSubstAddRightStep4
This is the same like addSubstAddRight except for the processing
order.
I'd use here a different substitution table f, e.g.,
0123456789
2168703549
I see my example is for addSubstAddLeftStep4, it should go in the
other direction!
You start by putting markers between the digits (so you don't need to
count later) like follows
2 75 1 9 95 5 6 2
_ _ _ _ _ _ _ _ _ 6
2 75 1 9 95 5 6 2
_ _ _ _ _ 6 _ _ _ 6
2 75 1 9 95 5 6 2
_ 8 _ _ _ 6 _ _ _ 6
when you reach the end you simply wrap around to the rightmost blank
2 75 1 9 95 5 6 2
_ 8 _ _ _ 6 _ _ 2 6
2 75 1 9 95 5 6 2
_ 8 _ _ 2 6 _ _ 2 6
2 75 1 9 95 5 6 2
8 8 _ _ 2 6 _ _ 2 6
2 75 1 9 95 5 6 2
8 8 _ _ 2 6 _ 9 2 6
2 75 1 9 95 5 6 2
8 8 _ 9 2 6 _ 9 2 6
and again
2 75 1 9 95 5 6 2
8 8 _ 9 2 6 4 9 2 6
2 75 1 9 95 5 6 2
8 8 3 9 2 6 4 9 2 6
** The whole mixing
I'd go for the three rounds in the order described.
The initial addSubstAddRight gets the first secret permutation in game
and makes some nice mixing in a regular way and makes the rightmost
digit depend on the whole row,
the following addJumpLeft makes a quite chaotic transformation,
and the final addSubstAddRightStep4 gets the second secret permutation
in game and makes some more mixing.
Maybe addJumpLeft, addSubstAddRight, and addJumpLeft again could be
easier and/or better.
I've never implemented it, I know nothing (yet) about what it really
does.
.
 References:
 Paper & pencil password algorithm
 From: James Taylor
 Re: Paper & pencil password algorithm
 From: James Taylor
 Re: Paper & pencil password algorithm
 From: James Taylor
 Re: Paper & pencil password algorithm
 From: James Taylor
 Re: Paper & pencil password algorithm
 From: James Taylor
 Re: Paper & pencil password algorithm
 From: James Taylor
 Re: Paper & pencil password algorithm
 From: Maaartin
 Re: Paper & pencil password algorithm
 From: James Taylor
 Paper & pencil password algorithm
 Prev by Date: Re: RSA question
 Next by Date: Re: Paper & pencil password algorithm
 Previous by thread: Re: Paper & pencil password algorithm
 Next by thread: Re: Paper & pencil password algorithm
 Index(es):
Relevant Pages
