1 Week 14 - Wednesday CS 113

2 Last time What did we talk about last time? RecursionSocial media and other technological impacts

3 Questions?

4 Final Project

5 Social Media

6 Arab Spring Starting in December 2010, a movement in the Middle East has ousted rulers of Egypt, Libya, Tunisia, and Yemen There have been massive protests throughout the region, and a civil war is still raging in Syria WikiLeaks exposed corruption and human rights abuses The Arab Social Media Report by the Dubai School of Government confirms that many activities were organized through Facebook and Twitter

7 Texting In 2009, one study showed that 286 million Americans (the vast majority of the population) sent billion texts per month, averaging 534 each In 2007, 700 billion texts were sent in China Half of them were spam The government monitors texts in China Europe texts heavily as well Most plans have unlimited free texting Finland is famous for its less-interactive society Finns have a stronger bias to talking on the phone and texting over real-life interactions Interactive TV shows where you text to play are popular The Prime Minister of Finland allegedly broke up with his girlfriend over text in 2006

8 Impacts of texting Texting allows unprecedented levels of communication A 2009 study showed that young adults who used “textisms” (lol, brb) in daily writing were worse formal writers But better informal ones! Texting reduces focus on life around us A 2008 head on train collision that killed 25 people was likely due to an engineer texting A 2009 VA Tech study suggests that texting while driving can increase chances of a crash by a factor of 23

9 Facebook Facebook is well over 10 years oldMore than 1 billion users, around 1/7 of the world’s population 50% of users log on every day The average user has 130 friends Even with a disappointing IPO, its market capitalization is over $340 billion It has become a central part of how many people communicate in the developed world What are its pros and cons?

10 Copyrights and OwnershipBlown to Bits Chapter 6

11 RIAA The Recording Industry Association of America (RIAA) is one of the leading organizations going after music piracy Between 2003 and 2008, the RIAA filed more than 26,000 lawsuits Even innocent people were asked to settle for an average of around $4000 Sometimes mistaken IP address identity Losing in court could result in a fine of $750 per song Innocence is a complicated question if you're using peer-to-peer file-sharing software which can automatically distribute files that are not permanently stored on your computer

12 Copyright infringementCopyright infringement in the US wasn't a crime until 1897 A maximum fine of $1000 In 1976, the penalties increased if the infringement was for commercial gain RIAA and MPAA pushed for these laws In 1997, the No Electronic Theft (NET) Act made it criminal to copy anything over $1000 in value, even if not for commercial gain

13 Napster Any corporate or university server risked lawsuits if it was distributing copyrighted material But Napster appeared in 1999 and changed everything Individuals had all the copyrighted material Napster was only a service that allowed the individuals to connect over the Internet and exchange files It claimed that it was not violating copyrights But the court said that it was guilty of secondary infringement and shut it down

14 Decentralized sharingA decentralized wave of applications came after Napster Grokster, Morpheus, Kazaa Unlike Napster, these programs had no central server They realized on decentralized networks of users The RIAA sued them, and they defended themselves the same way that Sony had in 1984 with VCRs If there are non-infringing uses possible, the creators are not liable for misuses In 2005, the RIAA won an appeal, making these file sharing products liable for any infringement

15 Technology outpacing the lawYou are not supposed to copy works (digital or otherwise) without explicit permission However, in order to play a movie or display an image, the bits on the hard drive or DVD must be copied into RAM Is that copying? A 1995 report from Congress said that it was So, if you buy a movie on DVD, you don't have the right to watch it In fact, Sony lawyers in 2007 still argue that you don't have the right to copy a CD you bought onto your computer

16 DRM Digital Rights Management (DRM) are technologies that make it so that copyrighted material can only be used by the purchaser Until the MPAA and RIAA can control your eyes and ears, DRM will only partially work There are always workarounds You can record the music coming out of your speakers There is a backlash against DRM particularly when it makes things harder for the consumer Many single player games must be connected to the Internet to run DRM is the technological approach to piracy, but a social change might be more effective

17 DMCA 1998's Digital Millenium Copyright Act (DMCA) made it illegal to create or possess technology designed to circumvent copyright protection You can't even publish instructions on how to circumvent copyrights It's a strange prohibition, since you can publish instructions on how to crack a safe or pick a lock But not on how to break the encryption in a DVD

