~

QClF frames at 30 frame/s, sub-sampled in time by factors o f 4 (rates References

under 20 kbitls) and 3 (other rates) to generate 7.5 framels and 10 1 MALLAT, S.G., and ZHANG, 2.: 'Matching pursuits with time-frequency
frame/s, respectively. Coding was performed only on luminance dictionaries', IEEE Trans. Signal Process., 1993, 41, pp. 3397-3415
component in bit-rates that vary in the range 10-100 kbit/s. 2 NEVE R., and ZAKHOR, A,: 'Very low bit rate video coding based in
Note that in (2) and (3), there is a dependency on the parameter a. We matching pursuits', 1997, IEEE Tmns. Circuits Swt., 7, pp. 158-171
have verified experimentally that, for n in the range [0.5, 0.851, the 3 NEFF, R., and ZAKHOR, A,: 'Modulus quantization far matching pursuits
PSNR performance is quite insensitive to a. In our experiments, we video coding', lEEE Trans. Circuits Sjm yideo Technol.. 2000, 10,
have used an E = 0.56 for all cases. pp. 895-912
4 VANDERGHCYNST, E , and FROSSAKD, P: 'Adaptive entropy-constrained
Table 1 compares the average peak signal-to-noise ratio (PSNR) of
matching pursuits quantization'. IEEE Int. Conf. on Image Proccssing,
the original matching pursuits video encoder (MP) [2] with our 2001, pp. 423426
adaptation using generalised bit-plancs (MPGBP) for some rates. 5 CRAUER. M., DA SILVA, E.A.E, and RAMOS, E.c.: 'Convergent algorithms
Table 1: Comparison, in terms of PSNK, between two matching for successive approximation vector quantiration with applications to
wavelet image compression', IEE Pmc.. Vir. Image Signal Process.,
pursuits implementations
1999, 146, pp. 159-164
6 BELL. T.C., CLEARY, i . G , and WITTEN. I.H.: 'Text compression' (Prentice
Hall, Englewood Cliffs. NI, 1990)

Classes of impossible differentials of

advanced encryption standard
R.C.W. Phan
Recently, a class of gensralised four-round impossible differentials of
the advanced encryption standard (AES) was presented. The previous
work is extended and applies more flexibility to construct flio ncw
classes of impossible diticrentials of the AES

Fig. 1 shows thc variation o f the average PSNR with rate for both Introduction: Thc advanced encryption standard (AES) is a 128-bit
imolementations of the matchineI. nursuits encoders. We can see fmm block cipher with a 128-, 192- or 256-bit secret kcy [I]. A daca block
this Figure that the use ofthe gcneralised hit-planes scheme consistently of the AES is expressed as an array of 4 x 4 bytes with row and
imoroves the oerfomance ofthe matching_Dursuits
. . . for
encoder from 121 column indices, i, j (0, I , 2, 3 ) . The input block is passed through
all rates. In addition, this improvement increases with the hit rate. a round function which is itcrated 10 times. At the same time, the
Indeed our results are comnatible with the best ones in the literature, 128-bit secret key is input to a key schedule to obtain round keys for
that have been obtained using sophisticated adaptive shategics [3]. Note use in each round. Each round function consists of SubBytes, a
that the knee on the curves around 20 kbit/s is due to the increase of the nonlinear 8 x 8 S-box byte substitution; ShiftRaws, a cyclic shift of
frame rate from 7.5 to 10 fratne/s. each row by different byte offsets; MixColumns, a linear combination
of all 4 bytes in the same column; and KcyAddition. an exclusive-OR
*1 (XOR) o f the data block with the round key. Each round is identical
42- except that an extra KeyAddition is added before the first round and
Mixcolumns is excluded from the last round.
40-

38- .....
..
_
..........
......
.....
...
XOR patterns and huncuted differentials: Let a pair of AES . data
1 blocks P and P* differ in certain (active) bytc positions and are equal
5 36-
in athcr (passive) byes.
v)
a 31-
... MP (Mother) DeJinirion I ; An XOR pattcm is a 4 x 4 array that specifies the active
32- ...... MPGBP (Silent) and passive byte positions of a pair of AES data blocks P and P*
MP (Silent)
30- Consider the influence of the round hnction components on the
201: , , , , , , , , , dismbution of the active bytes in the XOR pattem. SubBytcs operates
on each byte independently hence it does not affect the XOR pattem.
10 20 30 40 50 60 70 80 90 100
rate, kbitk KeyAddition does not affect the XOR panem either because XORing
twice with thc mund key cancels out its effect. ShiftRows only shifts an
Fig. 1 Yarinfion of average PSNR wirh rale f i r Mother and Silml active byte to another position in the same row but docs not diffuse it
sequences over to other bytc positions. MixColumns causes an active byte to
Conclusions: We have proposed a novel algorithm far performing sprcad to all four byte positions in the same column. T I C input XOR
greedy decompositions on redundant dictionaries. Instead of generat- pattem and its corresponding output XOR pattern after i rounds of the
ing at its output a sequence of pairs comprising indenes o f atoms and AES are collectively known as an i-round truncated differential.
It is obvious that MixColumns greatly influences the behaviour of
-
corresmndine coefficients. as in the classical MP aleorithm, it only
mncatcd differentials as it causes the sole diffusion of active bytes.
generates a sequence of indexes of atoms. The results obtained are
vely promising, yielding a significant improvement over the classical Since MixColnmns operates on each column of the data block inde-
MP-based video compression algorithm [2]. pendently, it is sufficient to consider the XOR pattems of these
individual columns, which are called the column XORs. The distribu-
tion ofthe individual input and output column XORs of MinColumns is
0 IEE 2002 31 Jonuurv 2002 given in Table I [2]. The '1' in the column XOR denotes an activc byte
while a '0' denotes a passive byte.

