PROTECTING CIPHER BLOCK CHAINING AGAINST ADAPTIVE

CHOSEN PLAINTEXT ATTACK

Chuan-Wen Loe

DSO National Laboratories

20 Science Park Drive, Singapore 118230

Khoongming Khoo

DSO National Laboratories

20 Science Park Drive, Singapore 118230

Keywords:

Cipher Block Chaining, Adaptive Chosen Plaintext Attack, Input-Output Masked CBC.

Abstract:

In the literature, several encryption modes of operation based on cipher block chaining (CBC) has been proven

to be secure under non-adaptive chosen plaintext attack (CPA-1) in the left-or-right (LOR) or ﬁnd-then-guess

(FTG) security models. However, it was shown by Joux et. al. at Crypto 2002 that if we allow the adversary

to perform an adaptive chosen plaintext attack (CPA-2), then CBC, ABC and GEM are susceptible to FTG

attacks. In this paper, we propose a new CBC-type encryption called input-output masked CBC (IO-CBC)

which can protect against FTG and LOR attacks based on forcing an input collision, protects against Joux’s

FTG attack under proper implementation, and increases the difﬁculty of linear and differential cryptanalysis.

The efﬁciency of IO-CBC is comparable to CBC because it does only one additonal encryption when compared

with CBC. We also reasoned that the security proof of an IO-CBC variant follows from that of OCB.

1 INSECURITY OF CBC-TYPE

MODES UNDER CPA-2 ATTACK

The CBC mode is one of the most commonly used en-

cryption mode in practice. Let E

(·) denote a secure

block encryption function with secret key k. CBC can

be described as:

Algorithm 1 CBC Mode:

Input: Randomly Generated Initial Vector (IV),

Plaintext blocks M[1], M[2], . . . , M[l].

Initialize: O[0] = IV,

Input: I[i] = M[i] ⊕ O[i − 1],

Output: O[i] = E

(I[i]),

Ciphertext: C[i] = O[i], i = 1, . . . , l.

Output: IV, Ciphertext blocks C[1], C[2], . . . , C[l].

The CBC mode was proven to be secured against

left-or-right distinguishing attack (LOR-secure) (Bel-

lare, 1997, Proposition 15, Lemma 16, Theorem 17)

under non-adaptive chosen plaintext attack (CPA-1).

However in (Joux, 2002), Joux et. al. proved that un-

der blockwise adaptive chosen plaintext attack (CPA-

2), CBC can be distinguished by a ﬁnd-then-guess

(FTG) attack. The FTG attack uses the fact that in

CBC under CPA-2, the adversary can force a collision

in the input of the block cipher at any two iterations i

and j (j > i) by setting M[j] = C[j −1]⊕C[i− 1]⊕

M[i]. In that case, the ciphertext of iteration i and j

will be the same. This fact can also be used to mount

a LOR-attack on CBC under CPA-2 assumptions.

Similar LOR and FTG attacks, based on collision

of the block cipher input at two blocks, can also

be performed against CBC-type encryption modes

like the Accumulated Block Chaining (ABC) (Knud-

sen, 2000) and the Propagating CBC mode (PCBC)

(Matyas, 1982). In ABC, the adversary forces a colli-

sion as in CBC but instead of comparing C[i] = C[j],

he compares C[i]⊕M[i−1] = C[j]⊕M [j − 1]. And

in PCBC, to force a collision, the adversary needs to

choose a plaintext M[j] such that M[j] ⊕ C[j − 1] ⊕

M[j − 1] = M [i] ⊕ C[i − 1] ⊕ M[i − 1].

In the LOR and FTG attacks, the adversary is able

to force a collision because the ”masking” at each

block is known, therefore adaptively choose the ap-

propriate plaintext. Moreover, a collision can be veri-

ﬁed by observing the ciphertext. This pose an advan-

tage to blackbox cryptanalysis as a stepping stone to

determine the mode of operation the encryptor uses.

To protect encryption modes against these attacks

is to mask the input and output with some unknown

data. One possible candidate is IACBC proposed by

Jutla. To encrypt m blocks of data, additional log(m)

135

Loe C. and Khoo K. (2006).

