Elias - On Tue, Aug 07, 2012 at 03:36:32AM +0400, Solar Designer wrote: > On Mon, Aug 06, 2012 at 11:27:45PM +0300, Elias Yarrkov wrote: > > I use a custom KDF. I intend to write about this manner of constructing KDFs > > later. The goal is to cause a high area*time cost for massively parallel > > brute > > force via ASIC, similar to scrypt. > > Please do write about this. > > It is curious how you deliberately use a narrow pipe for the expensive > component of the KDF (but not for the KDF as a whole). You'd need to > include some explanation/proof that this is safe (given certain threat > models).
Here's an attack: For each in a set of passphrases to be tested, compute the KDF value assuming that its expensive component returned 0, and test the keys. If no match found, assume that the expensive component returned 1 and repeat - and so on until either the key is found (which may be double-checked by computing the KDF fully) or the set of possible return values from the expensive component is exhausted. In your example, with the expensive component returning a 32-bit value, this attack will succeed after testing 2**31 possible values on average when there is in fact a correct passphrase among those tested, and it will fail after testing 2**32 possible values otherwise. This puts an upper bound on the cost, regardless of the (possibly configurable) cost of the expensive component. It also lets an attacker avoid the memory cost altogether (but pay for this with the processing cost of the algorithm above). The latter is fine if you're only concerned about area*time cost rather than also about preventing certain devices (such as GPUs) from being used for the attack efficiently. In fact, scrypt deliberately allows for a similar tradeoff: http://www.openwall.com/lists/crypt-dev/2011/07/01/2 Overall, I think that having a narrower-pipe expensive component in a KDF might be OK (especially if there are multiple invocations of such components per a full KDF computation), but 32 bits for the only expensive component is likely too narrow for some otherwise reasonable uses (cost settings). Alexander _______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
