Re: Paper & pencil password algorithm

Maaartin <grajcar1@xxxxxxxxx> wrote:

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

Interpersonal friction has a tendency to be far more motivating than
straight discussion of technical topics and, like sand castles, it's
easier to pull apart someone else's work than it is to help build
something. It is clear to me that the other threads are of that type.
It's a shame because I think some of the participants have sufficient
knowledge to help us in this thread but instead they waste precious
hours of their lives arguing. Such is human nature.

James Taylor wrote:
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).

Really? This non-linear quality must be something a bit deeper than I
thought. That's fascinating, I wish I could see how that linear
multiplication works. Seeing that might help me understand the essential
property required for non-linearity.

Smart combining operation from different groups is the key to strength.

Ah, ok. But then why isn't the combination of fold and sum sufficient?
Are they not different operations? What kind of smart combining do I
need?

Does it have to involve polynomials of high order?

Not at all. Can you solve
a + b + 2*c = 9 [A]
a + b + c = 6 [B]
5*a + b + c = 10 [C]

It's been a long time since I studied maths, but I'll give it a try. My
approach would be to use each equation to substitute for a variable in
the next equation like so:

Rearranging [A]: a = 9 - b - 2*c [D]
Substituting [D] in [B]: (9 - b - 2*c) + b + c = 6
=> 9 - c = 6 => c = -3 [F]
Substituting [D] and [F] in [C]:
5*(9-b-2*(-3)) + b + (-3) = 10
=> 45 - 5*b + 6 + b -3 = 10
=> -4*b +48 = 10
=> b = -(10 - 48)/4
=> b = 38/4 = 19/2 = 9.5 [G]
Substituting [F] and [G]in [D]:
a = 9 - 9.5 - 2*(-3) = 5.5

Hmmm, I feel that that was easier than it would be in the general case.

? Could you do it with hundreds of variables?

Unlikely. Not without making a mistake. A computer could though.

Now what about
a + b + c*c = 7
a + b*b + c = 8
a*a + 2*b + c = 9

Let me try a similar approach:
a = 8 - b^2 - c
b = 7 - a - c^2
b = 7 - (8 - b^2 - c) - c^2
b = 7 - 8 + b^2 + c - c^2
c^2 - c + 1 = b^2 - b
a = 8 - (7 - a - c^2)^2 - c
a = 8 - (49 - 7*a - 7*c^2 - 7*a + a^2 + a*c^2 - 7*c^2 + a*c^2 + c^4) - c
a = 8 - (49 - 7*a - 7*a + a^2 - 7*c^2 - 7*c^2 + a*c^2 + a*c^2 + c^4) - c
a = 8 - 49 + 7*a + 7*a - a^2 + 7*c^2 + 7*c^2 - a*c^2 - a*c^2 - c^4 - c
a = -41 + 14*a - a^2 + 14*c^2 - 2*a*c^2 - c^4 - c

I'm stuck. No it's worse than that, I'm lost and I have no idea what I'm
supposed to be doing. It seems intractable but that's probably just my
inexperience. I'm sure a better mathematician could solve it.

? What about hundreds of variables?

I cannot judge, because I didn't manage to solve just three, let alone
hundreds. Whatever the correct approach is, my guess is that it would be
very complex to do by hand and would certainly need to be done on a
computer. I notice that the substitution technique I tried resulted in
higher and higher powers being generated on each substitution. I'm not
sure whether high powers are solvable in general, but maybe they can be
avoided by using a different method altogether.

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

Reading statements like that makes me think there's something about this
linearity concept I still don't get. In what sense is a mapping from one
set of things to another set of a different type be said to be linear or
not?

Have a look at
http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
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.

Yes, complicated. I note that the "S-box" is described as being
non-linear, but that the MixColumns step is not. There is some talk of
reversibility of these operations, but reversibility does not seem to be
the same thing as linearity. This makes me wonder, because my password
algorithm does not need to be reversible, whether there may be a simple
way for me to avoid a linear algebraic cryptanalysis.

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.

So if add is linear, xor must be the non-linear operation, right? If
both add and xor are linear, perhaps the necessary non-linearity comes
from Salsa20's constant distance rotations? No, none of those components
sound to me like they would qualify as non-linear (although I'm still
lacking the essential insight to judge this accurately). If linear
operations can be combined to produce a non-linear output, then maybe it
is in the method of combining that the non-linearity arises.

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.

