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 candidates have addressed the issue. 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: http://allmydata.org/source/tahoe/trunk/docs/about.html 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 adds logging/operations/deployment improvements. 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, at your option.) INSTALLATION Tahoe works on Linux, Mac OS X, Windows, Cygwin, and Solaris. For installation instructions please see docs/install.html [8]. HACKING AND COMMUNITY Please join us on the mailing list [9] to discuss uses of Tahoe. 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. SPONSORSHIP Tahoe is sponsored by Allmydata, Inc. [13], a provider of commercial backup services. Allmydata, Inc. contributes hardware, software, ideas, bug reports, suggestions, demands, and money (employing several allmydata.org Tahoe hackers and instructing them to spend part of their work time on this free-software project). Also they distribute customized t-shirts just for
