Thank you for the thoughtful analysis Raid. The hash and salt are both known to the attacker :) It looks like I'm going to have to settle with confounding efforts by the man via increased hash computation cost.
-Travis On Mon, Aug 10, 2009 at 6:53 PM, <[email protected]> wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > Travis, > > On Mon, 10 Aug 2009 22:50:32 +0200 T Biehn <[email protected]> wrote: >>I don't have control over the set. Sorry I wasn't more explicit >>about >>this. Although, it should have been obvious that the solution >>needed >>to satisfy the conditions: >>Data to one way hash. >>The set has 9,999,999,999 members. > > if these are the only two conditions, I wonder why a static salt > does not satisfy your requirements? If the salt is not publicly > known, the procedure is secure in respect to the hash-function in > use... > > So, suppose the third condition is the salt may be publicly known. > > Suppose, we have plaintext (alphabet E, length of alphabet s = |E|) > with fixed length, say 'c' chars. So if you insert the salt at a > random position, there are c+1 possibilities for the position of > the salt. So the bruteforce attacker has to run c more tests than > having the salt in a fixed position. > > Comparing the two procedures under a theoretically view, there isnt > a significant difference in terms of runtime complexity: > > If the salt is not publicly known and at a fixed position, > complexity (means: number of possible plaintexts) is at O(s**c). > Your method only rises complexity by a constant factor: It's at O( > (c+1) * s**c). > > Theoretically this is negligible: If it takes me 2 hours to > bruteforce procedure 1 (fixed position), why bother about 20 hours > computing for procedure 2? > > Practically it depends on your overall requirements. > > Besides, your procedure lowers the latch for DoS... at least > slightly (same argument as above). > > So far, my two cents... > > raid > -----BEGIN PGP SIGNATURE----- > Charset: UTF8 > Version: Hush 3.0 > Note: This signature can be verified at https://www.hushtools.com/verify > > wpwEAQMCAAYFAkqApOoACgkQ/WWNsggjSSFjgAP/Wr/yus6Zf8e/nkegfMw4AeRS5Xz4 > GP91CUbwEEgy0qMsL7HvrAc7oo7dt5PpEZIePVkBF8ea9WeW9RlX1YK7ZlkkIP6ZLKx2 > XgT515eGNeTMbcKSmAOWlIkL4JtKRBxh7YLb0QP0yi3pCY7MGl4ZAtcGN25vx3Nkkq18 > WMoO6VQ= > =UN3m > -----END PGP SIGNATURE----- > > _______________________________________________ > Full-Disclosure - We believe in it. > Charter: http://lists.grok.org.uk/full-disclosure-charter.html > Hosted and sponsored by Secunia - http://secunia.com/ > -- pgp http://pastebin.com/f6fd606da pgp _______________________________________________ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
