Re: Paper & pencil password algorithm

Maaartin <grajcar1@xxxxxxxxx> wrote:

I didn't answer everything, but the posting is very long anyway.

It is strange that your posting does not appear as a followup to the
correct previous message in my newsreader. Instead it appears as a
follow up to a much older message which has long since expired and been
flushed from my news spool.

James Taylor wrote:

I think a permutation matrix
might be simply lots of zeros with a 1 once in each row, but it's
trickier to imagine a matrix that performs an ordered accumulative sum
of the digits with an additional one added in on the leftmost digit.

What about
1 0 0 0
1 1 0 0
1 1 1 0
1 1 1 1
for sum of 4 elements

That looks like it sums the digits correctly, but how do you add the
extra 1 at the beginning of the row? Maybe adding that extra 1 was a
cleverer decision than I first imagined. Maybe there is no matrix for
adding the extra 1. Maybe it is sufficient to defeat this linear
algebraic approach.

and something like
1 0 0 0
0 0 1 0
0 0 0 1
0 1 0 0
for fold and their product for foldsum?

Yes, if you can get the first matrix to add the extra 1, then
multiplying the two would give you foldsum as a matrix. I would be
interested to see that.

How would data dependent
permutation work? Could that be as simple as changing the start point
of the fold depending on the odd/even-ness of the first digit?

Yes, but than you have just a single non-lienar operation there.

One non-linear step is enough isn't it? We only want to defeat simple
use of linear algebra to crack the key. We're only trying to defeat
criminals and malicious work colleagues, not the NSA.

Would that be sufficient, when combined with the summing pass, to be
non-linear?

A single non-linear operation makes it all non-linear, but when
analyzing it, you habe only a single obstacle there. The more
obstacles, the better.

Moreover, in this case, there're only two possibilities, so at worst
the attacker needs to do twice as much work.

Yes, I see. So really we want something that applies differently to each
digit. Changing the fold in such a simple way is too simple. We need the
fold (or something like it) for the mixing to work well, so perhaps we
should be looking at improving the sum instead. (See below.)

Your operation has a small disadvantage: it's not bijective, since
"12" and "21" both lead to "12".
You loose a single bit per round, this is probably no problem as
you're not going to make many of them.

You could take the deciding parity bit from somewhere else (eg. the
middle of the string, or the sum of the two middle digits).
Alternatively, with the decider being the first digit, you could reverse
the fold so that the middle of the string ends up on the left and the
ends are folded together on the right. It's not so neat though.

But I'd rather try something like this:
Take one secret digit, let's say 1, an odd number, so write the first
two digits swapped as follows:
12345678
2......1 here 2 is an even number so make no swap
23....41 here 3 is an odd number so make a swap
235..641 here 5 is an odd number so make a swap
23597641 done
Obviously, this is bijective. It never does a fold but something quite
similar.

Maaartin, you've done it again! I like it. It's a nice simple way of
modifying the permutation based on the data. I just love brainstorming
with you. My ideas dry up when there's nobody to bounce ideas off. :-)

Of course, we need to give some thought to the ramifications of this
particular permutation, such as whether the mixing it does has any
degenerate cases. Perhaps I should write a program to test the
statistical distribution of odd and even numbers for instance. You see,
the reason I chose the original "fold" permutation was because it was
guaranteed to split the digits apart from each other and it also moved
the digits at the right end (that had been most affected by the sum of
the preceding digits) to the left end where they are most able to affect
the other digits, so it maximised the mixing feedback.

With the permutation you've just described, the digits at the right end
get moved to the middle where they are less able to affect the digits to
the left. And the digits at the very left end of the result have all
come from near the left end of the previous row. Also, on a purely
practical level when doing this on paper, it might be difficult to work
from the outside inwards because you may misjudge the space and run out
of space making a mess of the calculation. Maybe you can think of a way
to improve this permutation to fix those things.

Writing a single symbol each time would be probably better.

Yes, and writing them left to right would be easier. Okay, so what do
you think of the following idea? It attempts to be nearly the same
ordering as "fold":

First take the digit from the right end and cross it out:

012345678-
9.........

If that digit is odd, then take the 1st digit from the other end:

-12345678-
90........

If that digit is even, take the 2nd (unused) digit from the other end:

-123456-8-
907.......

The 7 is odd, so take the 1st digit from the other end:

--23456-8-
9071......

1 is odd, so take the 1st digit from the right:

--23456---
90718.....

8 is even, so take 2nd from left:

--2-456---
907183....

3 is odd, so 1st from right:

--2-45----
9071836...

even, so 2nd from left:

--2--5----
90718364..

even, so 2nd from right:

-----5----
907183642.

even, so 2nd from left, but there is only one remaining so take that and
we've finished:

----------
9071836425

We started picking from the right (which ensures that the rightmost
digit always ends up becoming the leftmost), and then we just alternated
left, right, left, right, etc. Each time we picked the first or second
digit based on the parity of the previously picked digit. The parity of
*every* digit (except the last one) is involved in controlling the
permutation. I'm not sure if that's better or worse than your
permutation that is only dependent on half of the digits.

Of course, this will also need some testing before I trust it to permute
in a way that distributes the odd and even numbers without bias. What do
you think?

In any case, such substitutions don't seem to add much in the way of
diffusion/mixing, while adding a fair bit of cognitive load.

It depends on the art of the substitution. If it's secret, then it's
another part of the key.
If you do something like "add two to every odd digit", then it's quite
simple.

I like that idea. Could that be used during the "sum" pass to make it
non-linear? Maybe that's not sufficient. It's certainly reversible
because you just subtract 2 from each odd number when working in
reverse. But does reversibility imply linearity?

If we could find such a simple way to make the sum non-linear, that
would be fantastic! I might even be inclined to keep the nice quick and
simple original "fold" rather than the data-dependent permutations we
discussed above (which require rather more work and are slower) *if* the
sum could be made non-linear in such an easy manner.

Hmmm, lets try some examples. I'm going to add 2 to even numbers (not
odd) because my brain finds it easier. On the left is the new sum with
evens+2, and on the right is the original "sum" for comparison:

36856312 36856312
64495013 40839235

Hmmm, lets continue applying the sum with evens+2 to that result
repeatedly and see if it looks good:

64495013
71561147
01867063
14429950
40609055
55112496
83679342
94290379
28211634
31367384
67207228

Looks good so far, and feels fairly easy. If you can tell me it's
non-linear, then this is definitely a good modification to the sum pass.
It would certainly be much easier to get the non-linearity this way than
by the permutation method. Is this evens+2 sum non-linear?

So it seems, even with the additional restriction of a and b both having
to be single digit integer values, there was not enough information in
the two equations given to establish beyond doubt the value of a and b.

Yes, but something like this can only happen because of 10 being no
prime.

Ah, so base 10 has some advantages over prime bases then! ;-)

The exact convention you choose to use would vary between each
individual using this password system, so an attacker would be unlikely
to guess it with 100% accuracy.

Yes but still, he can think out some tens of hundreds possibilities
and try them out.

But for every possibility he has to run all the same cryptanalysis
hoping to crack the key, then try the next possible naming convention
and run all the same cryptanalysis again, etc, etc. Each and every
possible minor difference in the naming convention adds hugely to the
search space. It is not a quick matter to check every possible
convention that the user could be using.

I wouldn't want secrecy of the algorithm to be necessary for it to be
secure enough for the purpose.

I understand. It would be nice to share it in case somebody would
analyze it and expose its weaknesses or improve it or just show it
works fine.

That would be nice too, but actually I would be happy if I could simply
help people improve their passwords, and thus their security.

Keeping a computer algorithm secret is stupid (most of the time) as
there'll be always somebody disassembling it, so you can't really do
it.
But keeping a hand algorithm secret is doable and than it's just like
password but much easier to remember and much harder to crack.
And even if a had an wonderful hand algoritm which takes just two
minutes and is secure enough, I could probably save one minute by
using a secret one.

I understand all that, and agree with it. I might even keep some minor
details of my personal algorithm secret. However, my primary goal here
is to find an algorithm that will be useful for everyone, not just me.

I think about doing all the work using symbols instead of digits.

Well, the nice thing about the Polybius square translating each
character to two digits is that you get some "fractionation" for free.
Digits are also slightly easier and quicker to manipulate
mathematically, of course. So, what is the advantage of moving to a
character based system?

First, I'd encode the message using some constrained character sets:
1. Either 25 or 35 symbols arranged in a 5x5 square or 7x5 rectangle,
respectivelly.
2. Or any odd number of symbols arranged in line.

The encoding would be quite trivial in all cases, something like

