Block Cipher Modes

From the 70s: ECB, CBC, CFB, OFB, CTR

Concern of the time: error propagation

Status quo until late 90s:

A third consideration is fault-tolerance. Some applications need to parallelize encryption or decryption, while others need to be able to preprocess as much as possible. In still others it is important that the decrypting process be able to recover from bit errors in the ciphertext stream, or dropped or added bits.

Bruce Schneier, in Applied Cryptography (1996)

Block Cipher Modes Failures

Exploiting malleability

ECB: Rearrange/replay blocks
CTR, OFB: Bitwise modification of blocks
CBC: Change current ciphertext block to predictably change the next plaintext block (during decryption)

Chosen-boundary attacks

ECB, CBC, CFB: Partial chosen-plaintext control
Decrypt messages byte by byte

Authenticated Encryption (AE)

Input: key, nonce, message

Output: ciphertext, authentication tag

Protects Confidentiality, Integrity, Authenticity

Protects traffic in IPsec, SSH, TLS, etc.

Authenticated Encryption
with Additional Data (AEAD)

Input: message, additional data, key, nonce

Ouput: ciphertext, authentication tag

Integrity & Authenticity covers cleartext data

Useful to protect datagram parts that need remain in clear (such as headers including routing data)

AE(AD) Constructions
Generic Composition

Combine a symmetric cipher and a MAC

Options:

Encrypt-and-MAC
MAC-then-encrypt
Encrypt-then-MAC (generally better)

Examples:

AES128-CBC+HMAC-SHA-256
ChaCha20+Poly1305

Common Risks with Authenticated Encryption

Interaction between cipher and MAC (key reuse, etc.)

Sec(cipher+MAC) &leq; Min( Sec(Cipher), Sec(MAC) )

Custom ciphers/modes if no suitable standard

"Misuse" (constant/repeated nonces, etc.)

Bad parameters choice (such as GCM tag size)

Led to some problems...

Padding Oracle Attacks

2002: on MAC-then-encrypt CBC-mode ciphers

2002–2014: Repeatedly exploited to mount attacks on TLS (BEAST, Lucky Thirteen, etc.)

Latest variant: POODLE

Padding Oracle On Downgraded Legacy Encryption
(vs. SSLv3 & TLS)

Competition for

Authenticated

Encryption:

Security,

Applicability, and

Robustness

CAESAR

Identify a portfolio of authenticated ciphers that offer advantages over AES-GCM (the current de-facto standard) and are suitable for widespread adoption.

March 15 2014 – End of 2017

Led by DJB, with a committee of 22 cryptographers

Sponsored by but not organized/controlled by NIST

http://competitions.cr.yp.to/caesar.html

What's Wrong with AES-GCM?

Unnecessarily complex (to implement)

Fast only if AES/Galois field arithmetic HW support is available, like AES-NI

Without HW support: Constant-time implementations even more complicated

Auth key recovery if nonce is reused

What's Wrong with AES? Nothing

If NSA isn't interested in cryptanalysis, then who is?

Academics also find new "attacks" on AES every year

