Prev: Dynamic Hill cipher
Next: PE Scrambler
From: Maaartin on 26 Apr 2010 18:57
On Apr 26, 11:56 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
> Not all hash functions use extensive final processing between the last
> input and outputting the digest. For many (e.g. MD4 and MD5) the
> digest is simply the last chaining variable.

You're right. So maybe all modern hash functions do?

[snip]

It seems to be quite complicated, or maybe it's too late for me (it's
1 AM here).

I'd suggest using all 52 bridge cards, so each letter occurs twice.
The only change in the algorithm is:
"start by finding the FIRST OCCURENCE OF THE corresponding card in the
deck".


I've got an idea for the data extraction. I hope, it's easy and hides
the internal state well.

After the data input, do the following as many times as needed.
- Look at the top card, treat it as a number N between 0 and 12.
- Count N more cards.
- Put them to the bottom.
- Output the bottom card.

Example:
3 a b c 1 d e f ... z
=> (move 1+3 cards)
1 d e f ... z 3 a b c
output: c
=> (move 1+1 cards)
e f ... z 3 a b c 1 d
output: d

Done this way, it does not allow arbitrary output, but the output is
not constrained to be a permutation. Dependend on the stack size,
there's a lower limit how near two occurences of the same output may
come. With a redundant stack (all 52 bridge cards for 26 letters),
there's no such limit, although there's a similar limit for three
occurences. I wouldn't care, since three occurences of a single letter
are quite unprobable, anyway.


One idea for processing after doing the output:
- Go through the stack from the top until you see the second color
change.
- Move the cards to the bottom.

Example (lowercase letters are red, uppercase are black):
a b c d E F G h ... z
=>
h ... z a b c d E F G

Such an operation could be done after feeding a character, too.

When doing this, I'd suggest to use clubs and diamonds for the first
13 letters and hearts and spades for the second 13 ones, so each
letter occurs in both colors.

Another idea for processing after doing the output:
- Go through the stack from the top until you encounter at least one
card of each shape (c, d, h, s).
- Move the cards to the bottom.

Example:
c c c d d c h h d c s c ... x
=>
c ... x c c c d d c h h d c s
From: J.D. on 26 Apr 2010 18:59
On Apr 26, 5:56 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
> Indeed.  Perhaps you (brian) could improve the mix rate by doing
> something like the following:
>
> Split the deck into a red and a black decks by suits.  Each deck would
> have 26 cards, corresponding to each letter in the English alphabet.
> 1) Using the red deck first, use your algorithm (in the link a few
> posts above) adjusted for a deck of length 26 to feed in the first
> letter of the message.
> 2) Take the resulting reordered red deck, and spread them out in a
> line.
> 3) Then place a black card under each red card according to some
> formula:  For example;
> i) interpret each red card as a number, (e.g. ace of hearts = 1),
> ii) then apply an affine function (e.g. f = (7x)+5 mod 26) to the
> number of the given red card,
> iii) and then (interpreting each black card as a number in the same
> range) place the black card corresponding to the output of the
> function under the red card (e.g. f(1) = 12, so under the ace of
> hearts place the queen of clubs, assuming the queen of clubs = 12).
> 4) Then, scoop up the black deck, keeping the cards in the order they
> are placed below the red cards, and use the black deck to absorb the
> second letter of the message (using your algorithm).
> 5) Repeat steps 2-4, except using the black deck along the top and
> placing the red cards below according to the formula.
> ...and continue repeating until all letters of the message are
> absorbed.

Some python code (which would tack on to your code in the link):
def convert(deck):
a = len(deck)
length = a-1
tempdeck = list()
for i in range(length):
tempdeck.append(((deck[i]*7)+5)%length)
return tempdeck

So, hashing a message "abc":
#deck = [0....25]
deck = shuffle(deck, 0) #a = 0
deck = convert(deck)
deck = shuffle(deck, 1) #b=1
deck = convert(deck)
deck = shuffle(deck, 2) #c=2
deck = convert(deck)
#and the digest:
print(deck)

