Entropy on native memorable password on macosX keychain

Question

I have been trying to find information on this. But I haven't found anything online.

When you use the password manager on mac, it can provide "memorable" passwords.

For example pick3"enigma. (You choose the number of characters)

I haven't found any information in what is the dictionary being used, what options of extra characters and numbers are used, and how are they all fixed to get the amount of characters you suggest... Therefore, I am unable to determine the total entropy of such passwords.

Is there anywhere where I could find the range of words it can use, and the possibilities, to understand what is the total entropy provided by these passwords?

Or a source that provides some reliable information of what is the entropy of a "memorable password" created by the keychain

Answer 1

Anders Bergh reverse-engineered the OS X Password Assistant and wrote a command-line utility which does the same job. From its source you can find out that all of the password generation is done by a proprietary undocumented library function SFPWAPasswordSuggest() from the SecurityFoundation framework.

Though the function is proprietary and no official Apple documentation exists, you can play with either the function itself or the command-line utility around it to figure out what it's producing. Allister Banks already did that in 2015, assumingly for OS X Yosemite, and came up with a code snippet which produces pretty much the same results (except for a few strange author's preferences, like limiting the range of available random numbers).

In a nutshell, SFPWAPasswordSuggest() picks two random words from a vocabulary and inserts a random number and one special character (in that order) between them. The random number length is such that the overall string length will be exactly as required, and there will always be a single special character. Regarding the vocabulary, OS X from Yosemite to High Sierra use /System/Library/Frameworks/SecurityInterface.framework/Resources/pwa_dict_en.gz, 287 kb in size and with 83935 English words of length between 2 and 24, for that:

$ gzcat pwa_dict_en.gz | python2 -c 'import sys
> sys.stdin.read(512)
> word_counts = dict()
> for num_of_letters_index in range(64):
>     value = int(sys.stdin.read(8).strip(), 16)
>     if value:
>         word_counts[num_of_letters_index] = value
> print "Distribution:", word_counts'
Distribution: {1: 26, 2: 191, 3: 1229, 4: 3170, 5: 5591, 6: 8913, 7: 12452, 8: 13462, 9: 12163, 10: 9820, 11: 7007, 12: 4516, 13: 2704, 14: 1429, 15: 691, 16: 329, 17: 150, 18: 61, 19: 21, 20: 5, 21: 3, 22: 1, 24: 1}
$

Here's how you can parse the file. In other OS X versions, the function may be designed somewhat differently; use dtruss ./sf-pwgen to figure out.

Note that GUI limits the length of your generated password with number 31. As far as I can see, the function doesn't produce an error for longer requests, yet is not guaranteed to work for passwords longer than 31 characters. Actually, for passwords above 67 characters, it's almost guaranteed to fail; as you can spot above the vocabulary doesn't feature enough words of sufficient length, and the generating algorithm doesn't handle this case well, simply returning a short passphrase consisting of only numbers and a special character:

$ ./sf-pwgen -c 1 -l 68
2814154076!
$

---

EDIT 24.01.2018: on behalf of Alex Recuenco:

Calculating entropy

Following @ximaera solution.

import math

x = {1: 26, 2: 191, 3: 1229, 4: 3170, 5: 5591, 6: 8913, 7: 12452, 8: 13462, 9: 12163, 10: 9820, 11: 7007, 12: 4516, 13: 2704, 14: 1429, 15: 691, 16: 329, 17: 150, 18: 61, 19: 21, 20: 5, 21: 3, 22: 1, 24: 1}

def entropy(pass_length, n_symbols = 30):
    combinations = 0
    for key, value in x.items():
        for key2, value2 in x.items():
            if (key + key2) < (pass_length - 1):
                combinations += value * value2 * n_symbols * (10 ** (pass_length - key - key2 - 1))
                # last value

    return {'combinations': combinations, 'entropy': math.log2(combinations)}

print(entropy(31))

Which when you run it:

> {'combinations': 1124445877165765109161692550890600, 'entropy': 109.79284135298234}

110 bits of entropy, maximum... I thought it would be better for some reason. The entropy of a password of just numeric characters of length 30 is approximately 100

Answer 2

Estimating entropy with zxcvbn

One reasonable way to estimate an upper bound on the entropy of a password whose generation method you don't know is to feed it to the zxcvbn password strength meter, which has an online demo (that I just linked) and is reasonably sophisticated. For pick3"enigma we get:

password:              pick3"enigma
guesses_log10:         8.28991
score:                 3 / 4
function runtime (ms): 1

guess times:
100 / hour:            centuries (throttled online attack)
10  / second:          7 months (unthrottled online attack)
10k / second:          5 hours (offline attack, slow hash, many cores)
10B / second:          less than a second (offline attack, fast hash, many cores)

match sequence:

'pick'
pattern:              dictionary    
guesses_log10:        2.56585   
dictionary_name:      us_tv_and_film    
rank:                 368   
reversed:             false 
base-guesses:         368   
uppercase-variations: 1 
l33t-variations:      1

'3"'    
pattern:              bruteforce    
guesses_log10:        2

'enigma'
pattern:              dictionary
guesses_log10:        2.63347
dictionary_name:      passwords
rank:                 430   
reversed:             false
base-guesses:         430
uppercase-variations: 1
l33t-variations:      1

The guesses_log10 field can be used to calculate the entropy by converting to base 2 (multiply by 3.3) and adding one. The password therefore should not have much more than 28.5 bits of entropy. As the output dump shows above, the word pick is #368 in zxcvbn's us_tv_and_film dictionary, and enigma is #430 in its passwords dictionary (of common passwords), so an offline attacker can guess the password in a fairly short amount of time without having very intimate knowledge of the password generation internals, just general knowledge about how people often pick passwords.

Estimating entropy from dictionary size and algorithm

Another approach: @ximaera's answer says the password is generated like this, using a dictionary of 83,935 words:

In a nutshell, SFPWAPasswordSuggest() picks two random words from a vocabulary and inserts a random number and one special character (in that order) between them.

A random word from a set of 83,935 is a bit more than 16 bits of entropy. A digit from 0-9 is about 3.3 bits. An ASCII non-alphanumeric character (out of 33) is about 5 bits. So that would give us a about 41 bits if that was the whole explanation of the generator's algorithm.

But as @ximaera points out that's not the whole story, because the generator also has logic to limit the password character length, apparently by rejecting candidate passwords not equal to a user-requested length. So actually it's rather complicated to calculate the precise entropy. Too complicated to bother trying, I would say, because the simpler calculation above already tells us it must be less than 41 bits, and probably quite a bit less. That's not a precise number by any means, but it's broadly consistent with the zxcvbn estimate of 28.5 bits.

Conclusion

The passwords generated aren't very strong, at least not at that length. If we regard 64 bits (e.g., Diceware five-word passphrases) as the bare minimum password strength we ought to use, then this Apple generator falls far short. A sophisticated attacker doesn't even need to know precisely how the algorithm works, as zxcvbn demonstrates.