Confidentiality an adversary cannot read our messages
analogy: locking and unlocking the message
alice uses the key to lock the message in a box alice sends the message ( locked in the box ) over the insecure channel eve sees the locked box, but cannot access the message without the key bob receives the message ( locked in the box ) and uses the key to unlock the message
alice uses the key to ENCRYPT the message, change the message into scrambled form alice sends the encrypted message over the insecure channel eve sees the encrypted message, but cannot figure out the original message without the key bob receives the encrypted message and uses the key to decrypt the message back to its original form
plaintext: original message ciphertext: encrypted message
integrity: an adversary cannot CHANGE our messages without being detected analogy: adding a seal on the message. alice uses the key to add a special seal on the message ( e.g. puts tape on the envelope ) alice sends the message and the seal over the insecure channel if mallory tampers with the message, shell break the seal without the key mallory cannot create her own seal
schemes provide integrity by adding a ta or signature on messages checksums are not ideal if you have a very powerful attacker alice uses the key to generate a tag and sends that along with the message
threat models: ciphertext only ( attackers have ciphertext, need to decrypt it ) known plaintext ( attackers know SOME ciphertext, and it’s corresponding plaintext, needs to decrypt some OTHER ciphertext ) chosen plaintext ( attackers can get any ciphertext they want, and need to decrypt some specific cyphertext ) ( e.g. if eve can trick alice into encrypting arbitrary messages of eve’s choice )
encryption schemes aim to provide confidentiality ( but not integrity or authentication ) symmetric key means that alice and bob share the same key
bitstring is a sequence of bits e.g. 101010101010101110
number representation
in computers all data is represented as bits names for groups of bits 8 bits = 1 byte 1 word = 4 bytes 1 word = 32 bits
4 bits can be represented as 1 hexadecimal digit ( base 16 )
the byte 0b11000110 can be written as 0xC6 in hex for clarity, we add 0b in front of bits and 0x in front of hex
a symmetric key encryption scheme has three algorithms keygen() → K : generate a key K Enc(K,M) → C Encrypt a plaintext M using the key K to produce ciphertext C another notation Ek (M) → C
what properties do we want for a symmetric encryption scheme? correctness: decrypting a ciphertext should result in the message that was originally encrypted Dec(K, Enc(K,M)) = M for all K ← KeyGen() and M Efficiency: encryption / decryption algorithms should be fast: >1 gbps on a standard computer.
recall our definition of confidentiality: “An adversary cannot read our messages” what if eve can read the first half of alice’s message, but not the second half? what if eve figures out that alice’s message starts with “Dear Bob”
a better definition of confidentiality: the ciphertext should not give the attacker any additional information about the plaintext
we design a game to test our definition: eve chooses two messages M0 and M1 of the same legnth alice chooses one message at random (Mb), encrypts it, and sends the ciphertext eve knows either M0 or M1 was sent, but doesnt know which eve reads the ciphertext and tries to guess which message was sent if the probabibility that eve correctly guesses which message was sent is at most 1/2, then the encryption scheme is confidential
consider a grading system in CCI for exams that has two possible outcomes: pass or fail then M0 and M1 can only be one of the two opetions the result after encryption is sent from the instructor to the CCI eve can read the ciphertext, let’s consider two encryption schemes enc(“pass” )or enc(“fail”) is a random 0 or 1 probabibility of eve guessing is 1/2, but this is random, so there is no correctness here, no way to decrypt
scheme #2 enc(“pass”) always starts with 00 enc(“fail”) always starts with 11 now you can get your message back, but eve can always know what things are, you have not actually encrypted anything