[Cryptography] Justify the sequence of operations in CTR mode.

[Roland C. Dowdeswell]

On Thu, Feb 11, 2016 at 01:27:44PM -0800, Ray Dillinger wrote:
>

> In considering attacks on disk encryption, I realized we've been doing
> it wrong.  Our objectives with CTR mode are to obscure the relationship
> between identical blocks while permitting random access (not requiring
> reading/writing additional blocks when changing something in the
> middle).
> 
> CTR mode encryption is defined as
> 
> Ciphertext = E(counter, key) XOR Plaintext.
> 
> This obscures the relationship between identical blocks and allows
> random access, but leaves the data malleable.  If Mallory knows or
> can guess the plaintext, he can XOR the ciphertext with a difference
> vector to substitute a plaintext of his choice.

It's much worse than this.  CTR mode in its simplest form can't be
used for full disk encryption.  The contents of disks have a lot
of predictable bits in them, superblocks, inodes, etc.  And the
disk blocks get rewritten.  Once a block is rewritten with the same
keys, you can easily start breaking it.  Basically, XOR the old
and new ciphertext and you end up with the old and new plaintext
XORed which should give you real information.

If you want to avoid re-use of the same CTR output then you will
need to have a counter which is not mapped exactly one to one to
the ciphertext location of the disk.  But this would mean that
would have to maintain a separate table which maps the counters to
the disk locations and it becomes difficult to do atomic writes
efficiently.

These days, XTS mode is, I think what people are using for full
disk encryption.  It is a better starting point for this analysis.

> I propose instead "CXR mode", defined as
> 
> Ciphertext = E(counter XOR Plaintext, key)
> 
> Which also obscures the relationship between identical blocks and
> permits random access, but leaves the data nonmalleable.  With CXR,
> if Mallory has not the key, any change he makes to the ciphertext
> block is overwhelmingly likely to result in garbage.

This would be vulnerable to chosen plaintext and watermarking
attacks.  For example, if I could give you a file which you write
to the disk, it would be trivial for me to organise the file to
have only a small number of possible ciphertext blocks output by
choosing my plaintext to undo the XOR with the counter.

--
    Roland Dowdeswell                      http://Imrryr.ORG/~elric/