A one-time password (OTP) is one of network security technologies, which is a security system that requires a new password whenever a user desires to receive authentication. This system is intended to solve a serious security problem occurring when a fixed password is leaked in a general ID/password-based security system. Recently, the system is increasingly used in an enterprise or financial institution which requires high-level security.
The OTP has several types such as an S/Key type, a challenge/response type, a time synchronization type, and the like, among which the time synchronization type uses time to generate a single-use password, as seen from its name. When a user generates a client-side OTP and delivers the generated client-side OTP to an authentication server together with a PIN (a user password, a secret key), the server uses an init-secret and PIN of a user corresponding to an ID of the client to generate a server-side OTP and check whether the generated server-side OTP is consistent with the received client-side OTP. In the time synchronization type, since the authentication server and the user should enter the same time as an OTP input value, user authentication cannot but fail if time between the authentication server and the user token is not the same. However, it is practically difficult to always synchronize the user terminal with the server. Accordingly, in many cases, an error range of the time is set, and if the time is within the error range, authentication is considered successful. For example, the authentication server sets an effective range of a certain time (for example, −180 sec to +180 sec) before and after a time when a request for authentication is received from a user and determines that the authentication has succeeded when one of server-side OTPs that are generated as time information in the effective range is consistent with an OTP of a user.
However, the authentication server needs to generate a number of OTPs according to the effective time range, thus increasing a burden at the server side. In particular, since the OTP is encoded using MD5 and the like, an overhead caused by generating the OTP is greater than that of a general password type. For example, if n server-side OTPs are generated in the effective range, it takes a time O(n) to authenticate one client. Furthermore, if m devices are registered for each client, the authentication process should be repeatedly performed on each device and thus it takes a time O(n*m) to authenticate one client.