While on holiday in France in May I received an email from Google "New sign-in".


  Your Google Account was just used to sign in:
  
  Nairobi, Kenya. Tuesday, 26 May 2015 22:10 (East Africa Time).


I hastily changed my password. I've never been to Kenya.

My question is: How did this happen? I believe I practised good security:


My password was long—four words similar to smoke daily us sitting (I chose this password in 2014, upgrading from something similar to m0zzarella).
I never used this password for anything else.
I used two-factor authentication to receive codes by SMS (no smartphone, so no authenticator app).
I created an app-specific password for my phone's email app (Nokia S40 phone).


Why didn't two-factor authentication stop the hacker? Here's what I did on holiday:


Checked my email
Used a web browser on my phone to log in to a Google website.


I can't remember which web browser I used. I had both Nokia Xpress (default browser) and Opera Mini. (Since then a software upgrade replaced the default browser with a version of Opera Mini). I know both of these work by 'sending the data via their servers'.

Is it possible a password or SMS was intercepted? All this happened while I was on holiday and using a foreign phone network. Has this happened to anyone else?



It's a shame Google didn't prevent the sign-in. Previously on another account Google contacted me "Suspicious sign-in prevented" when someone tried to log in from China.

Your password was not stolen. As you pointed out, Opera Mini uses proxy servers. Per the link provided in thexacre's answer, Google incorrectly identifies the servers as being in Nairobi, Kenya:


  When you use Opera Mini, you're connected to Opera servers, which
  download websites you want, compress and transform them, and at the
  end they are sent to your phone. So the idea is similar to proxy
  servers. IP address on the screenshot you attached is in fact one of
  Opera Mini servers, so you shouldn't be worried. I don't know why it's
  detected as Kenya, you'd better ask Google.


So everything was fine except for Google's IP geolocation.
