# Re: Paper & pencil password algorithm

*From*: Maaartin <grajcar1@xxxxxxxxx>*Date*: Wed, 25 Feb 2009 10:37:10 -0800 (PST)

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?

Now what about

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

http://en.wikipedia.org/wiki/Advanced_Encryption_Standard#High-level_description_of_the_algorithm

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 PolybiusWow! That many? How do you calculate this?

square has less than 525 bits.

Just trivially. Can you count the possibilities?

Try to break your original LFG idea. This will help you more than

asking and reading.

I think there's an algorithm doable in five minutes and secure enough,

but be prepared for your girlfriend beating you before you're done

with its description.

.

**Follow-Ups**:**Re: Paper & pencil password algorithm***From:*James Taylor

**Re: Paper & pencil password algorithm***From:*WTShaw

**Re: Paper & pencil password algorithm***From:*Kristian Gjøsteen

**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:*Maaartin

**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

**Re: Paper & pencil password algorithm***From:*Maaartin

**Re: Paper & pencil password algorithm***From:*James Taylor

- Prev by Date:
**Re: Secret sharing algorithm with chosen keys** - 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):