### Re: another feature RNGs could provide

```On Tue, Dec 27, 2005 at 11:34:15PM +, Ben Laurie wrote:
If you don't have sufficient plain/ciphertext, then of course you can
choose incorrect pairs.

Yep - that's my point. The thing to note is that for an arbitrary
permutation, knowing the image of n plaintexts tells you (almost)
nothing else.  Usually for a block cipher with a smaller key space,
knowing a plaintext/ciphertext pair actually has a pretty big impact
on what you know about the key, and this is how people usually think

In AES with a 128 bit block and 256 bit key, if the images are
uniformly and independently distributed, then each pair known reduces
the possible amount of key space by about 128 bits, so 2 or 3 pairs
will nail the key down with reasonable probability. For good measure
we could say 20 or 30 would be sufficient, even if the images aren't
well distributed.

For S_(2^128) the original key space has (2^128)! keys so it is
about 128*(2^128) bits. Knowing 30 pairs here will reduce the key
space by about 128*30 bits, leaving us with 128*(2^128) - 128*30 =
128*(2^128-30) bits. We've barely had any impact at all, because
the key space was much bigger to begin with.

Of course, this also shows why using an arbitrary permutation in
S_(2^128) isn't very practical - you need to store 128*(2^128) bits
to remember which one you're using!

David.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: another feature RNGs could provide

```On 12/26/05, Ben Laurie [EMAIL PROTECTED] wrote:
Surely if you do this, then there's a meet-in-the middle attack: for a
plaintext/ciphertext pair, P, C, I choose random keys to encrypt P and
decrypt C. If E_A(P)=D_B(C), then your key was A.B, which reduces the
strength of your cipher from 2^x to 2^(x/2)?

Almost true.  The cardinality of the symmetric group S_(2^x) is
(2^x)!, so it reduces it from (2^x)! to roughly sqrt((2^x)!).  That's
still a lot.

I suspect this is some information-theoretic limit for x-bit block ciphers.
--
http://www.lightconsulting.com/~travis/
Vast emptiness, nothing sacred. -- Bodhidharma --
GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: another feature RNGs could provide

```On Tue, Dec 27, 2005 at 03:26:59AM -0600, Travis H. wrote:
On 12/26/05, Ben Laurie [EMAIL PROTECTED] wrote:
Surely if you do this, then there's a meet-in-the middle attack: for a
plaintext/ciphertext pair, P, C, I choose random keys to encrypt P and
decrypt C. If E_A(P)=D_B(C), then your key was A.B, which reduces the
strength of your cipher from 2^x to 2^(x/2)?

Almost true.  The cardinality of the symmetric group S_(2^x) is
(2^x)!, so it reduces it from (2^x)! to roughly sqrt((2^x)!).  That's
still a lot.

I'm fairly sure knowing that E(P) = C reduces the key space from
(2^x)!  to (2^x - 1)!, because you've just got to choose images for
the remaining 2^x - 1 possible blocks.

I think a problem with Ben's arument is in assuming that knowing
E_A(P)=D_B(C) tells you that your key was A.B. For example, suppose
my key K is the permutation:

1 - 2
2 - 3
3 - 4
4 - 1

and my P = 2. Now we know E_K(P) = C = 3. Ben guesses A:

1 - 1
2 - 3
3 - 2
4 - 4

and B:

1 - 1
2 - 2
3 - 3
4 - 4

He sees that E_A(P) = E_A(2) = 3 = D_B(3), and so assumes that K =
A.B. But A.B = A != K.

(In this example, imagine x = 2, and we label the blocks 00 = 1,
01 = 2, 10 = 3, 11 = 4.)

David.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: another feature RNGs could provide

```
On Dec 21, 2005, at 0:10, Ben Laurie wrote:

Good ciphers aren't permutations, though, are they? Because if they
were, they'd be groups, and that would be bad.

A given cipher, with a given key, is a permutation of blocks.
(Assuming output blocks and input blocks are the same size.)  It may
be (and often is) the case that the set of all keys does not span the
set of all possible permutations, in which case the permutations

{ E_k() | k in set of all keys }

may or may not turn out to be a group.

For blocks of n bits and keys of m bits, there are n! permutations
but 2^m of them are representable by some key.  If m = n, this is a
fraction roughly equal to

(2e/n)^n

About 10^-70 for n=64.  I don't know the probability of a randomly
selected subset of a permutation group being a group, but at these
scales, I bet it's small.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: another feature RNGs could provide

```Matt Crawford wrote:
On Dec 21, 2005, at 0:10, Ben Laurie wrote:
Good ciphers aren't permutations, though, are they? Because if they
were, they'd be groups, and that would be bad.

A given cipher, with a given key, is a permutation of blocks.  (Assuming
output blocks and input blocks are the same size.)  It may be (and often
is) the case that the set of all keys does not span the set of all
possible permutations, in which case the permutations

{ E_k() | k in set of all keys }

may or may not turn out to be a group.

For blocks of n bits and keys of m bits, there are n! permutations but
2^m of them are representable by some key.  If m = n, this is a fraction
roughly equal to

(2e/n)^n

About 10^-70 for n=64.  I don't know the probability of a randomly
selected subset of a permutation group being a group, but at these
scales, I bet it's small.

Must try not to post to crypto when I'm jetlagged! I had my wires
crossed here, what's bad is when the keys form a group, of course (as
others have also pointed out).

--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/
**  ApacheCon - Dec 10-14th - San Diego - http://apachecon.com/ **
There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit. - Robert Woodruff

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### RE: another feature RNGs could provide

```Actually, by definition, a cipher should be a permutation from the set
of plaintexts to the set of ciphertexts. It has to be 1 to 1 bijective
or it isn't an encryption algorithm.

