[PDF] Cryptanalysis of three matrix-based key establishment protocols

View - Download Cryptanalysis of three matrix-based key establishment protocols

Previous PDF

Next PDF

J. Math. Cryptol.5(2011), 159-168

DOI 10.1515/JMC.2011.010 © de Gruyter 2011Cryptanalysis of three matrix-based key establishment protocols

Simon R. Blackburn, Carlos Cid and Ciaran Mullan

Communicated by María Isabel González Vasco

Abstract.We cryptanalyse a matrix-based key transport protocol due to Baumslag, Camps, Fine, Rosenberger and Xu from 2006. We also cryptanalyse two recently pro- posed matrix-based key agreement protocols, due to Habeeb, Kahrobaei and Shpilrain, and due to Romanczuk and Ustimenko.

Keywords.Cryptanalysis, group-based cryptography.

2010 Mathematics Subject Classification.94A60.

1 Introduction

Regular proposals are made to employ groups in cryptography; see for example the survey article by Blackburn et al. [2] or the book by Myasnikov et al. [6]. In particular, matrix groups are often considered because matrices are easy to repre- sent and manipulate. However, such proposals generally have a poor reputation: we are unaware of any fully specified proposals that are widely regarded as secure. In this paper we cryptanalyse a matrix-based key transport protocol due to Baumslag, Camps, Fine, Rosenberger and Xu [1], which we refer to as the BCFRX scheme. In fact, their proposal is more general and they suggest several plat- form groups; we consider their only matrix group proposal. We cryptanalyse this scheme in a very strong sense. We show that for practical parameter sizes a passive adversary can feasibly recover the session key after observing just one run of the protocol. We find an even more efficient attack if two or more runs of the proto- col are observed. Our techniques reduce the problem of breaking the scheme to a We also cryptanalyse two recently proposed matrix-based key agreement proto- cols, due to Habeeb, Kahrobaei and Shpilrain (HKS) [4], and due to Romanczuk and Ustimenko (RU) [7]. These schemes both fail due to straightforward linear

algebra attacks. This work constitutes Sections 3 and 4.Ciaran Mullan"s work was supported by E.P.S.R.C. PhD studentship EP/P504309/1.

160S.R. Blackburn, C. Cid and C. Mullan2 The BCFRX scheme

We begin by describing the BCFRX scheme. The protocol assumes that Alice and Bob a priori share some secret information, namely their long-term secret key. The goal of the protocol is for Alice and Bob to establish a session key for subsequent cryptographic use. To achieve this, Bob chooses the session key and sends it to

Alice in three passes, as follows.

LetGbe a finitely presented group. LetAandBbe two commuting subgroups ofG(soABDBAfor allA2AandB2B). The groupGis made public and the subgroupsAandBform Alice and Bob"s long-term secret key. Then: Bob chooses a session keyK2Gand elementsB;B02B. He sends

CWDBKB0to Alice.

Alice picks elementsA;A02Aand sendsDWDACA0DABKB0A0to Bob. SinceAandBcommute, we have thatABKB0A0DBAKA0B0. Bob sends

EWDB1DB01DAKA0to Alice.

Alice computesKDA1EA01.

We can think of this protocol as Shamir"s three-pass (or no-key) protocol [5, Protocol 12.22, p. 500], with the operation of multiplying on the left and right by a group element replacing the exponentiation operation. There was no detailed discussion of security in [1], but we need to specify a security model and what it means to break the protocol, in order to cryptanalyse it. We will consider the weakest possible notion of security: the passive adversary model. So we will regard the protocol as broken if we can construct an adversary that can feasibly compute the session key, after eavesdropping on one or more runs of the protocol; this adversary must perform well for practical parameter sizes. Baumslag et al. [1] suggested several abstract platform groups to serve forG. the group of invertible44matrices of determinant 1 over the integers. It was proposed that the commuting subgroupsAandBshould be constructed as fol- lows. WritingI2for the22identity matrix, define the subgroupsUandLofG by UD SL

