Brian Gladman and Hal Finney have been comparing test vectors and discovered a problem in EME-2 with case where there is only one 16-byte block. The spec is a little ambiguous in this case, and Hal and Brian have proposed some changes to correct this issue (see forwarded message below). Note that Shai is still working on the proposal text, so this is just a rough draft.
There is also some inconvenience in the way that the EME-2 key structure is defined. A proposal is to change the ordering so that the fixed size key comes first and the variable length key comes second so that it can be more efficiently implemented within a C structure.
Please let the group know if either of these changes break existing implementations and we can try to find other ways around these issues.
---------- Forwarded message ----------
From:
Brian GladmanDate: Thu, Oct 16, 2008 at 2:19 AM
Subject: Re: EME-2 Implementation
To: Hal Finney
Cc: Shai Halevi, Matt Ball, Fabio Maino
Hal Finney wrote:
> Studying the spec, it looks to me like most of the problems were in
> some optimizations I included in order to avoid the need to
> dynamically allocate memory in the pseudo-code, or to pre-allocate
> large arrays big enough for the largest possible plaintext. However
> there is one line in the pseudo-code which should probably be changed:
>
> if len(Pm)<16 then
> Cm = Pm ⊕ (MM truncated to len(Pm) bytes)
> CCCm = Cm | 0x80…0 // pad Cm to 16 bytes
> else if (m-1 mod 128 > 0) then
> M = Mult-by-alpha(M)
> CCCm = PPPm ⊕ M
> * else CCCm = AES-Enc(Key1, M1⊕PPPm) ⊕ M1
> CCC1 = MC1 ⊕ CCC2 ⊕ … ⊕ CCCm ⊕ T_star
>
> The last "else" clause should be protected with "else if m > 1 then".
> We don't want to do that extra encryption for 1-block messages, but as
> written, it happens. Now arguably the next line undoes the effect of
> this line, but still at a minimum it is unnecessary and confusing.
>
> The same construction is found in the decryption pseudo-code.
>
> I think these are probably the only two changes needed for correctness.
>
> I don't know if Brian had any other insights into parts of the spec
> which are ambiguous?
Hi All,
Shai and I have been exchanging emails on exactly this and I hope that
he will shortly be able to make a proposal for changes to the pseudocode
so that the last block is no longer a special case when m is greater
than 1. I will leave Shai to distribute the revised proposal as he is
working on the master - but I much prefer it.
> Brian also suggested that we re-order how we split the key up into
> subkeys, so that the variable-sized piece is at the end rather than
> the beginning. I have no objection to that. If Shai agrees, I can
> update the reference code, and either he or I can provide the few
> changes necessary to the draft spec.
I would like to see this change as it fits in with common practice in C
and C++ and hence makes sense given the widespread use of these two
languages.
If you folks can confirm acceptance (or rejection) of this (in whatever
way that you do such things!), I will then make any necessary changes
and provide draft test vectors accordingly.
best regards,
Brian