67 views

Skip to first unread message

Jun 2, 2001, 9:21:46 AM6/2/01

to

If I understand correctly one of the LR theorems is about making a random

permutation out of a three round feistel. It involves truly random

functions as F functions where one of them (at least) is not a bijection.

permutation out of a three round feistel. It involves truly random

functions as F functions where one of them (at least) is not a bijection.

If I get this correctly isn't this theorem recursive?

I.e take three random eight bit functions. Now you have a 16 bit PRF, etc..

This is the Turtle design (Matt Blaze) right?

I wonder.... other than the obvious efficiency issue why don't people

consider these? They are provably random permutations and are generally

easy to design...?

--

Tom St Denis

---

http://tomstdenis.home.dhs.org

Jun 2, 2001, 11:20:32 AM6/2/01

to

Tom St Denis wrote:

>

> If I understand correctly one of the LR theorems is about making a random

> permutation out of a three round feistel. It involves truly random

> functions as F functions where one of them (at least) is not a bijection.

>

> If I understand correctly one of the LR theorems is about making a random

> permutation out of a three round feistel. It involves truly random

> functions as F functions where one of them (at least) is not a bijection.

The Luby-Rackoff results are about constructing *pseudo*random

permutations from *pseudo*random functions, not exactly as you stated.

The definition of pseudorandomness has many nuances and important but

unobvious implications; it's difficult to explain in a few words.

I don't have the paper with me right now, but I remember the gist of it.

The function F in general is not bijective, but permutations are not

excluded.

If the application is secure encryption, you probably want to use a

4-round Feistel structure (to obtain a "super pseudorandom invertible

permutation generator"). See the Luby-Rackoff paper for more details.

> If I get this correctly isn't this theorem recursive?

Yes, you can apply the result recursively.

> I.e take three random eight bit functions. Now you have a 16 bit PRF, etc..

No. Pseudorandomness is a property of a scalable scheme. You cannot talk

about pseudorandomness when the security parameter is fixed at a given

value.

> This is the Turtle design (Matt Blaze) right?

I don't know--I'm not familiar with Turtle.

> I wonder.... other than the obvious efficiency issue why don't people

> consider these? They are provably random permutations and are generally

> easy to design...?

Of course people have considered it, it's such as obvious idea. What a

recursive application of the Luby-Rackoff results yield is not a

"provably random permutation", it is just another "pseudorandom

invertible permutation generator" to use the author's terminology. You

have to be *extremely* careful about what is proved. The devil is in the

details.

--

Nicol So, CISSP // paranoid 'at' engineer 'dot' com

Disclaimer: Views expressed here are casual comments and should

not be relied upon as the basis for decisions of consequence.

Jun 2, 2001, 12:06:58 PM6/2/01

to

"Nicol So" <nob...@no.spam.please> wrote in message

news:3B190440...@no.spam.please...

Thanks, I had a hunch I was missing a slight detail.

Tom

Jun 2, 2001, 12:23:35 PM6/2/01

to

Nicol So wrote:

>> If I get this correctly isn't [the Luby-Rackoff] theorem recursive?

>

>Yes, you can apply the result recursively.

>> If I get this correctly isn't [the Luby-Rackoff] theorem recursive?

>

>Yes, you can apply the result recursively.

But beware: The guaranteed security level drops dramatically

each time you apply it. Remember, these security theorems

say "the construction is secure against adversaries using at

most q queries"; and the q will go down by the square root

for each extra level of recursion.

Jun 2, 2001, 2:16:17 PM6/2/01

to

"Tom St Denis" <tomst...@yahoo.com> wrote in message

news:KL5S6.9000$Be4.2...@news3.rdc1.on.home.com...

> I.e take three random eight bit functions. Now you have a 16 bit PRF,

etc..

The term "psuedo-random" applies to lots of things you wouldn't like.

(256^256)^3 is much less than 65536!, so most permutations of 16 bit numbers

can't be constructed this way. To randomly select such a permutation will

take about 1000000 random bits.

Jun 2, 2001, 2:36:05 PM6/2/01

to

"Matt Timmermans" <ma...@timmermans.nospam-remove.org> wrote in message

news:F2aS6.22838$Gf.27...@news20.bellglobal.com...

Actually that would be (256!)^3 or about 2^5051, wheras a 65536 element set

can have about 2^954036.863550 possible orders.

I agree they are diff #'s but does LR specifically say it must be randomly

selected from the set of all perms?

Tom

Jun 2, 2001, 3:27:16 PM6/2/01

to

I could be wrong, but I don't think the Luby-Rackoff results are of that

form. I think they were able to come up with an upper bound on the

distinguishing probability of any polynomial-size circuit, based on the

number of times the oracle is consulted. The upper bound is a

"negligible" function in the security parameter. I don't think there's a

threshold on the # of queries beyond which the security (distinguishing

probability) drops (increases) dramatically.

The phenomenon you pointed out is one of the "nuances" I was referring

to in my previous message. Often times constructions in

complexity-theoretic security proofs can be applied

repeatedly/recursively a polynomial # of times without changing the

asymptotic results. But that doesn't mean it doesn't matter when the

