4

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

3
+50

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

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.

  • A choice from the whole 83,935 set is only available to you if you choose a password length of 31 characters. The author has probably set the desired length to 16 characters. Given those preferences, a much shorter dictionary (31,572 at best) would be used by the framework. – ximaera Jan 24 '18 at 0:00
  • 1
    @ximaera: Ah, yes, that's an important detail I didn't catch. I'll edit my answer a bit. – Luis Casillas Jan 24 '18 at 0:03
  • Thank you for the explanation! For the record, the minimum "memorable" password length allowed by the OS X password manager in High Sierra is as low as 8 characters, while the default length seems to be hard-coded to be 12 characters. It has just suggested a passphrase "both7:league" for me. I don't think at that point they at Apple Inc. really maintain it well. – ximaera Jan 24 '18 at 0:39
  • I think this estimation is under estimating. Notice that that software assumes it already knows the password is formed by a 4 letter word, then a digit and a symbol, then a 6 letter word. While as @ximaera has pointed, it is a bit more complicated. (It could be a one letter word and 5 letters, 2 letter and 5 letters, etc) I would say that my estimation, shouldn't be far-off if the word list is as described by ximaera. I only said "upper-bound", because I am assuming that all words are equally likely to be chosen (Which we can't know for certain, without inspecting the code) – Alex Recuenco Jan 24 '18 at 10: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.