PROTECTING CIPHER BLOCK CHAINING AGAINST ADAPTIVE CHOSEN PLAINTEXT ATTACK.

In Proceedings of the International Conference on Security and Cryptography, pages 135-140

DOI: 10.5220/0002100301350140

 SciTePress

encryptions of the values r +1, . . . , r +log(m) where

r is secret. Then these log(m) encrypted values are

expanded using Gray’s code to form m pairwise inde-

pendent secret blocks S

, S

, . . . , S

. The encryp-

tion of IACBC is identical to CBC except that the

block cipher output O[i] is XORed with S

to form

the ciphertext C[i]. Similarly, OCB (Rogaway, 2001)

uses (a different) masking to enhance ECB mode.

In this paper, we propose a new CBC-type en-

cryption mode called input-output masked CBC mode

(IO-CBC). Unlike OCB and IACBC which gener-

ates their maskings from an independent (from the

plaintext and ciphertext) structured algorithm (Gray’s

Code), IO-CBC generates its masking from a psedo-

random source, the block encryptor.

2 THE INPUT-OUTPUT MASKED

CBC MODE

In this Section, we describe the Input-Output Masked

CBC mode (IO-CBC). The design goals of IO-CBC

are as followed:

1. On-line

2. Memory Free

3. Single Pass

4. Increase effort required in Differential and Linear

Cryptanalysis with reused nouce condition

5. Inﬁnite Error Propagation (Better Diffusion)

6. Single Key

7. Minimize Encryption

It is a slight modiﬁcation of the CBC mode we

masked both the block cipher input and output with

the previous output block transformed by a specially

chosen linear function F (·).

· · ·

Algorithm 2 Input-Output Masked CBC Mode:

F (·) = A non-singular linear function such that

(s) ⊕ F

(s) preserves the entropy of s.

Input: Randomly Generated Initial Vector (IV),

Plaintext blocks M[1], M[2], . . . , M[l].

Initialize: O[0] = E

(IV ),

Input: I[i] = M[i] ⊕ F (O[i − 1]),

Output: O[i] = E

(I[i]),

Ciphertext: C[i] = O[i] ⊕ F (O[i − 1]).

Output: IV, Ciphertext blocks C[1], C[2], . . . , C[l]

As we shall see in Section 4, it is important that the

encrypted IV O[0] = E

(IV ) to be kept secret in this

scheme. To preserve the entropy of O[0], we need a

non-singular linear function such that that it is as hard

to guess F

(O[0]) ⊕ F

(O[0]) as guessing O[0].

3 EFFICIENCY OF IO-CBC

In IO-CBC, the operations are similar to CBC except

for an extra linear transform F (O[i − 1]) for input-

output masking at iteration i. The overall complexity

is still equivalent to one block encryption per iteration

because the linear function computation can be con-

sidered free on most platforms. Thus the efﬁciency of

IO-CBC is only one block encryption more than CBC

where the extra work is for encrypting the IV.

Since IO-CBC maskings are dependant from the

previous block, hence it is an on-line encryption and

does not required additional memory. In compari-

son, some CBC-type encryption like IACBC cannot

do on-line encryption because it requires the sender

to know the length of the whole plaintext beforehand

(say m blocks) to do log(m) additional encryption for

the Gray’s Code masking.

4 SECURITY

In this Section, we consider adaptive chosen plaintext

attack on IO-CBC. The assumption is that the adver-

sary can choose the plaintext M[i] after observing the

ciphertext C[1], C[2], . . . , C[i − 1]. He has no control

over the initial vector (IV), which is generated by the

encryptor.

4.1 Protection Against Attacks based

on Forcing an Input Collision

In FTG and LOR attacks on CBC-type encryption

modes under CPA-2, the adversary tries to force an

input collision. This is achieved by choosing an ap-

propriate plaintext block M [i], which when XORed

with a known input masking, will produce a desired

input value I[i]. For example, to force a collision in

CBC, an adversary will choose an M[j] which sat-

isﬁes M [j] ⊕ C[j − 1] = M[i] ⊕ C[i − 1], j > i,

SECRYPT 2006 - INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY

136

where the input masking-values C[i − 1], C[j − 1] are

known. This is not possible for IO-CBC because the

adversary cannot deduce the input masking.

In IO-CBC, an adversary can control the input I[i]

at iteration i by choosing an appropriate plaintext

block M [i] if the input mask F (O[i − 1]) is known

because I[i] = M[i] ⊕ F (O[i − 1]). But to know

F (O[i − 1]), the adversary needs to XOR the known

value C[i − 1] with the unknown value F (O[i −2]) to

obtain O[i − 1]. Similarly, to know F (O[i − 2]), the

adversary needs to XOR C[i − 2] with F (O[i − 3]) to

obtain O[i − 2]. Inductively, we deduce that:

F (O[i − 1]) = F (C[i − 1] ⊕ F (C[i − 2]⊕

. . . ⊕ F (C[1] ⊕ F (O[0]) . . .)))). (1)

IV, C[1], . . . , C[i] are known values but adversary

does not know O[0] = E

(IV ) which is not trans-

mitted. Although the adversary knows the IV, he can-

not deduce E

(IV ) from it because E

is a secure

encryption function.

Because F (·) is a linear function, F (x ⊕ y) =

F (x) ⊕ F (y) and we can write equation (1) as:

F (O[i − 1]) = F (C[i − 1]) ⊕ F

(C[i − 2])⊕

. . . ⊕ F

i−1

(C[1]) ⊕ F

(O[0]). (2)

Together with the equation I[i] = M [i] ⊕ F (O[i −

1]), we see that for i > j, we can force a collision

I[i] = I[j] if we choose M[i] as follows.

M[i] = M[j] ⊕ F (O[i − 1]) ⊕ F (O[j − 1])

= M [j] ⊕ F (C[i − 1]) ⊕ F

(C[i − 2])⊕

. . . ⊕ F

i−j

(C[j]) ⊕ F

(O[0]) ⊕ F

(O[0]).

We note that the only unknown summand in the

above equation is F

(O[0]) ⊕ F

(O[0]). The con-

dition we impose on F (·) ensures that the entropy of

(O[0])⊕F

(O[0]) is the same as O[0] which is kept

secret. Thus an adversary cannot force a collision.

One possible choice for the function F (·) is to let

it be the shift register matrix of a linear feedback

shift register (LFSR) whose feedback polynomial is a

primitive polynomial x

+ c

n−1

+ . . . + c

x + c

F =







0 0 0 . . . 0 c

1 0 0 . . . 0 c

0 1 0 . . . 0 c

0 0 0 . . . 1 c

n−1







(3)

The output sequence of such an LFSR is usually

called a binary m-sequence.

Proposition 1 (Shift and add property for binary m-

sequences (Golomb, 1982, Chapter 3)) Let F (·) be

the shift register matrix of an n-bit LFSR with prim-

itive feedback polynomial (see equation (3)). Let

the initial state of this LFSR be s. Then for any

0 ≤ i 6= j ≤ 2

− 2, there exist 0 ≤ k ≤ 2

− 2

such that F

(s) ⊕ F

(s) = F

(s).

By Proposition 1, the entropy of F

(s) ⊕ F

(s) will

be the same as that of s. Therefore the linear map

in equation (3) is a suitable choice for the function

F (·) in Algorithm 2. However, since LFSR is a

shift and generates an unknown most signiﬁcant bit,

hence LFSR

(x) is similar to LF SR

i+1

(x). To pre-

vent attacks that exploit this property, let F

(x) =

LF SR

(x) and F

i+1

(x) = LF SR

i+B

(x), where B

is the block size.

4.2 Elimination of Output Masking

For the adversary, in addition to the difﬁculty of con-

trolling the input I[i] in IO-CBC, it is also difﬁcult for

him to deduce the encryption output O[i]. This is be-

cause he can only observe the ciphertext C[i] which is

O[i] XORed with an unknown masking. However in

the LOR and FTG attacks of (Alkassar, 2001; Bellare,

1997; Joux, 2002), it is essential that the adversary be

able to deduce the output (e.g. to determine when an

output collision O[i] = O[j] occurs in a CBC attack)

to distinguish the plaintext message that is being en-

crypted.

To get around the effect of the secret masking at

the output is to ﬁnd a linear combination of the out-

put masks which sums to a known value. This is the

basic idea used in (Joux, 2002; Sung, 2003) where

