RE: Wide-block Encryption Alternative
Shai,
Thanks for taking the time to reply to this. I spent some time
this week trying to write out a proof of security. The result
is what you might expect.
1. Yes, it's a little trickier than I first thought.
2. I did find some minor flaws in the algorithm that
need to be corrected.
Regarding your specific comments on security, I think I agree with
some and disagree with others. But it's probably a waste of time
to say much until I feel like I have a correct proof, or fail in
the effort. I may change my mind a few times between now and then.
> The main problem with this proposal (in my view) is the long keys. You
> need more than 512 bytes of key which makes the scheme problematic if
> you need to switch keys often (in buzzwords, it is less "key agile").
In order for this to be a problem, I would expect two conditions would
need to exist.
1. The working set of different keys is greater than 64.
2. More than 10% of the sectors being encrypted/decrypted use
a different key from the immediately preceding one done.
If either of these conditions is not met, the re-keying seems to be
quite inexpensive. (Numbers are of course arbitrary, but probably
the right order of magnitude.)
Initially, anyway, it struck me as unlikely that either of these
conditions, let alone both, would occur in storage applications.
Is there experience in the group or stated requirements that
would indicate the contrary?
> As for speed and gate count, I don't really know. My guess
> is that it would be fairly close to EME on "high end hardware" (maybe 30%
> this way or that) and slower than EME on "low end hardware". But this
> is only a guess.
Why do you think it would be slower on "low end hardware"?
If I have time, I will try to synthesize some representative
logic blocks and get gate counts. Although this will not be
highly accurate, it might give a little insight.
> The specific bounds that you get would be worse than for EME (maybe
instead
> of 7q^2/2^n you get 100q^2/2^n or even 1000q^2/2^n), but I don't think
> that we really care.
If I do more than 16 times worse than EME, I will consider this a failure.
I think I can do 8, but not sure yet.
- Thanks, Jim