Quote from: PawGo on March 16, 2022, 01:06:51 PM

I must admit that until recently I was not aware of existence of mini-private-key format... I have found information about it accidentally and I decided to play a little with it.
So, just to recall some information:
The size of 'physical' items forced creators to find a way how to encode information about Bitcoin private key on a small area. Typical WIF, which has more than 50 characters would be too long. So, the new format has been created. Initially minikeys had 22 characters, later 30 characters. What is similar to WIF is that minikeys are build based on Base58 characters - that format excludes characters which looks similar to other, what could be problematic for user. That way, for example, characters like 'l' (lowercase L) or 0 (zero) and O (uppercase o) are excluded. Later, creators decided to exclude "1", so in fact the new format "base57" is used. And just a detail - minikeys starts with a letter "S".
The main difference between WIF and minikeys is that WIF encodes the exact private key, while minikey is in fact more like "brainwallet" phrase - the ways to restore private key is completely different. In case of WIF all we need is "base58 decoding" to retrieve information about private key (and additionally information if we had correct WIF, so decoded private key is really the one we look for). In case if minikey we must calculate hash of a key, just like we do with brainwallets.
What is also interesting, is that minikeys also has some kind of verification if input (the text found on physical item) is correct. Verification is based on fact, that not each combination of characters could be treated as a valid minikey - only when "extended" minikey produces hash which starts with "00" in hex.
All hashes on minikeys are sha256.
Let's take an example (we will work on short keys, 22 characters):
ScatCATcatCATcatCATcat
We must verify if key is correct, to get this information we calculate hash of key "extended" by appending character "?" (question mark).

Code:

sha256(ScatCATcatCATcatCATcat?) = 2dbe5cf8ac83725536cbb3d74a89dec34dd5c57af867431745449119f49788ec

Because hash starts with "2d", "ScatCATcatCATcatCATcat" cannot be used as a valid minikey;

SkK5VPtmTm3mQKYaJQFRZP

Code:

sha256(SkK5VPtmTm3mQKYaJQFRZP?) = 00442b142a40eefcd894b0bb6f19c58284f2e7248cee7e4910cd37afbfc7879a

Now we see that SkK5VPtmTm3mQKYaJQFRZP is a "correct" minikey. Then we may calculate hash to retrieve the real private key:

Code:

sha256(SkK5VPtmTm3mQKYaJQFRZP) = f30c1ddd12ea91bd35d5d1b83eac611717d99da826f207c3c3d4839e271648cb

That key gives uncompressed public key
04bf2d4231ca9ec2a49664f5b821bd44ad6cb38c6393936f1e3a6a8f4e0ee81686666e952387a4d d63a2ac7fb8c63737a9c4be142a186c1496d7013569c028143c
which produces hash160 fc258e14e4d1705f4c5a1f77e9a693531de82553
which could be converted into address 1PzEGi7a6UEGCAXtGjZj8kBX2VEHcLMrqd.

Now, let's ask how safe it is. I will focus on famous Cascascius coins - the list of coins (produced and already 'opened') is available online: https://casascius.uberbills.com/ and https://casasciustracker.com/
From serie 1, which was based on short keys (22 characters) and full base58, there are slightly less than 5000 coins still unopened.
I was aware of only one tool to brute-force minikeys and try to attack them knowing public addresses of coins - it was Keyhunt by @albert0bsd (https://bitcointalk.org/index.php?topic=5322040.0)
Just for fun and programming exercise I decided to prepare a small tool for "attacking" Cascascius, but using GPU. Working, but probably not extremely optimized program is available here: https://github.com/PawelGorny/MinikeyCuda
Program may work in two modes - random or sequential.
Sequential processing is very similar to typical WIF solving, where we change character by character and test the result. Initially we test if minikey is eglible for processing (if hash of key+? produces 00), then we hash again to generate the private key. Then we verify if private key produces address we look for. Statistically every 1/256 minikey is "correct" and produced private should be tested.
On my dev card rtx3060 I have performance of about 8mln keys/s, which gives around 30k/s 'valid' keys,
Random mode works quite differently - using GPU we produce bunch of 'valid' keys and then we check all of them. That way we may check much more keys, but we are not able to verify if we do not have duplicates. The corresponding performance is about 600-750k/s.
But what is the possibility of successful attack? Let's calculate:
For short keys, we have 58^21 possibilities = 1,076435e+37. As statistically 1/256 keys are valid, we must test 4,204824e+34 keys.
If we are able to test 500k/s and we are sure we will not have duplicated work, we need:
1 401 608 248 902 228 061 589 725 886 minutes, which gives 2 666 682 360 925 091 441 380 years (if I am not mistaken) to test all the keys.
Calculations for longer keys (30 characters) are left to the reader.
In other words - if you are in the possession of one of coins, I think you may sleep safe.

But if (I have no idea if situation like that may occur) you have lost part of your key, 6-7 characters, maybe more - it would be possible to recover it.

Has anyone downloaded this repository? https://github.com/PawelGorny/MinikeyCuda
it disappeared from github. If you downloaded it, send it to my email: cassiosamasr@gmail.com thanks

AbadomRSZ

Posts

Merits