RU2774807C2 - Homomorphous encryption for authentication using password - Google Patents

Abstract

FIELD: communication.

SUBSTANCE: invention relates to secure information transmission via a communication network. Homomorphous encryption is used for protection of an authentication string, for example a password, during authentication both on a client device and on a server device. Embodiment options relate to a server device and a client device made with the possibility of authentication of a client device user. The user has an access to the authentication string. The server device is made with the possibility of encryption of a dataset of a symbol/position according to a homomorphous encryption algorithm. The client device allows for the user to select a subset from the encrypted set, from which a verification number is calculated, using a homomorphous operation.

EFFECT: increase in the security of data transmission.

17 cl, 7 dwg

Description

FIELD OF TECHNOLOGY

The present invention relates to a client device, a server device, a server method, a client method, and a computer-readable storage medium.

BACKGROUND OF THE INVENTION

US Pat. No. 7,735,121 discloses a known system for secure transmission of information over a communications network. This known method can be used to enter authentication information such as a PIN.

This known system comprises a remote computing device connected to a web server via a telecomm network. The web page used to authenticate the user contains a virtual panel from which the user can enter sensitive information. The virtual pad contains a plurality of alphanumeric buttons that can be directly selected on the display of a user's remote computing device to enter confidential information. Alphanumeric characters are randomly displayed in different places on the virtual panel. The actual characters displayed on the virtual bar are mapped to an alternate character set stored in a database on the authentication server. Characters from the alternate character set that match the sensitive information entered by the user are then encrypted using the Secure Socket Layer (SSL) layer and passed to the authentication server.

There are several problems associated with this known system. For example, a web server is vulnerable to a memory scan attack. After decrypting the response from the user, the user's password can be seen in memory. An attacker with access to the server's memory can extract the password from it. Similarly, on the client side, an attacker can record the data that is sent from the user's device and then replay it, impersonating the user to the server.

DISCLOSURE OF THE INVENTION

According to the claims, a client device and a server device are provided that are capable of authentication. The server device uses homomorphic encryption to encrypt the character/position data set according to the homomorphic encryption algorithm. The client device calculates a parity number from the encrypted character/position data. Because the character/position is encrypted using homomorphic encryption, the check number calculation can be performed on the encrypted data without the need for decryption. Finally, only the check number needs to be returned. In this way, the server can check if the received and stored parity match each other without needing to know which character/position data was selected, i.e. the server does not need to know the authentication string, such as a password or User PIN.

In an embodiment, the server device obtains mapping data for characters in the character set and associates the mapping data with encrypted character/position data corresponding to the character. The user can, on the client device, select display data corresponding to the characters in the authentication string. Thus, the authentication string is not required even in the memory of the client device. The display data is preferably difficult to machine read, eg, cannot be read by a machine. Even if the mapping data is difficult to read, even if it is probably impossible, it will make automated attacks more difficult.

The authentication method described herein can be applied to a wide range of applications. Such applications include communication systems (for example, to protect the authenticity of messages), financial systems (for example, to protect financial transactions), storage systems (for example, to protect the authenticity of data), etc.

The method of the present invention may be implemented on a computer as a computerized method, or in specialized equipment, or a combination of both. The executable code for the method of the present invention may be stored in a computer program product. Examples of computer program products include memory devices, optical storage devices, integrated circuits, servers, interactive software, etc. Preferably, the computer program product comprises non-transitory program code stored on a computer-readable storage medium for carrying out the method in accordance with the present invention. when running this software product on a computer.

In a preferred embodiment, the computer program comprises computer program code configured to perform all steps of the method of the present invention when the computer program is executed on the computer. Preferably, the computer program is implemented on a computer-readable storage medium.

According to another aspect of the present invention, a method for making a downloadable computer program is provided. This aspect is used when the computer program is downloaded from, for example, Apple's App Store, Google's Play Store, or Microsoft's Windows Store, or when the computer program is available for download from such a store.

BRIEF DESCRIPTION OF THE DRAWINGS

Further details, aspects and embodiments will be described by way of example only with reference to the drawings. Elements in the figures are shown for simplicity and clarity and are not necessarily drawn to scale. In the figures, elements that correspond to elements already described may have the same reference numerals. Content of drawings:

in FIG. 1 schematically shows an example embodiment of an authentication system;

in FIG. 2 schematically shows an example of an implementation of data dependencies;

in FIG. 3 schematically shows an exemplary embodiment of character/position data;

in FIG. 4 schematically shows an example of an implementation of mapping data;

in FIG. 5 schematically shows an example of an implementation of the server method and the client method;

in FIG. 6a schematically shows a computer-readable storage medium having a writable portion containing a computer program according to the present embodiment,

in FIG. 6b is a schematic representation of a processor system according to an embodiment.

The list of position numbers in Fig. 1-4:

100 - server device

101 - authentication system

110 - storage device for check numbers

120 - encryption block

130 - communication interface

140 - comparison block

150 - permutation generator

160 display data block

200 - client device

210 - display

220 - user interface

230 - communication interface

240 - homomorphic calculation block

250 - storage device

310 - character/position data set

320 - subset of character/position data set

325, 326 - authentication string

330 - first unblinded check number

340 - first check number

345, 346 - blinding number

350 - a set of encrypted character/position data

360 - a subset of the encrypted character/position dataset

370 - second unblinded check number

380 - second character/position data set

410 - many positions,

420 - character set

430 - character/position number

500 - permutation

510 - display data

511 - display data

530 - encrypted character/position data

520-529 - encrypted character/position data

IMPLEMENTATION OF THE INVENTION

Although the present invention may be embodied in many different forms, one or more specific embodiments are shown and will be described in detail in the drawings, with the understanding that the present description is to be considered as exemplifying the principles of the present invention and is not intended to limit the invention to the specific embodiments shown and described. implementation options.

In the following, for purposes of understanding, the elements of the embodiments are described at run time. However, it is obvious that the respective elements are configured to perform the functions described as being performed by them. In addition, the present invention is not limited to these embodiments, and the invention lies in each of the new features or combination of features described herein or set forth in mutually different dependent claims.

