Entries Tagged "contests"

Page 5 of 7

SHA-3 Second Round Candidates Announced

NIST has announced the 14 SHA-3 candidates that have advanced to the second round: BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein.

In February, I chose my favorites: Arirang, BLAKE, Blue Midnight Wish, ECHO, Grøstl, Keccak, LANE, Shabal, and Skein. Of the ones NIST eventually chose, I am most surprised to see CubeHash and most surprised not to see LANE.

Here’s my 2008 essay on SHA-3. Here’s NIST’s SHA-3 page. And here’s the page on my own submission, Skein.

Posted on July 24, 2009 at 12:15 PM • View Comments

Fourth Movie-Plot Threat Contest Winner

For this contest, the goal was to:

…to find an existing event somewhere in the industrialized world—Third World events are just too easy—and provide a conspiracy theory to explain how the terrorists were really responsible.

I thought it was straightforward enough but, honestly, I wasn’t very impressed with the submissions. Nothing surprised me with its cleverness. There were scary entries and there were plausible entries, but hardly any were both at the same time. And I was amazed by how many people didn’t bother to read the rules at all, and just submitted movie plot threats.

But, after reading through the entries, I have chosen a winner. It’s HJohn, for his kidnap-blackmail-terrorist connection:

Though recent shooting sprees in churches, nursing homes, and at family outings appear unrelated, a terrifying link has been discovered. All perpetrators had small children who were abducted by terrorists, and perpetrators received a video of their children with hooded terrorists warning that their children would be beheaded if they do not engage in the suicidal rampage. The terror threat level has been raised to red as profiling, known associations, and criminal history are now useless in detecting who will be the next terrorist sniper or airline hijacker. Anyone who loves their children may be a potential terrorist.

Fairly plausible, and definitely scary. Congratulations, HJohn. E-mail me and I’ll get you your fabulous prizes—as soon as I figure out what they are.

For historical purposes: The First Movie-Plot Threat Contest rules and winner. The Second Movie-Plot Threat Contest rules, semifinalists, and winner. The Third Movie-Plot Theat Contest rules, semifinalists, and winner.

Posted on May 12, 2009 at 6:40 AM • View Comments

Fourth Annual Movie-Plot Threat Contest

Let’s face it, the War on Terror is a tired brand. There just isn’t enough action out there to scare people. If this keeps up, people will forget to be scared. And then both the terrorists and the terror-industrial complex lose. We can’t have that.

We’re going to help revive the fear. There’s plenty to be scared about, if only people would just think about it in the right way. In this Fourth Movie-Plot Threat Contest, the object is to find an existing event somewhere in the industrialized world—Third World events are just too easy—and provide a conspiracy theory to explain how the terrorists were really responsible.

The goal here is to be outlandish but plausible, ridiculous but possible, and—if it were only true—terrifying. (An example from The Onion: Fowl Qaeda.) Entries should be formatted as a news story, and are limited to 150 words (I’m going to check this time) because fear needs to be instilled in a population with short attention spans. Submit your entry, by the end of the month, in comments.

The First Movie-Plot Threat Contest rules and winner. The Second Movie-Plot Threat Contest rules, semifinalists, and winner. The Third Movie-Plot Theat Contest rules, semifinalists, and winner.

EDITED TO ADD: The contest has ended; the winner is here

Posted on April 1, 2009 at 6:37 AM •

More SHA-3 News

NIST has published all 51 first-round candidates in its hash algorithm competition. (Presumably the other submissions—we heard they received 64—were rejected because they weren’t complete.) You can download the submission package from the NIST page. The SHA-3 Zoo is still the best source for up-to-date cryptanalysis information.

Various people have been trying to benchmark the performance of the candidates, but—of course—results depend on what metrics you choose.

And there’s news about Skein’s performance. And two Java implementations. (Does anyone want to do an implementation of Threefish?) In general, the Skein website is the place to go for up-to-date Skein information.

Posted on December 11, 2008 at 1:16 PM • View Comments

Skein and SHA-3 News

There are two bugs in the Skein code. They are subtle and esoteric, but they’re there. We have revised both the reference and optimized code—and provided new test vectors—on the Skein website. A revision of the paper—Version 1.1—has new IVs, new test vectors, and also fixes a few typos in the paper.

Errata: Version 1.1 of the paper, reference, and optimized code corrects an error in which the length of the configuration string was passed in as the size of the internal block (256 bits for Skein-256, 512 for Skein-512, and 1024 for Skein-1024), instead of a constant 256 bits for all three sizes. This error has no cryptographic significance, but affected the test vectors and the initialization values. The revised code also fixes a bug in the MAC mode key processing. This bug does not affect the NIST submission in any way.

