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