I was starting to think down this road myself recently, and had some thoughts about starting back at the simplest solutions an wondering why they weren't effective:
Namely, for the situation of a paper wallet or physical object (coin, etc.) being created by someone else, why not use a HMAC_SHA256 function? That would look something like:
Client picks a password
p and a salt
S. Using HMAC_SHA256, with
p as the key, signing the message
S, an output hash
k of 256-bit length then becomes a private key for a Bitcoin address. The Client derives the public address
K, and sends
S and
K to the printer to be printed onto the physical wallet. When the client receives the (amazingly gorgeous!) wallet back, they can add
p to it before storing it safely, ensuring anyone who was in possession of it could easily derive
k from
p and
S, or leaving
p a secret, making it a "brainwallet" that only the client could unlock.
Variables summary:
- p Private password picked by client
- S Private salt, shared with wallet creator
- k Address private key, derived from p and S
- K Public address of k
This would be vulnerable to brute-force attack by the wallet printer (they need to crack
p since they know
S), or in the case of a paper wallet where
S is secret (covered by hologram or inside the physical coin), someone holding that paper wallet would need to crack
S since
p is visible on the wallet. Meaning the strength of
p and
S would need to be rather strong.
So, to prevent people from picking "puppies" as their password
p, what about employing
BIP39 for this? Make both
p and
S a random 128-bit number, which commonly is expressed in mnemonic form of 12 words. 128 bits is 16 bytes, which is 32 characters long expressed in Hex, which fits nicely in a 3-Q QR code (Version 3; 29x29 cells, Q-level error correction; 25% error recovery). The wallet can have a QR code for
S and/or its mnemonic or base58-encoded, both optionally covered by a hologram by the printer. The client then can print the mnemonic of
p on it, as above. 128-bits is the same strength as BIP32 and Electrum chain codes, which should be strong enough on their own, to resist a brute-force attack.
Alternately, make the bit-length of
p and
S smaller, and use Scrypt on the HMAC_SHA256 to ensure brute-forcing is still hard. If
p and
S were 64-bit, that would be a six-word mnemonic, 16 hex characters (fits in a 1-Q QR code; 21x21 cells), or 11 base58 characters. Would Scrypt parameters of something like r=8, p=1, N=1024 be a good starting point?
So, from your list of requirements, thinking
S is really the "minikey" in this scheme:
- 30-character code that starts with P (so, 29 random characters): No, this would be identifiable as a two-part key, both halves presented as a BIP39 (or similar) mnemonic.
- The ability for a person to create the minikeys without knowing the password: Unlike the current minikey scheme, this one doesn't require "mining" for one, but the creator only has half the key required to get k
- Uses scrypt for hashing the password and deriving the private key: Yes.
- Tunable scrypt parameters: Yes. The Scrypt calculation would be done by the client before requesting the wallet be created/printed, so could be whatever they want.
- The ability for the costly scrypt step to be outsourced: No.
- Typo detection on the password, that requires all the expensive computation to be done to know whether the check passes or fails: Yes to typo detection (BIP39 has a checksum feature), no to expensive.
- About 169 bits, 156 of it random: Two 64-bit half-keys would only be 128 bits of entropy, but that could be adjusted higher.
So, not a perfect match to your requirements, but very simple. The one other downside to this method is that if the client wants dozens of wallets created, they need to pre-calculate all them in advance (unlike, say the BIP38 using EC multiplication and a sequence of multiple addresses). As far as evaluating your requirements, I don't value the "outsourcing the Scrypt generation" as highly. I do think this simple schema could be improved by adding in metadata to indicate the Scrypt parameters used (as part of
p) and a flag as part of
S to indicate it is half a key (starting with some flag, like the 'P' you proposed; making
S best expressed in base58 rather than mnemonic), needing some
p to complete (and some hash/checksum of
p to pair them back up if separated). Having 156-bits of entropy I think is okay; I think it should be somewhere in the range of 128-160 bits (if 128-bits is okay for an Electrum/BIP32 chain code, I'd set that as the bottom limit).
Any glaring holes with this rather simple option?
