Call for review: Hashing by hand algorithm
in [Cryptography]
|
Prev: Dynamic Hill cipher
Next: PE Scrambler
From: bmearns on 26 Apr 2010 13:41 On Apr 26, 12:47 pm, "J.D." <degolyer...(a)yahoo.com> wrote: > On Apr 26, 9:09 am, bmearns <mearn...(a)gmail.com> wrote: > > > I actually opened my request for review to a slightly broader audience > > over the weekend, and so the algorithm is described on the following > > webpage:http://brianpmearns.com/bpm/shufflehash > > It seems like it should be somewhat vulnerable to pre-image attack for > very short message lengths. For example, it is trivially reversible > for messages of just one letter (e.g. if you 'hashed' a single letter > then the card for the letter right after it (e.g. 'B' if you hashed > 'A') would be at the bottom of the deck -- I am assuming the output of > the hash is simply the full deck after all shuffles are completed). > And with 52 cards, even after two or three letters have been added to > the hash, most cards remain in their starting order relative to each > other. It seems like it should be easy (easier than a brute force pre- > image attack) to restrict the guesses the cards that are no longer in > their original order relative to the other cards (which would be a > significant subset of the full deck for very short messages). For > example, I used your code to hash a 3 letter message with a deck of 26 > cards. The output is this: > [18, 19, 20, 21, 22, 23, 24, 25, 4, 0, 1, 2, 3, 5, 8, 6, 7, 9, 16, 10, > 11, 12, 13, 14, 15, 17] > Note that the letters from 18 to 25 are in relative order, so a good > guess is that the hash did not include any number in that range. > Similarly, 0 to 3 is in order, as is 10 to 15. In fact, a superficial > glance reveals that the numbers most radically out of the starting > order are 4, 8 and 16 (which, not incidentally, was the message). A > pre-image attack restricted to those three letters would very quickly > find the message (much faster than a standard brute force pre-image > attack on 3 letter messages). > > This sort of guess-work becomes much more problematic after several > more letters are added to the hash -- but a good cryptographic hash > shouldn't be easily reversible no matter how long the message is. Thank you J.D., that was very useful feedback. I think I'd better start calling this something other than a cryptographic hash function. Maybe just a "scrambling function" would get me in less trouble =). You're absolutely right about the vulnerabilities you pointed out. If a smaller deck is used, then this sort of vulnerability would fade much more quickly, right? Your point that a hash should be secure regardless of how long the input is correct, of course, but for my specific purposes, I don't mind if it requires some minimum (reasonable) number of inputs before it becomes secure (which is why I should stop calling it a cryptographic hash). Just off the top of my head, I would guess that if the number of inputs is at least half the total deck-size, it should be safe against this? Additionally, pre-image resistance (collision resistance in general) is not my /primary/ concern, though it certainly is a concern. In the context I'm looking at (narrow as it may be), it's not useful for an attacker to just find some m2 such that hash(m2) = hash(m1). If they know hash(m1) then they can already break into that specific account. In order to learn the "core" password, they would need to find the exact value m1. Or I suppose they could find some value m3 such that hash(seed1+m3) = hash(seed1+password) and hash(seed2+m3) = hash(seed2+password), but I'm going to go out on a limb and guess that if they can do that, they can just find the password directly. Thanks again for the great feedback, I need to make sure I take this into account if I actually end up using it. If you have any more I would very much love to hear it. Warm regards, -Brian
From: J.D. on 26 Apr 2010 13:59 On Apr 26, 1:41 pm, bmearns <mearn...(a)gmail.com> wrote: > If > a smaller deck is used, then this sort of vulnerability would fade > much more quickly, right? Intuitively it seems like that should be the case, though I don't have a proof either one way or the other.
From: bmearns on 26 Apr 2010 14:38 On Apr 26, 1:59 pm, "J.D." <degolyer...(a)yahoo.com> wrote: > On Apr 26, 1:41 pm, bmearns <mearn...(a)gmail.com> wrote: > > > If > > a smaller deck is used, then this sort of vulnerability would fade > > much more quickly, right? > > Intuitively it seems like that should be the case, though I don't have > a proof either one way or the other. Yes, unfortunately formal (or even informal) proofs for cryptographic algorithms are nothing like my strong point. I'll see what sort of testing I can come up with for it. Thanks, again. -Brian
From: Maaartin on 26 Apr 2010 16:39 On Apr 26, 7:41 pm, bmearns <mearn...(a)gmail.com> wrote: > I think I'd better start calling this something other than a > cryptographic hash function. Maybe just a "scrambling function" would > get me in less trouble =). AFAIK, all cryptographic hashes use some final mixing, which can be quite time-consuming (e.g, CubeHash makes an equivalent of hashing 10 additional blocks). I see why you don't want to do it. > You're absolutely right about the vulnerabilities you pointed out. If > a smaller deck is used, then this sort of vulnerability would fade > much more quickly, right? Your point that a hash should be secure > regardless of how long the input is correct, of course, but for my > specific purposes, I don't mind if it requires some minimum > (reasonable) number of inputs before it becomes secure (which is why I > should stop calling it a cryptographic hash). You could require that after any input shorter than 10 there must be 1000 additional rounds (so you could keep claiming it to be cryptographic and prevent everybody from using such short inputs. :D) > Additionally, pre-image resistance (collision resistance in general) > is not my /primary/ concern, though it certainly is a concern. In the > context I'm looking at (narrow as it may be), it's not useful for an > attacker to just find some m2 such that hash(m2) = hash(m1). If they > know hash(m1) then they can already break into that specific account. > In order to learn the "core" password, they would need to find the > exact value m1. Or I suppose they could find some value m3 such that > hash(seed1+m3) = hash(seed1+password) and hash(seed2+m3) = > hash(seed2+password), but I'm going to go out on a limb and guess that > if they can do that, they can just find the password directly. I think so. The password must come last, otherwise the attacker could get all relevant information by simply looking at hash(password+""). Sure, this is a CPA and quite irrelevant to what you do. I'd even suggest to start with a secret stack arrangement. The reason is that rearranging the stack at the beginning is quite easy and less error- prone as compared to normal steps. What I liked on your former scheme (and miss now) was the use of card color - this is quite easy and could lead to good mixing. Would you like something like this? How is the performance of the current algorithm, I mean, how long does it take and what is the error rate?
From: J.D. on 26 Apr 2010 17:56
On Apr 26, 4:39 pm, Maaartin <grajc...(a)seznam.cz> wrote: > On Apr 26, 7:41 pm, bmearns <mearn...(a)gmail.com> wrote: > > > I think I'd better start calling this something other than a > > cryptographic hash function. Maybe just a "scrambling function" would > > get me in less trouble =). > > AFAIK, all cryptographic hashes use some final mixing, which can be > quite time-consuming (e.g, CubeHash makes an equivalent of hashing 10 > additional blocks). I see why you don't want to do it. 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. But yes, the tedium factor and corresponding error rate becomes very important when making 'by hand' algorithms. Balancing the goal of reasonable security with the goal of not driving the user insane with boredom is very hard. > What I liked on your former scheme (and miss now) was the use of card > color - this is quite easy and could lead to good mixing. Would you > like something like this? 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. This is still trivially reversible given a message of one letter. But hopefully it is harder to reverse for small messages that are larger than one letter. And really, how often are you going to use the capital letters as inputs? Addendum -- if this isn't too complicated already, you could have 26 _different_ affine functions for step 3, one per letter, and use the function A when the message letter just absorbed by the hash was 'a' and function B when the letter was 'b', and so on. |