High security brainwallet

[Jace]

I'm contemplating on a better approach for brainwallets than just "private key = Sha256(passphrase)".
 
Right now I intend to use something like this:
 
Private key = Sha256¹⁰⁰(p) xor Sha3¹⁰⁰(p)

where Hashⁿ(p) = Hash(Hash(...n times...(Hash(Hash(p)+p)...+p)+p)

We're dealing with 256-bit keys here, so by Sha3 I mean Keccak-256.
 
My reasoning behing this approach:
 
1. I know PBKDF2, Bcrypt and Scrypt are stronger in terms of brute force resistance (depending on the work factor + Scrypt is also memory-heavy). Problem: I want something that also allows people to create brainwallets client-side with smartphones. Waiting a few sec is acceptable, 30 sec is not. A dedicated hacker will typically have thousands, or rather millions times more hashing power than Average Joe's mobile device. Hence I can't enforce too much performance requirements. My approach is supposed to be a reasonable compromise. By the way, my method is very PBKDF2-alike (with a fixed iteration count of 100).
 
2. I know it's typically better to use a HMAC approach instead of regular hashing, or something else that takes not just a passphrase but also some kind of salt or key. Problem: people will have to remember not just the passphrase but also a key, which probably over-complicates things. Deriving the salt or key from the passphrase seems like a reasonable compromise, which is also more or less what I'm doing in my approach. However, for people who can manage remembering both a passphrase and a key (or remembering a passphrase and storing a peusdorandom key in KeePass or whatever) I guess Hashⁿ(k,p) = Hash(k+Hash(k+...Hash(k+Hash(k+p)+p)...+p)+p) would be a viable alternative.
 
3. The way I'm stacking or nesting the hashing functions, that is H(H(H(p)+p)+p) instead of H(H(H(p))), is to enforce maximum entropy maintenance. As far as I know there is no known proof that reducing the input to 256-bit values, doesn't significantly reduce the output entropy, or that this effect may even stack up in multiple hashing steps. Re-including the input p at every step avoids this.
 
4. Xorring the Sha256 and Sha3 outputs effectively gives me more than the best of both worlds. If one of these hashing algorithms ever gets compromised (i.e. becoming vulnerable to a better-than-brute-force colission attack), such a vulnerability cannot be abused in my approach as the result is still scrambled with the other algo. And even if both algos get compromised, this probably still couldn't be abused as these attacks likewise require different input, so the attacks will typically be mutually exclusive.
 
5. Obviously it's a bad idea (less secure and just plain stupid) to invent your own cryptography solutions instead of using existing, tested, well known algorithms. So I'm relying on proven principles as much as possible.
 
Any thoughts?

[1713969511]

1713969511

[1713969511]

1713969511

[1713969511]

1713969511

[gmaxwell]

Average Joe's mobile device. Hence I can't enforce too much performance requirements.

What you're saying there is that you can't actually afford to do something useful with strengthening. No amount of gluing together hash functions can fix that. No one is likely to attack any kind of "brainwallet" based on non-uniformity of the hash function. Your complicated scheme will not meaningfully have security beyond that of SHA2/PBDKF2 with 200 iterations and no salt: not much at all.  Relative to the multiply with the generator your 200 hash iterations would be lucky to add a fraction of a percent to the complexity.

If you want somewhat novel cryptography Adam Back's proposal for cryptographically blind straightening is perhaps the most interesting. The mobile device can outsource the work to a fast external machine in an information-theoretically secure manner (though the straightening itself I think only has RSA-assumption limited security).

Ultimately being unable to have a salt gives any attacker a huge pre-computation advantage, if the system is widely deployed. So I think widely deploying such systems is irresponsible.

is to enforce maximum entropy maintenance

Key derivation without entropy waste is an actively researched area of academic cryptography: http://cryptolen13.wikispot.org/Yevgeniy_Dodis:_key_derivation_without_entropy_waste but in your case the hash function has hundreds of bits of state space compared to your tens of bits of key entropy, it's not likely a major issue for brainwallets.

5. Obviously it's a bad idea (less secure and just plain stupid) to invent your own cryptography solutions instead of using existing, tested, well known algorithms. So I'm relying on proven principles as much as possible.

High security brainwallets? A bitter-sweet and clearly misunderstood feature in my unbiased opinion, one which is conspicuously absent in current clients. Constructed using random order and guarded by military intelligence they give even odds against oxymoronic attackers, at least until they're found missing. High-security brainwallets are the only choice of the wise fool.