Prev: Dynamic Hill cipher
Next: PE Scrambler
From: bmearns on 1 May 2010 00:00
On Apr 30, 10:09 pm, Maaartin <grajc...(a)seznam.cz> wrote:
> Using dragthrough.py I tried what happens, when the deck is ordered
> except for the first 5 cards, which get permuted. It's quite possible
> that I misunderstood something. Sure, such an input to rake is not to
> be expected to happen, but the results don't look good (the first line
> is the input to rake, the second is its output):
>
>  2  0  3  4  1  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
> 23 24 25
>  3  4  1  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
> 25  0  2
[snip]

You understood it fine, but I hadn't implemented the fix that J.D.
mentioned earlier, where aces need to be treated as 14, instead of 1.
I've committed this fix to Subversion, so if you update your working
copy you should get much better results. I got the following:
Input:[2, 0, 3, 4, 1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23, 24, 25]
Output:[15, 6, 8, 3, 11, 4, 0, 10, 19, 12, 17, 14, 16, 25, 23, 9, 7,
20, 13, 22, 24, 18, 21, 5, 2, 1]

I also added a new file, deck.py, to the repo. It implements a class
Deck which encapsulates a fairly flexible interface over a deck of
cards. It can handle input and output in three forms: numeric (like
I've been using [0,N-1]), letters from an alphabet, or card
descriptions like 7H, QD, etc. It needs some more work, but so far it
supports the sequence interface (so you can access it with square
brackets just like an array or other list) and has some methods for
moving some cards around in a few different ways. I'll do a little
more work on this when I can, then convert my existing operations to
use this class. Then I'll get to work on the test framework.

G'night.
-Brian
From: bmearns on 1 May 2010 08:38
Maaartin and J.D., I've sent you invitations to Google Wave. Not sure
if you are already signed up for it, or if you're interested, but I
thought this might actually be a good time to use it so we can keep
the discussion better organized. Hopefully you'll get the invites from
Google soon. If you're not interested, we can continue the
conversation here, or via e-mail.

-Brian
From: J.D. on 1 May 2010 13:55
On May 1, 8:38 am, bmearns <mearn...(a)gmail.com> wrote:
> Maaartin and J.D., I've sent you invitations to Google Wave. Not sure
> if you are already signed up for it, or if you're interested, but I
> thought this might actually be a good time to use it so we can keep
> the discussion better organized. Hopefully you'll get the invites from
> Google soon. If you're not interested, we can continue the
> conversation here, or via e-mail.
>
> -Brian

Well, I am on Wave, but I am not sure if I am using it correctly. Did
you get my message?

But anyway, I have another proposal that I think might be secure, and
is more in the spirit of your original idea (or...the second of your
ideas...I am losing track). Which is to say, I think it should be
faster than my current proposal, and it does not require that you put
down any cards or do a 'deal' step.

Specification:

This hash function is narrowly tailored to the task of key
diversification (rather than the broad array of other tasks that hash
functions can be used for). To that end, it takes two inputs: a
secret key with around 88 bits of entropy, and a seed, and then
produces a series of different outputs, each with around 88 bits of
entropy. The seed does not need to be secret, or even random. But
hashing the same secret key with two different seeds will (I think)
generate two very different outputs, in such a manner that it is very
hard to extract the secret key from the outputs via a preimage attack.

The secret key is a string composed of letters from the English
alphabet, and needs to be at minimum 18 letters long (if the key is
very random). Keys that are less random (e.g. a natural language
phrase) need to be longer (in order to have 88 bits of entropy). The
algorithm can accommodate longer keys, but keys shorter than 18
letters will be dangerously insecure. The seed is a string 8 letters
long -- and one way to use the seed is like a counter (e.g. first seed
value is 'aaaaaaaa', second is 'aaaaaaab', and so on).

Once you have your secret key and the session-specific seed, the
algorithm to produce the output has three stages -- initialization,
absorption, and finalization. The algorithm uses 34 cards -- all 26
of the red cards, and the 8 black face cards (the ace, jack, queen and
king of both the spades and the clubs).

Initialization:

Start with the 34-card deck split into two groups: a) the 26 red
cards, in starting order (Ah, 2h, 3h...Kh, Ad, 2d, 3d...Kd), and b)
the 8 black face cards in starting order (which can either be "Jc, Qc,
Kc, Ac, Js, Qs, Ks, As" or "Ac,Jc, Qc, Kc, As, Js, Qs, Ks" depending
on where you think it is best to place the Aces).
Starting with the LAST letter of your secret key, L:
i) convert L to a number, N, according to its place in the alphabet
(a=1, b=2, etc);
ii) count off N cards from the top of the red deck;
iii) slip the top black card (i.e. the Jack or the Ace, whichever is
first) into the red deck after the Nth card, and reassemble the deck
(it now has 27 cards rather than 26);
iv) Repeat steps i-iii with the second from last letter of the key,
L-1, and the next black card. Repeat for L-2, L-3 and so on until all
the black cards have been interspersed in among the red cards and you
have one single deck with 34 cards.