R. Caetano, E.A.B. da Silva and A.G. Ciancio Phan and Siddiquk impossible differenlials: In [2], Phan and Siddiqi
(PEE/COPPElDELiEE/Uni"~~~idnde Federal do Rio de Jnneiro, constructed a class of gcneralised 4-round impossible differentials of
Cx. P 68504, Rio de Janeiro, RJ 21Y45-970, Brazil) the AES by concatenating two probabiliq-one truncated differentials
E-mail: eduardo@lps.ufrj.br such that they form a contradiction [3] in the middle, hcnce causing

508 ELECTRONlCS LETERS 23rd May 2002 Vol. 38 No. 7 7

an impossible differential. From Table 1, an input column XOR o f o n e Proof of Lemma 1: Consider an input XOR pattern with two active
active bytc always causes &I output column XOR of all active bytes, bytes whose indices satisfy condition (I). Then after ShiftRows, we
hence after two rounds, the truncated differential with an input XOR have an XOR pattern with an active byte in only two columns. At the
pattem of only onc active byte causes an output XOR pattem of all output of MixColumns, we have an XOR pattem with two columns of
active bytes. This truncatcd differential was used in the first two all active bytes and two columns ofall passive bytes. Moving on to the
rounds of the AES. It was further shown that by working from the second round the output of ShiftRows is an XOR panem with two
other end of a four-round AES, thcn with an input XOR pattern o f 4 , active bytes in each column. After MixColumns, we have an output
8, 12, 13, 14 or 15 passive bytes, then after two inverse rounds (recall XOR panem with at least three active bytes in each column, due to
that the last round excludes a MixCalumns), which i i a t thc output of Proposition I .
round two, the output XOR pattcm would not havc all active bytes.
This contradicts the result obtained from the first two rounds of the D@nifion 2: An impossible differcntial of the AES is defined as the
AES, and hence a class of four-round impossible differentials was wherc a is the number of active bytes in the input XOR
couple ( a , /l)
obtained. pattern that would never cause p a c t i x bytes in the input XOR panern
that would never cause b active bytes in the output XOR pattern in
Tn,o new c1asse.s of impossible d , @ w z t i a l s : The class of impossible certain byte positions.
differcntials in [2] were constructed by using the miss-in-the-middle Notc that our definition of an impossible differential vanes slightly
technique [3] in a somewhat rigid manner. The impossible diffcrential from that in [2]. This is because in our case, the active bytes in the
was obtained by having one XOR pattem of all active bytes and output XOR pattern play a more important role than the passive bytes.
another without all active bytes contradict in thc middle. In this
Section, we construct two new classes of impossible differentials by Theorem I : Therc exists a class of generalised 4-round impossible
using the same technique but in a morc flexible manner, by having differentials of the form ( 2 , 1 1 2 ) where the I denotes the choice of
XOR patterns which differ in the number of active bytes in each the number of active bytes, fl in the output XOR panem.
column contradict in the middle. We first make some new observa-
tions from Table 1, which are formulated in propositions 1 and 2. Prmf of Theorem I : We apply the two-round probability-one
truncated differential in Lemma 1 to the first two rounds of the
AES. We thcn consider from the other end, at the output of round 4, an
Table 1: Distribution of Input/Output Column XORs of
Mixcolumn input XOR pattcm with at most two active bytes whose row and
column indices i, j satisfy the condition:
(j + i) mod 4 # 6' + i') mad 4. where i # i' and j # j' (2)
Then, with no MixColumns in the last round, an XOR panem with only
one active byte in at most two columns is obtained afler going through
the inverse ShiflRows. In round three, after going through inverse
MinColumns, we have an XOR panem with at most two columns with
all active bytes while thc rest have all passive bytes. Going through
another inverse ShiftRows causes an XOR panem with at most hvo
active bytes in each column at the end of round 2. But the truncated
differential in the fin1 two rounds (Lcmma I ) specifies that the XOR
panem has at least three active bytes in each column at the end ofround
2, hence a contradiction occurs, causing a 4-round impossihlc differ-
ential.
There is another class of impossihlc differentials which is constructed
as follows:

