### Misinformation: new crypto product

```A recent press release about a new cryptographic product, Permanent
Privacy (P.P.), mentioning my name, has led to a slew of
dramatically mistaken reports. Corrections: I have never had a
cryptography-related connection to Harvard. I had nothing to  do with
the press release.

Concerning my alleged support for the claim that P.P. provides
...the world's first practical data encryption system that is
absolutely unbreakable.:

Its practical versions are not absolutely unbreakable, as I tried
hard to convince them. The only claim I ever supported was that if
the additive stream cipher that is one component of P.P. consists of
a properly managed 'One-Time-Pad', it (obviously) provides
unbreakable encryption.

Peter Schweitzer

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

```

### Re: Looking through a modulo operation

```On Sun, Jul 20, 2008 at 04:14:33PM -0600, Matt Ball wrote:

From a little bit of off-line discussion, I think I've got a restatement of
the problem that is more suitable to those with a stronger programming
background than mathematical background:

If someone uses the __random32 function as defined in the 2.6.26 Linux
kernel, and leaks to you the result of taking successive outputs modulo
28233 (= 9 * 3137), can you determine the probable 96-bit internal state
with fewer than 1000 outputs and with modest processing power (e.g., a
laptop computer running less than a day)?

Here is a C implementation of __random32:

typedef unsigned long u32;
struct rnd_state { u32 s1, s2, s3; };
static u32 __random32(struct rnd_state *state)
{
#define TAUSWORTHE(s,a,b,c,d) ((sc)d) ^ (((s a) ^ s)b)

state-s1 = TAUSWORTHE(state-s1, 13, 19, 4294967294UL, 12);
state-s2 = TAUSWORTHE(state-s2,  2, 25, 4294967288UL, 4);
state-s3 = TAUSWORTHE(state-s3,  3, 11, 4294967280UL, 17);

return (state-s1 ^ state-s2 ^ state-s3);
}

After any consecutive 96 outputs, the 97th is a fixed linear function of
those just observed. It is not necessary to determine the internal state.

The internal state is s_n = (A**n)(s_0) for a fixed 96x96 matrix A (the
fact that it is a direct product of 3 32-bit matrices is not important).
This matrix has a minimum polynomial of degree at most 96.

A**96 = c_95 * A**95 + c_94 * A**94 ... + c_0 * I

The 32-bit output then also satisfies:

x_96 = c_95 * x_95 + c_94 * x_94 ... + c_0

for the same coefficients.

--

/\ ASCII RIBBON  NOTICE: If received in error,
\ / CAMPAIGN Victor Duchovni  please destroy and notify
X AGAINST   IT Security, sender. Sender does not waive
/ \ HTML MAILMorgan Stanley   confidentiality or privilege,
and use is prohibited.

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

```

### Re: Looking through a modulo operation

