Re: another feature RNGs could provide

2005-12-28 Thread David Malone
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
about block ciphers.

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

2005-12-27 Thread Travis H.
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

2005-12-27 Thread David Malone
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

2005-12-22 Thread Matt Crawford

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

2005-12-22 Thread Ben Laurie
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

2005-12-22 Thread Anton Stiglic
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

2005-12-22 Thread Bill Stewart



 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

2005-12-22 Thread Travis H.
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
permutation would help you at all.
--
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

2005-12-21 Thread Ben Laurie
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

2005-12-21 Thread Perry E. Metzger

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

2005-12-13 Thread Jason Holt


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).


http://scholar.google.com/scholar?q=schroeppel+hastyie=UTF-8oe=UTF-8hl=enbtnG=Search


-J

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


another feature RNGs could provide

2005-12-12 Thread Travis H.
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
sorts of places in the kernel and elsewhere to prevent replay (for
example, in DNS ID #s, in challenge-response protocols, for IVs where
you must never repeat an IV, etc.)  From what I can tell the common
practice is to pick a value at random, and hope that you don't get a
collision, but this has the problem of the birthday paradox.

The questions I have for you are:

1) What form should the API for this take?  I was thinking that there
could be a
create new sequence operation, and the system could return an opaque
value to the client to store for its next value, and the get next
operator could take it as an input, freeing the PRNG from having to
remember state for every stream.

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?

3) Is there any point in offering a permutation generator that is not
cryptographically strong?
--
http://www.lightconsulting.com/~travis/  -- P=NP if (P=0 or N=1)
My love for mathematics is unto 1/x as x approaches 0.
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

2005-12-12 Thread Jack Lloyd
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]