Topic: Brainstorm the next generation of minikey (Read 1155 times)

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?

Encrypted minikey is a great idea. Is it going to be added as an extension to BIP 38 (still in draft?) or will it be something new?

Especially interested in the tunable scrypt parameters. (Edit): Scrypt parameter options are a good idea, maybe one for low RAM/ low MIPS applications (i.e. POS/smart phones) too?

That is what this thread is all about.

https://bitcointalksearch.org/topic/m.3341985

there are three specific proposals in there and it coincidentally references BIP 38

The first and simplest is you dont need to outsource - just create a random 32-bit salt and use scrypt(iter=1), then delete the salt, your smart phone can easily create problems it cant solve then.

There is also a different way to outsource the work of redeeming a coin (so you could use a 46-bit salt and outsource to untrusted miners) something useful for litecoin miners to do.

Adam

I was thinking that that it would be a perfect thing to embed in the salt.  A flag or version code could optionally say, "The number in the salt is a hint that will save you (client) time from scanning blocks you don't need to scan".

And I agree that one may as well throw the whole kitchen sink into scrypt where available.  Can't hurt.  (I thought of that as I wrote "entropy" provided by the minikey creator as opposed to "factor" )

You could also add a date field to limit blockchain rescan on import. In my proposal (encryption of HD wallet root keys) it's a 2 byte field.

https://bitcointalksearch.org/topic/proposal-base58-encoded-hd-wallet-root-key-with-optional-encryption-258678

On top of that, the 4 byte salt, if it's anything like what it is in bip38, is more of a checksum. gmaxwell suggested to me that it's probably wise to include all other known fields into the salt that's used in Scrypt (increases entropy a bit). That way you could probably steal at least one byte from the checksum for use in the date field.

I am thinking of coming up with a new encrypted minikey spec for physical bitcoins and secure paper wallets.  I wanted to think out loud a bit, perhaps in case there are any really good ideas it could include that I haven't thought of.  I want to include the core features of BIP38 but then also fix what might be its shortcomings.

Here's what I am hoping it would be like:

• 30-character code that starts with P (so, 29 random characters)
• The ability for a person to create the minikeys without knowing the password (they have only an intermediate code which gives them some salt plus G*constant, the ability to know/compute constant remains with the person generating the intermediate code)
• Uses scrypt for hashing the password and deriving the private key
• Tunable scrypt parameters
• The ability for the costly scrypt step to be outsourced (eg by a mobile device, to a web service), without giving that service the key/factors or any advantage other than the single exception of being able to bruteforce the key without the cost of scrypt if they were to come into possession of the complete key independently
• Typo detection on the password, that requires all the expensive computation to be done to know whether the check passes or fails

This coding scheme would ONLY be useful for generating new private keys and bitcoin addresses, not for encoding existing/known ones.

Twenty-nine random base58 characters gives about 169 bits, which I on a whim would think to allocate as follows:
9 bits - typo protection checksum
32 bits - salt chosen by the person who knows the password
4 bits - represents the version and selects the scrypt parameters
124 bits - entropy provided by the minikey creator who doesn't know the password

I'm hoping to hear constructive criticism of the feature set as well as the bit allocation I've proposed.