Personal cryptography: a story about one useful vulnerability

  • Tutorial
image
Asymmetric cryptography has become an elegant solution to the key distribution problem. But as often happens, what helped fix one problem caused another.

The public key, due to the mathematical properties of asymmetric cryptographic algorithms, is a set of random bits that do not contain any information about the owner, so it cannot serve as an authentication tool. This flaw has led to the emergence of a hierarchical public key certification system.
Let's consider how authentication of users occurs at present:
  1. Alice goes through the verification procedure in a certification center (CA) and receives a certificate
  2. Alice sends her certificate to Bob
  3. Bob receives CA certificate
  4. Using the obtained certificates, Bob authenticates Alice.

The first to simplify this scheme was Adi Shamir in 1984. He suggested that if it were possible to use Alice’s name or email address as a public key, this would deprive the complex authentication procedure of any meaning.
For a long time, the idea of ​​Shamir remained just a beautiful cryptographic puzzle, but in 2000, thanks to one known vulnerability in elliptical cryptography, the idea was able to be realized.

Class of vulnerable elliptic curves


Elliptic cryptography is based on the assumption that it is difficult to solve the discrete logarithm problem over the field of points of an elliptic curve.
The main advantage of “elliptic” over classical asymmetric cryptography is the much smaller size of the keys. This is explained by the fact that for the classical discrete logarithm problem there are so-called subexponential decision algorithms having the following computational complexity image. Therefore, to achieve a persistence of the order of 2 80, it is necessary that the number p be 1024 bits in size.
For the discrete logarithm problem over points of the elliptic curve, no subexponential algorithms were found. The fastest algorithms for this type of task have complexityimage. This allows the use of numbers as small as 160 bits to achieve the same strength threshold of 2 80 .

Moreover, there is a special class of elliptic curves for which all of the above is not entirely true. Such curves are called supersingular . For supersingular elliptic curves, a method was found to reduce the discrete logarithm problem over the points of the elliptic curve to the classical discrete logarithm problem. Accordingly, when using supersingular curves, the main advantage of elliptic cryptography becomes a big disadvantage. The small key size characteristic of the “elliptic” will allow using the subexponential algorithm with great efficiency and hacking the whole system.

In a little more detail, I described all this in one of my recent topics, Elliptic Cryptography: Theory . Today I want to talk about the method that makes supersingular curves so vulnerable and about the protocol that turned this flaw into an advantage.

Weil Mating


In 1983, Menezes, Okamoto, and Vanstone showed that for supersingular curves there is an effective way to map pairs of curve points to a non-degenerate element of a finite field.
The isomorphism used by them for this is called Weil pairing . Corresponding to two points of the field E (F q l ) this isomorphism puts an element of the field F q l . In other words, the Weil pairing allows you to reflect the set of points of the elliptic curve in the set of residues modulo a large number.

Let (G 1 , +) be the group of points of an elliptic curve. And (G 2 , *) is a group of residues modulo a large number. And let these two groups be isomorphic with respect to the Weyl pairing e x. Weyl mating has the following properties:
  1. Identity: all performed
  2. Bilinear: for all is done
  3. Non-degeneracy: For all such that is performed
  4. Practical Efficiency: For all P and R, numbers allow efficient calculation

From bilinearity it follows that . Thus, to solve the discrete logarithm problem on elliptic curves using Weil pairing, it is necessary to calculate the pair and . Possessing these two elements of the group G 2, we can apply a subexponential algorithm to search for n .

It is the Weyl pairing that makes supersingular curves useless in EDS algorithms. On the other hand, it also helped to realize the idea of ​​Shamir.

Diffie-Hellman Decision Challenge


The fundamental problems of modern asymmetric cryptography on elliptic curves are:
  • The discrete logarithm problem. Two points of the curve P and Q are given . It is necessary to find a number a such that Q = aP . The ECDSA digital signature algorithm is based on the complexity of this task.
  • Diffie-Hellman Computational Problem. Three points of the curve are given: P, aP, bP . You must compute the abP element . This task underlies the ECDH key distribution algorithm.

In addition, there is another type of problem that is as intractable as the two previous ones, but has an effective solution for the case of supersingular curves.

