- there is no "adding a salt"
Of course there is. As you said, it's an inherent part of the algorithm. But never put it beyond some people to use a trivial salt (or use the same one for all users)
"because each one is initialized with a completely different public salt"
If they follow the proper procedures, yes, building a lookup table is impossible.