Is the password generator really reliable ?

Steven34 · April 2016

Hello,

I use the 1Password "password generator" every couple of days.
Mostly without symbols, with 3-6 numbers, of sizes 12-15.

Last week, I generated a new password for a website, and created a new record for it.
Yesterday, I noticed that I have a duplicate password with the one created last week and another one from 2014.

The password is : i7BjfbdWDa42niB

Statistically, that seems very unlikely with a password of this complexity.
Is this an initialisation bug ? Is the generator based on a true cryptographic randomness source ? Or an unprecedented luck in my life ?

Steve

1Password Version: 6.2.1
Extension Version: Not Provided
OS Version: 10.11.4
Sync Type: iCloud

Megan · April 2016

Hi @Steven34,

One of our security experts has written a pretty awesome post that you might find interesting:

How 1Password calculates password strength.

It’s not exactly in line with your question, but I mention it because you seem interested in the nitty gritty details, so it might be a neat read for you.

Now, I have to admit, I’ve never seen anything like that with the password generator before, and I would be tempted to lean towards ridiculous luck, but I’m no expert. I’m going to ping our guru, @jpgoldberg to see if he can shine a light on things, or provide a bit of a better direction if we need to do some investigating. :)

jpgoldberg · April 2016

Thank you for pointing that out, @Steven34.

