1
$\begingroup$

Does mapping a large character-set hash onto a small character-set hash lower entropy for a fixed size substring?

I'm writing a python app that involves generating passwords for websites. During the application I want to convert hexidecimal hashes to alphanumeric strings, and take the first twenty characters of the output. I want to convert to alphanumeric, because most websites at least support the upper-lower alphanumeric character set.

I surjectively map the larger character set of hexadecimal bytes $\{00...\text{ff}\}$ onto the smaller set of upper and lowercase alphanumerics $\{a...z, A...Z, 0...9\}$.

The mapping is done by recycling the 62 alphanumeric elements cyclically to correspond to each element of the 256 bytes

$$00 \rightarrow a$$ $$01 \rightarrow b$$ $$\vdots$$ $$0e \rightarrow 9$$ $$0f \rightarrow a$$ $$\vdots$$

For example, if the world's most secure password - "password" - is sha512 digested as hexadecimal it is unsurprisingly - $128 \times log_2(16) = 512$ bits.

$$ \text{b109f3bbbc244eb82441917ed06d618}\\ \text{b9008dd09b3befd1b5e07394c706a8b}\\ \text{b980b1d7785e5976ec049b46df5f1326}\\ \text{af5a2ea6d103fd07c95385ffab0cacbc}\\ 86\\ $$

Since each pair of hex-digits is mapped onto one alphanumeric digit, I assume the entropy of the resultant alphanumeric string is $64 \times log_2(62) = 382.5459$ bits.

$$\text{1j5bcKq8KdvcwVJpuiJj3efBGh5oYSp}\\\text{9 e1D6GB4YeFiLHtMZCUQxdfhpvjhVmWck}\\$$

The new string has half the length but ~75% of the entropy of the original string, so there is more per-character entropy in the alphanumeric projection, making

$$\text{1j5bcKq8Kd}$$

a better password than

$$\text{b109f3bbbc}$$

Have I made any invalid assumptions, or done the math incorrectly? Any insights into whether or not this surjective mapping is a good idea would be appreciated. If any clarification or edits are needed I'd be happy to make them - please leave a comment below.

Improve this question
$\endgroup$
5
  • $\begingroup$ Your re-encoding method is unnecessarily complex - why not just treat the hash output as an integer and convert it to base-62 using iterative div-mod? $\endgroup$
    – pg1989
    Feb 18, 2014 at 23:42
  • 2
    $\begingroup$ I.e. your hexidecimal digest is really just a base-16 integer. Use a base conversion function to express it as a base-62 integer, and use the first 20 characters of the resulting string. $\endgroup$
    – pg1989
    Feb 18, 2014 at 23:48
  • 1
    $\begingroup$ Likely $0e\rightarrow 9$ and $0f\rightarrow a$ is wrong, I guess $3d\rightarrow 9$ and $3e\rightarrow a$ is meant. The result of SHA-512 has 512 bits, but not 512 bit of entropy when the input is a low-entropy password. The transformation applied to 512 bits with full entropy would not quite give $64\cdot log_2(62)$ bit of entropy, for symbol $9$ is less likely than symbol $a$ is; I get $380.8\dots$ bit using the classic formula. The assumption that an alphanumeric password is valid fails for my email provider. $\endgroup$
    – fgrieu ♦
    Feb 19, 2014 at 8:29
  • $\begingroup$ pg1989 Good idea. I figured it would be easier to map the bytes directly; other languages I've worked with have patchy support for parsing hex and changing base. I've rewritten the function now with a base16 -> base62 converter @fgrieu I think you're right - I'll edit the example. I see that some chars will be more frequent than the last few in the charset: were you invoking Benford's law, or just the surjective mapping? I know some services won't allow alphanumeric, but frankly I avoid them. $\endgroup$
    – Róisín Grannell
    Feb 19, 2014 at 22:28
  • $\begingroup$ Not Benford's law, just the formula that I linked to, giving entropy of a random but biased source. With a true base-62 converter, the bias (which was already small) becomes negligible. My email provider wants 8 characters at least, including 2 letters, 2 digits, and 2 special characters, or something on that tune. $\endgroup$
    – fgrieu ♦
    Feb 19, 2014 at 22:44

