Catch up on stories from the past week (and beyond) at the Slashdot story archive


Forgot your password?

Comment Re:No weakness (Score 1) 300

A "perfect" cryptographic hash must meet three criteria:

a) The best herustic for determining an input which will produce the same hash as a specific target input will require as many steps on average as brute-forcing. (ie: the probability of getting a collision is the same whether you are using a programmatic solution or guessing.)

b) If inputs A, A' and A'' produce the same output, where A and A' are known, the best herustic for determining A'' will remain no better than one that brute-forces.

c) If inputs A and A' produce the same output as each other, inputs B and B' likewise produce the same output as each other, and so on for some statistically-significant number of distinct outputs, the outputs will follow a random distribution.

In other words, the apparent strength of the hash is the actual strength of the hash, no matter how much information has been obtained (either by analysis or by chance). There are two "obvious" properties which are necessary but not in themselves sufficient to produce those criteria. These properties are:

a) The change in output in relation to a given change in input will follow a random distribution.

b) Where the change in input is a fixed increment of any kind, neither the output nor the change in output nor any other order differential may be constant or cycle as a whole (though unpredictable repeats are a requirement of randomness), no matter what the period of that cycle would be.

These properties are common to almost all systems that are sensitive to initial conditions, which is why some of the more elaborate hashing schemes use well-understood chaotic systems rather than trying to mess around with the underlying cryptographic theory. If you know the system is deterministic (ie: for identical input it must produce identical output) but is non-predictable (ie: there exists no method whatsoever for figuring out the output - or even guessing the range it might fall in, other than the entire allowable range - for a given input except to perform the operation) then predicting a collision should be impossible. In practice, chaotic systems aren't the easiest of beasts to work with when you want fixed-length hashes and you want them yesterday. You could produce extremely strong cryptographic hashes chaotically if you don't mind waiting a day or two for each one.

In practice, no cryptographic hash will be totally "perfect", it can only be approximate. And the faster it needs to be, the more shortcuts you need to take, so the less perfect it can be even in theory. This is one reason there is some commentary on the SHA3 mailing list on whether speed should be as emphasized in the current test as the criteria suggest - that maybe NIST should relax that a little and get something stronger. Weaknesses in MD4, MD5 and even IPSec have been pointed out in respect to an overemphasis on speed in the past. Not sure on how far you could go with that, but the very impressive speedups achieved on the posted hashes suggests that the speed of the algorithm is a non-issue, that there are so many avenues for making the code faster that you can disregard that side of things almost entirely. At least for this contest. The better choice may well end up being the stronger choice, no matter what the relative performance of the reference implementations.

Comment Re:Kudos to NSA (Score 1) 140

I could be wrong, but take a look at the following extract from the linked article:

"These patents--numbers 5,206,951, 5,421,012, and 5,226,161--referred to the integration of data between object managers, and between data managers, and to the integration of different programs that were manipulating data of different types."

To me, this sounds like an implementation of Java issue, not an issue with Java as a language. You could implement all kinds of mechanisms in the JVM that did the same thing but were not covered by those patents.

Comment Re:Kudos to NSA (Score 1) 140

The implementation of a business method or algorithm is patentable, but the semantics fall short of a full implementation. Also, patents are not supposed to include those things which are "obvious". You could not patent the AND operator, for example, even if there was no prior art. (Ok, the USPO gets muddled on what is "obvious", which is why the one-click patent may or may not actually be valid.) For the most part, instructions in a language are "obvious" and also have oodles of prior art. It would be very hard to invent a computer language in which an instruction has syntax and semantics different from a conventional programming language in some non-trivial way and in which the instruction is still useful. Even then, interfaces are generally ruled unpatentable for the reason stated at the start - they're not an implementation, they merely describe in a highly abstract way what the end result of any member of the entire class of implementations would be. That's too vague. You can't patent ranges of inventions, only a specific invention.

In this case, the language is based on Haskell, so prior art immediately applies. A patent that attempts to cover a pre-existing method (obvious or not) should - if the judge is sober - be thrown out of court so fast it reaches escape velocity. Preferably along with any USPO clerk that allowed it. Since most crypto operations are likely to be simple boolean operands, power functions or modulo, and since these all exist in pretty well nearly all programming languages, anything not Haskell-specific is going to be prior art from somewhere else.

