Diffie-Hellman For our discussion of public-key cryptography, we're going to follow the historical path. Public-key cryptography was really started by Whitfield Diffie and Martin Hellman when they published their article "New Directions in Cryptography" in 1976 [33]. So far in this book, we've only talked about encryption and authentication with shared secret keys. But where do we get those shared secret keys from? If you have 10 friends you want to communicate with, you can meet them all and exchange a secret key with each of these friends for future use. But like all keys, these keys should be refreshed regularly, so at some point you will have to meet and exchange keys all over again. A total of 45 keys are needed for a group of 10 friends. But as the group gets larger, the number of keys grows quadratically. For 100 people all communicating with each other, you need 4950 keys. Specifically, in a group of N people, we would need N(N - 1)/2 keys. This quickly becomes unmanageable. Diffie and Hellman posed the question of whether it would be possible to do this more efficiently. Suppose you have an encryption algorithm where the encryption and decryption keys are different. You could publish your encryption key and keep your decryption key secret. Anyone could then send you an encrypted message, and only you could decrypt it. This would solve the problem of having to distribute so many different keys. Diffie and Hellman posed the question, but they could only provide a partial answer. Their partial solution is today known as the Diffie-Hellman key exchange protocol, often shortened to DH protocol [33]. 1 81 182 Part III Key Negotiation The DH protocol is a really nifty idea. It turns out that two people communicating over an insecure line can agree on a secret key in such a way that both of them end up with the same key, without divulging it to someone who is listening in on their conversation. 1 1 .1 Groups If you've read the last chapter, it won't surprise you that primes are involved. For the rest of this chapter, p is a large prime. Think of p as being 2000 to 4000 bits long. Most of our computations in this chapter will be modulo p-in many places we will not specify this again explicitly. The DH protocol uses Z;, the multiplicative group modulo p that we discussed in Section 10.3.3. Choose any g in the group and consider the numbers 1,g,g2,g3, ... , all modulo p, of course. This is an infinite sequence of numbers, but there is only a finite set of numbers in Z;. (Remember, Z; is the numbers 1, ... , p - 1 together with the operation of multiplication modulo p.) At some point, the numbers must start to repeat. Let us assume this happens at gi = gi with i < j.="" as="" we="" can="" do="" division="" modulo="" p,="" we="" can="" divide="" each="" side="" by="" g="" i="" and="" get="" 1="gj-i." in="" other="" words,="" there="" is="" a="" number="" q="" :="j" -="" i="" such="" that="" t'="1" (mod="" p).="" we="" call="" the="" smallest="" positive="" value="" q="" for="" which="" t'="1" (mod="" p)="" the="" order="" of="" g.="" (unfortunately,="" there="" is="" quite="" a="" bit="" of="" terminology="" associated="" with="" this="" stuff.="" we="" feel="" it="" is="" better="" to="" use="" the="" standard="" terminology="" than="" invent="" our="" own="" words;="" this="" will="" avoid="" confusion="" when="" reading="" other="" books.)="" if="" we="" keep="" on="" multiplying="" gs,="" we="" can="" reach="" the="" numbers="" 1,g,g2,="" ...="" ,t'-l.="" after="" that,="" the="" sequence="" repeats="" as="" t'="1." we="" say="" that="" g="" is="" a="" generator="" and="" that="" it="" generates="" the="" set="" 1,g,g2,="" ...="" ,t'-l.="" the="" number="" of="" elements="" that="" can="" be="" written="" as="" a="" power="" of="" g="" is="" exactly="" q,="" the="" order="" of="" g.="" one="" property="" of="" multiplication="" modulo="" p="" is="" that="" there="" is="" at="" least="" one="" g="" that="" generates="" the="" entire="" group.="" that="" is,="" there="" is="" at="" least="" one="" g="" value="" for="" which="" q="P" -="" 1.="" so="" instead="" of="" thinking="" of="" z;="" as="" the="" numbers="" 1,="" .="" ..="" ,="" p="" -="" 1,="" we="" can="" also="" think="" of="" them="" as="" 1,="" g,="" g2,="" ...="" ,="" gp-2.="" a="" g="" that="" generates="" the="" entire="" group="" is="" called="" a="" primitive="" element="" of="" the="" group.="" other="" values="" of="" g="" can="" generate="" smaller="" sets.="" observe="" that="" if="" we="" multiply="" two="" numbers="" from="" the="" set="" generated="" by="" g,="" we="" get="" another="" power="" of="" g,="" and="" therefore="" another="" element="" from="" the="" set.="" if="" you="" go="" through="" all="" the="" math,="" it="" turns="" out="" that="" the="" set="" generated="" by="" g="" is="" another="" group.="" that="" is,="" you="" can="" multiply="" and="" divide="" in="" this="" group="" just="" as="" you="" can="" in="" the="" large="" group="" modulo="" p.="" these="" smaller="" groups="" are="" called="" subgroups="" (see="" section="" 10.3.3).="" they="" will="" be="" important="" in="" various="" attacks.="" there="" is="" one="" last="" thing="" to="" explain.="" for="" any="" element="" g,="" the="" order="" of="" g="" is="" a="" divisor="" of="" p="" -="" 1.="" this="" isn't="" too="" hard="" to="" see.="" choose="" g="" to="" be="" a="" primitive="" element.="" let="" h="" be="" any="" other="" element.="" as="" g="" generates="" the="" whole="" group,="" there="" is="" an="" x="" such="" chapter="" 11="" •="" diffie-hellman="" 1="" 83="" that="" h="?." now="" consider="" the="" elements="" generated="" by="" h.="" these="" are="" 1,="" h,="" h2,="" h3,="" ••.="" which="" are="" equal="" to="" 1,?,g2x="" ,="" tx="" ,="" ....="" (all="" our="" computations="" are="" still="" modulo="" p,="" of="" course.)="" the="" order="" of="" h="" is="" the="" smallest="" q="" at="" which="" hq="1," which="" is="" the="" same="" as="" saying="" it="" is="" the="" smallest="" q="" such="" that="" q="1." for="" any="" t,="" t="1" is="" the="" same="" as="" saying="" t="0" (mod="" p="" -="" 1).="" so="" q="" is="" the="" smallest="" q="" such="" that="" xq="0" (mod="" p="" -="" 1).="" this="" happens="" when="" q="(p" -="" 1)/="" gcd(x,="" p="" -="" 1).="" so="" q="" is="" obviously="" a="" factor="" of="" p="" -="" 1.="" here's="" a="" simple="" example.="" let's="" choose="" p="7." if="" we="" choose="" g="3" then="" g="" is="" a="" primitive="" element="" because="" 1,g,g2,="" ...="" ,gs="1," 3,="" 2,="" 6,="" 4,="" 5.="" (again,="" all="" computations="" are="" modulo="" p.)="" the="" element="" h="2" generates="" the="" subgroup="" 1,="" h,="" h2="1," 2,4="" because="" h3="23" mod="" 7="1." the="" element="" h="6" generates="" the="" subgroup="" 1,="" 6.="" these="" subgroups="" have="" sizes="" 3="" and="" 2="" respectively,="" which="" are="" both="" divisors="" of="" p="" -="" 1.="" this="" also="" explains="" parts="" of="" the="" fermat="" test="" we="" talked="" about="" in="" section="" 10.4.1.="" fermat's="" test="" is="" based="" on="" the="" fact="" that="" for="" any="" a="" we="" have="" ap-1="1." this="" is="" easy="" to="" check.="" let="" g="" be="" a="" generator="" of="" z;,="" and="" let="" x="" be="" such="" that="" =="" a.="" as="" g="" is="" a="" generator="" of="" the="" entire="" group,="" there="" is="" always="" such="" an="" x.="" but="" now="" ap-1="?(P-l)" =="" (gp-l)x="I" x="1." 1="" 1="" .2="" basic="" dh="" for="" the="" original="" dh="" protocol,="" we="" first="" choose="" a="" large="" prime="" p,="" and="" a="" primitive="" element="" g="" that="" generates="" the="" whole="" group="" z;.="" both="" p="" and="" g="" are="" public="" constants="" in="" this="" protocol,="" and="" we="" assume="" that="" all="" parties,="" including="" the="" attackers,="" know="" them.="" the="" protocol="" is="" shown="" in="" figure="" 11.1.="" this="" is="" one="" of="" the="" usual="" ways="" in="" which="" we="" write="" cryptographic="" protocols.="" there="" are="" two="" parties="" involved:="" alice="" and="" bob.="" time="" progresses="" from="" the="" top="" to="" the="" bottom.="" first="" alice="" chooses="" a="" random="" x="" in="" z;,="" which="" is="" the="" same="" as="" choosing="" a="" random="" number="" in="" 1,="" ...="" ,="" p="" -="" 1.="" she="" computes="" mod="" p="" and="" sends="" the="" result="" to="" bob.="" bob="" in="" turn="" chooses="" a="" random="" y="" in="" z;.="" he="" computes="" gy="" mod="" p="" and="" sends="" the="" result="" to="" alice.="" the="" final="" result="" k="" is="" defined="" as="" y.="" alice="" can="" compute="" this="" by="" raising="" the="" gy="" she="" got="" from="" bob="" to="" the="" power="" x="" that="" she="" knows.="" (high-school="" math:="" (gyy="?Y.)" similarly,="" bob="" can="" compute="" k="" as="" )y.="" they="" both="" end="" up="" with="" the="" same="" value="" k,="" which="" they="" can="" use="" as="" a="" secret="" key.="" but="" what="" about="" an="" attacker?="" the="" attacker="" gets="" to="" see="" and="" gy,="" but="" not="" x="" or="" y.="" the="" problem="" of="" computing="" y="" given="" and="" gy="" is="" known="" as="" the="" diffie-hellman="" problem,="" or="" dh="" problem="" for="" short.="" as="" long="" as="" p="" and="" g="" are="" chosen="" correctly,="" there="" is="" no="" known="" efficient="" algorithm="" to="" compute="" this.="" the="" best="" method="" known="" is="" to="" first="" compute="" x="" from="" ,="" after="" which="" the="" attacker="" can="" compute="" k="" as="" (gyy="" just="" like="" alice="" did.="" in="" the="" real="" numbers,="" computing="" x="" from="" is="" called="" the="" logarithm="" function,="" which="" you="" find="" on="" any="" scientific="" calculator.="" in="" the="" finite="" field="" z;,="" it="" is="" called="" a="" discrete="" logarithm,="" and="" in="" general="" the="" problem="" of="" computing="" x="" from="" in="" a="" finite="" group="" is="" known="" as="" the="" discrete="" logarithm="" problem,="" or="" dl="" problem.="" 1="" 84="" part="" iii="" •="" key="" negotiation="" alice="" x="" en="" z;="" figure="" 11.1:="" the="" original="" diffie-hellman="" protocol.="" bob="" yen="" z;="" the="" original="" dh="" protocol="" can="" be="" used="" in="" many="" ways.="" we've="" written="" it="" as="" an="" exchange="" of="" messages="" between="" two="" parties.="" another="" way="" of="" using="" it="" is="" to="" let="" everybody="" choose="" a="" random="" x,="" and="" publish?="" (mod="" p)="" in="" the="" digital="" equivalent="" of="" a="" phone="" book.="" if="" alice="" wants="" to="" communicate="" with="" bob="" securely,="" she="" gets="" gy="" from="" the="" phone="" book,="" and="" using="" her="" x,="" computes="" gry.="" bob="" can="" similarly="" compute="" y="" without="" any="" interaction="" with="" alice.="" this="" makes="" the="" system="" usable="" in="" settings="" such="" as="" e-mail="" where="" there="" is="" no="" direct="" interaction.="" 1="" 1="" .3="" man="" in="" the="" middle="" the="" one="" thing="" that="" dh="" does="" not="" protect="" against="" is="" the="" so-called="" man-in-themiddle="" attack.1="" look="" back="" at="" the="" protocol.="" alice="" knows="" she="" is="" communicating="" with="" somebody,="" but="" she="" does="" not="" know="" with="" whom="" she="" is="" communicating.="" eve="" can="" sit="" in="" the="" middle="" of="" the="" protocol="" and="" pretend="" to="" be="" bob="" when="" speaking="" to="" alice,="" and="" pretend="" to="" be="" alice="" when="" speaking="" to="" bob.="" this="" is="" shown="" in="" figure="" 11.2.="" to="" alice,="" this="" protocol="" looks="" just="" like="" the="" original="" dh="" protocol.="" there="" is="" no="" way="" in="" which="" alice="" can="" detect="" that="" she="" is="" talking="" to="" eve,="" not="" bob.="" the="" same="" holds="" for="" bob.="" eve="" can="" keep="" up="" these="" pretenses="" for="" as="" long="" as="" she="" likes.="" suppose="" alice="" and="" bob="" start="" to="" communicate="" using="" the="" secret="" key="" they="" think="" they="" have="" set="" up.="" all="" eve="" needs="" to="" do="" is="" forward="" all="" the="" communications="" between="" alice="" and="" bob.="" of="" course,="" eve="" has="" to="" decrypt="" all="" the="" data="" she="" gets="" from="" alice="" that="" was="" encrypted="" with="" key="" k,="" and="" then="" encrypt="" it="" again="" with="" key="" k'="" to="" send="" to="" bob.="" she="" has="" to="" do="" the="" same="" with="" the="" traffic="" in="" the="" other="" direction="" as="" well,="" but="" that="" is="" not="" a="" lot="" of="" work.="" with="" a="" digital="" phone="" book,="" this="" attack="" is="" harder.="" as="" long="" as="" the="" publisher="" of="" the="" book="" verifies="" the="" identity="" of="" everybody="" when="" they="" send="" in="" their="" ,="" alice="" knows="" she="" is="" using="" bob's="" .="" we'll="" discuss="" other="" solutions="" when="" we="" talk="" about="" digital="" signatures="" and="" pkls="" later="" on="" in="" this="" book.="" ithe="" terminology="" may="" look="" similar,="" but="" a="" man-in-the-middle="" attack="" is="" different="" than="" a="" meet-inthe-middle="" attack="" from="" section="" 2.7.2.="" chapter="" 11="" •="" diffie-hellman="" alice="" eve="" bob="" x="" en="" z;="" -------+="" v="" en="" z;="" g="" -------+="" v="" yen="" z;="" +------="" gy="" w="" en="" z;="" +------="" gw="" k="" (gwy="" k="" (g')w="" k'="" +---="" (gyy="" k'="" +---="" (gv)y="" figure="" 11.2:="" diffie-hellman="" protocol="" with="" eve="" in="" the="" middle.="" there="" is="" at="" least="" one="" setting="" where="" the="" man-in-the-middle="" attack="" can="" be="" addressed="" without="" further="" infrastructure.="" if="" the="" key="" k="" is="" used="" to="" encrypt="" a="" phone="" conversation="" (or="" a="" video="" link),="" alice="" can="" talk="" to="" bob="" and="" recognize="" him="" by="" his="" voice.="" let="" h="" be="" a="" hash="" function="" of="" some="" sort.="" if="" bob="" reads="" the="" first="" few="" digits="" of="" h(k)="" to="" alice,="" then="" alice="" can="" verify="" that="" bob="" is="" using="" the="" same="" key="" she="" is.="" alice="" can="" read="" the="" next="" few="" digits="" of="" h(k)="" to="" bob,="" to="" allow="" bob="" to="" do="" the="" same="" verification.="" this="" works,="" but="" only="" in="" situations="" where="" you="" can="" tie="" knowledge="" of="" the="" key="" k="" to="" the="" actual="" person="" on="" the="" other="" side.="" in="" most="" computer="" communications,="" this="" solution="" is="" not="" possible.="" and="" if="" eve="" ever="" succeeds="" in="" building="" a="" speech="" synthesizer="" that="" can="" emulate="" bob,="" it="" all="" falls="" apart.="" finally,="" the="" biggest="" problem="" with="" this="" solution="" is="" that="" it="" requires="" discipline="" from="" the="" users,="" which="" is="" risky="" since="" users="" regularly="" ignore="" security="" procedures.="" in="" general,="" it="" is="" much="" better="" to="" have="" technical="" mechanisms="" for="" thwarting="" man-in-the-middle="" attacks.="" 1="" 1="" .4="" pitfalls="" implementing="" the="" dh="" protocol="" can="" be="" a="" bit="" tricky.="" for="" example,="" if="" eve="" intercepts="" the="" communications="" and="" replaces="" both="" g"="" and="" gy="" with="" the="" number="" i,="" then="" both="" alice="" and="" bob="" will="" end="" up="" with="" k="1." the="" result="" is="" a="" key="" negotiation="" protocol="" that="" looks="" as="" if="" it="" completed="" successfully,="" except="" that="" eve="" knows="" the="" resulting="" key.="" that="" is="" bad,="" and="" we="" will="" have="" to="" prevent="" this="" attack="" in="" some="" way.="" a="" second="" problem="" is="" if="" the="" generator="" g="" is="" not="" a="" primitive="" element="" of="" z;="" but="" rather="" generates="" only="" a="" small="" subgroup.="" maybe="" g="" has="" an="" order="" of="" one="" million.="" 1="" 85="" 1="" 86="" part="" iii="" •="" key="" negotiation="" in="" that="" case,="" the="" set="" {="" 1,g,i,="" .="" .="" .="" ,g'l-l="" }="" only="" contains="" a="" million="" elements.="" as="" k="" is="" in="" this="" set,="" eve="" can="" easily="" search="" for="" the="" correct="" key.="" obviously,="" one="" of="" the="" requirements="" is="" that="" g="" must="" have="" a="" high="" order.="" but="" who="" chooses="" p="" and="" g?="" all="" users="" are="" using="" the="" same="" values,="" so="" most="" of="" them="" get="" these="" values="" from="" someone="" else.="" to="" be="" safe,="" they="" have="" to="" verify="" that="" p="" and="" g="" are="" chosen="" properly.="" alice="" and="" bob="" should="" each="" check="" that="" p="" is="" prime,="" and="" that="" g="" is="" a="" primitive="" element="" modulo="" p.="" the="" subgroups="" modulo="" p="" form="" a="" separate="" problem.="" eve's="" attack="" of="" replacing="" [f="" with="" the="" number="" 1="" is="" easy="" to="" counter="" by="" having="" bob="" check="" for="" this.="" but="" eve="" could="" also="" replace="" [f="" with="" the="" number="" h,="" where="" h="" has="" a="" small="" order.="" the="" key="" that="" bob="" derives="" now="" comes="" from="" the="" small="" set="" generated="" by="" h,="" and="" eve="" can="" try="" all="" possible="" values="" to="" find="" k.="" (of="" course,="" eve="" can="" play="" the="" same="" attack="" against="" alice.)="" what="" both="" alice="" and="" bob="" have="" to="" do="" is="" verify="" that="" the="" numbers="" they="" receive="" do="" not="" generate="" small="" subgroups.="" let's="" have="" a="" look="" at="" the="" subgroups.="" working="" modulo="" a="" prime,="" all="" (multiplicative)="" subgroups="" can="" be="" generated="" from="" a="" single="" element.="" the="" entire="" group="" z;="" consists="" of="" the="" elements="" 1,="" ...="" ,p="" -="" 1="" for="" a="" total="" of="" p="" -="" 1="" elements.="" each="" subgroup="" is="" of="" the="" form="" 1,="" h,="" h2,="" h3,="" •••="" ,="" hq-1="" for="" some="" h="" and="" where="" q="" is="" the="" order="" of="" h.="" as="" we="" discussed="" earlier,="" it="" turns="" out="" that="" q="" must="" be="" a="" divisor="" of="" p="" -="" 1.="" in="" other="" words:="" the="" size="" of="" any="" subgroup="" is="" a="" divisor="" of="" p="" -="" 1.="" the="" converse="" also="" holds:="" for="" any="" divisor="" d="" of="" p="" -="" 1="" there="" is="" a="" single="" subgroup="" of="" size="" d.="" if="" we="" don't="" want="" any="" small="" subgroups,="" then="" we="" must="" avoid="" small="" divisors="" of="" p="" -="" 1.="" there="" is="" another="" reason="" for="" wanting="" large="" subgroups.="" it="" turns="" out="" that="" if="" the="" prime="" factorization="" of="" p="" -="" 1="" is="" known,="" then="" computing="" the="" discrete="" log="" of="" [f="" can="" be="" broken="" down="" into="" a="" set="" of="" discrete="" log="" computations="" over="" subgroups.="" this="" is="" a="" problem.="" if="" p="" is="" a="" large="" prime,="" then="" p="" -="" 1="" is="" always="" even,="" and="" therefore="" divisible="" by="" 2.="" thus="" there="" is="" a="" subgroup="" with="" two="" elements;="" it="" consists="" of="" the="" elements="" 1="" and="" p="" -="" 1.="" but="" apart="" from="" this="" subgroup="" that="" is="" always="" present,="" we="" can="" avoid="" other="" small="" subgroups="" by="" insisting="" that="" p="" -="" 1="" have="" no="" other="" small="" factors.="" 1="" 1="" .5="" safe="" primes="" one="" solution="" is="" to="" use="" a="" safe="" prime="" for="" p.="" a="" safe="" prime="" is="" a="" (large="" enough)="" prime="" p="" of="" the="" form="" 2q="" +="" 1="" where="" q="" is="" also="" prime.="" the="" multiplicative="" group="" z;="" now="" has="" the="" following="" subgroups:="" -="" the="" trivial="" subgroup="" consisting="" only="" of="" the="" number="" 1.="" -="" the="" subgroup="" of="" size="" 2,="" consisting="" of="" 1="" and="" p="" -="" 1.="" -="" the="" subgroup="" of="" size="" q.="" -="" the="" full="" group="" of="" size="" 2q.="" chapter="" 11="" diffie-hellman="" 1="" 81="" the="" first="" two="" are="" trivial="" to="" avoid.="" the="" third="" is="" the="" group="" we="" want="" to="" use.="" the="" full="" group="" has="" one="" remaining="" problem.="" consider="" the="" set="" of="" all="" numbers="" modulo="" p="" that="" can="" be="" written="" as="" a="" square="" of="" some="" other="" number="" (modulo="" p,="" of="" course).="" it="" turns="" out="" that="" exactly="" half="" the="" numbers="" in="" 1,="" ...="" ,="" p="" -="" 1="" are="" squares,="" and="" the="" other="" half="" are="" non-squares.="" any="" generator="" of="" the="" entire="" group="" is="" a="" non-square.="" (if="" it="" were="" a="" square,="" then="" raising="" it="" to="" some="" power="" could="" never="" generate="" a="" non-square,="" so="" it="" does="" not="" generate="" the="" whole="" group.)="" there="" is="" a="" mathematical="" function="" called="" the="" legendre="" symbol="" that="" determines="" whether="" a="" number="" modulo="" p="" is="" a="" square="" or="" not,="" without="" ever="" needing="" to="" find="" the="" root.="" there="" are="" efficient="" algorithms="" for="" computing="" the="" legendre="" symbol.="" so="" if="" g="" is="" a="" non-square="" and="" you="" send="" out="" gr,="" then="" any="" observer,="" such="" as="" eve,="" can="" immediately="" determine="" whether="" x="" is="" even="" or="" odd.="" if="" x="" is="" even,="" then="" gr="" is="" a="" square.="" if="" x="" is="" odd,="" then="" gr="" is="" a="" non-square.="" as="" eve="" can="" determine="" the="" squareness="" of="" a="" number="" using="" the="" legendre="" symbol="" function,="" she="" can="" determine="" whether="" x="" is="" odd="" or="" even;="" eve="" cannot="" learn="" the="" value="" x,="" except="" for="" the="" least="" significant="" bit.="" the="" solution="" for="" avoiding="" this="" problem="" is="" to="" use="" only="" squares="" modulo="" p.="" this="" is="" exactly="" the="" subgroup="" of="" order="" q.="" another="" nice="" property="" is="" that="" q="" is="" prime,="" so="" there="" are="" no="" further="" subgroups="" we="" have="" to="" worry="" about.="" here="" is="" how="" to="" use="" a="" safe="" prime.="" choose="" (p,q)="" such="" that="" p="2q" +="" 1="" and="" both="" p="" and="" q="" are="" prime.="" (you="" can="" use="" the="" isprime="" function="" to="" do="" this="" on="" a="" trial-and-error="" basis.)="" choose="" a="" random="" number="" a="" in="" the="" range="" 2,="" ...="" ,p="" -="" 2="" and="" set="" g="0'2" (mod="" p).="" check="" that="" g="" #-="" 1="" and="" g="" #-="" p="" -="" 1.="" (if="" g="" is="" one="" of="" these="" forbidden="" values,="" choose="" another="" a="" and="" try="" again.)="" the="" resulting="" parameter="" set="" (p,="" q,g)="" is="" suitable="" for="" use="" in="" the="" diffie-hellman="" protocol.="" every="" time="" alice="" (or="" bob)="" receives="" a="" value="" that="" is="" supposed="" to="" be="" a="" power="" of="" g,="" she="" (or="" he)="" must="" check="" that="" the="" value="" received="" is="" indeed="" in="" the="" subgroup="" generated="" by="" g.="" when="" you="" use="" a="" safe="" prime="" as="" described="" above,="" you="" can="" use="" the="" legendre="" symbol="" function="" to="" check="" for="" proper="" subgroup="" membership.="" there="" is="" also="" a="" simpler="" but="" slower="" method.="" a="" number="" r="" is="" a="" square="" if="" and="" only="" if="" r="" q="1" (mod="" p).="" you="" also="" want="" to="" forbid="" the="" value="" 1,="" as="" its="" use="" always="" leads="" to="" problems.="" so="" the="" full="" test="" is:="" r="" #-="" 1="" \="" rq="" mod="" p="1." 1="" 1="" .6="" using="" a="" smaller="" subgroup="" the="" disadvantage="" of="" using="" the="" safe="" prime="" approach="" is="" that="" it="" is="" inefficient.="" if="" the="" prime="" p="" is="" n="" bits="" long,="" then="" q="" is="" n="" -="" 1="" bits="" long="" and="" so="" all="" exponents="" are="" n="" -="" 1="" bits="" long.="" the="" average="" exponentiation="" will="" take="" about="" 3n/2="" multiplications="" of="" numbers="" modulo="" p.="" for="" large="" primes="" p,="" this="" is="" quite="" a="" lot="" of="" work.="" the="" standard="" solution="" is="" to="" use="" a="" smaller="" subgroup.="" here="" is="" how="" that="" is="" done.="" we="" start="" by="" choosing="" q="" as="" a="" 2s6-bit="" prime.="" (in="" other="" words:="" 2255="">< q="">< 22="" 56).="" next="" we="" find="" a="" (much)="" larger="" prime="" p="" such="" that="" p="Nq" +="" 1="" for="" some="" arbitrary="" 1="" 88="" part="" iii="" key="" negotiation="" value="" n.="" to="" do="" this,="" we="" choose="" n="" randomly="" in="" the="" suitable="" range,="" compute="" p="" as="" nq="" +="" 1,="" and="" check="" whether="" p="" is="" prime.="" as="" p="" must="" be="" odd,="" it="" is="" easy="" to="" see="" that="" n="" must="" be="" even.="" the="" prime="" p="" will="" be="" thousands="" of="" bits="" long.="" next,="" we="" have="" to="" find="" an="" element="" of="" order="" q.="" we="" do="" that="" in="" a="" similar="" fashion="" to="" the="" safe="" prime="" case.="" choose="" a="" random="" a="" in="" z;="" and="" set="" g:="a" n.="" now="" verify="" that="" g="1=" 1="" and="" t'="1." (the="" case="" g="p" -="" 1="" is="" covered="" by="" the="" second="" test,="" as="" q="" is="" odd.)="" if="" g="" is="" not="" satisfactory,="" choose="" a="" different="" a="" and="" try="" again.="" the="" resulting="" parameter="" set="" (p,="" q,g)="" is="" suitable="" for="" use="" in="" the="" diffie-hellman="" protocol.="" when="" we="" use="" this="" smaller="" subgroup,="" the="" values="" that="" alice="" and="" bob="" will="" exchange="" are="" all="" in="" the="" subgroup="" generated="" by="" g.="" but="" eve="" could="" interfere="" and="" substitute="" a="" completely="" different="" value.="" therefore,="" every="" time="" alice="" or="" bob="" receives="" a="" value="" that="" is="" supposed="" to="" be="" in="" the="" subgroup="" generated="" by="" g,="" he="" or="" she="" should="" check="" that="" it="" actually="" is.="" this="" check="" is="" the="" same="" as="" in="" the="" safe="" prime="" case.="" a="" number="" r="" is="" in="" the="" proper="" subgroup="" if="" r="1=" 1="" \="" rq="" mod="" p="1." of="" course,="" they="" should="" also="" check="" that="" r="" is="" not="" outside="" the="" set="" of="" modulo-p="" numbers,="" so="" the="" full="" check="" becomes="" 1="">< r="">< p="" \="" rq="1." for="" all="" numbers="" r="" in="" the="" subgroup="" generated="" by="" g="" we="" have="" that="" rq="1." so="" if="" you="" ever="" need="" to="" raise="" number="" r="" to="" a="" power="" e,="" you="" only="" have="" to="" compute="" r="" cmodq,="" which="" can="" be="" considerably="" less="" work="" than="" computing="" r="" e="" directly="" if="" e="" is="" much="" larger="" than="" q.="" how="" much="" more="" efficient="" is="" the="" subgroup="" case?="" the="" large="" prime="" p="" is="" at="" least="" 2000="" bits="" long.="" in="" the="" safe-prime="" situation,="" computing="" a="" general="" takes="" about="" 3000="" multiplications.="" in="" our="" subgroup="" case,="" takes="" about="" 384="" multiplies="" because="" x="" can="" be="" reduced="" modulo="" q="" and="" is="" therefore="" only="" 256="" bits="" long.="" this="" is="" a="" savings="" of="" a="" factor="" of="" nearly="" eight.="" when="" p="" grows="" larger,="" the="" savings="" increase="" further.="" this="" is="" the="" reason="" that="" subgroups="" are="" widely="" used.="" 1="" 1="" .7="" the="" size="" of="" p="" choosing="" the="" right="" sizes="" for="" the="" parameters="" of="" a="" dh="" system="" is="" difficult.="" up="" to="" now,="" we="" have="" been="" using="" the="" requirement="" that="" an="" attacker="" must="" spend="" 2128="" steps="" to="" attack="" the="" system.="" that="" was="" an="" easy="" target="" for="" all="" the="" symmetric="" key="" primitives.="" public-key="" operations="" like="" the="" dh="" system="" are="" far="" more="" expensive="" to="" start="" with,="" and="" the="" computational="" cost="" grows="" much="" more="" quickly="" with="" the="" desired="" security="" level.="" if="" we="" keep="" to="" our="" requirement="" of="" forcing="" the="" attacker="" to="" use="" 2128="" steps="" to="" attack="" the="" system,="" the="" prime="" p="" should="" be="" about="" 6800="" bits="" long.="" in="" practical="" systems="" today,="" that="" would="" be="" a="" real="" problem="" from="" a="" performance="" point="" of="" view.="" there="" is="" a="" big="" difference="" between="" key="" sizes="" for="" symmetric="" primitives="" and="" key="" sizes="" for="" public-key="" primitives="" like="" dh.="" never,="" ever="" fall="" into="" the="" trap="" of="" comparing="" a="" symmetric="" key="" size="" (such="" as="" 128="" or="" 256="" bits)="" to="" the="" size="" of="" a="" public="" chapter="" 11="" •="" diffie-hellman="" 189="" key="" that="" can="" be="" thousands="" of="" bits.="" public-key="" sizes="" are="" always="" much="" larger="" than="" symmetric-key="" sizes.2="" public-key="" operations="" are="" far="" slower="" than="" the="" encryption="" and="" authentication="" functions="" we="" presented="" earlier.="" in="" most="" systems,="" the="" symmetric-key="" operations="" are="" insignificant,="" whereas="" the="" public-key="" operations="" can="" have="" a="" real="" effect="" on="" performance.="" we="" must="" therefore="" look="" much="" more="" closely="" at="" the="" performance="" aspects="" of="" public-key="" operations.="" symmetric-key="" sizes="" are="" typically="" fixed="" in="" a="" system.="" once="" you="" design="" your="" system="" to="" use="" a="" particular="" block="" cipher="" and="" hash="" function,="" you="" also="" fix="" the="" key="" size.="" that="" means="" that="" the="" symmetric="" key="" size="" is="" fixed="" for="" the="" life="" of="" the="" system.="" public-key="" sizes,="" on="" the="" other="" hand,="" are="" almost="" always="" variable.="" this="" makes="" it="" much="" easier="" to="" change="" the="" key="" size.="" our="" intent="" in="" this="" book="" is="" to="" design="" a="" system="" that="" will="" be="" used="" for="" 30="" years,="" and="" the="" data="" must="" be="" kept="" secure="" for="" 20="" years="" after="" it="" has="" first="" been="" processed.="" the="" symmetric="" key="" size="" must="" be="" chosen="" large="" enough="" to="" protect="" the="" data="" up="" to="" 50="" years="" from="" now.="" but="" the="" variable-sized="" public="" keys="" only="" have="" to="" protect="" the="" data="" for="" the="" next="" 20="" years.="" after="" all,="" all="" keys="" have="" a="" limited="" lifetime.="" a="" public="" key="" might="" be="" valid="" for="" one="" year,="" and="" should="" protect="" data="" for="" 20="" more="" years.="" this="" means="" that="" the="" public="" key="" only="" needs="" to="" protect="" data="" 21="" years,="" rather="" than="" the="" 50="" years="" needed="" for="" symmetric="" keys.="" each="" year,="" you="" generate="" a="" new="" public="" key,="" and="" you="" can="" choose="" larger="" public="" keys="" as="" computing="" technology="" progresses.="" the="" best="" estimates="" of="" how="" large="" your="" prime="" p="" needs="" to="" be="" can="" be="" found="" in="" [85].="" a="" prime="" of="" 2048="" bits="" can="" be="" expected="" to="" secure="" data="" until="" around="" 2022;="" 3072="" bits="" is="" secure="" until="" 2038;="" and="" 4096="" bits="" until="" 2050.="" the="" 6800="" bits="" we="" mentioned="" above="" is="" derived="" from="" the="" formulas="" in="" [85].="" that="" is="" the="" size="" of="" p="" if="" you="" want="" to="" force="" the="" attacker="" to="" perform="" 2128="" steps="" in="" an="" attack.="" be="" very="" careful="" with="" these="" types="" of="" predictions.="" there="" is="" some="" reasonable="" basis="" for="" these="" numbers,="" but="" predicting="" the="" future="" is="" always="" dangerous.="" we="" might="" be="" able="" to="" make="" some="" sensible="" predictions="" about="" key="" sizes="" for="" the="" next="" 10="" years,="" but="" making="" predictions="" about="" what="" things="" will="" be="" like="" 50="" years="" from="" now="" is="" really="" rather="" silly.="" just="" compare="" the="" current="" state="" of="" the="" art="" in="" computers="" and="" cryptography="" with="" the="" situation="" 50="" years="" ago.="" the="" predictions="" in="" [85]="" are="" by="" far="" the="" best="" estimates="" we="" have;="" nevertheless,="" treat="" them="" with="" caution.="" so="" what="" are="" we="" to="" do?="" as="" cryptographic="" designers,="" we="" have="" to="" choose="" a="" key="" size="" that="" will="" be="" secure="" for="" at="" least="" the="" next="" 20="" years.="" obviously="" 2048="" bits="" is="" a="" lower="" bound.="" larger="" is="" better,="" but="" larger="" keys="" have="" a="" significant="" extra="" cost.="" in="" the="" face="" of="" so="" much="" uncertainty,="" we="" would="" like="" to="" be="" conservative.="" so="" here="" is="" our="" advice:="" as="" of="" today,="" use="" 2048="" bits="" as="" an="" absolute="" minimum.="" (and="" don't="" forget="" that="" as="" time="" passes="" this="" minimum="" will="" grow.)="" if="" at="" all="" possible="" from="" a="" performance="" point="" of="" view,="" use="" 4096="" bits,="" or="" as="" close="" to="" 4096="" bits="" as="" you="" can="" 2this="" holds="" for="" the="" public-key="" schemes="" we="" discuss="" in="" this="" book.="" other="" public-key="" schemes,="" such="" as="" those="" based="" on="" elliptic="" curves,="" can="" have="" completely="" different="" key="" size="" parameters.="" 1="" 90="" part="" iii="" •="" key="" negotiation="" afford.="" furthermore,="" make="" absolutely="" sure="" that="" your="" system="" can="" handle="" sizes="" up="" to="" 8192="" bits.="" this="" will="" save="" the="" day="" if="" there="" are="" unexpected="" developments="" in="" attacking="" public-key="" systems.="" improvements="" in="" cryptanalysis="" will="" most="" likely="" lead="" to="" attacks="" on="" smaller="" key="" sizes.="" switching="" to="" a="" very="" much="" larger="" key="" size="" can="" be="" done="" while="" the="" system="" is="" in="" the="" field.="" it="" will="" cost="" some="" performance,="" but="" the="" basic="" operation="" of="" the="" system="" will="" be="" preserved.="" this="" is="" far="" better="" than="" losing="" all="" security="" and="" having="" to="" reengineer="" the="" system,="" which="" is="" what="" you="" would="" have="" to="" do="" if="" the="" system="" could="" not="" use="" larger="" keys.="" some="" applications="" require="" data="" to="" be="" kept="" secret="" for="" much="" longer="" than="" 20="" years.="" in="" these="" cases,="" you="" need="" to="" use="" the="" larger="" keys="" now.="" 1="" 1="" .8="" practical="" rules="" here="" are="" our="" practical="" rules="" for="" setting="" up="" a="" subgroup="" you="" can="" use="" for="" the="" dh="" protocol.="" choose="" q="" as="" a="" 256-bit="" prime.="" (there="" are="" collision-style="" attacks="" on="" the="" exponent="" in="" dh,="" so="" all="" our="" exponents="" should="" be="" 256="" bits="" long="" to="" force="" the="" attacker="" to="" use="" at="" least="" 2="" 1="" 28="" operations.)="" choose="" p="" as="" a="" large="" prime="" of="" the="" form="" nq="" +="" 1="" for="" some="" integer="" n.="" (see="" section="" 11.7="" for="" a="" discussion="" of="" how="" large="" p="" should="" be.="" computing="" the="" corresponding="" range="" for="" n="" is="" trivial.)="" choose="" a="" random="" g="" such="" that="" g="" -="f=." 1="" and="" gt="1." (the="" easy="" way="" to="" do="" this="" is="" to="" choose="" a="" random="" a,="" set="" g="aN," and="" check="" g="" for="" suitability.="" try="" another="" a="" if="" g="" fails="" the="" criteria.)="" any="" party="" receiving="" the="" subgroup="" description="" (p,="" q,g)="" should="" verify="" that:="" -="" both="" p="" and="" q="" are="" prime,="" q="" is="" 256="" bits="" long,="" and="" p="" is="" sufficiently="" large.="" (don't="" trust="" keys="" that="" are="" too="" small.)="" -="" q="" is="" a="" divisor="" of="" (p="" -="" 1).="" -="" g="" -="f=." 1="" and="" gt="1." this="" should="" be="" done="" even="" if="" the="" description="" is="" provided="" by="" a="" trusted="" source.="" you="" would="" be="" amazed="" at="" how="" often="" systems="" fail="" in="" some="" interesting="" way,="" especially="" when="" they="" are="" under="" attack.="" checking="" a="" set="" (p,="" q,g)="" takes="" a="" little="" time,="" but="" in="" most="" systems="" the="" same="" subgroup="" is="" used="" for="" a="" long="" time,="" so="" these="" checks="" need="" only="" be="" performed="" once.="" any="" time="" a="" party="" receives="" a="" number="" r="" that="" is="" supposed="" to="" be="" in="" the="" subgroup,="" it="" should="" be="" verified="" that="" 1="">< r="">< p="" and="" rq="1." note="" that="" r="1" is="" not="" allowed.="" using="" these="" rules,="" we="" get="" the="" version="" of="" the="" diffie-hellman="" protocol="" shown="" in="" figure="" 11.3.="" both="" parties="" start="" by="" checking="" the="" group="" parameters.="" each="" of="" them="" only="" has="" to="" do="" this="" once="" at="" start-up,="" not="" every="" time="" they="" run="" a="" dh="" protocol.="" (they="" should="" do="" it="" after="" every="" reboot="" or="" reinitialization,="" however,="" because="" the="" parameters="" could="" have="" changed.)="" alice="" known:="" (p,="" q,g)="" check="" (p,="" q,g)="" parameters="" x="" en="" {="" 1,="" ...="" ,="" q="" -="" 1="" }="" 1=""><:: y=""><:: p,="" yq="1" k="" +-="" (yy="" x="" :="g'" y="" :="gY" figure="" 11.]:="" diffie-hellman="" in="" a="" subgroup.="" chapter="" 11="" •="" diffie-hellman="" 191="" bob="" known:="" (p,="" q,g)="" check="" (p,="" q,g)="" parameters="" i=""><:: x=""><:: p="" ,="" xq="1" y="" en="" {="" 1,="" ...="" ,="" q="" -="" 1="" }="" k="" +-="" (x)y="" the="" rest="" of="" the="" protocol="" is="" very="" much="" the="" same="" as="" the="" original="" dh="" protocol="" in="" figure="" 11.1.="" alice="" and="" bob="" now="" use="" the="" subgroup,="" so="" the="" two="" exponents="" x="" and="" y="" are="" in="" the="" range="" 1,="" ...="" ,="" q="" -="" 1.="" both="" alice="" and="" bob="" check="" that="" the="" number="" they="" receive="" is="" in="" the="" proper="" subgroup="" to="" avoid="" any="" small-subgroup="" attacks="" by="" eve.="" the="" notation="" we="" use="" for="" the="" checks="" is="" a="" relational="" operator="" (such="" as="or"><) with a question mark above it. this means that alice (or bob) should check that the relation holds. if it does, then everything is all right. if the relation is not correct, then alice has to assume that she is under attack. the standard behavior is to stop the execution of the protocol, not send any other messages, and destroy all protocol-specific data. for example, in this protocol alice should destroy x and y if the last set of checks fails. see section 13.5.5 for a detailed discussion of how to handle these failures. this protocol describes a secure variant of dh, but it should not be used in exactly this form. the result k has to be hashed before it is used by the rest of the system. see section 14.6 for a more detailed discussion. 1 1 .9 what can go wrong? very few books or articles talk about the importance of checking that the numbers you receive are in the correct subgroup. niels first found this problem in the internet key exchange (ike) protocol of ipsec [60]. some of the ike protocols include a dh exchange. as ike has to operate in the real world, it has to deal with lost messages. so ike specifies that if bob receives no answer, he should resend his last message. ike does not specify how alice should process the message that bob sent again. and it is easy for alice to make a serious mistake. 1 91 part iii key negotiation for simplicity, let us suppose alice and bob use the dh protocol in the subgroup illustrated in figure 11.3 without checking that x and y are proper values. furthermore, after this exchange alice starts using the new key k to send an encrypted and authenticated message to bob that contains some further protocol data. (this is a very common situation, and similar situations can occur in ike.) here is the dangerous behavior by alice: when she receives a resend of the second message containing y, she simply recomputes the key k and sends the appropriate reply to bob. sounds entirely harmless, right? but the attacker eve can now start to play games. let d be a small divisor of (p - 1). eve can replace y by an element of order d. alice's key k is now limited to d possible values, and is completely determined by y and (x mod d). eve tries all possible values for (x mod d), computes the key k that alice would have gotten, and tries to decrypt the next message that alice sends. if eve guesses (x mod d) correctly, this message will decrypt properly, and eve has learned (x mod d). but what if p - 1 contains a number of small factors (d1, d2 , ••• , dk)? then eve can run this attack repeatedly for each of these factors and learn (x mod d 1 ), ••• , (x mod dk). using the general form of the chinese remainder theorem (see section 12.2) she can combine this knowledge to obtain (x mod d1d2 d3 ••• dk). so if the product of all small divisors of p - 1 is large, eve can get a significant amount of information about x. as x is supposed to be secret, this is always a bad development. in this particular case, eve can finish by forwarding the original y to alice and letting alice and bob complete the protocol. but eve has collected enough information about x that she can now find the key k that alice and bob use. to be quite clear: this is not an attack on ike. it is an attack on an implementation of ike that is allowed by the standard [60]. still, in our opinion the protocol should include enough information for a competent programmer to create a secure implementation. leaving this type of information out is dangerous, as somebody somewhere will implement it the wrong way. (we have not verified whether this attack applies to newer versions of ike.) for this attack to work, eve has to be lucky enough to have a p - 1 with sufficient small divisors. we are designing against an adversary that can perform 2128 steps of computing. this allows eve to take advantage of all divisors of p - 1 up to 2128 or so. we've never seen a good analysis of the probabilities of how much information eve could get, but a quick estimate indicates that on average eve will be able to get approximately 128 bits of information about x from the factors smaller than 2128. she can then attack the unknown part of x using a collision-style attack, and as x is only 256 bits long, this leads to a real attack. at least, it would if we didn't check that x and y were in the proper subgroup. chapter 11 diffie-hellman 1 93 the attack becomes even easier if eve was the person selecting the subgroup (p, q, g). she may have put the small divisors into p - 1 herself when she selected p in the first place. or maybe she sat on the committee that recommended certain parameters for a standard. this isn't as crazy as it seems. the u.s. government, in the form of nist, helpfully provides primes that can be used with dsa, a signature scheme that uses subgroups like this. other parts of that same u.s. government (e.g., nsa, cia, fbi) have a vested interest in being able tu break into private communications. we certainly don't want to imply that these primes are bad, but it is something that you would want to check before you use them. this is easy to do; in fact, nist published an algorithm for choosing parameters that does not insert additional small factors, and you can check whether the algorithm was indeed followed. but few people ever do. in the end, the simplest solution is to check that every value you receive is in the proper subgroup. all other ways of stopping small subgroup attacks are much more complicated. you could try to detect the small factors of p - 1 directly, but that is way too complicated. you could require the person who generated the parameter set to provide the factorization of p - i, but that adds a great deal of complexity to the whole system. verifying that the received values are in the right subgroup is a bit of work, but it is by far the simplest and most robust solution. 1 1 .1 0 exercises exercise 11.1 assume 200 people wish to communicate securely using symmetric keys, one symmetric key for each pair of people. how many symmetric keys would this system use in total? exercise 11.2 what are the subgroups generated by 3, 7, and 10 in the multiplicative group of integers modulo p = ii? exercise 11.3 why is a number r a square modulo p, p = 2q + 1 and p and q both prime, if and only if rq = 1 (mod p). exercise 11.4 what problems, if any, could arise if alice uses the same x and ?: for all her communications with bob, and bob uses the same y and gy for all his communications with alice? exercise 11.5 alice and bob wish to agree on a 256-bit aes key. they are trying to decide between using 256-bit, 512-bit, or some other length dh public keys ?: and gy. what would be your recommendation to them? with="" a="" question="" mark="" above="" it.="" this="" means="" that="" alice="" (or="" bob)="" should="" check="" that="" the="" relation="" holds.="" if="" it="" does,="" then="" everything="" is="" all="" right.="" if="" the="" relation="" is="" not="" correct,="" then="" alice="" has="" to="" assume="" that="" she="" is="" under="" attack.="" the="" standard="" behavior="" is="" to="" stop="" the="" execution="" of="" the="" protocol,="" not="" send="" any="" other="" messages,="" and="" destroy="" all="" protocol-specific="" data.="" for="" example,="" in="" this="" protocol="" alice="" should="" destroy="" x="" and="" y="" if="" the="" last="" set="" of="" checks="" fails.="" see="" section="" 13.5.5="" for="" a="" detailed="" discussion="" of="" how="" to="" handle="" these="" failures.="" this="" protocol="" describes="" a="" secure="" variant="" of="" dh,="" but="" it="" should="" not="" be="" used="" in="" exactly="" this="" form.="" the="" result="" k="" has="" to="" be="" hashed="" before="" it="" is="" used="" by="" the="" rest="" of="" the="" system.="" see="" section="" 14.6="" for="" a="" more="" detailed="" discussion.="" 1="" 1="" .9="" what="" can="" go="" wrong?="" very="" few="" books="" or="" articles="" talk="" about="" the="" importance="" of="" checking="" that="" the="" numbers="" you="" receive="" are="" in="" the="" correct="" subgroup.="" niels="" first="" found="" this="" problem="" in="" the="" internet="" key="" exchange="" (ike)="" protocol="" of="" ipsec="" [60].="" some="" of="" the="" ike="" protocols="" include="" a="" dh="" exchange.="" as="" ike="" has="" to="" operate="" in="" the="" real="" world,="" it="" has="" to="" deal="" with="" lost="" messages.="" so="" ike="" specifies="" that="" if="" bob="" receives="" no="" answer,="" he="" should="" resend="" his="" last="" message.="" ike="" does="" not="" specify="" how="" alice="" should="" process="" the="" message="" that="" bob="" sent="" again.="" and="" it="" is="" easy="" for="" alice="" to="" make="" a="" serious="" mistake.="" 1="" 91="" part="" iii="" key="" negotiation="" for="" simplicity,="" let="" us="" suppose="" alice="" and="" bob="" use="" the="" dh="" protocol="" in="" the="" subgroup="" illustrated="" in="" figure="" 11.3="" without="" checking="" that="" x="" and="" y="" are="" proper="" values.="" furthermore,="" after="" this="" exchange="" alice="" starts="" using="" the="" new="" key="" k="" to="" send="" an="" encrypted="" and="" authenticated="" message="" to="" bob="" that="" contains="" some="" further="" protocol="" data.="" (this="" is="" a="" very="" common="" situation,="" and="" similar="" situations="" can="" occur="" in="" ike.)="" here="" is="" the="" dangerous="" behavior="" by="" alice:="" when="" she="" receives="" a="" resend="" of="" the="" second="" message="" containing="" y,="" she="" simply="" recomputes="" the="" key="" k="" and="" sends="" the="" appropriate="" reply="" to="" bob.="" sounds="" entirely="" harmless,="" right?="" but="" the="" attacker="" eve="" can="" now="" start="" to="" play="" games.="" let="" d="" be="" a="" small="" divisor="" of="" (p="" -="" 1).="" eve="" can="" replace="" y="" by="" an="" element="" of="" order="" d.="" alice's="" key="" k="" is="" now="" limited="" to="" d="" possible="" values,="" and="" is="" completely="" determined="" by="" y="" and="" (x="" mod="" d).="" eve="" tries="" all="" possible="" values="" for="" (x="" mod="" d),="" computes="" the="" key="" k="" that="" alice="" would="" have="" gotten,="" and="" tries="" to="" decrypt="" the="" next="" message="" that="" alice="" sends.="" if="" eve="" guesses="" (x="" mod="" d)="" correctly,="" this="" message="" will="" decrypt="" properly,="" and="" eve="" has="" learned="" (x="" mod="" d).="" but="" what="" if="" p="" -="" 1="" contains="" a="" number="" of="" small="" factors="" (d1,="" d2="" ,="" •••="" ,="" dk)?="" then="" eve="" can="" run="" this="" attack="" repeatedly="" for="" each="" of="" these="" factors="" and="" learn="" (x="" mod="" d="" 1="" ),="" •••="" ,="" (x="" mod="" dk).="" using="" the="" general="" form="" of="" the="" chinese="" remainder="" theorem="" (see="" section="" 12.2)="" she="" can="" combine="" this="" knowledge="" to="" obtain="" (x="" mod="" d1d2="" d3="" •••="" dk).="" so="" if="" the="" product="" of="" all="" small="" divisors="" of="" p="" -="" 1="" is="" large,="" eve="" can="" get="" a="" significant="" amount="" of="" information="" about="" x.="" as="" x="" is="" supposed="" to="" be="" secret,="" this="" is="" always="" a="" bad="" development.="" in="" this="" particular="" case,="" eve="" can="" finish="" by="" forwarding="" the="" original="" y="" to="" alice="" and="" letting="" alice="" and="" bob="" complete="" the="" protocol.="" but="" eve="" has="" collected="" enough="" information="" about="" x="" that="" she="" can="" now="" find="" the="" key="" k="" that="" alice="" and="" bob="" use.="" to="" be="" quite="" clear:="" this="" is="" not="" an="" attack="" on="" ike.="" it="" is="" an="" attack="" on="" an="" implementation="" of="" ike="" that="" is="" allowed="" by="" the="" standard="" [60].="" still,="" in="" our="" opinion="" the="" protocol="" should="" include="" enough="" information="" for="" a="" competent="" programmer="" to="" create="" a="" secure="" implementation.="" leaving="" this="" type="" of="" information="" out="" is="" dangerous,="" as="" somebody="" somewhere="" will="" implement="" it="" the="" wrong="" way.="" (we="" have="" not="" verified="" whether="" this="" attack="" applies="" to="" newer="" versions="" of="" ike.)="" for="" this="" attack="" to="" work,="" eve="" has="" to="" be="" lucky="" enough="" to="" have="" a="" p="" -="" 1="" with="" sufficient="" small="" divisors.="" we="" are="" designing="" against="" an="" adversary="" that="" can="" perform="" 2128="" steps="" of="" computing.="" this="" allows="" eve="" to="" take="" advantage="" of="" all="" divisors="" of="" p="" -="" 1="" up="" to="" 2128="" or="" so.="" we've="" never="" seen="" a="" good="" analysis="" of="" the="" probabilities="" of="" how="" much="" information="" eve="" could="" get,="" but="" a="" quick="" estimate="" indicates="" that="" on="" average="" eve="" will="" be="" able="" to="" get="" approximately="" 128="" bits="" of="" information="" about="" x="" from="" the="" factors="" smaller="" than="" 2128.="" she="" can="" then="" attack="" the="" unknown="" part="" of="" x="" using="" a="" collision-style="" attack,="" and="" as="" x="" is="" only="" 256="" bits="" long,="" this="" leads="" to="" a="" real="" attack.="" at="" least,="" it="" would="" if="" we="" didn't="" check="" that="" x="" and="" y="" were="" in="" the="" proper="" subgroup.="" chapter="" 11="" diffie-hellman="" 1="" 93="" the="" attack="" becomes="" even="" easier="" if="" eve="" was="" the="" person="" selecting="" the="" subgroup="" (p,="" q,="" g).="" she="" may="" have="" put="" the="" small="" divisors="" into="" p="" -="" 1="" herself="" when="" she="" selected="" p="" in="" the="" first="" place.="" or="" maybe="" she="" sat="" on="" the="" committee="" that="" recommended="" certain="" parameters="" for="" a="" standard.="" this="" isn't="" as="" crazy="" as="" it="" seems.="" the="" u.s.="" government,="" in="" the="" form="" of="" nist,="" helpfully="" provides="" primes="" that="" can="" be="" used="" with="" dsa,="" a="" signature="" scheme="" that="" uses="" subgroups="" like="" this.="" other="" parts="" of="" that="" same="" u.s.="" government="" (e.g.,="" nsa,="" cia,="" fbi)="" have="" a="" vested="" interest="" in="" being="" able="" tu="" break="" into="" private="" communications.="" we="" certainly="" don't="" want="" to="" imply="" that="" these="" primes="" are="" bad,="" but="" it="" is="" something="" that="" you="" would="" want="" to="" check="" before="" you="" use="" them.="" this="" is="" easy="" to="" do;="" in="" fact,="" nist="" published="" an="" algorithm="" for="" choosing="" parameters="" that="" does="" not="" insert="" additional="" small="" factors,="" and="" you="" can="" check="" whether="" the="" algorithm="" was="" indeed="" followed.="" but="" few="" people="" ever="" do.="" in="" the="" end,="" the="" simplest="" solution="" is="" to="" check="" that="" every="" value="" you="" receive="" is="" in="" the="" proper="" subgroup.="" all="" other="" ways="" of="" stopping="" small="" subgroup="" attacks="" are="" much="" more="" complicated.="" you="" could="" try="" to="" detect="" the="" small="" factors="" of="" p="" -="" 1="" directly,="" but="" that="" is="" way="" too="" complicated.="" you="" could="" require="" the="" person="" who="" generated="" the="" parameter="" set="" to="" provide="" the="" factorization="" of="" p="" -="" i,="" but="" that="" adds="" a="" great="" deal="" of="" complexity="" to="" the="" whole="" system.="" verifying="" that="" the="" received="" values="" are="" in="" the="" right="" subgroup="" is="" a="" bit="" of="" work,="" but="" it="" is="" by="" far="" the="" simplest="" and="" most="" robust="" solution.="" 1="" 1="" .1="" 0="" exercises="" exercise="" 11.1="" assume="" 200="" people="" wish="" to="" communicate="" securely="" using="" symmetric="" keys,="" one="" symmetric="" key="" for="" each="" pair="" of="" people.="" how="" many="" symmetric="" keys="" would="" this="" system="" use="" in="" total?="" exercise="" 11.2="" what="" are="" the="" subgroups="" generated="" by="" 3,="" 7,="" and="" 10="" in="" the="" multiplicative="" group="" of="" integers="" modulo="" p="II?" exercise="" 11.3="" why="" is="" a="" number="" r="" a="" square="" modulo="" p,="" p="2q" +="" 1="" and="" p="" and="" q="" both="" prime,="" if="" and="" only="" if="" rq="1" (mod="" p).="" exercise="" 11.4="" what="" problems,="" if="" any,="" could="" arise="" if="" alice="" uses="" the="" same="" x="" and="" :="" for="" all="" her="" communications="" with="" bob,="" and="" bob="" uses="" the="" same="" y="" and="" gy="" for="" all="" his="" communications="" with="" alice?="" exercise="" 11.5="" alice="" and="" bob="" wish="" to="" agree="" on="" a="" 256-bit="" aes="" key.="" they="" are="" trying="" to="" decide="" between="" using="" 256-bit,="" 512-bit,="" or="" some="" other="" length="" dh="" public="" keys="" :="" and="" gy.="" what="" would="" be="" your="" recommendation="" to="">