Absorption:

Here is the general technique to absorb a letter, 'X':
1) Convert 'X' into a number, N, according to its place in the
alphabet (a=1, n=2..etc);
2) Count off N cards from the top of the deck;
3) Take the following card, the N+1 card, and move it to the top of
the deck;
4) Take the N+2 card and move it to the bottom of the deck.

And that's it. You can avoid the complexity of step 1 (i.e. avoid
having to convert the letter into a number) by simply reciting the
alphabet as you move from card to card through the deck, stopping when
you reach the place in the alphabet specified by the current letter
being absorbed. To illustrate, here is the deck of 34 cards before
the absorption step:

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14.....33]

Now, to absorb the letter 'F', count off F cards from the top by
reciting the alphabet for each card until you reach 'F':
[a,b,c,d,e,f]_[6,7,8,9,10,11,12,13,14.....33]

Now move the following two cards as specified above:
[6,a,b,c,d,e,f]_[8,9,10,11.....33,7]

And put the deck back together:
[6,0,1,2,3,4,5,8,9,10,11....33,7]

Now the deck is ready to absorb the next letter....

The text to be absorbed in the above manner is:
1) All 8 letters of the seed;
2) Then all letters of the secret key (this time in normal order);
3) Then all 8 letters of the seed again.

Thus if you have a secret key of 18 letters (the minimum size) you
will absorb 34 letters in total during the absorption phase.

Finalization:

The last phase is very simple: Remove the black cards. The outputted
digest is simply the 26 red cards that remain. This removal makes
reversal attacks more difficult, even if the attacker knows the seed.

Rationale:

Some of the steps may seem a little weird (e.g. Why absorb the seed
twice? And why use the last 8 letters of the key in reverse order
during the initialization phase?). However they have a specific
purpose: to ensure that all letters of both the seed and the secret
key have approximately the same impact on the digest. The diffusion
of the absorption operation is not complete, and hence letters
absorbed later have less of an impact on the digest compared to
letters absorbed before. So we have to integrate those weaker letters
at the beginning in some way. Hence the seed is absorbed twice and
the last 8 key letters determine where the 8 black cards are inserted
into the deck.

I don't have python code for this algorithm yet. But preliminary hand
testing gives a pretty good rate of 3 to 4 letters processed per
minute (and possibly higher given practice), and that includes the
initialization step.

Any thoughts, critiques, or questions?


From: Maaartin on 1 May 2010 15:35
On May 1, 7:55 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
> On May 1, 8:38 am, bmearns <mearn...(a)gmail.com> wrote:
> Once you have your secret key and the session-specific seed, the
> algorithm to produce the output has three stages -- initialization,
> absorption, and finalization. The algorithm uses 34 cards -- all 26
> of the red cards, and the 8 black face cards (the ace, jack, queen and
> king of both the spades and the clubs).

It looks like all the exact kind if the black cards doesn't matter at
all, they could be even all the same (e.g., 8 jokers), right?

> Initialization:
[snip]

Here I assume that all black cards are indistinguishable. Either I'm
wrong again, or the order of input is not very important, since the
result is the same for different permutations, as the program shows:

#########
def new_deck():
result = ""
for i in range(26): result += chr(ord("a") + i)
return result

def all_perms(str):
if len(str) <=1:
yield str
else:
for perm in all_perms(str[1:]):
for i in range(len(perm)+1):
yield perm[:i] + str[0:1] + perm[i:]

inputs = set()
outputs = set()
for s in all_perms("martin"):
inputs.add(s)
deck = new_deck();
for c in s:
n = ord(c) - ord("a")
deck = deck[:n] + "_" + deck[n:]
outputs.add(deck)
print len(inputs), len(outputs)
#########
result:
720 432
#########

I'd propose a simple change, which could make this step stronger (or
not, you know me already :D):
After inserting the black card, swap the the parts, i.e.,
deck = deck[n:] + "_" + deck[:n]
To my surprise, that produces 706 different outputs.

> Absorption:
[snip]

That's quite similar to the counting step of Mirdek (I gave a URL here
yesterday or about).

> Finalization:
> The last phase is very simple: Remove the black cards. The outputted
> digest is simply the 26 red cards that remain. This removal makes
> reversal attacks more difficult, even if the attacker knows the seed.

That's nice.

> Rationale:
>
> Some of the steps may seem a little weird (e.g. Why absorb the seed
> twice?

Doing anything twice is IMHO helpful in general, unless the second
pass undoes the work of the first, or it introduces some weird
weakness. The question is if it is the best way.

> And why use the last 8 letters of the key in reverse order
> during the initialization phase?).

