New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Topics in Computer Science

by: Dr. Humberto Beier

Topics in Computer Science 22C 196

Marketplace > University of Iowa > ComputerScienence > 22C 196 > Topics in Computer Science
Dr. Humberto Beier
GPA 3.87

Eunjin Jung

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Eunjin Jung
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 26 page Class Notes was uploaded by Dr. Humberto Beier on Friday October 23, 2015. The Class Notes belongs to 22C 196 at University of Iowa taught by Eunjin Jung in Fall. Since its upload, it has received 13 views. For similar materials see /class/228049/22c-196-university-of-iowa in ComputerScienence at University of Iowa.


Reviews for Topics in Computer Science


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/23/15
Fast Dictionary Attack 220196 Security in Distributed System Dat Tien Nguyen Mar 29 2007 Quick notes 0 First I m very sorry for my English It you have any questions or t comments feel free to ask I Hopefully I won t make you fall asleep Db onanA ack De m on 0 l A me rhod used To break syslems by lesling all possible passwords beginning wi rh words rha r have a higher possibili ry of A being used quot from webopedia 7 Definition cont 0 2 An email spamming Technique in which the spammer sends out millions of emails with randomly generated addresses using combinations of letters 7 added to known domain names from webopedla Dic attack vs BF attack Dic Attack BF attack Tw possibilities Tw all which are most possibilities likely to succeed Need some Need no clues clues Maybe Successful unsuccessful eventually Egtltarnple 0 Break Uday39s password Whal diclionary should we lry English diclionaw India diclionaw His girl friends lisl Do you wanl lol Welnamese diclionaw Some nai39ve im provernenl Use a large diclionary or s more diclionaries W Use slring manipulalion in lhe diclionary password lls backward drowssap Numberleller replacement p4ssw0r Capilalizalion PasSwoRd Rainbow Table MarkovianDeterministic Finite Automata Dictionary Advanced improvement I 3 a 39 I My presentation 0 i Philippe Oechslin Making a faster Cryptanalytic Time Memory Trade Off N805 or 2 A Narayanan and V Shmatikov Fast t Dictionary Attacks on Passwords Using Time Space Tradeoff Fun facts about RaibowCrack Roinbovv Toble The problem 0 Given 0 fixed ploiniexf PO and The corresponding cipher rexf CO The encrypt function is S 0 Find The key k 6 N such ihoi Co SKPO The originol me rhod Try To generoie all possible cipheriexis by encrypting P0 with all N possible keys The cipheriexis ore orgonized in o choins so That only The first and The lost elements of o choin will be stored The originol me rhod cont The choins ore erected by using 0 reduction function R which creoies 0 key from o cipher iexi SmPo o Bra l gt Z A 1 Zn1 RSKPO is written as fllt f f 13914 ki1 4 ii2 439 The original method cont 0 m chains of length t are created Their first and last elements are stored Given a cipher text C Find the key 7 Generate a chain of Keys starting vmth WC and up to lengtht r if there is a Key in the chain that 39 matches a last Key from the table 7 r 4 C should be in this Key chain E 7 Using the first Key of the chain to 39 generate the whole chain and the expected Key is the one comesiust 739 before RtC Disadvantages o Chains starting at different Keys collide and mer e 9 reduce e number of distinct Keys covered by a table Finding a matching endpoint does not imply that the key in the table false alarm r The Key maybe in a chain tha e t aVet same endpoint but is not 1 in the table E 7 Z A r The chain containing Key is in the E table but merge vm h other chains 37 9 search through all chains that 7 have the same endpoint Until the Key is found 7 quot Some improvement 0 Using more tables to obtain a higher probability of success Each table has a different reduction function Given the probability of success of one table is Pbb e Using n table will increase the probability of success to t t139Ptabten Some improvement cont 0 Using distinguished points DP as endpoints 3 e Distinguished points are points for VthCt t a simpte criteria hotds true The ittSt ten bits are zero 7 Chains are generated untit distinguished point appears 7 Given a cipher text generate a chain untit we find a distinguished point and onty tootltit up in the memory Some improvement cont 0 Advantages of using distinguished endpoints 7 Loop detection 7 Merge detection Disadvantages e The length of chains are not fixed I Fatse atarm cases 7 e What happens ifthe chain starting waf ar with tht contains loop itself E g e What happens ifthe chains starting with RC contains the 39 chain in the table 3 39 7 Rainbow Table Use successive reduction function for each point in the chain k1 A L2 fZl kt Rainbow Table conT 0 Classical Table vs Rainbow Table Rainbow Table conT To look Up a key Apply RM To The cipherTeXT Look Up The resulT in The endpoinTs of Table If we don T find apply Rn2 and TM To see if The key was in The second lasT column So on and so forTh Rainbow Table conl Advanlages Reduce the number of table looku Classical lable l2 Rainbow lable MM 2 Merge deleclion No loops Don l have lo spend lime lo delecl and relecl loop chains Fixed lenglh chains False alarm cases Rainbow Table conl lmprovemenl To have higher success rate lncrease lhe size of lhe lable Using more lables People choose using more lables beca use Easy lo calculale lhe success rale39 7 One Table 80 7 Five Tables l 7 07085 09996 Easy lo calculale lhe of lables needed Hybrid MarkovianDFA diclionary Why use Markov models 0 The facl Thai The passwords are generaled by people which are unlikely To be uniformly dislribuled in The space of alphabel sequences Why use Mdrkov models 0 Morkov models ore commonly used in Ndlurol Longuoge Processing ll defines o probobilily dislribulion over sequences of symbols Used lo generole rondom 7 yel pronounceoble pwds in l LANL in The Idle l980s Very effeclive ol guessing 2 passwords generdled by r k users V Mdrkovidn filtering 0 Zero order Morkov model Eoch chorocler is generoled occording lo The underlying probobilily dislribulion ond inde endenll of lhe prev aus geneyroled choroclers l 39 erovx Markovian filtering cont First order model Each diagram ordered pair of characters is assigned a probability and each character is generated by looking at the previous character Pth2quot39xn VtximinXi Ixt i ni I Markovian dictionary Zero order dictionary a mewr 2 6 r4 First order dictionary 39DV Q 111721 n 112 1H11u211tzi Z 6 w Markovran dictionary cont 0 The models can drastically reduce the size of the plausible pwd space 7 Ex consider Becnaracter sequence 7 lt 8 85 means 85 percents of sequences are ignored Tne size if only l7 of tne key space Tne zerororder dictionary contalm 90 of tne dictionary Tne fllSerldel dictionary can even do better more tnan 95 Markovian dictionary cont 0 The distribution of letter frequencies used in Markovian filtering is languagespecific Two ways to deal with unknown languages Combine the keyspaces for two or more languages Come up with a distribution that works reasonably well for multiple languages Filtering using Finite Automaton o A search space that contains only alphabetic sequences is unlikely to have a goo coverage of the plausible pwd 7 Human often mix upperilovver characters and numbers 7 S stem re uires users to ut s ecial cl taracteg to their pvvdsp p 0 Even that the distribution of resulting pwds is not random 7 Numbers are likely in the end 7 Tbhe first character is more likely to e u r Pwd contains mostly lower chars Filtering using Finite Automaton Deterministic finite automata are ideal for expressing such properties Specify a set of common regular expression 7 All lower case 7 One upper case followed by all lower case Dictionary the set of sequences matching the Markomah filtering and acce ted by at least one DFA corresponding to the regular expression 77mm 7 iii HEmrur gt H and Filtering using Finite Autom The complete alphabet 7 Lower case chars 26 r Uppercase chars26 7 Special cham space hyphen uhaemcore period and comma 5 Total 67 chars The associated Keyspace of Sec ar sequences is 675 2 TO 5 9 impossible for BF attack Dimde this set into 4 categories a e lowercase A e u numerals s 7 special The input al habet of the automata consists otiust these 4 symbols dton Indexing Algorithms IA 0 With Markovian filtering andor DFA filtering we have a compressed dictionaryquot 0 We need to index the compressed dictionary An ef cient enumeration algorithm which takes index i as input and outputs the ilh element of the dictionaw Indexing Algorithrns cont 0 Some chonges Modi ed dictiondw Dug a lnl 7 l39 and mgrI 3 I Discretize the probd bility distribution on 7 n lnl 7 mm 2mm ugtlt log Vgtlt and A loge I r 7 Discretize the value of u to the nearest multiple of HO 51 ltu0 lS lorge the memory lS low t butthe dccurocyis low 05 well V IA tor Zero order Morkovidn dic Portiol dictionaries Dy gyg gryy 3 03 E D92 I a EFL aw For any string prefix 0 Partial Dic all sequences satisfies the Morkovion proper 7 7 Note that Dwell is weilde n g becouse llgtlt dBVle e I39IXer x l l rlxeonXl HXEBVle Ml IA for Zeroorder Markovian dic The recursive algorithm to compute the size of a partial dictionan 39Dmhreshozcz totaliength level currenueugtht parttatistzei currentitength tevet it tevet gt threshota return 0 it totatitength currentitength return i sum O for each char in atphabet sum sum parttatistzei currentitength riE tevetmuchar return sum IA for Zeroorder Markovian dic Function takes an index as input and returns the corresponding key geLkechunenUength index teven tr totaLtengtn cunenLtength tetutn foreach cnattn atpnaoet newjevet tevet rnuchav tooked uprtom pvecornputed array slze pavtioLsiZet currenLtengthH newjeve rsum stze gtt a 39t 39 refers tostrtng concatenation tetutn cnat t geLkevicurrenLtengthH indexrsurn newJevet stZe conttot cannot teacn nete print tndex tatget tnan kevspace stze extt 20 lAs for other dictionaries o Firstorder Markovian dictionaw r Partialisize2curilenprevichahlevel r Getlltey2curilenindexpre7charleel o DFA dictionary 7 ParitiaLsize3curlenstate r Getikeyl curilemndexstate 0 Any keyspace r Computeibins r Getikeymndex 0 Hybrid MarkovianDFA dictionaw 77 r Getikeysmndex W 0 Multiple keyspaces r Getlltey6lltl K2lltnindegtlt Possible optirnizations o The hybrid algorithm should use 50100 ta ble lookups a nd the table must fit into the cache 0 Getkey6 can be accelerated by pre computation Getkeyl can be speed up by reordering the characters so that the more frequent ones come rst This strategy works for Getkey2 as well Expemnenf Rainbow vs MarkovianDFA paper 2 142 real pwds from Passware Search space 6characier alphanumeric seq uences Length 6 Length 7 Length 8 A 0139 Others Concw on Rainbow Table MarkoviqnDFA Brute Force Dictionary aHack aHack Not language Language specific specific Has real Not yet application i 22 Fun facts about Rainbow Crack 0 All the configurations are done for a 666MHz CPU 256MB RAM 7 Nowadays With a 30GHZ CPU AGB RA t e time shouid be 5 times iess than their resu its 0 5 Rainbow tables Crack Windows hash function LM but it can be configured for other hash algorithms such as MD5 orSHAi 39 Fun facts about Rainbow Crack set length space usage rate cwptahalysis time precomp ute time days 18 Fun facts about Rainbow Crack Char set Alpha numeric AZO9 Plaintext length i7 Key space 80603140212 Disk usage 3 GB Success rate 09904 Mean cwpta nalysis 76276 s time 7 7 Table precompute 15 days 17 h r time Fun facts about Rainbow Crack Char set All alpha numeric symbol Plaintext length i7 Key Space 6823331935124 Disk usage 119 GB Success rate 09990 727 Mean cwpta na lysis time 1970106 s 3 mm Ta ble precompute time 2354 days 65 r 7 i Tables 52 TB 1TB is about the same amount of information as all of the books in a large library httpkbiuedudataackwhtml Supported Algorithms 13 CiscoPIX LanManager MD4 MDS NTLIVl MyISQLl2h3 IMySQLSHAthHlAl 39 Ha LMC a enge LMC a enge r NTLMChallenge MSCache Oracle 0 It takes them 3 years to generate all 1 tables 97 years for one computer 1 Successful rate 1 00 httpwwwrainbowcrack 7 on inecom H D References 0 i Philippe Oechslin Making a faster Cryptanalytic Time Memory Trade Off 2 A Narayanan and V Shmatikov Fast Dictionary Attacks on Passwords Using Time Space Tradeoff 3 DE Denning Cryptography and Data Security page 100 E Addison Wesley 1982 b r 2 25 Thcmk you for your offen rion Question if 1mm 26


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.