Thursday, November 2, 2017

NaMeCryReNoWriMo, day 2: AES and GCM

https://en.wikipedia.org/wiki/Rijndael_key_schedule
https://csrc.nist.gov/csrc/media/publications/fips/197/final/documents/fips-197.pdf

AES is a symmetric block cipher, one of the most widely used and most secure (if used properly).  Although quantum computers would weaken AES (approximately cutting the effective key size in half), it's still feasible to use by simply doubling the key size.  This is distinctly better than, say, RSA, which becomes unusable due to how much faster quantum computers could potentially be at breaking it.

Originally called Rijndael, which they should've stuck with because it's way cooler.

Multiple different versions for different key sizes.

Based on a substitution-permutation network, meaning it's a mix of exchanging bits for other bits (substitution) and shuffling bits into new orders (permutation).  Due to the simplicity of these operations it's extremely fast in both hardware and software.  Most processors these days have specific logical circuits for it (I think?) and you can buy ICs specifically dedicated to performing AES operations.

AES is performed in rounds.  10 for 128-bit, 12 for 192-bit, and 14 for 256-bit.  It's performed on each 128 bits of the message, and it's done with the bits arranged in a 4x4 matrix of bytes.  Upper-left is the first byte, then it counts down and then right, so it's in the order:

00, 04, 08, 12
01, 05, 09, 13
02, 06, 10, 14
03, 07, 11, 15

In total, the algorithm is something vaguely resembling the following:

-Generate the keys for the rounds, using a set formula and the key provided by the user.  In total AES needs n+1 128-bit keys, where n is the number of rounds, so these are generated from the 128/192/256-bit main key.
-xor each byte of the block being encrypted with one of the bytes of the first round key
-Now, do the following n-1 times:
--A lookup table is used to do some non-linear substitution.
--Rotate the lower three rows of the matrix a number of times.
--Perform an (invertible) linear transformation on the columns of the matrix
--XOR in the next round key
-For the last round, don't do the linear transformation:
--Substitution
--Rotate rows
--XOR round key
-Done!

There are attacks directly against AES that are faster than brute force, but none that appear to approach the level at which they could realistically be implemented.  However, modified versions of AES with a reduced number of rounds are potentially breakable, not than anyone uses AES with a reduced number of rounds and actually expects it to still be secure.

Most meaningful attacks against AES are side-channel attacks that don't attempt to break the cipher directly and instead rely on analyzing other information, such as how long it takes for an encryption to occur, what the resource usage of the machine performing the encryption is, and so on.

Modern intel processors have an AES throughput over 700MB/s

AES is a block cipher, so there are a number of different modes in which it can be used.  Based on glancing around online and talking with cryptographers, it sounds like GCM (Galois/counter mode) is the preferred mode.

??? Need to dive more into the details of the different transformations performed during the encryption process.

GCM (Galois/counter mode)

https://en.wikipedia.org/wiki/Galois/Counter_Mode
http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf

Mode of operation for symmetric key cryptographic block ciphers
efficient
authenticated encryption

Counter mode is just generating the keystream by encrypting successive values from a counter (1, 2, 3, etc).  Allows parallelization of both encryption and decryption and direct access to a specific part of the plaintext without decrypting the rest, because you can just increment the counter to whatever spot the block is at and generate the decryption key.
Although it sounds iffy to generate the keystream just from a basic counter like 1,2,3, as long as the cipher being used is secure, this is totally fine.  If there are security issues with it, that means that you're using a bad cipher, not that you should change the counter.

Galois refers to the authentication that's added on afterwards.
Based on Galois (finite) field multiplication.

Two functions, authenticated encryption and authenticated decryption

??? Need to study more math to understand how it works
??? What are the other modes of encrypting with symmetric block ciphers?

Galois fields (also called finite fields)

https://en.wikipedia.org/wiki/Finite_field
https://en.wikipedia.org/wiki/Field_(mathematics)

Field: A set of elements that has the operations multiplication, addition, division, and subtraction.  These operations must comply with:
-Associativity (addition and multiplication): a+(b+c)=(a+b)+c and a*(b*c)=(a*b)*c
-Commutativity (addition and multiplication): a+b=b+a and a*b=b*a
-Identity (addition and multiplication): There exist two elements 0 and 1 such that a+0=a and a*1=a
-Inverse (addition): For every element a, there exists an element denoted by -a such that a+(-a)=0
-Inverse (multiplication): For every element a apart from 0, there exists an element denoted by a^-1 or 1/a such that a*(1/a)=1
-Distributivity of multiplication over addition: a*(b+c)=(a*b)+(a*c)

Finite fields are (prepare to be shocked) fields that contain a (again, try not to fall off your chair) finite number of elements.  The number of elements is called the order of the field.  All finite fields contain p^k elements, where p is some prime number and k is a positive integer.  A common example is integers mod p, where p is a prime number.  As an example, let's look at integers mod 3: (0,1,2)
-Commutativity, associativity, identity, and distributivity are pretty clear so I'll skip them.
-Additive inverse?  Yep.  Inverses are (0, 2, 1), respectively. 0+0=0 is obvious.  2+1 = 3 = 0 mod 3 is a bit less clear if you aren't familiar with modular math.
-Multiplicative inverse?  Yep.  Inverses are (na, 2, 1), respectively.  0 has no multiplicative inverse, which is fine.  2*2 = 4 = 1 mod 3, and 1*1 = 1

??? Not a question, but wow do I need to refresh my college algebra.