# 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 n-element 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 keyboard-accessible 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 non-linear 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*d-9

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

message-hash 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 non-linearity 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 non-linear 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 non-linearity somewhere,

otherwise the whole mixing can be described by a single matrix making

any attack much easier.

In the linear case, each known message-hash 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(P-p)

and locate the n-th 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(P-p), 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(P-p), 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(P-p) = abs(2-2) = 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(P-p) = abs(4-6) = 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 7|5 1 9 9|5 5 6 2

_ _ _ _ _ _ _ _ _ 6

2 7|5 1 9 9|5 5 6 2

_ _ _ _ _ 6 _ _ _ 6

2 7|5 1 9 9|5 5 6 2

_ 8 _ _ _ 6 _ _ _ 6

when you reach the end you simply wrap around to the rightmost blank

2 7|5 1 9 9|5 5 6 2

_ 8 _ _ _ 6 _ _ 2 6

2 7|5 1 9 9|5 5 6 2

_ 8 _ _ 2 6 _ _ 2 6

2 7|5 1 9 9|5 5 6 2

8 8 _ _ 2 6 _ _ 2 6

2 7|5 1 9 9|5 5 6 2

8 8 _ _ 2 6 _ 9 2 6

2 7|5 1 9 9|5 5 6 2

8 8 _ 9 2 6 _ 9 2 6

and again

2 7|5 1 9 9|5 5 6 2

8 8 _ 9 2 6 4 9 2 6

2 7|5 1 9 9|5 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

- 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):