1
$\begingroup$

Given an entrophy of 1.5 bits per character, how long does a passphrase have the be to guarantee a key strength of a 128 bit random key?

Assuming an alphabet of 26, one character takes log2(26)=4.7 bits to be represented. Given this entrophy of 1.5 bits per character, can one simply answer this by:

(128/4.7) * 1.5 = 40.85

Meaning that the passphrase will have to be 41 characters long to guarantee key strength?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Check your math. If you know the amount of entropy per character, you don't need the number of bits to represent a single character to compute the required length (in characters) of the passphrase. $\endgroup$
    – Henrick Hellström
    Apr 8, 2013 at 16:59
  • $\begingroup$ This Wikipedia article is a good resource. $\endgroup$
    – hunter
    Apr 8, 2013 at 18:06
  • $\begingroup$ The Wikipedia page says that with an entrophy of 2 bits, an attacker would need half the time to break a passphrase. So this means the key would need to be double the length. Or in my case, the key would have to be 128*1.5 = 192 bits. And 192/4.7 = 40.85. This would mean my original answer was correct? $\endgroup$
    – Bas
    Apr 8, 2013 at 18:39
  • $\begingroup$ Always check the units. In your formula $(128/4.7)\cdot 1.5$, that is (128) bit, over (4.7) bit-per-char, times (1.5) bit-per-char; that is bit, when you want chars. Therefore, your formula must be wrong. Hint: try to find a formula that passes this test from the first sentence in your own question. $\endgroup$
    – fgrieu ♦
    Apr 8, 2013 at 19:02
  • 1
    $\begingroup$ @Thomas: I think the 1.5 bits/character estimation already includes that fact, it is fore some natural language like English. For truly random characters you can use the 4.7 bits/character. $\endgroup$
    – Paŭlo Ebermann
    Apr 9, 2013 at 18:12

1 Answer 1

Reset to default
5
$\begingroup$

No, your formula isn't correct. I don't know how you came to it, so I don't know what's wrong with your intuition.

You can check whether your formula makes sense with dimensional observation — it's the same kind of reasoning that helps a lot in physics. Write all numbers with their units:

  • entropy rate = 1.5 bit/character
  • random key size = 128 bits
  • passphrase length = X characters
  • information content per character in a 26-character alphabet = log2(26) bits/character = 4.7 bit/character

Your formula: $\dfrac{128\text{ bit}}{4.7\text{ bit/character}} \times 1.5\text{ bit/character} \approx 40.85\color{red}{\text{ bit}}$

We expected a number of characters, so something is wrong here.

In order to achieve the strength of a 128-bit random key, we need a total entropy of 128 bits for the passphrase. It's a simple proportionality rule: $$ \text{entropy per character} = \frac{\text{total entropy}}{\text{number of characters}} $$ so $$ X\text{ characters} = \frac{\text{total entropy}}{\text{entropy per character}} = \frac{128\text{ bit}}{1.5\text{ bit/character}} \approx 85.3\text{ character} $$ Sanity check: the passphrase length turns up as a number of characters. Since the number of characters has to be an integer, it needs to be at least 86 characters long.

The size of the alphabet is irrelevant here because the passphrase isn't chosen randomly over all possible sequences of letters. “Passphrase” implies that it is a sentence fragment in a human language, or close enough. 1.5 bit/letter is a common estimate for the entropy per character for English: the number of English sentences of length $L$ is approximately $2^{1.5·L}$, so if you pick one at random, you have a $1/(2^{1.5})^L$ chance of being right.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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