Re: "incrementing" ecb mode

From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: 10/15/03 

Date: Wed, 15 Oct 2003 09:47:09 +0100

Paul Rubin wrote

> Peter Fairbrother <zenadsl6186@zen.co.uk> writes:
>>> or you could use
>>> some kind of hash tree scheme.
>>
>> Could you explain please?
>
> Ehh, I'm not sure I want to spend the time making sure I have this
> right. But too first approximation: imagine a binary tree structure
> over the blocks of the file (i.e. if the blocks are numbered 1...N,
> for block #k if k < n/2, its two children are #2k and #2k+1). Then
> for each block, associate a MAC which is the MAC of the block combined
> with the MAC of its parent. Store the hash of the root node but not
> any of the others. If you change a block, you have to recompute its
> hash, which means recomputing the hash of its parent, its grandparent,
> etc. up to the root. That means to update a node, you have to do
> lg(N) hash operations and updates. For a million block file, that
> would be 20 operations. That may or may not be ok for your
> application but at least you don't have to mess with all million of
> the blocks.

Thanks for the explanation. It isn't much use to me, as I can't afford the
storage or transfers, but it's interesting.

>
>>> Using a CRC means anyone can change
>>> a block in the middle of the file without affecting the CRC.
>>
>> They would have to know the key used to encrypt the block and the key used
>> to encrypt the crc. The crc is a crc of the plaintext, and is stored
>> encrypted in the last block.
>
> No. If they can stick chosen plaintext into the file, they can modify
> the plaintext without changing the CRC.

I don't follow, perhaps we are talking about different things. If an
attacker could insert a chosen plaintext block (hard, but not impossible),
he would still have to be able to encrypt any modified plaintext block - and
to do that he would have to know the key.

>> Your idea of using keys based on an encrypted block number, rather than
>> incrementing the key, to deter or confuse related-key attacks has merit,
>> tho' I'd probably chose a different cipher to encrypt the keys from the
>> cipher used to encrypt the plaintext. Still thinking about it.
>
> No reason to use a different cipher. Do use a different key, of course.

If there is a related-key weakness in AES, then it might also apply to the
compounded encryption and key-generation process. I think it's far less
likely to exist if a different cipher is used for key generation. I'd feel
safer that way, anyway. 

-- 
Peter Fairbrother

Relevant Pages

  • Re: "incrementing" ecb mode
    ... > a block in the middle of the file without affecting the CRC. ... They would have to know the key used to encrypt the block and the key used ... The rekeying isn't a problem. ... cipher used to encrypt the plaintext. ...
    (sci.crypt)
  • Re: Question about bit strength
    ... Forget your home-brewed cipher. ... Create a pool of pseudo-random bytes by encrypting your ... Each time you need to encrypt one plaintext byte, ... encrypt it again. ...
    (sci.crypt)
  • im still trying to get the grips of monoalphabetic substitution.
    ... Now one exercise is to create a keyword cipher. ... now I'm writing a program to do this, encrypt and decrypt. ... the key letter from the cipher letter and i would have my plaintext back, ...
    (sci.crypt)
  • Re: AES as a stream cipher
    ... The use of CRC instead of a secure MAC was one of the things ... implication (like if you should first encrypt the plaintext and then create ...
    (sci.crypt)
  • Re: "incrementing" ecb mode
    ... Store the hash of the root node but not ... >> a block in the middle of the file without affecting the CRC. ... > to encrypt the crc. ... If they can stick chosen plaintext into the file, ...
    (sci.crypt)