Lemma 2: There cxists a probability-one truncated differential with

an input XOR panem with three active bytes whose TOW and column
indices i, j satisfy condition (1) and whose output XOR pattem after 2
rounds has at least two active bytes in each column.
iiin - - t - + + i i - + + # + # # .
~

Proof of Lemmo 2: Consider an input XOR pattem with three active

Ill1 - i r + a + + d a t + # t # # .
bytes whose indices satisfy condition ( I ) . Thcn after ShiftRows, we
- =o have an XOR pattem with an active byie in only three columns. At the
E 2 11255' output of MixColumns, we have an XOR pattem with thrce columns
+ 2 11255' of all active bytes and one column of all passive bytes. Moving on to

.=
# E 11255
0.984
@ =always
the second round, the output of ShiftRows is an X O R pattem with
thrcc active bytes in each column. After MixCalumns, we have an
output XOR panern with at least two active bytes in each column, due
*wri1ten as a mw for con,,enience to proposition 2.

Proposition I : An input column XOR with two active bytes in any Theorem 2: There exists a class of generalised 4-round impossible
position causes an output column XOR with at least three active differentials of the form (3, I ) .
bytes.
Proof o/ Theorem 2: We apply the two-round probability-onc
Proposirion 2: An input column XOR with thrce active bytes in any truncated differential in Lemma 2 to the firs1 two rounds of the
position causes an output column XOR with at least two active bytcs. ABS. We then consider from the other end, an input XOR pattem with
only one active byte in any position. Then, an XOR panem with only
one active byte also appears after going through the inverse Shif-
Lemma I : There exists a probability-one truncated differential with
tRows. In round three, after going through inverse MixColumns, wc
an input XOR pancrn with two active bytes whose row and column
have an XOR panem with only onc column with all active bytes while
indices i, j satisfy thc condition:
the rest have all passive bytes. Going through another inverse
6~ ) 4 # 6'- i') mud 4.
i mod where i # i' and j #j' (1) ShiftRows causes an XOR pattcm with only one active byte in each
column at the end of round 2. This contradicts with the truncatcd
and the output XOR pattcm of which after two rounds has at least three diffcrcntial in thc first two rounds (Lemma 2), hence causing a four-
active bytcs in each column. round impossible differential.

ELECTRONICS LETTERS 23rd May 2002 Vol. 38 No. 1 1 509

 ~

Conclusion: We have presented two new classes of Sour-round Electronic filters for time-constant extraction: In 151.
. . the problem
. US
impossible differentials of the AES by applying the miss-in-the- fitting measured data on a linear combination of exponential functions
middle technique in a more flexible manner. These can be used in is solved by basis orthonormalisation. The solution is cast into an
an impossible differential cryptanalytic attack on reduced round adaptive filtering operation.
variants of the AES. Fig. 1 shows the architecnrre of the filter. The part drawn in
solid lines refers to extraction of n = 2 exponential components only.
Extension of the scheme is suggested by dashed lines.
0 IEE 2002 6 November 2001
Electronics Letlers Onlim No: 20020347
Dol: 10.1049/e1:20020347
R.C.W. Phan (Swinburne Samwuk Institute of techno lo^. 1st Flour,
State Complex, Sarowok, 935 76 Kuching, Malaysia)
E-mail: rphan@swinbume.edu.my

References
1 National Instihlte of Standards and Technology: 'Drafi FlPS for the
..I, 2s , -1
r
_''

