Part I PS 3 discussion of SPINS paperScenarioMessage Authentication Code (MAC)Cryptographic Hash ChainsµTesla [Perrig, et. al., 2002]Part II Viruses and Cryptography Principles and Practise of X-RAYING F. Perriot, P. Ferrie Virus Bulletin, Sept. 2004Lessons to LearnIntroductionHistorical Glimpse of MalwareVirus Infection (PE files)Armored VirusesDetecting Encrypted VirusesMore complicated DecryptionOther complicating methods of DecryptionX-RAY detectionWhy X-RAYX-RAY OverviewX-RAY ApproachesSlide 19Invariant ExampleHow to apply X-RAYingSlide 22W95/Perenast XOR cipherW32/Efish.A Substitution CipherX-RAY ProblemsW32/Magistr More Advanced X-RAY techniquesW32/MagistrHomophonic CipherW32/Efish.C Homophonic CipherW32/Efish.C Attacking PRNGSlide 31Questions?W32/Efish.A Scanning for duplicate bytesW32/Efish.A More Efficient ScanningOther X-RAY OptionsW32/BagifX-RAYing W32/BagifMultiple Layers of Encryption1Part IPS 3 discussion of SPINS paperCS 588February 22, [email protected] of small, low-powered devices with sensors and actuators, communicating wirelesslyHigh-power base station3Message Authentication Code (MAC)•Essentially a one-way hash function with a key, k•Used for message integrity and authentication–If m is altered to m’ then MAC(m) ≠ MAC(m’)–Only those that know k can create correct MAC4Cryptographic Hash Chainsf f fxK3 = f (x)K2 = f (f (x))K1 = f (f (f (x)))Initially store: K0 = f4(x)K1 = f3(x)verify f (K1) = f(f3(x)) = K0K2 = f2(x) verify f 2(K2) = f2(f2(x)) = K0timef is a one-way function: easy to calculate f(x), but difficult to invert f.Kj = f (Kj+1)5µTesla [Perrig, et. al., 2002]•Initially: sensor nodes know K0 = fn(x) base station knows x•Base station messages encrypted using K1 = fn-1(x) •Nodes store and time stamp messages, but cannot decrypt them (yet)•At time t1, base station broadcasts K1•Nodes verify f (K1) = K0•Nodes use K1 to decrypt earlier messages•Nodes and base station must have loosely synchronized clocks: cannot accept messages encrypted with K1 after K1 was revealed6Part IIViruses and CryptographyPrinciples and Practise of X-RAYINGF. Perriot, P. FerrieVirus Bulletin, Sept. 20047Lessons to Learn•Simple methods of encryption are prevalent•Viruses provide good applications of things you have seen in this class so far•Another security trade-off–Resources in sensornets–Speed in virus scanning8Introduction•Cohen’s definition of a virus–A program that is able to infect other programs by modifying them to include a possibly evolved copy of itselfWin32 PE file (.exe)virus9Historical Glimpse of Malware•“Elk Cloner”–1982: First PC virus–Displayed poem after 50th reset•Morris Worm–1988: A network program that attacked many different vulnerabilities to compromise machine•Blaster Worm–2004: Typical unpatched UVa CS machine compromised ~1 to 2 minutes10Virus Infection (PE files)•Easiest way is to prepend while overwriting host application beginning–Original application will not work•Can append into last section of PE file–Change entry point to beginning of the virus–Insert jmp at entry point to jump to the virus•Virus writers need something more to fight detection11Armored Viruses•Encryption–Thwarts disassembly–Can hide virus code; From W95/Mad.2736 Virus; mov src, destmov ecx, LENGTH_OF_VIRUSDecrypt:xor [edi], al ; key is in alinc ediloop Decrypt ; decrement ecx12Detecting Encrypted Viruses•Polymorphic viruses mutate decryptors•Static decryptors are easier to detect–Advanced polymorphic virus decryptors can still be statically detected•MtE has a constant, conditional backwards jump–Use wildcards in matching algorithm (e.g., 0x75 ?? 0xBF)13More complicated DecryptionDecryptorDecryptorDecryptorDecryptorDecryptor n14Other complicating methods of Decryption•Virus can use brute force to decrypt (no key needed)•Multiple layers of encryption•Key can slide, shift•Non-linear decryption (substitution)•Debuggers can modify decryption code (e.g., when decryption code is used as key)–Emulators may optimize decryption code15X-RAY detection•X-RAY–Attacking the encryption of the virus code•Virus encryption is usually weak•Only have a few seconds (make it fast)71 99 99 c4e8 00 00 5dPCIf XOR is only encryption used, how can we quickly determine key?16Why X-RAY•Can be cheaper (faster) than emulation•Emulator may not be able to emulate virus•Decryptors can be buggy•Works on ~50% of recent Win32 viruses17X-RAY Overview•Known-plaintext attack–Assume we know virus body (or variant)–Just need to know if the virus is really present•Sliding x-rayC 71 99 99 c4C 71 99 99 c4 2525C 71 99 99 c4 25…18X-RAY Approaches•Key Recovery–Guess key, then match ciphertext to some part of plaintext•Key validation–Recover several keys or pieces of keys–Do the keys match with respect to given encryption method?71 99 99 c4e8 00 00 5dPC^^^^99 99 99 9919X-RAY Approaches•Invariant scanning–Can reduce ciphertext and then compare against reduced plaintext–Very fast–Check Rc == Rp71 99 99 c4 e8 00 00 5dPC71 99 99 c4C >> 1e8 00 5dRc =C ^ (C>>1)e8 00 00 5dP >> 1e8 00 5dRp =P ^ (P>>1)20PC >> 1Rc =C ^ (C>>1)CPP >> 1Rp =P ^ (P>>1)Reduce CiphertextReduce PlaintextLabel each plaintext charactere8 00 00 5dp0 p1 p2 p3Invariant ExampleE8^99 00^99 00^99 5d^99p0^p1p1^p2 p2^p3p0 p1 p2 p3p0 p1 p2 p3p0^p1 p1^p2 p2^p3E8^99 00^99 00^99 5d^9921How to apply X-RAYing•Want to filter out files for X-RAYing–Use file geometry, positions and sizes of segments that characterize infected objects (e.g., virus decryptor, virus body, min/max size of decryptor, min infected file size, …)–Use frequency analysis•Encrypted bytes will have fairly random distribution•Look at ratio of zero bytes to non-zero bytes22How to apply X-RAYing•Choice of signatures–Look at segments from begin, middle, and end of last section•Length of signatures–Related to unicity distance–If a virus has a max key length of n bits, add n bits to plaintext signature–Want to avoid false positives•Misalignment (e.g., sub on 4 bytes instead of single bytes)23W95/PerenastXOR cipher•To encrypt:1. XOR dword (32 bits) of virus with a key2. Add encrypted value to key to produce next key3. Rotate key i times (later variants did this)• 1011 rotated 1 time to right: 11014. Jump to step 1 if virus not encrypted•To X-RAY:–XOR first 2 dwords of ciphertext with first 2 dwords of