Call for review: Hashing by hand algorithm
in [Cryptography]
|
Prev: Dynamic Hill cipher
Next: PE Scrambler
From: Maaartin on 30 Apr 2010 20:02 On Apr 29, 8:25 pm, bmearns <mearn...(a)gmail.com> wrote: > No, it only gets rid of 1 at a time, but I may not have described it > very well. My fault, I simply can't read (and was too optimistic, too). > Here's the python: The problem with this snippet is that I can't run it without some work (yes, I'm lazy and you use other representation than I do). Now with the SVN it's no problem anymore. > > evaluate(input_function, finalizing_function, output_function, effort, > > seed) > That looks pretty good, but do you mean there would be a different one > of these functions to test every metric? No, that's why it return a list of numbers instead of only one. But it's probably better to return a dictionary, so the different metrics do have a name. > I think we can set it up a > little more efficiently where we can test a number of different > metrics on a single deck. I was thinking about testing all at once. Maybe better idea: Let "evaluate" accept a dictionary as a parameter and compute and insert all metrics (it knows about) which are missing in the dictionary. This way we could build a big "evaluate" by calling many smaller once and we could simply call it again, when we implement more metrics (yes, I assume some persistent storage). Unfortunately, I'm a poor guy running Windoze and use python in cygwin, and there's no txtdb package there. On Apr 30, 5:08 am, "J.D." <degolyer...(a)yahoo.com> wrote: > I have some analysis for the two algorithms that I tested by hand > (mine and Maaartin's). Thank you for your "Exhumation book", good work. I'll try to keep my answer short and will possible write more after having it read more carefully. > The first thing to note is that both the "bury" and the fixed (1,2) > deal operations are easily undoable. Here is how to undo them: Sure. Bury could be easily made non-bijective, but I preferred it this way. > The first step in reversing the hash is to undo those three buries, > which can be done by calling "Disinter" three times. Obviously, doing any bijective operation at the end is useless. I knew it, but I didn't think about this, since we're never going output the whole deck. Burry should help in case only some prefix gets known, otherwise it's completelly useless. Nonetheless, beeing able to find out the last letter (and even more) from the whole deck is a serious weakness. > Generally you don't want to let the attacker be able to easily > determine even one of the letters of the message with 100% certainty. > So that is an area where Maaartin's algorithm needs improvement. Sure. Probably a replacement instead of an improvement. > That bury step in the middle is the weak point, and will enable us to > (with a certain amount of guessing) undo all three steps. Here I disagree, without the bury it would be even weaker (you could simply skip undoing it, or am I wrong?). I consider placing the card in a defined position to be the root of all evil here. I shoud have used somethink like h X t -> t X h instead of h X t -> t h X Currently I'd prefer h X i Y t -> t Y i X h anyway. Doing h X i Y t -> t X i Y h instead changes IMHO just a bit (or nothing in a color-blind algorithm). Changing the positions of X or Y in this 5-tuple is bad since it gets an instance either at one end or adjacent to the other. Any other permutation of (h, i, t) seems to make less work, e.g., h X i Y t -> t X h Y i is about the same as a double-cut on X. I've found http://www.ciphergoth.org/crypto/mirdek/description.html and like the counted cut. > General Definition: A self-justifying card is a card with a face value > of "N", and there are N cards between it and some "anchor-point". The > relevant anchor-point given our assumption is the current highest > instance (X). To illustrate: Nice! > I have a similar analysis for my own algorithm, but for now let's make > sure that the above analysis is a) clear, and b) correct. Is there > any part that you guys need clarified or expanded upon? Do you spot > any errors in the analysis? No, but I'll have to re-read it all. On Apr 30, 7:05 pm, "J.D." <degolyer...(a)yahoo.com> wrote: > On Apr 29, 12:34 pm, bmearns <mearn...(a)gmail.com> wrote: > OK, I think I found a slight problem with the 'raking' operation as > described above (though not necessarily a fatal one -- it only occurs > in relatively rare situations, and might not matter much in the end): > > Take a deck where the top card is black. It becomes the 'Selected' > card. Now assume the next card (the 'Top' card) is also black, and is > an ace (I understand that aces = 1 in your numbering scheme). > I don't know how big of a problem that is, but there is an easy fix > either way The probability of the black aces is 2/52/52, they may be red instead, so there's a failure probability of 4/52/52=0.0015, which is too bad, especially when the remedy is trivial. > -- just interpret aces as 14, and don't have any card equal > 1 for the purposes of the 'bury' operation. In terms of the > naturalness of this fix, while it may be natural to interpret aces as > 1, it is just as natural to interpret them as 14 (since in many card > games they are the highest card of the given suit). I currently hate using A=14, I know it doesn't matter, but it would be nice to settle down on the simplest rules. Adding one to each card's numeric value or simply moving one more card works as good. On Apr 30, 8:26 pm, bmearns <mearn...(a)gmail.com> wrote: > I've run it several times by hand now. First, I need to apologize for > being overly critical of the time it took the other algorithms, > because raking is not exactly a speed-of-sound operation. I expected it to be slow, because of having to count up to eight on the average for each card. But you do it once for each output letter, which is not as bad. > However, I > did get noticeably better and faster with a bit of practice, and the > results still look very promising. Give us some numbers, I'm curious.
From: bmearns on 30 Apr 2010 20:55 On Apr 30, 8:02 pm, Maaartin <grajc...(a)seznam.cz> wrote: > On Apr 30, 8:26 pm, bmearns <mearn...(a)gmail.com> wrote: > > > I've run it several times by hand now. First, I need to apologize for > > being overly critical of the time it took the other algorithms, > > because raking is not exactly a speed-of-sound operation. > > I expected it to be slow, because of having to count up to eight on > the average for each card. But you do it once for each output letter, > which is not as bad. > > > However, I > > did get noticeably better and faster with a bit of practice, and the > > results still look very promising. > > Give us some numbers, I'm curious. On my last try, I finished a 26-card deck in about 4 minutes. It should be almost exactly linear in time, so a 52-card deck would take twice as long. Personally, I'm pretty satisfied with a 26-card deck in terms of security: it gives just over 88 bits max for each output. I'm working on setting up the code framework before I start doing more testing, so I'll get back when I have more info. -Brian
From: J.D. on 30 Apr 2010 20:59 On Apr 30, 8:02 pm, Maaartin <grajc...(a)seznam.cz> wrote: > > Obviously, doing any bijective operation at the end is useless. I knew > it, but I didn't think about this, since we're never going output the > whole deck. I suppose. However outputting only a subset of the full deck does not _necessarily_ make an insecure hash function secure. Recall that the untruncated digest is a permutation of a deck of cards for which every card is unique -- if you truncate the deck in some way so as to only output a subset of the deck, the attacker can look at the cards that are outputted and can tell which cards are missing. If the subset of missing cards is small enough, it might still be practical to simply guess the order of the missing cards and conduct an attack on the guessed full deck. Of course, there are probably ways of truncating the deck such that this is very hard -- but that would mean trying to find a secure truncation method. If the hash function is reasonably secure against attacks even when the full deck is outputted then this possibility can be dismissed, and we can truncate the deck however we like (i.e. in the simplest, fastest way), or even not truncate it at all. > > > That bury step in the middle is the weak point, and will enable us to > > (with a certain amount of guessing) undo all three steps. > > Here I disagree, without the bury it would be even weaker (you could > simply skip undoing it, or am I wrong?). Well....yes, you're wrong (maybe). If you dropped the bury step in the middle and just had the two shuffle-cuts, your algorithm would actually be stronger -- at least against the attack I laid out in my looooong post; it might however be weaker against some other attack (hence the 'maybe'). The efficiency of my attack rests on being able to narrow the scope of its search by searching for self-justifying cards, because if a potential reversal step does NOT result in self- justifying cards then we can discard that possibility as not being a viable path to a preimage. The bury operation necessitates the existence of self-justifying cards in any viable path to a preimage, and thus gives the attacker a way to distinguish viable paths from unviable paths. Without the bury operation, the second shuffle-cut is trivial to reverse, but the _first_ shuffle-cut is much harder to reverse (and would probably have an average branching rate that makes my attack unfeasible).
From: Maaartin on 30 Apr 2010 21:41 On May 1, 2:55 am, bmearns <mearn...(a)gmail.com> wrote: > On Apr 30, 8:02 pm, Maaartin <grajc...(a)seznam.cz> wrote: > > Give us some numbers, I'm curious. > > On my last try, I finished a 26-card deck in about 4 minutes. It > should be almost exactly linear in time, so a 52-card deck would take > twice as long. Personally, I'm pretty satisfied with a 26-card deck in > terms of security: it gives just over 88 bits max for each output. IIUYC, the time does not depend on the number of cards, but on the length of output to be produced. So you loose no time here when using a 52 card deck, right? On May 1, 2:59 am, "J.D." <degolyer...(a)yahoo.com> wrote: > On Apr 30, 8:02 pm, Maaartin <grajc...(a)seznam.cz> wrote: > > Obviously, doing any bijective operation at the end is useless. I knew > > it, but I didn't think about this, since we're never going output the > > whole deck. > > I suppose. However outputting only a subset of the full deck does not > _necessarily_ make an insecure hash function secure. I fully agree, I only wanted to say, that my reason for the buries was to shuffle the stack in a way, where the most important card (the one controlling the bury amount gets at the bottom, so it gets kept hidden for a short output. That's all. > Recall that the > untruncated digest is a permutation of a deck of cards for which every > card is unique -- if you truncate the deck in some way so as to only > output a subset of the deck, the attacker can look at the cards that > are outputted and can tell which cards are missing. Yes, but for password generation we need to output only 10 to 20 cards out of 52. > If the subset of > missing cards is small enough, it might still be practical to simply > guess the order of the missing cards and conduct an attack on the > guessed full deck. Of course, there are probably ways of truncating > the deck such that this is very hard -- but that would mean trying to > find a secure truncation method. Maybe we could limit ourselves to red cards, so all letters stay in the deck in at least one instance. But forget about it, that's not the way I'd like to follow. > If the hash function is reasonably > secure against attacks even when the full deck is outputted then this > possibility can be dismissed, and we can truncate the deck however we > like (i.e. in the simplest, fastest way), or even not truncate it at > all. Agreed. OTOH, if we had a secure output function (not truncating, just something working like rake or my output_function but secure), than we do not need to care about the previous mixing much (we should still avoid internal collisions, although the attacker has no use for them). > > > That bury step in the middle is the weak point, and will enable us to > > > (with a certain amount of guessing) undo all three steps. > > > Here I disagree, without the bury it would be even weaker (you could > > simply skip undoing it, or am I wrong?). > > Well....yes, you're wrong (maybe). If you dropped the bury step in > the middle and just had the two shuffle-cuts, your algorithm would > actually be stronger -- at least against the attack I laid out in my > looooong post; it might however be weaker against some other attack > (hence the 'maybe'). The efficiency of my attack rests on being able > to narrow the scope of its search by searching for self-justifying > cards, because if a potential reversal step does NOT result in self- > justifying cards then we can discard that possibility as not being a > viable path to a preimage. I see, many thanks for the explanation. > The bury operation necessitates the > existence of self-justifying cards in any viable path to a preimage, > and thus gives the attacker a way to distinguish viable paths from > unviable paths. Without the bury operation, the second shuffle-cut is > trivial to reverse, but the _first_ shuffle-cut is much harder to > reverse (and would probably have an average branching rate that makes > my attack unfeasible). I see I need much more sleep, so I can come out with something better. Thx again.
From: Maaartin on 30 Apr 2010 22:09
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 2 1 0 4 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 4 1 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 2 2 3 0 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 5 1 4 3 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 2 2 4 0 3 1 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 6 3 1 5 4 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 2 3 4 2 1 0 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 6 5 2 1 4 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 3 4 0 3 1 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 3 1 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 4 4 3 1 0 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 5 2 1 3 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 4 4 3 2 0 1 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 5 3 1 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 4 And now I *really* go to bed. |