1 Answer 1

Reset to default
3
$\begingroup$

In general, if a function $f$ has collisions, then it may reduce entropy: $$H[f(X)] \leq H[X].$$ The inequality applies to any notion of entropy—min-entropy, Shannon entropy, Hartley entropy, Rényi entropy, etc. This happens because if $f(x_i) = f(x_j)$ for $x_i \ne x_j$, the probability masses $\Pr[X = x_i]$ and $\Pr[X = x_j]$ both contribute toward the probability mass $\Pr[f(X) = y]$ where $y$ is the common value of $f(x_i)$ and $f(x_j)$. In particular, the min-entropy is $$-\log_2 \max_y \sum_{x \in f^{-1}(y)} \Pr[X = x].$$ Here the outputs with the most colliding inputs are $\{\mathtt a, \mathtt b, \mathtt c, \mathtt d, \mathtt e, \mathtt f, \mathtt g, \mathtt h\}$, each having five distinct inputs ($f^{-1}(\mathtt a) = \{0,62,124,186,248\}$, etc.), so in the best case, if $X \in \{0,1,2,\dots,255\}$ has uniform distribution, the min-entropy of $f(X)$ is $-\log_2 5/256 \approx 5.678$. For a string of independent inputs $X_1 \mathbin\| X_2 \mathbin\| \cdots \mathbin\| X_n$, the concatenation $f(X_1) \mathbin\| f(X_2) \mathbin\| \cdots \mathbin\| f(X_n)$ has min-entropy about $5.678n$. Thus a 64-character string from this will have at most about 363 bits of min-entropy.

Note that this is a bit less than a uniform random string from the same alphabet, which has $\log_2 62$ bits of entropy per character, or about $5.954n$ bits of entropy in a string of $n$ independent characters, which for a 64-character string gives about 384 bits of min-entropy as you calculated.

There are other ways to do roughly what you're doing:

  • Use base64. This is an injective map from octet strings to strings of $\{\mathtt a, \mathtt b, \mathtt c, \dots, \mathtt z, \mathtt A, \mathtt B, \mathtt C, \dots, \mathtt Z, \mathtt0, \mathtt1, \mathtt2, \dots, \mathtt9, \mathtt+, \mathtt/\}$ with optional padding. Of course, you can change the exact character set if need be to comply with mandatory and forbidden special characters.
  • Use rejection sampling. From the infinite stream $\operatorname{SHA512}(k \mathbin\| 0) \mathbin\| \operatorname{SHA512}(k \mathbin\| 1) \mathbin\| \operatorname{SHA512}(k \mathbin\| 2) \mathbin\| \dots$, take the acceptable octets (which encode, say, graphic US-ASCII characters) and reject the unacceptable ones until you have a password as long as you want.
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ To elaborate on the base64 thing and on $H[f(X)] \leq H[X]$: It's worth noting that if $f$ is injective then $H[f(X)] = H[X]$. If you apply a transformation to a random variable and that transformation is lossless (you can unambiguously relate any output back to its original input) then entropy is preserved. His example of base64, reader, is highlighted because its easy to implement. Not because it's a feature particular to base-64 encoding. $\endgroup$
    – Future Security
    Jun 20, 2019 at 21:04
  • $\begingroup$ And that's because, when a function is one-to-one, the set of probabilities associated with each potential value of $f(X)$ is the same as the set of probabilities associated with each potential value of $X$. Only the probabilities of each distinct outcome has an influence on entropy. The value of each outcome itself is irrelevant. That's why one-to-one transformations neither increase nor decrease entropy. $\endgroup$
    – Future Security
    Jun 20, 2019 at 21:14

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.