Linear Subspace Cryptanalysis of Harn’s Secret Sharing-Based Group Authentication Scheme

摘要

Shamir's secret sharing is used as an important underlying primitive in many other cryptographic schemes, such as group authentication and group key agreement schemes. Although Shamir secret sharing has unconditional security, it is not necessarily the case for the protocols founded on that. A common imperfect assumption in such schemes is to be satisfied of only hiding the polynomials coefficients from the adversary. In this direction, we present a new method that can be potentially used for cryptanalysis of some Shamir's secret sharing-based schemes. This method is called the linear subspace cryptanalysis, in which the attack problem is made equivalent to the problem of studying the belongingness of a vector to a given linear subspace. Using the proposed method, we analyse the Harn's group authentication protocol, which is a remarkable scheme recently designed based on Shamir's scheme. This scheme has two main variants: one-time asynchronous and multiple-time asynchronous. In the one-time variant, it has been evaluated by the designer that the number of group members should be bounded to n <; kt + 1, in order to make the scheme resistant against outside attacks. This constraint has been relaxed in the multiple-time variant, backed by the hardness of the discrete logarithm problem. In this paper, we show that neither confining the number of group members nor using discrete logarithm have made the one-time and multiple-time variants of this scheme resistant against impersonation attack. We show that, in both cases, an outside attacker can impersonate an authorized group member in a polynomial time, when at least t + k-1 authorized members are participating in the group authentication session. The main observation, based on which the attack works, is that the dimension of the linear subspace spanned by the Lagrange components for any predefined set of users never exceeds t +k-1.