A popular authentication mechanism is the username/password combination, also known as user credentials. Typically, credentials are sent to an authentication server for verification. When an attacker obtains the credentials of some user, he is able to impersonate a user on the server, i.e. the attacker can convince the server that he is the user from whom he stole the credentials. Unfortunately, in practice, many users use the same passwords in many applications. Therefore, an attacker is able to impersonate a user in more applications, and not just in one application that he hacked.

The problem is that attackers are able to read the memory when the user enters their credentials. These attacks are called memory scans. Existing solutions are mainly based on multi-factor authentication, where the user must complete multiple authentication steps, preferably on separate devices As a result, a simple credential scan is not enough for an attacker to impersonate a user on the server, but on the other hand, the user loses sensitive data (his password, which he will probably use in several applications).

A possible solution could be to ensure that the password is never present in memory. For example, you can have the user enter a sequence of numbers using a secure keyboard so that the value of the number cannot leak due to the known location of the button pressed, and the value resulting from the button press is not an open value, but an encoded value.

This secure keypad ensures that all password information such as PIN is hidden from the memory scanner. This solution will exclude the leakage of a confidential personal password to such an attacker. However, an attacker could simply scan and replay the encoded password to the server to impersonate the user anyway.

пользователей и хэшей (имеющих соль, или иначе, модификатор входа хэш-функции) соответствующих паролей

. Когда сервер получает имя пользователя и пароль

, он вычисляет

и проверяет, справедливо ли

.To authenticate to the server, the client typically sends its credentials over a secure channel. The server then uses its database to check if the username/password combination matches. For example, the database contains combinations of names

users and hashes (having a salt, or otherwise, a hash function input modifier) of the corresponding passwords

. When the server receives the username and password

, it calculates

and checks if it's true

.

If an attacker is able to attack the server, then he can find a database containing the credentials (their derivatives) of the user. There are good solutions to prevent an attacker from obtaining sensitive passwords from a database, such as the use of cryptographic hashes in the previous example. However, when an attacker is able to scan the active server's memory, in most situations he will see the public password in the server's memory. The following describes implementations that use homomorphic encryption to protect an authentication string, such as a password, during authentication, on both the client device and the server device.

On FIG. 1 schematically shows an exemplary embodiment of an authentication system 101. The authentication system 101 includes a client device 200 and a server device 100 that are configured for client device 200 to authenticate a user of client device 200 to server device 100. The user is authenticated by ensuring that they know the authentication string.

Client device 200 and server device 100 may be electronic devices implemented as embodiments of the present invention. The client device 200 includes a communication interface 230 configured to communicate with the server device, and the server device 100 includes a communication interface 130. These communication interfaces are configured to communicate with each other in a digital format, such as by exchanging digital messages, such as through a computer network. For example, a computer network may be the Internet, an intranet, a WLAN, etc. A computer network may be the Internet. For example, communication interfaces 130 and/or 230 may be wired interfaces, such as an Ethernet port. For example, interfaces 130 and/or 230 may be wireless interfaces, such as a Wi-Fi interface, such as containing a Wi-Fi antenna.

The client device 200 and the server device 100 cooperate such that the client device can authenticate the user of the client device 200 to the server device 100. For example, the server device 100 may be configured for some service for which the user is authorized and other users are not. For example, server 100 could be a file server that stores documents the user has access to, a streaming server that provides access to valuable content, a web store that stores the user's credit card information, and so on.

The client device 200 and the server device 100 each contain a processor circuit. They may also contain memory containing computer processing instructions. The processor circuit is configured to execute instructions stored in the memory. The execution of the authentication is implemented in the processor scheme, examples of which are shown in this document. On FIG. 1 shows functional blocks that may be functional blocks of a processor circuit. For example, Fig. 1 can be used as an approximate plan for organizing a processor circuit. On FIG. 1, the processor circuit is not shown separately from the blocks. For example, the functional blocks shown in Fig. 1 may be wholly or partially implemented in computer instructions that are stored on device 100 or 200, such as in the electronic memory of device 100 or 200, and may be executed by the microprocessor of device 100 or 200. In hybrid implementations, the functional blocks are implemented partially in hardware. such as co-processors, such as crypto processors, and partly in software stored and executed on device 100 or 200.

The server device 100 is configured to authenticate the user from the client device 200. The user has access to the authentication string. The authentication string has a plurality of characters in a plurality of positions, the characters being selected from a character set. For example, the authentication string could be a PIN code, in which case the character set is the numbers {0, 1, 2, ..., 9}. For example, the authentication string may be an alphanumeric string, in which case the character set may be {a, ..., z, A, ..., Z, 0, ..., 9}. In addition, one or more punctuation characters may be added to the character set according to the needs of the authentication system 101.

The server device 100 includes a memory 110 configured to store the first parity number, such as a parity memory 110 . During the installation phase, the first verification number was calculated from the authentication string. However, in an implementation, knowing the first parity number is not sufficient to obtain an authentication string. Moreover, the first pass number cannot be used on its own to authenticate to server 100. In other words, even if the attacker were to obtain the first pass number, it would not help him either get the authentication string or authenticate to the server. 100. The client device 200 is configured such that during the authentication process, a second verification number is calculated from the authentication string. The client device 200 can do this because the user provides input based on knowledge of the authentication string. The second verification number is then sent to the server device 100. A match is checked between the first and second verification number, which in turn confirms that both verification numbers were calculated from the same authentication string. Accordingly, the user is authenticated.

The parity memory 110 may contain a plurality of parity numbers for a plurality of users. For example, the verification number may be associated with a username. For example, pairs of a check number and a username can be stored. The relationship can be established by a user name derivative, such as a hash or a hash with a salt, or a hash function input modifier. In this case, the parity store 110 may store the parity along with the derivative.

On FIG. 2 schematically shows an example of an implementation of possible data dependencies. This drawing explains the possible relationship between the first and second verification numbers and the authentication string.

