Home About Research Projects

Master's Thesis

Provable Security of Submissions to the CAESAR Cryptographic Competition

The aim of this thesis was to prove some submissions to the CAESAR competition secure in the framework of provable security.

Abstract
Short Summary
Downloads

This thesis was done by Robin Ankele from Dez 2014 - May 2015 during his stay at the COSIC group at the KU Leuven, Belgium. He was advised by Dr. Bart Mennink, Dr. Elena Andreeva.


Abstract

Modern cryptography is build upon the approach to design and develop provable secure primitives. Hereby, a security proof is typically the reduction from a problem P - related with the security of the candidate scheme, to a well known problem P1 of e.g. a random oracle or a one-way function. An authenticated encryption scheme (AE), is a symmetric primitive that provides both - data privacy and data integrity. To identify a secure and robust authenticated encryption scheme, the CAESAR competition was recently announced. COPA is an AE composition scheme used in several CAESAR candidates. We consider COPA in the nonce-respecting setting, and derive a variant of the scheme COPA, which we prove secure beyond the birthday bound. For the proof, we use Patarin's coefficient-H technique - a well known technique for probable security of symmetric primitives. Furthermore, we show the applicability of our results to the CAESAR candidates AES-COPA and PRØST, where we increase the IND-CPA security bound from 264 to 283 encryption calls for AES-COPA and from 264(2128) to 283(2168) encryption calls for PRØST-COPA, respectively. Moreover, we studied the mode COPA in the CAESAR candidate schemes Deoxys, Joltik and KIASU. Since COPA is used there in a slightly derivate version, we established another separate proof for privacy and integrity. Therefore, we can give first results on the conjecture of Jean et al., that Deoxys, Joltik and KIASU achieve security beyond the birthday bound in the nonce-respecting setting.

Keywords: Provable Security, CAESAR, Authenticated Encryption, COPA, IND-CPA, INT-CTXT, Nonce, AES-COPA, PRØST, Deoxys, Joltik, KIASU



COPA

In this thesis we have analyzed COPA - an authenticated encryption scheme and derived a variant of this scheme for which we prove security beyond the birthday bound in the nonce respecting setting. COPA was announced at ASIACRYPT 2013 by Andreeva et al.

COPA

COPA is a variant of COPA, that is aimed to achieve security beyond the birthday bound. The following table shows the differences between COPA and COPA.

COPA

COPA

Adversary

nonce-reusing

nonce-respecting

Li (Tweaks)

EK(0)

EK(L)

Vi (AD)

see Thesis

PRFK(N, AD)

K (Key)

K

K1, K2, K3

Table: Main Differences between COPA and COPA

Figure: Message Processing of COPA after replacement of PRF with a random function and EK with permutations.

Privacy Proof for COPA

Theorem. Let Π = (E,E-1) denote the candidate COPA. Moreover, let D be a distinguisher making at most q queries to either E or $OAE and using time t then,

AdvEIND-CPA(D) ≤ 8(σ + q \choose 3) / (2n - q)2 + 2AdvESPRP(2σ + q, t') + AdvEPRF(q, t')

For the proof we use Patarin's coefficient-H technique. For the detailed proof we refer to the thesis in the Downloads section.

Integrity of COPA

Although we haven't established a security proof for the integrity of COPA, we conjecture that the bound of the original COPA proof holds.

Application to AES-COPA

AES-COPA is a CAESAR candidate, proposed by Andreeva et al. AES-COPA uses as underlying design principle COPA. Using our improvement of COPA we can increase security beyond the birthday bound as shown in the following table:

AES-COPA

AES-COPA

Confidentiality of plaintext

264

283

Integrity of plaintext

264

264

Integrity of associated data

264

264

Integrity of PMN

264

264

Table: Security Claims of AES-COPA and AES-COPA for n = 128.

Application to PRØST-COPA

PRØST is a CAESAR candidate, proposed by Kavun et al. PRØST-COPA uses as underlying design principle COPA. Using our improvement of COPA we can increase security beyond the birthday bound as shown in the following table:

PRØST-COPA

PRØST-COPA

Confidentiality of plaintext

264/2128

283/2168

Integrity of plaintext

264/2128

264/2128

Integrity of associated data

264/2128

264/2128

Integrity of PMN

264/2128

264/2128

Table: Security Claims of PRØST-COPA and PRØST-COPA for n = {128, 256}.



Downloads

Master's Thesis

.pdf

894 kB

Presentation

.pdf

770 kB

© Robin Ankele 2015