CLOC: Authenticated Encryption
for Short Input
Tetsu Iwata, Nagoya University
Kazuhiko Minematsu, NEC Corporation
Jian Guo, Nanyang Technological University
Sumio Morioka, NEC Europe Ltd.
FSE 2014
March 3, 2014, London, UK
1

Outline• A new authenticated encryption with associate data scheme(AEAD)• CLOC: Compact Low‐Overhead CFB, pronounced as “clock”

2CLOC Design Goal
• Provably secure AEAD that is based on a blockcipher– Standard security notions for privacy and authenticity• To improve previous schemes, CCM, EAX, and EAX‐prime– the implementation overhead beyond the blockcipher– the precomputation complexity– the memory requirement

3CLOC Design Goal
• Suitable for handling short input data, say 16 bytes, without
needing precomputation nor large memory• Suitable for small microprocessors, where the word size istypically 8 bits or 16 bits, and there are significant restrictionsin the size and the number of registers

4

CCM, EAX, and EAX‐Prime• AEADs based on a blockcipher• CCM (NIST SP 800‐38C)– not online• EAX (ISO/IEC 19772)– precomputation costs (L = EK(0), 2L, 4L, EK(1), and EK(2))– time and memory• EAX‐prime (ANSI C12.22)– efficiently handles short input data with small memory– practical attacks• CLOC removes these limitations– remove L = EK(0) or doubling operations over GF(2n)5Short Input Data
• Performance for short input data matters:– Low‐power sensor networks• Zigbee: at most 127 bytes– Bluetooth Low Energy: at most 47 bytes– Electronic Product Code (EPC): typically 96 bits
• For long input data, the efficiency of CLOC is the same as CCM,
EAX, and EAX‐prime– 2 blockcipher calls per 1 plaintext block– CLOC is for short input data

6

CLOC Properties• Nonce‐based AEAD
• uses only the encryption of the blockcipher both forencryption and decryption• When |A| 1 , it makes |N|n + |A|n + 2|M|n blockcipher
calls for a nonce N, associated data A, and a plaintext M– where |X| is the length of X in bits and |X|n is the length inn‐bit blocks– 1 |N| n−1, so |N|n = 1– No precomputation (blockcipher calls, generation of key
dependent tables, . . . ) is needed– when |A| = 0, it needs |N|n + 1 + 2|M|n calls
7CLOC Properties• For short input data
– 1‐block nonce, 1‐block associated data, and 1‐block
plaintext– CLOC: 4 calls– CCM: 5 or 6 calls– EAX: 7 calls (where 3 out of 7 can be precomputed)– EAX‐prime: 5 calls (where 1 out of 5 can be precomputed)• Static associated data can be handled efficiently• It works with two state blocks (i.e. 2n bits)• Sequential
8Overview of the Scheme• Encrypt‐then‐PRF paradigm• uses a variant of CFB mode in its encryption part and a variantof CBC MAC in the authentication part9

Tools• The one‐zero padding function: ozp– ozp(X) = X if |X|=jn for some j > 0, and ozp(X) = X||10…0• The tweak functions: f1, f2, g1, g2, and h– use them to directly update the state• The bit fixing functions: fix0 and fix1
– fix0(X): overwrite msb1(X) with 0– fix1(X): overwrite msb1(X) with 1• fix1(0000) = 1000, fix1(1100) = 1100

10

V <‐ HASHK(A,N)• A variant of CBC MAC• 1 |N| n−1

11V <‐ HASHK(A,N)• A variant of CBC MAC• 1 |N| n−1

12V <‐ HASHK(A,N)• A variant of CBC MAC• 1 |N| n−1

13V <‐ HASHK(A,N)• A variant of CBC MAC• 1 |N| n−1

14

C <‐ ENCK(V,M)• A variant of CFB mode15

T <‐ PRFK(V,C)• A variant of CBC MAC

16

T <‐ PRFK(V,C)• A variant of CBC MAC• g1 is used when |C|=017

Rationale• The bit fixing functions– used to logically separate CBC MAC and CFB mode
– otherwise, attacks are possible

18

Rationale• The tweak functions– There are 55 differential probability constraints• K xor f1(K), f1(K) xor g1(f1(h(K))), . . .
– Define a matrix M as

– K ∙ M = (K[1], K[2], K[3], K[4]) ∙ M= (K[2], K[3], K[4], K[1] xor K[2])1920

Rationale• The tweak functions– associate (i1, i2, i3, i4, i5) ∈ {1, . . . , 14}5 with (f1, f2, g1, g2, h)– f1: Mi1, f2: Mi2, g1: Mi3, g2: Mi4, h: Mi5• Tested all (i1, i2, i3, i4, i5) ∈ {1, . . . , 14}5
– e.g., K xor f1(K): the rank of I xor Mi1 is full (I is the identity
matrix)– 145 ‐> 864 candidates• Defined a cost function to choose the best exponentiations– roughly measures the computational cost of (f1, f2, g1, g2,h)– (i1, i2, i3, i4, i5) = (8, 1, 2, 1, 4)
21

Works with Two State Blocks

22Security• Privacy:– Indistinguishability of ciphertexts from random bits against
nonce‐respecting adversaries in a chosen plaintext attack
setting••23

Security• Authenticity:– Unforgeability against nonce‐reusing adversaries in achosen ciphertext attack setting– A strong adversary••

24Software Implementation• Embedded software• Atmel AVR ATmega128– 8‐bit microprocessor– AES from [AVR‐Crypto‐Lib] written in assembler• 156.7 cpb for encryption, 196.8 cpb for decryption– CLOC, EAX, and OCB3
• modes are written in C
• OCB3 code from [OCB News and Code] w/ modification– doubling operations are on‐line, large precomputation may
not be suitable to handle short input data for microprocessors– compiled with Atmel Studio 625

Software Implementation

•
•
•
•

1‐block AD, no static AD computation
cycle counting is obtained by the simulation of Atmel Studio 6
RAM is measured with a public tool [EZSTACK]In CLOC, the RAM usage is low and Init is fast, and it is fast for
short input data, up to around 128 bytes
26

Software Implementation

updated from the pre‐proceedings

27Software Implementation
•
•
•
•
•

General purpose CPUIntel processor, Core i5‐3427U 1.80GHz (Ivy Bridge family)
AES‐128, AES‐NI
CLOC: about 4.9 cpb for long input data (more than 220 blocks)
AES calls in CFB mode and CBC MAC (in tag generation) can bedone in parallel

28

Software Implementation• For long input data, CLOC is close to the speed of serial
encryption only mode (CBC mode)• CLOC: about 4.9 cpb– serial AES‐128 encryption: about 4.3 cpb
29

Software Implementation• For long input data, CLOC is close to the speed of serial
encryption only mode (CBC mode)• CLOC: about 4.9 cpb– serial AES‐128 encryption: about 4.3 cpb
30

Software Implementation• For long input data, CLOC is close to the speed of serial
encryption only mode (CBC mode)• CLOC: about 4.9 cpb– serial AES‐128 encryption: about 4.3 cpb
31

Hardware Implementation• Not the main focus• Altera FPGA, Cyclone IV GX (EP4CGX110DF31C7)– w/ AES‐128, composite field S‐box implementation, round‐based architecture• Size is measured in terms of LEs (logic elements)• one block of associated data and 8 blocks of plaintexts• Slightly smaller and faster than EAX
32

Conclusions• Designed CLOC and analyzed the security and the efficiency• CLOC is designed to efficiently handle short input data andsuitable for use in small microprocessors– it works without heavy precompuation nor large memory33