In ubiquitous computing environments, people may obtain their services from application servers by using mobile devices at any time and anywhere. For convenience, most of those devices are small and of limited power and computation capacity. In this paper, we propose a robust user authentication and key agreement scheme suitable for ubiquitous computing environments. The main merits include: (1) a security-sensitive verification table is not required in the server; (2) the password can be chosen and changed freely by the clients and cannot be derived by the privileged administrator of the server; (3) all well-known security threats are solved in our proposed scheme; (4) the scheme does not have a serious time-synchronization problem; (5) the client and the server can establish a common session key; (6) the scheme is practical and efficient; (7) the scheme can preserve the privacy of the client's secret key even if the secret information stored in a smart card is compromised.