Hi All,
I just wanted to follow up on my previous e-mail with some more comments on
LRW. These are some concerns that should probably be addressed in the 1619
document.
Security Level of LRW
---------------------
I think the 1619 spec. needs a little better definition of the security level.
Currently it just states that "It is proven in [LRW02] that this mode indeed
achieves the stated
security goals, assuming that the underlying AES block cipher is secure". What
is this security level? It would be worthwhile to explicitly outline the
difficultly of acquiring plaintext and indicate the amount of plaintext that
will be leaked in each instance.
For example, AES-256 in CTR mode will leak about 1-bit of plaintext after about
2^64 blocks [Ferguson and Schneier, "Practical Cryptography", section 5.8.2].
CBC mode will on average leak about 128 bits of plaintext after 2^64 blocks
[same reference]. ECB mode leaks 128 bits of plaintext every time two 128-bit
blocks of plaintext match (which is a huge amount of plaintext information).
For all these modes, the attacker can extract all the plaintext by a
brute-force attack on the 256-bit key (which would minimally take the energy of
around 100,000 supernovas or so, unless quantum computers catch on).
>From looking at LRW mode, it looks like it will probably leak less information
>than ECB mode, but will likely leak more information than CTR mode, and
>possibly even more information than CBC mode.
As outlined in my previous e-mail, LRW mode will leak 128 bits of plaintext for
every detected collision. Ideally, this wouldn't happen until around 2^64
cipher blocks, but a poor choice of K2 could increase the probability of a
collision.
Theoretically, the birthday limit could even be reduced with a perfectly random
K2, a certain percentage of the time. For example, there is a 1 in 2^16 (1 in
65536) chance that the most significant 16 bits will be zero for a perfect
random number. In this situation, the birthday limit could be reduced by as
much as 8 bits (from 2^64 to 2^56) depending on the characteristics of the data
on disk. Again, there's a little hand waving, but the important point is that
LRW will probably not be able to achieve the ideal birthday limit of 2^64 for
some values of K2 that occur normally. In this sense, LRW can leak more
information than CBC. For practical purposes, this may not matter, but it is
something to be aware of.
(Can anyone prove that the birthday limit of LRW is 2^64 blocks with a random
K2? If not, what is the likely birthday limit?)
Writing K2 to Disk
------------------
There is another security concern that should be outlined in the 1619 spec:
Writing K2 to the disk. Even if K2 is a perfect random number, it becomes
possible for an attacker to identify K2 if it is immediately preceded or
followed by 32 bytes of zeros. If the alignment is correct, then this will
cause a collision. If the attacker knows the location of K2 on the disk, it
then becomes possible to recover K2. Alternatively, if K2 is written in
multiple locations on the disk (followed or preceded by zeros) it could be
possible to determine K2 by computing (C1 + C2) / (I1 + I2) for all cipher text
block pairs, then look for a collision.
It's probably a good idea to mention in the specification that the user should
not write K2 to the disk. However, in practice this becomes very hard to
enforce. With the presence of a swap-file, it is quite possible that K2 could
be unknowingly written to disk if it ever exists in RAM. There is no good way
for an application to control this since the operating system controls the swap
file. Additionally, if the computer writes K2 to a file, then deletes the
file, it is quite possible that the file still exists on the disk. Even if the
application overwrites the file first, it could be possible that the hard disk
had to migrate data from a bad sector, leaving the original data on disk.
Modification attack with K2
---------------------------
The 1619 spec should probably mention some of the exploits possible if the
attacker acquires K2. In particular, it is possible for the attacker to
(somewhat) arbitrarily modify plaintext. This is accomplished by creating a
collision with another known plaintext on the disk. As you may recall, if two
blocks have a collision, the following equality is true:
P1 + P2 = K2 * (I1 + I2)
or
P1 = P2 + K2 * (I1 + I2)
The new cipher block can be created using this equation:
C1 = C2 + K2 * (I1 + I2)
As long as there are enough cipher text blocks, it could be possible to find a
cipher block with the appropriate pattern. Assuming that some of the bits are
"Don't Care", the probably of a controlled modification could be increased. If
the modification has low entropy relative to K2 an other plaintext blocks, the
probably could also be increased.
If the attacker knows of several probable values for K2, it could be possible
to make several modifications, hoping that one of them results in a collision.
Even if the integrity of the data is protected by a CRC, it is possible to
modify both the plaintext block and the corresponding plaintext CRC. The
likelihood of finding the proper collisions goes down significantly, but it is
still possible.
Derivation of K2
----------------
I think David McGrew had a good idea about deriving K2 from K1. By using a
strong cryptographic function to create K2, we wouldn't have to worry about the
user shooting themselves in the foot by using a plaintext password.
It would probably be a bad idea to create K2 by passing all-zeros through the
AES engine (using the same algorithm as GCM) because 'all-zeros' is a possible
input in the AES engine during normal operation. Maybe it would be possible to
use a hashing function that uses K1 and produces K2. This would be good if K1
was 256-bits long. However, if K1 is only 128-bits long, a hashing function
would reduce the entropy of K2 by about 2/3 of a bit. It seems like it would
be acceptable to have 127.3 bits of entropy for K2, but this would be a
judgment call based on the required security level. Any thoughts?
Keeping IVs Different Across Different Vendors
----------------------------------------------
Has anyone thought about the implications of two different vendors accidentally
choosing the same IV, then the user using the same key on both hard disks?
There was some talk about using a unique vendor ID, along with a drive serial
number. Did that idea go anywhere? Or is the idea to allow the users to
compromise the security by using the same key on multiple drives? Personally,
I think there should be some protection to the user if they use the same key on
multiple drives. This is the same problem that we need to address in the
1619.1 group, as well.
More Comments on the LRW Alternative Mode (LRW-ECT)
---------------------------------------------------
I wanted to revisit the alternative LRW mode and propose it as a stronger
alternative to the current LRW mode, assuming that a user wants a stronger
security level.
I haven't yet heard of a name for this mode, so I would like to propose calling
it "Electronic codebook mode (ECB) with Counter (CTR) Tweak", or ECT for short.
Since this is an LRW derivative mode, a complete name would be "LRW-ECT".
Here is the definition for ECT mode:
(C = Cipher text block, P = Plaintext block, T = Tweak, I = Initialization
Vector, K1 = Key1, K2 = Key2)
C = T + Encode(K1, T + P)
where
T = Encode(K2, I)
To recover the plaintext, just reverse the operation:
P = T + Decode(K1, T + C)
where T is the same as for encoding.
This mode (LRW-ECT) does not have the weakness outlined above for normal LRW
mode with Galois multiplier. In particular, the following is true:
- In ECT mode, it is safe to write K2 to disk
- The birthday limit goes back to 2^64 blocks because the output of the AES
engine is completely random, unlike the output of the Galois multiplier.
However, I believe it is not statistically possible for an attacker to identify
such a collision, so there is no leaked plaintext.
- The best way for an attacker to recover K2 in ECT mode would be to mount a
known plaintext/cipher text attack on AES. However, if AES is an idea block
cipher (which it currently seems to be, practically speaking), the best attack
would be a brute force attack on the key space. Conversely, in LRW mode, it is
trivial to recover K2 if the Tweak value is recovered.
Obviously, regular LRW mode is probably good enough for most consumer needs.
However, if there was a need to encrypt highly sensitive information, and extra
hardware is not a problem, then the LRW-ECT mode would provide a provably
higher security level.
-Matt
