Cryptography course - AES

AES is a subs-perm network not Feistel (in which half the bits remain unchanged in every round). Here all bits change in every round.

Intel Westmere and AMD Bulldozer architectures have special instructions for AES.

AES implementation will have shortest code when tables are not pre computed and vice versa.

So, to transmit AES implementation to browser, just the code is sent and browser pre computes the table.

On AES-128 best known attacks are only 4 times faster than exhaustive search - i.e. 2^126. AES-256 though can be broken in 2^99.

Can we build a PRF from a PRG? Though the ultimate goal is to build PRP.

Answer is yes. It's called GGM PRF.

If we have a PRF, we can plug it in Luby-Rackoff theorem which says that PRF + 3 round Fiestel will give us PRP.

But constructing a PRP like this is very slow in practice, so it's not used.

Any secure PRP is a secure PRF if |X| is sufficiently large. For e.g. |X| for AES is 2^128. 

Now,

How to correctly encrypt long messages with block ciphers?

If two parts of the message are same, and the block cipher is not long enough to encrypt the full message, attacker can gain information about the underlying text.

One way to solve it is to use - Deterministic Counter mode.

Sol 1

Randomized Encryption

Given the same PT, output different CT every time due to randomization. But the size of CT increases since the randomness is encoded in the message.

Sol 2

Nonce based Encryption

Message is encrypted using (k, n) and this pair never repeats. n could be public too. For e.g. for HTTP(s) packet counter can be used as n since packets arrive in order.

Cipher block chaining - with random IV

but if IV is predictable, CPA challenge will fail. In SSL/TLS this was a bug.

CBC -with nonce

Another key to encrypt nonce since nonce has to be random.

Randomized counter mode (CTR)

Parallelizable - Unlike CBC

Advantages of CTR over CBC

Parallel

Requires PRF rather than PRP

Better error bounds

No Padding required

But all these encryptions don't really protect against message tampering.