How can a Microsoft "unsuccessful sign-in" trigger a 2FA request?

Question

I was certain I'd find a question asking this, but a search didn't return any results.

I have 2FA enabled on my Microsoft account, which requires me to approve all sign-ins using the Microsoft Authenticator app. My understanding is, after you supply the correct userID + password, you're asked to approve the sign-in with the Authenticator app.

Yet twice in a week, I received such a request without trying to log in anywhere. More still, the attempt came outside my location (on both occasions from Netherlands, as I discovered on the Microsoft sign-in logs). Microsoft claims the sign-in was unsuccessful (presumably because I denied access on the Authenticator app), but I suspect that, since I received the 2FA request, my sign-in details (the password, basically) were compromised. So I changed it (though Microsoft says "Don’t worry. This sign-in attempt was unsuccessful, so there is no need to change your password", which in my opinion is really bad advice).

A week later, the same thing happened again, again from Netherlands. My super-long, super-complex password was apparently again compromised, or so it seems.

My questions:

• Am I right to assume the password was compromised on both occasions? Is there any other way a 2FA request could be triggered?
• About a couple of months ago, I started using Thunderbird as an email client, on which I used a Microsoft-generated app password (criminally not complex) to access my Outlook inbox. The way Microsoft log-ins work, would I receive a 2FA prompt if someone tried to log in using an app password that's already in use?
• A bit hypothetical (feel free to ignore it) but realistically speaking (and excluding malware, which I feel I can exclude with a reasonable degree of certainty), how likely is it to brute-force twice in a week a password that is 20 characters long, with upper,lower,numbers,symbols? I mean, if it's possible, are passwords meaningful anymore?

Answer 1

There are other ways a 2FA notification could be triggered, without the password being exposed - for example, it might be required if somebody impersonating you tries to use the "reset password" flow - but changing your password is a good first step. If it's an actual login attempt, I would expect the password would indeed be compromised (though having changed it, that now seems less likely). Is there anything in your email about the failed attempts? That might have more info.

If a password is repeatedly being compromised, there are a few possibilities. One is of course that your passwords are guessable ("complexity" adds almost nothing, by the way), or that you're re-using passwords breached from somewhere else (worth checking for breached accounts and/or passwords on https://haveibeenpwned.com/). Alternatively, there might be malware (on your device, or another that you use) which is stealing passwords. Finally, it could be a glitch on the server side... but that seems much less likely.

"App passwords" do not require 2FA - that's part of the point of them - but they are also cryptographically random and unique, two properties that a human-generated password almost never has. You say it's not complex, but again, that adds basically nothing; it almost certainly has far more entropy (non-guessability) than any password you can memorize. As https://xkcd.com/936/ points out, a typical password - even a "complex" one - has only maybe entropy in the low-to-mid 20s, while four simple words, randomly chosen in random order, has more like mid 40s - roughly one-to-four million times as hard. However, simply using 10 randomly-chosen lowercase letters - no symbols, no mixed case, and still quite short - is 47 bits of entropy, eight times as hard to guess as the "correct horse battery staple" approach (which comes from diceware), even assuming the attacker knows exactly which approach you are using. In any case, since app passwords don't trigger 2FA checks, that shouldn't matter anyhow.

Twenty actually random characters from a set of 26 lowercase, 26 uppercase, 10 digits, and 32 symbols (the number available on most US QWERTY keyboards, not counting space) has an entropy of log2((26+26+10+32)^20) = log2(94^20) = log2(2.9E39) = 131 bits. 131 bits of entropy is huge - 128 bits is considered plenty for cryptographic purposes - and is well into "if every computer on earth spent all their time doing nothing else, it still wouldn't be broken in your lifetime" range (I once computed that, making some assumptions about Moore's law and other future developments in computing, it would take roughly 300 years... and to be clear, that's not 300 years with today's computers, that's "in 300 years, computers might be good enough that this would be possible inside a year of work"). Twice in a week may as well be impossible given the verification process required. That's assuming that the server somehow even let somebody try that many times.

However, your password almost certainly isn't actually 20 totally random characters from that set, is it? D1git@lDr4cula2021!! is 20 characters, contains upper, lower, numbers, and symbols... and is utterly worthless garbage as a password for you. Hopefully you're generating them better than that, but I hope this demonstrates the degree to which "complexity" is meaningless if it's predictable substitutions or tacked-on characters.