Brute-force attack on surrogate Mediaserver blocks

[b.fallenstein@xxxxxx]

A note on 'surrogate' Mediaserver blocks, the proposed mechanism for
publishing a Mediaserver block that contains confidential data.

(Mediaserver blocks are byte sequences identified by SHA-1 hashes. It is
important that data is not copied from one block to another, as that would break
Xanadu linking. However, if you want to publish only part of a block, the
SHA-1 hash cannot be verified any more. It is proposed that you publish a
'surrogate' block containing only part of the original block, and digitally sign
the statement that this is indeed what the original block did contain.)

Suppose you've created a surrogate block, dropping n confidential bits from
the original block. In O(2^n) time, an attacker can trivially get the
original information; they just have to try any sequence of n bits and fit them in
the missing places, computing the SHA-1 hash for each completion. If it equals
the ID of the original block, the completion *is* the original block (with
very high probabiliy).

If the attacker has an idea of what the original data looks like (for
example, characters of English text), their attack can be much more efficient (they
simply try the more likely completions first). English text is known to have
very little entropy.

The attack is trivially parallelizable: simply assign a number of systems
non-overlapping subsets of the set of possible completions.

For textual data, this could be a real problem (if only a small part of a
block is deleted).

- Benja

-- 
GMX - Die Kommunikationsplattform im Internet.
http://www.gmx.net