(Note for testing with shorter decks: while the above 'convert'
function will work for any length of deck, the chosen affine function
(y = 7x+5 mod no. of cards in deck) is intended for decks of 26 cards
-- it might not be appropriate for other deck lengths)
From: J.D. on 26 Apr 2010 19:07
On Apr 26, 6:57 pm, Maaartin <grajc...(a)seznam.cz> wrote:
> On Apr 26, 11:56 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
>
> > Not all hash functions use extensive final processing between the last
> > input and outputting the digest.  For many (e.g. MD4 and MD5) the
> > digest is simply the last chaining variable.
>
> You're right. So maybe all modern hash functions do?

Well, most hashes based on the Merkle Damgard construction seem to
have the digest = the last chaining variable. This includes several
of the SHA-3 hash function candidates (if I remember correctly, I can
try to look up a cite if you want). That said, hash functions based
on the Sponge construction use processing between the last input and
the output, and perhaps others do too.

>
> One idea for processing after doing the output:
> - Go through the stack from the top until you see the second color
> change.
> - Move the cards to the bottom.
>
> Example (lowercase letters are red, uppercase are black):
> a b c d E F G h ... z
> =>
> h ... z a b c d E F G
>
> Such an operation could be done after feeding a character, too.
>
> When doing this, I'd suggest to use clubs and diamonds for the first
> 13 letters and hearts and spades for the second 13 ones, so each
> letter occurs in both colors.
>
> Another idea for processing after doing the output:
> - Go through the stack from the top until you encounter at least one
> card of each shape (c, d, h, s).
> - Move the cards to the bottom.
>
> Example:
> c c c d d c h h d c s c ... x
> =>
> c ... x c c c d d c h h d c s

I like both of those ideas. They are simpler and perhaps more
effective than my suggestion...
From: J.D. on 26 Apr 2010 19:22
On Apr 26, 6:59 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
> On Apr 26, 5:56 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
>
>
>
> > Indeed.  Perhaps you (brian) could improve the mix rate by doing
> > something like the following:
>
> > Split the deck into a red and a black decks by suits.  Each deck would
> > have 26 cards, corresponding to each letter in the English alphabet.
> > 1) Using the red deck first, use your algorithm (in the link a few
> > posts above) adjusted for a deck of length 26 to feed in the first
> > letter of the message.
> > 2) Take the resulting reordered red deck, and spread them out in a
> > line.
> > 3) Then place a black card under each red card according to some
> > formula:  For example;
> > i) interpret each red card as a number, (e.g. ace of hearts = 1),
> > ii) then apply an affine function (e.g. f = (7x)+5 mod 26) to the
> > number of the given red card,
> > iii) and then (interpreting each black card as a number in the same
> > range) place the black card corresponding to the output of the
> > function under the red card (e.g. f(1) = 12, so under the ace of
> > hearts place the queen of clubs, assuming the queen of clubs = 12).
> > 4) Then, scoop up the black deck, keeping the cards in the order they
> > are placed below the red cards, and use the black deck to absorb the
> > second letter of the message (using your algorithm).
> > 5) Repeat steps 2-4, except using the black deck along the top and
> > placing the red cards below according to the formula.
> > ...and continue repeating until all letters of the message are
> > absorbed.
>
> Some python code (which would tack on to your code in the link):
> def convert(deck):
>         a = len(deck)
>         length = a-1
>         tempdeck = list()
>         for i in range(length):
>                 tempdeck.append(((deck[i]*7)+5)%length)
>         return tempdeck
>
> So, hashing a message "abc":
> #deck = [0....25]
> deck = shuffle(deck, 0) #a = 0
> deck = convert(deck)
> deck = shuffle(deck, 1) #b=1
> deck = convert(deck)
> deck = shuffle(deck, 2) #c=2
> deck = convert(deck)
> #and the digest:
> print(deck)
>
> (Note for testing with shorter decks: while the above 'convert'
> function will work for any length of deck, the chosen affine function
> (y = 7x+5 mod no. of cards in deck) is intended for decks of 26 cards
> -- it might not be appropriate for other deck lengths)