ABCDEFGHIJKLMNOPQRSTUVWXY
abcdefghijklmnopqrstuvwxy
0123456789Zz+-/*=!?.,;:<>

ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789
abcdefghijklmnopqrstuvwxyz0-/.:!?<>

could encode a set of 75 or 70 symbols (containing everything you
need) in just 25 or 35 symbols, repectivelly.

I don't see how you use it. Please give an example.

For uniqueness you'd need to use somehow the row of the original
symbol as well, but this can be handled.
The whole hashing would be done using the small symbol set instead of
digits.
The transformation of the computed hash to pasword would somehow map a
character from this symbol set to a character from the larger set.

Sure, we can work out the "somehow" later. After all we need to solve
the issue of how the password length extension mechanism works without
leaking information about the key.

The computation is the more complicated part, so here's the idea:

Ad 1: Use the rectangle for operations like in
http://en.wikipedia.org/wiki/Playfair_cipher
http://www.pbs.org/wgbh/nova/decoding/doubplayfair.html

Ok.

http://www.pbs.org/wgbh/nova/decoding/doubtrans.html

Ah, but that's used very differently to the Playfair square.

or others - I think I could do better (to be described another time).
For this to work well it's important that both sizes are odd numbers.

Sorry, I'm confused. Both sizes of what?

Ad 2: You could use something like
http://en.wikipedia.org/wiki/Slide_rule
but with a linear scale and with symbols instead of digits.
As you need nearly no precission, tho pieces of paper would suffice.
Just write something like
PRIL?S?Z?UTOCKYNEDABHQWFXJMVG
on the bottom of one of them and something like
PCHNA??W?TELODZJUBSMKRYFIGQXV
anywhere on the other.

I'm still not sure where you are going with this. Is the above for
making a substitution cipher by aligning one of those rows with the
other? What do the question marks mean?

In one step you can compute an expression similar to x+y-z but
containing some substitutions (details another time).

I'm totally lost now. How do we calculate x+y-z when we are dealing with
characters instead of digits?

Well, I spent several hours on it, encouraged by spotting that the 11th
char is always one after the 1st char.

So much?

Yes, when you said you thought I could crack it, I believed you. I
thought if I didn't crack it easily there must be something wrong with
me. I just didn't look in the right place for the pattern. I spent too
long looking for more complicated mathematical relationships between the
characters as they appear in order, and I didn't look for the characters
being picked in a different order. Silly me. I guess it's just lack of
experience.

Please explain how it works.

for (int n=0; n<20; ++n) {
char[] a = new char[20];
for (int i=0; i<10; ++i)
a[i] = symbols.charAt(random.nextInt(symbols.length()));
for (int i=0; i<10; ++i) {
char c0 = a[((2*i + (i<5?0:1)) % 10)];
int pos0 = 0;
while (symbols.charAt(pos0) != c0) ++pos0;
a[10+i] = symbols.charAt((pos0+1) % symbols.length());
}
System.out.println(a);
}

Ah, yes I see it now. Thanks.

By the way, which programming language is that?

Yes, that's a possibility, although I really quite like the digits
because (in base 10 anyway) they are easy to manipulate

Yes, I see. But you see why I don't like base 10 for this. And I see
why you don't like base 11.
So maybe we agree upon using bases 5 and possibly 7 (for the
rectangle) or 29 (my prefered choice for the slide rule).

I think I need a clear example of how these ideas work, then I can give
you more feedback.

Now, unfortunately I have to go away from home for a week. I won't have
Usenet access (for posting) in the next week, but I will check this
thread on Google Groups and give thought to anything I read there until
I return home.

Thanks for your time and help with this. I think we have some
encouraging new ideas. I can't wait to hear what you think of mine.

--
James Taylor
.

Relevant Pages

  • Re: Even numbered 3 dis that go through a city but the parent doesnt
    ... I recall reading a description of the logic of 3di numbering that explained that even ones are supposed to bypass something while odd ones are supposed to go to something. ... The hundreds digit implies a loop that will return to the base highway, but in actual practice seems to mean "will return to some Interstate. ...
    (misc.transport.road)
  • Re: Paper & pencil password algorithm
    ... of the digits with an additional one added in on the leftmost digit. ... Take one secret digit, let's say 1, an odd number, so write the first ... Multiplying each digit by a constant is linear as well (just think ... I'd encode the message using some constrained character sets: ...
    (sci.crypt)
  • Re: Enigma 1656 - Five integers
    ... The sum of the five integers is divisible by ... However the second digit can't be a 2. ... following three digits have to be odd, even, even to maintain an odd sum for ...
    (rec.puzzles)
  • Re: Enigma 1405 - Digitally divided
    ... It's a better approach than I used, but there are a few slips 'tween ... {odd, odd, odd, 8} ... Therefore it cannot co-exist with an even digit, meaning is out. ... All 6 permutations of 5 work, as shown in list 3. ...
    (rec.puzzles)
  • Re: maximum number of code words
    ... > When you choose a codeword of length n, you can imagine choosing the ... > first n-1 bits, where there are 2 choices for each position. ... > 1 choice for the final digit, or two choices, depending on what ... I think I was thrown somewhat by the even number of 0's versus odd ...
    (sci.math)