NIST has received 64 submissions. (This article interviews one of the submitters, who is fifteen.) Of those, 28 are public and six have been broken. NIST is going through the submissions right now, making sure they are complete and proper. Their goal is to publish the accepted submissions by the end of the month, in advance of the Third Cryptographic Hash Workshop to be held in Belgium right after FSE in February. They expect to quickly make a first cut of algorithms—hopefully to about a dozen—and then give the community about a year of cryptanalysis before making a second cut in 2010.

Lastly, this is a really nice article on Skein.

These submissions make some accommodation to the Core 2 processor. They operate in “little-endian” mode (a quirk of the Intel-like processors that reads some bytes in reverse order). They also allow a large file to be broken into chunks to split the work across multiple processors.

However, virtually all of the contest submissions share the performance problem mentioned above. The logic they use won’t optimally fit within the constraints of a Intel Core 2 processor. Most will perform as bad or worse than the existing SHA-1 algorithm.

One exception to this is Skein, created by several well-known cryptographers and noted pundit Bruce Schneier. It was designed specifically to exploit all three of the Core 2 execution units and to run at a full 64-bits. This gives it roughly four to 10 times the logic density of competing submissions.

This is what I meant by the Matrix quote above. They didn’t bend the spoon; they bent the crypto algorithm. They moved the logic operations around in a way that wouldn’t weaken the crypto, but would strengthen its speed on the Intel Core 2.

In their paper (PDF), the authors of Skein express surprise that a custom silicon ASIC implementation is not any faster than the software implementation. They shouldn’t be surprised. Every time you can redefine a problem to run optimally in software, you will reach the same speeds you get with optimized ASIC hardware. The reason software has a reputation of being slow is because people don’t redefine the original problem.

That’s exactly what we were trying to do.

EDITED TO ADD (11/20): I wrote an essay for Wired.com on the process.

Posted on November 19, 2008 at 6:14 AM • View Comments

TSA News

Item 1: Kip Hawley says that the TSA may reduce size restrictions on liquids. You’ll still have to take them out of your bag, but they can be larger than three ounces. The reasons—so he states—are that technologies are getting better, not that the threat is reduced.

I’m skeptical, of course. But read his post; it’s interesting.

Item 2: Hawley responded to my response to his blog post about an article about me in The Atlantic.

Item 3: The Atlantic is holding a contest, based on Hawley’s comment that the TSA is basically there to catch stupid terrorists:

And so, a contest: How would the Hawley Principle of Federally-Endorsed Mediocrity apply to other government endeavors?

Not the same as my movie-plot threat contest, but fun all the same.

Item 4: What would the TSA make of this?

Posted on October 29, 2008 at 2:27 PM • View Comments

The Skein Hash Function

NIST is holding a competition to replace the SHA family of hash functions, which have been increasingly under attack. (I wrote about an early NIST hash workshop here.)

Skein is our submission (myself and seven others: Niels Ferguson, Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, and Jesse Walker). Here’s the paper:

Executive Summary

Skein is a new family of cryptographic hash functions. Its design combines speed, security, simplicity, and a great deal of flexibility in a modular package that is easy to analyze.

Skein is fast. Skein-512—our primary proposal—hashes data at 6.1 clock cycles per byte on a 64-bit CPU. This means that on a 3.1 GHz x64 Core 2 Duo CPU, Skein hashes data at 500 MBytes/second per core—almost twice as fast as SHA-512 and three times faster than SHA-256. An optional hash-tree mode speeds up parallelizable implementations even more. Skein is fast for short messages, too; Skein-512 hashes short messages in about 1000 clock cycles.

Skein is secure. Its conservative design is based on the Threefish block cipher. Our current best attack on Threefish-512 is on 25 of 72 rounds, for a safety factor of 2.9. For comparison, at a similar stage in the standardization process, the AES encryption algorithm had an attack on 6 of 10 rounds, for a safety factor of only 1.7. Additionally, Skein has a number of provably secure properties, greatly increasing confidence in the algorithm.

Skein is simple. Using only three primitive operations, the Skein compression function can be easily understood and remembered. The rest of the algorithm is a straightforward iteration of this function.

Skein is flexible. Skein is defined for three different internal state sizes—256 bits, 512 bits, and 1024 bits—and any output size. This allows Skein to be a drop-in replacement for the entire SHA family of hash functions. A completely optional and extendable argument system makes Skein an efficient tool to use for a very large number of functions: a PRNG, a stream cipher, a key derivation function, authentication without the overhead of HMAC, and a personalization capability. All these features can be implemented with very low overhead. Together with the Threefish large-block cipher at Skein core, this design provides a full set of symmetric cryptographic primitives suitable for most modern applications.