2.Z/ 0

0 I 2! andLD I 20

0SL2.Z/!

:(2.1) LetM2SL4.Z/be a secret matrix known to both Alice and Bob. Then we define

ADM1UMandBDM1LM:(2.2)

We may thus view the long-term secret key as the matrixM.

Cryptanalysis of three matrix-based key establishment protocols161As described the proposal is not yet fully specified, since it remains to specify

how the long-term secret keyMis chosen, and how the protocol chooses elements fromAandBat various points. It was stated in Baumslag et al. [1] that elements are picked randomly fromAandB, and we presume that the matrixMis picked in a similar fashion fromGDSL4.Z/. But since the groupGand its subgroups A;Bare infinite, the meaning of the word random is unclear in this context. Any practical cryptanalysis will depend on the details of how these random choices are made; however the cryptanalysis we give below will work for any efficient method for making these random choices that we can think of. In any fully specified implementation of the protocol, there exists an integerƒ such that the entries of all matrices generated in the protocol lie in the interval .ƒ=2;ƒ=2/. Since the standard way to represent a44integer matrix of this form uses approximately16log2ƒbits, it is natural to think of log2ƒas the security parameter of the scheme.

A cryptanalysis

Our cryptanalysis proceeds in three stages. In Stage 1, we argue that integer com- putations may be replaced by computations modulopfor various small primesp. In Stage 2 we show that knowledge of a matrixNof a restricted form allows a passive adversary to compute any session key transmitted under the scheme. Fi- nally, in Stage 3, we show that this matrixNmay be computed in practice. None of these stages is rigorous (though Stage 2 may be made so), but the stages all work well in practice.

Stage 1: Working modulop

Suppose an adversary wishes to discover a session keyK. Since the entries ofK lie in the interval betweenƒ=2andƒ=2, it is enough to findKmodnfor any n > ƒ. Indeed, this is how we approach our cryptanalysis. We will show (see Stages 2 and 3 below) that in practice we may efficiently computeKmodpifor small primespiof our choice. (We are thinking ofpias a prime of between 80 and 300 bits in length: in some sense quite large, but in general smaller thanƒ.) We run this computation for several different primespiuntilQpi> ƒ. Setting nDQpi, we can then appeal to the Chinese remainder theorem to calculate

KmodnDK.

We write this more precisely as follows. LetTbe a fully specified version of the BCFRX protocol, with SL

4.Z/as a platform. For a primep, letZpbe

the integers modulop. LetTpbe the BCFRX protocol under the platform group GDSL4.Zp/, defined as follows. We identify the subgroupsUandLdefined by (2.1) with their images in SL

4.Zp/. Let the subgroupsAandBbe chosen

162S.R. Blackburn, C. Cid and C. Mullanto be of the form (2.2) for some matrixM2Gchosen uniformly at random.

Let the protocol pick all elements fromAandBuniformly and independently at random. This makes sense sinceGis finite. We useTpto model the protocol Ttaken modulop. This model is not quite accurate: for example, it is almost certain that whenM2SL4.Z/is chosen according to the method specified inT, the distribution ofMmodpwill not be quite uniform in SL4.Zp/. But for all ways we can think of in whichTcan be specified, the protocolTpis a good model forTtaken modulop(in the sense that an adversary that succeeds in practice to recover the session key generated byTpwill also succeed in practice to recover Kmodpwhen presented with the matrices from a run of the protocolT). Note that an adversary has great freedom in choosingp, which makes the reduction to T pdifficult to design against. The fact (see below) that the session key forTpcan be feasibly computed in practice shows thatTis insecure.

Stage 2: Restricting the long-term key

We consider the protocolTpover SL4.Zp/defined above. From now on, let us write an arbitrary44matrixZin block form asZDZ

11Z12Z

21Z22
, for the obvious

22submatricesZijofZ.

