0
$\begingroup$

My question is simple. I have a secret that is generated with a 10 byte long pseudorandom generator library (e.g. Java's SecureRandom), that in theory provides a security equivalent to $2^{40}$ (birthday bound). This secret is encoded afterwards (e.g. Base64). This is supposed to reduce entropy, while extending the string lenght.

If I want to brute force the secret, does the encoding have any negative impact on the protection? (in other words, does it facilitate the brute forcing at all?) My intuition is that the security is not affected, but I learnt to be extra cautious with this sort of things.

Improve this question
$\endgroup$
4
  • $\begingroup$ How do you figure the entropy reduction? Are you talking the reduced entropy rate of 8 bits/byte to 6 bits/character? $\endgroup$ – Paul Uszak May 1 '19 at 22:27
  • $\begingroup$ By the way, 'denigrate' means to say something is bad, but does not mean that description is correct. In fact something that is denigrated is usually in fact good. If you mean 'reduce', say 'reduce'. $\endgroup$ – dave_thompson_085 May 2 '19 at 1:15
  • $\begingroup$ Yes, I mean the entropy reduction in terms of entropy per byte: where there could be 256 possibilities before now this set is reduced. But of course, this increases the string length $\endgroup$ – user1156544 May 2 '19 at 7:04
  • $\begingroup$ You are right, @dave_thompson_085, perhaps I have not chosen the most accurate verb $\endgroup$ – user1156544 May 2 '19 at 7:06
3
$\begingroup$

A byte is 8 bits; 10 random bytes are therefore 80 random bits, which is $2^{80}$ equiprobable alternatives (not $2^{40}$), which is 80 bits of entropy. (Unless your 10 byte random string is actually an ASCII representation of a 40-bit hexadecimal value; since SecureRandom outputs full range byte[] I'll assume it's not that.)

This secret is encoded afterwards (e.g. Base64). This is supposed to reduce entropy, while extending the string length.

This "entropy reduction" isn't real. Any Base64 encoder is a one-to-one function—each of the $2^{80}$ inputs in your example is mapped to a unique output. There are therefore $2^{80}$ unique possible outcomes as well, each one equally likely, and thus 80 bits of entropy like originally.

What's probably confusing you is that the binary representation of the Base64-encoded string is longer than 80 bits, but it's not made of uniform random bits, so in that sense it's not a full-entropy string—the 14-ish bytes in the Base64 string are 112 bits long but would only collectively have 80 bits of entropy.

If I want to brute force the secret, does the encoding has any negative impact on the protection?

Not really. Again, $2^{80}$ possible outcomes, all of them equally likely.

Improve this answer
$\endgroup$
9
  • $\begingroup$ You are forgetting the birthday bound to calculate $2^{80}$, don't you? $\endgroup$ – user1156544 May 2 '19 at 7:00
  • $\begingroup$ Your answer is what my intuition says, and what seems correct (except from the fact that you are assuming more security - $2^{80}$ than what I think it has - $2^{40}$). Note that I have not accepted yet because I am looking for a potential smart answer that can state the opposite (in cryptography, many security breaks are counterintuitive) $\endgroup$ – user1156544 May 2 '19 at 8:03
  • $\begingroup$ @user1156544 80 bits of entropy provide 40 bits of security against collisions when applying the birthday paradox directly. They are still 80 bits of entropy. Collision attacks may, or may not, be relevant depending on the context of the protocol or algorithm being studied. $\endgroup$ – A. Hersean May 2 '19 at 9:14
  • $\begingroup$ Agree. That is why I never said it has an entropy of $2^{40}$ but a provided security equivalent to $2^{40}$. $\endgroup$ – user1156544 May 2 '19 at 9:39
  • $\begingroup$ @user1156544 It only provides 40 bits of security in few contexts. This result cannot be generalized like you do. Even the reduction to half the bits is just a rule of thumb and cannot be applied when one seeks a probability of collisions of 2^-32. $\endgroup$ – A. Hersean May 2 '19 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.