существует функция

, такая что

Другими словами, шифрование суммы может быть вычислено из зашифрованных слагаемых, притом это может быть сделано без знания ключа шифрования. Некоторые схемы гомоморфного шифрования могут поддерживать умножение. Существуют также схемы гомоморфного шифрования, которые поддерживают более одной операции, например сложение и умножение. Хотя такие схемы могут быть использованы в варианте реализации, такие сложные типы гомоморфного шифрования не требуются, поскольку нужна только одна операция. Примеры схем гомоморфного шифрования: Ривеста-Шамира-Адлемана (Rivest, Shamir, Adleman, RSA) (без заполнения), Эль-Гамаля (ElGamal), Гольдвасера-Микали (Goldwasser-Micali), Бенало (Benaloh), Пэйе (Paillier) и т. д. Например, числа могут быть выбраны из группы целых чисел по модулю простого числа. Другими примерами являются эллиптические кривые, сформированные некоторым генератором. Группа обратимых чисел по модулю составного числа и т. д.On FIG. 2 shows a set 310 of character/position data. Set 310 contains a number for each combination of a character from the character set and a position in the authentication string. The character/position data can be secret, but it doesn't have to be; it can be open data. Typically, the numbers are selected from a finite group, ring, or field, such as those used in the applied homomorphic encryption scheme. The homomorphic encryption scheme allows you to encrypt data, such as numbers, for example, in a group. In addition, there is at least one binary operation that can be performed on encrypted numbers. For example, a homomorphic encryption scheme that supports addition allows the sum of a set of numbers to be computed during encryption. For example, for such encryption

there is a function

, such that

In other words, the encryption of the sum can be calculated from the encrypted terms, and this can be done without knowing the encryption key. Some homomorphic encryption schemes may support multiplication. There are also homomorphic encryption schemes that support more than one operation, such as addition and multiplication. Although such schemes may be used in an implementation, such complex types of homomorphic encryption are not required since only one operation is needed. Examples of homomorphic encryption schemes: Rivest, Shamir, Adleman, RSA (no padding), ElGamal, Goldwasser-Micali, Benaloh, Paillier, and etc. For example, numbers can be chosen from the group of integers modulo a prime number. Other examples are elliptic curves generated by some generator. The group of invertible numbers modulo a composite number, etc.

On FIG. 3 schematically shows an example implementation of character/position data. A plurality of positions 410 are shown. An authentication string can be obtained by selecting a character from a set of 420 characters for each position of the authentication string. For each position combination in position set 410 and for each character in character set 420, the number of symbol/position is selected. If there are n positions and m possible characters, then there are typically nm character/position numbers. Some combinations can be omitted, but as a consequence, these character/position combinations are not possible in the authentication string.

In an embodiment, the authentication string may be of a given length, or the authentication string may be any length, at least 2 less than some maximum length. However, you do not need to use all positions from multiple positions in the authentication string. For example, authentication strings of different lengths can be supported by leaving some positions open. In an alternative implementation, the amount of character/position data can be reduced by encoding one character as an empty position. Authentication strings of different lengths can also be supported by including a fill character in the character set. You can require authentication strings to have no more than a string of consecutive characters at the end of the authentication string. On FIG. 3 shows one combination of position and symbol: the number 430.

In an embodiment, the character/position data is random numbers. Using random numbers means there is little risk of having two different authentication strings that produce the same verification numbers. Accordingly, there may be multiple authentication strings that will be accepted when authenticating a given user. However, the risk of this is low and alternative authentication strings are not known. In addition, the risk can be reduced as much as required, for example, by choosing a larger group, etc. for homomorphic encryption.

In an embodiment, the character/position data set 310 is chosen such that any subset yields a different result for an operation supported by homomorphic encryption. For example, if homomorphic encryption supports addition, then the character/position data set 310 may be selected as multiples of the base powers of the degree. The exponent base can be chosen as the number of characters in the character set. For example, if the supported operation is addition, then this choice will give different sums for each subset.

For example, if homomorphic encryption supports multiplication, then the character/position dataset 310 may be selected in terms of powers, with the exponents being multiples of the base powers of the power. The exponent base can be chosen as the number of characters in the character set. For example, if the supported operation is multiplication, then this choice will give a different product for each subset. For example, powers can be powers of a generator. An additional benefit of selecting character/position data as generator exponents is that exponentiation serves as an additional layer of encryption. In particular, deriving an authentication string from a verification number is more difficult, even if it is not blinded (see below).

In an embodiment, the character/position number is less than the group size. In an embodiment, the character/position numbers are exponents of a power base, such as a generator, and the exponents are less than the group size or order of the group generated by the generator. In an embodiment, the character/position numbers or exponents are less than the order of the group divided by the size of the character set.

The character/position data may be public, but does not have to be. In particular, for increased security against cryptographic attacks, the character/position data may be private to the client device. For example, if the character/position data is random data, an attacker analyzing the data exchanged between the server and the client device cannot determine which character/position data the observed data corresponds to. The same character/position data set is used during the setup phase as well as during each of the subsequent authentication phases. The character/position data may be randomly selected for each user whose authentication the server device 100 supports.

The authentication string 325 defines a subset 320 of the character/position data set 310 . In particular, the subset 320 includes character/position numbers corresponding to the characters actually used in the different positions of the authentication string. From the subset 320, the first check number 340 is output.

For example, the first parity number can be obtained from subset 320 by performing an operation supported by homomorphic encryption, such as a multiplication. For added security, this result can be blinded. For example, the first unblinded parity number 330 can be obtained from the subset 320 by performing a supported operation, such as multiplying the numbers in the subset. Further, the first non-blinded parity number 330 can be blinded with the blinding number 340. The latter is the (blinded) first parity number 340. For example, a supported operation can be used to enable the blinding number: for example, the blinding number can be added to the first non-blinded parity number 340 or multiplied by it. The blinding number is optional. In the absence of a blinding number, an attacker who obtains the first unblinded verification number of 330 can launch a dictionary attack to determine the authentication string. The blinding number reduces the information that the non-blinded check number 330 contains about the authentication string 325, perhaps reducing it to zero, for example. Further, we will assume that the first check number is blinded, but this is not necessary. The blinding number may be a random number, such as generated by a random number generator.

