This message was too old and has been purged

[Ritual]

Much appreciated mate, and thanks for your time. Be sure to PM me your BTC address after you post - I'll send what I can your way.

Rit.

[Evil-Knievel]

This message was too old and has been purged

[Evil-Knievel]

This message was too old and has been purged

[Ritual]

EK: That's OK I think by now most of us have realised that you're a mathematician rather than a teacher

No offense, but you're operating at a level higher than alot of us on this thread. We need a baby-level explanation, particularly if you're asking 2 BTC for this!

Having said that, you seem to be intelligent, organised and energetic about it, which gives me faith.

Please don't take this as a criticism of any kind - I kinda consider you my last hope for the missus' wallet!

Rit.

[Evil-Knievel]

This message was too old and has been purged

[FiatKiller]

What are the valid characters for a wallet password? Are specials allowed like "&%$!"?
I used to use alt-codes a lot to be a smarta**, like alt-255 which looks like a space, but isn't.
EDIT: found the list: (no zero, lowercase L, uppercase "oh", uppercase I)
“123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

EK, great explanation. I'm not clear on G though. Is it a fixed value?

[BurtW]

You do realize that the point n*G and the next point (n+1)*G are not physically close to each other on the curve, right?

Going through the sequence n*G, (n+1)*G, (n+2)*G, etc. results in a psuedorandom sequence of points on the curve.

What you decribed above is searching the psuedorandom point space hoping to run across one of your randomly placed marker points.

Or did I miss something?

Now to put some numbers on what you are attempting you said you want to generate about 10¹¹ points and test against those points.

To make the math easier let's give you 2⁴⁰ points and round up to 2²⁵⁶ possible points.

So for every one of your 2⁴⁰ known points there are 2^(256-40) = 2²¹⁶ unknown points.

Plus every time through your loop P_next = P_prev + G you have to check the generated result P_next against all 2⁴⁰ of your known points in order to see if you got lucky.  That will take some time no matter how clever you are.

[BurtW]

EK, great explanation. I'm not clear on G though. Is it a fixed value?

Yes G is a constant in the specification Bitcoins uses.  From the specification:

The base point G in compressed form is:

G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
 
and in uncompressed form is:

G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

[Evil-Knievel]

This message was too old and has been purged

[BurtW]

So you are clever in your point selection in order to make your comparison a bit faster.  

The smaller you make the common bits the more collisions you will get that require a time consuming full comparison, the larger you make your common bits the more costly your initial comparison.  Somewhere between 2²⁵⁶ and 2⁸ bits lies an optimal number of bits given how much you want to spend on your FPGA or ASIC hardware.

I already granted you the comparison can be done is a clever way to speed it up a bit.

This still boils down to a brute force attack.  A clever brute force attack but a brute force attack never the less.

[Ritual]

BurtW - well, that's kinda the point, isn't it? People want to know if the basic, impossible brute force-attack (20 billion years or whatever) can be reduced to something reasonable (say, a few months).

Is this the case here?

Rit

[BurtW]

All you need are these two numbers:

The number of known points (2⁴⁰ in the example so far)

The amount of time needed (on average, given a clever implementation) to compare the result of the N = P + G calculation to all the known points.

I think we can bascially neglect the time it takes to calculate N = P + G but that does take some time to do.

Given these two numbers we can calculate the time needed to crack any key.  The notion of "weak keys" is silly and is just introducing "luck" into the equation for no reason.

[BurtW]

BTW Evil-Knievel,

Are you going to pay this promised bounty:

https://bitcointalk.org/index.php?topic=427712.msg4902522#msg4902522

[itod]

All you need is these two numbers:

The number of known points (2⁴⁰ in the example so far)

Excuse if this is silly question because my understanding of this is very limited - but 2⁴⁰ is not a very big number, it's around 1 Terra. Since, to my understanding, Y coordinate is not very important because it is binary determined by the X coord and the sign +1/-1, there's only 32 bytes * 1 Terra = 32TB of data to check, which is well within range of todays disk arrays. This shouldn't be hard to check against, should it?

So, is this the correct explanation of the attack method:
- You need 2⁴⁰ X coordinates which have the 32 least significant bits matched to the X coord of the attacked public key, and all 2⁴⁰ with known private keys. That's what we've been doing in the other thread, collected 8 million of them in a few days
- You go through the sequence n*G, (n+1)*G, (n+2)*G ... (n+k)*G and check only those 32 bits for a match
- If you find a match, you check the X coord against the 32TB of data with known private keys
- If you find a match there you calculate found secret - k to get unknown private key
- If not you add 1 to k and repeat the process

Is this the correct attack vector? It looks too simple to me, I've must have misunderstood something.

[BurtW]

I think you got it.  That is my understanding also.

Assuming for now 2⁴⁰ known keypairs all we need is an estimate for the average comparison time given that some of them will be a short quick comparison as you suggested and others will be very long, having to do full comparisons.

Then we can easily calculate how long, on average, to crack a key pair.

[BurtW]

Storage needed for the public keys:

257 bits, 256 for the X coordinate + one bit for the sign of the Y coordinate BUT the bottom 32 bits are the same for all keys so we really just need a total of 257 - 32 = 225 bits each

Storage needed for the private keys:  256 bits each

So realistically we still need 64 bytes to store each known key pair

2⁴⁰ * 64 bytes is exactly 64 binary terabytes of data that needs to be stored - no big deal by today's standards.

But, have you ever tried to read 64 Tibytes of information from a disk drive?  Be sure to use SSDs for this as HDDs will be too slow for the full comparison operation

[itod]

So realistically we still need 64 bytes to store each known key pair

I disagree on that, you don't exactly need private keys to be handy, you need them only in the very rare occasion the attack was successful for the final printout of the found private key. They can be on the tape or something. Only the 1/2 of the data, 32TB with X coordinates have to be on the fast RAID.

[onzoom]

So realistically we still need 64 bytes to store each known key pair

I disagree on that, you don't exactly need private keys to be handy, you need them only in the very rare occasion the attack was successful for the final printout of the found private key. They can be on the tape or something. Only the 1/2 of the data, 32TB with X coordinates have to be on the fast RAID.
[/quote

32 TB on tape ? ]

[itod]

So realistically we still need 64 bytes to store each known key pair

I disagree on that, you don't exactly need private keys to be handy, you need them only in the very rare occasion the attack was successful for the final printout of the found private key. They can be on the tape or something. Only the 1/2 of the data, 32TB with X coordinates have to be on the fast RAID.

32 TB on tape ?

DAT 160 = 80 GB uncompressed (160 GB compressed)
DAT 320 = 160 GB uncompressed (marketed as 320 GB assuming 2:1 compression)

Cheep and ultra-reliable, you need less than 100 of them for this database. Whoever tries this in practice won't have a problem to buy 100 tapes.


Edit:
Just found out there are 6TB models now:
http://www8.hp.com/us/en/products/tape-drives-enclosures/index.html#!view=column&page=1
Had no idea that technology advanced so far in a few years.

[BurtW]

I was only giving total storage requirements.

Yes, you put the public keys in about 32 Tb of SSD and the private keys on 32 Tb of HDD.  32 Tb of HDD is not that much in the grand scheme of cracking ECC so forget the tape.