Password entropy match for alphanumeric but there are special characters in password

Question

I have a problem cracking some of the fundamentals on passwords' entropies. Namely: I have read this article about a guy cracking DKIM of Google (maybe more noticing that the keys are only 512 bits)

Then I have tried checking it whether it is really 512 or something longer etc. I have finally came up with Wikipedia page http://en.wikipedia.org/wiki/Password_strength#Random_passwords that would explain to me how length of a key is computed.

So using the table provided in there I compute examplar key: jL/Dw06dEEleG8YQSm0ZmlMVoDzfy2g4cDWA/NceLTocnDRzh3zpfQX91IRnu7qNAaao23+0E0nFT3NnfGuyS7gC7f17vGZQJ2IhsW/xrJ/LQ77ogGf/dbaCLHX016mmSmNXq4oPfsoLwnO8MjnP3kj341mDNf5750WlpNPNrV2e/7ZBImBt8ZxFGMe6fXjQVlzzU2MYE+JOs1bF8KisU1sbi+kzdq8NP8qz+dvdAxbXez/7C57yPXZhkqf8iWO8Hn7y/n2ekcDXE+9bYK5cPiOZY0eUwd1odNRF7FhmuCBIkO6LjF9/373sGIw/6fcJQ7plyhE1ExooM7j9H7FUuw==

344 characters long.

From the wiki table we have

Where, L is the length of a password with desired copmlexity (entropy) H and N is the number of symbols in the set that we are working in (e.g. 62 in alphanumeric or 95 of ASCII printable characters).

So my question here is : for complexity 2048 bits, alphanumeric characters I get :

L = ~~ 344

where this is ours hash's length, so why are there / and + and = in the password. Is this because it is coded with base64 ?

PS

If I try to decode this key with base64 and ASCII charset then I get some rubbish

NI^JmS<h8p5-:4s|}gIOsg|kK{fP'b!oCgu,uJcW~s29HY5{E]A"`mE}xV\ScNVS[3v
?{?=vac~}[`\>#cGhtEXf H_?   Ce5(3T

What am I doing from here ? As far as I know no hashing functions returns special characters.

Answer 1

The key is Base64 encoded.

Base64 encoding allows data to be stored as ASCII, because the output of that encoding only uses a-z, A-Z, 0-9, / and ., with = for padding. The "rubbish" you see is the ASCII representation of the raw bytes of the key.

Your entropy analysis is therefore very close to correct, because the character set of the data is 64, not 62. If we do the math, log2(64) is 6, which makes the ideal length for 2084 bits of entropy 341.333 bytes. Since you can't store 0.333 of a byte, we can assume that the ideal length of the base64 encoding of any data with 2084 bits of entropy is 342 bytes. Now notice that there are two padding characters on the end of the base64 string, which means that the real length is actually 342 bytes. As such, we've just proven that the key has ideal entropy.

Answer 2

Base64 encoding is just a trick by which arbitrary bytes are encoded into characters which can be written everywhere "text" is supported (e.g. in a TXT record in the DNS). Three bytes become four characters. You have 344 characters, which is 4*86, so this encodes 3*86 bytes, i.e. 258 -- but the two final characters are '=', which means that the two final bytes are to be ignored (they were added because the source data length was not a multiple of 3; that's just a kind of padding).

So this is the Base64 encoding of a sequence of 256 bytes, exactly. It so happens that Google's DKIM key is now supposed to be a 2048-bit RSA key; the main component of that key is a big integer of size 2048 bits (i.e. greater than 2²⁰⁴⁷, lower than 2²⁰⁴⁸), which, when encoded, has size exactly 256 bytes. That's what you observe, so that's fine.

(It is a RSA key: a mathematical object which is not meant to be remembered or typed by a human being. Thus, it is not a password.)