The result is that there is absolutely nothing in Cryptol that can be protected, save the specific implementation provided and there's so far bugger all evidence that their implementation is any more interesting than anyone else's.

Comment Re:Kudos to NSA (Score 1) 140

You can't patent interfaces, only implementations. A language is not an implementation and therefore is inherently unpatentable. Well, except in the US, where apparently icons for data files can be patented. Ok, in theory languages cannot be patented. They don't define a process, they don't describe a mechanism, they merely codify the syntax and semantics of the building-blocks that can be used to build mechanisms or processes.

Comment Re:Kudos to NSA (Score 1) 140

Far as I can see, it's a very trimmed-down formal language and not a whole lot more. Yes, a lot of the work is in the compiler, but there are plenty of well-developed compilers for languages just as well-designed, and a fair few are Open Source, not proprietary or with absurd conditions. And even those which are proprietary, such as Intel or Green Hills, the trial version is full-blown and not a toy edition. Re-implementing Cryptol as a front-end to an existing high-quality compiler, or as a translator (the cryptol-to-something equivalent of f2c) should not be overly difficult. Certainly not as hard as writing a Cryptol compiler from scratch of equal calibre.

As far as whether it would infringe on IP, I doubt it. Microsoft got walloped by Sun over using a trademarked name, not over the language per-se, which is why they could get away with just renaming it. But Microsoft couldn't take action against Mono or any of the Open Source .Net reimplementations because that's not something that can be protected. In this case, the worst that can happen is someone abseils down from a helicopter in the dead of night and sends you on a guided tour of Afghanistan. That's all. They can't sue you.

Linux Business

