11/13/07</TITLE= > <META http-equiv=3DContent-Type content=3D"text/html; = charset=3Dwindows-1252"> <META content=3DWord.Document name=3DProgId> <META content=3D"MSHTML 6.00.6000.16609" name=3DGENERATOR> <META content=3D"Microsoft Word 10" name=3DOriginator><LINK=20 href=3D"Solutions-IV_files/filelist.xml" rel=3DFile-List><LINK=20 href=3D"Solutions-IV_files/editdata.mso" rel=3DEdit-Time-Data><o:SmartTagType name=3D"date"=20 namespaceuri=3D"urn:schemas-microsoft-com:office:smarttags"></o:SmartTagT= ype><o:SmartTagType=20 name=3D"place"=20 namespaceuri=3D"urn:schemas-microsoft-com:office:smarttags"></o:SmartTagT= ype><o:SmartTagType=20 name=3D"City"=20 namespaceuri=3D"urn:schemas-microsoft-com:office:smarttags"></o:SmartTagT= ype> <STYLE>@font-face { font-family: Wingdings; } @font-face { font-family: Batang; } @font-face { font-family: Nimbus Roman No9 L; } @font-face { font-family: Nimbus Sans L; } @font-face { font-family: @Batang; } @page Section1 {size: 8.5in 11.0in; margin: 1.0in 1.25in 1.0in 1.25in; = mso-header-margin: 35.4pt; mso-footer-margin: 35.4pt; mso-paper-source: = 0; } P.MsoNormal { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; FONT-FAMILY: "Nimbus Roman No9 = L"; mso-style-parent: ""; mso-pagination: none; mso-hyphenate: none; = mso-fareast-font-family: "Nimbus Sans L"; mso-bidi-font-family: "Times = New Roman" } LI.MsoNormal { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; FONT-FAMILY: "Nimbus Roman No9 = L"; mso-style-parent: ""; mso-pagination: none; mso-hyphenate: none; = mso-fareast-font-family: "Nimbus Sans L"; mso-bidi-font-family: "Times = New Roman" } DIV.MsoNormal { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; FONT-FAMILY: "Nimbus Roman No9 = L"; mso-style-parent: ""; mso-pagination: none; mso-hyphenate: none; = mso-fareast-font-family: "Nimbus Sans L"; mso-bidi-font-family: "Times = New Roman" } H1 { FONT-SIZE: 14pt; MARGIN: 12pt 0in 3pt 0.5in; TEXT-INDENT: -0.25in; = FONT-FAMILY: Arial; mso-list: l4 level1 lfo4; tab-stops: list .5in; = mso-pagination: widow-orphan; mso-bidi-font-family: "Times New Roman"; = mso-style-next: Normal; mso-outline-level: 1; mso-bidi-font-size: = 10.0pt; mso-font-kerning: .5pt; mso-bidi-font-weight: normal } H3 { FONT-SIZE: 13pt; MARGIN: 12pt 0in 3pt; FONT-FAMILY: Arial; = mso-pagination: none; mso-hyphenate: none; mso-fareast-font-family: = "Nimbus Sans L"; mso-style-next: Normal; mso-outline-level: 3 } P.MsoBodyTextIndent { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt 0.25in; WORD-BREAK: break-all; = FONT-FAMILY: "Times New Roman"; TEXT-ALIGN: justify; mso-pagination: = none; mso-fareast-font-family: Batang; mso-bidi-font-size: 10.0pt; = mso-font-kerning: 1.0pt; mso-fareast-language: KO } LI.MsoBodyTextIndent { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt 0.25in; WORD-BREAK: break-all; = FONT-FAMILY: "Times New Roman"; TEXT-ALIGN: justify; mso-pagination: = none; mso-fareast-font-family: Batang; mso-bidi-font-size: 10.0pt; = mso-font-kerning: 1.0pt; mso-fareast-language: KO } DIV.MsoBodyTextIndent { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt 0.25in; WORD-BREAK: break-all; = FONT-FAMILY: "Times New Roman"; TEXT-ALIGN: justify; mso-pagination: = none; mso-fareast-font-family: Batang; mso-bidi-font-size: 10.0pt; = mso-font-kerning: 1.0pt; mso-fareast-language: KO } A:link { COLOR: navy; TEXT-DECORATION: underline; mso-style-parent: ""; = text-underline: single } SPAN.MsoHyperlink { COLOR: navy; TEXT-DECORATION: underline; mso-style-parent: ""; = text-underline: single } A:visited { COLOR: purple; TEXT-DECORATION: underline; text-underline: single } SPAN.MsoHyperlinkFollowed { COLOR: purple; TEXT-DECORATION: underline; text-underline: single } SPAN.SpellE { mso-style-name: ""; mso-spl-e: yes } SPAN.GramE { mso-style-name: ""; mso-gram-e: yes } DIV.Section1 { page: Section1 } OL { MARGIN-BOTTOM: 0in } UL { MARGIN-BOTTOM: 0in } </STYLE> </HEAD> <BODY lang=3DEN-US style=3D"tab-interval: .5in" vLink=3Dpurple = link=3Dnavy> <DIV class=3DSection1> <H1=20 style=3D"MARGIN-LEFT: 0in; TEXT-INDENT: 0in; TEXT-ALIGN: right; = mso-list: none; tab-stops: .5in"=20 align=3Dright><st1:date Month=3D"11" Day=3D"13" Year=3D"2007"><SPAN=20 style=3D"FONT-WEIGHT: normal; FONT-SIZE: 12pt; FONT-FAMILY: 'Times New = Roman'; mso-bidi-font-size: 10.0pt; mso-bidi-font-weight: = bold">11/13/07</st1:date><SPAN=20 style=3D"FONT-WEIGHT: normal; FONT-SIZE: 12pt; FONT-FAMILY: 'Times New = Roman'; mso-bidi-font-size: 10.0pt; mso-bidi-font-weight: = bold"><o:p></o:p></H1> <H1=20 style=3D"MARGIN-LEFT: 0in; TEXT-INDENT: 0in; TEXT-ALIGN: center; = mso-list: l1 level1 lfo2; tab-stops: list 0in"=20 align=3Dcenter>CS = G254/U645 Network=20 Security<o:p></o:p></H1> <H1=20 style=3D"MARGIN-LEFT: 0in; TEXT-INDENT: 0in; TEXT-ALIGN: center; = mso-list: l1 level1 lfo2; tab-stops: list 0in"=20 align=3Dcenter><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-bidi-font-size: = 14.0pt">Problem Set =96=20 IV Solutions<o:p></o:p></H1> <o:p> </o:p> 1) = <B=20 style=3D"mso-bidi-font-weight: normal">DES <SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'"><o:p> </o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">a)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>64=20 bits<o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">b)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">Suppose that there exists an = encryption=20 algorithm that produces cipher blocks smaller than the plain-text = blocks. Then=20 the number of different plain-text words is greater than the number of = possible=20 cipher-text blocks. Thus multiple plain-text blocks will encrypt to the = same=20 cipher-block. However, it would not be possible to perform decryption = for such=20 cipher-text blocks, because there would be no way of determining which=20 particular plain-text block they have to decrypt to. Thus the size of = the=20 cipher-block has to be at least as big as the size of plain-text block = to=20 prevent the loss of information.<o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">c)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>DES=20 key is a 64-bit quantity. However, one bit in each octet is used for odd = parity=20 on each octet. Thus only 7*8=3D56 bits comprise the actual meaningful = key. Thus=20 there are 256 different DES keys<o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">d)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>DES=20 consists of 16 rounds of permutation. There is also an additional = initial and=20 final permutation.<o:p></o:p> <![if !supportLists]><I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">e)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">Getting right half is easy: = <SPAN=20 class=3DGramE>Ri<I=20 style=3D"mso-bidi-font-style: normal"> =3D Ri+1. To get = the left=20 half: Li =3D <SPAN=20 class=3DGramE>Ri+1 <I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5=20 (Ki mangle Ri). We can compute mangle, since = we know=20 both Ki and = <SPAN=20 class=3DGramE>Ri.=20 Since we also have <I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Ri+<I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">1 <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">and since we know that <I=20 style=3D"mso-bidi-font-style: normal">A <I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5 B=20 <SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5 B=20 =3D A, we can perform the above <SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5=20 operation to recover <SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Li<SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">. <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">Notice that while recovering Li we did not need = the mangle=20 to be reversible.<I=20 style=3D"mso-bidi-font-style: normal"><o:p></o:p> <![if !supportLists]><I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">f)<SPAN=20 style=3D"FONT: 7pt 'Times New = Roman'"> =20 <![endif]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">3DES (also known as=20 <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">EDE</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">) works by first encrypting = plain text=20 with K1, then decrypting it with <st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">K2</st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">, <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">then encrypting it with = K1.=20 Thus there are 256*256 possible keys to try, or=20 2112 total tries to be made in the worst case before finding = the=20 correct keys. (Note that if three distinct keys were used, there is an = attack,=20 known as meet in the=20 middle attack that makes 3DES no more secure than performing = encryption once. This is the reason for reusing first key, instead of = three=20 unique keys.)<SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p></o:p> <o:p> </o:p> 2) <B=20 style=3D"mso-bidi-font-weight: normal">Passwords <o:p> </o:p> a)=20 In the Lamport one-time = password=20 scheme <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"> picks a password, =93pwd,=94 = and a=20 reasonably large number n (like 1000), and repeatedly applies a hash = function,=20 h, to it. She then sends <SPAN=20 class=3DGramE>hn(pwd) to Bob=20 along with n. Bob stores it in a database.<o:p></o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">When she wishes to prove her = identity to=20 Bob she contacts him, at which point Bob sends her back n, Alice then = computes=20 hn-1(pwd) and sends the result to Bob. Bob takes the received = quantity, hashes it once, and checks against the database. If it matches = Bob=20 considers the response valid and replaces the stored quantity with the = received=20 quantity and replaces n by n-1. <o:p></o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> <![if !vml]><img width=3D234 = height=3D126 src=3D"Solutions-IV_files/image001.gif" align=3Dleft = v:shapes=3D"_x0000_s1026 _x0000_s1027 _x0000_s1028 _x0000_s1029 = _x0000_s1030 _x0000_s1031 _x0000_s1032 _x0000_s1033 = _x0000_s1034"><![endif]> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">h(<SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">h999(pwd)) ?=3D=20 h1000(pwd)<o:p></o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><SPAN=20 style=3D"mso-spacerun: yes"> Replaces <SPAN=20 class=3DGramE>h1000(pwd) with=20 h999(pwd)<o:p></o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> <![if !vml]> <table cellpadding=3D0 cellspacing=3D0> <tr> <td width=3D88 height=3D28 bgcolor=3Dwhite = style=3D'vertical-align:top;background: white'><![endif]><![if !mso]><SPAN=20 style=3D"Z-INDEX: 2; POSITION: absolute; mso-ignore: vglayout"> <TABLE cellSpacing=3D0 cellPadding=3D0 width=3D"100%"> <TBODY> <TR> <TD><![endif]> <DIV class=3Dshape=20 style=3D"PADDING-RIGHT: 7.2pt; PADDING-LEFT: 7.2pt; = PADDING-BOTTOM: 3.6pt; PADDING-TOP: 3.6pt"=20 v:shape =3D "_x0000_s1035"> S/KEY</DIV><![if = !mso]></TD></TR></TBODY></TABLE><![endif]><![if !mso & = !vml]> <![endif]><![if !vml]></td> </tr> </table> <![endif]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">b)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>The=20 Lamport scheme is secure against eavesdropping since the password is = never sent=20 in the clear, only the hash (or hash chain) of the password is = communicated.=20 <o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">c)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>Even=20 though the password is not held in Bob=92s database, the hash chain of = the=20 password, hn<SPAN=20 class=3DGramE>(pwd) is, and so an attacker can do an offline = dictionary=20 attack by repeatedly making a guess and comparing <SPAN=20 class=3DSpellE>hn(guess) against the stored value.=20 <o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">d)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>In=20 the small n attack an intruder impersonates Bob and when=20 <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"> attempts to authenticate, = sends back a=20 small value for n, like 50. When <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"> responds with <SPAN=20 class=3DGramE>h50(pwd) then the intruder can utilize = this to=20 impersonate <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">, assuming the actual n at Bob = is greater=20 than 50.<o:p></o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> 3) = <B=20 style=3D"mso-bidi-font-weight: normal">Sessions = Keys<o:p></o:p> <o:p> </o:p> a) <o:p> </o:p> <I=20 style=3D"mso-bidi-font-style: normal">KAB(<I=20 style=3D"mso-bidi-font-style: normal">KAB) is not a good = choice,=20 because this choice of session key would result in the same session key = for all=20 sessions. And it is advisable to have unique session keys for different=20 sessions. <o:p> </o:p> <I=20 style=3D"mso-bidi-font-style: normal">R(<I=20 style=3D"mso-bidi-font-style: normal">KAB)<SPAN=20 style=3D"mso-spacerun: yes"> is a bad choice, since R = was sent on=20 the clear. Thus the eavesdropper who obtains <I=20 style=3D"mso-bidi-font-style: normal">R(<I=20 style=3D"mso-bidi-font-style: normal">KAB)<SPAN=20 style=3D"mso-spacerun: yes"> can decrypt it with R and = obtain the=20 shared secret. <o:p> </o:p> <I=20 style=3D"mso-bidi-font-style: normal">R<I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5KAB=20 is not secure, because once the session key is discovered the = intruder=20 will also know the shared secret (because R was sent on the clear and KAB =3D R<I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5KAB<I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5R.) <o:p> </o:p> <SPAN=20 style=3D"mso-spacerun: yes"> = b) The=20 main reasons for using session keys are: <o:p> </o:p> If somebody is = performing attack,=20 the more information he gets encrypted with the same key, the more = likely he is=20 to succeed. Thus it is wise to use the secret shared key (or = authentication key)=20 only when establishing connection to generate a per-session key for = every new=20 session <o:p> </o:p> If the shared secret = is=20 compromised, but separate session keys were used for encrypting past = sessions it=20 would not be possible for the intruder who discovers the shared secret = to=20 decrypt recorded past sessions. <o:p> </o:p> When dealing with = untrusted=20 software, it is better to hand it a session key that is only valid for = one=20 session, than revealing the long-term secret key to the application. <o:p> </o:p> <![if !vml]> <table cellpadding=3D0 cellspacing=3D0> <tr> <td width=3D64 height=3D40 bgcolor=3Dwhite = style=3D'vertical-align:top;background: white'><![endif]><![if !mso]><SPAN=20 style=3D"Z-INDEX: 3; POSITION: absolute; mso-ignore: vglayout"> <TABLE cellSpacing=3D0 cellPadding=3D0 width=3D"100%"> <TBODY> <TR> <TD><![endif]> <DIV class=3Dshape=20 style=3D"PADDING-RIGHT: 7.2pt; PADDING-LEFT: 7.2pt; = PADDING-BOTTOM: 3.6pt; PADDING-TOP: 3.6pt"=20 v:shape =3D "_x0000_s1037"> <I=20 style=3D"mso-bidi-font-style: normal">string<I=20 style=3D"mso-bidi-font-style: = normal"><o:p></o:p></DIV><![if = !mso]></TD></TR></TBODY></TABLE><![endif]><![if !mso & = !vml]> <![endif]><![if !vml]></td> </tr> </table> <![endif]> =20 c) <![if !vml]> <table cellpadding=3D0 cellspacing=3D0 align=3Dleft> <tr> <td width=3D59 height=3D1></td> </tr> <tr> <td></td> <td><img width=3D246 height=3D114 = src=3D"Solutions-IV_files/image002.gif" v:shapes=3D"_x0000_s1039 = _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043"></td> </tr> </table> <![endif]><o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> If during this = exchange Trudy was=20 listening on the channel, Trudy would now be able to obtain the key, = since <I=20 style=3D"mso-bidi-font-style: normal">key =3D key <I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5<SPAN=20 style=3D"mso-spacerun: yes"> string <I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5<SPAN=20 style=3D"mso-spacerun: yes"> string. <o:p> </o:p> <![if !supportLists]><SPAN=20 style=3D"mso-fareast-font-family: 'Nimbus Roman No9 L'; = mso-bidi-font-family: 'Nimbus Roman No9 L'"><SPAN=20 style=3D"mso-list: Ignore">d)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>In this case <I=20 style=3D"mso-bidi-font-style: normal">known plain text or <I=20 style=3D"mso-bidi-font-style: normal">offline attack can be = performed. Some=20 encryption schemes are quite robust to this = type of=20 attack, but in many cases a few <I=20 style=3D"mso-bidi-font-style: normal"><plaintext, cipher text> = suffice=20 to calculate the secret key. Thus it is advisable to keep <I=20 style=3D"mso-bidi-font-style: normal"><plaintext, cipher text> = pairs=20 secret. <o:p> </o:p> 4)=20 Otway-Rees (slightly modified) <SPAN=20 style=3D"mso-spacerun: yes"> Alice = <SPAN=20 style=3D"FONT-FAMILY: Wingdings; mso-ascii-font-family: 'Nimbus Roman = No9 L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: = symbol; mso-symbol-font-family: Wingdings; mso-no-proof: yes"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Wingdings">=E0=20 Bob: Alice, Bob, <I=20 style=3D"mso-bidi-font-style: normal">KA(<SPAN=20 class=3DSpellE><I=20 style=3D"mso-bidi-font-style: = normal">NA,Alice,Bob<I=20 style=3D"mso-bidi-font-style: normal">) <SPAN=20 style=3D"mso-spacerun: yes"> Bob = <SPAN=20 style=3D"FONT-FAMILY: Wingdings; mso-ascii-font-family: 'Nimbus Roman = No9 L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: = symbol; mso-symbol-font-family: Wingdings; mso-no-proof: yes"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Wingdings">=E0=20 KDC: <I=20 style=3D"mso-bidi-font-style: normal">KB(<I=20 style=3D"mso-bidi-font-style: normal">NB, Alice, Bob<I=20 style=3D"mso-bidi-font-style: normal">), <I=20 style=3D"mso-bidi-font-style: normal">KA(<SPAN=20 class=3DSpellE>NA,<SPAN=20 style=3D"FONT-STYLE: normal">Alice,Bob) <SPAN=20 style=3D"mso-spacerun: yes"> KDC = <SPAN=20 style=3D"FONT-FAMILY: Wingdings; mso-ascii-font-family: 'Nimbus Roman = No9 L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: = symbol; mso-symbol-font-family: Wingdings; mso-no-proof: yes"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Wingdings">=E0=20 Bob: <I=20 style=3D"mso-bidi-font-style: normal">KA(<I=20 style=3D"mso-bidi-font-style: normal">NA,KAB),=20 KB(NB,KAB) <SPAN=20 style=3D"mso-spacerun: yes"> Bob = <SPAN=20 style=3D"FONT-FAMILY: Wingdings; mso-ascii-font-family: 'Nimbus Roman = No9 L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: = symbol; mso-symbol-font-family: Wingdings; mso-no-proof: yes"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Wingdings">=E0=20 Alice: <I=20 style=3D"mso-bidi-font-style: normal">KA(<I=20 style=3D"mso-bidi-font-style: = normal">NA,KAB) <SPAN=20 style=3D"mso-spacerun: yes"> Alice = <SPAN=20 style=3D"FONT-FAMILY: Wingdings; mso-ascii-font-family: 'Nimbus Roman = No9 L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: = symbol; mso-symbol-font-family: Wingdings; mso-no-proof: yes"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Wingdings">=E0=20 Bob: <I=20 style=3D"mso-bidi-font-style: normal">KAB(Anything = recognizable) <o:p> </o:p> <o:p> </o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">a)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>The=20 KDC checks that the first part of the message is encrypted with = KB,=20 Bob=92s key, and that the names in the message, = =93<st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">=94, =93Bob=94 match with those = in the second=20 part which is encrypted with <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">=92s key, KA. This = ensures that=20 only bob could have generated this message. (Note that the possibility = of a=20 replay attack is prevented down the line when = <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"> checks the nonce NA = in Bob=92s=20 reply). <o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">b)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]><st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"> checks that the message is = encrypted=20 with the key KA, this ensures that = it was=20 generated by the KDC, she then checks that the message contains = NA,=20 this proves the freshness of the message and thus she knows Bob has = actually=20 talked to the KDC and not just used an old message from the KDC.=20 <o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"mso-fareast-font-family: 'Times New Roman'"><SPAN=20 style=3D"mso-list: Ignore">c)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>There is no need for a separate round for = authenticating Bob to <st1:City><st1:place>Alice</st1:place></st1:City> = because=20 <st1:City><st1:place>Alice</st1:place></st1:City> ensures that she is = talking to=20 Bob from his reply. Bob=92s reply must be encrypted with=20 <st1:City><st1:place>Alice</st1:place></st1:City>=92s key, = KA, and=20 containing her nonce, NA, so she knows he must have been=20 authenticated by the KDC. (Note that a man in the middle attack by Trudy = is=20 possible but so long as Alice and Bob use the session key KAB = to=20 encrypt the rest of their conversation Trudy cannot impersonate Bob). = <![if !supportLists]><SPAN=20 style=3D"mso-fareast-font-family: 'Nimbus Roman No9 L'; = mso-bidi-font-family: 'Nimbus Roman No9 L'"><SPAN=20 style=3D"mso-list: Ignore">d)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>If=20 =93Anything recognizable=94 were a fixed message then it would be = possible to infer=20 KAB by an offline attack that encrypted =93Anything = recognizable=94 with=20 all possible keys and compared against the cipher text. If a random salt = were=20 concatenated to =93Anything recognizable=94 then such an offline attack = would be=20 defeated since there are too many different possibilities to=20 check.</DIV></BODY></HTML>

