Forget passwords, tricky sums are more secure


This post was chosen as an Editor's Selection for ResearchBlogging.orgFaster, more secure logins for multimedia sites might be possible thanks to a new approach to website and database security. Boolean logins would allow thousands if not millions of users to more quickly access the content to which they are entitled, such as music, video and images. The same approach might also reduce the risk of hackers accessing the materials illicitly.

Nikolaos Bardis of the University of Military Education, in Vari, Greece and colleagues there and at the Polytechnic Institute of Kiev, in Ukraine, have developed an innovative approach to logins, which implements the advanced concept of zero knowledge identification.

Classic user identification requires the remote user sending a username and a password to the system to which they want to be authenticated. The system looks up the username in its locally stored database and if the password submitted matches the stored password, then access is granted. This method for identification works under the assumption there exist no malicious users and that their local terminals cannot be infected by malware. Increasingly, these assumptions are too naïve. Not all users may be assumed to have good intentions. Technology continuously facilitates the capture of transactions in wireless channels. Usernames and passwords can therefore be easily obtained by malicious third parties (other users or viruses) and be used for illegal accesses to systems.

Zero knowledge user identification solves these issues by using passwords that change for every session and are not known to the system beforehand. The system can only check their validity.

The basis of modern cryptography are analytically insoluble mathematical equations; i.e. equations that have a solution, but this solution cannot be found by a formula. Consider the modulo operation, for which A mod B represents the remainder of the division A/B. Then assume for example, the equation 5Xmod7 = 2. There exists no mathematical formula that can give X = … . The solution may only be found by trying all possible values. Trying X=2: one gets 52=25, 25mod7 = 4. Not true. Trying X=3: one gets 53=125, 125mod7 = 6. Not true. Trying further X=4: one gets 54=625, 625mod7 = 2. Hence X = 4 is a solution. This solution was relatively easy to find because the numbers were small.

Normally, the numbers used would have hundreds of decimal or thousands of binary digits. Hence the process is in practice safe. Algorithms like RSA, El-Gamal and DSA are based on the above principle. One more characteristic of the equations used is that they have multiple solutions. In the above example, 5Xmod7 = 2, another solution is X=10: 510mod7 = 2. The legitimate user would hence formulate the two passwords (X =4 and X = 10). Following that, the user registers to the system giving the base (5), the modulo (7) and the result (2). When the user wants to login, they will first use the 1st password. The system does not know if it is correct, but calculates 54mod7 =2, verifies the submitted password and grants access. Next time round, a different password may be used.

The basic drawback of this is the extremely high computational complexity, when numbers of hundreds of digits are raised to powers of tens of digits and the remainder of the division with another large number is sought. Hence a different mathematical problem had to be found, for which the calculations for authentications are relatively simpler.

This problem is finding the solution of a system of non-linear Boolean equations. A solution exists but there is no easy way to find them quickly. In practice, the only solution is successive trials. Such equations are the basis for algorithms like DES and AES. In general one may say that for a given system of non-linear Boolean equations F(X), the value X that corresponds to a given Y=F(X) can only be determined by trials. The proposed method allows the remote user to construct a transformation F(X) and the complete set of solutions X1, X2, X3, …., Xn such that F(X1) = F(X2) = F(X3) = … = F(Xn) =Y. The user registers to the system and submits F(X) (as a truth table) as well as Y. For the first session, the user will submit X1 as the first password. For the second session, the username remains the same but the password is X2. Each time, the system calculates F(X) and only grants access if F(X) equals Y.

Put simply, zero-order user authentication schemes, supply the user with a special function that produces an extremely large number of different results for all its possible inputs. A set of inputs that produce a common result is selected. These inputs are the user’s passwords. A new user registers by submitting to the system their function and the common result. The user authenticates for a normal session using each password only once. The user provides the password at the beginning of each session. The system calculates the value produced when this password is used as input to the function. If this is equal to the common result, then authentication is successful and access is granted. Someone that is trying to gain access without the necessary knowledge (an illicit user) will practically have to try all possible password combinations, before reaching the correct one.

The proposed scheme has potential use in any system where malicious users have incentives to gain illegal access and perform actions they are not entitled to. The number of such systems increases rapidly as information gains value.

The advantages of the proposed scheme depend to what it is compared. If it is compared to classic authentication systems then the proposed scheme is not faster. It is however safer, as it implements zero knowledge identification. This means that a malicious colleague or a virus cannot obtain passwords and exploit them for illegal purposes. Additionally, passwords that have been stolen by tapping into the communication channel may not be used since the password changes for every session.

If the comparison is done compared to existing zero knowledge schemes based on modular exponentiation, then the proposed approach accelerates authentication by about 1000 times. This is a very important result, since the high computational cost has until now deterred the wide use of the concept of zero knowledge identification. One must take into account the fact that in modern systems the number of users ranges to the thousands or tens of thousands and hence authentication must be quick. Apart from that, the periodic repetition of the authentication process can prohibit a criminal from taking over an already active session.

Research Blogging IconNikolaos Bardis, Nikolaos Doukas, & Oleksandr P. Markovskyi (2011). Fast subscriber identification based on the zero knowledge principle for multimedia content distribution Int. J. Multimedia Intelligence and Security, 1 (4), 363-377


Author: David Bradley

Freelance science journalist, author of Deceived Wisdom. Photographer and musician.