Luby-Rackoff Theorems?
Tom St Denis
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
Nicol So
>
> 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.
Tom St Denis
"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
David Wagner
>> 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.
Matt Timmermans
"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.
Tom St Denis
"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
Nicol So
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.)
David Wagner
>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).
Tom St Denis
"Nicol So" <nob...@no.spam.please> wrote in message
news:3B190440...@no.spam.please...
> >
> > 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
Nicol So
>
> 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?
Nicol So
>
> 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?
--
Nicol So
>
> 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.
Tom St Denis
"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
David Wagner
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.
Nicol So
>
> 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.
Nicol So
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.
David Wagner
>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.
David Wagner
>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
Benjamin Goldberg
>
> 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.
Tom St Denis
"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
David Wagner
>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.
David Wagner
>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.
Benjamin Goldberg
>
> 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?
David Wagner
>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.
Serge Vaudenay
>
> 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.
>
> 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