15-441 Computer NetworkingSecurity ThreatsThree Levels of DefensePrivate Key AuthenticationReplay AttackPreventing Replay AttacksPrivate Key CryptosystemsOne Time PadSimple Permutation CipherData Encryption Standard (DES)OverviewInitializationTerminationA RoundPermutations and SubstitutionsKey TransformationE-Box (Expansion Box)S-Box (Substitution Box)P-Box (Permutation Box)Block Cipher ModesElectronic Code Book (ECB) ModeCipher Block Chaining (CBC) ModeCipher Feedback Mode (CFB) ModeOutput Feedback Mode (OFB) ModeOther Ciphers15-441 Computer NetworkingLecture 21: Security and CryptographyThanks to various folks from 15-441, semester’s past and others2Security Threats•Impersonation•Pretend to be someone else to gain access to information or services•Insecrecy•Eavesdrop on data over network•Corruption•Modify data over network•Repudiation•Deny sending a message•Break-ins•Take advantage of implementation bugs•Denial of Service•Flood resource to deny use from legitimate users3Three Levels of Defense•Firewalls•Filtering “dangerous” traffic at a middle point in the network•Covered next lecture•Network level security (e.g. IPsec)•Host-to-host encryption and authentication•Can provide security without application knowledge•Cannot always protect applications from each other•Application level security•True end-to-end security•Requires extra effort per application•Libraries help, like SSL/TLS4Private Key Authentication•Alice wants to talk to Bob•Needs to convince him of her identity•Both have private key k•Naive scheme Alice Bob•Vulnerability?“I am Alice”, x, E(x, k)5Replay Attack•Eve can listen in and impersonate Alice later Alice Bob Eve“I am Alice”, x, E(x, k)“I am Alice”, x, E(x)6Preventing Replay Attacks•Bob can issue a challenge phrase to Alice Alice Bob“I am Alice”E(x, k)x7Private Key Cryptosystems•Finite message domain M, key domain K•Key k K•Known by all parties•Must be secret•Encrypt: E: M × K M•Plaintext mp to ciphertext mc as mc = E(mp, k)•Decrypt: D: M × K K•mp = D(mc, k) = D(E(mp, k), k)•Cryptographic security•Given mc, hard to determine mp or k•Given mc and mp, hard to determine k8One Time Pad•Messages•n-bit strings [b1,…,bn]•Keys•Random n-bit strings [k1,…,kn]•Encryption/Decryption•c = E(b, k) = b k = [b1 k1, …, bn kn] denotes exclusive or•b = D(b, k) = c k = b k k = b [1, …, 1] = b•Properties•Provably unbreakable if used properly•Keys must be truly random•Must not be used more than once•Key same size as message9Simple Permutation Cipher•Messages•n-bit strings [b1,…,bn]•Keys•Permutation of n•Let = -1•Encryption/Decryption•E([b1,…,bn], ) = [b (1),…,b (n)]•D([b1,…,bn], ) = [b (1),…,b (n)]•Properties•Cryptanalysis possible•Only small part of plaintext and key used for each part of ciphertextData Encryption Standard (DES)11OverviewInitializationTerminationRoundRound…RoundPlaintextCyphertextKeyKeyKeyKey16 rounds of permutations and substitutionDES is a 64-bit block cipher. Both the plaintext and ciphertext are 64 bits wide.The key is 64-bits wide, but every eighth bit is a parity bit yielding a 54-bit key.12InitializationPlaintextInitial PermutationRight HalfLeft HalfRoundKey13TerminationCiphertextReverse Initial PermutationRight HalfLeft HalfRoundKey14A RoundRight HalfLeft HalfTransformed Key (48-bit)Permutations and substitutionXORLeft HalfRight Half15Permutations and SubstitutionsRight HalfTransformed Key (48-bit)S-Box SubstitutionP-Box PermutationXORE-Box Permutation8 S-Boxes are used by the P-Box16Key Transformation64-bit KeyRemove parity bit56-bit Keysplit28-bit left semikey28-bit right semikeyshiftshift28-bit shifted left semi-key28-bit shifted right semi-keyCompression Permutation48-bit semi-key17E-Box (Expansion Box)1 2 3 4 5 6 7 8 .. .. .. .. 29 30 31 32 1 2 3 4 5 6 7 8 9 10 11 .. .. .. .. 44 45 46 47 4832481118S-Box (Substitution Box)There are 8 different S-Boxes, each of which provides a different 6:4 mapping. Where’d they come from? Some combination of IBM and NSA.The mappings are based on cryptanalysis and are ostensibly free of weaknesses, back-doors, &c.19P-Box (Permutation Box)S-Box 1S-Box 2 S-Box 3 S-Box 4 S-Box 5S-Box 6 S-Box 7 S-Box 848-bit input32-bit output20Block Cipher Modes•“How do we break a message down into blocks for encryption by DES or another block cipher?”21Electronic Code Book (ECB) ModeBlock 1 Block 2 Block 3 Block 4 Block 5 … E(block)E(block) E(block)E(block)E(block)E(block)Block 1 Block 2 Block 3 Block 4 Block 5 … PlaintextCiphertext• Pad last block, if necessaryBlock Encryption22Cipher Block Chaining (CBC) ModeRandom Block 1 Block 2 Block 3 Block 4 … E(block) E(block)E(block)E(block)E(block)Block 2 Block 3 Block 4 Block 5 … PlaintextCiphertext• Pad last block, if necessary• Random Block called IV can be sent in plain text. Not a secret – just prevents a codebook. Often times a timestamp. XOR XOR XOR XOR XORBlock Encryption23Leftmost Cipher Feedback Mode (CFB) Mode C I-6 C I-5 C I-4 C I-3 C I-2 C I-1 Shift Register (1 Block wide)Next unit of CiphertextE(register)1 unit is 1/N blockBlock Encryption Encrypted RegisterXORNext unit of PlaintextAfter each unit, shift input register and insert the most recently generated unit of ciphertextoutput24Leftmost Output Feedback Mode (OFB) Mode C I-6 C I-5 C I-4 C I-3 C I-2 C I-1 Shift Register (1 Block wide)Next unit of CiphertextE(register)1 unit is 1/N blockBlock Encryption Encrypted RegisterXORNext unit of PlaintextAfter each unit, shift input register and insert the leftmost unit of the encrypted register.output25Other Ciphers•Triple-DES•DES three times•mc = E(D(E(mp, k1), k2, k3)•Effectively 112 bits•Three times as slow as DES•Blowfish•Developed by Bruce Schneier circa 1993•Variable key size from 32 to 448 bits•Very fast on large general purpose CPUs (modern PCs)•Not very easy to implement in small hardware•Advanced Encryption Standard (AES)•Selected by NIST as replacement for DES in 2001•Uses the Rijndael algorithm•Keys of 128, 192
View Full Document
Unlocking...