1
$\begingroup$

This string, "Au+u1hvsvJeEXxky" has a Shannon entropy of 3.75 and a length of 16.

The binary form of the string ( derived from Ascii-table ) is:

01000001 01110101 00101011 01110101 00110001 01101000 01110110 01110011 01110110 01001010 01100101 01000101 01011000 01111000 01101011 01111001

This string has a Shannon entropy of 1.39 and a length of 128.

So while both strings are interchangeable, their entropy differs. Why is that? And are both strings evenly strong in resisting a brute force guessing attack?

thnx.

$\endgroup$
  • 7
    $\begingroup$ An individual string does not have Shannon entropy. Only a probability distribution has Shannon entropy. $\endgroup$ – Mikero Jul 15 '18 at 15:56
  • 5
    $\begingroup$ @PaulUszak I can't tell if you're trying to be sarcastic, since in your other answer you seem to actually think that a single string has Shannon entropy. But yes, def decompress(s): return("Au+u1hvsvJeEXxky") is the "decompression algorithm" you are referring to, and you're right, s can be 0 bytes. $\endgroup$ – Mikero Jul 16 '18 at 0:09
  • 5
    $\begingroup$ Nothing can be said about the strength of a string to resist a brute force attack. (Spoiler: I can guess your string with 100% success in one try, because I already know it.) If you want to study an adversary's probability of success, or expected cost for a successful attack, you have to make the adversary have some uncertainty about it, and you have to quantify the adversary's uncertainty. What are all the possibilities? Will the adversary weigh some possibilities with greater plausibility than others? $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 0:15
  • 4
    $\begingroup$ @PaulUszak Do you usually count the size of /usr/bin/gzip when you measure the size of a compressed file? If you care about the length of a decompression algorithm, then you are talking about (some variant of) Kolmogorov complexity, not Shannon entropy. $\endgroup$ – Mikero Jul 16 '18 at 0:17
  • 4
    $\begingroup$ @PaulUszak If the recipient of a telegram knows a priori that the telegram will always contain Au+u1hvsvJeEXxky, then indeed, the telegram can be compressed into exactly 0 bytes. Mikero gave a program that the recipient can run to recover the original message on receipt of a telegram. (Note that the program is not included in the telegram—only some encoding of the message is.) However, this is not a very useful system for sending messages, because you can't send any message other than Au+u1hvsvJeEXxky. $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 0:18
3
$\begingroup$

I'm going to telepathically make a wild guess.

My wild guess is that you generated the string Au+u1hvsvJeEXxky by asking a computer to choose sixteen characters independently and uniformly at random from the alphabet consisting of a-z, A-Z, 0-9, +, and -, which is, coincidentally, the base64 alphabet.

The distribution on individual characters has 6 bits of entropy per character. The distribution on strings of sixteen characters chosen independently from this distribution is sixteen times that, namely 96 bits of entropy per string.

If I, as the adversary knowing this information about your process but not knowing the particular outcome, tried to guess your string, I would have a $1/2^{96}$ chance of getting it right. If I kept trying guesses, the expected number of guesses before I get it right—that is, the average of number of guesses over all possible values of your string—is $2^{95}$. That's a lot of guesses.

However, as the adversary, I often have more powers than that. Often, what I have is some hash of your string $H(s)$, and not just yours but $H(s_0), H(s_1), \ldots, H(s_{9999})$ of ten thousand different users who all used the same process. My goal as the adversary is to find at least one of the strings $s_i$—chances are if I can get a foothold by compromising one user, I can use that to compromise more users in a network.

If I do this intelligently, the cost of my attack—measured in joules, or USD, or EUR—is significantly less than $2^{95}$ times the cost of testing a single guess by evaluating $H$. With the help of Oechslin's rainbow tables, if parallelized $p$ ways, at least hundred million, I can share work between attacking many targets at once, and it will cost only about $2^{82}$ evaluations of $H$, in the time for about $2^{82}/p \leq 2^{56}$ sequential evaluations. The Bitcoin network spends this cost in about a year; $2^{56}$ nanoseconds is about two years.

That's a high cost, and a long time to wait, but it's absolutely within the budget of a major corporation or government. I would recommend making sure that the cost is around $2^{128}$ evaluations of $H$ so that it is completely out of reach of foreseeable human engineering. There are three ways to do this:

  1. Have every user choose from ${\geq}2^{256}$ possibilities uniformly at random. For example, instead of sixteen-character base64 strings, use forty-three-character base64 strings. Or use sequences of twenty words chosen independently uniformly at random from a word list of 7776 words.

  2. Store a salt unique to each user, and use $(\sigma_i, H(\sigma_i, s_i))$ where $\sigma_i$ is the $i^{\mathit{th}}$ user's salt and $s_i$ is the $i^{\mathit{th}}$ user's secret. This thwarts rainbow tables and prevents the adversary from sharing work between multiple users.

  3. Use a password hash that is costly to evaluate like scrypt or argon2id.

