[SEC] Cryptography II

Cryptography II

Content

  • Symmetric Encryption
  • Block Ciphers
    • SP-Networks
    • The advanced Encryption Standard
  • Modes of Operation
  • Hash Functions
    • The Birthday Paradox
    • Message Authentication Codes

Symmetric Ciphers

Symmetric ciphers are divided into two categories:

  1. Stream cipher: each plaintext corresponds to one ciphertext
  2. Block cipher

Block Ciphers

  • Block ciphers use a key to encrypt a fixed-size block of plaintext into a fixed-size block of ciphertext
  • If you’re careful, you can convert between block and stream ciphers using modes of operation

SP-Networks

  • Claude Shannon suggested that all that was required for a strong cipher was repeated substitution and permutation
  • SP-Networks combine a substitution process with a permutation into a single round
  • Rounds are then repeated enough times to ensure the algorithm is secure

What does it mean by “permutation”?

It means that the ciphertext can be translated back to plaintext

  • Substitution Boxes - Add confusion by replacing values with other values using a lookup table
    enter image description here
  • Permutation Boxes - Add diffusion by moving values around from input to output
    enter image description here

A simple 8-bits SP-Network

enter image description here
enter image description here

  • This is a single round! One round isn’t enough!
    • Careful analysis of input changes and output changes can reveal the contents of the S-boxes
    • More rounds produces more diffusion
  • Replacing permutation with linear transformation is more effective
    • Each bit is the XOR combination of multiple S-box outputs
  • Large block size
    • An 8-bit block would be vulnerable to dictionary attacks, just pre-compute all possible blocks
    • Typically we see 128-bit and 256-bit block sizes
  • S-box design
    • “Psuedorandomness” of the result is compromised with poor S-box design

Key Mixing

  • The previous SP-Network didn’t use a key, we can add one using XOR:
    enter image description here

Advanced Encryption Standard

  • Superseded DES as a standard in 2002
  • A standard built around the Rijndael Algorithm
  • Rijndael is an SP-network with a 128-bit block size, and a key length of 128, 192 or 256-bits
  • Round count depends on key length
    • 10,12 or 14 cycles
  • AES is vastly superior to DES, which had a 64-bit block and 56 bit key
    enter image description here

AES Security

  • Is currently the standard algorithm for symmetric encryption, and is likely to remain that way
  • How good is it?
    • \(2^{128}\) keys, let’s say we get lucky and crack it at \(2^{127}\)
    • Long time, almost impossible

Block Cipher Modes

  • Most message don’t come in convenient 128-block lengths
  • We’ll need to run a block cipher repeatedly on consecutive blocks
  • Why not just use a stream cipher?
    • Historically stream ciphers have proven harder to implement
    • ChaCha20 is pretty good

Electronic Code Book(ECB)

  • Just encrypt each block one after another
    • Weak to redundant data divulging patterns

Cipher Block Chaining(CBC)

  • XOR the output of each cipher block with the next input
    • Not totally immune to the insertion of malicious blocks
      enter image description here

Counter Mode(CTR)

  • Encrypting a counter to produce a stream cipher
    • Can be parallelized
      enter image description here

Galois Counter Mode(GCM)

  • Extends counter mode to add authenticity
    • The sender definitely sent that message, and it hasn’t changed
  • Very similar to counter mode, but adds an authentication tag
    • The tag is calculated using multiplication in a Galois Finite field GF
    • Extremely parallelisable
    • Robust to message alteration

Hash Functions

enter image description here

Strong Hash Functions

  • The output must be indistinguishable from random noise
  • Bit changes must diffused through the entire output
  • Usually hash functions iteratively jumble blocks of a message after another
  • Once all the message is gone, we read the current hash
  • The initial hash is usually defined in the spec
  • For a hash function to be useful, we need it to have some important properties
    • One-way: Given h(M), we can’t calculate M easily
    • Weak collision resistance: Given M and h(M), we cannot find some M’ such that h(M) = h(M’)
    • Strong collision resistanceL We can’t find some message pair M \(\neq\) M’, such that h(M) = h(M’)

The birthday paradox

enter image description here

  • The output of the hash must be long enough to avoid a birthday attack
  • Given a hash function outputs n bit hashes
  • You will find a collision after about \(2^{n/2}\) random attempts

Some notable examples

enter image description here

Message Authentication Codes

  • Provide integrity and authenticity, not confidentiality
    • Protecting system files
    • Ensuring message haven’t been altered
  • Calculate a keyed hash of the message, then append this to the end of the message

HMAC

enter image description here

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文