# Re: Paper & pencil password algorithm

I don't have the time to answer it all, so try yourself.

I REALLY WONDER WHY ALL THE PEOPLE HERE PREFER FACTORING OF 17 AND
GROUP NPD THERAPY TO ANSWERING THIS.

Ok, got that, but what suffices to make something non-linear? Does it
necessarily have to involve multiplication and not simply addition?

Sure, addition alone is linear. Even multiplication alone is (a kind
of) linear (in a different group). Smart combining operation from
different groups is the key to strength.

Or even multiplication insufficient? Does it have to involve polynomials of high order?

Not at all. Can you solve
a + b + 2*c = 9
a + b + c = 6
5*a + b + c = 10
? Could you do it with hundreds of variables?

a + b + c*c = 7
a + b*b + c = 8
a*a + 2*b + c = 9
? What about hundreds of variables?

Which steps in my algorithm would need to be non-linear:
1. Name -> digits (currently using Polybius square)
2. Hashing the digits (currently "foldsum")
3. Extending the digits (currently LFG)
4. Digits to password (Polybius square)

The more the better. But 1 and 4 are functions from one set to another
so speaking about non-linearity doesn't make sense at first glance.
But think a litlle longer and you'll see they're already non-linear
(except in case of bad Polybius squares).

Have a look at
There're 10 or 14 rounds, each of them containing one non-linear step
and some linear mixing. The details are complicated but you can
quickly get some idea.

Have also a look at
http://en.wikipedia.org/wiki/Salsa20
There're some simple operation combined many times. Both add and xor
are the fastest possible operations, using only one of them would make
the cipher very weak.

Is it sufficient for just one of the steps to be non-linear?

It depends on the strength required. There's nothing like a formula
for this.

Hmmm, I still feel a bit lost.

I see.

So, perhaps we can hide the state of the Lagged Fibonacci Generator
(LFG) by running it in a separate parallel set of digits instead of
running it inline.

That's about the same, at least at first glance.

It occurs to me that if we continue beyond the end of the LFG row until
we run out of LFG digits, and discard the initial hash at the beginning,
we will have the 40 digits we wanted without any disclosure of the hash

Without any OBVIOUS disclosure.

This parallel LFG method is certainly more time consuming because it's
two long sequences of digit sums rather than just one, but that's still
better than four rows of 40 digit foldsum hashing. The question is
whether parallel LFG is worthwhile in terms of the security improvement
over the single LFG? Does it qualify as a non-linear operation?

Is there a system of linear equations the result obeys?

One thing I like is that the LFG initiating keyword can be carefully
chosen up front to produce good long sequences independently of any
individual name being processed. You don't need to be able to identify
and fix poor cycles each time you run the algorithm on a name, you can
stick to the same LFG you know works.

Right.

My concern is that using the same LFG each time may itself be an
information leak. What do you think?

Yes, it is.

Do we now have a password length
extension function that doesn't give away information about the Polybius
key? Or the LFG initialising keyword for that matter?

Yes, using MD5 should be just fine.:D
But I see nothing suitable and doable by hand here.

On the contrary, I think we have already considered combinations of
techniques that together fall in the sweet spot between secure enough
and fast enough. We're just exploring where the best balance between
these is.

I don't think so. Once you'll see how using only linear operations
makes it weak, you'll see you need to do more work.

I think the parallel LFG is less work than longer input into the hashing
step, don't you agree?

Yes. But I also think that using a extension function means - for the
same overall security level - much more work than making a longer
hash.

I'm very sorry, but I don't yet understand this maths. Maybe you can
break it down for me if you think I'd benefit from a better
understanding. Thanks.

Somebody others should do. You'd better make another topic of this.

I can't say, but the following should suffice: The whole Polybius
square has less than 525 bits.
Wow! That many? How do you calculate this?

Just trivially. Can you count the possibilities?