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.

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?

share|improve this question
1  
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. –  Henrick Hellström Apr 8 '13 at 16:59
    
This Wikipedia article is a good resource. –  hunter Apr 8 '13 at 18:06
    
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? –  Bas Apr 8 '13 at 18:39
    
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. –  fgrieu Apr 8 '13 at 19:02
1  
@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. –  Paŭlo Ebermann Apr 9 '13 at 18:12
show 5 more comments

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

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

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