Thread (2 messages) 2 messages, 2 authors, 2005-02-13

Re: [PATCH] OpenBSD Networking-related randomization port

From: Roland Dreier <hidden>
Date: 2005-02-13 00:19:17
Also in: lkml

Possibly related (same subject, not in this thread)

    linux> It's easy to make a smaller hash by just thowing bits away,
    linux> but a block cipher is a permutation, and has to be
    linux> invertible.

    linux> For example, if I take a k-bit counter and encrypt it with
    linux> a k-bit block cipher, the output is guaranteed not to
    linux> repeat in less than 2^k steps, but the value after a given
    linux> value is hard to predict.

Huh?  What if my cipher consists of XOR-ing with a k-bit pattern?
That's a permutation on the set of k-bit blocks but it happens to
decompose as a product of (non-overlapping) swaps.

In general for more realistic block ciphers like DES it seems
extremely unlikely that the cipher has only a single orbit when viewed
as a permutation.  I would expect a real block cipher to behave more
like a random permutation, which means that the expected number of
orbits for a k-bit cipher should be about ln(2^k) or roughly .7 * k.

 - R.
Keyboard shortcuts
hback out one level
jnext message in thread
kprevious message in thread
ldrill in
Escclose help / fold thread tree
?toggle this help