```Florian Weimer writes:
I've got a function f : S - X x S where S = (Z/2Z)**96 and
X = (Z/2Z)**32.  Suppose that s_0 is fixed and (x_i, s_i) = f(s_{i-1}).
(f implements a PRNG.  The s_i are subsequent internal states and the
x_i are results.)

Now f happens to be linear.  I know the values of x_i, x_{i+1}, ...,
x_{i+k} modulo N, [where N = 28233].
Is it possible to recover s_i with reasonable effort (better than brute
force, and k should be in the hundreds, not thousands)?

Yes.  I will show two attacks.  The results: Attack #1 is a
straightforward improvement to exhaustive search, and takes 2^52 work (~
10-20 CPU-years?).  Attack #2 is a more sophisticated meet-in-the-middle
attack, and takes 2^37 work and 2^35 space; the best instantiation I've
found looks like it would involve 16GB of RAM and a few days or weeks
of computation.  Both attacks recover the entire state of the PRNG,
given only a handful of known outputs.  It's possible there may be
other, better attacks.

My conclusion is that this PRNG is not cryptographically strong and
should not be used anywhere that you may face an adversary who is
motivated to break the PRNG.  In short, this PRNG is broken.

Attack #1: Given x mod N, there are only about 2^32/28233 = 2^17.2
possibilities for x, and it's easy to enumerate them all.  Suppose we
know x_1 mod N, x_2 mod N, ..., x_7 mod N.  Enumerate all
(2^17.2)^3 = 2^51.6 possibilities for x_1, x_2, and x_3.  For each
such possibility, you know 96 bits of output from a linear system,
and there are 96 unknowns, so you can solve for s_0.  Given s_0,
you can compute the predicted value of x_4, .., x_7 and compare them
to the observed values of x_4 mod N, etc.  If everything matches,
you've found the original seed s_0 and broken the PRNG.

This requires trying 2^51.6 possibilities, so it's a bit less than
2^51.6 work.  That's already a small enough number that the system
is not cryptographically secure.

This can be sped up slightly by noting that x_4 is a linear function
of x_1,x_2,x_3.  We can precompute the form of that linear function
and express it as a 32x96 matrix.  The best approach I can see will take
something like 500 CPU cycles to compute x_4 from x_1,..,x_3, so I'd
expect the total number of CPU cycles needed at something like 2^60.6
or so.  On a 4GHz machine, that's like 13 CPU-years.  Of course it is
trivially parallelizable.

Attack #2: If we were given inferred values of x_1, x_2, x_3, and x_4,
we could check them for consistency, since they represent 128
equations in 96 unknowns.  In particular, we can find a linear function
g from 128 bits to 32 bits such that g(x_1,x_2,x_3,x_4) = 0 if
x_1,..,x_4 are consistent with having been produced by this PRNG.
In fact, this can be broken down further, so that if x_1,..,x_4
are consistent, they will satisfy this equation:
h(x_1,x_2) = h'(x_3,x_4).
Call this the check equation.  Here h,h' are linear functions from 64
bits to 32 bits, so if x_1,..,x_4 are not consistent, they have only a
2^-32 chance of satisfying this check equation.

Suppose we are given x_1 mod N, .., x_8 mod N.  We'll enumerate all
2^34.4 possibilities for x_1,x_2, compute h(x_1,x_2) for each, and
store them in a hash table or sorted list keyed on the 32-bit value
of h(x_1,x_2).  Once that table is built, we'll enumerate all 2^34.4
possibilities for x_3,x_4, compute h'(x_3,x_4) for each, and find
all occurrences in the table where
h(x_1,x_2) = h'(x_3,x_4).
On average, we expect to find about 2^34.4/2^32 = 2^2.4 matches.
For each such match, compute the predicted value of x_5 as a function
of x_1,..,x_4 and see whether it agrees with the observed value of
x_5 mod N, etc., to weed out false matches.  In total, you'll need
to explore 2^34.4 + 2^34.4*2^2.4 ~= 2^37 possibilities, and you'll
need space for 2^34.4 entries in the table.

We can store the table as a sorted list.  This list will take up about
1600 GB, and you could buy enough hard disks for that at ~ \$2000, say.
You can add an index in memory that tells you, for each value of
h(x_1,x_2), which block or sector on disk those entries of the list is
found at.  You'll need to make 2^34.4 random seeks into this hard disk
array.  With good disk head scheduling algorithms you might be able to
get the seek time down a bit, but even optimistically we're probably
still talking about a year of computation.

Fortunately, we can trade time for space.  With 16GB of RAM, we can
store 1/128th of the list: namely, all values where the low 7 bits
of h(x_1,x_2) are some fixed value V.  We cycle through all choices
of V, repeating the attack once for each V.  With this choice, I expect
the amount of time spent waiting for RAM to be comparable to the CPU
cost of the attack.  For each V, we have to evaluate a linear function
2^35.4 times.  It looks to me like this will take a few CPU-days.

Disclaimers: I have not checked any of the above analysis.  I have
not implemented it to test whether these attacks actually work.  Even
if the ```

### Re: Looking through a modulo operation

```On Mon, Jul 21, 2008 at 12:03:50PM -0400, Victor Duchovni wrote:

On Sun, Jul 20, 2008 at 04:14:33PM -0600, Matt Ball wrote:

From a little bit of off-line discussion, I think I've got a restatement of
the problem that is more suitable to those with a stronger programming
background than mathematical background:

If someone uses the __random32 function as defined in the 2.6.26 Linux
kernel, and leaks to you the result of taking successive outputs modulo
28233 (= 9 * 3137), can you determine the probable 96-bit internal state
with fewer than 1000 outputs and with modest processing power (e.g., a
laptop computer running less than a day)?

I skipped over this part when reading the original message. Expecting per
Florian's original message the outputs to be a linear function of the
inputs, but they are not.

After any consecutive 96 outputs, the 97th is a fixed linear function of
those just observed. It is not necessary to determine the internal state.

This of course applies to the 32-bit output of the RNG. The operation
of reducing the 32-bit output modulo 28333, is not linear (over the
F_2 bit string vector-space). While:

x_96 = c_95 * x_95 + ... c_0 * x_0

this is only true bitwise modulo 2. It is not obvious how one might
recover the full 32-bit outputs from the truncated outputs.

--

/\ ASCII RIBBON  NOTICE: If received in error,
\ / CAMPAIGN Victor Duchovni  please destroy and notify
X AGAINST   IT Security, sender. Sender does not waive
/ \ HTML MAILMorgan Stanley   confidentiality or privilege,
and use is prohibited.

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

```

