Security Features of Authenticated Encryption

Security Aspects of
Authenticated Encryption
Elena Andreeva
COSIC, KU Leuven
Summer school on design and security of cryptographic
algorithms and devices for real-world applications
Croatia, 05/06/2014
Outline
 Authenticated Encryption AE
 Generic AE composition
 Dedicated AE schemes
 nonce-based AE
 nonce misuse resistant AE
 Further challenges
2
Security Goal
Confidentiality
+
Authenticity
3
Ways to Build AE Schemes?
1. Generic AE composition
off the shelf primitives
Symmetric Authentication (MAC)
+
Symmetric Encryption
2. Dedicated AE scheme (AE designs from scratch)
3. Something in between  (state of the art)
4
Generic Composition [BN’00]
1. Ways of composing
Enc then MAC secure
MAC then Enc insecure
Enc and MAC insecure
Caveat: Careful with interpretations!
5
Conventional Encryption
• Enc = (Kg, Enc, Dec)
Key generation: K ←$ Kg
Encryption: (st, C) ←$ EncstK(M) (randomized or stateful)
Decryption: M ← DecK(st, C) (deterministic)
Correctness: DecK(EncK(M)) = M
•
Indistinguishability
$IND-CPA(CCA)
M
st,C
EncK
M
|st,C|
$
Random
bits
6
MAC
• MAC = (Kg, MAC, Verify)
Key generation: K ←$ Kg
Authentication: T ← MACK (M) (any)
Verification: 1/0 ← VerifyK (M, T) (deterministic)
Correctness: VerifyK(M, MACK (M)) = 1
•
Unforgeability (weak M’ ≠ M; strong M’,T’ ≠ M,T)
M
T
M’,T’
MACK
VerifyK
?
Win if ? is 1
7
Generic Composition [BN’00]
• $IND-CPA Enc + Unforgeable MAC
AE secure: Enc then MAC
• Off the shelf schemes
Enc (CBC, CTR,...) + MAC (CBC-MAC,HMAC,PMAC...)
Caveat: Careful with interpretations!
A. Enc often with badly or externally generated
random IV
B. IV should not be communicated out of band
8
A: Random IV Encryption
•
Fix A: Environment
Enc = (Kg, Enc, Dec)
not Enc selects IV
Key generation: K ←$ Kg
B: IV still in-band
Encryption: IV, C ← EncIVK(M) (deterministic)
Decryption: M ← DecK (IV, C) (deterministic)
Correctness: DecK(EncIVK(M)) = M
•
Indistinguishability
$IND-CPA
M
EncK
IV, C
IV←$IV
M
|IV,C|
$
Random
bits
9
Nonce IV
•
•
•
•
•
N: nonce IV
Not required to be random
Unique non-repeating value
Can be communicated out of band
Theoretically: a way to work with an IV
(randomness/state) out of Enc algorithm
• Practically: ease of use
10
Nonce-based Encryption Scheme
•
•
Fix A: Adversary
can select N
Enc = (Kg, Enc, Dec)
Fix B: out-of-band
Key generation: K ←$ Kg
Encryption: C ← EncK(N, M) (deterministic)
Decryption: M ←DecK(N, C) (deterministic)
Correctness: DecK(N, EncK(M)) = M
Indistinguishability (nonce respecting adversary)
$IND-CPA
N,M
EncK
C
N,M
|C|
$
Random
bits
11
Generic Composition Reconsidered [NRS’14]
• Build nonce-based AE from
1. IV-Enc + MAC
Efficiency issues: 2 passes over the data
SIV
12
Generic Composition Reconsidered [NRS’14]
• Build nonce-based AE from
2. N-Enc + MAC
• Generic composition disadvantages
-
Efficiency issues: 2 passes over the data
Prone to misuse with conventional Enc schemes
13
Outline
 Authenticated Encryption AE
 Generic AE composition
 Dedicated AE schemes
 Nonce-based AE
 Nonce misuse resistant AE
 Further challenges
14
Dedicated AE: State of the Art
Prior to CAESAR
Building Block
Block cipher
Permutation
* hold a patent
Nonce dependent
AE security
IAPM*’00, OCB*’01,
XECB*’01, CCM’03,
GCM’04, OTR*’14,
CLOC’14
SpongeWrap’11
Ketje&Keyak’14
NORX’14
Nonce independent
AE security
SIV’06, BTM’09,
McOE-G’11, POET’14
COPA’13
APE’14
15
Nonce-based AE
• AE = (Kg, E, D)
Key generation: K ←$ Kg
Encryption: C ← EK(A, N, M) (deterministic)
Decryption: M/⊥ ← DK (A, N, C) (deterministic)
Correctness: DK(A, N, EK(A, N, M)) = M
• AE confidentiality + AE integrity = AE security
16
AE Confidentiality
•
$IND-CPA
N, A,M
C
N, A,M
EK
Adversary is nonce respecting
|C|
$
Random
bits
17
AE Integrity
•
INT-CTXT
N, A,M
C
C’≠ C
EK
DK
?
Win if ? is M ≠ ⊥
Adversary maybe nonce respecting
18
Nonce-based AE Security
N, A, M
EK
C
N, A,C’
?
N, A,M
DK
|C|
$
Random
bits
⊥
N, A,C’
⊥
Adversary is nonce respecting
19
Example: OCB [RBBK’01]
M2
M1
α1
α2
AESK
α1
αi= fi(K,N)
βi= gi(K,N)
...
αd
AESK
C2
⊕Mi
i=1
β1
AESK
...
α2
C1
Md
d
αd
AESK
β2
Cd
T
20
Outline
 Authenticated Encryption AE
 Generic AE composition
 Dedicated AE schemes
 Nonce-based AE
 Nonce misuse resistant AE
 Further challenges
