Cryptography Reference
In-Depth Information
can use (1) to determine
B
0
and
k
0
for every plaintext - ciphertext pair. You can
see that determining
S
2
from (1) represents the same problem as determining
S
3
from (2). We determine
S
2
and
S
0
analogously. Running a check based on
other plaintext - ciphertext pairs eliminates wrong solutions for
X
. If several
solutions still remain, we have to test with other methods, depending on the
problem at hand.
I wrote a demonstration program to this end and ran tests under UNIX (see
Appendix A.1,
algor/RC5a
directory). It is not even 400 lines long, includ-
ing overhead. The critical function is
solve X
, which solves equation (4) (as
described above); it's only 50 lines long. I admit having worked at this short
function for quite a while. Have a look at the source text and you will see why.
You don't need to understand
solve X
when using this program. You can
blindly feed it with some plaintext and the entire ciphertext — and the entire
plaintext will come out in a flash. The result is impressive: in all cases tested,
three plaintext - ciphertext pairs sufficed to find a unique solution, and the
computing time on a 133-MHz Pentium under UNIX V.4.2 was only 2 ms
(0.002 seconds)!
This attack doesn't make RC5 any weaker, though. It cannot even be mounted
against the two-round RC5, nor can it be mounted against the one-round variant
of the RC5a algorithm that will be discussed in Section 5.4.3. And yet, the
entire thing is no dry run as you will see in the next section.
Attacking Chip Cards
Helena Handschuh first presented a
timing attack
against RC5 in the 'rump
session' (where ideas and comments are suggested freely) at the EUROCRYPT
'98: an attacker measures the execution times of encryptions and tries to recover
information from them. I don't want to discuss the details here, because this
method will be discussed in detail in Section 5.10.
The result sounds alarming at first: once you have access to a chip card with
internal secret RC5 key, all you need is to encrypt about 8 Mbytes of cho-
sen plaintext (i.e., approximately 2
20
plaintext blocks); then you measure the
ciphering times to get hold of all subkeys. However, this method is applicable
only to certain 8-bit microprocessors, and even then, they can be thwarted with
little effort.
I find another type of attack much more dangerous: while having access to such
a card, why wouldn't one better use the 'hacker methods' by Anderson and
Kuhn, as described in Section 4.4.5? As a reminder: you mess up the processor
