A technique of performing knowledge based authentication (KBA) involves collecting activity data and time data based on operation of a mobile device, the activity data identifying an activity performed by the mobile device, and the time data identifying a time of the activity. The technique further involves generating a KBA question based on the activity data and the time data. The technique further involves providing the KBA question to a user to authenticate the user. Such a technique is capable of being performed by a remote server which communicates with the mobile device over time (e.g., in response to certain events, periodically, combinations thereof, etc.). Accordingly, the remote server is able to accumulate activity and time data which is not stored permanently (or perhaps even at all) by the mobile device, and then generate KBA questions based on that data.