Don't worry, AES won't (can't?) be broken
(At least for any reasonable definition of "broken")

CAESAR's 57 submissions

ACORN	++AE	AEGIS	AES-CMCC	AES-COBRA
AES-COPA	AES-CPFB	AES-JAMBU	AES-OTR	AEZ
Artemia	Ascon	AVALANCHE	Calico	CBA
CBEAM	CLOC	Deoxys	ELmD	Enchilada
FASER	HKC	HS1-SIV	ICEPOLE	iFeed[AES]
Joltik	Julius	Ketje	Keyak	KIASU
LAC	Marble	McMambo	Minalpher	MORUS
NORX	OCB	OMD	PAEQ	PAES
PANDA	Π-Cipher	POET	POLAWIS	PRIMATEs
Prøst	Raviyoyla	Sablier	SCREAM	SHELL
SILC	Silver	STRIBOB	Tiaoxin	TriviA-ck
Wheesht	YAES

CAESAR's 57 submissions

ACORN	++AE	AEGIS	AES-CMCC	AES-COBRA
AES-COPA	AES-CPFB	AES-JAMBU	AES-OTR	AEZ
Artemia	Ascon	AVALANCHE	Calico	CBA
CBEAM	CLOC	Deoxys	ELmD	Enchilada
FASER	HKC	HS1-SIV	ICEPOLE	iFeed[AES]
Joltik	Julius	Ketje	Keyak	KIASU
LAC	Marble	McMambo	Minalpher	MORUS
NORX	OCB	OMD	PAEQ	PAES
PANDA	Π-Cipher	POET	POLAWIS	PRIMATEs
Prøst	Raviyoyla	Sablier	SCREAM	SHELL
SILC	Silver	STRIBOB	Tiaoxin	TriviA-ck
Wheesht	YAES

Flaws: none 39, major 13, minor 5

NORX Design Goals

High security

High speed (in SW and HW)

Simplicity (of specs and code)

Online / one-pass

Scalability (parallelism, unrolling)

High key agility (no "key schedule")

Side-channel leaks robustness (esp. timings)

NORX Parameters and Proposed Instances

Word Bit Size	Number of Rounds
W ∈ {32, 64}	1 ≤ R ≤ 63

Parallelism Degree	Tag Bit Size
0 ≤ D ≤ 255	\|A\| ≤ 10W

NORX[W-R-D]	Nonce (2W)	Key (4W)	Tag (4W)
NORX64-4-1	128	256	256
NORX32-4-1	64	128	128
NORX64-6-1	128	256	256
NORX32-6-1	64	128	128
NORX64-4-4	128	256	256

R=6: higher security margin
D=4: high throughput on parallel architectures

NORX Mode

"Monkey duplex" construction (from Keccak/SHA3)

Process header, payload, and trailer data in one pass

Data expansion via multirate padding: 10*1

State

16 W-bit words S = (s₀,...,s₁₅)

Rate (data) words and capacity (security) words:

State Properties, in bits:

W	Size	Rate	Capacity
32	512	320	192
64	1024	640	384

Initialisation

Load nonce, key and constants into S:

Parameter integration (v1):

s₁₄ = s₁₄ ^ (R<<26) ^ (D<<18) ^ (W<<10) ^ |A|

Apply round permutation: S = F^R(S)

Initialisation

Load nonce, key and constants into S:

Parameter integration (v2):

s₁₂ = s₁₂ ^ W
s₁₃ = s₁₃ ^ R
s₁₄ = s₁₄ ^ D
s₁₅ = s₁₅ ^ |A|

Apply round permutation: S = F^R(S)

Absorb Header / Trailer

Integrate domain separation constant:

s₁₅ = s₁₅ ^ {0x01,0x04}

Apply round permutation: S = F^R(S)

Absorb data:

Encrypt Payload

Integrate domain separation constant:

s₁₅ = s₁₅ ^ 0x02

Apply round permutation: S = F^R(S)

Absorb data:

Set new ciphertext block: c = (z₀,...,z₉)

Generate Tag

Integrate domain separation constant:


                        s₁₅ = s₁₅ ^ 0x08

Apply round permutation twice:

S = F^R(S)
S = F^R(S)

Set tag: t = (s₀,s₁,s₂,s₃)

The Permutation G(a,b,c,d)

1.	`a = H(a,b)`	5.	`a = H(a,b)`
2.	`d = ROTR(a^d,R0)`	6.	`d = ROTR(a^d,R2)`
3.	`c = H(c,d)`	7.	`c = H(c,d)`
4.	`b = ROTR(b^c,R1)`	8.	`b = ROTR(b^c,R3)`

with:

H(x,y) = (x^y)^((x&y)<<1)
ROTR(x,r) = (x>>>r)
(R0,R1,R2,R3) =
- (8,11,16,31) for W=32-bit words
- (8,19,40,63) for W=64-bit words

Properties of F^R/F/G

Inspired from BLAKE(2)/ChaCha

H is almost integer addition: + is replaced by ^ in

x+y = (x^y)+((x&y)<<1)

Only bit-wise ops, no carries; no S-boxes

Only constant-time operations

Hardware friendly: horizontal and vertical folding

Software friendly: direct use of SIMD instructions

Is NORX Secure?

Main threat: differential cryptanalysis, so let's prove resistance to some basic attacks (ongoing work)

No 1-round characteristics of probability...
- greater than 2^-64 (32-bit)
- greater than 2^-53 (64-bit)
Best 4-rounds characteristics:
- probability 2^-584 (32-bit)
- probability 2^-836 (64-bit)
Initialisation has ≥ 8 rounds
Conservative parameters: potential 16% speedup

Software Speed (SUPERCOP)

Source: http://www1.spms.ntu.edu.sg/~syllab/speed

NORX among the fastest CAESAR candidates

Fastest sponge-based scheme

Reference code has competitive speed, too

NORX vs. AES-GCM (x86/amd64)

AES-GCM "standard": OpenSSL 1.0.1j compiled with no-asm flag.
> openssl speed -evp aes-{128,256}-gcm

NORX vs. AES-GCM (ARMv7)

AES-GCM "standard": OpenSSL 1.0.1j compiled with no-asm flag.
> openssl speed -evp aes-{128,256}-gcm

Hardware Efficiency (ASIC)

NORX chip, source: http://asic.ee.ethz.ch/2013/CronorX.html

180nm UMC @125MHz, area ≈ 59kGE

NORX64-4-1 throughput: ≈ 10Gbps

CAESAR

Crypto competition 2014–2017

About authenticated encryption

57 submissions received

2nd-round candidates announced on Jan 15, 2015

http://competitions.cr.yp.to/
https://aezoo.compute.dtu.dk
http://www1.spms.ntu.edu.sg/~syllab/speed

PS: Another competition https://password-hashing.net

NORX

CAESAR candidate (one of the unbroken ones)

Innovative not-ARX core and parallelisable mode

Minimizes side-channel leaks (timing, padding)

No dependency on AES instructions/accelerators

Straightforward to implement, very fast in SW / HW

https://norx.io/

Code available in C, C++, Go, Python, Rust

No patents, free for everyone, code under CC0

Platform	Implementation	cpb	MiBps
Ivy Bridge: i7 3667U @ 2.0GHz	AVX	3.37	593
Haswell: i7 4770K @ 3.4GHz	AVX2	2.51	1390

Platform	Implementation	cpb	MiBps
BBB: Cortex-A8 @ 1.0GHz	NEON	8.96	111
iPad Air: Apple-A7 @ 1.4GHz	Ref	4.07	343

CAESAR & NORX The Future of Authenticated Encryption?

Who

Block Cipher Modes Failures (1/3) ECB

Block Cipher Modes Failures (2/3) CBC with constant IV

Block Cipher Modes Failures (3/3) CTR with reused nonce

Block Cipher Modes

Block Cipher Modes Failures

Authenticated Encryption

Authenticated Encryption (AE)

Authenticated Encryption with Additional Data (AEAD)

AE(AD) Constructions Generic Composition

AE(AD) Constructions Dedicated Methods

Common Risks with Authenticated Encryption

Crypto Failures

Padding Oracle Attacks

WEP

TLS (and RC4)

RC4

Insecure, but fast in Swift!

CAESAR

AES-GCM Everywhere

What's Wrong with AES-GCM?

What's Wrong with AES? Nothing

CAESAR's 57 submissions

CAESAR's 57 submissions

NORX

NO(T A)RX

NORX Design Goals

NORX Parameters and Proposed Instances

NORX Mode

NORX Mode

State

Initialisation

Initialisation

Initialisation

Absorb Header / Trailer

Absorb Header / Trailer

Encrypt Payload

Encrypt Payload

Generate Tag

Generate Tag

The Permutation FR

The Permutation G(a,b,c,d)

Properties of FR/F/G

Is NORX Secure?

Performance

Software Speed (x86/amd64)

NORX64-4-1 (single-core)

Software Speed (ARMv7, ARMv8-A)

NORX64-4-1 (single-core)

Software Speed (SUPERCOP)

NORX vs. AES-GCM (x86/amd64)

NORX vs. AES-GCM (ARMv7)

Hardware Efficiency (ASIC)

Conclusion

CAESAR

NORX

One last thing

Do not use NORX in production

At least for now...

CAESAR & NORX
The Future of Authenticated Encryption?

Block Cipher Modes Failures (1/3)
ECB

Block Cipher Modes Failures (2/3)
CBC with constant IV

Block Cipher Modes Failures (3/3)
CTR with reused nonce

Authenticated Encryption
with Additional Data (AEAD)

AE(AD) Constructions
Generic Composition

AE(AD) Constructions
Dedicated Methods

The Permutation F^R

Properties of F^R/F/G