Re: Proposal for XML Encryption Syntax and Processing

[snip things that are out of scope for the discussion, my apologies]

> The issue we have been discussing here is the leakage of (approximate)
> message length, rather than message content per se.

> Most ciphers do
> little to conceal this.

Speaking as a member of the cryptographic community, we came to the
conclusion that while it is of interest to us, and is of cryptographic
importance, it was better that the cipher algorithm should not even attempt
to conceal the message length, in fact we often go to great lengths to make
the input and output sizes the same (quite often with bragging right
attached to the best). However we have created additional techniques for
such purposes. The easiest is to match the sizes of all the messages.
Normally this is done through compression, each of the N messages recieves a
number from 0 to N-1. Other times this is done through expansion, each
message is given a range of messages of a particular size from which the
actual encrypted message is randomly chosen. What I would suggest in this
case though is a variation of block filling. If we add another (optional)
attribute to the definition of the encrypted node, specifically a segmenting
length, this can be overcome. In particular this segmenting length would
consist of a number of bits, the encrypted data would be forced to a
multiple of the segmenting length through a padding method. Because we can
have potentially very large segmenting lengths many of the normal methods
won't be functional, instead I suggest using the method that has been
adopted by the hash functions, postpend a 1-bit, followed by enough 0 bits
to fill all but the last 128-bits of the segment, postpend the length of the
data in bits, high order bit first. If the segmenting length is present
there must be at least 128-bits added (the initial 1 bit is non-critical).
Apply your favorite chaining mode and all message now have a length that is
a multiple of segment length. Removal of the padding is simple, take the
last 128-bits of the last segment, call the number K. Take the first K bits
of the decrypted data that is the decrypted value, if there are any
remaining bits after the removal of the last 128, and the first K, verify
that the remaining bits are in fact 1 followed by 0s (to detect transmission
errors).

To make this more secure, I would suggest allowing an ordering like:
Padding
All-Or-Nothing-Transform
encryption

The presence of the AONT in the middle will make any leakage of the padding
information through the cipher impossible unless the entire message also
leaks through the cipher (which would be perfectly equivalent to breaking
the encryption). For some purposes the AONT phase is far more important than
the padding portion. Placing the AONT before the Padding supplies potential
to leak the very information that the padding is present to protect (the
length of the message), so it is important that the AONT be performed after
the segment filling padding. Following the AONT there may be padding to fill
the last block of the cipher, but that is a trivial issue and will leak no
information about the real length of the document.
                        Joe

Received on Monday, 8 January 2001 19:58:25 UTC