The reason for the reversal is obtaining some sort of equal influence
on the output (I mean the sum of the "time distances" of insertions to
the end is the same for the last 8 key letters), right?

At the same time, you don't reverse the seed since the seed is not to
be kept secret, so you save some work here, right?

[snip]
> I don't have python code for this algorithm yet.

I've just found my card deck, till now I've used only python. :D

> But preliminary hand testing gives a pretty good rate of 3 to 4 letters processed per minute

Does it include the fact that each letter gets processed twice?
Assuming no and assuming 4 letters per minute, I come to 2*8/4=4
minutes for the 8 letter seed and 18/4=4.5 minutes for the key.
From: WTShaw on 1 May 2010 17:38
On Apr 29, 8:15 am, bmearns <mearn...(a)gmail.com> wrote:
> On Apr 29, 6:32 am, WTShaw <lure...(a)gmail.com> wrote:
> [snip]
>
>
>
>
>
> > I see that you guy have been through some difficulty working on your
> > idea.  I wholeheartedly render my sympathies.  OK, back to describing
> > the best technique for hand-working a counted hash.  First, let me say
> > that it is a very old idea and I have references to the idea in the
> > 30's but not the name.  A better description is from a the document
> > stamped top-secret, I know because I have one. The includes the M-94
> > and how to shuffle the wheels based on a sentence or just a repeated
> > phrase, the last part that I have dubbed Projection.  I learned of how
> > the hash worked about 1954 as he used it during the war. Not having a
> > better name, I named it Counted Hash years ago and did describe it
> > here.
>
> > 0)The best method for doing a counted hash uses a large graph of maybe
> > 30 cells on a side.
>
> > 1) Write 26 characters to be hashed centered on the top, 2 blank cells
> > cells at each end.
>
> > 2)  Center the abc.. series on left and right vertical columns of the
> > paper, blank cells top and bottom.
>
> > 3) In each row when the letter from the top is the same as the letter
> > on the left or right edge, write the letter of the moment.
>
> > 4) When you have filled the chart, you should have used each of the
> > top letters once somewhere in the column below it dependent on finding
> > the appropriate row..
>
> > 5) Beginning with "A' row, going left to right, number the letters
> > 1-26.  If you have 3 A's, they would be 1-2-3. B would start with 4 if
> > you had any B's.  Some rows would have not entries it those letters
> > did not occur at the top.
>
> > 6) At this point you might want to number the centered characters 1-26
> > on the left edge by writing 1-26 in the second vertical column which
> > should have been left blank.
>
> > 7) At the bottom of the page, find the number of the character
> > assigned as you looked at each row in step 5) and write it
> > in the next to bottom row.
>
> > 8)Write the letter in the bottom row that corresponds to the the
> > letter-number on the left edge from the number in each cell in the row
> > above the bottom row.
>
> > 9) You should have written on the bottow row the completed hash, a
> > permutation of 26 letters.
>
> > 10) To chain another hash, do as before except use the just completed
> > hash for the vertical alphabetic sequences on the left and right edges
> > of the new grid.
>
> WTShaw- Your recent bouts of lucidity are a pleasant surprise. I think
> I followed your description, Let me try a short example (view in fixed-
> width font):
> --debbcfiha--
> -
> a         a   (1)
> b   bb        (2,3)
> c     c       (4)
> d d           (5)
> e  e          (6)
> f      f      (7)
> g
> h        h    (8)
> i       i     (9)
> - 562347891
> - efbcdehia
>
> I put the numberings of each cell off to the side, but I think this is
> what you were describing.
>
> It's interesting, but highly biased. An a in the digest will almost
> always correspond to a in the message (anytime there is an a in the
> message). Just generally, the letters in the digest tend to be pretty
> close to the corresponding letter in the message. I'm not saying I
> could uniquely reverse it, but it seems that a significant amount of
> information about the message can be pretty easily and reliably
> gleaned from the digest.
>
> It's also extremely non-ideal that you have to write everything down.
>
> -Brian

It takes but a brief program because one stage is not enough,
really...it requires chaining. It's the price you need to pay.

As for any set, works the same as long as the letters your are hashing
to chain a given permutation are in that permutation. Just use the
same quantity of letters to hash the same length permutation. Beyond
the chart, it's the numeric sequence that shuffles the permutation of
a given length.

About reversing, that was the test I gave you...don't give up as the
solution is obvious in the 64 character perm.

Remember that 26+26+12=64. Any given letter must be repeated in the
same line at least twice and be sequential in the base 64 default
order. Consider that high frequency letters might have more entries
in their row. It's inductive!
First  |  Prev  |  Next  |  Last
Pages: 8 9 10 11 12 13 14 15 16 17 18 19
Prev: Dynamic Hill cipher
Next: PE Scrambler