Using a Cryptovariable with an API Designed for Human-Generated Passwords

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.

• 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. Commented Feb 27, 2015 at 20:27
• 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. Commented Feb 27, 2015 at 21:46

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, 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.