they used the relation S

⊕ S

= 0 to at-

tack IACBC. However, the attack in (Joux, 2002) can

be prevented if we keep the encrypted IV secret. We

show that IO-CBC can be protected in a similar way.

For the case when F (·) is a linear function in IO-

CBC, there exist a linear combination which sums to

a known value. This is because m(F ) = 0 when

m(x) =

i∈I

is the minimal polynomial of the

linear function F (·). Thus

i∈I

(O[0]) = 0.

together with equation (2), this implies:

i∈I

F (O[i − 1]) =

i∈I

(F (C[i − 1]) ⊕ F

(C[i − 2])⊕

. . . ⊕ F

i−1

(C[1])). (4)

Therefore we have a linear combination of output

masks that sum up to a known value.

It can be shown that Joux’s FTG attack on IACBC

can be applied to IO-CBC in a similar way using

equation (4); but under the assumption that the en-

crypted IV, E

(IV ) = O[0], is given under ﬂawed

implementation. However if O[0] is given, IO-CBC

will be reduced into a CBC since from equation (2),

PROTECTING CIPHER BLOCK CHAINING AGAINST ADAPTIVE CHOSEN PLAINTEXT ATTACK

137

all masking will be revealed. Hence adversary can

attack ﬂawed implemented IO-CBC as though it is a

CBC mode, and Joux’s attack will be unnecessary.

IO-CBC is designed for a single key encryption,

however if it is extended to two keys, having sepa-

rate keys for each of the masking and data, the key

recovery attack for IACBC in (Sung, 2003) cannot

be applied on IO-CBC. The attack in (Sung, 2003)

expressed the maskings S

in terms of plaintext and

ciphertext, and eliminate the linear masking with

⊕ S

= 0. Thus we get an expres-

sion involving just the plaintext, ciphertext and key

. The key k

that is used for the secret masking

is excluded, which reduces the key space complex-

ity. Thus we can perform exhaustive key search on k

and k

separately to deduce them with a complexity

of 5 · 2

instead of 2

, where n is the size of each

key.

Based on equation (4), we consider the key re-

covery attack of (Sung, 2003) on a 2-key variant of

IO-CBC. In this variant, we use a different key k

for encryption of IV (O[0] = E

(IV )) and k

for

the plaintext. We need to express the secret masking

F (O[i − 1]) in terms of M[i], C[i] and K

C[i] = O[i] ⊕ F (O[i − 1])

F (O[i − 1]) = C[i] ⊕ E

(I[i])

F (O[i − 1]) = C[i] ⊕ E

(M[i] ⊕ F (O[i − 1]))

For ease of explaination, suppose there exist an output

mask relation: F (O[a − 1]) ⊕ F (O[b− 1]) ⊕ F (O[c −

1] = 0. Then

(M[a] ⊕ F (O[a − 1]))⊕

(M[b] ⊕ F (O[b − 1]))⊕

(M[c] ⊕ F (O[c − 1]))

= C[a] ⊕ C[b] ⊕ C[c]

Although the output masking is eliminated, the in-

put masking exists and from equation (2), we see

that k

remains as a factor in F (O[a − 1]), F (O[b −

1])andF (O[c − 1]). Hence we are unable to exclude

from k

, and brute force complexity remains at

4.3 Resistance to Differential and

Linear Cryptanalysis

In this section, we shall see that IO-CBC makes dif-

ferential and linear cryptanalysis harder.

Linear cryptanalysis is a known plaintext attack

while differential cryptanalysis is a chosen chosen

plaintext attack. For example in DES, the adversary

needs about 2

known plaintext-ciphertext pairs to

launch a successful linear attack (Matsui, 1994) and

chosen plaintext-ciphertext pairs to launch a dif-

ferential attack (Biham, 1992).

In our context, we name a plaintext-ciphertext pair

an input-output pair. IO-CBC makes it hard for the

adversary to collect known input-output pairs. The

reason is because we have XOR-masked the plaintext

M[i] with F (O[i − 1]) to form the input I[i]. And

as explained before, knowing F (O [i − 1]) is equiva-

lent to knowing O[0] = E

(IV ) which is kept secret.

Thus known input attack cannot be applied. More-

over, the input masking is secret and thus cannot con-

trol the encryption input by choosing an appropriate

plaintext. Thus chosen input attack cannot be per-

formed. Even if adversary managed to control or de-

duce the input, he will have difﬁculty in deducing the

output from the ciphertext because of the secret mask-

ing F (O[i − 1]).

One possibility to proceed with chosen and known

input-output attacks is that the adversary can guess the

value of O[0] = E

(IV ) and apply linear or differen-

tial cryptanalysis for each of these guess. In that case,

we need to multiply the attack complexity of differen-

tial or linear cryptanalysis by 2

where B is the block

size of the block cipher E

. This greatly increase the

complexity of the attack.

The other way, is to sent the ﬁrst message session

and from the returned ciphertext, adaptively adjust

the plaintext for the next session (assume same IV).

This is so since from equation (2), the unknown data

(O[0]) is blockwise similar in both sessions. How-

ever after the 1

block of the 2

session, a differ-

ent ciphertext (from 1

session) will masked the 2

block of the 2

session. Hence the only practical at-

tack it to perform an adaptive blockwise chosen plain-

text attack with reused IV.

Note that in two IO-CBC sessions which uses the

same IV, the input and output differences are the same

as the plaintext and ciphertext differences at the ﬁrst

block. However, they will be different from block two

onwards. Therefore another way to perform differen-

tial attack is to form plaintext differences at the ﬁrst

block in many IO-CBC sessions with the same IV.

However, this is not feasible in practice because the

IV is randomly generated and not controlled by the

adversary while we will need around 2

IO-CBC ses-

sions with the same IV to perform differential attack

on DES.

Re-use of IV may pose a threat to OCB and

IACBC, in particular, differential attack can be ap-

plied on OCB since the input-output masking in both

sessions are equal and will cancel each other at ev-

ery block. Thus all the blocks of two OCB sessions

which uses the same IV can be used in a differen-

tial attack. For example, if a IO-CBC session trans-

mits 2

blocks of encrypted data, then we only need

= 128 sessions that uses the same IV to perform

differential attack on DES, which is much less than

SECRYPT 2006 - INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY

138

the 2

sessions needed in IO-CBC.

Thus IO-CBC increases the work required for dif-

ferential cryptanalysis as compared to OCB under

reused nouce condition.

4.4 Isomorphism to OCB

There are many other linear functions that the authors

have yet to research on to ensure a secure mode of

operation. However, IO-CBC and OCB share similar

features of masking both the input as well as the out-

put of the block encryptor using linear transformation

of unknown data.

Hence IO-CBC will be isomorphic to OCB if the

non-singular linear (in GF(2)) function F (·) in IO-

CBC is the masking function in OCB, F

(O[0]) =

· O[0] ⊕ O

′

[0]. Where γ

is the Gray’s code repre-

sentation of integer i and O

′

[0] is the encrypted result

of O[0].

From equation (2), we have:

F (O[i − 1]) = G(C[i − 1] · · · C[1]) ⊕ F

(O[0]) (5)

Where G(C[i − 1] · · · C[1]) is a linear function of

known values, and F

(O[0]) is the masking technique

used in OCB. Since G(C[i − 1] · · · C[1]) is known,

it does not provide resistance to any distinguishing

algorithm. Hence F

(O[0]) is the only masking in

IO-CBC, which is similar to OCB. So it is obvi-

ous that IO-CBC with linear function F

(O[0]) =

· O[0] ⊕ O

′

[0] is a general case of OCB.

Given the security proof of OCB (Rogaway, 2001),

we can be sure that IO-CBC with linear function (5)

will be at least as secure as OCB. Furthermore using

the provable security and authenticity in (Rogaway,

2001), we can be sure that IO-CBC can be extended

to a variant with both privacy and authenticity in a

single pass mode of operation.

5 ERROR PROPAGATION

When a legitimate user receives a ciphertext, he can

recover the plaintext by performing IO-CBC in re-

verse.

O[0] = E

(IV ),

O[i] = C[i] ⊕ F (O[i − 1]),

I[i] = D

(O[i]), D

is the decryption function.

M[i] = I[i] ⊕ F (O[i − 1]), i = 1, . . . , l.

If an error bit occurs at C[i] during transmission, it

will cause a bit error in O[i]. This will cause I[i] and

M[i] to be garbled. Similarly, O[i + 1] = C[i + 1] ⊕

F (O[i]) will have some bit errors because of bit errors

in F (O [i]). This will cause I[i + 1] and M[i + 1]

to be garbled. Inductively, we see that M[i], M[i +

1], . . . , M[l] will all be garbled. Therefore IO-CBC

has inﬁnite error propagation.

Thus IO-CBC is suitable for an environment where

we do not allow for any error in the received cipher-

text, e.g. we do not want the message to be tampered

with during transmission. The inﬁnite error propaga-

tion property of IO-CBC is a very good way to detect

whether a transmitted ciphertext has been tampered

with, by introducing a checksum as we shown a vari-

ant in Section 4.4.

Error propagation also provides more resistance to

birthday attack. In (Knudsen, 2000), the matching ci-

phertext attack is described as follows:

Fact 1 Consider an n-bit block cipher used in the

ECB, CBC or CFB mode. It is assumed that the plain-

text blocks are chosen at random from a uniform dis-

tribution. If s blocks are encrypted under the same

key, information is leaked about some plaintext blocks

with a probability of p

= 1 − (1 − 2

−n

)

s(s−1)/2

When s = 2

(n+1)/2

, this probability is about 0.63.

This attack basically tries to detect if there is a col-

lision in the plaintext blocks by observing the cipher-

text. E.g. for ECB, C

= C

⇒ P

= P

. In (Knud-

sen, 2000), it is stated that error propagation modes

are generally less prone to such an attack, this will

include ABC and IO-CBC.

Lastly, another advantage of error propagation is

to provide better diffusion for encryption operations

(Knudsen, 2000). Suppose the plaintext space has

low entropy, say each plaintext block can take only

s values where s is small. If we are using ECB

mode, then it is easy to deduce that the plaintext has

low entropy by observing the ciphertext. However,

if C

= g

, · · · , M

i−v

, C

i−1

, · · · , C

i−w

), then

any ciphertext block can take up to s

v+w

values. If

s < 2

B/(v+w)

then some B-bit values will never oc-

cur, where B is the block size. Hence in (Knudsen,

2000), the way to provide more diffusion is to make

v and w big or to construct a mode such that each ci-

phertext depends on all previous plaintext and cipher-

text blocks. When such a property is satisﬁed, it will

introduce inﬁnite error propagation mode as in ABC

and IO-CBC.

6 VARIANT WHERE THE

INPUT-OUTPUT MASK IS A

NONLINEAR FUNCTION

In IO-CBC, we have used linear functions for the

transformation F (·). The rational for using a linear

transformation is to reduce the computational over-

head of the masking. To prevent future attacks that

PROTECTING CIPHER BLOCK CHAINING AGAINST ADAPTIVE CHOSEN PLAINTEXT ATTACK

139

exploit the linear property of F (·), it might be use-

ful to replace it by an efﬁcient computable nonlinear

function.

Usually, the security of a block cipher against stan-

dard attacks like differential and linear cryptanalysis

is higher than required. For example, by the wide-trail

design principle of AES (Daemon, 2002), the maxi-

mum differential characteristic probability of AES is

(4/256)

= 2

−150

for 4 rounds, (4/256)

= 2

−300

for 8 rounds and (4/256)

= 2

−450

for 12 rounds.

However, we just need the characteristic differential

probability to be smaller than 2

−128

for protection

against differential attack. A similar estimate holds

for the strength of AES against linear cryptanalysis.

In that case, we can afford to reduce the block ci-

pher by one round and let F (·) be an unkeyed round

of the block cipher. E.g., for AES-256, we can reduce

it to 13 rounds and let F (·) be an AES round with-

out XORing with a subkey. The performance is still

equivalent to one block encryption per iteration be-

cause we are taking one round out of the block cipher

to form the function F (·). Therefore the overall efﬁ-

ciency of IO-CBC is one encryption more than CBC

where the extra work is for encrypting the IV.

As in the analysis of Section 4, this variant will sat-

isfy equation (1). Because F (·) is a nonlinear func-

tion, equation (1) cannot be simpliﬁed and F (O[i−1])

is an increasingly complex function of the secret

O[0] = E

(IV ) as i increases. Thus it is more dif-

ﬁcult for the adversary to deduce F (O[i − 1]) and

control the input I[i] to force a collision by choosing

M[i].

With respect to Joux’s FTG attack in (Joux, 2002)

or Sung’s key recovery attack in (Sung, 2003), it may

be difﬁcult to ﬁnd a linear combination of the output

mask F (O[i − 1]) which sums to a known value be-

cause the recursion of F (·) in equation (1) will result

in a complex highly nonlinear function.

7 CONCLUSION AND FUTURE

WORK

In this paper, we have introduced a new CBC-type

mode of operation called IO-CBC. We have shown

that it is as efﬁcient as CBC mode and provides pro-

tection against various adaptive chosen plaintext at-

tacks introduced in (Joux, 2002; Sung, 2003). It

also makes differential and linear cryptanalysis harder

than other modes of operation like ECB, CBC and

OCB. Tbe IO-CBC mode has inﬁnite error propa-

gation which makes it suitable for applications that

needs to detect occurence of any errors during trans-

mission. From section 4.4, we get a provable security

similar to OCB given that the linear function is simi-

lar to OCB. A useful problem for future research is to

establish the provable security of IO-CBC and a wider

class of linear function F (·).

Having conﬁdence that a variant of IO-CBC is iso-

morphic to OCB in section 4.4, another problem for

future research is to extend IO-CBC to a provable

variant, like IACBC and OCB, that does both conﬁ-

dentiality and authentication. Together with the inﬁ-

nite propagation property, tampering with transmitted

ciphertext will be easily detected.

REFERENCES

Alkassar, A., Geraldy, A., Pﬁtzmann, B. and Sadeghi, A. R.

(2001). Optimized Self-Synchronizing Mode of Op-

eration. LNCS 2335, Fast Software Encryption 2001.

Springer-Verlag.

Bellare, M., Desai, A., Jokipii, E. and Rogaway, P. (1997).

A Concrete Security Treatment of Symmetric Encryp-

tion. Proceedings of Foundations of Computer Sci-

ence’97. IEEE Press, 1997.

Biham, E. and Shamir, A. Differential Cryptanalysis of

the Full 16-Round DES. LNCS 740, Crypto ’92,

Springer-Verlag, 1993.

Daemon, J. and Rijmen, V. The Design of Rijndael: AES -

The Advanced Encryption Standard, Springer, 2002.

Golomb, S.W. Shift Register Sequences, Revised Edition,

Agean Park Press, 1982.

Joux, A., Martinet, G. and Valette, F. Blockwise Adaptive

Attackers: Revisiting the (In)Security in some Prov-

ably Secure Encryption Modes: CBC, GEM, IACBC.

LNCS 2442, Crypto 2002, pp. 17-30, Springer-Verlag,

2002.

Jutla, C. Encryption Modes with Almost Free Message In-

tegrity. LNCS 2045, Eurocrypt 2001, pp. 529-544,

Springer-Verlag, 2001.

Knudsen, L. Block Chaining Modes of Operation. Techni-

cal Report, Department of Informatics, University of

Bergen, 2000.

Matsui, M. The First Experimental Cryptanalysis of the

Data Encryption Standard. LNCS 839, Crypto ’94,

pp. 1-11, Springer-Verlag, 1994.

Matyas, M. and Matyas, S. Cryptography: A New Dimen-

sion in Computer Data Security, John Wiley and Sons,

New York, 1982.

Preneel, B., Nuttin, M., Rijmen, V. and Buelens, J. Crypt-

analysis of DES in the CFB mode. LNCS 773, Crypto

’93, pp. 212-223, Springer-Verlag, 1994.

Rogaway, P., Bellare, M., Black, J. and Krovetz, T. OCB: A

block-cipher mode of operation for efﬁcient authen-

ticated encryption. http://www.cs.ucdavis.edu/ rog-

away, 2001.

Jaechul Sung, Deukjo Hong and Sangjin Lee Key Recovery

Attacks on RMAC, TMAC, and IACBC LNCS 2727,

pp. 265-273, 2003.

SECRYPT 2006 - INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY

140