Re: nonce length

Hi Dan,

the xenc:EncryptedData/@Nonce attribute like described in the spec is NOT a 
fully-working solution against IV-Attacks. Even while using a Nonce, an 
attacker can modify encrypted contents without knowing the key if he can 
make a good guess about the plaintext. In short, the number of modifyable 
bytes is:

modifyableByteLength = blockLength - (nonceLength % blockLength)

Example AES (blockLength = 16 bytes)

nonceLength  |  modifyableByteLength(nonceLength)
-------------+-----------------------------------
    0        |       16 bytes
    1        |       15 bytes
    2        |       14 bytes
    3        |       13 bytes
...
   15        |        1 bytes
   16        |       16 bytes
   17        |       15 bytes
   18        |       14 bytes

This attack works because the decryptor has no way to detect that the IV or 
bytes inside a complete Nonce block are tampered. (Yes, I know that 
encryption does not provide integrity, but in the past it was argued that 
the Nonce solves the IV-attack problem). In the spec, we have to following 
sentence (section 6.3):


  "Some encryption algorithms take an initialization
   vector (IV) such that an adversary modifying the
   IV can make a known change in the plain text after
   decryption. This attack can be avoided by securing
   the integrity of the plain text data, for example
   by signing it, or, for most such algorithms, by
   including an algorithm dependent length. A nonce
   at least as long as the block for CBC chaining
   block encryption algorithms may be adequate."

Well, today I've learned that only nonce values of (n * blocklength - 1) 
are 'secure' and this only if you encrypt an Element (because in this case 
only the 1st byte can be modified and this is the '<' sign which MUST be 
the first if you have Element content).

Example below shows how this looks like; I encrypt the contents of the root 
element which is only a Text node (luckily of length = blocklength ;-))) In 
the example I changed "1 USD           " to "999.999.999 EUR ".


- Plaintext ------------------------------------------------

<!-- AES-Key is in hex "000102030405060708090a0b0c0d0e0f"
<!-- 1 -->
<root>1 USD           </root>
<!-- 2 -->

- Original ciphertext --------------------------------------

<!-- AES-Key is in hex "000102030405060708090a0b0c0d0e0f"
<!-- 1 -->
<root><xenc:EncryptedData xmlns:xenc="http://www.w3.org/2001/04/xmlenc#" 
Id="myFirstEncryptedElement" Nonce="32" 
Type="http://www.w3.org/2001/04/xmlenc#Content">
<xenc:EncryptionMethod 
Algorithm="http://www.w3.org/2001/04/xmlenc#aes128-cbc"></xenc:EncryptionMe
thod>
<ds:KeyInfo xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
<ds:KeyName>Christian Geuer-Pollmann</ds:KeyName>
</ds:KeyInfo>
<xenc:CipherData>
<xenc:CipherValue>xk0dIDXBBtpMGasfZFQXegnju13ya7MMSMZvwBKycKJ+AzhsG7D/dPK6l
qy1aRFxzIdIfGON9Zl+
prptdMSo+ob76T3CY1bHPQhGjQQmnEA=</xenc:CipherValue>
</xenc:CipherData>
</xenc:EncryptedData></root>
<!-- 2 -->

- modified ciphertext --------------------------------------

<!-- AES-Key is in hex "000102030405060708090a0b0c0d0e0f"
<!-- 1 -->
<root><xenc:EncryptedData xmlns:xenc="http://www.w3.org/2001/04/xmlenc#" 
Id="myFirstEncryptedElement" Nonce="32" 
Type="http://www.w3.org/2001/04/xmlenc#Content">
<xenc:EncryptionMethod 
Algorithm="http://www.w3.org/2001/04/xmlenc#aes128-cbc"></xenc:EncryptionMe
thod>
<ds:KeyInfo xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
<ds:KeyName>Christian Geuer-Pollmann</ds:KeyName>
</ds:KeyInfo>
<xenc:CipherData>
<xenc:CipherValue>xk0dIDXBBtpMGasfZFQXegnju13ya7MMSMZvwBKycKJ2GlQRZqnmeuujj
6zQHGNxzIdIfGON9Zl+
prptdMSo+ob76T3CY1bHPQhGjQQmnEA=</xenc:CipherValue>
</xenc:CipherData>
</xenc:EncryptedData></root>
<!-- 2 -->

- resulting plaintext --------------------------------------

<!-- AES-Key is in hex "000102030405060708090a0b0c0d0e0f"
<!-- 1 -->
<root>999.999.999 EUR </root>
<!-- 2 -->

------------------------------------------------------------


--On Donnerstag, 3. Januar 2002 14:04 -0500 Dan Lanz <lanz@zolera.com> 
wrote:

> Section 6.3 states: "Some encryption algorithms take an
> initialization vector such that an adversary modifying the
> IV can make a known change in the plain text after decryption.
> This attack can be avoided by securing the integrity of the
> plain text data, for example by signing it, or, for most
> such algorithms, by including an algorithm dependent length.
> A nonce at least as long as the block for CBC chaining block
> encryption algorithms may be adequate."
>
> It is unclear to me what "algorithm dependent length" is
> referring to in the second sentence.  Is this referring to
> the possibility that the structure of CBC encryption
> algorithms (and perhaps others) allows blocks to be added to
> the end of an encrypted message w/o being detected?
>
> Additionally, I believe the final sentence should be
> clarified.  Is this implying that a nonce would only be useful
> to block algorithms in CBC mode?  (I realize that the
> specification currently lists only block encryption algorithms
> in CBC mode, but it appears to leave open the possibility for
> future specification of stream ciphers).  Also, it would be
> useful to give a firm recommendation as to the length of the
> nonce that should be employed for reasonable protection against
> chosen plaintext attacks.  Although the specification states
> that it should be at least as long as a CBC block for a given
> algorithm, does this mean that a nonce *exactly* as long as a
> block is sufficient?  Would it be better to make it longer
> and, if so, how much?
>
> Dan Lanz
>

Received on Friday, 4 January 2002 08:03:49 UTC