It should be noted that neither the authentication string 325, nor the unblinded verification number 330, nor the blind number 345 is required in the authentication phase by the server device. For example, the server device may receive the first parity 340 during the setup phase, for example, from a client device or from a trusted third party. In the authentication phase, the server device needs the character/position data 310 and the first verification number, whether blinded or not. If the character/position data 310 is not random, it can be computed as needed rather than stored.

Server device 100 contains block 120 encryption. Encryption unit 120 is configured to encrypt character/position data set 310 in accordance with a homomorphic encryption algorithm. Encryption is performed on an element-by-element basis. On FIG. 3, this is shown as an encrypted set 350. During authentication, the encrypted set 350 is sent to the client device 200. In order to avoid replay, it is preferable that the result of this encryption be different for different authentications. For example, this can be achieved by using a different key each time the suite 310 is encrypted, such as by choosing a random key. For example, this can be achieved by choosing a probabilistic encryption scheme (or both). For example, the encryption scheme may be ElGamal encryption, which is a homomorphic and probabilistic encryption scheme.

The client device 200 includes a homomorphic calculation unit 240 . The homomorphic calculation unit 240 is configured to calculate an encrypted second parity number from a subset 360 of the encrypted character/position data set 350 . The encrypted set 350 is received from the server device 100. For example, a user of the client device 200 may select a subset 360 of the received set 350 based on their knowledge of the authentication string 326 . If authentication string 325 and authentication string 326 are the same, then subset 360 is the same as subset 320, with the difference that subset 360 is encrypted and subset 320 is not. For example, the received set 350 may contain an indication of which character/position encrypted number corresponds to which character/position. For example, set 350 may be sorted. For example, a user may enter an authentication string on the user interface 220 of the client device 200, such as on a touch screen keyboard, etc., to select a subset 360.

This indication may or may not be machine readable. The disadvantage of specifying in a machine-readable manner which character/position cipher number in set 350 corresponds to which character/position is that client device 200 may become scannable even if server device 100 is not. It is advisable to avoid attacks on server 100 because an attack on server 100 typically means that many of the authentication strings are compromised or compromised. Because the authentication string is often reused, this can have severe security implications. Below is a solution that also reduces the risk of an attack on the client device 200.

The homomorphic calculation unit 240 is configured to homomorphically calculate an encrypted second parity number from a subset of the encrypted character/position data set. For example, homomorphic compute unit 240 may perform the same computation that is performed on set 320 to obtain the number 330, with the difference that homomorphic compute unit 240 performs the computation on encrypted data. The second check number 370 is encrypted but not blinded.

In the case of blinding, homomorphic compute unit 240 can be configured to blind the encrypted second parity number with blind number 346. If homomorphic compute unit 240 performs the same computation and blinding (albeit on encrypted data) and uses the same blinding number (but encrypted), then the second parity number 380 is the same as the first parity number 340, albeit encrypted.

There are several ways in which the client device 200 can obtain the encrypted blinding number. For example, the encrypted blinding number can be obtained in the setup phase, encrypted for each key that will be used in the authentication phase. The encrypted blinding numbers may be in the memory of the device 200. In this case, the same key or a limited number of keys may be used during authentication. In an alternative implementation, the encryption scheme may be a public/private key encryption scheme. Client device 200 may receive a public key that is also used to encrypt set 310 to obtain set 350. In this case, homomorphic cipher 240 may encrypt the blinding number itself. The blinding number may be obtained from the user or from the storage 250 of the client device 200.

является неослепленным проверочным числом, то блок гомоморфного шифрования может вычислять

,

или

и т. д. для константы

и

. Эти числа могут быть ослеплены с помощью ослепляющего числа либо до, либо после дополнительного вычисления. Например, блок 240 гомоморфного шифрования может вычислять

, а блок 140 сравнения может проверять, что второе проверочное число в

раз больше первого проверочного числа.The second parity number, whether it be the unblinded number 370 or the blinded number 380, is sent to the server device 100. The server device 100 includes a comparator 140 . The comparison unit 140 is configured to check the correspondence between the first check number and the encrypted second check number for user authentication. For example, if client device 200 performs the same calculation as server device 100 (but on encrypted data), then comparator 140 may be configured to decrypt the second parity to compare it to the first parity for equality. This is optional, although, for example, homomorphic cipher 240 may be configured to compute a different number, eg, homomorphic cipher 240 may be configured to compute twice the first parity number or add a constant to it. More generally, if

is an unblinded check number, then the homomorphic cipher block can compute

,

or

etc. for a constant

and

. These numbers can be blinded with a blinding number either before or after additional calculation. For example, block 240 homomorphic encryption can calculate

, and the comparator 140 can check that the second parity in

times the first check number.

As stated above, the implementation above protects against server-side scanning, but client-side scanning is possible. In an embodiment, additional optional protection is proposed as follows. In an embodiment, the server device 100 includes a permutation generator 150 and a data display unit 160 . The permutation generator 150 is configured to permutate the character set. The permutation generator 150 may generate a per-position per permutation, but may also generate fewer permutations than the number of positions, in which case some of the permutations are reused. For example, some permutation may be used for each position. Preferably, a new permutation is generated for at least each authentication. Server device 100 may include a random number generator to generate character/position and/or permutation data.

The data mapper 160 is configured to obtain display data for characters in the character set. The mapping data depicts characters from the character set, but in a machine-readable form. In an embodiment, the display data is retrieved from the display data store or retrieved from an external device of the display data generator. The display data may also be generated on the server device 100. Image data generation is known as such . For example, algorithms are known for generating the so-called CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart, CAPTCHA). For example, a different display data set is obtained for each position. Fewer display data sets than the number of positions may be generated, in which case some of the display data is reused. For example, some display data may be used for all positions. You don't even need to use different mapping data for each authentication. In this case, the client device caches display data to be used in subsequent authentication. Display data consumes a relatively large amount of data, which is reduced by caching. The display data may be an image, for example, there may be an image for each character. The display data may be a movie. For example, a movie is such that a human can recognize a character from an image or video clip, but a computer cannot. At the very least, the need for an attacker to analyze images or clips makes attacks more error-prone, less automated, and more resource-intensive. Thus, it becomes more difficult for an attacker to spread attacks to many users instead of a few selected users. For example, display data can be in jpg, png, etc. or mp4, avi, etc. format.

The mapping data is sent to the client device 200 along with a set of encrypted character/position data 350 . The mapping data may be sent in a permuted order, but associated with the correct character/position data. On FIG. 4 shows a permutation 500 of the character set used for PIN codes. The same can be done with larger character sets. Permutation 500 may indicate the order in which display data for characters in the character set is sent to client device 200. Display data 510 is also shown in FIG. 4. The displayed mapping data 510 is the characters in the character set, but in a non-machine readable form, in the order indicated in the permutation. In this case, display data is generated by selecting a random font and superimposing two black stripes in a random orientation. Instead, any method of generating unreadable data that is known in the art can be used. The display data corresponding to the encrypted character/position data 520-529 corresponding to the character is shown below. For example, if mapping data 510 is generated for the first position, then character/position data 520-529 is character/position data for a combination of a character in the character set and the first position. For the next position, the new character/position data is used, and optionally a new permutation and/or a new display set. In a more secure implementation, each position has its own character/position data, display set, and permutation.

The client device 200 is configured to receive display data from the server device associated with the encrypted character/position data. The client device 200 includes a display 210. The display 210 is configured to display the received display data for each item. After displaying the mapping data for a particular position, the user can select the correct character corresponding to that position in the authentication string. When selecting display data, the associated encrypted character/position data is also selected for subset 360. For example, if the first character of the authentication string is 9, then the user can select display data 511, and encrypted character/position data 521 is added to subset 361. Thus, the user selects the correct character/position data, and this without the attacker knowing what it represents: the character/position data is encrypted and corresponds to an image on the display that is not machine-readable.

For example, client device 200 may be implemented in accordance with the following pseudocode.

For each position in the authentication string, do the following:

Display the mapping data that is accepted for the position

Accept user selection for display data to display

Add encrypted character/position data for the position and the selected character to subset 360.

Various implementations of devices 100 and 200 may include an input interface that may be selected from various architectures. For example, the input interface may be a keyboard, touch screen, mouse, etc. Display data may be selected via the input interface.

Storage devices, such as storage device 110 and 250, may be implemented as electronic memory, such as flash memory, or magnetic memory, such as a hard disk drive, etc. Storage device 110 or 250 may include a plurality of discrete memories that together constitute a storage device . The storage device may also be implemented as a local storage device or an external storage device such as a cloud storage device. In the latter case, the device comprises a reader and writer for reading from and writing to an external storage device, for example via a network connection. For example, part of the storage device may be a secure storage device and the remainder may be a conventional storage device. The storage device may also contain temporary memory, such as RAM.

Typically, each of the devices 100 and 200 contains a microprocessor (not shown separately) that runs the appropriate software on the devices 100 and 200; for example, this software may have been loaded and/or stored in appropriate memory, such as volatile memory such as RAM or non-volatile memory such as flash memory (not shown separately). In an alternative implementation, the devices 100 and 200 are fully or partially implemented in programmable logic, such as, for example, a field-programmable gate array (FPGA). Devices 100 and 200 may be implemented, in whole or in part, in the form of a so-called application-specific integrated circuit (ASIC), ie, an integrated circuit (IC) custom-made for its particular application. For example, the circuits may be implemented in CMOS, for example using a hardware description language such as Verilog, VHDL, etc.

In an embodiment, devices 100 and 200 may comprise one or more circuits. The circuits implement the corresponding blocks described in this document. The circuits may be a processor circuit and a storage circuit, where the processor circuit executes instructions electronically represented in the storage circuits.

The processor circuit can be distributed, for example, in the form of several subprocessor circuits. The storage device may be distributed across a plurality of distributed storage subdevices. Some or all of the memory may be electronic memory, magnetic memory, etc. For example, a storage device may have a volatile part and a non-volatile part. Part of the storage device may be read-only.

On FIG. 5 schematically shows an exemplary embodiment of a method 500 for a server and a method 600 for a client.

Method 600 for the server is configured to authenticate a user from a client device, such as client device 200, where the user has access to an authentication string. The authentication string has a plurality of characters in a plurality of positions, the characters being selected from a character set. Method 600 for the server includes:

- storing (610) a first parity number calculated from a subset of the character/position data set, said subset being indicated by an authentication string, and the character/position data set containing a number for each combination of a character from the character set and a position in the authentication string,

- encrypting (620) the character/position data set in accordance with the homomorphic encryption algorithm and sending the encrypted set to the client device,

- receiving (630) from the client device a second verification number obtained by homomorphic calculation of an encrypted second verification number from a subset of the encrypted set, wherein the subset is indicated by said authentication string, and

- checking (640) the correspondence between the first check number and the encrypted second check number to authenticate the user.

Method 700 for a client is configured to authenticate a user to a server device, such as server device 100. The user has access to an authentication string. The authentication string has a plurality of characters in a plurality of positions, the characters being selected from a character set. Method 700 for a client includes:

- receiving (710) a character/position data set encrypted in accordance with the homomorphic encryption algorithm, wherein the encrypted character/position data set contains a number for each combination of a character from the character set and a position in the authentication string,

- homomorphic calculation (720) of the encrypted second parity number from a subset of the encrypted character/position dataset, the subset being indicated by said authentication string,

- sending (730) the encrypted second verification number to the server device.

Methods 600 and 700 may include additional steps. In particular, they may include obtaining, displaying, and selecting display data for a character set. Dependencies between the two methods are indicated by dotted arrows.