ABS', 2001 V
2 and SlUUlQU, M.U.: 'Generalized Impossible Differentials of
PHAN, R.C.W.,
...
Advanced Encryption Standard', Electron. Let., 2001.37, (14), pp. 896- Fig. 1 Archilecture of oduptivrfilter
898
3 BIHAM. E., BlRYUKoV A,, and SIIAMIR, A,: 'Miss in the Middle Attacks on Transfer fwctions shown in hones
Idea and Kihufu'. Proceedings of Fast Software E n c ~ p t i o n'99, 1999, Dashed boxes suggest extension (0 order n greeei than NIo
pp. 124-138, (LNCS 1636)
The data signal d(t) must be reversed in time, and a first approxima-
tion of time constants {I,), i = 1, . . . ,n chosen. Functions

Time-constant extracting filters for fast gas

identification in electronic noses
P. Accettola, M. Balsi, A. D'Amico, C. Di Natale, and
A. Macagnano and E Sortino
Electronic nose recognition of gases is addressed by extracting time
constants of sen~orresponse. Based on a fit of such responses on a for i = 1,. . . ,n are defined, and filter output sampled at t = O (note that
proper orthogonal basis, a filtecng is introduced :ha1 yields the desired
result in real-lime, significantly earlier than the steady-state. Expee- operation of the filter is started at I = - r; where Tis the total length of
ments proved the effectiveness of the approach. data signal acquired). Outputs are then used to compute

Introduction: Electronic noses (EN) [I] are arrays of gas-sensitive

devices aimed at identifying volatile compounds. To this purpose,
suitable feanrrc extraction must be performed on the data collected on
exposure of the sensor array to an unknown gas. Mast EN applica-
tions have been based on the use of steady-state response. Howsvzr,
and polynomial
chemical sensor response may be slow. Dynamic features of the signal
not only improve detection performance, but speed it up considerably S" + h,s"-' i..+
. h,s +
h,
(21. Current solutions employing transient response parameters
normally require complicated analysis of the whole data set, so that is built with the resulting coefficients. New estimates of time constants
in any case it is necessary to wait for the steady state, and to use are taken as the opposites of the reciprocals of the mots is,) of this
complex architectures and algorithms, owing to the large number of polynomial (zi= -I/?,), and the procedure is iterated until the change
parameters involved. in estimates is small enough. Generally, a very small number of
In this Letter, we focus on the early recognition of gas by applying iterations are sufficient.
adaptive filtering tn transient response, without waiting for the steady That the signal is time-reversed and filtered several times, is not a
state. The basis for our work is the observation, both theoretical and problem. In fact, we can resort to digital storage and filtering of the
practical, that the adsorption dynamics of a single gas species is quite signal itself. The operation time of the electronics is in any case
accurately modelled by a first-order differential equation, so that negligible with respect to reasonable sampling intervals of the sensor
response has the form of a damped exponential [3]. For a given output, so that the whole iterative filtering process can be easily
sensor, the time constant of the evolution, depending on the gas performed within the time between two samples, and the estimation
under test (and independent of concentration when the adsorption is repeated with increased accuracy evety time a new sample is acquired.
diffusion-limited) is an optimal candidate for early gas quality estima-
tion. When N gases arc present on the sensor the system is not
completely linear, nevertheless the sensor response .s(1) can be consid- Experimental results: We collected the data from a sensor array [ 6 ]
composed of seven quartz microbalances, located in a constant
ered as a summation of exponential terms [4]:
temperature chamber. Active films are porphyrins and cavitands.
, " .
Samoline freuuencv was 0.1 Hz.
I

We started by measuring rcsponse to ethanol and isopropylic alcohol

. . .
pumoed seoaratelv. in the chamber. which was flushed each time with
where time constants iidepend on the adsorption affinity of the given synthetic air. To check the hypothesis that each gas would contribute
K ~ and
S sensor. and parameters A , also depend on ear conccntration. anc time constant, wc tried filters for one, two and three time constants
- The problem of fining a sum of real exponentialfunctions to data is and checked conditioning af the computation (in particular, of the
an ill-posed problem, owing to the basis not being orthogonal. In this matrix of a parameters), and variance of the estimated time constants.
Letter we solve the problem of achieving a significant fit by real-time Comparing the results for one and two time constants, we observed that
filtering, obtaining a reliable set of time constants that allows recag- in the second case variance of the two estimates was reasonable (one or
nition of different gases. two orden of magnihlde smaller than the man), and that the larger of

510 ELECTRONICS LETTERS 23rd May 2002 Vol. 38 No. I 1