Oops, function should read:

def convert(deck):
length = len(deck)
tempdeck = list()
for i in range(length):
tempdeck.append(((deck[i]*7)+5)%length)
return tempdeck
From: J.D. on 26 Apr 2010 19:35
On Apr 26, 7:22 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
> On Apr 26, 6:59 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
>
>
>
> > On Apr 26, 5:56 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
>
> > > Indeed.  Perhaps you (brian) could improve the mix rate by doing
> > > something like the following:
>
> > > Split the deck into a red and a black decks by suits.  Each deck would
> > > have 26 cards, corresponding to each letter in the English alphabet.
> > > 1) Using the red deck first, use your algorithm (in the link a few
> > > posts above) adjusted for a deck of length 26 to feed in the first
> > > letter of the message.
> > > 2) Take the resulting reordered red deck, and spread them out in a
> > > line.
> > > 3) Then place a black card under each red card according to some
> > > formula:  For example;
> > > i) interpret each red card as a number, (e.g. ace of hearts = 1),
> > > ii) then apply an affine function (e.g. f = (7x)+5 mod 26) to the
> > > number of the given red card,
> > > iii) and then (interpreting each black card as a number in the same
> > > range) place the black card corresponding to the output of the
> > > function under the red card (e.g. f(1) = 12, so under the ace of
> > > hearts place the queen of clubs, assuming the queen of clubs = 12).
> > > 4) Then, scoop up the black deck, keeping the cards in the order they
> > > are placed below the red cards, and use the black deck to absorb the
> > > second letter of the message (using your algorithm).
> > > 5) Repeat steps 2-4, except using the black deck along the top and
> > > placing the red cards below according to the formula.
> > > ...and continue repeating until all letters of the message are
> > > absorbed.
>
> > Some python code (which would tack on to your code in the link):
> > def convert(deck):
> >         a = len(deck)
> >         length = a-1
> >         tempdeck = list()
> >         for i in range(length):
> >                 tempdeck.append(((deck[i]*7)+5)%length)
> >         return tempdeck
>
> > So, hashing a message "abc":
> > #deck = [0....25]
> > deck = shuffle(deck, 0) #a = 0
> > deck = convert(deck)
> > deck = shuffle(deck, 1) #b=1
> > deck = convert(deck)
> > deck = shuffle(deck, 2) #c=2
> > deck = convert(deck)
> > #and the digest:
> > print(deck)
>
> > (Note for testing with shorter decks: while the above 'convert'
> > function will work for any length of deck, the chosen affine function
> > (y = 7x+5 mod no. of cards in deck) is intended for decks of 26 cards
> > -- it might not be appropriate for other deck lengths)
>
> Oops, function should read:
>
> def convert(deck):
>         length = len(deck)
>         tempdeck = list()
>         for i in range(length):
>                 tempdeck.append(((deck[i]*7)+5)%length)
>         return tempdeck

After some testing, this does not substantially increase the avalanche
rate, and we still end up with digests for short messages with too
much order. For instance, hash of message 3,9,15:
[16, 21, 0, 5, 10, 15, 20, 14, 25, 4, 9, 19, 13, 24, 3, 8, 18, 6, 23,
2, 7, 12, 17, 22, 1, 11]
And hash of message 3,8,15:
[21, 6, 0, 5, 10, 15, 20, 14, 25, 4, 9, 19, 16, 24, 3, 8, 13, 18, 23,
2, 7, 12, 17, 22, 1, 11]
That is clearly unacceptable...

Perhaps my idea can still work, but (as described in the addendum to
my post) by using one out of 26 different affine functions for the
conversion step, as selected by the latest letter absorbed. I am
still learning python (I started yesterday), so I am not sure how to
do that. Also, it may be too complicated to efficiently do by hand.
Maaartin's idea(s) may be more workable...
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Prev: Dynamic Hill cipher
Next: PE Scrambler