18 Free as in beer There are pushes to provide copyright free forms of intellectual property Open source projects have created incredibly useful free software for everyone Linux is maybe the greatest example OpenOffice.org is a free alternative to the MS Office suite When you create any work, you automatically hold a copyright on it Creative Commons is a project that allows you to loosen that copyright and give everyone else rights to copy or even remix your work When you create work, you can mark it with different Creative Commons licenses that allow specific rights

19 Hash Functions Try to digest this

20 Where do passwords go? What magic happens when you type your password into… Windows or Unix to log on? Amazon.com to make a purchase? A Harry Potter fan site so that you can post on the forums? A genie travels back in time and checks to see what password you originally created!

21 Catch-22 Your computer needs to be able read the password file to check passwords But, even an administrator shouldn’t be able to read everyone’s passwords Hash functions to the rescue!

22 Hash functions Avalanching Preimage Resistance Collision ResistanceTake a long message and turn it into a short digest Lots of interesting properties (lots more than these): A small change in the message should make a big change in the digest Avalanching Given a digest, should be hard to find a message that would produce it Preimage Resistance Should be hard to find two messages that hash to the same digest (collision) Collision Resistance

23 Our solution Instead of storing actual passwords, Windows and Unix machines store the hash of the passwords When someone logs on, the operating system hashes the password and compares it to the stored version No one gets to see your original password! Not even a system administrator

