Quote from: Jean-Luc on December 10, 2013, 09:53:11 PM

I started writing this post in reply to http://nextcoin.org/index.php/topic,471.msg3484.html#msg3484 , only to find that the thread has been locked before I was able to post it. So copying it here:

Quote from: Come-from-Beyond

transactions.nxt still contains public keys data.

Then I am correct, you need at least one outgoing transaction before the full public key of an account is stored in transactions.nxt. After that, the full 256 bits are used. But before any outgoing transactions, it is physically not possible for the network to know the account public key - let's say I generated an account using the vanity generator, and gave the account number to someone to send me money. I have never entered my password in the client yet, the account public key could not possibly be known to the network yet.

One other thing I want to point out, the maximum possible password length is irrelevant when trying to evaluate the risk of collisions. Of course, if you use 100000 character passwords, the number of collisions will be enormous. However all that means is that you don't need a 100000 character password. To determine the brute force resources required to find a collision all that matters is the total number of different accounts possible - which currently is 2^64 if you compare account id only, or 2^256 if you compare the full 256-bit public key. Second, it matters how long it takes you to calculate an account number given a password. You cannot indeed compare with bitcoin and the sha-256 hashing power of the bitcoin network, because in addition to sha-256 Nxt is using curve25519 - and there are no asics that calculate that (actually... I don't know, the bitcoin mining asics certainly don't, but who knows what type of hardware NSA has).

Assuming a perfect distribution, you need to try 2^64 different passwords to generate all possible 2^64 account numbers (ignoring the full-public key comparison). So how fast can one do that? On my laptop, with the Vanity.java code I posted on bitcointalk, I can go through 8000 passwords per seconds. This means it will take me 2^64/(8000*3600*24*365) = 73,117,802 years to generate all possible account numbers and have a 100% certainty that the one I am after has been found. Somebody doing this exercise of course will not be after one account only, but would be creating a rainbow table to be used against any account created now or in the future. But try to estimate how much storage space this rainbow table will require...
And that's only for accounts which have only ever received transactions, with no outgoing transactions. Once you send money from your account, its public key gets known to the network, so the account is protected to 2^256 against collisions - try the above calculation now again.

Nxt has different types of transactions. For example, extended payment (not implemented now though) will include all 256 bits of the recipient. So rainbow tables is just a waste of time.