> From: Shai Halevi
>
> Mart, which document are you referring to? The last draft (dated Dec-20
> 2005) doesn't have section 5.2.1 and doesn't describe any optimizations.
I'm referring to the only public version available on the web [LRWAES] from
August 6, 2004. Quite evidently this is an ancient revision.
> Then, you initially compute some-number * K2 using a full multiplication.
Can this be done more efficiently than the full multiplication algorithm
described in Algorithm 1, section 5.1 in [LRWAES], page 12
(where the worst-case cost is 128 + 128 xors and 128 right shifts
of 128-bit blocks)?
> [Comments on key derivation function and re-keying cost]
First, let me point out that I did not intend to propose KDF to be part
of the
standard. But implementations -- particularly software-based -- *may*
want to
use a KDF as unique sector keys are an additional layer of protection
against
cryptoanalysis. Thus at least the cost of multi-key mode versus single-key
mode should possibly be considered when evaluating algortithms.
As Laszlo mentioned, AES re-keying is (designed to be) expensive -- but
it's a
speed/security tradeoff decision best left to the implementer. Unique
sector
keys are used in e.g. GDBE [Kamp03] (which, by the way, is a DARPA-sponsored
project). The rationale is also given in that document. Implementers may
extend the key scope to several sectors to lessen the re-keying cost.
The usefulness of unique strong sector keys is obvious (harder
cryptoanalysis,
protection against copy-paste attacks, ...), but let me put it in
context. There is a recent paper [PG05] that
describes a distinguishing attack on EME/CMC with 2^64 chosen plaintext
sectors. (Note that this does not mean that EME/CMC are insecure, just that
the security bounds already given in EME/CMC specs [EME, CMC] are
tight.) The
idea is to create a sector-wide collision in two ciphertext sectors from a
collision in the first block and attack on the mixing layer.
The attack on CMC described on page 8 of [PG05] slides would not work if
unique sector key generation was part of the algorithm. Even though PPP_1 =
PPP'_1, the last blocks PPP_m and PPP'_m will be different if the keys
for the
respective sectors are different, hence the masks M and M' are also
different
and the collision of the first block will not propagate through to other
layers or other blocks. Same holds for EME.
But KDF is not a panacea. On the contrary, it can have adverse effects
if the
generated keys are weak or related.
In a tweakable scheme, the tweak can be used in key generation. E.g.
given a
global key GK and plaintext sector with index I that will be used as the
tweak, the sector key K_I can be calculated as
e_GK(2^128 - I) = K_I,
where e_GK is AES keyed with GK. The keys are unique, unrelated and
strong (in
the sense of a prp). This is just an example, there should be well-defined
criteria for such a function so that candidates can be evaluated properly.
Multiplication in GF(2^128) may possibly be utilized instead of the cipher
call.
--- Side note: wiki for collaboration
In the light of recent heated discussions -- don't you think that the
current
mailing list based collaboration is somewhat inefficient and becoming a
little
hard to handle? Maybe a wiki should be considered as an additional tool for
working with standard drafts and proposals? The mailing list would still
serve
as the main hub of discussion, but larger texts that may need further
revising
and parallel collaboration would be stored in the wiki. The wiki would
hopefully continue to evolve after the SISWG project ends.
Mediawiki (the wiki engine behind www.wikipedia.org) is an excellent,
free wiki, providing support for
- LateX syntax for entering formulae,
- authentication and authorization control,
- fine-grained editing of page subsections,
- other standard wiki tools like revision history, diffs etc.
Feature list: http://meta.wikimedia.org/wiki/MediaWiki_feature_list
--- References
[LRWAES] Draft Proposal for Tweakable Narrow-block Encryption, a SISWG
draft.
August 6, 2004.
http://www.siswg.org/docs/LRW-AES-10-19-2004.pdf
[CMC] Shai Halevi and Phillip Rogaway. A Tweakable Enciphering Mode.
http://eprint.iacr.org/2003/148
[EME] Shai Halevi and Phillip Rogaway. A Parallelizable Enciphering Mode.
http://eprint.iacr.org/2003/147
[GBDE] Poul Henning Kamp. GEOM based disk encryption. BSDCON'03.
http://phk.freebsd.dk/pubs/bsdcon-03.gbde.paper.pdf
[PG05] Raphael C.-W. Phan and Bok-Min Goi. On the Security Bounds of
CMC, EME, EME+ and EME* Modes of Operation. ICICS 2005.
The full article of [PG05] is not freely available:
http://dx.doi.org/10.1007/11602897_12
However, there is a session paper that conveys the main idea:
http://www.icics2005.org/ICICS'05/ICICS%2012-DEC/session%2010/1%20ICICS%2005%20EME.pdf