The following lemma shows that there are many equivalent long-term keys for the protocolTp. Lemma 2.1.LetM2SL4.Zp/be the long-term key shared by Alice and Bob, and define subgroupsAandBbyADM1UMandBDM1LM. Let N2GL4.Zp/be any matrix such thatN1UNDAandN1LNDB. IfN is known, then any session key can be efficiently computed by a passive adversary. Proof.An adversary is presented with matricesC,DandEthat are transmitted as part of the protocol. We have thatCDBKB0,DDABKB0A0andEDAKA0 for some unknown matricesA;A02AandB;B02B. Suppose that the adversary is also able to obtain a matrixNsatisfying the conditions of the lemma. Since A;A

02A, we may writeADN1RNandA0DN1R0Nfor some unknown

matricesR;R02U. Similarly we may writeBDN1SNandB0DN1S0N for some unknown matricesS;S02L. Define an (unknown) matrixK0byK0DNKN1. Define matricesC0,D0,E0 by C

0WDNCN1DSK0S0;

D

0WDNDN1DRSK0S0R0; E0WDNEN1DRKR0:

Note that the adversary can computeC0,D0andE0.

Cryptanalysis of three matrix-based key establishment protocols163Using the fact thatS;S02LandR;R02U, we may write

C 0D

K011K012S022

S

22K021S22K022S022!

D 0D R

11K011R011R11K012S022

S

22K021R011S22K022S022!

E 0D R

11K011R011R11K012

K

021R011K022!

ClearlyK011is known to the adversary sinceK011DC011. Moreover,K022is known sinceK022DE022. To computeK012, find any matrixXsuch thatXD012DC012(note there may

be more than one suchXifK012is noninvertible). This impliesXR11K012DK012sinceS022is invertible. Thus an adversary can computeXE012DK012. Simi-

larly, to computeK021find any matrixYsuch thatD021YDC021. This implies K

021R011YDK021and an adversary can computeE021YDK021.

OnceK0is known, the session keyKmay be recovered sinceKDN1K0N.Let Mat

2.Zp/be the set of22matrices overZp. LetMat2.Zp/be

defined by D´ 1 0 0 1! 1 0 0 0! 0 0

0 0!µ

We say thatN2GL4.Zp/is ofrestricted formifN11;N222. Lemma 2.2.For any long-term keyMused in the protocolTp, there is a matrix Nof restricted form satisfying the conditions of Lemma2.1. Moreover, for an overwhelming proportion of long-term keysM, we may impose the condition that N

11DN22DI2, whereI2is the22identity matrix.

Proof.LetfWMat2.Zp/!GL2.Zp/be a function such thatf.X/X2for allX2Mat2.Zp/. Such a functionfcertainly exists: it can be derived from a standard row reduction algorithm.

Define

HWD f.M 11/ 0 0 f.M 22/!
andNWDHM:

164S.R. Blackburn, C. Cid and C. MullanThe definition ofHmeans thatN11;N222, and soNis of restricted form.

Also, any matrix

H2 GL

2.Zp/ 0

0GL2.Zp/!

has the property thatH1UHDUandH1LHDL. So N

1UNDM1H1UHMDM1UMDA

and similarlyBDN1LN. So the main statement of the lemma is proved. To see why the last statement of the lemma holds, note that for an overwhelmingquotesdbs_dbs29.pdfusesText_35

[PDF] sl6 bac pro

[PDF] co2 polaire ou apolaire

[PDF] molécule apolaire def

[PDF] transcription acte de mariage franco-algérien nantes 2015

[PDF] ccm mariage tunisie

[PDF] formulaire transcription de mariage tunisien

[PDF] formulaire de transcription de mariage franco-marocain

[PDF] mariage sans ccm maroc

[PDF] certificat de capacité de mariage tunisie pdf

[PDF] capacité de mariage franco tunisien

[PDF] transcription mariage marocain sans ccm

[PDF] transcription mariage franco marocain 2016

[PDF] transcription acte de mariage francais au consulat du maroc

[PDF] demande de transcription d'acte de mariage célébré au maroc

[PDF] ccp chimie 2 pc 2014 corrigé