24 Password file Below is an example of what a password file might be look like. Name Hash Ahmad IfW{6Soo Bai Li 853aE90f Carmen D390&063 Deepak CWc^Q3Ge Erica e[6s_N*X1

25 Cryptography

26 Cryptography "Secret writing"The art of encoding a message so that its meaning is hidden Cryptanalysis is breaking those codes

27 Encryption and decryptionEncryption is the process of taking a message and encoding it Decryption is the process of decoding the code back into a message A plaintext is a message before encryption A ciphertext is the message in encrypted form A key is an extra piece of information used in the encryption process

28 Notation A plaintext is M (sometimes P) A ciphertext is CThe encryption function E(x) takes M and converts it into C E(M) = C The decryption function D(x) takes C and converts it into M D(C) = M We sometimes specify encryption and decryption functions Ek(x) and Dk(x) specific to a key k

29 Attacks Cryptography is supposed to prevent people from reading certain messages Thus, we measure a cryptosystem based on its resistance to an adversary or attacker Kinds of attacks: Ciphertext only: Attacker only has access to an encrypted message, with a goal of decrypting it Known plaintext: Attacker has access to a plaintext and its matching ciphertext, with a goal of discovering the key Chosen plaintext: Attacker may ask to encrypt any plaintext, with a goal of discovering the key Others, less common

30 Shift ciphers Example: E("math is great") = "zngu vf terng"ROT13 Cipher (a shift cipher) E("math is great") = "zngu vf terng" Note that encryption = decryption for this cipher How hard is it to crack shift ciphers? A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

31 Substitution Cipher What about a random permutation of letters?For example: E("math is great") = "uiyp tq abziy" 26! possible permutations Hard to check every one A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

32 Frequency attack English language defeats usSome letters are used more frequently than others: ETAOINSHRDLU Longer texts will behave more and more consistently Make a histogram, break the cipher

33 Cipher text SPHB JLSP K ECGPCQFT GYBKYD, VFCMB C LSPGBYBG, VBKX KPG VBKYD, SOBY EKPD K RJKCPT KPG HJYCSJU OSMJEB SZ ZSYQSTTBP MSYB - VFCMB C PSGGBG, PBKYMD PKLLCPQ, UJGGBPMD TFBYB HKEB K TKLLCPQ, KU SZ USEB SPB QBPTMD YKLLCPQ, YKLLCPQ KT ED HFKEIBY GSSY. "'TCU USEB OCUCTSY," C EJTTBYBG, "TKLLCPQ KT ED HFKEIBY GSSY - SPMD TFCU KPG PSTFCPQ ESYB." KF, GCUTCPHTMD C YBEBEIBY CT VKU CP TFB IMBKX GBHBEIBY; KPG BKHF UBLKYKTB GDCPQ BEIBY VYSJQFT CTU QFSUT JLSP TFB ZMSSY. BKQBYMD C VCUFBG TFB ESYYSV; - OKCPMD C FKG USJQFT TS ISYYSV ZYSE ED ISSXU UJYHBKUB SZ USYYSV - USYYSV ZSY TFB MSUT MBPSYB - ZSY TFB YKYB KPG YKGCKPT EKCGBP VFSE TFB KPQBMU PKEB MBPSYB - PKEBMBUU FBYB ZSY BOBYESYB. KPG TFB UCMXBP, UKG, JPHBYTKCP YJUTMCPQ SZ BKHF LJYLMB HJYTKCP TFYCMMBG EB - ZCMMBG EB VCTF ZKPTKUTCH TBYYSYU PBOBY ZBMT IBZSYB; US TFKT PSV, TS UTCMM TFB IBKTCPQ SZ ED FBKYT, C UTSSG YBLBKTCPQ "'TCU USEB OCUCTBY BPTYBKTCPQ BPTYKPHB KT ED HFKEIBY GSSY - USEB MKTB OCUCTBY BPTYBKTCPQ BPTYKPHB KT ED HFKEIBY GSSY; - TFCU CT CU KPG PSTFCPQ ESYB."

34 Moving toward plain textSNPE YMSN A LIDNIUHO DTEATF, WHICE I MSNDETED, WEAK AND WEATF, SVET LANF A XYAINO AND PYTISYR VSCYLE SG GSTUSOOEN CSTE - WHICE I NSDDED, NEATCF NAMMINU, RYDDENCF OHETE PALE A OAMMINU, AR SG RSLE SNE UENOCF TAMMINU, TAMMINU AO LF PHALBET DSST. "'OIR RSLE VIRIOST," I LYOOETED, "OAMMINU AO LF PHALBET DSST - SNCF OHIR AND NSOHINU LSTE." AH, DIROINPOCF I TELELBET IO WAR IN OHE BCEAK DEPELBET; AND EAPH REMATAOE DFINU ELBET WTSYUHO IOR UHSRO YMSN OHE GCSST. EAUETCF I WIRHED OHE LSTTSW; - VAINCF I HAD RSYUHO OS BSTTSW GTSL LF BSSKR RYTPEARE SG RSTTSW - RSTTSW GST OHE CSRO CENSTE - GST OHE TATE AND TADIANO LAIDEN WHSL OHE ANUECR NALE CENSTE - NALECERR HETE GST EVETLSTE. AND OHE RICKEN, RAD, YNPETOAIN TYROCINU SG EAPH MYTMCE PYTOAIN OHTICCED LE - GICCED LE WIOH GANOAROIP OETTSTR NEVET GECO BEGSTE; RS OHAO NSW, OS ROICC OHE BEAOINU SG LF HEATO, I ROSSD TEMEAOINU "'OIR RSLE VIRIOET ENOTEAOINU ENOTANPE AO LF PHALBET DSST - RSLE CAOE VIRIOET ENOTEAOINU ENOTANPE AO LF PHALBET DSST; - OHIR IO IR AND NSOHINU LSTE."

35 Real plain text ONCE UPON A MIDNIGHT DREARY, WHILE I PONDERED, WEAK AND WEARY, OVER MANY A QUAINT AND CURIOUS VOLUME OF FORGOTTEN LORE - WHILE I NODDED, NEARLY NAPPING, SUDDENLY THERE CAME A TAPPING, AS OF SOME ONE GENTLY RAPPING, RAPPING AT MY CHAMBER DOOR. "'TIS SOME VISITOR," I MUTTERED, "TAPPING AT MY CHAMBER DOOR - ONLY THIS AND NOTHING MORE." AH, DISTINCTLY I REMEMBER IT WAS IN THE BLEAK DECEMBER; AND EACH SEPARATE DYING EMBER WROUGHT ITS GHOST UPON THE FLOOR. EAGERLY I WISHED THE MORROW; - VAINLY I HAD SOUGHT TO BORROW FROM MY BOOKS SURCEASE OF SORROW - SORROW FOR THE LOST LENORE - FOR THE RARE AND RADIANT MAIDEN WHOM THE ANGELS NAME LENORE - NAMELESS HERE FOR EVERMORE. AND THE SILKEN, SAD, UNCERTAIN RUSTLING OF EACH PURPLE CURTAIN THRILLED ME - FILLED ME WITH FANTASTIC TERRORS NEVER FELT BEFORE; SO THAT NOW, TO STILL THE BEATING OF MY HEART, I STOOD REPEATING "'TIS SOME VISITER ENTREATING ENTRANCE AT MY CHAMBER DOOR - SOME LATE VISITER ENTREATING ENTRANCE AT MY CHAMBER DOOR; - THIS IT IS AND NOTHING MORE."

36 One time pad What if we had some really long key that allowed us to change each character in the plaintext in some secret way? Use another message as a key and add them together: T H I S M E A G C O L Y K Q Z W P

37 Problems with one time padPicking a truly random key to use for encryption is necessary The key must be as long as the message If you can send a key that long safely, why not send the message the same way? Like other symmetric key cryptography, one difficulty is agreeing on the key ahead of time

38 Modern encryption There are a few modern encryption standardsThe Data Encryption Standard (DES) was commonly used until the 1990s when its short key size of 56 bits became relatively easy to brute force The Advanced Encryption Standard (AES) is commonly used now Has key sizes of 128, 192, and 256 bits AES is one of the most secure ways to send a message But sender and receiver have to share the key ahead of time!

39 Now that you mention it…How does logging on to Amazon.com work? Everything that gets sent across the Internet hops from computer to computer Anyone can read it No wonder there’s so much credit card fraud

40 What about the gold lock?Isn’t there that gold lock in the corner of Internet Explorer and Firefox? Doesn’t that give us some security? Yes! But, what does that lock do? How does it send your password or credit card number to Amazon.com secretly? Answer: Magic!

41 What kind of magic? We need a way to encrypt a message so that anyone can encrypt it, but only the intended recipient can decrypt it Such systems are called public key cryptography If we could easily encrypt something that only Amazon.com could read, we could send our credit card number that way To do it, we need some math…

42 Review of modular arithmeticModulo operator takes the remainder Two numbers are said to be congruent modulo n if they have the same remainder when divided by n For example, 39  3 (mod 12) Addition, subtraction, and multiplication: [(a mod n) + (b mod n)] mod n = (a + b) mod n [(a mod n) – (b mod n)] mod n = (a – b) mod n [(a mod n) x (b mod n)] mod n = (a x b) mod n

43 Divided and conquered We can’t actually divideInstead, we have to find the multiplicative inverse The multiplicative inverse of x exists if and only if x is relatively prime to n 13 ∙ 5  65  1 (mod 16) So, 13 and 5 are multiplicative inverses mod 16 But, 2, 4, 6, 8, 10, and 12 do not have multiplicative inverses mod 16

44 RSA algorithm Named for Rivest, Shamir, and AdlemanTake a message M converted to an integer It's not too hard to turn text into an integer Everything inside a computer is a number anyway Create an encrypted version C as follows: C = Me mod n Decrypt C back into M as follows: M = Cd mod n = (Me)d mod n = Med mod n

45 Message to be encryptedThe pieces Term Details Source M Message to be encrypted Sender C Encrypted message Computed by sender n Modulus, n = pq Known by everyone p Prime number Known by receiver q e Encryption exponent d Decryption exponent Computed by receiver (n) Totient of n

46 How it works To encrypt: C = Me mod ne is often 3, but is always publically known To decrypt: M = Cd mod n = Med mod n We get d by finding the multiplicative inverse of e mod (n) So, ed  1 (mod (n))

47 RSA example M = 26 p = 17, q = 11, n = 187, e = 3 C = M3 mod 187 = 185(n) = (p – 1)(q – 1) = 160 d = e-1 mod 160 = 107 Cd = mod 187 = 26 If you think you can trust me

48 Why it’s safe You can’t compute the multiplicative inverse of e mod (n) unless you know what (n) is If you know p and q, finding (n) is easy Finding (n) is equivalent to finding p and q by factoring n No one knows an efficient way to factor a large composite number Brute force (even done cleverly) takes millions of years or more for big numbers

49 Why it isn’t safe Advances in number theory could make the algorithm obsolete All public key cryptography would come crashing down Alternatively, quantum computers could make it easy to factor large composites Right now scientists claim to have successfully factored the number 15 on a quantum computer

50 Quiz

51 Upcoming

52 Next time… More on computer security Chapter 5 of Blown to Bits Lab 14

53 Reminders Keep working on the Final ProjectRead Blown to Bits Chapter 5