Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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...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.

$$ b109f3bbbc244eb82441917ed06d618\\ b9008dd09b3befd1b5e07394c706a8b\\ b980b1d7785e5976ec049b46df5f1326\\ 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.

$$1j5bcKq8KdvcwVJpuiJj3efBGh5oYSp\\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

$$1j5bcKq8Kd$$

a better password than

$$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.

share|improve this question
    
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? –  pg1989 Feb 18 at 23:42
2  
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. –  pg1989 Feb 18 at 23:48
1  
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. –  fgrieu Feb 19 at 8:29
    
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. –  RyanGrannell Feb 19 at 22:28
    
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. –  fgrieu Feb 19 at 22:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.