Hi Matt,
On Dec 21, 2005, at 3:20 PM, Matt Ball wrote:
Sorry for the long e-mail, but there are some important security
issues with LRW that we need to look at before finalizing the
standard. These issues won't necessarily preclude using LRW, but I
think it's important to know how NOT to use LRW.
Abstract:
This document discusses ways to attack LRW through algebraic
weaknesses in the Galois Multiplier. This attack becomes strong if
Key2 (K2) looks similar to the plaintext (e.g. if K2 is an ASCII
password). The result of this attack is to leak 128-bits of
plaintext for each detected collision (similar to ECB mode). A
covert channel within LRW is discussed. Lastly, an alternative
mode is proposed that eliminates these weaknesses.
Alternative mode:
I've attached a picture for a slightly different tweak mode that
replaces the Galois multiplier with a second AES engine. Has
anyone seen a mode like this? In particular, is there any known IP
claims to this mode? (I do not make any claims myself)
the original LRW paper proposed a mode that used two block cipher
invocations per block of plaintext, one to produce the tweak T, and
the other to compute C = E(K, P + T) + T. AFAIK the LRW authors did
not patent their work - someone asked Moses Liskov about patents at
the Crypto conference, and he said that they had not filed for a
patent. He also didn't rule out doing that in the future, but of
course at that point overseas rights were gone (since disclosure
preceeded any potential filing). Of course, anyone using LRW or a
mode like it needs to be aware of the OCB patent.
I'm sending this out because it looks like LRW can leak information
if the KEY2 looks similar to the plaintext. We may want to add an
alternative mode if people want a higher security level.
Here are some advantages of this alternative mode:
- Using I = 0 is secure (This is also true with LRW if Electronic
Code Book mode is secure)
- Knowing the Tweak (T) does not help in recovering Key2 (whereas
in LRW, knowledge of T completely reveals Key2)
- It is possible to implement this using less hardware by reusing
the AES engine. The throughput would be half as much, but this may
not matter with laptop hard disks.
- Detection of collisions becomes significantly harder
Concerning LRW mode:
There is a possible security problem if Key2 is poorly chosen. In
particular, if Key2 has low entropy, low hamming weight, or long
runs of binary 1s or 0s, (or is otherwise systematically non-
random) it then becomes possible to detect situations where the AES
engine encoded the same data (thus revealing 128-bits about the
plaintext). The problem is especially bad if Key2 is a relatively
short ASCII password. In this case, the Key2 would look very
similar to ASCII data on the hard disk, making it easier to create
collisions with the plaintext.
Recovering Key2 in LRW:
What happens if we take the XOR of two ciphertext blocks?
Generally speaking, we should get a pseudo-random number. However,
what happens when the AES engine encoded the same data? By XORing
the cipherblocks, we completely remove the output of the AES engine
(which was the same) and are left only with data relating to Key2
(K2) and the IV (a.k.a. I). Let's take a closer look at this:
(Let '+' be bitwise XOR, and '*' be a 128-bit Galois Field
multiply; C? = Ciphertext, K2 = Key2, I? = IV, P? = plaintext;
substitute '?' with 1 or 2):
From the LRW specification, we get these equations:
C1 = (K2 * I1) + AES(K1, K2 * I1 + P1)
C2 = (K2 * I2) + AES(K1, K2 * I2 + P2)
Now, assume that the output of the AES engine is the same for both
these equations. Here's what happens when we add the two lines:
C1 + C2 = (K2 * I1) + (K2 * I2) + (AES1 + AES2)
C1 + C2 = (K2 * I1) + (K2 * I2) + 0 (output of AES1 and AES2
matches)
C1 + C2 = K2 * (I1 + I2)
(distributive law for finite fields)
Before going any further, take a look at the last line: The sum of
two ciphertexts involved in a collision equals Key2 times the two
Is XORed together. Now, let's assume that we are incrementing the
least-significant digit of I each time. In this case, (I1 XOR I2)
= 1, assuming I1 is even and I2 immediately follows I1. Note that
the XOR operator will cancel-out anything within I1 or I2 that
matches (e.g. the drive number).
IMPORTANT POINT: This equation holds even if we use the upper bits
of I for a drive number or other unique identifier.
So what this means is that for every other consecutive pair of
ciphertexts, we get this equation:
C1 + C2 = K2 * (1) = K2
It then becomes trivial to recover K2.
Now, let's looks at what happens when K2 has low hamming weight
(i.e. low number of binary 1s). In general, taking (I1 + I2) will
also have low hamming weight (this is because we don't vary the Is
very much). Because of the nature of the 128-bit multiplier, the
result of K2 * (I1 + I2) will also have low hamming weight. This
is especially true if the most-significant bits of K2 are zero. In
this case, we may not even need to take the modulo of the primitive
polynomial after expanding the multiplication. Even if we did, the
generator polynomial itself has low hamming weight and will not add
too much to the final result (especially if I1 + I2 only has 1 bit
set).
In this case, it becomes relatively easy to detect collisions
within the AES engine by performing statistical analysis on all the
combinations of the ciphertext blocks. If we want to get more
sophisticated, it would be possible to completely eliminate the
effects of the Galois multiply altogether by dividing each
ciphertext sum by (I1 + I2):
Compute (C1 + C2) * (I1 + I2)^-1 = K2
Since I1 and I2 are known for each cipher block, this computation
becomes straightforward. In dedicated hardware, it could be
possible to compute the inverse of I1 and I2 in about 128 clock
cycles through successive squaring. Frequently, (I1 + I2) will
result in the same value, so it should be possible to precompute
all the most common values, making a software-based attack feasible.
LRW Collisions:
Now, for this attack to be useful, it has to be somewhat likely
that we get a collision. A first guess would be to say that we
wouldn't start getting collisions until the birthday limit of the
cipher, which is around 2^64 ciphertext blocks (128 bits / 2).
However, this is assuming that the input into the AES engine is a
totally random number. In practice, this is not generally true.
In fact, the chance of a collision greatly increases when K2 looks
very similar to the plaintext (or rather the XOR of two plaintext
blocks). Let's take the example of using an ASCII password for
K2. Furthermore, let's assume that the harddisk mostly contains
ASCII characters.
How do we create a collision? That is, how do we make the inputs
of the AES engine equivalent? Here is the equation for the input
into the AES engine:
AES(K1, K2 * I + P)
For a collision, we need an I and P that match this equation:
AES(K1, K2 * I1 + P1) = AES(K1, K2 * I2 + P2)
K2 * I1 + P1 = K2 * I2 + P2 (if the outputs of AES match, the
inputs match)
or
P1 + P2 = K2 * I1 + K2 * I2 (rearrange)
P1 + P2 = K2 * (I1 + I2) (distributive law)
Interestingly, we get that (I1 + I2) term again. Keep in mind that
this will generally have low hamming weight, making it so K2 * (I1
+ I2) will also have low hamming weight. In the case where I1 and
I2 are consecutive, we get P1 + P2 = K2 (because I1 + I2 = 1).
If P1, P2 and K2 are all ASCII strings, the average entropy will be
much lower than 128 bits. Some studies show that text contains
about 1.5 bits of entropy per byte. If this is the case, we could
expect a total entropy of about 1.5 bits * 16 bytes = 24 bits. The
birthday attack would then succeed after about 2^12 = 4096
ciphertext blocks.
In practice, there's probably more entropy than 1.5 bits. However,
if we say there is 4 bits of entropy per character, our birthday
limit just went down from 2^64 to 2^32. It would be quite
reasonable for a harddisk to contain 64 GB of data to make this
attack work.
Obviously, there is a lot of hand waving here. We would probably
want to do a study to see what the real numbers look like.
Here's the bottom line:
If K2 resembles the plaintext, it becomes possible to attack the
data well below the theoretical birthday limit.
Ideally, the security of a cryptosystem should be completely
independent of the data patterns. This is true of both CBC and CTR
modes. ECB falls flat on its face in this regard. It looks like
LRW has some of the same characteristics as ECB.
That's an interesting analysis. However, if the key is chosen
uniformly at random, then there are no issues with LRW, right? So
the concern could be alleviated by requiring that keys be uniformly
random. Any mode of operation is going to have problems if its keys
are low-entropy ASCII strings. If we need to assume that the user
has chosen K2 poorly, then we ought to expect that they have not
chosen K1 well either. In that case, it is not clear that LRW fails
in a way that's more spectacular than any other mode would, AFAICT.
In practice, if there is a desire to use password-based keys, then
I'd suggest that a dedicated password-to-key function be used (PKCS#5
or HMAC, for example). This is a good idea for any system that
admits passwords, though of course it is getting into the subject of
key management (which the WG should probably start formal work
on :-) Alternatively, for LRW, the mode definition could be modified
so that K2 is derived from K1, similar to what GCM, CMAC, and some
other modes do.
David
Covert Channel with LRW:
If an application is running on the host computer that has
knowledge of K2, it becomes possible to create a covert channel by
writing blocks that intentionally create collisions. This is done
by writing blocks with the relationship P1 + P2 = K2 * (I1 + I2).
If several blocks are written in this manner, it becomes possible
to detect this using the methods outlined above. However, in this
case, it doesn't matter if K2 is strong or weak because it's
possible to write several consecutive blocks that contain
collisions. The attack algorithm would then search for consecutive
blocks that have collisions. Using this covert channel, it is
possible to send binary information by either writing blocks with
collisions or without. It might even be possible to encode K1 in
this manner, causing a total loss of security.
Notes on alternative mode:
The alternative proposed mode does not have the shortcomings
mentioned above. Since we have replaced the Galois multiplier with
a second AES engine, we are now working with strong pseudorandom
data for the tweak value. None of the simple algebraic properties
hold. The birthday limit returns to 2^64 blocks because the output
of the second AES engine is random. Furthermore, if it was somehow
possible to recover the Tweak value (T), this would not reveal Key2
(K2). Lastly, there are no weak values for I to worry about
(assuming AES is indistinguishable from an ideal cipher).
Let me know what you all think.
Matt Ball
Embedded Software Engineer
Quantum Corporation
4001 Discovery Drive, Suite 1100
Boulder, CO 80303
(720) 406-5766
<LRW_Alternative.jpg>