Therefore, if you want an ergodic sequence of size 2^N, a counter
encrypted under an N bit block cipher will do it.

Perry

Yes, and the set of keys define a subset of all of the possible permutations
(working on the same size input as the block cipher).  The set of all
permutations is a group, but a subset of that is not necessarily a subgroup.

Most security proofs of modes of operations, and others, model a block
cipher as a random permutation.

--Anton

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: another feature RNGs could provide

```

Good ciphers aren't permutations, though, are they? Because if they
were, they'd be groups, and that would be bad.

Actually, by definition, a cipher should be a permutation from the set
of plaintexts to the set of ciphertexts. It has to be 1 to 1 bijective
or it isn't an encryption algorithm.

The groups-are-bad problem applies to the
mapping between keys and plaintext-cyphertext bijections,
not the mapping between plaintext and cyphertext.
You're trying to avoid the situation where
E(x,key1) == E( E(x,key2), key3) for all x

The mapping between plaintext and cyphertext doesn't need to be 1-1
bijective.

1-n mappings from 1 plaintext to multiple cyphertexts
can work fine for many applications,
but have the practicality problem that the cyphertext is
longer than the plaintext, and there aren't many
applications where you really want the expansion.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: another feature RNGs could provide

```On 12/21/05, Perry E. Metzger [EMAIL PROTECTED] wrote:
Good ciphers aren't permutations, though, are they? Because if they
were, they'd be groups, and that would be bad.

Actually, by definition, a cipher should be a permutation from the set
of plaintexts to the set of ciphertexts. It has to be 1 to 1 bijective
or it isn't an encryption algorithm.

Isn't the question people normally care about whether encryption over
all keys is closed or not, and only relevant if you're trying to
increase the keyspace through multiple encryption?

The other day I was thinking of using a very large key to select a
permutation at random from the symmetric group S_(2^x).  That would be
a group, but I don't see how you knowing that I'm using a random
--
http://www.lightconsulting.com/~travis/
I once went to a mathematics conference.  I got the room number Pi.  It was
easy to find, but took forever to dial on the in-house phone. -- Steven Wright
GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: another feature RNGs could provide

```Jack Lloyd wrote:
On Mon, Dec 12, 2005 at 12:20:26AM -0600, Travis H. wrote:
2) While CTR mode with a random key is sufficient for creating a
permutation of N-bit blocks for a fixed N, is there a general-purpose
way to create a N-bit permutation, where N is a variable?  How about
picking a cryptographically strong permutation on N elements, where N
is not necessarily a power of 2?

Use can use the Bear or Lion constructions to form 2^{arbitrary} bit block
ciphers quite easily.

Good ciphers aren't permutations, though, are they? Because if they
were, they'd be groups, and that would be bad.

--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/
**  ApacheCon - Dec 10-14th - San Diego - http://apachecon.com/ **
There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit. - Robert Woodruff

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: another feature RNGs could provide

```
Ben Laurie [EMAIL PROTECTED] writes:
Jack Lloyd wrote:
On Mon, Dec 12, 2005 at 12:20:26AM -0600, Travis H. wrote:
2) While CTR mode with a random key is sufficient for creating a
permutation of N-bit blocks for a fixed N, is there a general-purpose
way to create a N-bit permutation, where N is a variable?  How about
picking a cryptographically strong permutation on N elements, where N
is not necessarily a power of 2?

Use can use the Bear or Lion constructions to form 2^{arbitrary} bit block
ciphers quite easily.

Good ciphers aren't permutations, though, are they? Because if they
were, they'd be groups, and that would be bad.

Actually, by definition, a cipher should be a permutation from the set
of plaintexts to the set of ciphertexts. It has to be 1 to 1 bijective
or it isn't an encryption algorithm.

Therefore, if you want an ergodic sequence of size 2^N, a counter
encrypted under an N bit block cipher will do it.

Perry

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: another feature RNGs could provide

```

On Mon, 12 Dec 2005, Travis H. wrote:

One thing I haven't seen from a PRNG or HWRNG library or device is an
unpredictable sequence which does not repeat; in other words, a
[cryptographically strong?] permutation.  This could be useful in all

Rich Schroeppel tells me his Hasty Pudding cipher can be used to create PRPs
(pseudorandom permutations) of arbitrary size.  It even has the ability to let
you define external functions to help define set membership (for sets which
aren't just composed of the natural numbers).

-J

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: another feature RNGs could provide

```On Mon, Dec 12, 2005 at 12:20:26AM -0600, Travis H. wrote:
2) While CTR mode with a random key is sufficient for creating a
permutation of N-bit blocks for a fixed N, is there a general-purpose
way to create a N-bit permutation, where N is a variable?  How about
picking a cryptographically strong permutation on N elements, where N
is not necessarily a power of 2?

Use can use the Bear or Lion constructions to form 2^{arbitrary} bit block
ciphers quite easily.

-Jack

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```