Re: Paper & pencil password algorithm
- From: Maaartin <grajcar1@xxxxxxxxx>
- Date: Sat, 7 Mar 2009 10:46:10 -0800 (PST)
I didn't answer everything, but the posting is very long anyway.
Oh, I guess that proves your point that theRight.
multiplications, in this particular case, can be solved as a set of
linear equations.
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 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?
How would data dependentYes, but than you have just a single non-lienar operation there.
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?
Would that be sufficient, when combined with the summing pass, to beA single non-linear operation makes it all non-linear, but when
non-linear?
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.
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.
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 2 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.
Writing a sinle symbol each time would be probably better.
Presumably a non-linear substitution would be any substitution thatMultiplying each digit by a constant is linear as well (just think
couldn't be represented by adding a constant to each digit.
about the system of equations).
Multiplying each digit by a constant and adding another constant is
linear, too.
but this:Yes.
0123456789
5061728394
would not be linear. Am I right?
In any case, such substitutions don't seem to add much in the way ofIt depends on the art of the substitution. If it's secret, than it's
diffusion/mixing, while adding a fair bit of cognitive load.
another part of the key.
If you do something like "add two to every odd digit", than it's quite
simple.
I therefore prefer the permutation technique.You could do both, it'd be better but take more time.
It seems that we need two more equations in order to fix the two extraYou don't. Surelly you get infinitelly many solutions, here even when
unknown non-negative integers x and y.
constrained to the integers.
But taken modulo 10 a unique solutions may arise.
What about this
3*a + 5*b = 3 (1)
2*a + 8*b = 8 (2)
6*a + 10*b = 6 (3) = 2*(1)
6*a = 6 (4) = (3) mod 10
2*a = 2 (5) = 2*(4) mod 10
a=1 or a=6 (6), you can't do better sind 2 is a factor of 10
5*b = 0 or 5*b = 5 (7) by substituting (6) in (1), seems to be
completelly useless
8*b = 6 or 8*b = 6 (8) by substituting (6) in (2) mod 10
8*b = 6 (9) trivial
2*b = 4 (10) = 4*(9) mod 10
b=2 or b=7 (11), again, you can't do better sind 2 is a
factor of 10
a=1 and b=2 or a=6 and b=7 by recalling (6); (6) isn't useless when
considering both cases separatelly
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.
Of cause there may be linear dependent equations.
Doing the same mod 11 leads immediatelly to a single solution:
3*a + 5*b = 3 (1)
2*a + 8*b = 8 (2)
0*a + 14*b = 18 (3) = 3*(2) - 2*(1)
3*b = 7 (4) = (3) mod 11
b = 6 (5) = 4*(3) mod 11
3*a + 30 = 3 (6) by substitution into (1)
3*a = 6 (7) = (6) mod 11
a = 2 (8) = 4*(7) mod 11
After I did it, I see, I should have used Gaussian elimination
instead. This means about the same amount of work, but is much more
systematic.
What is the lesson you wanted me to learn from this?Maybe something like that's quite easy to make such a system and solve
it.
The unknowns are the digits assigned to the characters in your square.
While there may be not enough equations for uniquely determining the
solution,
simple relations may occur greatly reducing the search space.
They are just one set of symbols mapped to another. There is no inherent
ordering in the symbols unless you choose to impose one, and no
relationship between the symbols until you define it. They're just
symbols.
You're 100% right. But when you consider using some simple symbol
substitutions (as I did),
than it starts making sense. Surely, I'd need to be more precise and
give a sort of definition for this.
Nice.(a + b) ^ (c + a)No simplification possible.
Ok, I think you made the point.
The exact convention you choose to use would vary between eachYes but still, he can think out some tens of hundreds possibilities
individual using this password system, so an attacker would be unlikely
to guess it with 100% accuracy.
and try them out.
And in many cases there's a single obvious possibility like
"google" (I've only one account)
"amazon" (I've no account, but if I had, it'd be just one)
"nic.us" (If I had to do with one "nic" I'd be prepared to deal with
more of them)
"somesite:1", "somesite:2" (there's a site where I have two accounts
differing by a digit; sure I could use a different separator here)
I wouldn't want secrecy of the algorithm to be necessary for it to beI understand. It would be nice to share it in case somebody would
secure enough for the purpose.
analyze it and expose its weaknesses or improve it or just show it
works fine.
But I'm afraid nobody will, so you nothing except for a good feeling.
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.
But (as already said) I understand your goal.
I don't recall it anymore but it must have been something different.But than maybe one foldsum round could be more secure.Are you suggesting that I could append the result of a third foldsum
round to the output of the second round to make a password twice as
long?
Maybe I was thinking about using a single (maybe more complicated)
round for a longer input, so you wouldn't need to extend the hash.
Wouldn't that also reveal too much about my key?It surely would since there not enough mixing in between.
I love that idea. It's the best idea so far.
I think about doing all the work using symbols instead of digits.
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.
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.
The computation is the more complicated part, so here 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
http://www.pbs.org/wgbh/nova/decoding/doubtrans.html
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.
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.
In one step you can compute an expression similar to x+y-z but
containing some substitutions (details another time).
For this to work well the lenght must be an odd number.
I tried it out but I didn't measure the time at all.
Well, I spent several hours on it, encouraged by spotting that the 11thSo much?
char is always one after the 1st char.
I was not able to see the relationship between the 12th char and the 2nd.Maybe just cause there's none?
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);
}
The 13th character is the successor of the 2nd, the 15th is the
successor of the 3nd, and so on.
I just made a sort of fold.
http://en.wikipedia.org/wiki/The_quick_brown_fox_jumps_over_the_lazy_dogbut here I used a different key (taken from wiki)You mean Wikipedia? Please give me the URL.
But I forgot to remove the duplicated characters.
Yes, that's a possibility, although I really quite like the digitsYes, I see. But you see why I don't like base 10 for this. And I see
because (in base 10 anyway) they are easy to manipulate
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).
.
- Follow-Ups:
- Re: Paper & pencil password algorithm
- From: James Taylor
- Re: Paper & pencil password algorithm
- Prev by Date: Re: Military and government encryption
- Next by Date: Re: Military and government encryption
- Previous by thread: Re: Paper & pencil password algorithm
- Next by thread: Re: Paper & pencil password algorithm
- Index(es):
Relevant Pages
|