From: "Saved by Windows Internet Explorer 7" Subject: 11/13/07 Date: Sat, 16 Feb 2008 02:16:38 -0500 MIME-Version: 1.0 Content-Type: text/html; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable Content-Location: http://www.ccs.neu.edu/course/csg254/Solutions-IV.htm X-MimeOLE: Produced By Microsoft MimeOLE V6.0.6000.16545 11/13/07</TITLE= > <META http-equiv=3DContent-Type content=3D"text/html; = charset=3Dwindows-1252"> <META content=3DWord.Document name=3DProgId> <META content=3D"MSHTML 6.00.6000.16609" name=3DGENERATOR> <META content=3D"Microsoft Word 10" name=3DOriginator><LINK=20 href=3D"Solutions-IV_files/filelist.xml" rel=3DFile-List><LINK=20 href=3D"Solutions-IV_files/editdata.mso" rel=3DEdit-Time-Data><o:SmartTagType name=3D"date"=20 namespaceuri=3D"urn:schemas-microsoft-com:office:smarttags"></o:SmartTagT= ype><o:SmartTagType=20 name=3D"place"=20 namespaceuri=3D"urn:schemas-microsoft-com:office:smarttags"></o:SmartTagT= ype><o:SmartTagType=20 name=3D"City"=20 namespaceuri=3D"urn:schemas-microsoft-com:office:smarttags"></o:SmartTagT= ype> <STYLE>@font-face { font-family: Wingdings; } @font-face { font-family: Batang; } @font-face { font-family: Nimbus Roman No9 L; } @font-face { font-family: Nimbus Sans L; } @font-face { font-family: @Batang; } @page Section1 {size: 8.5in 11.0in; margin: 1.0in 1.25in 1.0in 1.25in; = mso-header-margin: 35.4pt; mso-footer-margin: 35.4pt; mso-paper-source: = 0; } P.MsoNormal { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; FONT-FAMILY: "Nimbus Roman No9 = L"; mso-style-parent: ""; mso-pagination: none; mso-hyphenate: none; = mso-fareast-font-family: "Nimbus Sans L"; mso-bidi-font-family: "Times = New Roman" } LI.MsoNormal { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; FONT-FAMILY: "Nimbus Roman No9 = L"; mso-style-parent: ""; mso-pagination: none; mso-hyphenate: none; = mso-fareast-font-family: "Nimbus Sans L"; mso-bidi-font-family: "Times = New Roman" } DIV.MsoNormal { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; FONT-FAMILY: "Nimbus Roman No9 = L"; mso-style-parent: ""; mso-pagination: none; mso-hyphenate: none; = mso-fareast-font-family: "Nimbus Sans L"; mso-bidi-font-family: "Times = New Roman" } H1 { FONT-SIZE: 14pt; MARGIN: 12pt 0in 3pt 0.5in; TEXT-INDENT: -0.25in; = FONT-FAMILY: Arial; mso-list: l4 level1 lfo4; tab-stops: list .5in; = mso-pagination: widow-orphan; mso-bidi-font-family: "Times New Roman"; = mso-style-next: Normal; mso-outline-level: 1; mso-bidi-font-size: = 10.0pt; mso-font-kerning: .5pt; mso-bidi-font-weight: normal } H3 { FONT-SIZE: 13pt; MARGIN: 12pt 0in 3pt; FONT-FAMILY: Arial; = mso-pagination: none; mso-hyphenate: none; mso-fareast-font-family: = "Nimbus Sans L"; mso-style-next: Normal; mso-outline-level: 3 } P.MsoBodyTextIndent { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt 0.25in; WORD-BREAK: break-all; = FONT-FAMILY: "Times New Roman"; TEXT-ALIGN: justify; mso-pagination: = none; mso-fareast-font-family: Batang; mso-bidi-font-size: 10.0pt; = mso-font-kerning: 1.0pt; mso-fareast-language: KO } LI.MsoBodyTextIndent { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt 0.25in; WORD-BREAK: break-all; = FONT-FAMILY: "Times New Roman"; TEXT-ALIGN: justify; mso-pagination: = none; mso-fareast-font-family: Batang; mso-bidi-font-size: 10.0pt; = mso-font-kerning: 1.0pt; mso-fareast-language: KO } DIV.MsoBodyTextIndent { FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt 0.25in; WORD-BREAK: break-all; = FONT-FAMILY: "Times New Roman"; TEXT-ALIGN: justify; mso-pagination: = none; mso-fareast-font-family: Batang; mso-bidi-font-size: 10.0pt; = mso-font-kerning: 1.0pt; mso-fareast-language: KO } A:link { COLOR: navy; TEXT-DECORATION: underline; mso-style-parent: ""; = text-underline: single } SPAN.MsoHyperlink { COLOR: navy; TEXT-DECORATION: underline; mso-style-parent: ""; = text-underline: single } A:visited { COLOR: purple; TEXT-DECORATION: underline; text-underline: single } SPAN.MsoHyperlinkFollowed { COLOR: purple; TEXT-DECORATION: underline; text-underline: single } SPAN.SpellE { mso-style-name: ""; mso-spl-e: yes } SPAN.GramE { mso-style-name: ""; mso-gram-e: yes } DIV.Section1 { page: Section1 } OL { MARGIN-BOTTOM: 0in } UL { MARGIN-BOTTOM: 0in } </STYLE> </HEAD> <BODY lang=3DEN-US style=3D"tab-interval: .5in" vLink=3Dpurple = link=3Dnavy> <DIV class=3DSection1> <H1=20 style=3D"MARGIN-LEFT: 0in; TEXT-INDENT: 0in; TEXT-ALIGN: right; = mso-list: none; tab-stops: .5in"=20 align=3Dright><st1:date Month=3D"11" Day=3D"13" Year=3D"2007"><SPAN=20 style=3D"FONT-WEIGHT: normal; FONT-SIZE: 12pt; FONT-FAMILY: 'Times New = Roman'; mso-bidi-font-size: 10.0pt; mso-bidi-font-weight: = bold">11/13/07</st1:date><SPAN=20 style=3D"FONT-WEIGHT: normal; FONT-SIZE: 12pt; FONT-FAMILY: 'Times New = Roman'; mso-bidi-font-size: 10.0pt; mso-bidi-font-weight: = bold"><o:p></o:p></H1> <H1=20 style=3D"MARGIN-LEFT: 0in; TEXT-INDENT: 0in; TEXT-ALIGN: center; = mso-list: l1 level1 lfo2; tab-stops: list 0in"=20 align=3Dcenter>CS = G254/U645 Network=20 Security<o:p></o:p></H1> <H1=20 style=3D"MARGIN-LEFT: 0in; TEXT-INDENT: 0in; TEXT-ALIGN: center; = mso-list: l1 level1 lfo2; tab-stops: list 0in"=20 align=3Dcenter><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-bidi-font-size: = 14.0pt">Problem Set =96=20 IV Solutions<o:p></o:p></H1> <o:p> </o:p> 1) = <B=20 style=3D"mso-bidi-font-weight: normal">DES <SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'"><o:p> </o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">a)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>64=20 bits<o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">b)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">Suppose that there exists an = encryption=20 algorithm that produces cipher blocks smaller than the plain-text = blocks. Then=20 the number of different plain-text words is greater than the number of = possible=20 cipher-text blocks. Thus multiple plain-text blocks will encrypt to the = same=20 cipher-block. However, it would not be possible to perform decryption = for such=20 cipher-text blocks, because there would be no way of determining which=20 particular plain-text block they have to decrypt to. Thus the size of = the=20 cipher-block has to be at least as big as the size of plain-text block = to=20 prevent the loss of information.<o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">c)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>DES=20 key is a 64-bit quantity. However, one bit in each octet is used for odd = parity=20 on each octet. Thus only 7*8=3D56 bits comprise the actual meaningful = key. Thus=20 there are 256 different DES keys<o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">d)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>DES=20 consists of 16 rounds of permutation. There is also an additional = initial and=20 final permutation.<o:p></o:p> <![if !supportLists]><I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">e)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">Getting right half is easy: = <SPAN=20 class=3DGramE>Ri<I=20 style=3D"mso-bidi-font-style: normal"> =3D Ri+1. To get = the left=20 half: Li =3D <SPAN=20 class=3DGramE>Ri+1 <I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5=20 (Ki mangle Ri). We can compute mangle, since = we know=20 both Ki and = <SPAN=20 class=3DGramE>Ri.=20 Since we also have <I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Ri+<I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">1 <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">and since we know that <I=20 style=3D"mso-bidi-font-style: normal">A <I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5 B=20 <SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5 B=20 =3D A, we can perform the above <SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5=20 operation to recover <SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Li<SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">. <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">Notice that while recovering Li we did not need = the mangle=20 to be reversible.<I=20 style=3D"mso-bidi-font-style: normal"><o:p></o:p> <![if !supportLists]><I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">f)<SPAN=20 style=3D"FONT: 7pt 'Times New = Roman'"> =20 <![endif]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">3DES (also known as=20 <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">EDE</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">) works by first encrypting = plain text=20 with K1, then decrypting it with <st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">K2</st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">, <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">then encrypting it with = K1.=20 Thus there are 256*256 possible keys to try, or=20 2112 total tries to be made in the worst case before finding = the=20 correct keys. (Note that if three distinct keys were used, there is an = attack,=20 known as meet in the=20 middle attack that makes 3DES no more secure than performing = encryption once. This is the reason for reusing first key, instead of = three=20 unique keys.)<SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p></o:p> <o:p> </o:p> 2) <B=20 style=3D"mso-bidi-font-weight: normal">Passwords <o:p> </o:p> a)=20 In the Lamport one-time = password=20 scheme <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"> picks a password, =93pwd,=94 = and a=20 reasonably large number n (like 1000), and repeatedly applies a hash = function,=20 h, to it. She then sends <SPAN=20 class=3DGramE>hn(pwd) to Bob=20 along with n. Bob stores it in a database.<o:p></o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">When she wishes to prove her = identity to=20 Bob she contacts him, at which point Bob sends her back n, Alice then = computes=20 hn-1(pwd) and sends the result to Bob. Bob takes the received = quantity, hashes it once, and checks against the database. If it matches = Bob=20 considers the response valid and replaces the stored quantity with the = received=20 quantity and replaces n by n-1. <o:p></o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> <![if !vml]><img width=3D234 = height=3D126 src=3D"Solutions-IV_files/image001.gif" align=3Dleft = v:shapes=3D"_x0000_s1026 _x0000_s1027 _x0000_s1028 _x0000_s1029 = _x0000_s1030 _x0000_s1031 _x0000_s1032 _x0000_s1033 = _x0000_s1034"><![endif]> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">h(<SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">h999(pwd)) ?=3D=20 h1000(pwd)<o:p></o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><SPAN=20 style=3D"mso-spacerun: yes"> Replaces <SPAN=20 class=3DGramE>h1000(pwd) with=20 h999(pwd)<o:p></o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> <![if !vml]> <table cellpadding=3D0 cellspacing=3D0> <tr> <td width=3D88 height=3D28 bgcolor=3Dwhite = style=3D'vertical-align:top;background: white'><![endif]><![if !mso]><SPAN=20 style=3D"Z-INDEX: 2; POSITION: absolute; mso-ignore: vglayout"> <TABLE cellSpacing=3D0 cellPadding=3D0 width=3D"100%"> <TBODY> <TR> <TD><![endif]> <DIV class=3Dshape=20 style=3D"PADDING-RIGHT: 7.2pt; PADDING-LEFT: 7.2pt; = PADDING-BOTTOM: 3.6pt; PADDING-TOP: 3.6pt"=20 v:shape =3D "_x0000_s1035"> S/KEY</DIV><![if = !mso]></TD></TR></TBODY></TABLE><![endif]><![if !mso & = !vml]> <![endif]><![if !vml]></td> </tr> </table> <![endif]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">b)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>The=20 Lamport scheme is secure against eavesdropping since the password is = never sent=20 in the clear, only the hash (or hash chain) of the password is = communicated.=20 <o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">c)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>Even=20 though the password is not held in Bob=92s database, the hash chain of = the=20 password, hn<SPAN=20 class=3DGramE>(pwd) is, and so an attacker can do an offline = dictionary=20 attack by repeatedly making a guess and comparing <SPAN=20 class=3DSpellE>hn(guess) against the stored value.=20 <o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">d)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>In=20 the small n attack an intruder impersonates Bob and when=20 <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"> attempts to authenticate, = sends back a=20 small value for n, like 50. When <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"> responds with <SPAN=20 class=3DGramE>h50(pwd) then the intruder can utilize = this to=20 impersonate <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">, assuming the actual n at Bob = is greater=20 than 50.<o:p></o:p> <SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"><o:p> </o:p> 3) = <B=20 style=3D"mso-bidi-font-weight: normal">Sessions = Keys<o:p></o:p> <o:p> </o:p> a) <o:p> </o:p> <I=20 style=3D"mso-bidi-font-style: normal">KAB(<I=20 style=3D"mso-bidi-font-style: normal">KAB) is not a good = choice,=20 because this choice of session key would result in the same session key = for all=20 sessions. And it is advisable to have unique session keys for different=20 sessions. <o:p> </o:p> <I=20 style=3D"mso-bidi-font-style: normal">R(<I=20 style=3D"mso-bidi-font-style: normal">KAB)<SPAN=20 style=3D"mso-spacerun: yes"> is a bad choice, since R = was sent on=20 the clear. Thus the eavesdropper who obtains <I=20 style=3D"mso-bidi-font-style: normal">R(<I=20 style=3D"mso-bidi-font-style: normal">KAB)<SPAN=20 style=3D"mso-spacerun: yes"> can decrypt it with R and = obtain the=20 shared secret. <o:p> </o:p> <I=20 style=3D"mso-bidi-font-style: normal">R<I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5KAB=20 is not secure, because once the session key is discovered the = intruder=20 will also know the shared secret (because R was sent on the clear and KAB =3D R<I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5KAB<I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5R.) <o:p> </o:p> <SPAN=20 style=3D"mso-spacerun: yes"> = b) The=20 main reasons for using session keys are: <o:p> </o:p> If somebody is = performing attack,=20 the more information he gets encrypted with the same key, the more = likely he is=20 to succeed. Thus it is wise to use the secret shared key (or = authentication key)=20 only when establishing connection to generate a per-session key for = every new=20 session <o:p> </o:p> If the shared secret = is=20 compromised, but separate session keys were used for encrypting past = sessions it=20 would not be possible for the intruder who discovers the shared secret = to=20 decrypt recorded past sessions. <o:p> </o:p> When dealing with = untrusted=20 software, it is better to hand it a session key that is only valid for = one=20 session, than revealing the long-term secret key to the application. <o:p> </o:p> <![if !vml]> <table cellpadding=3D0 cellspacing=3D0> <tr> <td width=3D64 height=3D40 bgcolor=3Dwhite = style=3D'vertical-align:top;background: white'><![endif]><![if !mso]><SPAN=20 style=3D"Z-INDEX: 3; POSITION: absolute; mso-ignore: vglayout"> <TABLE cellSpacing=3D0 cellPadding=3D0 width=3D"100%"> <TBODY> <TR> <TD><![endif]> <DIV class=3Dshape=20 style=3D"PADDING-RIGHT: 7.2pt; PADDING-LEFT: 7.2pt; = PADDING-BOTTOM: 3.6pt; PADDING-TOP: 3.6pt"=20 v:shape =3D "_x0000_s1037"> <I=20 style=3D"mso-bidi-font-style: normal">string<I=20 style=3D"mso-bidi-font-style: = normal"><o:p></o:p></DIV><![if = !mso]></TD></TR></TBODY></TABLE><![endif]><![if !mso & = !vml]> <![endif]><![if !vml]></td> </tr> </table> <![endif]> =20 c) <![if !vml]> <table cellpadding=3D0 cellspacing=3D0 align=3Dleft> <tr> <td width=3D59 height=3D1></td> </tr> <tr> <td></td> <td><img width=3D246 height=3D114 = src=3D"Solutions-IV_files/image002.gif" v:shapes=3D"_x0000_s1039 = _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043"></td> </tr> </table> <![endif]><o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> <o:p> </o:p> If during this = exchange Trudy was=20 listening on the channel, Trudy would now be able to obtain the key, = since <I=20 style=3D"mso-bidi-font-style: normal">key =3D key <I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5<SPAN=20 style=3D"mso-spacerun: yes"> string <I=20 style=3D"mso-bidi-font-style: normal"><SPAN=20 style=3D"FONT-FAMILY: Symbol; mso-ascii-font-family: 'Nimbus Roman No9 = L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: symbol; = mso-symbol-font-family: Symbol"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Symbol">=C5<SPAN=20 style=3D"mso-spacerun: yes"> string. <o:p> </o:p> <![if !supportLists]><SPAN=20 style=3D"mso-fareast-font-family: 'Nimbus Roman No9 L'; = mso-bidi-font-family: 'Nimbus Roman No9 L'"><SPAN=20 style=3D"mso-list: Ignore">d)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>In this case <I=20 style=3D"mso-bidi-font-style: normal">known plain text or <I=20 style=3D"mso-bidi-font-style: normal">offline attack can be = performed. Some=20 encryption schemes are quite robust to this = type of=20 attack, but in many cases a few <I=20 style=3D"mso-bidi-font-style: normal"><plaintext, cipher text> = suffice=20 to calculate the secret key. Thus it is advisable to keep <I=20 style=3D"mso-bidi-font-style: normal"><plaintext, cipher text> = pairs=20 secret. <o:p> </o:p> 4)=20 Otway-Rees (slightly modified) <SPAN=20 style=3D"mso-spacerun: yes"> Alice = <SPAN=20 style=3D"FONT-FAMILY: Wingdings; mso-ascii-font-family: 'Nimbus Roman = No9 L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: = symbol; mso-symbol-font-family: Wingdings; mso-no-proof: yes"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Wingdings">=E0=20 Bob: Alice, Bob, <I=20 style=3D"mso-bidi-font-style: normal">KA(<SPAN=20 class=3DSpellE><I=20 style=3D"mso-bidi-font-style: = normal">NA,Alice,Bob<I=20 style=3D"mso-bidi-font-style: normal">) <SPAN=20 style=3D"mso-spacerun: yes"> Bob = <SPAN=20 style=3D"FONT-FAMILY: Wingdings; mso-ascii-font-family: 'Nimbus Roman = No9 L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: = symbol; mso-symbol-font-family: Wingdings; mso-no-proof: yes"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Wingdings">=E0=20 KDC: <I=20 style=3D"mso-bidi-font-style: normal">KB(<I=20 style=3D"mso-bidi-font-style: normal">NB, Alice, Bob<I=20 style=3D"mso-bidi-font-style: normal">), <I=20 style=3D"mso-bidi-font-style: normal">KA(<SPAN=20 class=3DSpellE>NA,<SPAN=20 style=3D"FONT-STYLE: normal">Alice,Bob) <SPAN=20 style=3D"mso-spacerun: yes"> KDC = <SPAN=20 style=3D"FONT-FAMILY: Wingdings; mso-ascii-font-family: 'Nimbus Roman = No9 L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: = symbol; mso-symbol-font-family: Wingdings; mso-no-proof: yes"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Wingdings">=E0=20 Bob: <I=20 style=3D"mso-bidi-font-style: normal">KA(<I=20 style=3D"mso-bidi-font-style: normal">NA,KAB),=20 KB(NB,KAB) <SPAN=20 style=3D"mso-spacerun: yes"> Bob = <SPAN=20 style=3D"FONT-FAMILY: Wingdings; mso-ascii-font-family: 'Nimbus Roman = No9 L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: = symbol; mso-symbol-font-family: Wingdings; mso-no-proof: yes"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Wingdings">=E0=20 Alice: <I=20 style=3D"mso-bidi-font-style: normal">KA(<I=20 style=3D"mso-bidi-font-style: = normal">NA,KAB) <SPAN=20 style=3D"mso-spacerun: yes"> Alice = <SPAN=20 style=3D"FONT-FAMILY: Wingdings; mso-ascii-font-family: 'Nimbus Roman = No9 L'; mso-hansi-font-family: 'Nimbus Roman No9 L'; mso-char-type: = symbol; mso-symbol-font-family: Wingdings; mso-no-proof: yes"><SPAN=20 style=3D"mso-char-type: symbol; mso-symbol-font-family: = Wingdings">=E0=20 Bob: <I=20 style=3D"mso-bidi-font-style: normal">KAB(Anything = recognizable) <o:p> </o:p> <o:p> </o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">a)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>The=20 KDC checks that the first part of the message is encrypted with = KB,=20 Bob=92s key, and that the names in the message, = =93<st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">=94, =93Bob=94 match with those = in the second=20 part which is encrypted with <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'">=92s key, KA. This = ensures that=20 only bob could have generated this message. (Note that the possibility = of a=20 replay attack is prevented down the line when = <st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"> checks the nonce NA = in Bob=92s=20 reply). <o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'; mso-fareast-font-family: 'Times = New Roman'"><SPAN=20 style=3D"mso-list: Ignore">b)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]><st1:City><st1:place><SPAN=20 style=3D"FONT-FAMILY: 'Times New = Roman'">Alice</st1:place></st1:City><SPAN=20 style=3D"FONT-FAMILY: 'Times New Roman'"> checks that the message is = encrypted=20 with the key KA, this ensures that = it was=20 generated by the KDC, she then checks that the message contains = NA,=20 this proves the freshness of the message and thus she knows Bob has = actually=20 talked to the KDC and not just used an old message from the KDC.=20 <o:p></o:p> <![if !supportLists]><SPAN=20 style=3D"mso-fareast-font-family: 'Times New Roman'"><SPAN=20 style=3D"mso-list: Ignore">c)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>There is no need for a separate round for = authenticating Bob to <st1:City><st1:place>Alice</st1:place></st1:City> = because=20 <st1:City><st1:place>Alice</st1:place></st1:City> ensures that she is = talking to=20 Bob from his reply. Bob=92s reply must be encrypted with=20 <st1:City><st1:place>Alice</st1:place></st1:City>=92s key, = KA, and=20 containing her nonce, NA, so she knows he must have been=20 authenticated by the KDC. (Note that a man in the middle attack by Trudy = is=20 possible but so long as Alice and Bob use the session key KAB = to=20 encrypt the rest of their conversation Trudy cannot impersonate Bob). = <![if !supportLists]><SPAN=20 style=3D"mso-fareast-font-family: 'Nimbus Roman No9 L'; = mso-bidi-font-family: 'Nimbus Roman No9 L'"><SPAN=20 style=3D"mso-list: Ignore">d)<SPAN=20 style=3D"FONT: 7pt 'Times New Roman'"> =20 <![endif]>If=20 =93Anything recognizable=94 were a fixed message then it would be = possible to infer=20 KAB by an offline attack that encrypted =93Anything = recognizable=94 with=20 all possible keys and compared against the cipher text. If a random salt = were=20 concatenated to =93Anything recognizable=94 then such an offline attack = would be=20 defeated since there are too many different possibilities to=20 check.</DIV></BODY></HTML>