Existe banco de dados em /var/log/lastlog (AFAIK binário). Veja a página de manual para lastlog(8) . O arquivo deve ser atualizado pelo módulo PAM pam_lastlog(8) .
Pode haver alguma diferença na versão do Ubuntu que você está usando (eu não tenho esse arquivo, nem a mensagem no meu 15.10).