Submission + - Linux 2.6.28 Stocking Stuffers ( 1

darthcamaro writes: Little penguins all around the world are waiting for Penguin-Master Linus Torvalds to deliver some Glogg inspired Xmas cheer in the form of the new 2.6.28 kernel. Among the innovations in 2.6.28 is ext4 as stable, wireless USB drivers, better KVM support and the GEM graphic memory management technology.
"We now have a proper memory manager for video memory, the GEM [Graphics Execution Manager] memory manager," Greg Kroah-Hartman said. "This gives Linux much better graphics performance than it previously had."


Submission + - What Parallel Programming? ( 1

jd writes: "Lawrence-Livermore publishes a nice summary of many (but not all) of the different ins and outs of parallel programming. Different programming languages implement either different models of parallel programming or radically different interpretations. Examples would include Cilk++ (a modded version of Gnu C++), Erlang and Occam (Pascal derivative with more hacks than a newspaper). You could write a small book on the communications libraries that facilitate parallel programming — not in describing them, just listing them. Everything from the major families of message passing (PVM, MPI and BSP) to sharing memory (Distributed Shared Memory, ccNUMA, RDMA) to remote calls (RMI, Corba, RPC) to platform-specific aids (MOSIX, Keerighed and even TIPC), and beyond. There are way, way too many options and no real good guides on when one options should be used above another. I've done my share of parallel processing, but I want to hear other people's opinions on what solutions they've personally tried, what situations they've thought would work (but didn't) or what situations unexpectedly worked better than they'd hoped."

Submission + - What Parrots Tell us About the Evolution of Birds (

GrrlScientist writes: "One of the most contentious issues among scientists who study the evolution of birds is identifying precisely when the modern birds (Neornithes) first appeared. This is due to conflicts between the fossil record and molecular dating methodologies. But there is another way to address this discrepancy. Because the evolution of parrots and cockatoos reflects the evolution of the birds (Aves) themselves, studying the psittaciformes offers compelling insights into this mystery. Further, because psittaciformes generally are not migratory and because they tend to occupy discrete ranges, their ancient patterns of diversification are easier to discern than for many other taxonomic orders of birds that have dispersed widely."
Operating Systems

Submission + - Linux kernel internals from Process Birth to Death

An anonymous reader writes: The creation and management of user-space processes in Linux have many principles in common with UNIX but also include several unique optimizations specific to Linux. Here, review the life cycle of Linux processes and explore the kernel internals for user process creation, memory management, scheduling, and death.

Comment Re:Why is this shocking? (Score 2, Interesting) 235

Since the number of problem-solvers is independent of the number of problems, and problem-solvers can examine multiple solutions to the same problem, along with a limited range of solutions for many problems, you can expect the number of publications to exceed the number of problems and the number of problem-solvers. However, you are correct that merely increasing the quantity of papers (which is all the current rules do) will cause the quality to suffer. The total thought put in to N papers over a period of time t cannot exceed the total amount of thought the brain can output over time t.

Sure, natural multitaskers will be able to better exploit the total amount of thought the brain can exploit when N exceeds 1, but if N exceeds their threshold, the quality suffers. For the rest of humanity, where single-tasking is the rule, N absolutely has to be 1.

Current funding rules for academia and research labs mean that quantity is profitable, quality is not. That is exactly the wrong way to get any real work done and is partly why papers on hyperdilution and test-tube cold fusion are serious money-spinners. They take no effort to write, get cited lots (even if by debunkers - doesn't matter, since funding is a function of the absolute number of citations and not by whether the citing papers agree), and grab the attention of potential external sponsors who couldn't tell a good paper from a confetti'd dingo's kidneys.

Comment Re:Clueless (Score 1) 194

It's interesting, but predictable (in hindsight). Look at cable television. The US has thousands of channels, but most of them show extremely similar material, if not the same. The capacity to have choice should have, if the Long Tail was correct, engendered choice. In practice, it didn't. As Britain went from BBS's 1 and 2, and ITV, to five terrestrial channels and an ungodly number of satellite stations, the quality of broadcasts has dropped, not risen. The increase in the range of options has led to a reduction in the ability to choose something desirable.

Radio stations show another aspect to all of this. Most radio stations are now owned by a tiny handful of owners, like (Un)Clear Channel. Very few people bothered supporting their local station and very few people complain about the absolute uniformity in things like playlists today. The explosion of apparent choice has killed off the real choices.

I believe the Long Tail could be made to work profitably for on-line vendors, but not until this sort of apparent paradox is resolved. You have to start by making it harder to have stores mass-produced by a virtual xerox. There have to be incentives of some sort to encourage diversity and specialty, as that is when you can really maximize sales on obscure stuff - concentrate it in a few places rather than mush it over everyone.


Submission + - F#'s Syme: Why functional languages are poetic 1

mr sanjeev writes: Don Syme, the developer of F# says he can see the poetry in in functional programming. "I've worked with many languages, from BASIC to assembly code. One of the last check-ins I made when implementing generics for .NET, C# and VB had a lot of x86 assembly code. My first job was in Prolog. I think programmers should learn languages at all extremes. Functional languages attract me because of their simplicity even when solving complex tasks. If you look through the code samples in a book such as F# for Scientists they are breathtaking in their elegance, given what they achieve. A good functional program is like a beautiful poem: you see the pieces of a 'solution' come together. Of course, not all programs end up so beautiful. It's very important that we tackle 'programming in the large' as well. That's what the object-oriented features of F# are for." And what languages should developers learn? "F#, Python, Prolog, Haskell, C# and Erlang!"

Submission + - Republican IT Specialist Dies in Plane Crash ( 1

nbauman writes: Surprisingly ignored by the NYT, WSJ, and Washington Post is this story, the least-conspiratorial version of which is on Democracy Now:

"A top Republican internet strategist who was set to testify in a case alleging election tampering in 2004 in Ohio has died in a plane crash. Michael Connell was the chief IT consultant to Karl Rove and created websites for the Bush and McCain electoral campaigns. Michael Connell was deposed one day before the election this year by attorneys Cliff Arnebeck and Bob Fitrakis about his actions during the 2004 vote count in Ohio and his access to Karl Rove's email files and how they went missing."

"The lawyers in the case refer to him as a high-IQ Forrest Gump, by which they mean that he seems to have been present at the scene of every dubious election of the last eight years," Florida 2000, Ohio in 2004, Alabama 2002, Don Siegelman's re-election for governor, the Saxby Chambliss-Max Cleland Senate race in Georgia 2002, said Mark Crispin Miller. "To be Karl Rove's IT guru seems to have meant basically setting it up so that votes could be electronically shaved to the disadvantage of the Democrats and the advantage of Republicans."

The suggestion that Republicans murdered Connell to keep him from exposing their voter fraud is far-fetched and ridiculous.

Slashdot Top Deals

Whoever dies with the most toys wins.