[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
IDEA and timing attacks
John Kelsey <[email protected]> wrote in sci.crypt
>
> -----BEGIN PGP SIGNED MESSAGE-----
>
> [ To: sci.crypt ## Date: 08/24/96 03:11 am ##
> Subject: IDEA and Timing Attacks ]
>
> I'm still kind-of recovering from this year's Crypto conference, but
> I told several people I would post this. At the rump session this
> year, I presented an arguably practical timing attack on many
> implementations of IDEA. There are actually two attacks available,
> but one requires extremely fine timing results. After I gave the
> presentation, Willi Meier told me he had independently found the
> same results, and had implemented the full attack (which I hadn't
> yet done).
>
> There are two different attacks. The most practical is an
> adaptive chosen-plaintext attack, which requires about 5*n*2^{16}
> chosen plaintexts (read ``five n times two to the sixteenth''),
> where the parameter n depends on the precision of timings available
> and the timing variability of the implementation. The second attack
> is ciphertext-only, but requires timing measurements precise enough
> to detect the difference between a single multiply of a zero vs.
> nonzero value. It requires about 5*n*2^{16} values, as well.
>
> The basic idea behind the attack is as follows: in many
> implementations, a zero input into the multiply operation is handled
> by an if statement, and so does not cause a multiply instruction to
> actually be executed. The result on a 486 is that it is
> significantly faster to multiply by a zero rather than a nonzero
> value. This timing difference gives us a really nice way to learn
> information about the internal values of the cipher.
>
> This presentation is necessarily not very good, since I can't embed
> a diagram here. If you have a copy of _Applied Cryptography_, then
> turn to the section on IDEA (page 321 in the hardback version of the
> second edition). The diagram shows one round of IDEA, and then
> (after the ellipses) the output transformation.
>
> The chosen plaintext attack works as follows:
>
> 1. Build a run of n*2^{16} chosen plaintexts, by choosing a
> single value for X_1, and choosing n of each possible value for X_3,
> with X_2 and X_4 taking on values at random. Time the encryption of
> each batch of n plaintexts with the same X_3 value.
>
> 2. Choose a new value for X_1, and then build another run of
> chosen plaintexts exactly as above.
>
> 3. For each of these two runs, if the value of Z_5 is not zero,
> there should be a different value for X_3 that gives the lowest
> encryption time. (These are the values that force the input to the
> multiply with Z_5 to be zero.) Call these X_3 and X_3'. This gives
> us two equations in two unknowns, and we can solve for it with a
> 32-bit brute-force search. (There may be faster ways, as well.)
>
> (X_1 (*) Z_1) = (X_3 + Z_3)
> (X_1'(*) Z_1) = (X_3'+ Z_3)
>
> We now have recovered Z_1 and Z_3.
>
> 4. Let's call the input to the multiply with Z_5 A. We can use
> knowledge of Z_1 and Z_3 to force A to keep the same value. We then
> choose three new runs of chosen plaintexts, each containing 2^{16}
> batches of n plaintexts apiece. Each of these ensures that A and
> X_2 are kept constant, so that we wind up three difference values
> for A, X_2 and X_4 which correspond to zero inputs into the multiply
> with Z_6. This means that we wind up with three equations in three
> unknowns.
>
> (A (*) Z_5) + ((Z_2 + X_2 ) XOR (Z_4 (*) X_4 )) = 0
> (A' (*) Z_5) + ((Z_2 + X_2' ) XOR (Z_4 (*) X_4' )) = 0
> (A''(*) Z_5) + ((Z_2 + X_2'') XOR (Z_4 (*) X_4'')) = 0.
>
> This can be solved with a 48-bit brute force search (there are
> probably faster ways). We now have 80 bits of IDEA's key, and can
> brute-force search the remaining 48 bits.
>
> Note that this is actually an adaptive chosen-plaintext attack as
> described. I'm pretty sure this can be turned into a proper
> chosen-plaintext attack with some work, and I'll probably be hacking
> on this in the next few weeks, as time allows.
>
> The ciphertext only attack is simpler in some ways. The first 32
> bits are extremely easy to recover--find the average time to encrypt
> blocks with each value in their first and last 16 bits, and then
> solve for the subkey values that would be necessary for those
> multiplies to have zeros as their inputs. Next, we look for a
> correlation between low encryption times and the values for Z_3 in
> the output transformation that would result in zero inputs into the
> previous round's MA box multiply. Finally, we attack the second
> multiply in that MA box, using all four output values. The
> approximate computational difficulty is 2^{48}, as before.
>
> There are other timing attacks on IDEA. We gave one in our paper at
> Crypto this year (the one on related-key cryptanalysis of several
> ciphers, by Bruce Schneier, David Wagner, and me), and the
> related-key timing attack is where I got the idea to try a timing
> attack on the whole cipher.
>
> All timing attacks are implementation-dependent to some extent. On
> a Pentium, I suspect the timing attack will be considerably harder.
> (One person I discussed the attack with said he thought it would
> take longer to do the conditional branch for the if statement than
> to do the multiply, so we might have zero multiplies taking more
> rather than less time.)
>
> Most applications aren't really susceptible to timing attacks,
> because of the way they're used. In addition, chosen-plaintext
> attacks on block ciphers are pretty nicely thwarted by using CBC or
> CFB modes. It is probably also possible to implement IDEA so that
> it executes in constant time. I should point out that it is *NOT*
> enough either to add random delays (which fall out if you add more
> samples), nor to just get rid of the big timing difference with zero
> inputs (though that will make timing attacks somewhat more
> difficult). As long as internal (secret) information is being
> leaked by timing, the cipher is probably vulnerable to some kind of
> timing attack.
>
> --John Kelsey, [email protected] / [email protected]
> PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
>
> -----BEGIN PGP SIGNATURE-----
> Version: 2.6.2
>
> iQCVAwUBMh7GKEHx57Ag8goBAQEqGQQApXRQUMWz3gpJIwGrLbVhcgcpSMXyrq0g
> iTi2qjH7dJjmWugpLnbm18XHzOPZMKizdZ/gin1O3Rk89dXfqK4sIICwY3QmkwFR
> ZQ2My4mTUn27ibjAjZTDuvxLXnqqoOFRrMUTQGIlMTCZdBooSWrif+pTLQbIsoPr
> saHlDl2bWts=
> =tWIq
> -----END PGP SIGNATURE-----