Prime and Pre­ju­di­ce: Pri­ma­li­ty Tes­ting Under Ad­ver­sa­ri­al Con­di­ti­ons

Mar­tin R. Al­brecht, Jake Mas­si­mo, Ken­neth G. Pa­ter­son, Juraj So­mo­rovs­ky

ACM CCS 2018


Ab­stract

This work pro­vi­des a sys­te­ma­tic ana­ly­sis of pri­ma­li­ty tes­ting under ad­ver­sa­ri­al con­di­ti­ons, where the num­bers being tested for pri­ma­li­ty are not ge­ne­ra­ted ran­dom­ly, but in­s­tead pro­vi­ded by a pos­si­bly ma­li­cious party. Such a si­tua­ti­on can arise in se­cu­re mes­sa­ging pro­to­cols where a ser­ver sup­p­lies Dif­fie-Hell­man pa­ra­me­ters to the peers, or in a se­cu­re com­mu­ni­ca­ti­ons pro­to­col like TLS where a de­ve­loper can in­s­ert such a num­ber to be able to later pas­si­ve­ly spy on cli­ent-ser­ver data. We study a broad range of cryp­to­gra­phic li­b­ra­ries and as­sess their per­for­mance in this ad­ver­sa­ri­al set­ting. As ex­am­ples of our fin­dings, we are able to con­struct 2048-bit com­po­si­tes that are de­cla­red prime with pro­ba­bi­li­ty 1/16 by OpenSSL's pri­ma­li­ty tes­ting in its de­fault con­fi­gu­ra­ti­on; the ad­ver­ti­sed per­for­mance is 2−80. We can also con­struct 1024-bit com­po­si­tes that al­ways pass the pri­ma­li­ty tes­ting rou­ti­ne in GNU GMP when con­fi­gu­red with the re­com­men­ded mi­ni­mum num­ber of rounds. And, for a num­ber of li­b­ra­ries (Crypt­lib, Lib­Tom­Crypt, Ja­va­Script Big Num­ber, WolfSSL), we can con­struct com­po­si­tes that al­ways pass the sup­p­lied pri­ma­li­ty tests. We ex­plo­re the im­pli­ca­ti­ons of these se­cu­ri­ty failu­res in ap­p­li­ca­ti­ons, fo­cu­sing on the con­struc­tion of ma­li­cious Dif­fie-Hell­man pa­ra­me­ters. We show that, un­less ca­re­ful pri­ma­li­ty tes­ting is per­for­med, an ad­versa­ry can sup­p­ly pa­ra­me­ters (p,q,g) which on the sur­face look se­cu­re, but where the dis­cre­te lo­ga­rithm pro­blem in the sub­group of order q ge­ne­ra­ted by g is easy. We close by ma­king re­com­men­da­ti­ons for users and de­ve­lo­pers. In par­ti­cu­lar, we pro­mo­te the Bail­lie-PSW pri­ma­li­ty test which is both ef­fi­ci­ent and con­jec­tu­red to be ro­bust even in the ad­ver­sa­ri­al set­ting for num­bers up to a few thousand bits.

[eprint]

Tags: Bail­lie-PSW test, Dif­fie-Hell­man, Lucas test, Mil­ler-Ra­bin test, pu­blic-key cryp­to­gra­phy / Pri­ma­li­ty tes­ting, TLS