Skein is efficient on a variety of platforms, both hardware and software. Skein-512 can be implemented in about 200 bytes of state. Small devices, such as 8-bit smart cards, can implement Skein-256 using about 100 bytes of memory. Larger devices can implement the larger versions of Skein to achieve faster speeds.

Skein was designed by a team of highly experienced cryptographic experts from academia and industry, with expertise in cryptography, security analysis, software, chip design, and implementation of real-world cryptographic systems. This breadth of knowledge allowed them to create a balanced design that works well in all environments.

Here’s source code, text vectors, and the like for Skein. Watch the Skein website for any updates—new code, new results, new implementations, the proofs.

NIST’s deadline is Friday. It seems as if everyone—including many amateurs—is working on a hash function, and I predict that NIST will receive at least 80 submissions. (Compare this to the sixteen NIST submissions received for the AES competition in 1998.) I expect people to start posting their submissions over the weekend. (Ron Rivest already presented MD6 at Crypto in August.) Probably the best place to watch for new hash functions is here; I’ll try to keep a listing of the submissions myself.

The selection process will take around four years. I’ve previously called this sort of thing a cryptographic demolition derby—last one left standing wins—but that’s only half true. Certainly all the groups will spend the next couple of years trying to cryptanalyze each other, but in the end there will be a bunch of unbroken algorithms; NIST will select one based on performance and features.

NIST has stated that the goal of this process is not to choose the best standard but to choose a good standard. I think that’s smart of them; in this process, “best” is the enemy of “good.” My advice is this: immediately sort them based on performance and features. Ask the cryptographic community to focus its attention on the top dozen, rather than spread its attention across all 80—although I also expect that most of the amateur submissions will be rejected by NIST for not being “complete and proper.” Otherwise, people will break the easy ones and the better ones will go unanalyzed.

EDITED TO ADD (10/30): Here is a single website for all information, including cryptanalysis, of all the SHA-3 submissions. A spoke to a reporter who told me that, as of yesterday, NIST had received 30 submissions. And three news articles about Skein.

Posted on October 29, 2008 at 6:35 AM • View Comments

Contest: Cory Doctorow's Cipher Wheel Rings

Cory Doctorow wanted a secret decoder wedding ring, and he asked me to help design it. I wanted something more than the standard secret decoder ring, so this is what I asked for: “I want each wheel to be the alphabet, with each letter having either a dot above, a dot below, or no dot at all. The first wheel should have alternating above, none, below. The second wheel should be the repeating sequence of above, above, none, none, below, below. The third wheel should be the repeating sequence of above, above, above, none, none, none, below, below, below.” (I know it sounds confusing, but here’s a chart.)

So that’s what he asked for, and that’s what he got. And now it’s time to create some cryptographic applications for the rings. Cory and I are holding an open contest for the cleverest application.

I don’t think we can invent any encryption algorithms that will survive computer analysis—there’s just not enough entropy in the system—but we can come up with some clever pencil-and-paper ciphers that will serve them well if they’re ever stuck back in time. And there are certainly other cryptographic uses for the rings.

Here’s a way to use the rings as a password mnemonic: First, choose a two-letter key. Align the three wheels according to the key. For example, if the key is “EB” for eBay, align the three wheels AEB. Take the common password “PASSWORD” and encrypt it. For each letter, find it on the top wheel. Count one letter to the left if there is a dot over the letter, and one letter to the right if there is a dot under it. Take that new letter and look at the letter below it (in the middle wheel). Count two letters to the left if there is a dot over it, and two letters to the right if there is a dot under it. Take that new letter (in the middle wheel), and look at the letter below it (in the lower wheel). Count three letters to the left if there is a dot over it, and three letters to the right if there is a dot under it. That’s your encrypted letter. Do that with every letter to get your password.

“PASSWORD” and the key “EB” becomes “NXPPVVOF.”

It’s not very good; can anyone see why? (Ignore for now whether or not publishing this on a blog makes it no longer secure.)

How can I do that better? What else can we do with the rings? Can we incorporate other elements—a deck of playing cards as in Solitaire, different-sized coins to make the system more secure?

Post your contest entries as comments to Cory’s blog post—you can post them here, but they’re not going to count as contest submissions—or send them to cryptocontest@craphound.com. Deadline is October 1st.

Good luck, and have fun with this.

Posted on September 5, 2008 at 12:01 PM • View Comments

1 … 3 4 5 6 7

Sidebar photo of Bruce Schneier by Joe MacInnis.