2

I'm working with a vendor who provides an API with a user registration method clearly designed for human-generated passwords. We're calling the API in an offline server-to-server fashion, however, and registering with the API on behalf of our user.

I'm relatively comfortable with the idea of generating our own cryptovariable, in lieu of either re-using the user's password or forcing the user to generate their own second password for the API. Either way, due to the design of the API, we're going to be forced to store the password/cryptovariable, which will additionally be encrypted both at rest and on the wire.

The only grief I have is that the API (again, apparently designed for human-generated passwords), has some restrictions on the password format that decrease entropy when using a cryptographic random number generator to generate the 'password' (more accurately a cryptovariable). I can do the math on them all except for one (and getting the code correct is also pretty reasonable).

The most cryptovariable-unfriendly of the 'password' rules is that there can be no repeating sequences of characters in the password. In other words (and not accounting for the other password rules the API enforces), 'ab' and 'ba' are OK, but 'aa' and 'bb' are not. For that specific simple case, assuming fixed-length of two and only the two symbols 'a' and 'b', I can see that restriction exactly halves the entropy, and I can also see that it's better as the length increases. In my case I would just double the length and call it a day, except there's also a maximum password length restriction (doh!).

So enough background -- my concise question is:

What is the entropy of a randomly generated, fixed-length 48-symbol long cryptovariable consisting of 64 symbols (A-Z, a-z, 0-9, + and /), where any combinations with any repeating sequences of symbols are excluded?

As a matter of personal edification, I would also like to know not just what the answer is in this specific case, but I would also like to understand how to determine the entropy for the 'non-repeating' conditions for various lengths and symbol sets. Seems like this might even be an exercise in a cryptography textbook, and would love a reference.

And, now that I'm ready to admit I've spent WAY more time on this already than I'd ever hoped, I'm also wondering:

Am I just being paranoid?

Specifically, since passwords that follow these rules are theoretically "secure enough" from brute force attacks that the remaining entropy is "enough", can I, in good conscience, just trust that the API is plenty "good enough", call it a day, and go have a beer?

-- Tim

p.s. I should also note I'm open to other out-of-the-box solutions to the problem at hand as well, but have already ruled out storing the user's human-generated password locally and prompting the user interactively when we need to pass it through to the API.

Reusing the user's password would force us to store the user's actual personal password locally, rather than use the much more appropriate industry standard practice of storing a one-way hash of the password -- so we very definately don't want to do that.

Forcing user interaction to generate a second password is both a bad user experience in general, and practically guarantees a high degree of password reuse by many users, so we don't want to do that, either. Further, and more critically, we're accessing the API mostly offline. Despite the heartburn this particular problem is giving me, offline use is fully supported by the API per the documentation. In any case, since we're accessing the API offline, we don't actually have an opportunity to request the user enter the password -- so we can't do that, either.

  • 2
    It's still ridiculously large. If you simply can't have two successive repeated characters the password space drops from 64^48 to 64*63^47. So that, expressed as 2^n for whatever value of n gets you to 64*63^47 == 2^n is the number of bits of entropy. – Xander Feb 27 '15 at 20:27
  • 1
    And if you can't have any repeated sequences of any length, the easiest entropy calculation is the worst case, which is 64*63*62*...*16. In this case you're dropping each character as it's used, so there can be no repeated sequences, as no character will be used twice. This still gives you a massive ~250 bits of entropy. – Xander Feb 27 '15 at 21:46
3

Computing entropy for a randomly chosen password can be broken down to a simple rule that can be used in virtually all cases, with some caveats. It's the log2() of the password character set space raised to the power of the password length. So, with a completely random password where all characters are independent, this is an easy calculation. E.G., For a password that is 8 characters long and composed only of uppercase English letters, it is: log2(26^8) or ~37.6 bits of entropy. Another slightly more verbose way to express this is: log2(26*26*26*26*26*26*26*26). If we were to add a constraint to our password, perhaps it must be four uppercase characters and then two digits, a randomly generated password will have log2(26*26*26*26*10*10) bits of entropy. (~25.4 bits)

So, in a more complex case like yours, you have to determine how many characters are available for each successive position in order to determine the password space and thus, the entropy. The condition prohibiting repetition means that you cannot actually know before hand the entropy of a specific password, because the character set to chose from will be constrained by characters already chosen...So you can only calculate the minimum entropy should the characters randomly chosen maximally constrain the character space for later characters. I don't actually want to work out this specific calculation but generally, to prevent any repetitive sequences, you need only limit the character space by the last character chosen (so you don't get bb) and if there are any previous incidents of the previous character, the characters that follow those incidents. (So if to this point the password is abcdbeb, you would need to exclude b, c, and e from the character space for the next character.) As you can see, this means that as the password grows in length, the available character space is not only going to shrink, but its size will only be known after the previously chosen characters have been examined.

So, the super simple method to determine minimum entropy with a maximum margin of error I mentioned in the comment is to simply exclude each character as it is used. With no possibility of a character being used twice, there is no possiblity of a repeating sequence. With a character space starting with 64 characters, and a password that is 48 characters long, this is log2(64*63*62*...*16) which is a massive ~249.7 bits of entropy. So, since we know that given your specific constraints, the entropy of your passwords will be higher, you have a huge safely margin, and there's no realistic chance of a successful brute force attack.

As an aside, if you had no constraints, and randomly chose 48 character passwords from a set of 64 characters, you would have had 288 bits of entropy.

  • "means that you cannot actually know before hand the entropy of a specific password" this is true in general, because specific passwords don't have entropy. Only password generation techniques have entropy. – PyRulez Mar 13 '16 at 2:10

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.