0.01BTC Monster puzzle - SOLVED

[MrFreeDragon]

Just to show again that I did not invent a monster but used a prototype. Of course it is not a classic space invader, but it exists and could be found in different stock images by key words "pixel monsters":


Changes: one more column to the center, one more pixel for every leg, eyes aligned with the mouth

Prototype monster available in these popular stock databases:
Stock #18930301 in vectorstock
Stock #105309653 in dreamstime
Stock #764317714 in shutterstock

[akkort]

Do the weakness #2 (revealed public key) no need to brute all 116 bits (2^116), and only square root of total length is enough --> 58 bits (2^58). However it is still very much to brute force. Assuming that the monster could be symmetric (116/2 = 58bits unknown bits only), it is enough to make only square root from 2^58 operations --> 2^29. This is possible to find very fast.

Exact. I created Giant Step hashtable for 2^29 symmetrical combinations. Then, check Baby Step for second half of picture, also 2^29 symmetrical combinations.
Border+one half = Giant Step
second half - public key = Baby step

Memory spent for giant step is about 6Gb, can be safe reduced to 3-4Gb. 20 minutes to build hashtable.
baby step takes about 2 minutes to find key.
BSGS can be used for keys up to 70-75 bits.

[LoyceV]

Just to show again that I did not invent a monster but used a prototype. Of course it is not a classic space invader, but it exists and could be found in different stock images by key words "pixel monsters":


Changes: one more column to the center, one more pixel for every leg, eyes aligned with the mouth

It was a nice puzzle and fun to try. I think the number of possibilities wasa tad high to manually find it though. As an estimate: say there are 100 more or less obvious pictures that can easily be found on the internet, each with a several details that can be changed giving at least thousands of combinations per image.

Exact. I created Giant Step hashtable for 2^29 symmetrical combinations. Then, check Baby Step for second half of picture, also 2^29 symmetrical combinations.
Border+one half = Giant Step
second half - public key = Baby step

Memory spent for giant step is about 6Gb, can be safe reduced to 3-4Gb. 20 minutes to build hashtable.
baby step takes about 2 minutes to find key.
BSGS can be used for keys up to 70-75 bits.

I'm impressed! Congratulations!

[math09183]

Do the weakness #2 (revealed public key) no need to brute all 116 bits (2^116), and only square root of total length is enough --> 58 bits (2^58). However it is still very much to brute force. Assuming that the monster could be symmetric (116/2 = 58bits unknown bits only), it is enough to make only square root from 2^58 operations --> 2^29. This is possible to find very fast.

Exact. I created Giant Step hashtable for 2^29 symmetrical combinations. Then, check Baby Step for second half of picture, also 2^29 symmetrical combinations.
Border+one half = Giant Step
second half - public key = Baby step

Memory spent for giant step is about 6Gb, can be safe reduced to 3-4Gb. 20 minutes to build hashtable.
baby step takes about 2 minutes to find key.
BSGS can be used for keys up to 70-75 bits.

Interesting... But how (why?) does this reduction work 2^116->2^58?
Does it mean that if I have for example private key in a range 2^144 and if I know public key then problem is reduced to 2^77?
Willing to learn more about it ;-)

[akkort]

Interesting... But how (why?) does this reduction work 2^116->2^58?
Does it mean that if I have for example private key in a range 2^144 and if I know public key then problem is reduced to 2^77?
Willing to learn more about it ;-)

For that key is more suitable Pollard's Kangaroo method. At current time, it is still uncrackable in years.

[math09183]

Interesting... But how (why?) does this reduction work 2^116->2^58?
Does it mean that if I have for example private key in a range 2^144 and if I know public key then problem is reduced to 2^77?
Willing to learn more about it ;-)

For that key is more suitable Pollard's Kangaroo method. At current time, it is still uncrackable in years.

Yes, of course; it was just an example - to see the possible approach.
It means that exposing public key changes really a lot...

[sukbir]

Congrats akkort

Do the weakness #2 (revealed public key) no need to brute all 116 bits (2^116), and only square root of total length is enough --> 58 bits (2^58). However it is still very much to brute force. Assuming that the monster could be symmetric (116/2 = 58bits unknown bits only), it is enough to make only square root from 2^58 operations --> 2^29. This is possible to find very fast.

Exact. I created Giant Step hashtable for 2^29 symmetrical combinations. Then, check Baby Step for second half of picture, also 2^29 symmetrical combinations.
Border+one half = Giant Step
second half - public key = Baby step

Memory spent for giant step is about 6Gb, can be safe reduced to 3-4Gb. 20 minutes to build hashtable.
baby step takes about 2 minutes to find key.
BSGS can be used for keys up to 70-75 bits.

[MrFreeDragon]

Do the weakness #2 (revealed public key) no need to brute all 116 bits (2^116), and only square root of total length is enough --> 58 bits (2^58). However it is still very much to brute force. Assuming that the monster could be symmetric (116/2 = 58bits unknown bits only), it is enough to make only square root from 2^58 operations --> 2^29. This is possible to find very fast.

Exact. I created Giant Step hashtable for 2^29 symmetrical combinations. Then, check Baby Step for second half of picture, also 2^29 symmetrical combinations.
Border+one half = Giant Step
second half - public key = Baby step

Memory spent for giant step is about 6Gb, can be safe reduced to 3-4Gb. 20 minutes to build hashtable.
baby step takes about 2 minutes to find key.
BSGS can be used for keys up to 70-75 bits.