As one of skill in the art will appreciate, many different ways of performing these methods are possible. For example, the order of the steps may be changed, or some steps may be executed in parallel. In addition, other method steps may be inserted between the steps. The inserted steps may be improvements to the method, such as those described herein, or may not be relevant to the method. For example, some steps may be executed, at least in part, in parallel. In addition, this stage may not be fully completed before the start of the next stage.

The method of the present invention may be executed using software that contains instructions for causing the processor system to execute methods 600 or 700. The software may contain only those steps that are undertaken by a system component. The software may be stored on a suitable storage medium such as a hard disk, floppy disk, memory, optical disk, etc. The software may be sent as a signal over or without wire, or using a data network such as the Internet. The software may be available for download and/or remote use on a server. The method of the present invention may be executed using a bitstream capable of configuring programmable logic, such as a field programmable gate array (FPGA), to implement the method.

As may be understood, the invention also extends to computer programs, in particular to computer programs on or in a carrier capable of practicing the invention. The program may be in source code, object code, intermediate source code, and object code, such as partially compiled form, or any other form suitable for use in implementing the method of the present invention. An embodiment relating to a computer program product comprises executable instructions corresponding to each of the processing steps of at least one of the methods set forth. These instructions may be subdivided into subroutines and/or stored in one or more files, which may be linked statically or dynamically. Another embodiment related to a computer program product comprises executable instructions corresponding to each of the means of at least one of the described systems and/or products.

As described above, the authentication mechanism based on username and password is vulnerable to memory scan attacks. These memory scan attacks involve two threats. Firstly, impersonation of the user and, secondly, the loss of confidential personal information. Known solutions do not eliminate both threats. Also, known servers are attractive targets because they contain many sensitive passwords. Other and/or more detailed implementations are described below, also using more mathematical language.

таблиц, в которой каждая строка представляет цифру от 0 до 9. В такой таблице 2 столбца. Один столбец содержит данные для отображения числа приложением, например

, а второй столбец содержит некоторое произвольное значение. Обозначим как

значение в памяти, являющееся результатом нажатия значения в строке i таблицы

, т. е. значение во втором столбце строки i таблицы

. Строки переставляют, чтобы скрыть реальные значения, которые они представляют. Каждый раз, когда пользователь вводит цифру, в память загружается новая таблица, чтобы обеспечить удаление связывающей информации, такой как, являются ли две введенные цифры одинаковыми.Consider a secure keyboard. It provides protection against lost credentials due to memory scans. A secure keyboard can be viewed as a sequence

tables in which each row represents a number from 0 to 9. Such a table has 2 columns. One column contains data for the application to display a number, for example

, and the second column contains some arbitrary value. Denote as

the value in memory resulting from pressing the value in row i of the table

, i.e. the value in the second column of row i of the table

. The strings are rearranged to hide the real values they represent. Each time the user enters a digit, a new table is loaded into memory to ensure that binding information, such as whether the two digits entered are the same, is removed.

The following authentication scheme protects against replay attacks, but does not use homomorphic encryption. The server is supposed to have a database where user credentials are securely stored. This means that the database itself does not leak any user's (full) credentials.

1. The user enters his username and his (derivative) is sent to the server.

2. The server checks that the user is logged in, and if so, it does the following:

случайную матрицу

так, что все элементы в каждом столбце являются уникальными. (a) Forms a sized

random matrix

so that all elements in each column are unique.

, действующих на множестве

. (b) Generates n random permutations

acting on the set

.

отображения. (c) Generates n data sets

display.

таблицу

, содержащую в строке j пару

.(d) Defines for

table

, containing in the string j the pair

.

. (e) Responds with a newly randomly selected keyboard

.

и вводит свой PIN

, дающий в результате строку

, которую отправляют обратно серверу. 3. The user provides

and enter your PIN

, resulting in the string

, which is sent back to the server.

и

, использующей взаимосвязь

, вытекающую из того факта, что пользователь выбирает i-ю цифру PIN (

) в строке

таблицы

. Таким образом, мы делаем вывод, что

удовлетворяет соотношению

), так что

.4. The server recreates the PIN using

and

, using the relationship

, resulting from the fact that the user selects the i-th digit of the PIN (

) in line

tables

. Thus, we conclude that

satisfies the relation

), so

.

5. Finally, the server checks the PIN against its database and removes any generated data from its memory.

будет принята сервером только один раз. Поэтому злоумышленник не может повторно воспроизвести

, чтобы выдать себя за пользователя. Кроме того, эта случайность обеспечивает, что сканировщик памяти на устройстве пользователя не сможет со временем собрать конфиденциальные сведения о введенном PIN пользователя.As the server generates fresh random keyboards,

will be accepted by the server only once. Therefore, an attacker cannot replay

to impersonate the user. In addition, this randomness ensures that the memory scanner on the user's device cannot collect sensitive information about the user's entered PIN over time.

The above procedure can also be used to protect user registration from memory scanning by simply removing the registration check and replacing the server side part of the check by storing the user's credentials in a database in a secure manner.

To prevent the memory scanner on the server from obtaining confidential passwords or PINs, we suggest the following.

будет группой, сформированной посредством

, порядок которой равен большому простому числу p. Предположим, что сервер имеет базу данных, содержащую производное имен пользователей и пароля Let

will be a group formed by

, whose order is equal to a large prime number p . Suppose the server has a database containing a derivative of usernames and password

- PIN пользователя, а

- некоторый неизвестный элемент

. Поскольку

представляет собой схему «обязательств Педерсена» (Pedersen Commitment), которая теоретически скрывает информацию,

не содержит информации о PIN, когда

неизвестен [1].where PIN

- user PIN, and

- some unknown element

. Because the

is a "Pedersen Commitment" scheme that theoretically hides information

does not contain PIN information when

unknown [1].

обозначает шифрование Эль-Гамаля [2] помощью секретного ключа. Поэтому Let

denotes the encryption of ElGamal [2] using a secret key. That's why

.where r is some uniform random value modulo p and

.

, который используется в

.User U is assumed to have saved

, which is used in

.

Then authentication happens like this:

1. The user enters their username and it (its derivative) is sent to the server.

2. The server checks that the user is logged in, and if so, it does the following:

. (a) Generates a random secret key

.

случайную матрицу

, где

. (b) Forms a sized

random matrix

, where

.

, действующих на множестве

. (c) Generates n random permutations

acting on the set

.

отображения. (d) Generates n data sets

display.

таблицу

, содержащую в строке j пару

.(e) Defines for

table

, containing in the string j the pair

.

и открытого ключа

. (f) Responds with a newly randomly selected keyboard

and public key

.

и вводит свой

, дающий в результате строку

. 3. The user provides

and enter your

, resulting in the string

.

из памяти и формирует случайное шифрование

с использованием открытого ключа h. 4. User retrieves

from memory and generates a random encryption

using the public key h .

. 5. The user responds with a string

.

и проверяет, совпадает ли она с

. 6. Server decrypts

and checks if it matches

.

7. Finally, deletes all generated data from its memory.

может быть использован другой набор символов. Instead of a 10 by n matrix for the set

a different character set may be used.

может быть представлена целым числом Correctness: It should be noted that the numeric string

can be represented as an integer

Moreover, from the ElGamal homomorphism

follows

so

Registration: Then registration proceeds as follows:

1. The user enters their username and it (its derivative) is sent to the server.

2. The server checks that the user is NOT logged in, and if so, it does the following:

. (a) Generates a random secret key

.

случайную матрицу

, где

. (b) Forms a sized

random matrix

, where

.

, действующих на множестве

. (c) Generates n random permutations

acting on the set

.

отображения. (d) Generates n data sets

display.

таблицу

, содержащую в строке j пару

. (e) Defines for

table

, containing in the string j the pair

.

и открытого ключа

. (f) Responds with a newly randomly selected keyboard

and public key

.

и вводит свой выбранный

, дающий в результате строку

. 3. The user provides

and enters your chosen

, resulting in the string

.

и случайное шифрование

с использованием открытого ключа h. 4. User generates a random

and random encryption

using the public key h .

. 5. The user responds with a string

.

в

и сохраняет пользователя U вместе с

. 6. Server decrypts

in

and saves user U along with

.

7. Finally, removes all remaining generated data from its memory.

и саму

. Из семантической стойкости схемы Эль-Гамаля [3] следует, что умножение основанного на случайном ключе шифрования на результат клавиатуры скрывает, в том числе для сервера, все выборы, сделанные пользователем на клавиатуре. Это также называют ослеплением шифрования. Кроме того, обязательства Педерсена обеспечивают невозможность использования

для выделения PIN. Zero knowledge of the server: The server only sees encryption based on a random key

and herself

. From the semantic strength of the ElGamal scheme [3], it follows that the multiplication of the encryption based on a random key by the result of the keyboard hides, including for the server, all the choices made by the user on the keyboard. This is also called encryption blindness . In addition, Pedersen's obligations ensure that

to allocate a PIN.

Note: Both simple fields and elliptic curves can be used to determine the proper group that implements the above implementations.

Link sources

[1] Pedersen.: Non-interactive and information-theoretic secure verifiable secret sharing. In Advances in Cryptology CRYPTO '91 Springer

[2] T. ElGamal.: A public key cryptosystem and a signature scheme based on discrete logarithms. In Proceedings of CRYPTO 84 on Advances in Cryptology, pages 10--18, New York, NY, USA, 1985. Springer-Verlag New York, Inc.

[3] Y. Tsiounis and M. Yung.: On the security of ElGamal based encryption. In H. Imai and Y. Zheng, editors, Public Key Cryptography, volume 1431 of Lecture Notes in Computer Science, pages 117--134. Springer, 1998.

On FIG. 6a shows a computer readable medium 1000 having a portion 1010 containing a computer program 1020, the computer program 1020 including instructions for causing the processor system to execute a client method or a server method according to an embodiment. The computer program 1020 may be implemented on the computer-readable storage medium 1000 in the form of physical marks or by magnetizing the computer-readable storage medium 1000. However, any other suitable embodiment is also possible. Further, it will be appreciated that although the computer readable storage medium 1000 is shown here as an optical disc, the computer readable storage medium 1000 may be any suitable computer readable storage medium such as a hard disk drive, solid state memory, flash memory, etc., and may be made without the possibility of recording or with the possibility of recording. Computer program 1020 includes instructions for causing the processor system to execute a client method or a server method according to an embodiment.

On FIG. 6b shows a schematic representation of a processor system 1140 according to an embodiment. The processor system includes one or more integrated circuits 1110. The architecture of one or more integrated circuits 1110 is shown schematically in FIG. 6b. Circuitry 1110 includes a processing unit 1120, such as a CPU, for executing computer program components to implement the method according to the embodiment and/or implement modules or blocks thereof. Circuitry 1110 includes a memory 1122 for storing program code, data, etc. The program code configures the processor system as either a client device implementation or a server device implementation.

Portion of memory 1122 may be read-only. Circuit 1110 may include a coupler 1126, such as an antenna, connectors, or both, etc. Circuit 1110 may include an ASIC 1124 to perform some or all of the processing defined in said method. The processor 1120, memory 1122, ASIC 1124, and coupler 1126 may be connected to each other via an interconnect 1130, such as a bus. Processor system 1110 may be configured to communicate contactlessly and non-contactly using an antenna and/or connector, respectively.

For example, in an embodiment, the client device, the server device, the key generation device, and/or the signature verification device may comprise a processor circuit and a memory circuit, the processor being configured to execute software stored in the memory circuit. For example, the processor circuitry may be an Intel Core i7 processor, ARM Cortex-R8, etc. In an embodiment, the processor circuitry may be an ARM Cortex M0. The memory circuitry may be a ROM circuitry or non-volatile memory circuitry such as flash memory. The memory circuit may be a volatile memory circuit such as SRAM. In the latter case, the device may comprise a non-volatile software interface, such as a hard drive, a network interface, etc., configured to be provided with software.