Diffie-Hellman Decision Making Problem .
Four points of the curve P, aP, bP, cP are given . It is necessary to determine whether the equality a = bc holds .
Before describing how Weyl pairing helps to solve this problem, I note that the identity property for points P and Q , such that Q = aP , leads to a rather inconvenient result. According to this rule, the mapping of the pair P and Q is equal to one .
To correct this drawback, it is necessary to find another point of the same order as Q, but linearly independent of P.
There is a special method called the deforming map, denoted by F (P) . When using deforming display Weil pairing is written as: .
The expression will not be equal to one, because the point F (P) is linearly independent of P. This operation is called modified Weil pairing.

We now consider the problem of making a Diffie-Hellman decision. We calculate the pair and . Given that , equality will be fulfilled only if a = bc .

This feature of supersingular curves made it possible to implement the so-called non - interactive key distribution scheme. And it served as a new impetus for research in the field of personal cryptography .

Personal cryptography. Non-interactive SOK key separation scheme


Let's return now to the main topic of this topic. Namely, the problem of key authentication.

In 2000, a group of researchers from Sakai, Ogishi, and Kasaraha developed a key separation method similar to the Diffie-Hellman protocol. But different from the latter in that in order to get a single encryption key, Alice and Bob users do not need to exchange public keys. Instead, they use each other's names as public keys. Due to the fact that the protocol does not provide for the participation of the second party to obtain the key, he received a non-interactive definition .

The non-interactive SOK protocol (in honor of the first letters of the names of its creators) consists of the following parts.

Setting system parameters
The protocol involves three parties: Alice, Bob and Trent (a trusted center that generates keys and identifies users).

The first part of the protocol is produced directly by Trent. It performs the following operations.
  1. Generates two groups (G 1 , +) and (G 2 , *) for which modified Weil pairing e is performed . And then selects an arbitrary spawning element image.
  2. Randomly selects the number l and sets the parameter P pub = l * P. The number l is the main secret key of the system.
  3. Selects a strong cryptographic hash function f. Function f is used to display the personal information of the user ID, in an element of the group G 1 .
  4. Announces system parameters (G 1 , G 2 , e , P, P pub , f).

Generating User Keys
This part is also performed by Trent. Let ID A be some unique identifier of Alice. This may be her full name or passport details.
After checking Alice’s identity and making sure that ID A really belongs to her, Trent does the following.
  1. Calculates an element of the group G 1 as P ID = f (ID A ).
  2. Sets Alice's private key S IDa = l * P IDa

It should be noted that Alice’s private key secrecy is based on the discrete logarithm problem over the points of an elliptic curve. And since we use a weak class of elliptic curves, the key sizes must correspond to about 1024 bits, as is the case with classical asymmetric cryptography.

Key separation algorithm
Alice and Bob IDs ID A and ID B are known to both partners. Therefore, they can calculate the elements of the group G 1 P A = f (ID A ) and P B = f (ID B ).
To generate a shared key K AB, Alice computes .
Bob, in turn, calculates a shared key with Alice .
Given bilinearity property independently of each other, they get the same element of the group G 2 : .

Advantages and Disadvantages of Personal Cryptography


Advantages The
non-interactivity inherent in personal cryptography gives them one very serious advantage. The public key exchange procedure completely loses its relevance.
There is no need to wait for the certificate of the other party to establish a connection. It’s enough to use the partner’s credentials to generate a shared key.

Moreover, this allows the so-called denied encryption . If Alice and Bob exchanged encrypted messages compromising Alice, and for some reason Bob decided to divulge this correspondence, Alice may say that she did not participate in the dialogue. Since Bob could generate a shared key himself and fake Alice's messages.

disadvantages
One of them is that Trent participating in the generation of private keys will have the ability to decrypt absolutely all messages on the network. Therefore, it is most likely to use personal cryptography only in small networks that have a certain authorized person.

The second drawback is that it is still unclear what to do in case of compromising the user's private key. The task of non-interactive key cancellation is still open.

However, despite these significant drawbacks, personal cryptography looks like a very attractive technology. And who knows how everything would turn out if in 1984 Shamir found such an interesting solution for his puzzle.
Tags:

Also popular now: