Popular in Course
Popular in ComputerScienence
This 100 page Class Notes was uploaded by Roman McCullough on Friday October 30, 2015. The Class Notes belongs to CMPSCI 591 at University of Massachusetts taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/232271/cmpsci-591-university-of-massachusetts in ComputerScienence at University of Massachusetts.
Reviews for S
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/30/15
Chapter 8 Network Security GLOW El understand principles of network security 0 cryptography and its manyuses beyond confidentiahty O authentication Olnessageinteg ty 0 key distribution El security in practice O rewaHs 0 security in application transport network link layers 8 Network Security 84 Chapter 8 roadmap 81 What is network security 82 Principles of cryptography 83 Authentication 84 Integrity 85 Key Distribution and certification 86 Access control firewalls 87 Attacks and counter measures 88 Security in many layers 8 Network Security 872 What is ne rwor39k secur39i ry Confiden riali ry only sender in rended receiver should unders rand message con ren rs o sender encryp rs message 0 receiver decryp rs message Au rhen rica rion sender receiver wan r To confirm iden ri ry of each o rher Message InTegri ry sender receiver wan r To ensure message no r alTered in Transi r or af rerwards wi rhou r deTecTion Access and Availabili ry services musT be accessible and available To users a Nemmk Secumv 373 Friends and enemies Alice Bob Trudy El well known in ne rwork securiTy world El Bob Alice lovers wan r To communicaTe quotsecurelyquot El Trudy inTruder may in rercep r dele re add messages ch annel dafacon139rol messag a Nemmk Secumv m Who might Bob Alice be El well rea 39fe Bobs and Alices El Web browserserver for electronic transactions eg online purchases El online banking clientserver El DNS servers El routers exchanging routing table updates El other examples 8 Network Security 875 There are bad guys and girls out there 9 What can a bad guyquot do a lot 0 eavesdrap intercept messages 0 actively insem messages into connection 0 I39mpequotsana an can fake spoof source address in packet or any field in packet O hoboMg take overquot ongoing connection by removing sender or receiver inserting himself in place 0 dem39a afsequotvca prevent service from being used by others eg by overloading resources more an f1s a7 equot 8 Network Security 876 Chap rer39 8 r39oadmap 81 Who is ne l39work secur i ry 82 Principles of cr39yp l39ogr aphy 83 Au l39hen rica l39ion 84 In l39egr i l39y 85 Key Dis l39r39ibu rion and cer39139ifica139ion 86 Access control firewalls 87 A H39acks and counter measures 88 Securi ry in many layers a Nemmk Sammy 377 The Ian ua eof cr39 To m h EAlice39s C Bob39s KA encryption K decryption key B key l cipherfexf decryption algorithm Eluinfexf luinTexT encrYl 39Oquot P algorithm symmeTric key crypTo sender receiver keys I39denrb a public key crypTo encrypTion key pubIr decrypTion key secrer priva re a Nemmk Sammy H Symmei ric key cryp rographx substitution cipher substituting one thing for another 0 monoaiphabetic cipher substitute one letter for another plaintext abcdefghijklmnopqrstuvwxyz ciphertext mnbvcxzasdfghj klpo iuytrewq Plaintext bob 1 love on alice ciphertext nkn s gktc wky ingst 9 How hard To break This simple cipher i brufe force how hard o i her x Newark Secumv x v Symme r ric key crypi og raphx piaintext Iaintext message m algorithm L m KAVBKAVBm symmetric ke crypfo Bob and Alice share know same symmetric f key AVE El eg key is knowing subsfifufion pa ern in mono alphabefic subsfifufion ci her El 9 how do Bob and Alice agree on key value x Newark Secumv x in Symmetric key crypto DES DES Data Encryption Standard El US encryption standard NIST 1993 El 56bit symmetric key 64bit plaintext input El How secure is DES O DES Challenge 56bitkeyencrypted phrase Strong cryptography makes the world a safer placequot decrypted brute force in 4 months 0 no known backdoor decryption approach El making DES more secure 0 use three keys sequentially 3DES on each datum 0 use cipherblock chaining a Nemm Secuv v 541 M m ML i M n v WNW DES operation initial permutation imam 16 identical rounds of Q function application 3 each using different 48 bits of key l final permutation i Q m pews W7 c4 bi 0W x Nemm seem m AES Advanced EncrypTion STandard El new Nov 2001 symme rrickey NIST s randard replacing DES El processes da ra in 128 bi r blocks El 128 192 or 256 bi r keys El bru re force decryp rion rry each key Taking 1 sec on DES rakes 149 Trillion years for AES 8 Network Security 843 Public Key CrypToqraphy symmefn39c key cryp ro publo key cryp roqraphy 393 3 CI requires sender El radically different receiver know shared approach Diffie secre r key Hellman76 RSA78 a CI Q how To agree on key CI sender receiver do in firs r place mn share secre r key particularly if never fquot CI publo encryp rion key me known To a CI pn39vafe decryp rion key known only To receiver 8 Network Security 844 Public key crxp rogr39aghx K Bob39spublic B key K Bob39s privafe B key I x l 5 pluinTexT erquotZV YPT39OV ciherTexT decryption Elainfexf messagem GIQOV39Tl I quot Km algorithm message m KgKm a Nemmk Secumy 845 Public key encrxp rion algori rhms Requirements need KE and K39B such The KKm m given public key Kg i r should be impossible Tocompu re priva l e key KB RSA Rivesf Shamir Adelson algori rl lm E Nemmk Secumy 845 RSA Choosinq keys 1 Choose Two large prime numbers p q eg 1024 bi rs each 2 Compu re n pq z pJqJ 3 Choose 5 wi rh eltn rha r has no common fac rors wi rh z e zare rela rively primequot 4 Choose dsuch rha r ed J is exac rly divisible by z in o rher words edmod z 1 5 PubI39c key is 075 Prvafe key is nd HT HT39 K K B B 8 Network Security 847 RSA Encryption decryp rion 0 Given ne and no as compu red above 1 To encryp r bi r pa r rern m compu re c m5 mod n ie remainder when me is divided by n 2 To decryp r received bi r pa r rern c compu re m cdmod n ie remainder when cdis divided by n h Magicl m memod ndmod n appens 2 C 8 Network Security 848 RSA example Bob chooses p5 qZ Then n35 224 55 so 5 zrela rively prime 29 so ed J exac rly divisible by 2 Jr le r rer m me c memod n encryp 39 I 12 1524832 17 C Cd m m decryp r 17 481968572106750915091411825223071697 12 I 8 Network Security 849 Why is ThaT m memod nzdmod n Useful number rheory resul r If pq prime and quot qu We y ymod 021144 xmodnx mod7 memod I7dmod n megmod n med mod pJqJ mod n using number Theory resul r above m mod n since we chose ea fo be divisible by pJqJ wifh remainder 1 m 8 Network Security 8720 RSA anofher imporfanf properfy The following proper ry will be very useful la rer K39BKm m KK39Bm 2 use public key use priva re key firs r followed firs r followed by priva re key by public key Resuf is ve same 8 Network Security 8721 Chap rer 8 roadmap 81 Wha r is ne rwork securi ry 82 Principles of cryp rography 83 Au rhen rica rion 84 In regri ry 85 Key Dis rribu rion and cer rifica rion 86 Access con rrol firewalls 87 A r racks and coun rer measures 88 Securi ry in many layers 8 Network Security 8722 Au rhen rica rion Goal Bob wan rs Alice 1390 quotprovequot her iden ri ry To him ProTocol agl0 Alice says I am Alicequot Failure scenario a Nemmk Secumy 8723 Au rhen rica rion Goal Bob wan rs Alice 1390 quotprovequot her iden ri ry To him ProTocol agl0 Alice says I am Alicequot in a ne rwork 3 Bob can no r see Alice so Trudy simply 4 I am Alicequot dBClar es herself To be Alice 8 Nemmk Secumy arm Au rhen rica rion ano rher Try ProTocol aEZO Alice says I am Alicequot in an IP packe r con raining her source IP address Failure scenario a Nemmk Secumy 8725 Au rhen rica rion ano rher Tr ProTocol aEZO Alice says I am Alicequot in an IP packe r con raining her source IP address Trudy can crea re a packe spoofingquot A lice39s address a Nemmk Secumy 8726 Au rhen rica rion ano rher Try ProTocol ap30 Alice says I am Alicequot and sends her secre r password To quotprovequot i r c Alic 39 passwor 4 Ali IP uddr Failure scenario a Nemmk Secumy 8727 Au rhen rica rion ano rher Tr ProTocol ap30 Alice says I am Alicequot and sends her secre r password To quotprovequot i r playback affack Trudy records Alice39s packet an after plays it back To Bob 8 Nemmk Secumy 8728 Au rhen rica rion ye r ano rher rr39v ProTocol ap31 Alice says I am Alicequot and sends her encrypfedsecre r password To quotprovequot i r Alice39s encrypted Mic I add passwor 3 Failure scenario a Nemmk Secumy 8729 Au rhen rica rion ano rher Tr ProTocol ap31 Alice says I am Alicequot and sends her encrypfedsecre r password To quotprovequot i r a Nemmk Secumy Eran Au rhenficafion ye r anofher TEX Goal avoid playback affack Nance number R used only once naI39ferme 2240 To prove Alice quotlivequot Bob sends Alice nonce R Alice must refurn R encrypi39ed wifh shared secre139 key I am Alicequot 1 R K R Alice is live and Namp only Alice kno key to encrfo nonce so it must Failures drawbacks 5392 Alice x Newark Secumv x a Au rhenficafion 0950 ap40 requires shared symmefric ke D can we aufhem39icafe using public key Techniques apao use nonce public key crypfography I am Alicequot l39 A C Bob com pales M KKR R an send my mm W could have the private uc i at K A K 01 I2 x Newark Secumv x 32 ap50 securi ry hole Man woman in The middle aTTack Trudy poses as Alice To Bob and as Bob To Alice 4 1 5 I am Alice I am Alice 39 K A My gm 41L K39 K no m K90 s 39 encrypfed wifh m K39 K m A A Alice39s public key a NeMukaecumy 8733 ap50 securi ry hole Man woman in The middle aTTack Trudy poses as Alice To Bob and as Bob To Alice 4 I I 9 g T V 4 v V Difficul r To deTecT El Bob receives every rhing Tha r Alice sends and vice versa eg so Bob Alice can meeT one week laTer and recall conversaTion El problem is Tha r Trudy receives all messages as well a NeIwuik Secumy 8736 Chapter 8 roadmap 81 What is network security 82 Principles of cryptography 83 Authentication 84 Message integrity 85 Key Distribution and certification 86 Access control firewalls 87 Attacks and counter measures 88 Security in many layers 8 Network Security 8735 Digital Signatures Cryptographic technique analogous to hand written signatures EI sender Bob digitally signs document establishing he is document ownercreator CI verifiable nonforgeable recipient Alice can prove to someone that Bob and no one else including Alice must have signed document 8 Network Security 8736 DigiTal SignaTur es Simple digiTal signaTur39e for39 message m CI Bob signs in by encr ypTing wiTh his pr ivaTe key Kg cr eaTing quotsignedquot message Krm 39 39 Bob39s rivaTe Bobs message m KB key P K30 Dear Alice 39 Oh howl have missed BObls message you I think of you all the m39 Slgned time bah blah blah SnCWpteCl With Bob algoriThm his private key 8 Network Security 8737 DiqiTal SiqnaTur es more CI Suppose Alice r eceives msg m digiTal signaTur e K m CI Alice verifies m signed by Bob by applying Bob39s public key K To Kgm Then checks KK m in CI If KK m m whoever signed in musT have used Bob39s pr ivaTe key Alice Thus ver ifies ThaT J Bob signed in J No one else signed in J Bob signed in and noT m39 NonrepudiaTion Alice can Take m and signaTur e K m To cour T and prove ThaT Bob signed in 8 Network Security 8738 Message Digesfs large message Compu ra rionally expensive ro publickeyencr yp r long messages Goal fixedleng rh easy Hash func rion pr oper fies focompu re digi ral quotfinger pr in rquot CI apply hash func rion H m m ge r fixed size message diges r Hm CI manyfol CI produces fixedsize msg diges r finger pr in r CI given message diges r x compu ra rionally infeasible To find m such rha r x Hm 8 Network Security 8739 Infer nef check3um poor crxpfo hash funcfion Infer ne r checksum has some pr oper fies of hash func rion produces fixed leng rh diges r 16bi r sum of message is manyfoone Bu r given message wi rh given hash value if is easy To find ano rher39 message wi rh same hash value message IOUl 009 9303 ASCII forma r message ASCII forma r 494F5531 IOUg 494F55 30302E39 001 30302E 3942D242 9BOB 3942D242 B2 c1 D2 AC differem messages 32 c1 D2 AC buf iden rical checksums 8 Network Security 840 20 Di iTal Si naTur e Si ned messa e di esT Alice ver ifies signa rur e and Bob sends d39g39lally S39Qned infegr ify of digifally signed message message lar39ge H H h messa 39 1 as m g funcTIon i 9 8 Network Securlty 81H dlgifal Signature encrypt d IgITaI SignaTure B decrypT l Hash FuncTion Alqor39iThms CI MD5 hash func rion widely used RFC 1321 O compu res 128bi r message diges r in 4s rep process 0 ar bi rr ar y 128bi r s rr ing x appear s difficul r ro cons rr39uc r msg m whose MD5 hash is equal m x CI SHAl is also used 0 US s randar d NIST FIPS PUB 1801 0 160bi r message diges r 8 Network Securlty 842 21 Chapter 8 roadmap 81 What is network security 82 Principles of cryptography 83 Authentication 84 Integrity 85 Key distribution and certification 86 Access control firewalls 87 Attacks and counter measures 88 Security in many layers 8 Network Security 843 Trusted Intermediaries Symmetric key problem Public key problem CI How do two entities CI When Alice obtains establish shared secret Bob39s public key from key over network web site email solu on diskette how does she know it is Bob39s public CI trusted key distribution key of Trudys center KDC acting as intermediary between SOIUT39OW entities CI trusted certification authority CA 8 Network Security 844 Key Distribution Center KDC CI Alice Bob need shared symme rr ic key CI KDC server shares differenf secr39e139 key wi rh each regis rer ed user39 many users CI Alice Bob know own symme rr39ic keys KAKDC KBKDC for communica ring wifh KDC a Netwurk Security 845 Key Disfr39ibu iion Cen ier39 KDC 039 How does KDC allow Bob Alice To defermine shared symme rr39ic secr39e139 key To communica re wifh each ofher KAKDCAv B gt AlicemKDcAR1 knows W Bob knows To use R1 To R1 KBKDCAvR1 communicate A Milli Alice Alice and Bob communicafe using R1 as session key for shared symme rr ic encr39yp rion E Netwurk Security 846 Cer l39ifica i39ion Au l39hori l39ies El CerTificaTion auThoriTy CA binds public key To parTicular en h E El E person rouTer regisTers iTs public key wiTh CA 0 E provides proof of idenfifyquot1 o CA 0 CA creafes cerfificafe binding E To ifs public key 0 cerfificafe confaining E39s public key digifally signed by CA CA says this is E39s public keyquot Bob39s a public K key KB B b cerfificafe for o s identifying Bobs public key information signed by CA a Nelwuik Secule aw Cer l39ifica i39ion Au l39hori l39ies El When Alice wanTs Bob39s public key 0 geTs Bob39s cerTificaTe Bob or elsewhere 0 apply CA39s public key To Bob39s cerTificaTe geT Bob39s public key a Nelwuik Secule ma A certificate contains Serial number to issuer CI info and key algorithm info about certificate issuer val id dates digital signature by issuer r Warn before sending data m sites certi ed by this authority OK 8 Network Security 8749 Chapter 8 roadmap 81 What is network security 82 Principles of cryptography 83 Authentication 84 Integrity 85 Key Distribution and certification 86 Access control firewalls 87 Attacks and counter measures 88 Security in many layers 8 Network Security 8750 25 Firewalls ll CVVU isola res organiza rion39s in rernal ne r from larger In rerne r allowing some packe rs To pass blocking o rhers public InTerneT adminisTered ne rwork firewall 8 Network Security 8751 Firewalls Why preven r denial of service a r racks O SYN flooding a r racker es rablishes many bogus TCP connec rions no resources lef r for quotrealquot connec rions preven r illegal modifica rionaccess of in rernal da ra O eg a r racker replaces CIA39s homepage wi rh some rhing else allow only au rhorized access ro inside ne rwork se r of au rhen rica red usershos rs rwo Types of firewalls O applica rionlevel o packe rfil rering 8 Network Security 8752 26 Should arriving packe r be allowed in Deparfing packe r le r ouf PackeT FilTer39ing CI in rernal ne rwork connec red ro In rerne r via rou rer firewall CI rou rer fil rers packe rbypacke r decision ro forwarddrop packe r based on 0 source IP address des rina rion IP address 0 TCPUDP source and des139ina139ion por139 numbers 0 ICMP message Type O TCP SYN and ACK bi139s 8 Network Security 8753 Packe i Filfering CI Example 1 block incoming and ou rgoing da ragrams wi rh IP pro rocol field 17 and wi rh ei rher source or des r por r 23 0 All incoming and ou rgoing UDP flows and relne r connec rions are blocked CI Example 2 Block inbound TCP segmen rs wi rh ACKO O Preven rs ex rernal clien rs from making TCP connec rions wi rh in rernal clien rs bu r allows in rernal clien rs ro connec r ro ou rside 8 Network Security 8754 27 Application gateways CI Filters packets on application data as well as on IPTCPUDP fields CI Example allow select internal users to telnet outside gatewaytoremote host te net session hosttogateway telnet session 1 Require all telnet users to telnet through gateway 2 For authorized users gateway sets up telnet connection to dest host Gateway relays data between 2 connections 3 Router filter blocks all telnet connections not originating from gateway 8 Network Security 8755 Limitations of firewalls and gateways CI IP spoofing router can39t know if data quotreallyquot comes from claimed source CI if multiple app s need special treatment each has own app gateway CI client software must know how to contact gateway o eg must set IP address of proxy in Web browser CI filters often use all or nothing policy for UDP CI tradeoff degree of communication with outside world level of security CI many highly protected sites still suffer from attacks 8 Network Security 8756 28 Chapter 8 roadmap 81 What is network security 82 Principles of cryptography 83 Authentication 84 Integrity 85 Key Distribution and certification 86 Access control firewalls 87 Attacks and counter measures 88 Security in many layers 8 Network Security 8757 Internet security threats Mapping 0 before attacking case the Jointquot find out what services are implemented on network 0 Use ping to determine what hosts have addresses on network 0 Portscanning try to establish TCP connection to each port in sequence see what happens 0 nmap httpwwwinsecureorgnmap mapper network exploration and security auditingquot Countermeasures 8 Network Security 8758 29 InTerneT securiTy ThreaTs Mapping coun iermeasures 0 record Traffic en rering ne rwork 0 look for suspicious ac rivi ry IP addresses por rs being scanned sequen rially 8 Network Security 8759 InTerneT securiTy ThreaTs Packe r sniffing O broadcas r media 0 promiscuous NIC reads all packe rs passing by O can read all unencryp red da ra eg passwords O 69 C sniffs B39s packe rs A c srcBdestA payload B Coun rermeasures 8 Network Security 8760 30 InTerneT securiTy ThreaTs Packe r sniffin coun rermeasures 0 all hos rs in organiza rion run sof rware Tha r checks periodically if hos r in rerface in promiscuous mode 0 one hos r per segmen r of broadcas r media swi rched E rherne r a r hub A g QC srcB destA payload l B 8 Network Security 8761 InTerneT securiTy ThreaTs IP Spoofing O can genera re quotrawquot IP packe rs direc rly from applica rion pu r ring any value in ro IP source address field 0 receiver can39f Tell if source is spoofed O eg C pre rends To be B Coun rermeasures 8 Network Security 8762 31 Infernef securify Threafs IP Spoofing ingress fil rering O rou rers should no r forward ou rgoing packe rs wi rh invalid source addresses eg da ragram source address MT in rou rer39s ne rwork O grea r bu r ingress fil rering can no r be manda red for all ne rworks 8 Network Security 8763 Infernef securify Threafs Denial of service lDOS O flood of maliciously genera red packe rs quotswampquot receiver 0 Dis rribu red DOS DDOS mul riple coordina red sources swamp receiver 0 eg C and remo re hos r SYNaffack A A lil iii C 8 Network Security 8764 32 Infernef securify Threafs Denial of service DOS counfermeasures O fil rer ou r flooded packe rs eg SYN before reaching hos r Throw ou r good wi rh bad 0 fraceback ro source of floods mos r likely an innocen r compromised machine 8 Network Security 8765 Chap rer 8 roadmap 81 Who is ne rwork securi ry 82 Principles of cryp l39ography 83 Aufhen rica rion 84 Infegri ry 85 Key Dis rribu rion and cer rifica rion 86 Access confrol firewalls 87 Affacks and counfer measures 88 Securi ry in many layers 881 Secure email 882 Secure socke rs 883 IPsec 884 Securi ry in 80211 8 Network Security 8766 33 Secure email a Alice wants to send confidential e rnail m to Bob Alice El generates random symmefrcprivate key K5 El encrypts message with K5 for efficiency El also encrypts K5 with Bob39s public key El sends both K5m and KBK5 to Bob 8 Nelwuvksecumv arm Secure email a Alice wants to send confidential e rnail m to Bob K5 Kams Bo El uses his private key to decrypt and recover K5 El uses K5 to decrypt K5m to recover m a Nelwuvksecumv area Secure email continued Alice wan rs To provide sender au rhen rica rion message inTegri ry WA lt9 m T Alice digi rally signs message sends bo rh message in The clear and digi ral signa rure a Nelwuvksecumv area K KHm H 1 compare l m m Secure email continued Alice wan rs To provide secrecy sender auThen rica rion message inTengTy EVE m Hm ng o m 1 6 K5 KK5 KE Alice uses Three keys her priva re key Bob39s public key newly crea red symmeTric key a Nelwuvksecumv mu PreTTy qood privacy PGP CI Inferne r email encryp rion scheme defacfo sfandard D uses symme rric key cryp rography public key cryp rography hash funcfion and digi ral signa rure as described provides secrecy sender aufhen rica rion in regri ry D D was Targef of 3year federal invesfigafion A P6P signed message inven139or Phil Zimmerman BEGIN PGP SIGNED MESSAGE Hash SHA1 BobMy husband 1s out of town tonightPasslonately yours Alice BEGIN PGP SIGNATURE Version PGP 50 Charset noconv thJRHhGJthglZEpJ108gE4VB3qu hFEVZP9t6n7G6m5Gw2 END PGP SIGNATURE 8 Network Security 8771 Secure sockeTs layer 55L CI Transpor r layer securi ry To any TCP based app using SSL services CI used be rween Web browsers servers for ecommerce sh r rp CI securi ry services 0 server au rhenficafion O dafa encryp rion O clien r au rhenficafion opfional CI server au rhen rica rion O SSLenabled browser includes public keys for rrus red CAs 0 Browser requests server cer rifica re issued by rrus red CA 0 Browser uses CA39s public key To ex rracf server39s public key from cer rifica re CI check your browser39s securi ry menu To see i rs rrus red CAs 8 Network Security 8772 36 55L lcom inuedl Encryp red SSL session CI Browser genera res symmefn39c sessmn key encryp rs i r wi rh server39s public key sends encryp red key To server CI Using priva re key server decryp rs session key CI Browser server know session key 0 All dafa sen in ro TCP socke r by clien r or server encrypfed wi139h session key CI SSL basis of IETF Transpor r Layer Securi ry TLS CI SSL can be used for nonWeb applica rions eg IMAP CI Clien r au rhen rica rion can be done wi rh clien r cer rifica res 8 Network Security 8773 IPsec NeTwork Layer SecuriTy CI Ne rwork layer secrecy o sending hos r encrypts rhe dafa in IP da ragram O TCP and UDP segmen rs ICMP and SNMP messages CI Ne rworklayer au rhen i39icafion O desfinafion hos139 can au rhen rica re source IP address CI Two principle profocols O au rhenficafion header AH profocol O encapsula rion securi ry payload ESP profocol CI For bo139h AH and ESP source desfinafion handshake O creafe nefworklayer logical channel called a securi ry associafion SA CI Each SA unidirec rional CI Uniquely defermined by O securi ry pro rocol AH or 0 source IP address 0 32bi1 connec rion ID 8 Network Security 8774 37 AuThenTicaTion Header AH ProTocol CI provides source auThenTicaTion daTa inTegriTy no confidenTialiTy CI AH header inserTed beTween IP header daTa field CI proTocoI field 51 CI inTermediaTe rouTers process daTagrams as usual AH header includes CI connecTion idenTifier CI auThenTicaTion daTa source signed message digesT calculaTed over original IP daTagram CI nexT header field specifies Type of daTa eg TCP UDP ICMP IP header AH header daTa eg TCP UDP segmenT 8 Network Security 8775 ESP ProTocoI CI provides secrecy hosT auThenTicaTion daTa inTegriTy CI daTa ESP Trailer encrypTed CI nexT header field is in ESP Trailer CI ESP auThenTicaTion field is similar To AH auThenTicaTion field CI ProTocol 50 4 auThenTicaTed gt 1 llt encrypTed gtl ESP ESP ESP l IP header TCPUDP segmem Trailer auThenT 8 Network Security 8776 38 IEEE 80211 securiTy CI Wardn39whg drive around Bay area see wha r 80211 ne rworks available 0 More Than 9000 accessible from public roadways O 85 use no encryp rionau rhen rica rion O packe rsniffing and various a r racks easy CI Securing 80211 0 encryp rion au rhen rica rion O firs r a r remp r a r 80211 securi ry Wired Equivalen r Privacy WEP a failure 0 curren r a r remp r 80211i 8 Network Security 8777 Wired EquivalemL Privacy WEP CI au rhen rica rion as in pro rocol 0040 O hos r reques rs au rhen rica rion from access poin r 0 access poin r sends 128 bi r nonce O hos r encryp rs nonce using shared symme rric key 0 access poin r decryp rs nonce au rhen rica res hos r CI no key dis rribu rion mechanism CI au rhen rica rion knowing The shared key is enough 8 Network Security 8778 39 WEP daTa encrypfion CI Hos rAP share 40 bi r symme rr ic key semi permanen r CI Hos r appends 24bi r ini rializa rion vec ror IV To cr ea re 64bi r key CI 64 bi r key used To genera re s rr eam of keys kiIV CI kiIV used To encr yp r i rh by re di in frame ci di XOR k3quot CI IV and encr yp red by res ci sen r in frame 8 Network Secu ty 8779 80211 WEP encrypTion IV per frame Ks 40bit key sequence generator secret for given Ks IV symmetric If 12 13 19 1pm 13m 80211 WEPencxypted data thlext heada lus CRC frame data gtd d2 d3 d CRC CRC4 plus CRC V V V V V 01 02 c c om QM Senderside WEP encr yp rion 8 Network Secu ty 8780 40 Breakinq 80211 WEP encryption Security hole CI 24bit IV one IV per frame gt IV39s eventually reused CI IV transmitted in plaintext gt IV reuse detected El Attack 0 Trudy causes Alice to encrypt known plaintext d1 d2 d3 d4 O Trudy sees ci di XOR kiIV O Trudy knows ci di so can compute kiIV O Trudy knows encrypting key sequence kllv kZIV k3IV 0 Next time IV is used Trudy can decrypt 8 Network Security 8781 80211i improved security El numerous stronger forms of encryption possible El provides key distribution El uses authentication server separate from access point 8 Network Security 8782 41 80211i four phases of operation AP access point I T AS client station Authentication 4 Discovery of security capabilities I STA and AS mutually authenticate together generate Master Key MK AP servers as pass throughquot STA derives Pairwise Master 5212 KEHPMK sendsto AP 0 STA AP use PMK to derive Temporal Key TK used for message enCFYPtionr integrity 8 Network Security 8783 EAP extensible authentication protocol El EAP endend client mobile to authentication server protocol El EAP sent over separate links 0 mobiletoAP EAP over LAN 0 AP to authentication server RADIUS over UDP 8 Network Security 8784 42 Ne rwork Securi ry Summary Basic Techniques O cryp rography symme rric and public 0 au rhen rica rion 0 message in regri ry 0 key dis rribu rion used in many differen r securi ry scenarios 0 secure email 0 secure Transpor r 55L 0 IP sec 0 80211 8 Network Security 8785 43 Regular Languages Lecture 2 Computational Linguistics CMPSCI 591N Spring 2006 University of Massachusetts Amherst Andrew McCaIIum Andrew McCallurn UNIass Amherst including material from Chris Manning and Jason Eisner A Little About Yourselves Have you programmed before Almost none at all Not much work for a software company Fortran C C C Lisp Perl Python Java Only Basic on my Tandy 286 mmmmmmmmmmmmmmmmmmmm st A Little About Yourselves Hobbies Fencing Hiking Singing Cooking Poker Working on machines like cars motorcycles airplanes Drinking Smoking Fencing Watching movies especially awesomely bad ones mmmmmmmmmmmmmmmmmmmm st A Little About Yourselves Favorite authors Kurt Vonnegut George Orwell Noam Chomsky Asimov Tolkein Pinger I avoid reading sorry Tolkein x6 CS Lewis etc Stroustrup Arthur C Clark Hemmingway x2 Salman Rushdie Obscure foreign names like Savyon Librecht Karel Capek Milan Kundera Bulgahov mmmmmmmmmmmmmmmmmmmm st A Little About Yourselves Why are you in the class Practical skills to help in my linguistic research accessing data building grammars Interested in how probabilistic methods can be integrated with algebraic grammars Possibilities of a computer that can make sense of language are very exciting I want to expand my knowledge of Al I want to focus my career in CL especially translation Want to simulate the mind s big bang I think this will help me get a job mmmmmmmmmmmmmmmmmmmm st Today s Main Points Examples of computation helping in Linguistic goals What are regular languages finite state automata and regular expressions Writing regular expressions in Python Examples on several large natural language corpora Finitestate transducers and morphology Homework assignment 1 mmmmmmmmmmmmmmmmmmmm st Some brief history 1950s Early CL on machines less powerful than pocket calculators Foundational work on automata formal languages probabilities and information theory First speech systems Davis et al Bell Labs MT heavily funded by military but basicallyjust word substitution programs Little understanding of natural language syntax semantics pragmatics mmmmmmmmmmmmmmmmmmmm st Some brief history 1960s Alvey report 1966 ends funding for MT in America the lack of real results realized ELIZA MIT Fraudulent NLP in a simple pattern matcher psycholtherapist It s true I am unhappy Do you think coming here will make you not to be unhappy I need some help that much is certain What would it mean to you if you got some help Perhaps I could earn to get along with my mother Tell me more about your family Early corpora Brown Corpus Kudera and Francis Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Some brief history 1970s Winograd s SHRDLU 1971 existence proof of NLP in tangled LISP code Could interpret questions statements commands Andrew McCallum UMass Amherst Which cube is sitting on the table The large green one which supports the red pyramid Is there a large block behind the pyramid Yes three of them A large red one a large green cube and the blue one Put a small one onto the green cube with supports a pyramid OK including material from Chris Manning and Jason Eisner Some brief history 1980s Procedural gt Declarative including logic programming Separation of processing parser from description of linguistic knowledge Representations of meaning procedural semantics SHRDLU semantic nets Schank logic perceived as answer finally applicable to real languages Montague Perceived need for KR Lenat and Cyc Working MT in limited domains METEO mmmmmmmmmmmmmmmmmmmm st Some brief history 1990s Resurgence of finitestate methods for NLP in practice they are incredibly effective Speech recognition becomes widely usable Large amounts of digital text become widely available and reorient the field The Web Resurgence of probabilistic statistical methods led by a few centers especially IBM speech parsing Candide MT system often replacing logic for reasoning Recognition of ambiguity as key problem Emphasis on machine learning methods mmmmmmmmmmmmmmmmmmmm st Some brief history 2000s Abit early to tell But maybe Continued surge in probability Bayesian methods of evidence combination and joint inference Emphasis on meaning and knowledge representation Emphasis on discourse and dialog Strong integration of techniques and levels brining together statistical NLP and sophisticated linguistic representations Increased emphasis on unsupervised learning mmmmmmmmmmmmmmmmmmmm st Examples of Computation Helping Linguistics Kevin Knight A Computational Approach to Deciphering Unknown Scripts Mayan Writing Pronunciation model by Expectation Maximization which we will study in about 5 wee ks Figure l The Pheiscos Disk c 17DOBC The disk is six inches wide dou Ivasided and is the earliest known document printed with a form of movable type mmm LMAssAmm numemmim an mmhsmam Examples of Computation Helping Linguistics Other examples coming later Learning Lexical Semantics Augmenting WordNet by mining the Web Automatically discovering English versus Japanese word order by grammar induction Neural Network learners go through the same periods mistakes on irregular verbs as children do and others mmmmmmmmmmmmmmmmmmmm st Noun phrase parsing Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Ed Hovy s thing Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Noam Chomsky 1928 Chomsky Hierarchy Generative Grammar LiberatarianSocialist The most cited person alive A Language Some sentences in the language The man tOOk the bOOk FromIChomsky19561hisfirstcontextfreeparsetree The purple giraffe hopped through the clouds This sentence is false Some sentences not in the language The girl the sidewalk the chalk drew Backwards is sentence this loDvaD tlhlngan Hol ghojmoH be mmmmmmmmmmmmmmmmmmmm st Compact description of a language Start with some nonterminal symbol S Expand that symbol using some substitution rules keep applying rules until all nonterminals are expanded to terminals The string of terminals is in the sentence mmmmmmmmmmmmmmmmmmmm st Chomsky Hierarchy Linguistic Type 0 languages Turingequivalent example ATNs Rewrite rules a a b where a b are any string of terminals and nonterminals Contextsensitive languages Rewrite rules aXb a acb TAGs where X is nonterminal and ab as above Contextfree languages PSGs Rewrite rules X a a where X a b as above FSAs O39ef a 432 s 07 all 8 Regular languages Rewrite rules X a aY where X Y are nonterminals and a is a string of terminals 44 age7 Andrew McCallum UMass Amherst including mater39al fr m cnris Manning and Jason Eisner Regular language example Nonterminals S X Y z An expansion Terminals m o S Rules mX S gt mX moY i 3quot mooY Y gt mooo Start symbol mmmmmmmmmmmmmmmmmm st Example Sheep Language Strinqs in and out of the example Regular Language Inthelanguage baF baaF baaaaaV Notmthelanguage ba bF abF bbaaaF aHbabaV Finitestate Automata indicates accept state a 9 I r doublecircle Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Recognizer A recognizer for a language is a program that takes as input a string W and answers yes if W is a sentence in the language and answers no otherwise We can think of this as a machine that emits only two possible responses it input mmmmmmmmmmmmmmmmmmmm st Regular Languages related concepts Regular Languages the accepted strings Finitestate Automata Regular Expressions machinery for accepting a way to type the automata Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Finite State Automata more formally A finite state automata is a 5tuple Q 2 qo F 6qi Q finite set of N states q0 q1 q2 qN nonterminals 2 finite set of terminals 6qi transition function given state and input returns next state production rules qo the start state F the set of final states b a The FSA gt63 q2 State marker Q Input tape b a a a a We will later return to a probabilistic version of this Annewnccnnmnnasnmm with Hidden Markov Models including material from Chris Manning and Jason Eisner Transition Table 5 mmmmmmmmmmmmmmmmmmmm st Input State b a l O 1 Q Q 1 Q 2 Q 2 Q 2 3 3 Q Q Q Regular Expressions The foundational operations Pattern Matches Concatenation abc abc Disjunction a b a b a bbd ad bbd Kleene star a e a aa aaa cabb ca Cbba The empty string Regular expressions Finitestate automata are Closed under these operations Andrew McCallum UMass Amherst 39 39ng material from Chris Manning and Jason Eisner Stephen Kleene 1909 1994 Attended Amherst College Best known for founding the branch of mathematical logic known as recursion theory together with Alonzo Church Kurt Godel Alan Turing and others and for inventing regular expressions KIeeneiness is next to Godeliness mmmmmmmmmmmmmmmmmmmm st Practical Applications of RegEx s Web search Word processing find substitute Validate fields in a database dates email addr URLs Searching corpus for linguistic patterns and gathering stats Finite state machines extensively used for acoustic modeling in speech recognition information extraction eg people amp company names morphology Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Two types of characters in REs Literal Every normal text character is an RE and denotes itself Metacharacters Special characters that allow you to combine REs in various ways Example a denotes a a denotes a or a or aa or aaa or mmmmmmmmmmmmmmmmmmmm st Basic Regular Expressions Pattern Matches Character Concat went went Alternatives go went go went aeiou a O u disjunc negation Aaeiou b c d f g wildcard char a z amp Loops amp skips a e a aa aaa one or more a a aa aaa zero or one colour color colour Andrew McCallum UMass Amherst 39 39ng in from Chris Manning and Jason Ersner More Fancy Regular Expressions Special characters t tab v vertical tab n newline r carriage return Aliases shorthand d digits 09 D nondigits quot09 w alphabetic azAZ W nonalphabetic quotazAZ s whitespace tnrfv w alphabetic azAZ Examples d dollars 3 dollars 50 dollars 982 dollars woow food boo oodles Escape character is the general escape character eg is not a wildcard but matches a period if you want to use in a string it has to be escaped Andrew McCallum UMass Amherst including material from Chris Manning and Jason Ersn Yet More Fancy Regular Expressions Anchors AKA zero width characters They match positions in the text A beginning of line s end of line b word boundary ie location with w on one side but not on the other B Examples btheb thetogether Counters 1 12 3 mmmmmmmmmmmmmmmmmmmm st Even More Fancy Regular Expressions Grouping a goodbad movie He said it again and again Parens also indicate Registers saved contents bwb1 matches boohoo and baha but not boohaa The digit after the indicates which of multiple paren groups as ordered by when then were opened Grouping without the cost of register saving He went thisthat way mmmmmmmmmmmmmmmmmmmm st Extra Fancy Regular Expressions Nonconsuming tests Positive lookAHEAD 3921 Negative lookAHEAD lt Positive lookBEHIND lt1 Negative lookBEHIND Example ltHhe wed w1y mmmmmmmmmmmmmmmmmmmm st Yowza Regular Expressions MultiIine with comments etc FROM recompilequotquotquot AFrom s Pltusergtw Pltdomaingt S s quotquotquotreVERBOSE Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Anchor to start of line maybe some spaces 39user group of word characters the domain some non space characters finally a space character Oral Quiz Describe the strings these will accept aba ab Aaeiouaeiou1 bdiswb Handson With little strings reshow function from NLTK import re def reshowregexp string print recompileregexp reMsubquotglt0gtquot stringrstrip Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Handson Investigating corpora regexspy regexcountpy Corpora 200k words of Wall Street Journal articles 3 books by Jane Austin Several plays by William Shakespeare Several books by Mark Twain and various other text from Walt Whitman amp others I will make these available on the course Web site mmmmmmmmmmmmmmmmmmmm st ELIZA Weizenbaum 1966 User Men are all alike ELIZA IN WHAT WAY User They re always bugging us about something or other ELIZA CAN YOU THINK OF A SPECIFIC EXAMPLE User Well my boyfriend made me come here ELIZA YOUR BOYFRIEND MADE YOU COME HERE User He says I m depressed much of the time ELIZA I M SORRY TO HEAR THAT YOU ARE DEPRESSED Implemented with regular expression substitution s YOU ARE depressedsad I AM SORRY TO HEAR THAT YOU ARE 1 s always CAN YOU THINK OF A SPECIFIC EXAMPLE Andrew McCanuni UMass Amherst including material from Chris Manning and Jason Eisner Nondeterministic FSAs More than one outgoing transition on a a Input State b a l O 1 Q 1 Q 12 Q 3222 32r i t g itter 2 Q Q 3 3 Q Q Q Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Nondeterministic finitestate automata as Recognizers The problem When processing a string we might follow the wrong transition and reject the string when we should have accepted it One solution turn the NFA into a DFA See CMPSCI 250 Ubiquitous problem in this course How to efficiently search through various possible paths parses to find HOW do one that works the most likely one etc humans do this mmmmmmmmmmmmmmmmmmmm st Solutions Lookahead Peek ahead to help decide which path to take Parallelism At each choice take every path in parallel Backup At each choice point mark the input state If we fail go back and try another path Need a stack or queue of markers Marker Machine state Collection of current state amp markers Search state Depthfirst search or Breadthfirst search Smart heuristic search A See CMPSCI 383 mom MMMM l mmmmmmmmmmm st Artificial Intelligence RE FSA equivalence proof How would you do it ass Amherst g aterial from Chtis Manning and Jason Eisner Morphology The study of the subword units of meaning not to attach Making a word plural Examples If word is regular add 3 dog dogs If word ends in y change y to i and add 3 baby babies If word ends in x add es fox foxes Recognizing that foxes breaks down into morphemes fox and es called Morphological Parsing Parsing taking an input and producing some sort of structure for it Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Morphology briefly o morpheme minimal meaningbearing unit stem main morpheme of a word eg fox af xes add additional meanings eg es includes pre xes suf xes in xes circum xes eg un Iy concatenative morphology nonconcatenative inflection stemmorpheme in the same class as stem eg nouns plural s possessive s derivation stemmorpheme in different class eg Iy makes and adverb from an adjective Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Morphological Parsing with Finite State Transducers We want a system that given foxes will output a parse foxes or fox PL FSAs will take input but not produce output other than accept reject Solution Finite State Transducers FST A FST is a twotape automaton that recognizes or generates pairs of strings Example Finitestate Transducer FSTs can be used to transform a word sun ace form into morphemes or viceversa An entire lexicon can be encoded as a FST mmm LMAssAm mmmm an mmhmm FST transition table Input 3 096 3 GEE State hh aza pp yy iy s eze rr ss tt mmm LMAssAm mmmm an mmhmm Fragment of a lexicon in a FST Further Closure Properties of FSAs Regular languages are also closed under the following operations Reversal If L1 is regular so is the language consisting of the set of all reversals of strings in L1 Intersection if L1 and L2 are regular languages so is the language consisting of all strings that are in both L1 and L2 Difference If L1 and L2 are regular languages so is the language consisting of all strings in L1 that are not in L2 Complementation If L1 is a regular language so is the set of all possible strings that are not in L1 mmmmmmmmmmmmmmmmmmmm st Announcement Undergraduate CMPSSCI Meeting First Friday Curriculum Information Spring Events JobsCo opsResearch positions in and out of the Department Library Carrels And More Friday February 3 2005 330 500 PM CMPS 150151 Computer Science Building Refreshments will be served mmmmmmmmmmmmmmmmmm st Next class Tuesday Feb 7 Learning Python Variables operators conditionals iteration etc functions classes modules Gather statistics from Pythonized Penn Treebank Calculate statistics from 200k words of WSJ Implement a phrase structure grammar and generate sentences from it Install Python and bring your laptop with you mmmmmmmmmmmmmmmmmmmm st First Homework assigned today Essentially Write some regular expressions Run them on some corpora Write 1 page about your experience and findings Extra credit for creativity and interesting application Feel free to come do it in office hours Due next Thursday one week from today Don t wait until Wednesday to install Python Recommended schedule Idea by Saturday Codedtested by Monday Writeup by Wednesday Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Office Hours CS Building Rm 264 Friday 2 4pm Monday 1030am1pm Tuesday 1030am1pm Wednesday 1030am1pm Thursday 1030am1230pm If you can t make these times let me know mmmmmmmmmmmmmmmmmmmm st Aside Grammar Induction Also called Grammatical Inference Learning finitestate automata from many examples of strings in and out of the language httpwwwinfouclacbeDdupontodupontqramhtml Learning FSA and CFG structure from data ass Amherst 3 material from Chris Manning and Jason Eisner Thank you Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'