0

I'm a beginner in Information Security and am learning about salting. Unfortunately, most of the time I have to learn by myself since the lecturer doesn't provide deep explanation on these. I now have to solve some problems related to this and having trouble understand how salting slow down the attack

An access control system requires users to choose a password on an alphabet of size 96 (without special characters in ASCII). If we want users to remember a password of length 4, but remain the security level of the system as if we are using a password of length 7, how many salt bits should be used?

My attempt: I know that if we use a salt bit string of length k, the attack speed will be slown down for 2^k times since the number of possible passwords to test increases 2^k times. I thought the number of salt bit we need to use is 3, but the answer is ceil(3*log96). Why is that?

I'll be very appreciative if somebody can give a clear explanation about this.

3 Answers 3

1

but remain the security level of the system as if we are using a password of length 7

Each character can have 96 different possibilities, and the it should be as if we are using a password 7 characters long. So, this is 96^7 different possibilities, which is 7.5144748e+13 possibilities. To convert this to base2, we take the log(base 2) of the above number, which gives us 2 ^ 46.09. So, a password of 7 characters in length, where each character can have 96 different possibilities, has an entropy of 46 bits.

If we want users to remember a password of length 4,

Applying the same logic above, this is 84934656 different possibilities, or 2^26.33 possibilities, or an entropy of 26 bits.

So, the salt has to increase the entropy by 20 bits (from 26 bits to 46 bits). This is equivalent to the answer that you posted. You could have arrived at the same answer in a more direct way, by converting everything to bits from the beginning and using rules of mathematics that apply to logs, but hopefully doing this way is more illustrative.

1

(This isn't the literal answer to your question, but provides context for you and others to understand why the question itself is somewhat incomplete for the problem space.)

A truly complete answer to this question should answer the local mathematical question first, and then expand to explain why that simple answer is insufficient (and really, that the question itself is misguided; choosing a proper salt length should be totally independent of password length.)

Separate from the local entropy question (addressed in other answers), there is also the question of global entropy. Understanding why requires some background information.

The question does not explicitly state what password-hashing algorithm is being used, but since the discussion is about selecting a salt, we're already talking about a bespoke/custom algorithm (rather than one that is designed for password storage, which already includes and automatically generates an appropriate salt).

So the underlying assumption is probably that the hash algorithm in use here is a natively unsalted one - such as MD5, SHA1, SHA256, etc. These are poor choices generally; and specifically as it relates to salt sizing, resistance to offline bruteforce attack of such a hash is marginal at best, but there are nevertheless some improvements that can be made.

Specifically, the goal of salt sizing for such a hash should be not only to ensure that no two local users have the same salt, but also that no two global users have the same salt - across any platform, anywhere. In other words, the goal of salting isn't just generally to increase entropy but specifically to increase resistance to precomputation.

This is so that an attacker can't get an automatic "free" crack by finding an already cracked instance of that hash+salt, in private precomputed rainbow tables, attack lists, and/or one of the corpora of all public known hashes and their associated cracks (such as those on hashes.org).

The math for an upper-bound defensible answer for this depends on your assumptions: how many global users are there, across how many platforms, and assuming that (worst case) they're all using the same hash type. Some hash types like vBulletin have salts that are utterly overkill - 30 characters from the 95-char ASCII space. Back of the napkin, I'd expect a 12-char salt in the 90-character range (no colons or spaces for hash processing/compatibility reasons) to provide "enough" reasonable global uniqueness - but Your Math May Vary. :D

Hashes like bcrypt, scrypt, etc. already have salts large enough to accommodate a global, cross-system attack surface like this, by design. But they also have other features (workfactors / rounds / stretching) that make them more suitable for password validation (slow for the attacker).

1
  • 1
    To put it more succinctly, if it's an online attack the system will add the salt for you, so it doesn't add to the strength of the password, if it's an offline attack you'll know the salt anyway. The question is bad. Commented Dec 24, 2020 at 19:14
0

I thought the number of salt bit we need to use is 3, but the answer is ceil(3*log96).

The salt must stand for 3 characters and not 3 bits. Since each of the characters can be one of 96 the bits needed to represent a character are log(96) (with log being the logarithm base 2). The minimal number of bits needed to represent these 3 characters is those 3*log(96). And since there are no broken bits it needs to be rounded up, i.e. ceil(3*log(96)).

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .