Cryptography-Digest Digest #499, Volume #14 Sat, 2 Jun 01 23:13:01 EDT
Contents:
Re: And the FBI, too (Re: National Security Nightmare?) (David Schwartz)
practical birthday paradox issues ("Tom St Denis")
Re: Echelon electronic eavesdropping network (Mok-Kong Shen)
Re: Luby-Rackoff Theorems? ("Tom St Denis")
Re: Luby-Rackoff Theorems? (Nicol So)
Re: Luby-Rackoff Theorems? (Nicol So)
Re: Luby-Rackoff Theorems? (Nicol So)
Re: Luby-Rackoff Theorems? ("Tom St Denis")
bent functions ("Tom St Denis")
Re: practical birthday paradox issues (John Savard)
Re: BBS implementation ("Niels Ferguson")
Re: bent functions ("Douglas A. Gwyn")
Re: bent functions ("Tom St Denis")
Re: practical birthday paradox issues ("Tom St Denis")
Re: practical birthday paradox issues ("Niels Ferguson")
Re: practical birthday paradox issues ("Scott Fluhrer")
Re: practical birthday paradox issues ("Tom St Denis")
----------------------------------------------------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,us.misc
Subject: Re: And the FBI, too (Re: National Security Nightmare?)
Date: Sat, 02 Jun 2001 16:07:53 -0700
Matthew Montchalin wrote:
> | By the way, I'm talking about civilians employed by
> |the NSA, not officers or enlisted personnel assigned to NSA
> |divisions. They seem to be less diligent about putting their
> |badges away before they walk into, say, a Burger King.
> So, how did they get assigned to the NSA divisions in the
> first place? What do their working papers look like? How
> would one division recognize a new recruit? By 'invitation'
> only? What does a typical 'invitation' look like? Is there
> a watermark on the paper? How do they secure their ranks
> when transferring agents electronically?
I honestly have no idea. I only witnessed one event ever that shed any
light on these questions. I'll relate it for its humor value.
I was in the waiting room at the inner perimiter of a facility shared
by the NSA and a few other DoD organizations. There was some slight
confusion about where I was supposed to meet my escort, so I basically
had to stay where I was until my escort realized that I hadn't gotten
through that checkpoint. I couldn't go further in without escort, I
couldn't go further out with my badge, and only my escort could turn in
the badge, so I was basically stuck.
While I was waiting, someone in military uniform walked up to the desk
to report for duty at a new assignment inside that facility. I'm pretty
sure it was NSOC, but I'm not totally sure. He showed his military ID
and she handed him a PIN pad. He pushed a few keys and then she produced
from an envelope his ID to enter that facility. She also handed him a
card with his PIN on it and said that he had to destroy it.
So he memorized it and then ate it. She explained that it was actually
supposed to go back into the envelope to be destroyed at Ft. Meade and
she wasn't sure quite what to do in this case. He said, "You said I
should destroy it". So she took a piece of scrap paper, wrote on it "he
ate it", and sealed it in the envelope. Miraculously, he had no
difficulty using his ID card and entering his PIN to get in.
DS
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: practical birthday paradox issues
Date: Sat, 02 Jun 2001 23:44:14 GMT
Well being the slowest math student on earth I figured out how the birthday
paradox applies to collision in the 2^(n/2) sense...
2^n/2 chosen texts is really (w^2)/2 pairs in this case it would be 2^(n-1)
pairs.
Wow.
Problem is.... if we say something like SHA-1 has a 2^80 resistance to the
bday paradox, don't we need 2^80 memory for all the chosen texts and 2^159
work to find a match? I.e we first need all the texts, then we must try
them as pairs one by one to find the collision?
What am I overlooking? (Keep in mind I am the slowest math student ...
hehehe)
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Echelon electronic eavesdropping network
Date: Sun, 03 Jun 2001 01:52:05 +0200
Nemo psj wrote:
>
> There was supposedly a new report made in the UK. Does anyone here know were I
> can find it?
Do you mean a paper by Duncan Campbell of 27.05, entitled
'COMINT Impact on International Trade'? It is at
http://www.heise.de/tp/deutsch/special/ech/default.html
In a recent thread, someone has given an URL of a draft
document of a temporary committee of the European Parliament:
http://os390-mvs.hypermart.net/encryption.htm
BTW, according to German newspapers, the Echelon station near
Bad Aibling will be abandoned in 2002, probably due to pressure
from the German government but probably also due to availability
of other better technologies (e.g. via satellites) that renders
that station deprecated.
M. K. Shen
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Luby-Rackoff Theorems?
Date: Sun, 03 Jun 2001 00:18:32 GMT
"Nicol So" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> 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.
<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
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Luby-Rackoff Theorems?
Date: Sat, 02 Jun 2001 20:43:38 -0400
Reply-To: see.signature
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.
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, 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.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Luby-Rackoff Theorems?
Date: Sat, 02 Jun 2001 20:44:05 -0400
Reply-To: see.signature
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.
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, 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.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Luby-Rackoff Theorems?
Date: Sat, 02 Jun 2001 20:56:52 -0400
Reply-To: see.signature
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.
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.
--
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.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Luby-Rackoff Theorems?
Date: Sun, 03 Jun 2001 01:14:40 GMT
"Nicol So" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> 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
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: bent functions
Date: Sun, 03 Jun 2001 01:16:44 GMT
Quicky:
A function is bent iff all linear approximations have the same probability
right?
I.e given the output of the walsh transform (I can provide the algorithm for
those that are unfamiliar) you get WT(X) = |2^(q/2)| for all X in Z_(2^q).
Is that right? So for a eight to one boolean function all WT outputs
(ignoring WT(0)) should be |2^4| = |16| right?
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: practical birthday paradox issues
Date: Sun, 03 Jun 2001 02:12:28 GMT
On Sat, 02 Jun 2001 23:44:14 GMT, "Tom St Denis"
<[EMAIL PROTECTED]> wrote, in part:
>don't we need 2^80 memory for all the chosen texts and 2^159
>work to find a match?
No, because we can sort n items with less than n^2 work, so we can get
by with less than 2^159 work. But yes, we do need all that memory,
although some of it can be on tape, not necessarily RAM.
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: "Niels Ferguson" <[EMAIL PROTECTED]>
Subject: Re: BBS implementation
Date: Sun, 3 Jun 2001 04:19:41 +0200
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:VJcS6.11845$[EMAIL PROTECTED]...
[...]
> > Where can I find some info on practical BBS implementation?
>
> Um, square an integer modulo a composite blum integer repeatedly and
output
> the log log n lower bits
I would be careful there. It is a long time ago I looked at these things,
but last I remember the O(ln ln n) lower bits are secure.
This is theoretically interesting, but a useless statement for practical
purposes.
What this means is that there is a constant K > 0 such that the
K * ln ln n lower bits are secure. Without some lower bound on K you
cannot use this as K might be 2^-200 or so. There is a separate proof
that the least significant bit is secure, so you can always use one bit.
BBS is useful because there is a 'proof' of security. If you take more than
a single bit per value, you lose the provable property and you are probably
better of with a (much) faster scheme based on symmetric-key methods.
Cheers!
Niels
--
======================================
Niels Ferguson, cryptography consultant. email: niels at ferguson dot net.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: bent functions
Date: Sun, 03 Jun 2001 02:19:15 GMT
Tom St Denis wrote:
> A function is bent iff all linear approximations have the same
> probability right?
I don't know what that would mean. A bent function is a Boolean
function all of whose (discrete) Fourier coefficients have the same
magnitude. (Feel free to substitute Hadamard/Walsh for Fourier.)
The implication is that indeed there is no "best" linear
approximant to the bent function. (Cryppies would say that "all
the bulges are the same".) This is the analogue of white noise,
and the connection of that with pseudorandomness should be evident.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: bent functions
Date: Sun, 03 Jun 2001 02:25:17 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> > A function is bent iff all linear approximations have the same
> > probability right?
>
> I don't know what that would mean. A bent function is a Boolean
> function all of whose (discrete) Fourier coefficients have the same
> magnitude. (Feel free to substitute Hadamard/Walsh for Fourier.)
> The implication is that indeed there is no "best" linear
> approximant to the bent function. (Cryppies would say that "all
> the bulges are the same".) This is the analogue of white noise,
> and the connection of that with pseudorandomness should be evident.
Yeah, don't the walsh transform masks (i.e the values used in the dot
product) represent the linear equations?
I.e if you have (-1)^((3 dot X) xor (5 dot F(X))) where dot is the binary
dot product. Does this mean that bits 0,1 of the input map to bits 0,2 of
the output... i.e x_0 xor x_1 = y_0 xor y_2 (for some values of x)
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: practical birthday paradox issues
Date: Sun, 03 Jun 2001 02:26:49 GMT
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Sat, 02 Jun 2001 23:44:14 GMT, "Tom St Denis"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >don't we need 2^80 memory for all the chosen texts and 2^159
> >work to find a match?
>
> No, because we can sort n items with less than n^2 work, so we can get
> by with less than 2^159 work. But yes, we do need all that memory,
> although some of it can be on tape, not necessarily RAM.
Do you sort the inputs or the outputs? I would imagine you sort all the
outputs....
Tom
------------------------------
From: "Niels Ferguson" <[EMAIL PROTECTED]>
Subject: Re: practical birthday paradox issues
Date: Sun, 3 Jun 2001 04:30:54 +0200
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:iTeS6.12347$[EMAIL PROTECTED]...
> Well being the slowest math student on earth I figured out how the
birthday
> paradox applies to collision in the 2^(n/2) sense...
>
> 2^n/2 chosen texts is really (w^2)/2 pairs in this case it would be
2^(n-1)
> pairs.
>
> Wow.
>
> Problem is.... if we say something like SHA-1 has a 2^80 resistance to the
> bday paradox, don't we need 2^80 memory for all the chosen texts and 2^159
> work to find a match? I.e we first need all the texts, then we must try
> them as pairs one by one to find the collision?
You need 2^80 memory slots, but this is math so we are not limited by
little things like equipment budgets.
You can find the matches without doing 2^159 work. A simple
general solution is to sort the 2^80 values (in n * ln n time), and
then find the matches in linear time. In practice you use a hash-table
like construction, which requires only 2^80 operations to find
all matches.
Cheers!
Niels
--
======================================
Niels Ferguson, cryptography consultant. email: niels at ferguson dot net.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: practical birthday paradox issues
Date: Sat, 2 Jun 2001 19:33:22 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:iTeS6.12347$[EMAIL PROTECTED]...
> Well being the slowest math student on earth I figured out how the
birthday
> paradox applies to collision in the 2^(n/2) sense...
>
> 2^n/2 chosen texts is really (w^2)/2 pairs in this case it would be
2^(n-1)
> pairs.
>
> Wow.
>
> Problem is.... if we say something like SHA-1 has a 2^80 resistance to the
> bday paradox, don't we need 2^80 memory for all the chosen texts and 2^159
> work to find a match? I.e we first need all the texts, then we must try
> them as pairs one by one to find the collision?
>
> What am I overlooking? (Keep in mind I am the slowest math student ...
> hehehe)
One thing you are overlooking is that by sorting the lists by hash value,
and doing a sequential scan, we can find a match with O(n log n) ~ 2^{86}
time. Sorting is a well-studied problem -- given that we had a place to
store 2^80 elements, and the time to generate all those hashes, the rest
really isn't all that difficult (comparitively speaking, of course).
But, you say, isn't doing all that infeasible? Yes, at current technology,
it is, and that is why NSA settled for 160 bits output for SHA-1...
--
poncho
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: practical birthday paradox issues
Date: Sun, 03 Jun 2001 03:07:04 GMT
"Niels Ferguson" <[EMAIL PROTECTED]> wrote in message
news:9fc7ep$fn0$[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:iTeS6.12347$[EMAIL PROTECTED]...
> > Well being the slowest math student on earth I figured out how the
> birthday
> > paradox applies to collision in the 2^(n/2) sense...
> >
> > 2^n/2 chosen texts is really (w^2)/2 pairs in this case it would be
> 2^(n-1)
> > pairs.
> >
> > Wow.
> >
> > Problem is.... if we say something like SHA-1 has a 2^80 resistance to
the
> > bday paradox, don't we need 2^80 memory for all the chosen texts and
2^159
> > work to find a match? I.e we first need all the texts, then we must try
> > them as pairs one by one to find the collision?
>
> You need 2^80 memory slots, but this is math so we are not limited by
> little things like equipment budgets.
>
> You can find the matches without doing 2^159 work. A simple
> general solution is to sort the 2^80 values (in n * ln n time), and
> then find the matches in linear time. In practice you use a hash-table
> like construction, which requires only 2^80 operations to find
> all matches.
>
Hmm n ln n, is the expected time of quicksort right?
Thanks for the info,
Tom
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