Method (1) is something the users can do. Alternatively, the computer can choose the user's secret for them, and ask the users to remember it. Methods (2) and (3) are things that whatever uses the secrets can do—something that the engineers of an application can put into their system to defend it against brute force attacks even if some users choose secrets poorly like human-chosen passwords.

All of the numbers above are premised on the model I telepathically guessed. Not everyone guesses the same model. The ent utility suggested by Paul Uszak and an entropy calculator on the web suggested by conchild instead guess the following probability distribution on symbols: probability 1/8 for u and v, probability 1/16 for {+, 1, A, E, J, X, e, h, k, s, x, y}, 0 probability for any other character. They suggested this by (a) counting the number of appearances of each character in your string, and (b) dividing by the length of your string. I, instead, used knowledge of common protocols on the internet to guess that you are using the base64 alphabet. We all assumed independence between characters. But nobody here knows anything about the process you used.

$\endgroup$
  • 1
    $\begingroup$ The simplest possible model is that the symbols (or sequences of symbols) are independently drawn from a single probability distribution. For the purpose of calculating an estimate of the source entropy (the problem at hand) there is no need to complicate the model by considering other factors. $\endgroup$ – conchild Jul 16 '18 at 2:54
  • 3
    $\begingroup$ @conchild From which probability distribution, and why? I pulled one out of my cloaca. I'm not saying it's the right one—it's a telepathic guess, after all, which means it's a load of balderdash—but I aimed here to provide (and justify) the quantitative tools to assess the security consequences of any distribution on the cost of brute force attacks, and used the distribution I guessed as an example. What is the complication you're concerned about? $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 3:03
  • 1
    $\begingroup$ Entropy estimates are useful in practice. Are you able to comment at all on useful approximations? Do you believe that the OP question is under-specified? You seem to be stuck, not knowing how to proceed, without a precise definition of the model. $\endgroup$ – conchild Jul 16 '18 at 15:57
  • 2
    $\begingroup$ @conchild Entropy estimates based on samples without a model for how they were generated are harmful in practice because they give a false sense of security and profoundly mislead people who don't understand the critical point that they work by positing and attempting to fit a naive model. If there's no probability distribution—if there's only the one string Au+u1hvsvJeEXxky—then there's no security. $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 16:09
  • $\begingroup$ @conchild There are plenty of useful approximations involving entropy. but they are meaningful only if there is actually a probability distribution that has entropy. Examples: (1), (2), (3). $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 16:12
2
$\begingroup$

Shannon entropy is a property of a random variable. It is defined as

$$H = -\sum_i^n {p_i \log_2 p_i}$$

where $p_i$ is a non-zero probability for each possible outcome. Note how the equation doesn't quite make sense for a single possible value. When people say a string (a password, message, or file) has a certain entropy they mean the string was sampled from a distribution with that entropy. This is just informal shorthand. Strings and values do not have entropy themselves.

Two different processes with two different probability distributions can produce the same output with different probabilities. It is incorrect to say a string has a certain amount of entropy with no context. There is no way to tell if a string posted on the internet has a certain Shannon entropy or min-entropy.


Example: If I tell you I rolled 6 twenty times in a row on a six sided die then I cannot ask you to tell me how much entropy is in a single roll of the specific die I used. It could be the case that the die is highly biased towards six, meaning it has relatively low entropy, or it could be the case I used a fair die and this outcome just happened by chance. (In which case it's not special despite the fact that it looks like I'm lying about the results. By definition this outcome is just as probable as every other list of twenty rolls I could give you.)


If you apply a lossless transformation to a random variable, you do not change the entropy of the result. If one outcome has some probability then the transformed outcome has the same probability.

If I'm using shorthand and each of the following are different encodings of the same 24 bit value, then I can say each string has equal entropy.

01000001 01110101 00101011

Zero One Zero Zero Zero Zero Zero One Zero One One One Zero One Zero One Zero Zero One Zero One Zero One One

ABAAAAAB ABBBABAB AABABABB

THTTTTTH THHHTHTH TTHTHTHH

Tails Heads Tails Tails Tails Tails Tails Heads Tails Heads Heads Heads Tails Heads Tails Heads Tails Tails Heads Tails Heads Tails Heads Heads

HTHHHHHT HTTTHTHT HHTHTHTT

Heads Tails Heads Heads Heads Heads Heads Tails Heads Tails Tails Tails Heads Tails Heads Tails Heads Heads Tails Heads Tails Heads Tails Tails