Respect to you! Very elegant solution!
You did not use the locked front door to come in, but decided to enter through the side/back door 

-snip-
Yes, of course; it was just an example - to see the possible approach.
It means that exposing public key changes really a lot...

For 256bit keys nowadays it is not possible to find the private key with these bsgs/pollard methods. The world record at the moment is something like 114bit (and 117bit on FPGA).
But of course for better security it is better never reveal the public key from your address. HD wallets are well designed for this purpose - they generate new wallet  after every transaction and transfer the change to new address.

[pooya87]

Interesting... But how (why?) does this reduction work 2^116->2^58?
Does it mean that if I have for example private key in a range 2^144 and if I know public key then problem is reduced to 2^77?
Willing to learn more about it ;-)

For that key is more suitable Pollard's Kangaroo method. At current time, it is still uncrackable in years.

Yes, of course; it was just an example - to see the possible approach.
It means that exposing public key changes really a lot...

it really does not.
brute forcing has always been about reducing the space you need to search. having the public key only changes the method but it will never reduce the search space. you still have to search the 256 bit space by only having the public key.
this puzzle was possible to brute force because it first reduces the search space to 144 bits then reduces it a little more by the last hint down to 116 bits. and finally with symmetry the search space is reduced down to half that value meaning 58-bits.

[sukbir]

Hi MrFreeDragon, I did google search about Baby-step, Giant-step and Pollard method but I can't figure out how it works.
Do I need to have programming skills to learn about these thing

ffffc3c38001824187e18ff1cdb3dffbdc3bd66b93c9b81da8158001c3c3ffff

Nice job! Congratulations!

The monster was created based on this picture: https://www.vectorstock.com/royalty-free-vector/retro-pixel-space-monsters-vector-18930301
I just changed the legs (make longer) and add one column to make it symmetric and fit the orange space (as the most monsters had odd columns). So slight changes to the image were done.

I can say that there were some weaknesses (i.e. attack vectors) in this puzzle:
1) The picture was symmetric
2) The public key was revealed (through the posted signature)
3) Border decreased the total bits to find from 256 down to 116

Do the weakness #2 (revealed public key) no need to brute all 116 bits (2^116), and only square root of total length is enough --> 58 bits (2^58). However it is still very much to brute force. Assuming that the monster could be symmetric (116/2 = 58bits unknown bits only), it is enough to make only square root from 2^58 operations --> 2^29. This is possible to find very fast.

akkort, can you please share your method to solve this puzzle. Did you use baby-step-giant-step or Pollard method? Or did you just draw the picture and was lucky with it?
If you use BSGS method or Pollard, did you adjust the public key to fit exact 58 bits length (i.e. subtract the border public point from the puzzle public point) or make a special code for the exact border pattern?

PS. I remember I mentioned no programming skills are required to solve this puzzle. Actually it is truth - to draw a picture we do not need a program. Signing a message I revealed the public key of the address and "opened the door" for possible baby-step-giant-step/pollard attacks.

[math09183]

it really does not.
brute forcing has always been about reducing the space you need to search. having the public key only changes the method but it will never reduce the search space. you still have to search the 256 bit space by only having the public key.

You mean that reduction is purely theoretical because of 'birthday paradox', right?

[pooya87]

You mean that reduction is purely theoretical because of 'birthday paradox', right?

i am trying to point out that the reduction happened because this is a puzzle not a truly random private key.

[math09183]

You mean that reduction is purely theoretical because of 'birthday paradox', right?

i am trying to point out that the reduction happened because this is a puzzle not a truly random private key.

I agree, but MrFreeDragon wrote "Do the weakness #2 (revealed public key) no need to brute all 116 bits (2^116), and only square root of total length is enough --> 58 bits (2^58)."
 and this is part I do not understand.

[MrFreeDragon]

You mean that reduction is purely theoretical because of 'birthday paradox', right?

i am trying to point out that the reduction happened because this is a puzzle not a truly random private key.

I agree, but MrFreeDragon wrote "Do the weakness #2 (revealed public key) no need to brute all 116 bits (2^116), and only square root of total length is enough --> 58 bits (2^58)."
 and this is part I do not understand.

BabyStep-GiantStep method allows to perform square root of the total length operations. The puzzle address search range was reduced by border and "special non touching requirement" down to 116 bits (2^116). So to find any key (symmetrical or not) withing this range only 2^58 operations are required (but also you should prepare a hashtable before search). To be honest you will not have enough RAM to prepare the hashtable for 116 bit key.

Here the code for BSGS you can use to find keys with specific ranges: https://github.com/JeanLucPons/BSGS

I did not mention in puzzle rules that the hidden monster was symmetric. So, it could be only the assumption (but reasonable assumption). Assuming that the "monster" could be symmetrical means that only 116/2=58 bits are unknown, because the 2nd part of the monster is just a mirrored from the 1st part. Symmetry could be vertical or horizontal - so you should try both, but more probable symmetry is vertical.

Now for 58 bits with BSGS you need only 2^29 operations - this is easy just for 1 CPU to calculate.

Hi MrFreeDragon, I did google search about Baby-step, Giant-step and Pollard method but I can't figure out how it works.
Do I need to have programming skills to learn about these thing
-snip-

Google for "Discrete Logarithm Problem" and you can find a lot of researches and presentations. For better understanding try to start with available presentations, some of them contain all the methods and compare them with each other.

Also in order to understand how Pollard/BSGS methods work, start with elliptic curve understanding (private key --> public key; scalar additions/multiplication if public keys - these knowledge is important to understand DLP solving methods.