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 nonlinear? 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 nonlinear:
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 nonlinearity doesn't make sense at first glance.
But think a litlle longer and you'll see they're already nonlinear
(except in case of bad Polybius squares).
Have a look at
http://en.wikipedia.org/wiki/Advanced_Encryption_Standard#Highlevel_description_of_the_algorithm
There're 10 or 14 rounds, each of them containing one nonlinear 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 nonlinear?
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 nonlinear 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.
.
 FollowUps:
 Re: Paper & pencil password algorithm
 From: James Taylor
 Re: Paper & pencil password algorithm
 From: WTShaw
 Re: Paper & pencil password algorithm
 From: Kristian Gjøsteen
 Re: Paper & pencil password algorithm
 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
 Paper & pencil password algorithm
 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):
Relevant Pages
