Hamburg, 2014-12-29
Nearly all of the symmetric encryption modes you learned about in school, textbooks, and Wikipedia are (potentially) insecure.
From the 70s: ECB, CBC, CFB, OFB, CTR
Concern of the time: error propagation
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.
Input: key, nonce, message
Output: ciphertext, authentication tag
Protects Confidentiality, Integrity, Authenticity
Protects traffic in IPsec, SSH, TLS, etc.
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)
Combine a symmetric cipher and a MAC
Options:
Examples:
Interaction between cipher and MAC (key reuse, etc.)
Sec(cipher+MAC) ≤ 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)
2002: on MAC-then-encrypt CBC-mode ciphers
2002–2014: Repeatedly exploited to mount attacks on TLS (BEAST, Lucky Thirteen, etc.)
2007: key recovery within minutes from a few thousand intercepted messages
Download aircrack-ng and try this at home
2013: RC4 biases shown to be usable against TLS
Exploits weaknesses in RC4 (again)
Competition for
Authenticated
Encryption:
Security,
Applicability, and
Robustness
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
The AE standard:
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
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")
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)
R=6: higher security margin D=4: high throughput on parallel architectures
"Monkey duplex" construction (from Keccak/SHA3)
Process header, payload, and trailer data in one pass
Data expansion via multirate padding: 10*1
16 W-bit words S = (s0,...,s15)
S = (s0,...,s15)
Rate (data) words and capacity (security) words:
State Properties, in bits:
Load nonce, key and constants into S:
Parameter integration (v1):
s14 = s14 ^ (R<<26) ^ (D<<18) ^ (W<<10) ^ |A|
Apply round permutation: S = FR(S)
S = FR(S)
Parameter integration (v2):
s12 = s12 ^ W
s13 = s13 ^ R
s14 = s14 ^ D
 s15 = s15 ^ |A|
Integrate domain separation constant:
s15 = s15 ^ {0x01,0x04}
Absorb data:
s15 = s15 ^ 0x02
Set new ciphertext block: c = (z0,...,z9)
c = (z0,...,z9)
s15 = s15 ^ 0x08
Apply round permutation twice:
Set tag: t = (s0,s1,s2,s3)
t = (s0,s1,s2,s3)
FR = R iterations of the permutation F
F runs G on state's columns, then diagonals
a = H(a,b)
d = ROTR(a^d,R0)
d = ROTR(a^d,R2)
c = H(c,d)
b = ROTR(b^c,R1)
b = ROTR(b^c,R3)
H(x,y) = (x^y)^((x&y)<<1)
ROTR(x,r) = (x>>>r)
(R0,R1,R2,R3)
(8,11,16,31)
(8,19,40,63)
Inspired from BLAKE(2)/ChaCha
H is almost integer addition: + is replaced by ^ in
H
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