It should be noted that the foregoing embodiments are illustrative, and not limiting, of the present invention, and that those skilled in the art are able to develop many alternative implementations.

In the claims, no position numbers given in brackets should be construed as limiting the claim. The use of the verb "comprises/includes" and its conjugations does not preclude the presence of other elements or steps other than those specified in a claim. The singular grammatical means used with an element does not preclude the presence of a plurality of such elements. The present invention can be implemented by means of equipment containing several different elements, and by means of an appropriately programmed computer. In a device-specific clause listing multiple features, some of those features may be implemented by the same piece of equipment. The mere fact that certain measures are set forth in mutually distinct dependent claims does not mean that a combination of these measures cannot be used effectively.

In the claims, references in parentheses refer to reference numbers in the drawings showing exemplary embodiments, or to formulas in embodiments, to make the claim more understandable. These references are not to be construed as limiting the claim.

Claims (44)

1. Server device (200) to verify the user from the client device (100), wherein the user has access to the authentication string (326), the authentication string has multiple characters in multiple positions (410), and the characters are selected from the set (420) characters, while the server device contains: - a memory device (110) storing the first check number (340,

) calculated from a subset (320) of the character/position data set (310), said subset being indicated by the authentication string (325, p ), and the data set (310,

) character/position contains a number (430) for each combination of a character from the character set and a position in the authentication string, - a processor circuit configured to: - encrypting the character/position data set according to the homomorphic encryption algorithm and sending the encrypted set (350) to the client device, - receiving from the client device a second parity number (380) obtained by homomorphic calculation of an encrypted second parity number from a subset of the encrypted set, said subset being indicated by the authentication string, and - checking the correspondence between the first check number and the encrypted second check number for user authentication. 2. The server device according to claim 1, in which the processor circuit is configured to: - forming a permutation (500) of a character set, receiving mapping data (510, 511) for characters in the character set and associating the mapping data with encrypted character/position data (530, 520-529) corresponding to said character, - sending the display data to the client device associated with the encrypted character/position data, and in order according to the generated permutation. 3. The server device according to claim 1, in which: - the same display data is used for all positions, or - at least two different positions used different display data. 4. The server device according to claim 2, wherein the client device is not sent the display data for subsequent authentication, and the cached display data is used in the client device. 5. The server device according to any one of the preceding claims, wherein the first parity number is blinded with a blinding number (

), and the calculation of the second check number includes blinding with the blinding number. 6. The server device according to any one of the preceding claims, wherein at least some of the character/position data is random numbers. 7. The server device according to any one of the preceding claims, wherein: - at least some of the character/position data is computed as multiples of the base powers of the degree, - at least some of the character/position data is computed as powers, the exponents being multiples of the powers of the base of the power. 8. The server device according to any one of the preceding claims, wherein the matching check includes deciphering the second check number. 9. The server device according to any one of the preceding claims, wherein the homomorphic encryption algorithm is a probabilistic homomorphic encryption algorithm. 10. A server device according to any one of the preceding claims, wherein the check number is a Pedersen commitment and/or where the encryption is an ElGamal encryption. 11. A client device for verifying a user for a server device, wherein the user has access to an authentication string, the authentication string has a plurality of characters in a plurality of positions, and the characters are selected from a character set, the client device comprising: - a processor circuit configured to: - receiving a set of character/position data encrypted in accordance with the homomorphic encryption algorithm, with the encrypted set (

) character/position data contains a number for each combination of a character from the character set and a position in the authentication string, - homomorphic calculation of the encrypted second check number (

) from a subset of said encrypted character/position data set, said subset being indicated by an authentication string ( p ), - sending the encrypted second verification number to the server device. 12. The client device according to claim 11, in which the processor circuit is configured to: - receiving display data from the server device associated with the encrypted character/position data, - displaying the received mapping data for each position of the authentication string; - receiving a user input selecting display data from the displayed display data, - selecting said subset according to the selected display data. 13. The client device according to any one of paragraphs. 11, 12, comprising a memory device for storing a blinding number, wherein the processor circuit is configured to blind the encrypted second parity number with the blinding number (

). 14. A method (600) for a server to validate a user from a client device (100), wherein the user has access to the authentication string (326), the authentication string has multiple characters in multiple positions (410), and the characters are selected from the set (420 ) characters, while the method for the server includes: - saving (610) the first check number (340,

) calculated from a subset (320) of the character/position data set (310), said subset being indicated by the authentication string (325, p ), and the data set (310,

) character/position contains a number (430) for each combination of a character from the character set and a position in the authentication string, - encryption (620) of the character/position data set in accordance with the homomorphic encryption algorithm and sending the encrypted set (350) to the client device, - receiving (630) from the client device a second verification number (380) obtained by homomorphic calculation of an encrypted second verification number from a subset of the encrypted set, wherein the subset is indicated by said authentication string, and - checking (640) the correspondence between the first check number and the encrypted second check number to authenticate the user. 15. A method (700) for a client to validate a user for a server device, wherein the user has access to an authentication string, the authentication string has a plurality of characters in a plurality of positions, and the characters are selected from a character set, the method for the client comprising: - receiving (710) a set of character/position data encrypted in accordance with the homomorphic encryption algorithm, wherein the encrypted set (

) character/position data contains a number for each combination of a character from the character set and a position in the authentication string, - homomorphic calculation (720) of the encrypted second check number (

) from a subset of the encrypted character/position data set, the subset being indicated by said authentication string ( p ), - sending (730) the encrypted second verification number to the server device. 16. A computer-readable storage medium (1000) containing transient and non-transitory data (1020) representing instructions whose execution by the processor system causes it to perform the method of claim 14. 17. A computer-readable storage medium (1000) containing transient and non-transitory data (1020) representing instructions, the execution of which by the processor system leads to the implementation of the method according to claim 15.

Images