Surely not! The relationships between digits in the sequence, which
might have been detectable when the sequence was used directly in the
output password, are now not detectable because they are used only to
modify the hash repeatedly. As the hash itself doesn't appear at the
start, no deduction can be made about... Oh wait! After the length of
the hash has been modified, this method then modifies the digits already
output, so then it is possible to deduce the digits of the LFG stream,
and thus both the LFG sequence and the initiating hash can be
discovered. Damn. :-(

Without any OBVIOUS disclosure.

Actually, WITH obvious disclosure.

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?

Clearly not. I must think of something better and also quicker to
perform than the parallel LFG. I was finding that it took around 6
minutes (instead of 4 minutes for the direct LFG method). I might have
been able to do it quicker with practise, but this is clearly too much
work, and for so little extra benefit.

Does it qualify as a non-linear operation?

Is there a system of linear equations the result obeys?

Isn't that nearly the same question? I feel even less able to answer
your question than mine.

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

Yes, it is.

Then some way to change the starting point of a known good LFG, would
seem like a good plan. The problem is, how do you move the starting
point of an LFG to some random point in a million-long sequence without
having to do all the intermediate steps?

I recall reading that Salsa20's random number generator could be quickly
started at any point. I wonder if something similar could be arranged
for this. When my current workload lifts, I shall have to do some more
investigation along these lines.

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 have to keep reminding myself not to get too carried away with making
this system uncrackable. For most of the threats I mentioned (spyware,
phishing, keyloggers, crooked site admins, etc) the collector of
passwords will not know there is an algorithmic relationship and, even
if they did, they would not know the exact naming scheme used, so they
wouldn't have accurate plaintext names to go with each cipher password.
Furthermore, they wouldn't be motivated to crack the algorithm because
the victim is just one of many thousands of others using much worse
passwords and reusing them on lots of sites.

The only threat I think requires this system to be secure is the
possibility of a targeted attack, such as a malicious work colleague
with whom I previously shared the algorithm and who has the ability to
collect my passwords. Nothing else comes immediately to mind. There may
be other types of targeted attack that might be more likely if I were a
multi-millionare, dissident, terrorist, or a spy, but I can safely rule
those out for this lifetime. ;-)

My conclusion, therefore, is that if any of my work colleagues turn
malicious, I ought to be very vigilant how I enter passwords, and ensure
that my personal home accounts are all based on a different key to my
work related accounts (a precaution I would adopt anyway).

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.

Hmmm, I am starting to see your point. However, I already know that two
rounds of foldsum hashing on a 40 digit (20 char) input is too much. It
takes too long and you need a big piece of paper! Extending a short hash
is much quicker and as long as my method of extension does not reveal
information about my key, I'll be happy with it.

Remember that the key and hash should be sufficient to make the password
unpredictable to someone who has seen only a handful of passwords, so
the purpose of the extension is only to beat rainbow tables and blind
brute-force. The extension doesn't need to be terribly secure in itself.
So, if we can find no better extension mechanism, I'll just add a fixed
suffix to the password, or repeat the password to the required length.
At least that doesn't give anything at all away about the key, and they
still have to crack the key to be able to have the rest of my passwords.

Of course, such simple extensions will be obvious to a password thief so
it would reduce the search space for brute-forcing other passwords. I'd
prefer something less obvious but which doesn't leak information about
the key.

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?

Well now, let's see. There's one, two, three.... ;-)

The naive approach is to say 100 factorial, however there are some
duplicate characters, and I structured my Polybius square into a subset
of 8x8 containing the characters needed for converting name to digits,
and an outer box containing some duplicate characters and some new ones
chosen from around 30 punctuation chars in ASCII. There are 64 chars in
the 8x8 square, and 36 in the outer box. Thus I'd say it should be 64! *
36! * ((64+30) choose 36). Right?

I worked that out to be about 5.87e156. Is that what you got?

Now I think we need to know what power of 2 will give us a number like
that. I think you can use logs for this: log(5.87e156)/log(2) = 520.
That's pretty close to what you got, so I must have done it roughly
correctly.

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

Yeah right! I'm not sure I could. I think my approach would be to
catalogue all the sequences that occur when the LFG is running on the
different sized initial states. I think doing that would bring great
insight into the nature of LFGs anyway. Then I'd look to see if there
are any useful cribs in the patterns of digits (importantly the pairs of
digits) and I'd look for similar patterns appearing in the extension
part of extended passwords. However, I'm pretty sure I'd get nowhere
with this approach without some sophisticated statistical analysis that
I do not posses among my skills.

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

I share that belief. It may look nothing like what we currently have
though. It may all be doable in a single step based on a two dimensional
representation of the hashing process that doubles up as the
pseudo-random generator.

but be prepared for your girlfriend beating you before you're done
with its description.

Sounds kinky! Do you really think it would turn her on that much?
Let's hurry to finish this! ;-)

--
James Taylor
.

Relevant Pages

  • Re: Paper & pencil password algorithm
    ... Composition of linear is linear. ... Name -> digits ... Extending the digits (currently LFG) ... For example, if the hash result is something short like 1234, the ...
    (sci.crypt)
  • Re: Paper & pencil password algorithm
    ... additions and simplified using linear algebra. ... The relationships between digits in the sequence, ... output, so then it is possible to deduce the digits of the LFG stream, ... nicely paired with passwords. ...
    (sci.crypt)
  • Re: Paper & pencil password algorithm
    ... Sure, addition alone is linear. ... each of them containing one non-linear step ... we run out of LFG digits, and discard the initial hash at the beginning, ...
    (sci.crypt)
  • Re: Paper & pencil password algorithm
    ... Sure, addition alone is linear. ... Name -> digits ... Extending the digits (currently LFG) ... each of them containing one non-linear step ...
    (sci.crypt)