Whatever source told you that the two strings have different entropy is wrong. Either you mean the were generated the same way, only differing in the final encoding they use. (In which case the should have equal entropy.)

Or we just have these two """equivalent""" strings but we know nothing about how they were generated. Then we must say that we don't know what entropy they have. (Or more properly, that we don't know the entropy of the process used to generated those strings.)

I am guessing you used an online calculator to determine entropy. Those cannot determine the entropy of a (process that generates a) string as I already explained. The results of such calculators are not usable.

Or you may have used some formula that estimates the entropy in normal English prose or in a password as a function of the length of the string (and maybe some other details). This has the same problem as the online calculators.

$\endgroup$
-5
$\begingroup$

You may have seen an equation similar to:-

$$ H = -K\sum_{i=1}^n {p_i \log p_i} $$

It comes from Shannon's A Mathematical Theory of Communication, 1948 and is the classic definition of information entropy. The cryptographic security notion of entropy is different to this, but your calculations are based on Shannon's classic definition (Note 1.). Ignore the scalar K for this question, but feel free to follow up in Shannon's work.

What you will not have seen much of on this site is the definition of $i$. This is the crux of your question, and why Shannon entropy is tricky to measure accurately. $i$ relates to the alphabet used, and even that is confusing as the alphabet may be over multiple characters, such as "qu" in English. Bits, bytes and words may the tallied differently and produce different entropy measures.

To demonstrate my answer with a more substantial dataset, consider a 4 MB file of sequential 32 bit integers from 0 $\rightarrow$ 999,999. Measure it's entropy using different bit widths for $i$:-

i (bits)         Hrate (bits /byte)    Htotal (bits)
  1                    7.1                 28M
  8                    6.3                 25M
 32                    3.5                 14M            
 ???                 0.0031              12,464

where ??? is unknown as Htotal was obtained via a proprietary compression algorithm (paq8px_v112). This example effectively changes the alphabet (read $i$) used in digesting the file, just as the question does with a swap to ASCII. Compressors exploit correlation over many bits, and thus the resultant measure is so small. But the result is as expected, in that the entropy of the first million integers is clearly low.

Anyway, that's why your entropy numbers come out differently.


Note 1. This subtle distinction in entropy definitions will cause us all problems. Some commentators will suggest that your strings do not have any entropy whatsoever, in contrast with accepted information theory and Shannon himslef. A good example of entropy measures of fixed text is this entropy rate graph from Thomas Schürmann and Peter Grassberger, Entropy estimation of symbol sequences.

entropy

$\endgroup$
  • 3
    $\begingroup$ As usual, Shannon's definition of entropy is a property of a probability distribution, not of a possible value it can take on. What the ‘entropy estimation’ tools do is attempt to fit a model that might have generated the data, like a linear regression, and then compute the entropy of _the model_—not of the data, which is nonsensical. The index $i$ ranges over all possible values in the probability distribution, like all 16-byte sequences—not over the indices of bytes in a single fixed 16-byte string. $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 0:05
  • 1
    $\begingroup$ The ent utility, rather than consulting with knowledgeable elders at a moot in the woods like the name suggests, attempts to fit a model that might have generated the data, and then computes the entropy of that model. The model is very simple: for each position in the string independently, a character is drawn from a distribution assigning to each character $c$ a probability $p(c)$. The probabilities in the model that ent fits are derived from the original input string: $p(c) = \#c/\ell$, where $\#c$ is the number of occurrences of $c$ in the input string and $\ell$ is its length. $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 1:03
  • 1
    $\begingroup$ The model that ent fits from this input includes the string Au+u1hvsvJeEXxky as we should expect, but excludes other strings like pH0W14rmQsY-Rn0F, because, among other things, the symbol p does not appear in the original string. This model doesn't mean much. It is an ad hoc construction to spit out a number that bears little resemblance to an actual study of the process that generated the string—which is to be expected because merely examining a single output from that process with no prior knowledge about the process can't tell us much about it. $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 1:08
  • 1
    $\begingroup$ The number printed by ent is the entropy of the model $p(c) = \#c/\ell$, where $c$ is each character in the original input string, $\#c$ is the number of times it appears in the original input string, and $\ell$ is the length of the original input string. In that model, an optimal encoding could on average compress telegrams generated using that process by 53%, e.g. by using an optimal Huffman code. Is that model the actual process that joop s used to choose the string? Probably not! Other models will have different entropy, like uniform random strings in the base64 alphabet. $\endgroup$ – Squeamish Ossifrage Jul 16 '18 at 1:38
  • 1
    $\begingroup$ This is a perfectly good answer. $\endgroup$ – conchild Jul 16 '18 at 2:32

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.