On Wed, May 10, 2000 at 05:30:53PM -0400, Theodore Y. Ts'o wrote:
> Consider that block-swapping attacks can preserve the checksum even
> though the attacker doesn't know the underlying data.
That's why I also added:
> each 64 bit or (128 bit) block is enciphered with a different key.
In the theoretical point of view, a good encryption function is
undistinguishable from a random permutation of the message space.
Moreover, two instances of this function, with two different keys,
should not have any more relation between them than two random
permutation. Otherwise, it is called "related keys" and considered as a
valid attack (although academic).
AES candidates have been designed in order to achieve these goals. And
it appears that 3DES is also good in that respect. Actually, 3DES
might be a very good choice for what I intend because:
-- it has been well studied, by many smart people and for many years
-- in bitslice mode, it is efficient, with a free key schedule
-- it has 168 bit keys
About bitslice: the trick (rediscovered by Biham and Biryukov in
1997) is to calculate the function with bit-to-bit logic, as if
it was specialized hardware. So there is one bit of data in each
register/variable. Actually, if we have 64-bit registers, we have 64
parallel instances of 3DES, each running on its own data and with its
own key. Bitslice makes fixed permutations free: these are a routing
problem resolved at compile-time, not at runtime. So key schedule
becomes free, too, and it is easy to make each instance run with its
own key. S-boxes become rather expensive, but alltogether, bitslice is
a big win. Bitslice was used by distributed.net for their DES-cracking
challenge.
And I happen to write these lines on an Alpha machine: 64 bits per
register, and there are exactly 64 64-bit blocks in 512 bytes (a
harddisk sector). Just what was needed.
About the key diversification: each 64-bit block is numbered on, say,
40 bits (this leaves room for an eight terabytes filesystem). A simple
diversification is the following: xor this number with the 40 least
significant bits of the master key. It could be argued that, by doing
this, we provide the attacker up to 2^40 keys, so we might (intuitively)
reduce the cost of an exhaustive search by a factor 2^40. So what ? We
still have 128 "secure" bits, which is considered safe nowadays (I
personnaly think that 80 bits are sufficient, but 128 bits are some
sort of standard; AES required 128-bit keys).
I am rather confident in the fact that there is no security problem
in my scheme, although I am of course discussing it with other people
(this mailing-list is not my only source of information).
What I do not quite know is the feasibility of the implementation; my
two main questions are:
-- will 3DES be fast enough ?
-- will the checksum calculation expensive ?
To the first question I will soon be able to provide an answer. I have
been working on this sort of things (DES, bitslice...) for a long time
and the pieces are reassembling. About "fast enough": I mean 100 MB/s on
a recent Alpha machine. On a 10 MB/s disk, we could read and write to
the disk using only 10% of the cpu, which is acceptable as a default
setting.
To answer to the second question, I need the experience from the
filesystem-guys, who know how a filesystem is typically used, and
who are supposed to at least lurk in this mailing-list. Hence this
discussion.
It is my understanding that typical filesystem write usage is either
creating new files and filling them, truncating files to zero length and
filling them, and appending to files. For these operations, the checksum
cost is zero (in terms of disk accesses). This is not true for mmaped()
files (databases, production of executables...) but I think (and I beg
for comments) that this may be handled with a per-file exception (for
instance, producing the executable file in /tmp and then copying it
into place -- since /tmp may be emptied at boottime, it is pointless to
ensure data integrity in /tmp when the machine is not powered).
Any comment is welcome, of course. I thank you for sharing part of your
time reading my prose.
--Thomas Pornin
