Call for review: Hashing by hand algorithm
in [Cryptography]
|
Prev: Dynamic Hill cipher
Next: PE Scrambler
From: J.D. on 27 Apr 2010 21:59 On Apr 27, 9:45 pm, bmearns <mearn...(a)gmail.com> wrote: > Man, you guys are hard to keep up with! But I appreciate all the great > input, I feel like we're getting close to something good. > > Re: mg_shuffle1 > > This looks great Maaartin. I think we can integrate a variation on > J.D.'s shuffle, in place of the simpler find_shuffle you used. > find_shuffle() does: [ h ] A [ i ] B [ t ] --> A [ i ] B [ t ] [ h ] > let find_shuffle_2() do : [ h ] A [ i ] B [ t ] --> [ i ] B [ h ] A > [ t ] For the moment the latest version of his algorithm specifies the following for find_shuffle: [ h ] A [ i ] B [ t ] --> [ i ] B [ t ] [ h ] A > > I'm having trouble understanding your deal function, though, and I've > lost track of which version that you described is actually > implemented. Can you describe it again in terms of what you actually > do with a deck of cards? Here is his description of his deal function: > It's very simple: Assume you hold all cards in your hand and there are > two initally empty decks on the table. > - Take 1 uppermost card from your hand, put it on the left deck. > - Take 2 uppermost cards from your hand, put them on the right deck. > - Repeat as long as you have cards in your hand (take less cards if > not enough present). > - Put the left deck on the right one, take all cards in your hand > again. Hope that helps. (and yeah, my brain is full for tonight too)
From: Maaartin on 27 Apr 2010 22:13 On Apr 28, 3:45 am, bmearns <mearn...(a)gmail.com> wrote: > This looks great Maaartin. I think we can integrate a variation on > J.D.'s shuffle, in place of the simpler find_shuffle you used. > find_shuffle() does: > [ h ] A [ i ] B [ t ] --> A [ i ] B [ t ] [ h ] > let find_shuffle_2() do: > [ h ] A [ i ] B [ t ] --> [ i ] B [ h ] A [ t ] Why not, I just couldn't decide what should be done to the two parts, so I went another way. > I've tried this by hand and it's pretty easy and quick. I know it > looks a little weak, because it leaves the tail alone. So why not [ t ] B [ i ] A [ h ] ? It keeps the distance between the two instances, but this distance changes every time, when exactly one instance of another letter falls in between them, which is quite often. > However, on > either side of your bury function, I think it will work out pretty > well. I prefer it over the original find_shuffle because it reverses > the order of A and B (the two occurrences), But the order is completelly irrelevant now, since everything we do is color-blind. > and (more importantly) > changes the interval between them. It also doesn't leave A or B at any > obvious location. That's right. > I'm having trouble understanding your deal function, though, and I've > lost track of which version that you described is actually > implemented. Can you describe it again in terms of what you actually > do with a deck of cards? I updated the whole description, see below. > I'm still wondering if we need to include the deal, > especially for every input. The deal is the only function capable of breaking many pairs apart. In case it takes too much time, we could think about making it easier, or doing it on every second input, or something like this. In fact, doing deal(deck, (1, 2, 4)) could be better and is easier to do. > If we use your three part algorithm (shuffle, bury, > shuffle), and then use a variation of the bury routine to choose the > outputs as we previously discussed, I expect we can get good results, > though obviously we'll need to test it to be sure. Maybe we could. Having a lot of pairs unbroken is no problem as long as we use a proper output routine. ######### On Apr 28, 3:59 am, "J.D." <degolyer...(a)yahoo.com> wrote: > For the moment the latest version of his algorithm specifies the > following for find_shuffle: > [ h ] A [ i ] B [ t ] --> [ i ] B [ t ] [ h ] A Does it? I seach only the first instance, so you're right. I'm thinking about a variant searching the red instance first and then the black one. But this is (slightly) more work and I see no real advantage yet. > (and yeah, my brain is full for tonight too) Is it late at where you are? :D Are there some result already? ######### To absorb the n-th letter from the message: 1. *** Shuffle: 1a. Find the first instance of that letter 1b. Take all cards before that instance and including that instance and move them to the end 2. *** Bury: 2a. Interpret the card at the top as a number N 2b. put it aside 2c. Count off N cards from the top and put them at the bottom 2d. Put the set-aside instance at the bottom 3. *** Shuffle Again 3a. Repeat step 1a 3b. Repeat step 1b 4. *** Deal Assume you hold all cards in your hand and there are two initally empty decks on the table 4a. Take 1 uppermost card from your hand, put it on the left deck 4b. Take 2 uppermost cards from your hand, put them on the right deck 4c. If there are still cards in your hand, goto 4a. (take less cards if not enough present) 4d. Put the left deck on the right one, take all cards in your hand again. 5. *** Output or next letter 5a. If the absorbed letter is NOT the last of the message then goto 1 (and absorb the next letter of the message) 5b. Otherwise, repeat "bury" process 3 times and output the result as the digest #########
From: J.D. on 27 Apr 2010 22:28 On Apr 27, 10:13 pm, Maaartin <grajc...(a)seznam.cz> wrote: > > > (and yeah, my brain is full for tonight too) > > Is it late at where you are? :D Heh. Sorry, I am not an indefatigable python-coding machine like some people... > > Are there some result already? Not yet. I have done several practice runs with my algorithm and yours, but no full speed runs as of yet. I will pick up where I left off tomorrow, when I am not so tired. I also need bmearns' preferred algorithm fully specified...
From: bmearns on 28 Apr 2010 11:11 On Apr 27, 9:59 pm, "J.D." <degolyer...(a)yahoo.com> wrote: > On Apr 27, 9:45 pm, bmearns <mearn...(a)gmail.com> wrote: [snip] > For the moment the latest version of his algorithm specifies the > following for find_shuffle: > [ h ] A [ i ] B [ t ] --> [ i ] B [ t ] [ h ] A Right, that's the same one you had originally, which is really just cutting the deck at the first instance. > > I'm having trouble understanding your deal function, though, and I've > > lost track of which version that you described is actually > > implemented. Can you describe it again in terms of what you actually > > do with a deck of cards? > > Here is his description of his deal function: > > > It's very simple: Assume you hold all cards in your hand and there are > > two initally empty decks on the table. > > - Take 1 uppermost card from your hand, put it on the left deck. > > - Take 2 uppermost cards from your hand, put them on the right deck. > > - Repeat as long as you have cards in your hand (take less cards if > > not enough present). > > - Put the left deck on the right one, take all cards in your hand > > again. > > Hope that helps. It does, thanks. It makes sense now and seems pretty powerful. Maybe I'm being too paranoid/romantic about the dealing issue; I just don't like having to put cards down. Even face down, it's a potential security issue (easier for someone to grab, harder for you to pick up and shuffle if disturbed), but there's always the case where you don't have a convenient work surface. With a two-part deal you can do it in- hand, but it's a bit wonky. Basically you would transfer the deck from one hand to the other. For a (1,2) deal, you would deal 1 card from the left hand to the top of the deck in your right hand, then 2 from the left hand to the bottom of the right-hand deck, then back to the top with 1, etc. I've got another idea for dealing in-hand, but I'm not sure how it compares to the existing method. It's really just a repeated application of Maaartin's bury technique, with a minor tweak. So you look at the top card, convert it to a number [1-13] (just the card's numerical value, 11, 12, 13 for J, Q, K), and count that many cards down. Take those top cards, /flip them over/ and move them to the bottom of the deck. Repeat until you hit the first upside down card, then flip the deck back over. In python (with apologies to FDR, and using numerical decks with ace represented by 0): ############################ def new_deal(deck): results = [] while len(deck) > 0: n = (deck[0] % 13) + 1 top = deck[0:n] results = top + results deck = deck[n:] return results ############################ It's not nearly as thorough of a deal as the other routine, but it is pretty fast and easy to do (I've actually tested it with cards, this time). I think it we have a strong output function like Maaartin said, this might be sufficient. A sample run with an ordered deck: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Becomes: 24 25 18 19 20 21 22 23 15 16 17 7 8 9 10 11 12 13 14 3 4 5 6 1 2 0 So you can see it keeps a lot of sequences, much worse than Maaartin's deal function. But with some other strong components, it might be sufficient. On Apr 27, 10:13 pm, Maaartin <grajc...(a)seznam.cz> wrote: > On Apr 28, 3:45 am, bmearns <mearn...(a)gmail.com> wrote: [snip] > So why not > [ t ] B [ i ] A [ h ] > ? It keeps the distance between the two instances, but this distance > changes every time, when exactly one instance of another letter falls > in between them, which is quite often. Yes, as long as there is some other operation between before the next time it is performed (as there currently is, the bury operation), then that should be better. If there was no operation in between, then feeding the same value twice in a row would just revert it back to where it was. > > If we use your three part algorithm (shuffle, bury, > > shuffle), and then use a variation of the bury routine to choose the > > outputs as we previously discussed, I expect we can get good results, > > though obviously we'll need to test it to be sure. > > Maybe we could. Having a lot of pairs unbroken is no problem as long > as we use a proper output routine. This is the direction I'm leaning towards right now. If we can make each feed nice and quick and simple, and then reinforce it with a good output function, I think it would make the whole system much more usable. One thing that might be worth point out is that what we have right now (minus the deal operation) is pretty similar to Schneier's Solitaire cipher. His does a triple cut around a pair of jokers, then a count cut based on the bottom card. We do a triple cut (or some variation there-of) around the input value, and then a count cut based on the top card (then another triple-cut). Solitaire, relies on the deck being initially arranged into a random permutation, but still, Schneier at least trusts these operations to maintain randomness, which I think it a good sign. > > (and yeah, my brain is full for tonight too) > > Is it late at where you are? :D Not really, but all these cards and algorithms were clogging my thinking. I feel much better after a night's rest. =) On Apr 27, 10:28 pm, "J.D." <degolyer...(a)yahoo.com> wrote: > On Apr 27, 10:13 pm, Maaartin <grajc...(a)seznam.cz> wrote: [snip] > > Are there some result already? > > Not yet. I have done several practice runs with my algorithm and > yours, but no full speed runs as of yet. I will pick up where I left > off tomorrow, when I am not so tired. I also need bmearns' preferred > algorithm fully specified... J.D., what testing are you doing/planning? You're not trying to run these algorithms by hand yet, are you? To get worthwhile test results we need to run a ton of trials and collect statistics on each one. I think this is much better done by computer. I'm still working on specifying my preferred algorithm, since my preference keeps changing =J. I'm thinking of moving back away from the two-instances concept. It works better for mixing, but it also removes a bit from every input (since the results are the same for two different inputs). With a full 52-card deck it's not such a big deal, but I'd like to leave the algorithm open to the possibility of using smaller decks. (For one thing, arranging 52 cards in order takes a little more than twice as long as arranging 26 cards in order). Obviously everything will be weakened using a smaller deck, there's no getting around that, but I think a 26-card deck should still provide reasonable security. If we use the two instance concept, that's only 13 different inputs, so only 3.7 bits per input. At that rate, a 12-value input (i.e., the master password) only gives about 44 bits, which I think is a bit weak for the master password. With 26 inputs, a 12-value input gives 56 bits, which is quite a bit more reasonable. Is there an easy way we can use two-instances, but have them not be equivalent? In Solitaire, you move the A joker by one card, and the B joker by two cards, before doing the triple cut, but I'm not crazy about that. I've run Solitaire a few times and that part's a bit of a burden, and slightly error prone (especially when the jokers are near each other or at the end of the deck). One idea is that if you find the B instance (i.e., the "complimentary" card) first, just move it and the cards before it to the end of the deck, like this: [ h ] B [ i ] A [ t ] --> [ i ] A [ t ] B [ h ] Then you can just continue through from there with the regular shuffle operation (what ever it may be, currently I think we left off with Maaartin's triple cut). So let's say the deck looks like this: [ h ] X [ i ] Y [ t ] Where E and F are complimentary cards. If we feed in X, we just apply the triple cut as is, so we get: [ t ] Y [ i ] X [ h ] But if we feed in Y, we would find the X first, and move it to the end: [ i ] Y [ t ] X [ h ] Then apply the triple cut from there and end up with [ h ] X [ t ] Y [ i ] So complimentary cards are no longer equivalent, but we can still use the triple cut which I think is better than a single cut. The one thing I notice is that the the second card (where the compliment is found first) leaves the head and the input card ( [ h ] X ) in- position. Assuming that happens 50% of the time, and in conjunction with our bury and second shuffle, maybe that's ok. If either of you have a better way to handle this, I'm all ears. Alright, here's a description of my current preference for the algorithm. I'm doing away with the deal until the output phase. In a deck of length 2K, feed input value X as follows: 1) Let Y be the compliment of X. If X >= K, then Y = X % K. Otherwise, Y = K+X. (So if you're using two different colors/suits, it's just the same rank card in the opposite color). 2) Perform a shuffle/triple-cut: 2a) Search through the deck from the top, looking for X or Y. 2b) If Y is found first, move Y to the end of the deck, then move all the cards that came before Y to the end of the deck: [ h ] Y [ t ] --> [ t ] Y [ h ] 2c) When you find X, perform a triple cut with X and Y: 2c.1) Collect all the cards that came before X into the opposite hand, then move X on top of that deck: [ h ] X [ i ] Y [ t ] --> lefthand( [ i ] Y [ t ] ) righthand( X [ h ] ) 2c.2) Continue stepping down through what's left of the original deck until you find Y. When you find it, move the cards that came before it to the top of the other deck, then move Y on top of that: lefthand( [ i ] Y [ t ] ) righthand( X [ h ] ) -- > lefthand( [ t ] ) righthand( Y [ i ] X [ h ] ) 2c.3) Finally, put whats left of the original deck (lefthand) on top of the other deck. lefthand( [ t ] ) righthand( Y [ i ] X [ h ] ) -- > [ t ] Y [ i ] X [ h ] (Less explicitly but more intuitively, you're just moving blocks of cards from the left hand to the right, where the blocks are separated by X and Y 3) Perform a count-cut/bury: 3a) Look at the top card, convert it to a value in [1, K] (simply the card's rank). 3b) Including that first card, count that many cards off the top of the deck, and move them to the bottom of the deck. E [ ... <E-1 cards> ... ] [ t ] --> [ t ] E [ ... <E-1 cards> ... ] (Note this step is not strictly reversible without knowing the previous state of the deck. However, there will typically only be a few possible ways to reverse it. I.e., start counting from the bottom of the deck. Any card that is equal to the count is a possibility. Any card that is not equal to the count is not a possibility.) 4) Perform a shuffle/triple-cut: 4a) Repeat step 2. After feeding all inputs, produce the output digest as follows: 1) Look at the top card, convert it to a value in [1, K] (simply the card's rank). 2) Including that first card, count that many cards off the top of the deck. 3) The next card is your output value. Move this to the bottom of the deck, then move all the cards that were above it to the bottom of the deck. E [ ... <E-1 cards> ... ] D [ t ] --> [ t ] D E [ ... <E-1 cards> ... ] output is D 4) Repeat steps 1-3 until sufficient number of outputs are generated. This is almost identical to the method Maaartin suggested earlier, but it modifies the deck at each pass, so I would /expect/ it not to loop very quickly. If it does, then we can go back to Maaartin's other suggestion of dropping the output card when it's selected. This slightly reduces the information density of the output, but if it stops looping it's obviously worth it, and we should still be able to get a good enough password from it: 26 permute 12 is still 52 bits. Regards, -Brian
From: bmearns on 28 Apr 2010 13:00
Couple bad results so far (using the description at the end of my last post). First, the output function I described still loops a lot. So I went with dropping the output card from the deck, which slightly reduces the density and obviously sets a limit on the length of the output, but I think it's still sufficient. More importantly, it's not cascading well. I only fed in 5 characters, and changing the first one only changed the last output. Guess it's back to the drawing board. Maybe it's not possible to get good performance without some sort of dealing. I'll add that and see how it goes. -Brian |