That absolutely should not happen. Even if you created a million passwords each between 2014 and last week you should not have a collision. [Note: I will update this post with the actual math for that, but I'm going to need some coffee before I start doing Birthday math.]

So you are absolutely correct to ask whether we use a cryptographically secure RNG behind the process. We do, and I've gone over this code myself. So either something else went wrong (perhaps the wrong password got saved to the wrong entry) or there is a problem with the SPG.

I will check again and try to run some tests to see if collisions occur more than they should. This may take some time, but it kind of pushes other things off of my to-do list.

Steven34 · April 2016

Hi @Megan and @jpgoldberg,

Thanks you very much for your answer and for the article.

Yes collisions would be 1 on 62^12 / NumberOfGeneratedPasswordInTwoYears.
And even with 1 million per days, like you said, it's still ridiculous.

As I posted the password in my first post, I changed the password from the service I used it.
So now I can't check anymore if maybe when I generated the new password, it erased an old one (by miss click or bug...)

Memory issues are also unlikely for me because after 2 years, I reboot the mac, upgrade the system, and have multiple 1Password updates.

As I can't directly test the PRNG, maybe your test will show something.

Thanks you again.
Steve

khad · April 2016

Thanks for your patience while we investigate further. We really appreciate you bringing this to our attention.

jpgoldberg · April 2016

Thanks @steven34,

Chances are at least two people reading this discussion have the same birthday

The chances of a collision are actually higher than (chance of password)/(number of passwords generated), due to what is sometimes called the Birthday Paradox. But it is still going to be an enormous number. You would need to generate 66 billion passwords to have a 50% chance of a duplication. For a 1% chance you would "only" need 8 billion. for a 1 thousandth of 1% chance you would need to generate about 80 million.

The chances of there being a collision among 1 million such passwords is less than 1 in 15 billion.

So even though collisions are far far more common than your formula would predict, they are still rare enough that we cannot write this off as a fluke.

(I've always wanted to write a blog post about the Birthday problem, but never seem to actually get around to it. Maybe on my birthday).

Alternative probabilities

Can I ask you to tell us more about the items? Note that if you generate a password for some site a long time ago, it will be saved in 1Password as a "Password". You may also have created a Login from that event, and then more recently updated the login. Here is an example of one of my "duplicates"

Another thing to look at is whether you have multiple services that shared the same password. For example, there was a time when Target (a major US retailer) contracted out to Amazon to run Target's web store. So there was a time when my Target password and my Amazon password were the same. A bit later Target realized it was somehow not all that bright to contract out their web store to a competitor and disentangled their logins from Amazon's, but there probably are plenty of people today who have the same password for Target and Amazon even though they were using 1Password correctly when creating those Logins.

Here is an example of another one of my duplicates.

I'm not trying to dismiss what you are saying, but I am looking for alternative explanations for what you might have encountered that are certainly more likely than a statistical fluke, and potentially more likely than an undetected bug of this nature. (But we are still on a bug hunt.)

Steven34 · April 2016

Héhé, you will be happy @jpgoldberg, (I'm also reassured with probability)

I spotted the bug, but still not understood it. I was going to make a screenshot of the duplicated element, and he changed.

When I subscribe to this forum, I generated a new password and store it in 1Password. Now I just discovered that the same previously key I use for other software has changed. And it takes the date of 19 April (my registration here).

In fact I changed the password for both my services and now I have a duplicate software key.

One is OK, but the other is like a ghost item that just mime another password. I tried to edit or create a new password, but I can't reproduce that. Maybe a sync issue, or an old artifact. I will try this week-end if I can gather any more information.

AGAlumB · April 2016

@Steven34: Ah, thank you for following up! While it still isn't completely clear what happened, there are a few possibilities considering the new information you've shared and Jeff's earlier hypotheses.

Indeed, it could be sync-related. Also, if you duplicate an item or copy it elsewhere (and perhaps copy it back), it will have a different UUID than the original. This is, after all, how you can have two items that otherwise appear identical coexisting in the same vault. So as I see it here are some likely causes:

Generated password was originally saved as a Password item when filling.

When you use 1Password to fill a newly generated password, a Password item is automatically saved as a safety net, in case a Login item is not saved. Therefore, these would both have the same random password, since one was used in the creation of the other.

Password (or Login item) was duplicated.

This would result in a nearly identical (different UUID and date) item to the original, including the random password.

In fact I changed the password for both my services and now I have a duplicate software key.

It sounds like you're describing the first example, where you generated and filled a new password to do the password change (thus creating a Password item in your vault) and then updated your password for the site (saving the Login item with the generated password). The very same password would then be stored twice: in the Password item and the Login item. Does that match what you're experiencing?

jpgoldberg · April 2016

Ok. It looks like we are good here.

This brings up a difficult and abstract point. It is hard to run definitive tests for some randomness things. Here is a test of collisions on passwords that are two words long (using a prototype of our word list generator).

func testDicewareBirthday() {
        if !runFailableTestss { return }

        // This will be a test for collisions.

        let units = 2
        let doCaps = false
        let separator = " "

        let dw = Diceware(units: units, separator: separator, capitalization: doCaps)

        let pInverse = 20
        let p = 1.0/Double(pInverse)

        let m = pow(2.0, dw.entropy)
        let trials = Int(sqrt(2.0 * m * p)) // Approximate number of individuals before having p chance of collision
        print("Trails for 1/\(pInverse): \(trials)")

        var pwds = Set<String>()
        for n in 1...trials {
            let pwd = dw.newPwd
            XCTAssert(!pwds.contains(pwd), "Collision found at \(n) of \(trials). Should happen only 1/\(pInverse) tests. ")
            pwds.insert(pwd)
        }
    }

The let pInverse = 20 is where I've set this to generate enough passwords to have a 1 out of 20 chance of there being a collision. Then it generates that many passwords and treats a collision as an "error".

Now we can't put this sort of test in as a formal unit test because it has a 1 out of 20 chance of failing even if nothing is broken. And we can't just run this test a bunch of times and see whether it fails "about" 1/20th of the time because we would still need to account that if you run that meta test enough times it will report a failure even when nothing is wrong.

And even a false positive rate of 1/20 doesn't mean that this will find anything but very large statistical biases that would lead to more than expected collisions. Quite simply, all you can do is prove that a random number generator isn't broken enough to be detected by the particular test you are running.

@Steven34's query did was prompt a bunch of us to look for suspicious duplications in our own vaults. All of the apparent duplications that any of us found were creations of sports that Brenty and I have posted about.

It is frustrating that we can't definitely test this stuff, but we do try to test for what we can.

For example there is a common error that people make when they try to generate a random number between, say, 1 and 100. It's called the "modulo bias". But how do we test that our tools for picking a random number in a range genuinely do give us a uniform distribution? There are a number of statistical tests that can tell you if your distribution deviates "significantly" from uniform, but the don't actually give us what we need.

Again, when prototyping some stuff, I developed a few tests, but all they can do is tell me if things are broken in very specific ways and above a particular threshold.

Anyway, now I am going off on random topics.

Cheers,
-j

Steven34 · October 2016

Hello,

In fact this bug seems to have nothing to do with the random password generator, it's indeed a sync or a vault issue.

I still have a duplicated password element that show up some time. I delete it and some time later it comes back...

These items always seems to be of type "password".

From September 2016

And just now

Since last week, I switched from iCloud to DropBox sync. I don't know if the last one was already here or not, so I will wait and see...
DropBox normally create some conflict files, but there is not.

Steve

Drew_AG · October 2016

Hi @Steven34,

Thanks for contacting us again for help! If I understand the current problem you've described, it sounds like you delete a Password item from your vault, but then it reappears later - in other words, that Password item seems to "undelete" itself. Is that correct?

If so, are the "Google Chrome" and "Sublime Text" Password items from your screenshots the ones that you deleted and which reappeared in your vault?

Since last week, I switched from iCloud to DropBox sync. I don't know if the last one was already here or not, so I will wait and see...

Please let us know if this happens again. It not, it might have been a 1-time issue related to switching from iCloud to Dropbox in the sync settings. Do you change your sync settings in 1Password frequently?