Are prefixes (after the first A,B,C,D character) more likely to be generated than a postfix?
GAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAnot legitimate addresses? What is the full ruleset for ed25519 strkey public addresses?
If the above all A account was valid, would it be just as likely as
GCQRXMSS6FBKF6OHLF4XWL6LDURPSPPRXDDGYZOGWQSOWT25542QUAXV? Basically, is each character in each location (except the first A,B,C,D) equally likely?
What is the time complexity for 4-character postfix, 4-character prefix, 5 character, 6 character ...
If it is known exactly/roughly when a vanity address was generated, is that address secure?
The public/visible encoding of keys is a format called "strkey" which is implemented here: https://github.com/stellar/stellar-core/blob/master/src/crypto/StrKey.cpp
It consists of a 1-byte type code, 32 bytes of public key, and 2 bytes of CRC-16, base32-encoded. So to answer your specific questions:
- After the first character (the type code) other prefixes are no more likely than others. For the public half of an Ed25519-type key, the first byte will always be 'G'. Presumably you're interested in a vanity value for the public half, not the private half ('S') because the private half is never supposed to be shared!
- No, AAAA...AAAA is not a valid address. The prefix byte and the suffix CRC in particular are not very flexible. Also the bytes in the middle have to be a valid group element of the 25519 curve, which not every byte string is.
- I don't know how to provide a formula for the probability of different base32 string representations of group elements, but I think you can roughly treat them as uniformly likely, as they're derived by multiplying a base group element by a securely-random private byte string.
- I just modified the code in stellar-core to generate vanity addresses out of curiosity and it appeared to take around 5-10 seconds of searching to reliably find a string with a given 5-character substring and 1-2 minutes with a 6-character substring. Trying to anchor at the beginning or end of the string is significantly slower. I suspect if you were dedicated you could write something to find them much faster -- this was a simple random brute-force experiment.
- There's nothing in an address that's at all related to its time of generation, besides the fact that a given random number generator is employed in generating the seed. So assuming the system RNG had decent entropy at the time of generation and didn't leak its state, and you've kept the secret half secure, any randomly generated key is as secure as any other.