21
Nonce Misuse Resistant AE
Not all security should be lost
if N misused!
22
Distinct Nonces
N1 M1
N2 M1
N3 M2
OCB
OCB
OCB
C1
C2
C3
23
Nonce Misuse OCB
Ciphertext Repetitions
What security can be lost?
N1 M1
N1 M1
N1 M2
OCB
OCB
OCB
C1
C1
C3
• Valid for all nonce respecting AE schemes
24
Nonce Misuse OCB
Ciphertext Block Repetitions
What else can be lost?
M2
M1
OCB-Enc
α1
α2
AESK
α1
...
αd
AESK
AESK
...
α2
C1
Md
C2
αd
Cd
25
Nonce Misuse OCB
Ciphertext Block Repetitions
What else can be lost? (OCB looses confidentiality)
M2
M’1
OCB-Enc
α1
α2
AESK
α1
•
...
αd
AESK
AESK
...
α2
C’1
Md
C2
αd
Cd
If C blocks repeat (over distinct OCB calls) then M blocks
repeat (OCB, IAPM, XCBC, ...)
19
What to Do against Nonce Misuse?
Not all security should be lost
if N misused!
1. Security up to common prefixes
ciphertext leaks only presence of common M prefixes
McOE-G, COPA, APE, COBRA, POET
2. Security up to repetitions
ciphertext leaks only presence of repeating Ms
SIV, BTM, HBS but two passes over the data
21
Nonce Misuse Resistance
via Online Ciphers
• Online cipher + authentication *BBKN‘01, FFLW’12+
nonce misuse resistant nmr AE scheme
secure up to common prefix repetitions
22
Regular vs Online Ciphers
•
•
Normally in a cipher
m1
m2
m3
m4
c1
c2
c3
c4
Online cipher
- more efficient
- different security (IND from random
online permutation)
m1
m2
m3
m4
c1
c2
c3
c4
22
COPA [ABLMY’13]
nmr AE
M2
M1
α0
EK
Md
⊕Mi
i=1
. . . 2d-1α0
2α0
EK
- nmr
- online
- parallelizable
d
β1
EK
EK
...
L
EK
α1
EK
2d-1α1
2α1
C1
EK
C2
L = EK(0)
α0 = 3L and α1= 2L
β1= 2d-1.32L and β2 = 2d-1.7L
EK
β2
Cd
T
30
COPA
Security Proof
d
M2
M1
XEX
XEX
⊕Mi
Md
i=1
XEX
XEX
...
Implicit ⊕ masks
αi = 2i-1.3L
XEX
XEX
XEX
C1
C2
Cd
XEX
T
If E is SPRP, COPA is AE secure up to 2n/2 queries
31
Outline
 Authenticated Encryption AE
 Generic AE composition
 Dedicated AE schemes
 Nonce-based AE
 Nonce misuse resistant AE
 Further challenges
32
Further Security Pitfalls in AE
What if attacker gets C decryptions before
verification completed?
RUP: Release of unverified plaintext *ABLMNY’14+
• Scenarios
-
Insufficient memory
Real-time requirements
• Not in current AE security models!
33
AE Syntax under RUP
•
Separate the AE Decryption D functionality into
Dec and Verify (how we design AE schemes)
C, T ← EK(A, N, M)
M ← DecK(A, N, C, T)
1/0←VerifyK(A, N, C, T)
Correctness: DecK(A, N, EK(A, N, M)) = M
and VerifyK(A, N, EK(A, N, M)) = 1
34
RUP Confidentiality
• Confidentiality: $IND-CPA + PA1
• Plaintext awareness PA1
N, A, M
EK
C
N, A,C
M
N, A, M
DecK
C
EK
N, A,C
M
Extractor
Adversary can choose any nonce
35
RUP Integrity
• Int-RUP
N, A, M
C, T
N, A, C, T
M
N, A, C’, T’
EK
DecK
VerifyK
?
Win if ? is valid 1
Adversary can choose any nonce
36
Security of AE
Schemes under RUP
IV Type
Scheme
PA1
Random
CTR, CBC encryption
Yes
Nonce
OCB
GCM, SpongeWrap
CCM
No
No
No
COPA
McOE-G
APE
SIV, BTM, HBS
Encode-then-Encipher
No
No
Yes
Yes
Yes
Arbitrary
37
Further Challenges
• AE security
- handling failure events?
- further generic results?
- identify relevant AE security risks?
• Security of present solutions?
38
Thank you!

Download Report