Computer Systems Security Lecture 3 Basic Cryptography II
› Modern Symmetric Ciphers
– Stream Ciphers › ChaCha20
Copyright By PowCoder代写 加微信 powcoder
– Block Ciphers
› Feistel Cipher Structure
› Data Encryption Standard (DES) › Modes of Operations
Modern Symmetric Ciphers
› Modern symmetric ciphers deal with information in binary bit level.
– 10010011111011101…
› Two major approaches – Stream Ciphers
– Block Ciphers
Stream Ciphers
› Stream ciphers process messages a bit at a time when en/decrypting.
Stream Ciphers
› Secret key length: 128 bits, 256 bits, etc.
› Maximum plaintext length: usually can be arbitrarily long. › Synchronous vs Asynchronous
› Security
– The secret key cannot be derived.
– The subsequent segment of the keystream cannot be deduced.
Example – ChaCha20 in TLS 1.3
› Developed by D. J. Bernstein in 2008
– A refinement of Salsa20
› Use a 256-bit key
– Divided into to 8 * 32-bit words
› Other inputs:
– 4 words: constants
– 2 words: a nonce
– 2 words: a block counter
› The input is packaged as a 512-bit block
block[0]: “expa” block[1]: “nd 3” block[2]: “2-by” block[3]: “te k” block[4]: key[0] block[5]: key[1] block[6]: key[2] block[7]: key[3]
block[8]: key[4] block[9]: key[5] block[10]: key[6] block[11]: key[7] block[12]: counter[0] block[13]: counter[1] block[14]: nonce[0] block[15]: nonce[1]
› 20 rounds
– Each round applies the following “quarter-round” function, four times, to a different set of words each time
a += b; d ^= a; d <<<= 16; c += d; b ^= c; b <<<= 12; a += b; d ^= a; d <<<= 8; c += d; b ^= c; b <<<= 7;
for (int i = 0; i < 10; i++) { // 20 rounds, 2 rounds per loop. QUARTERROUND(block[0], block[4], block[8], block[12]); // column 0 QUARTERROUND(block[1], block[5], block[9], block[13]); // column 1 QUARTERROUND(block[2], block[6], block[10], block[14]); // column 2 QUARTERROUND(block[3], block[7], block[11], block[15]); // column 3 QUARTERROUND(block[0], block[5], block[10], block[15]); // diagonal 1 QUARTERROUND(block[1], block[6], block[11], block[12]); // diagonal 2 QUARTERROUND(block[2], block[7], block[8], block[13]); // diagonal 3 QUARTERROUND(block[3], block[4], block[9], block[14]); // diagonal 4
› The output words (512 bits) are converted to bytes and XORed with the plaintext to produce ciphertext
ciphertext = plaintext XOR chacha20(key, nonce)
Design Consideration for Stream Ciphers
1. A deterministic function that produces a stream of bits that eventually repeats. The encryption sequence should have a large period.
– In ChaCha20, the 2-word counter allows a large period
2. The keystream should approximate the properties of a true random number stream as close as possible.
– In ChaCha20, the quarter-round functions allows a high diffusion.
3. The key should be long enough to resist brute-force attack.
– In ChaCha20, it is 256-bits.
Block Ciphers
Plaintext block
E.g., 64 bits
Ciphertext block
E.g., 64 bits
Encryption E
› A method of encrypting text in which a key and algorithm are applied to blocks of data
– Message is broken into fixed sized blocks. – It is encrypted, one block at a time.
Choice of Block Size
› Small block size may be insecure
– Same plaintext block always produces the same ciphertext block.
– 8-bit block size has only 256 values Use frequency analysis to break it!
› In practice, encryption algorithms are designed to ensure that all subsequent blocks result in ciphertext that does not match that of the previous encryption(s) (More to be discussed later).
Some extra information
Encryption E
Encryption E
Some extra information
Block Cipher Principles
› Most symmetric block ciphers are based on a Feistel Cipher Structure.
– To decrypt ciphertext to recover messages efficiently.
› Block ciphers look like a large substitution.
– E.g., a table of 264 plaintext-to-ciphertext entries for a 64-bit block
› Create the ciphertext from smaller building blocks – Using idea of “Product Cipher” mentioned in Lecture 1
& Substitution-Permutation Ciphers
› In 1949 introduced idea of substitution- permutation (S-P) networks
› These form the basis of modern block ciphers
› S-P networks are based on the two primitive cryptographic operations:
– substitution (S-box) – permutation (P-box)
› Provide confusion and diffusion of message
Confusion and Diffusion
› Cipher needs to completely obscure statistical properties of original message.
– A one-time pad does this perfectly
› More practically Shannon suggested combining elements
– Diffusion
› dissipates statistical structure of plaintext over bulk of ciphertext
– Confusion
› makes relationship between ciphertext and key as complex as possible
› In other words,
– Every bit in the ciphertext should depend on as many bits as possible in the plaintext and the key.
Feistel Cipher Structure
› (of IBM) devised the Feistel cipher › Partitions input block into two halves
– process through multiple rounds which perform a substitution on left data half based on round function of right half & subkey then have permutation swapping halves
› Implements Shannon’s substitution-permutation network concept
Feistel Cipher Design Principles
› Block size
– increasing size improves security, but slows cipher
› Key size
– increasing size improves security, makes exhaustive key searching harder, but may slow cipher
› Number of rounds
– increasing number improves security, but slows cipher
› Subkey generation
– greater complexity can make analysis harder, but slows cipher
› Round function
– greater complexity can make analysis harder, but slows cipher
› Fast software en/decryption & ease of analysis – are more recent concerns for practical use and testing
Data Encryption Standard (DES)
› A block cipher
› Both plaintext and ciphertext – 64 bits
– 64 bits (56-bit effective key)
› Encrypts by series of substitution and transpositions (or permutations)
Input of DES
– Need to be broken into 64-bit blocks; add pad at the last message if necessary.
– E.g.,X=(35077F10AB12FC65)HEX
› Secret key
– Any string of 64-bit long including 8 parity bits.
– 1 parity bit in each 8-bit byte of the key may be utilized for error detection in
key generation, distribution, and storage.
– K = (k1...k7k8...k15k16k17...k24...k32...k40...k48...k56...k64)
– The parity bits k8, k16, k24, k32, k40, k48, k56, k64 help ensure that each byte is of odd parity
DES Encryption Diagram
64-bit plaintext
Initial permutation
Iteration 1
Iteration 2
16 sub-keys, generated
from the 56-bit key
Iteration 16
32-bit Swap
Inverse permutation
64-bit ciphertext
DES Flow (High Level View)
› DES operates on 64-bit blocks of plaintext. After an initial permutation the block is broken into right half (R) and left half (L), each being 32 bits long.
› There are 16 rounds of identical operations, call function F, in which data are combined with 16 keys of 48 bits, one for each round.
– Each 48-bit key is derived from the 56-bit effective key
› After the 16th round, L and R are joined, and a final permutation (the inverse of the initial permutation) finishes the algorithm.
› DES’s operation is very repetitive
– readily implementable in hardware, as well as software.
DES Round Structure
› Uses two 32-bit L & R halves
› As for any Feistel cipher, it can describe as:
Ri = Li–1 XOR F(Ri–1, Ki)
Li-1 F(Ri-1, Ki)
DES Round Structure
› The function F takes 32-bit R and 48-bit subkey, and – expands R to 48 bits using perm E
– adds to subkey
– passes through 8 S-boxes to get a 32-bit result
– finally permutes this using 32-bit perm P
› F can be regarded as a generator of a pseudo-random key stream, which is used for “encrypting” the left half.
Li-1 F(Ri-1, Ki)
DES Round Structure
DES Module Operations
› Permutation boxes
– Specific boxes used in DES includes: PC1 and PC2 for sub-key generation; initial permutation (IP), IP-1, E-box and P-box
› Substitution boxes
– 8 specific S-boxes are used in DES
› Modulo 2 addition (XOR)
– Addition in binary form; used in function F
› 32-bit registers
– Use only to store data. In the key generator, two shift registers are used to cyclically shift the data used in key generation.
Permutation
› Permutation
– size of input and output are the same;
› E.g., IP, IP-1 and P-box
› Expansion
– size of output is greater than input stream, some input bits appear at two places in output
› E.g., E-box
Input Output
P-box contents = 2 6 4 8 7 5 9 3 1
Input Output
E-box contents = 2 6 4 1 7 5 7 3 1
Substitution
› Substitution boxes (S-boxes), provide a substitution code – i.e., a table mapping between input and output
› Each S-box stores a different set of 64 hexadecimal numbers in a matrix of 164;.
– 8 S-boxes in total, each accepts a 6-bit input and returns a 4-bit output.
› Consider a 48-bit input stream, first 6 bits input will be input to the first S box, next 6 bits will be for the second S box, and so on.
› Also known as a compression box
DES – Decryption
› Decryption processes are almost the same except that – 16 sub-keys are entered in reverse order
Sub-Key Generations
› Given a secret key K of 64-bit long (includes 8 parity bits) by the sender
– K = [0101 1000 0001 1111 1011 1100 1001 0100 1101 0011 1010 0100 0101 0010 1110 1010]
– Foreachbyte,the8th bitis1ifthenumberof1sinthefirst7 bits is even, 0 otherwise.
› Odd parity
› Objective: use these 56 bits to generate a different 48-bit sub-key for each round of DES
› Further Reading: https://page.math.tu- berlin.de/~kant/teaching/hess/krypto-ws2006/des.htm
Security of DES
› To attack DES, let us try exhaustive key search (a.k.a. brute force attack)
– For a key of n bits, the total number of possible keys (or the entire key space) is 2n.
– An average of half the combinations should be tried in order to find the key, i.e., 2n-1.
– Nowadays the minimum key size of any symmetric encryption schemes is 80 bits to make it impossible for a brute force attack.
› To give a better security margin, the key size is recommended to be at least 128 bits.
Brute force Attack Against DES
› Known-Plaintext Attack
– Given a plaintext x and corresponding ciphertext y, every possible key would be tested until a key K is found such that
E(K, x) = y
– Note: there may be more than one such key K.
– Total number of keys = 256 7.2 1016 keys
– Assume at the speed of 106 encryptions per second, it would need more than 1000 years to break DES, on average.
Brute force Attack Against DES
› In 2016, the Electronic Frontier Foundation (EFF) raised the level of honesty in crypto politics by revealing that the Data Encryption Standard (DES) is insecure!
– It now took a single machine less than 3 days to crack DES cipher
– Read the details
› https://www.eff.org/press/releases/eff-des-cracker-machine-brings- honesty-crypto-debate
Vulnerabilities
› In 2016, it is found that the DES and Triple DES ciphers have a birthday bound of approximately four billion blocks
– which makes it easier for remote attackers to obtain cleartext data via a birthday attack against a long-duration encrypted session
› Further readings:
– The “Sweet32” attack: https://sweet32.info/
– CVE-2016-2183: https://nvd.nist.gov/vuln/detail/CVE-2016- 2183
What Should We Use Today?
› AES (Advanced Encryption Standard) – designed by Rijmen-Daemen in Belgium – Published in 2001
– has 128/192/256-bit keys, 128-bit data
› Further reading:
› Supported by in SSL/TLS (HTTPS)
– You may check if your browser support AES › https://www.howsmyssl.com/
https://csrc.nist.gov/publications/detail/fips/197/final
More on Block Cipher
A Block Cipher takes as input a plaintext of one block and output a ciphertext of one block. It is very often viewed as a pseudorandom permutation.
What should we do if the message length is more than 1 block?
What should we do if the message length is not a multiple of the block? E.g., if the plaintext is 129 bits, how can we
encrypt it with DES?
Modes of Operations
› Different modes of operations have been developed to handle the first issue
– Electronic codebook mode – Cipher block chaining mode – Cipher feedback mode
– Output feedback mode
– Counter mode
Electronic Codebook (ECB) Mode
› The basic mode of operation
– Each block of the message is encrypted separately.
Decryption in ECB Mode
Cipher Block Chaining (CBC) Mode
CBC Mode Decryption
Cipher Feedback (CFB) Mode
› Similar to CBC mode
CFB Mode Decryption
OFB Mode Encryption
OFB Mode Decryption
› Home Exercise: Draw the diagram.
Counter (CTR) Mode
CTR Mode Decryption
› Another issue of block cipher is that the last block of plaintext is, in general, a partial block of size u bits, this being less than the block size of the cipher.
› One needs to apply a padding rule to allow the last block to be suitably encrypted.
› Padding means adding a fixed pattern of 1 and 0s to the end of the block, which can be easily distinguished from the actual information.
Padding Example
› Add a string 1000...0 to fill out the last block to the correct length.
› For decryption, take the plaintext as being read back to the least significant bit which is 1.
– may have to add a new block if the plaintext is already a multiple of the block size to avoid ambiguity
› For CTR mode one can simply use only the most significant u bits of the last output block for the XOR operation.
– This reveals the length of the message though, which is not always desirable.
› Modern Symmetric Ciphers
– Stream Ciphers › ChaCha20
– Block Ciphers
› Feistel Cipher Structure
› Data Encryption Standard (DES) › Modes of Operations
› (2017). Cryptography and Network Security: Principles and Practice (7th ed.). Pearson.
– Chapter 4
› (2005). Introduction to Computer Security. .
– Chapter 8.2.3 and 10.2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com