### WPost: Cybersecurity Will Take A Big Bite of the Budget

```[News report below.]

This highly classified little-publicized multi-billion dollar vague
program to secure Federal computers seems doomed to failure.  People
like you and I, in the unclassified private sector, design and build
and program all those computers and networks.

But of course we've never heard of this initiative.  And we probably
don't share its goals.

NSA's occasional public efforts to secure the civilian infrastructure
have been somewhat interesting.  Not that they've succeeded: they
crippled DES, wouldn't admit it was broken, and tried to force us all
to use it; the IPSEC they designed was painfully complex, impossible
to administer, easy to penetrate, and wouldn't scale; the export
controls they championed torpedoed civilian efforts to secure
ANYTHING; and Secure Linux seems to be no more secure than any other
Linux.  Do we know of *any* honest and successful NSA effort to raise
the integrity and security of the public infrastructure (even at the
expense of their ability to illegally tap it)?

Now that NSA, the President, and Congress have gone totally to the
Dark Side, we'd better assume that any such initiative does not have
the public's best interests at heart.  The theory is that the public's
computers will be easy for the government to break into, while
Wiretapper-General McConnell can shield every unconstitutional thing
he does from the prying eyes of the public and the courts?  It'd be
better for private-sector engineers to follow our own muses, rather
than become the rats following government-contractor Pied Pipers into
a totalitarian sewer.

Let's guess why they would classify this effort at all.  For security
through obscurity?  So that foreigners won't find out how to secure
their own computers against NSA intrusions (ahem, foreigners build ALL
our computers)?  Merely to hide their own incompetence?  Or because
the effort would be quickly identified as malfeasance, like trying to
impose a national ID system and routine suspicionless checkpoint
searches on a free people?

John

Forwarded-By: Melissa Ngo [EMAIL PROTECTED]

http://www.washingtonpost.com/wp-dyn/content/article/2008/07/20/AR2008072001641_pf.html

Cybersecurity Will Take A Big Bite of the Budget
By Walter Pincus
Monday, July 21, 2008; A13

President Bush's single largest request for funds and most important
initiative in the fiscal 2009 intelligence budget is for the
Comprehensive National Cybersecurity Initiative, a little publicized
but massive program whose details remain vague and thus open to
question, according to the House Permanent Select Committee on
Intelligence.

A highly classified, multiyear, multibillion-dollar project, CNCI --
or Cyber Initiative -- is designed to develop a plan to secure
government computer systems against foreign and domestic intruders and
prepare for future threats. Any initial plan can later be expanded to
cover sensitive civilian systems to protect financial, commercial and
other vital infrastructure data.

It is no longer sufficient for the U.S. Government to discover cyber
intrusions in its networks, clean up the damage, and take legal or
political steps to deter further intrusions, Director of National
Intelligence Mike McConnell noted in a February 2008 threat
assessment. We must take proactive measures to detect and prevent
intrusions from whatever source, as they happen, and before they can
do significant damage. His conclusions echoed those of a 2007
interagency review that led to CNCI's creation.

During debate on the intelligence authorization bill last week, Rep.
Jim Langevin (D-R.I.), a member of the House intelligence committee
and chairman of the Homeland Security subcommittee on emerging
threats, described cybersecurity as a real and growing threat that
the federal government has been slow in addressing.

Without specifying funding figures, which are classified, Langevin
said the panel approved 90 percent of the funds requested for CNCI but
warned that the committee does not intend to write the administration
a blank check.

The committee's report recognized that as the initiative develops, it
will be imperative that the government also take into account the
interests and concerns of private citizens, the U.S. information
technology industry, and other elements of the private sector.

Such a public-private partnership will be unlike any model that
currently exists, said the committee, which recommended a White House
study leading toward establishment of an oversight panel of lawmakers,
executive branch officials and private-sector representatives. The
panel would review the intelligence community's development of the
initiative.

The committee said it expects the policy debates over the initiative
to extend into the next administration, and major presidential

On the same day the intelligence bill passed the House, Sen. Barack
Obama (D-Ill.) told an ```