construction is used in practice.

"In theory, there's no difference between theory and practice. In

practice, there is." (I don't know who originally said it, but I think

it's very true.)

Jun 2, 2001, 5:45:59 PM6/2/01

to

Nicol So wrote:

>I could be wrong, but I don't think the Luby-Rackoff results are of that

>form.

>I could be wrong, but I don't think the Luby-Rackoff results are of that

>form.

They are. If you want to build a cipher with a n-bit block, Luby-Rackoff

only guarantees security up to q ~ min(2^{n/4},q') chosen texts, assuming

that the Feistel function is secure with up to q' chosen texts. This bound

is tight: There are attacks that can distinguish a Luby-Rackoff cipher from

an ideal cipher with O(2^{n/4}) texts, for example.

Let's say you want to use Luby-Rackoff twice to build a n-bit block cipher.

You're going to use Luby-Rackoff to build the n/2-bit Feistel function,

and so this Feistel function will only be secure up to q' ~ 2^{n/8} texts.

As a consequence, the entire cipher will only be guaranteed secure up to

q ~ 2^{n/8} texts as well.

For instance, suppose you want to build a 128-bit block cipher. With

plain Luby-Rackoff, you can build one that is secure for up to 2^32 texts.

With two levels of recursion, it is secure only up to 2^16 texts. And so on.

Hence my conclusion: you can use Luby-Rackoff recursively, but the security

guarantees get progressively weaker each time you do (assuming the block

size is held constant).

Jun 2, 2001, 8:18:32 PM6/2/01

to

"Nicol So" <nob...@no.spam.please> wrote in message

news:3B190440...@no.spam.please...

> Tom St Denis wrote:

> >

> > If I understand correctly one of the LR theorems is about making a

random

> > permutation out of a three round feistel. It involves truly random

> > functions as F functions where one of them (at least) is not a

bijection.

>

> The Luby-Rackoff results are about constructing *pseudo*random

> permutations from *pseudo*random functions, not exactly as you stated.

> The definition of pseudorandomness has many nuances and important but

> unobvious implications; it's difficult to explain in a few words.

> >

> > If I understand correctly one of the LR theorems is about making a

random

> > permutation out of a three round feistel. It involves truly random

> > functions as F functions where one of them (at least) is not a

bijection.

>

> The Luby-Rackoff results are about constructing *pseudo*random

> permutations from *pseudo*random functions, not exactly as you stated.

> The definition of pseudorandomness has many nuances and important but

> unobvious implications; it's difficult to explain in a few words.

<snip>

I looked into my EuroCrypt CD and I found their Crypto '85 paper "How to

construct pseudo-random permutations from pseudo-random functions," which is

not complete. The copy I have is a single page....

Does anyone have a copy of the full paper online?

Tom

Jun 2, 2001, 8:43:38 PM6/2/01

to David Wagner

David Wagner wrote:

>

> Nicol So wrote:

> >I could be wrong, but I don't think the Luby-Rackoff results are of that

> >form.

>

> They are. If you want to build a cipher with a n-bit block, Luby-Rackoff

> only guarantees security up to q ~ min(2^{n/4},q') chosen texts, assuming

> that the Feistel function is secure with up to q' chosen texts. This bound

> is tight: There are attacks that can distinguish a Luby-Rackoff cipher from

> an ideal cipher with O(2^{n/4}) texts, for example.

>

> Nicol So wrote:

> >I could be wrong, but I don't think the Luby-Rackoff results are of that

> >form.

>

> They are. If you want to build a cipher with a n-bit block, Luby-Rackoff

> only guarantees security up to q ~ min(2^{n/4},q') chosen texts, assuming

> that the Feistel function is secure with up to q' chosen texts. This bound

> is tight: There are attacks that can distinguish a Luby-Rackoff cipher from

> an ideal cipher with O(2^{n/4}) texts, for example.

Do you have a reference to the result? It doesn't seem to be in the 1988

Luby-Rackoff paper. Actually, it seems to contradict the main lemma of

that paper, which states:

"Let C_2n be an oracle circuit with m oracle gates such that no input

value is repeated to an oracle gate as in the above proposition. Then

|Pr[C_2n(F^2n)] - Pr[C_2n(H(F^n,F^n,F^n))]| <= m^2/2^n."

The notation used in the lemma is different than yours. Your 'q' is

their 'm', your 'n' is equivalent to 'n/2' in the lemma. The 'C_2n' in

the lemma is a candidate distinguisher for a 3-round Feistel structure

with truly random F functions.

Let q = 2^{3n/8} (in your notation). Now q violates your threshold by a

significant margin.

Converting to the notation of the lemma, we have

m = 2^{3n/16}.

Substituting into the lemma, we have

|Pr[C_2n(F^2n)] - Pr[C_2n(H(F^n,F^n,F^n))]|

<= 2^{3n/8}/2^n

= 2^{-5n/8},

which is (still) converges to 0 faster than n^-c for any c > 0.

Did I miss something?

Jun 2, 2001, 8:44:05 PM6/2/01

to

David Wagner wrote:

>

> Nicol So wrote:

> >I could be wrong, but I don't think the Luby-Rackoff results are of that

> >form.

>

> They are. If you want to build a cipher with a n-bit block, Luby-Rackoff

> only guarantees security up to q ~ min(2^{n/4},q') chosen texts, assuming

> that the Feistel function is secure with up to q' chosen texts. This bound

> is tight: There are attacks that can distinguish a Luby-Rackoff cipher from

> an ideal cipher with O(2^{n/4}) texts, for example.

>

> Nicol So wrote:

> >I could be wrong, but I don't think the Luby-Rackoff results are of that

> >form.

>

> They are. If you want to build a cipher with a n-bit block, Luby-Rackoff

> only guarantees security up to q ~ min(2^{n/4},q') chosen texts, assuming

> that the Feistel function is secure with up to q' chosen texts. This bound

> is tight: There are attacks that can distinguish a Luby-Rackoff cipher from

> an ideal cipher with O(2^{n/4}) texts, for example.

Do you have a reference to the result? It doesn't seem to be in the 1988

Luby-Rackoff paper. Actually, it seems to contradict the main lemma of

that paper, which states:

"Let C_2n be an oracle circuit with m oracle gates such that no input

value is repeated to an oracle gate as in the above proposition. Then

|Pr[C_2n(F^2n)] - Pr[C_2n(H(F^n,F^n,F^n))]| <= m^2/2^n."

The notation used in the lemma is different than yours. Your 'q' is

their 'm', your 'n' is equivalent to 'n/2' in the lemma. The 'C_2n' in

the lemma is a candidate distinguisher for a 3-round Feistel structure

with truly random F functions.

Let q = 2^{3n/8} (in your notation). Now q violates your threshold by a

significant margin.

Converting to the notation of the lemma, we have

m = 2^{3n/16}.

Substituting into the lemma, we have

|Pr[C_2n(F^2n)] - Pr[C_2n(H(F^n,F^n,F^n))]|

<= 2^{3n/8}/2^n

= 2^{-5n/8},

which is (still) converges to 0 faster than n^-c for any c > 0.

Did I miss something?

--

Jun 2, 2001, 8:56:52 PM6/2/01

to

Tom St Denis wrote:

>

> I looked into my EuroCrypt CD and I found their Crypto '85 paper "How to

> construct pseudo-random permutations from pseudo-random functions," which is

> not complete. The copy I have is a single page....

>

> Does anyone have a copy of the full paper online?

>

> I looked into my EuroCrypt CD and I found their Crypto '85 paper "How to

> construct pseudo-random permutations from pseudo-random functions," which is

> not complete. The copy I have is a single page....

>

> Does anyone have a copy of the full paper online?

The paper you should be looking for is:

Michael Luby and Charles Rackoff. How to construct pseudorandom

permutations from pseudorandom functions. SIAM Journal on Computing,

17(2):373-386, April 1988.

Now that you're in university, you should be able to find it in your

math/CS library. I don't think I've seen it available online.

Jun 2, 2001, 9:14:40 PM6/2/01

to

"Nicol So" <nob...@no.spam.please> wrote in message

> Tom St Denis wrote:

> >

> > I looked into my EuroCrypt CD and I found their Crypto '85 paper "How to

> > construct pseudo-random permutations from pseudo-random functions,"

which is

> > not complete. The copy I have is a single page....

> >

> > Does anyone have a copy of the full paper online?

>

> The paper you should be looking for is:

>

> Michael Luby and Charles Rackoff. How to construct pseudorandom

> permutations from pseudorandom functions. SIAM Journal on Computing,

> 17(2):373-386, April 1988.

I will look it up.

> Now that you're in university, you should be able to find it in your

> math/CS library. I don't think I've seen it available online.

Correction I am in College not university. (College in Canada is diploma

not degree based).

Tom

Jun 3, 2001, 5:31:27 AM6/3/01

to

I think you might have gotten caught by two subtle pitfalls.

If I'm not mistaken, they will account for the difference between

our two results, and correcting for them will give what I claimed.

But tell me whether you agree or not---this is tricky stuff,

and who knows, maybe I went wrong somewhere.

If I'm not mistaken, they will account for the difference between

our two results, and correcting for them will give what I claimed.

But tell me whether you agree or not---this is tricky stuff,

and who knows, maybe I went wrong somewhere.

1. The Luby-Rackoff paper uses 2n for the block size, and proves

security so long as m^2/2^n is small, where m is the number of

texts. Thus, this provides security up to m ~ 2^{n/2}. If we

let n' = 2n be the block size (n' is "my n" in my earlier post),

then this provides security for up to 2^{n'/4} texts. With a

128-bit block cipher, this is security up to 2^32 texts.

2. The Luby-Rackoff paper is actually not quite enough if you want

to use their construction recursively. You need to look to modern

generalizations. In particular, LR prove

If the Feistel function is truly random, then

the 4-round cipher is pseudorandom.

Note that they require a truly random (unconditionally secure)

Feistel function, so if you try to instantiate the Feistel function

using a recursive LR construction, the original LR theorem doesn't

apply. Since then, others have made the slight generalization to

the case where the Feistel function is assumed only to be pseudorandom

(e.g., Maurer, Lucks, Naor/Reingold, etc.). Let q-pseudorandom

refer to a keyed function that is indistinguishable from its idealized

version if the adversary has access to at most q texts. Then the

modern form of the Luby-Rackoff theorem is

If the Feistel function is q'-pseudorandom, then

the 4-round cipher is q-pseudorandom.

In particular, q is related to q' by q ~ min(q',2^{n/2}) where

n is as above, i.e., q ~ min(q',2^{n'/4}). This is why the q'

appears in my statement of the theorem but does not appear in

the original Luby-Rackoff paper.

Jun 3, 2001, 11:27:54 AM6/3/01

to

David Wagner wrote:

>

> I think you might have gotten caught by two subtle pitfalls.

> If I'm not mistaken, they will account for the difference between

> our two results, and correcting for them will give what I claimed.

> But tell me whether you agree or not---this is tricky stuff,

> and who knows, maybe I went wrong somewhere.

>

> I think you might have gotten caught by two subtle pitfalls.

> If I'm not mistaken, they will account for the difference between

> our two results, and correcting for them will give what I claimed.

> But tell me whether you agree or not---this is tricky stuff,

> and who knows, maybe I went wrong somewhere.

I agree that this is tricky stuff. I think I spotted some problems in

your argument. Please check my reasoning.

> 1. The Luby-Rackoff paper uses 2n for the block size, and proves

> security so long as m^2/2^n is small, where m is the number of

> texts. Thus, this provides security up to m ~ 2^{n/2}. If we

> let n' = 2n be the block size (n' is "my n" in my earlier post),

> then this provides security for up to 2^{n'/4} texts. With a

> 128-bit block cipher, this is security up to 2^32 texts.

I don't think that's the correct interpretation of the "main lemma" (the

lemma that I quoted in my last message). In the kind of complexity

theory-based approach used by Luby and Rackoff (and many others),

security is defined in terms of the non-existence of efficient computers

(e.g. PPTM, family of polynomial-size circuits) that can distinguish

between two distributions (in this case, uniformly distributed functions

in F^2n and permutations implemented by a 3-round Feistel structure).

The construction is secure iff *asymptotically* the distinguishing

probability

|Pr[C_2n(F^2n)] - Pr[C_2n(H(F^n,F^n,F^n))]|

converges to 0 faster than n^-c for any c > 0.

The intuition behind it is that if you keep increasing the security

parameter, *eventually* the distinguishing probability will become

small, and more importantly, become small so fast that you can't use

polynomial-time tricks to magnify it to any constant level.

So... what matters is the order of growth of the upper bound, but not

the exact value of the upper bound. This is a subtle but *very*

important point. We cannot take the expression of an upper bound, and

then argue that if you choose m to violate it, the construction suddenly

becomes insecure. The upper bound in the main lemma represents *a*

sufficient condition for security, but there're an infinite number of

others that can be used in place of it. Each one of these would yield a

different safety threshold for m, if we used your line of argument.

I think there's another issue in the way the main lemma is interpreted

in your argument. It seems to assume that it is OK so long as the *upper

bound* on the distinguishing probability is <= 1. But the distinguishing

probability, as the absolute difference between two probabilities, can

never exceed 1, so worrying about an upper bound getting beyond 1 is not

meaningful.

On the other hand, allowing the distinguishing probability to reach

*any* constant threshold is bad. Actually, allowing the distinguishing

probability to reach *any* threshold of the form n^-c (c > 0) is bad

because you can magnify it to a constant level in polynomial time.

I think the interpretation in your argument is at once too pessmistic in

one regard, and not conservative enough in another.

> 2. The Luby-Rackoff paper is actually not quite enough if you want

> to use their construction recursively. You need to look to modern

> generalizations. In particular, LR prove

> If the Feistel function is truly random, then

> the 4-round cipher is pseudorandom.

> Note that they require a truly random (unconditionally secure)

> Feistel function, so if you try to instantiate the Feistel function

> using a recursive LR construction, the original LR theorem doesn't

> apply. Since then, others have made the slight generalization to

> the case where the Feistel function is assumed only to be pseudorandom

> (e.g., Maurer, Lucks, Naor/Reingold, etc.). Let q-pseudorandom

> refer to a keyed function that is indistinguishable from its idealized

> version if the adversary has access to at most q texts. Then the

> modern form of the Luby-Rackoff theorem is

> If the Feistel function is q'-pseudorandom, then

> the 4-round cipher is q-pseudorandom.

> In particular, q is related to q' by q ~ min(q',2^{n/2}) where

> n is as above, i.e., q ~ min(q',2^{n'/4}). This is why the q'

> appears in my statement of the theorem but does not appear in

> the original Luby-Rackoff paper.

I'm not faimilar with the newer results so I can't discuss them

intelligently, but I'd appreciate some pointers so that I can get

updated on the developments.

You don't need to use newer and more precise results to argue about the

"security" of recursive Luby-Rackoff constructions. It's true that the

main lemma was proved assuming the F functions are truly random. But the

security of a recursive construction comes from the definition of

psuedorandomness. Basically if you can find a distinguisher for the

recursive construction, you can turn it into a distinguisher for the

inner construction, contradicting the main lemma.

The preceeding is akin to the argument that if you can securely extend a

random bit string by 1 bit, you can turn it into a pseudorandom

generator by repeatedly use the primitive to extend the string by a

polynomial amount.

At this level of precision, we are still talking about asymptotic

behavior; many practically relevant considerations are swept under the

rug. I'm not surprised if somebody refined the model to expose practical

differences between the Luby-Rackoff construction and its recursive

application.

Jun 3, 2001, 1:47:30 PM6/3/01

to

I just realized that allowing 2^{n/4} queries (n = block size) is

incompatible with the notion of pseudorandomness used in the

Luby-Rackoff paper. (Polynomial-size oracle circuits cannot have a

superpolynomial # of oracle gates). I need to think about the

implications some more.

incompatible with the notion of pseudorandomness used in the

Luby-Rackoff paper. (Polynomial-size oracle circuits cannot have a

superpolynomial # of oracle gates). I need to think about the

implications some more.

Jun 3, 2001, 5:02:32 PM6/3/01

to

Nicol So wrote:

>The construction is secure iff *asymptotically* [...]

>The construction is secure iff *asymptotically* [...]

Yeah, yeah, I know. I was hoping to not have to get into the

difference between asymptotic treatments and concrete security,

but I guess I should have known. :-) I am too lazy to give all

the details.

Concrete security is where you measure exactly the number of

texts and the advantage (the distinguishing probability), rather

than talking about asymptotics and polynomials and big-O notation.

Personally, I prefer the concrete security, and in this case,

you can remove the asymptotics pretty easily. In a concrete security

treatment of the Luby-Rackoff theorem, one can show that m^2/2^n is

an exact bound on the distinguishing probability (no constant factors

needed), if I'm remembering correctly.

This is why I used an expression like m ~ 2^{n/2}, rather than

m = 2^{n/2}: the "~" is intended to be a warning that this isn't

an exact equality (or if you want to think of it as an equality,

you shouldn't take it too seriously). In particular, if you want

an upper bound e on the distinguishing probability, you want

m^2/2^n <= e, and in general, e << 1.

If you prefer asymptotics, you can think of "~" as representing

asymptotic equivalence, disregarding constant (and polynomial) factors.

So, if you prefer to use asymptotics, you should interpret my claim

to mean that the LR cipher is secure so long as m/2^{n/2} -> 0 faster

than any polynomial as n -> infinity, or something like that.

But I personally happen to feel that worrying over these technical

issues distracts from what's really going on in the theorem.

>We cannot take the expression of an upper bound, and

>then argue that if you choose m to violate it, the construction suddenly

>becomes insecure. The upper bound in the main lemma represents *a*

>sufficient condition for security, [...]

Actually, as I mentioned in my original post, the m^2/2^n bound

is tight. In particular, there are explicit attacks (lower bounds)

that are within a constant factor of the LR upper bound. As a

consequence, the LR bound is a sufficient *and necessary* condition.

The original Luby-Rackoff paper is probably not the best place to

be looking for what is currently known on the Luby-Rackoff construction.

More is known today.

>I think there's another issue in the way the main lemma is interpreted

>in your argument. It seems to assume that it is OK so long as the *upper

>bound* on the distinguishing probability is <= 1.

Yeah, yeah, ok. As I wrote above, my post was only intended to

give the rough estimate. You can make this all precise by using

the notion of advantage (the distinguishing probability, a difference

of two probabilities); then the LR bound says that the advantage of

any adversary is <= m^2/2^n.

>I'm not faimilar with the newer results so I can't discuss them

>intelligently, but I'd appreciate some pointers so that I can get

>updated on the developments.

Alas, now that I looked again, I didn't find any that really capture

everything I wanted, i.e., (1) concrete security (rather than

asymptotics), and (2) the PRF->PRP theorem (rather than just the

information-theoretic case where the Feistel function is a truly

random function). But here are the best two references:

Naor & Reingold: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/lr_abs.html

(see Theorem 3.1; covers part (2) but not (1))

Rogaway's class notes: http://www.cs.ucdavis.edu/~rogaway/classes/227/winter99/

(see Lecture 3; covers part (1) but not (2))

Here are two other papers that are probably less useful, but I'll

include a pointer just for completeness:

Lucks: http://th.informatik.uni-mannheim.de/m/lucks/papers/LR-fast.ps.gz

Maurer: ftp://ftp.inf.ethz.ch/pub/publications/papers/ti/isc/wwwisc/Maurer92d.ps

>You don't need to use newer and more precise results to argue about the

>"security" of recursive Luby-Rackoff constructions. It's true that the

>main lemma was proved assuming the F functions are truly random. But the

>security of a recursive construction comes from the definition of

>psuedorandomness. Basically if you can find a distinguisher for the

>recursive construction, you can turn it into a distinguisher for the

>inner construction, contradicting the main lemma.

Yes, that's true, but the key thing is to measure concretely the

lower bound on how many texts would be needed by this distinguisher.

In particular, you'll find that, by this measure, security degrades

as you use the recursive construction, once you remove the asymptotics.

Jun 3, 2001, 5:04:29 PM6/3/01

to

Nicol So wrote:

>I just realized that allowing 2^{n/4} queries (n = block size) is

>incompatible with the notion of pseudorandomness used in the

>Luby-Rackoff paper. (Polynomial-size oracle circuits cannot have a

>superpolynomial # of oracle gates).

>I just realized that allowing 2^{n/4} queries (n = block size) is

>incompatible with the notion of pseudorandomness used in the

>Luby-Rackoff paper. (Polynomial-size oracle circuits cannot have a

>superpolynomial # of oracle gates).

Yes, Luby-Rackoff only considered attackers that make a polynomial

number of chosen-text queries to the cipher. But it turns out that

this restriction is not essential; the LR result was subsequently

generalized to hold for any number of queries. See the introduction to

the following paper for a long list of references and further discussion.

http://www.cs.berkeley.edu/~daw/papers/prf-crypto98-long.ps

Jul 1, 2001, 8:17:10 PM7/1/01

to

David Wagner wrote:

>

> Nicol So wrote:

> >I could be wrong, but I don't think the Luby-Rackoff results are of

> >that form.

>

> They are. If you want to build a cipher with a n-bit block,

> Luby-Rackoff only guarantees security up to q ~ min(2^{n/4},q') chosen

> texts, assuming that the Feistel function is secure with up to q'

> chosen texts.

>

> Nicol So wrote:

> >I could be wrong, but I don't think the Luby-Rackoff results are of

> >that form.

>

> They are. If you want to build a cipher with a n-bit block,

> Luby-Rackoff only guarantees security up to q ~ min(2^{n/4},q') chosen

> texts, assuming that the Feistel function is secure with up to q'

> chosen texts.

A 2n bit LR construct using n bit Fs is secure for min(2^n,q')

queries, assuming that those Fs are secure for up to q' queries.

An n bit Random Function is secure for up to 2^n queries.

An n bit Random Permutation is secure for up to 2^n-1 queries (I think).

A 128 bit LR construct using 64 bit RFs is secure for 2^32 queries.

A 64 bit LR construct using 32 bit RFs is secure for 2^16 queries.

A 32 bit LR construct using 16 bit RFs is secure for 2^ 8 queries.

A 16 bit LR construct using 8 bit RFs is secure for 2^ 4 queries.

The Turtle block cipher recurses all the way from a 128 bit block cipher

downwards, with an 8 bit Random Permutation for bottoming out (well,

actually psuedo random permutation, but it's created via shuffling, so

we can assume that it's close enough). The math up above seems to imply

that Turtle is provably secure for approximately 2^4 blocks.

> This bound is tight: There are attacks that can

> distinguish a Luby-Rackoff cipher from an ideal cipher with O(2^{n/4})

> texts, for example.

Yes, but how much do the weaknesses propogate upwards in a recursive

structure? I'd be surprised if there is a way to distinguish 128 bit

Turtle with only 2^4 chosen texts.

> Let's say you want to use Luby-Rackoff twice to build a n-bit block

> cipher. You're going to use Luby-Rackoff to build the n/2-bit Feistel

> function, and so this Feistel function will only be secure up to q' ~

> 2^{n/8} texts. As a consequence, the entire cipher will only be

> guaranteed secure up to q ~ 2^{n/8} texts as well.

>

> For instance, suppose you want to build a 128-bit block cipher. With

> plain Luby-Rackoff, you can build one that is secure for up to 2^32

> texts. With two levels of recursion, it is secure only up to 2^16

> texts. And so on.

s/it is secure up to/it is provably secure for up to/;

It's probably (though not provably) more secure than that.

If you could make a distinguisher for a 128 bit LR double-recursion

cipher which needs only 2^16 chosen texts, I'd be surprised. The proof

only says that you can't do it with less than that, not that that's the

most you'll need.

> Hence my conclusion: you can use Luby-Rackoff recursively, but the

> security guarantees get progressively weaker each time you do

> (assuming the block size is held constant).

--

The longer a man is wrong, the surer he is that he's right.

Jul 1, 2001, 9:20:22 PM7/1/01

to

"Benjamin Goldberg" <gol...@earthlink.net> wrote in message

news:3B3FBD86...@earthlink.net...

> David Wagner wrote:

> >

> > Nicol So wrote:

> > >I could be wrong, but I don't think the Luby-Rackoff results are of

> > >that form.

> >

> > They are. If you want to build a cipher with a n-bit block,

> > Luby-Rackoff only guarantees security up to q ~ min(2^{n/4},q') chosen

> > texts, assuming that the Feistel function is secure with up to q'

> > chosen texts.

>

> A 2n bit LR construct using n bit Fs is secure for min(2^n,q')

> queries, assuming that those Fs are secure for up to q' queries.

>

> An n bit Random Function is secure for up to 2^n queries.

> An n bit Random Permutation is secure for up to 2^n-1 queries (I think).

>

> A 128 bit LR construct using 64 bit RFs is secure for 2^32 queries.

> A 64 bit LR construct using 32 bit RFs is secure for 2^16 queries.

> A 32 bit LR construct using 16 bit RFs is secure for 2^ 8 queries.

> A 16 bit LR construct using 8 bit RFs is secure for 2^ 4 queries.

>

> The Turtle block cipher recurses all the way from a 128 bit block cipher

> downwards, with an 8 bit Random Permutation for bottoming out (well,

> actually psuedo random permutation, but it's created via shuffling, so

> we can assume that it's close enough). The math up above seems to imply

> that Turtle is provably secure for approximately 2^4 blocks.

Ah close but no cigar.

This is only true if you are given the output directly of each LR. i.e if I

give you the outputs of all 16-bit, 32-bit, ... LRs then yes 2^4 would be

the bound. But you are not.

> > This bound is tight: There are attacks that can

> > distinguish a Luby-Rackoff cipher from an ideal cipher with O(2^{n/4})

> > texts, for example.

>

> Yes, but how much do the weaknesses propogate upwards in a recursive

> structure? I'd be surprised if there is a way to distinguish 128 bit

> Turtle with only 2^4 chosen texts.

They might be. There is a way to distinguish slightly reduced MARS with

only 8 texts...

Tom

Jul 1, 2001, 11:52:36 PM7/1/01

to

Benjamin Goldberg wrote:

>A 2n bit LR construct using n bit Fs is secure for min(2^n,q')

>queries, assuming that those Fs are secure for up to q' queries.

>A 2n bit LR construct using n bit Fs is secure for min(2^n,q')

>queries, assuming that those Fs are secure for up to q' queries.

Nope. It is only secure for up to min(2^{n/2},q') queries.

>A 128 bit LR construct using 64 bit RFs is secure for 2^32 queries.

>A 64 bit LR construct using 32 bit RFs is secure for 2^16 queries.

>A 32 bit LR construct using 16 bit RFs is secure for 2^ 8 queries.

>A 16 bit LR construct using 8 bit RFs is secure for 2^ 4 queries.

This part *is* correct. I suspect you just had a typo for the

general case.

By the way, here's an argument that only O(2^{n/2}) chosen

plaintexts are needed to recognize a LR cipher with 2n-bit block.

Consider the following attack: Choose 2^{n/2} plaintexts of the

form (a_i,0). Look for i,j so that the partial encryptions of

(a_i,0) and (a_j,0) have a difference of the form (a_i xor a_j,0)

after two rounds of encryption. According to the birthday paradox,

such a pair i,j will exist with good probability. Moreover, in

this case, the corresponding ciphertexts will have a difference

of the form (a_i xor a_j, x) for some value x. Thus, such a pair

can be recognized.

We can see that such a pair occurs in a 4-round Luby-Rackoff with

about double the probability that one would expect for an ideal

cipher, and thus the LR cipher can be distinguished from an ideal

cipher with a 2n-bit block using O(2^{n/2}) chosen plaintexts.

Jul 1, 2001, 11:55:05 PM7/1/01

to

Benjamin Goldberg wrote:

>The Turtle block cipher recurses all the way from a 128 bit block cipher

>downwards, with an 8 bit Random Permutation for bottoming out (well,

>actually psuedo random permutation, but it's created via shuffling, so

>we can assume that it's close enough). The math up above seems to imply

>that Turtle is provably secure for approximately 2^4 blocks.

>The Turtle block cipher recurses all the way from a 128 bit block cipher

>downwards, with an 8 bit Random Permutation for bottoming out (well,

>actually psuedo random permutation, but it's created via shuffling, so

>we can assume that it's close enough). The math up above seems to imply

>that Turtle is provably secure for approximately 2^4 blocks.

Right.

>Yes, but how much do the weaknesses propogate upwards in a recursive

>structure? I'd be surprised if there is a way to distinguish 128 bit

>Turtle with only 2^4 chosen texts.

Unknown. It would surprise me if there is an attack that breaks Turtle

with only 2^4 chosen texts, but what do I know? In any case, there is

no proof either way, as far as I know.

On the other hand, the only reason I can see why one might prefer a

recursive Luby-Rackoff construction is the hope for provable security.

Such recursive ciphers are likely to be quite slow in practice, and

hence otherwise undesirable. Since your example shows that provable

security seems hard to achieve (for realistic parameter choices), this

makes it hard to justify using a recursive construction.

Jul 2, 2001, 7:29:00 AM7/2/01

to

David Wagner wrote:

>

> Benjamin Goldberg wrote:

> >A 2n bit LR construct using n bit Fs is secure for min(2^n,q')

> >queries, assuming that those Fs are secure for up to q' queries.

>

> Nope. It is only secure for up to min(2^{n/2},q') queries.

>

> Benjamin Goldberg wrote:

> >A 2n bit LR construct using n bit Fs is secure for min(2^n,q')

> >queries, assuming that those Fs are secure for up to q' queries.

>

> Nope. It is only secure for up to min(2^{n/2},q') queries.

Sorry, typo.

> >A 128 bit LR construct using 64 bit RFs is secure for 2^32 queries.

> >A 64 bit LR construct using 32 bit RFs is secure for 2^16 queries.

> >A 32 bit LR construct using 16 bit RFs is secure for 2^ 8 queries.

> >A 16 bit LR construct using 8 bit RFs is secure for 2^ 4 queries.

>

> This part *is* correct. I suspect you just had a typo for the

> general case.

Yes, thanks for correcting me.

> By the way, here's an argument that only O(2^{n/2}) chosen

> plaintexts are needed to recognize a LR cipher with 2n-bit block.

>

> Consider the following attack: Choose 2^{n/2} plaintexts of the

> form (a_i,0). Look for i,j so that the partial encryptions of

> (a_i,0) and (a_j,0) have a difference of the form (a_i xor a_j,0)

> after two rounds of encryption. According to the birthday paradox,

> such a pair i,j will exist with good probability. Moreover, in

> this case, the corresponding ciphertexts will have a difference

> of the form (a_i xor a_j, x) for some value x. Thus, such a pair

> can be recognized.

>

> We can see that such a pair occurs in a 4-round Luby-Rackoff with

> about double the probability that one would expect for an ideal

> cipher, and thus the LR cipher can be distinguished from an ideal

> cipher with a 2n-bit block using O(2^{n/2}) chosen plaintexts.

Has anyone calculated how many texts are needed to distinguish an

R-round (R > 4) Luby Rackoff?

As stated earlier, if R=4, and the blocksize is 2n bits, and the F

functions are n bit Random Functions, then we need 2^(n/2) texts.

What about when R=6 or 8? Is it easy to extend the proof in this

manner?

Jul 2, 2001, 2:29:04 PM7/2/01

to

Benjamin Goldberg wrote:

>Has anyone calculated how many texts are needed to distinguish an

>R-round (R > 4) Luby Rackoff?

>Has anyone calculated how many texts are needed to distinguish an

>R-round (R > 4) Luby Rackoff?

The best advance I've seen is a lower bound on the security of

6-round Luby-Rackoff by Patarin. The proof is extremely difficult,

and generalizing to more rounds seems even harder. I'm not sure whether

his lower bound is known to be tight or not. It is impressive work.

Here is a citation:

J. Patarin, ``About Feistel Schemes with Six (or More) Rounds,''

{\it Proceedings of the Fifth Fast Software Encryption Workshop},

LNCS 1372, Springer, 1998, pp. 103--121.

Jul 3, 2001, 3:07:27 AM7/3/01

to

Benjamin Goldberg wrote:

>

> David Wagner wrote:

> >

> > Benjamin Goldberg wrote:

> > >A 2n bit LR construct using n bit Fs is secure for min(2^n,q')

> > >queries, assuming that those Fs are secure for up to q' queries.

> >

> > Nope. It is only secure for up to min(2^{n/2},q') queries.

>

> Sorry, typo.

>

> > >A 128 bit LR construct using 64 bit RFs is secure for 2^32 queries.

> > >A 64 bit LR construct using 32 bit RFs is secure for 2^16 queries.

> > >A 32 bit LR construct using 16 bit RFs is secure for 2^ 8 queries.

> > >A 16 bit LR construct using 8 bit RFs is secure for 2^ 4 queries.

> >

> > This part *is* correct. I suspect you just had a typo for the

> > general case.

>

> Yes, thanks for correcting me.

>

>

> David Wagner wrote:

> >

> > Benjamin Goldberg wrote:

> > >A 2n bit LR construct using n bit Fs is secure for min(2^n,q')

> > >queries, assuming that those Fs are secure for up to q' queries.

> >

> > Nope. It is only secure for up to min(2^{n/2},q') queries.

>

> Sorry, typo.

>

> > >A 128 bit LR construct using 64 bit RFs is secure for 2^32 queries.

> > >A 64 bit LR construct using 32 bit RFs is secure for 2^16 queries.

> > >A 32 bit LR construct using 16 bit RFs is secure for 2^ 8 queries.

> > >A 16 bit LR construct using 8 bit RFs is secure for 2^ 4 queries.

> >

> > This part *is* correct. I suspect you just had a typo for the

> > general case.

>

> Yes, thanks for correcting me.

>

> Has anyone calculated how many texts are needed to distinguish an

> R-round (R > 4) Luby Rackoff?

>

> As stated earlier, if R=4, and the blocksize is 2n bits, and the F

> functions are n bit Random Functions, then we need 2^(n/2) texts.

> What about when R=6 or 8? Is it easy to extend the proof in this

> manner?

> R-round (R > 4) Luby Rackoff?

>

> As stated earlier, if R=4, and the blocksize is 2n bits, and the F

> functions are n bit Random Functions, then we need 2^(n/2) texts.

> What about when R=6 or 8? Is it easy to extend the proof in this

> manner?

What can be easily proven (by decorrelation technics, see

http://lasecwww.epfl.ch)

is that the advantage of the best distinguisher decreases exponentially

with the

number of rounds as long as it is initially < 1/2 with the same number

of texts:

with the LR Theorem, we can prove that the best advantage against R=4 is

< 1/2,

so we can deduce it is arbitrarily small when R increases.

For bounds with higher number of texts, the only reference is Patarin.

The bound

is amplified in the very same way by the above result.

Serge

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu