cryptography course - Authenticated Encryption

Authenticated Encryption

How to secure against tampering.

If message needs integrity but no confidentiality - use MAC

If message needs integrity and confidentiality - use Authenticated Encryption

3 options:

SSL(Mac-then-Encrypt),IPSec(Encrypt-then-MAC),SSH (Encrypt-and-MAC) => IPSec is the best one to provide AE

Standards:

GCM, CCM, EAX

OCB : a direct construction from a PRP - Efficient in the sense that you don't have to invoke AES(or another block cipher) twice - once each for encryption and MAC

- parallel

But OCB is not widely used and not a standard - primarily due to various patents

TLS

AE in real world

Attacks

IMAP over TLS

Padding Oracle

Attacking non-atomic decryption => 

KDF

HKDF - key derivation function from HMAC (Generating multiple keys from one key)

Password based KDF - PBKDF/PKCS

Searching on Encrypted data

Deterministic Encryption - cannot be CPA secure. Solution - pair (k, m) is unique. Same message won't be encrypted by the same key. CBC with fixed IV is not det. CPA secure.

SIV with wide PRP.

EME

Disk Encryption

Encryption cannot expand original text. Sector size fixed.
If 2 sectors have same content, their cipher texts will also be the same. Information will leak.

First, approach - let's use different keys for different sectors.

But even with this approach, user can still change the text and then revert it to find a leakage or pattern.

Tweakable block cipher - where tweak comes from sector number.

XTS tweakable block cipher

Use tweakable encryption when you need many independent PRPs from one key.

Format preserving encryption

Credit card encryption - 

Cryptography course - Message integrity

Let's talk about how to ensure integrity rather than confidentiality - for e.g. banner ads.

CRC is not enough. We need a shared key with both parties.

MAC - Message Authentication Codes => S,V

S(k,m) -> t

V(k,m,t) -> 0,1

Popular variations using AES

CBC-MAC

H-MAC

Truncated PRF is also secure if 1/2^w is negligible where w is the length after truncation.

Encrypted CBC-MAC (ECBC)

Raw CBC which doesn't do the final encryption with a different key.

NMAC (Nested MAC)

Output is in the key space. As opposed to ECBC where output is in X.

In both NMAC and ECBC last encryption step is required else it's insecure.

AES based ECBC is the most popular MAC algo.

AES based ECBC should not be used for more than 2^48 messages.

Message padding

If we append 0s at the end to pad the message, it's risky. Let's a cheque of amount 1 is the message. We pad 0s at the end, which makes it 1000. Now, both 1 and 1000 have the same tag!!

So, padding must be invertible. If m0 != m1, pad(m0) != pad(m1) should hold.

ISO standard

So, pad with 100..00. While removing the pad, keep removing till you get the first 1.

If the message is already a multiple of the block size, add a pad still.

Using CMAC we can avoid padding for messages which are multiple of block sizes.

If the message is multiple of block size, encrypt the last block with K2. If not, pad and encrypt with K1.

PMAC

Parallel, incremental.

One time MAC - parallel of one time pad for integrity

Carter wegman MAC - build many time MAC from one time MAC

Collision resistance - Merkle Damgard paradigm

Davies meyer compression function.

Timing attacks on MAC verification

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.