### ANNOUNCING Allmydata.org Tahoe, the Least-Authority Filesystem, v1.2

```
Dear people of the Cryptography mailing list:

The Hack Tahoe! contest (http://hacktahoe.org ) has already led a
security researchers to spot a flaw in our crypto design.  This
release fixes that flaw.

Regards,

Zooko

ANNOUNCING Allmydata.org Tahoe, the Least-Authority Filesystem, v1.2

We are pleased to announce the release of version 1.2.0 of the Tahoe
Least Authority Filesystem.

The Tahoe Least Authority Filesystem is a secure, decentralized,
fault-tolerant filesystem.  All of the source code is available under
a Free Software, Open Source licence (or two).

This filesystem is encrypted and distributed over multiple peers in
such a way it continues to function even when some of the peers are
unavailable, malfunctioning, or malicious.

A one-page explanation of the security and fault-tolerance properties
that it offers is visible at:

This is the successor to Allmydata.org Tahoe Least Authority
Filesystem v1.1, which was released June 11, 2008 [1].  This release
fixes a security issue in Tahoe v1.1, fixes a few small issues in the
web interface, adds a check health operation for mutable files, and

See the known_issues.txt file [2] and the NEWS file [3] for details.

COMPATIBILITY

The version 1 branch of Tahoe is used as the basis of the consumer
backup product from Allmydata, Inc. -- http://allmydata.com .

Tahoe v1.2 is fully compatible with Tahoe v1.0.  v1.2 clients produce
files which can be read by v1.0 clients.  v1.2 clients can read files
produced by clients of all versions = v0.8.  v1.2 servers can serve
v1.0 clients and v1.2 clients can use v1.0 servers.

This is the third release in the version 1 series.  We believe that
this version of Tahoe is stable enough to rely on as a permanent store
of valuable data.  The version 1 branch of Tahoe will be actively
supported and maintained for the forseeable future, and future
versions of Tahoe will retain the ability to read files and
directories produced by Tahoe v1 for the forseeable future.

WHAT IS IT GOOD FOR?

With Tahoe, you can distribute your filesystem across a set of
computers, such that if some of the computers fail or turn out to be
malicious, the filesystem continues to work from the remaining
computers.  You can also share your files with other users, using a
cryptographic capability-based access control scheme.

Because this software is the product of less than two years of active
development, we do not categorically recommend it for the storage of
data which is extremely confidential or precious.  However, we believe
that the combination of erasure coding, strong encryption, and careful
engineering make Tahoe safer than common alternatives, such as RAID,
or traditional backup onto a remote server, removable drive, or tape.

This software comes with extensive unit tests [4], and there are no
known security flaws which would compromise confidentiality or data
integrity.  (For all currently known issues please see the
known_issues.txt file [2].)

This release of Tahoe is suitable for the friendnet use case [5] --
it is easy to create a filesystem spread over the computers of you and
your friends so that you can share disk space and share files.

LICENCE

You may use this package under the GNU General Public License, version
2 or, at your option, any later version.  See the file COPYING.GPL
[6] for the terms of the GNU General Public License, version 2.

You may use this package under the Transitive Grace Period Public
Licence, version 1.0.  The Transitive Grace Period Public Licence says
that you may distribute proprietary derived works of Tahoe without
releasing the source code of that derived work for up to twelve
months, after which time you are obligated to release the source code
of the derived work under the Transitive Grace Period Public
Licence. See the file COPYING.TGPPL.html [7] for the terms of the
Transitive Grace Period Public Licence, version 1.0.

(You may choose to use this package under the terms of either licence,

INSTALLATION

Tahoe works on Linux, Mac OS X, Windows, Cygwin, and Solaris.  For
installation instructions please see docs/install.html [8].

HACKING AND COMMUNITY

Patches that extend and improve Tahoe are gratefully accepted -- the
RoadMap page [10] shows the next improvements that we plan to make and
CREDITS [11] lists the names of people who've contributed to the
project.  The wiki Dev page [12] contains resources for hackers.