Entries Tagged "hashes"
Page 3 of 6
Nikon Image Authentication System Cracked
Not a lot of details:
ElcomSoft research shows that image metadata and image data are processed independently with a SHA-1 hash function. There are two 160-bit hash values produced, which are later encrypted with a secret (private) key by using an asymmetric RSA-1024 algorithm to create a digital signature. Two 1024-bit (128-byte) signatures are stored in EXIF MakerNote tag 0×0097 (Color Balance).
During validation, Nikon Image Authentication Software calculates two SHA-1 hashes from the same data, and uses the public key to verify the signature by decrypting stored values and comparing the result with newly calculated hash values.
The ultimate vulnerability is that the private (should-be-secret) cryptographic key is handled inappropriately, and can be extracted from camera. After obtaining the private key, it is possible to generate a digital signature value for any image, thus forging the Image Authentication System.
News article.
Canon’s system is just as bad, by the way.
Fifteen years ago, I co-authored a paper on the problem. The idea was to use a hash chain to better deal with the possibility of a secret-key compromise.
NIST Defines New Versions of SHA-512
NIST has just defined two new versions of SHA-512. They’re SHA-512/224 and SHA-512/256: 224- and 256-bit truncations of SHA-512 with a new IV. They’ve done this because SHA-512 is faster than SHA-256 on 64-bit CPUs, so these new SHA variants will be faster.
This is a good thing, and exactly what we did in the design of Skein. We defined different outputs for the same state size, because it makes sense to decouple the internal workings of the hash function from the output size.
NIST Announces SHA-3 Finalists (Skein is One of Them)
Yesterday, NIST announced the five hash functions to advance to the third (and final) round in the SHA-3 selection process: BLAKE, Grøstl, JH, Keccak, and Skein. Not really a surprise; my predictions—which I did not publish—listed ECHO instead of JH, but correctly identified the other four. (Most of the predictions I saw guessed BLAKE, Grøstl, Keccak, and Skein, but differed on the fifth.)
NIST will publish a report that explains its rationale for selecting the five it did.
Next is the Third SHA-3 Candidate Conference, which will probably be held in March 2012 in Washington, DC, in conjunction with FSE 2012. NIST will then pick a single algorithm to become SHA-3.
More information about Skein and the SHA-3 selection process, including lots of links, is here. Version 1.3 of the Skein paper, which discusses the new constant to defeat the Khovratovich-Nikolié-Rechberger attack, is here (description of the tweak here). And there’s this new analysis of Skein.
And if you ordered a Skein polo shirt in September, they’ve been shipped.
Wanted: Skein Hardware Help
As part of NIST’s SHA-3 selection process, people have been implementing the candidate hash functions on a variety of hardware and software platforms. Our team has implemented Skein in Intel’s 32 nm ASIC process, and got some impressive performance results (presentation and paper). Several other groups have implemented Skein in FPGA and ASIC, and have seen significantly poorer performance. We need help understanding why.
For example, a group led by Brian Baldwin at the Claude Shannon Institute for Discrete Mathematics, Coding and Cryptography implemented all the second-round candidates in FPGA (presentation and paper). Skein performance was terrible, but when they checked their code, they found an error. Their corrected performance comparison (presentation and paper) has Skein performing much better and in the top ten.
We suspect that the adders in all the designs may not be properly optimized, although there may be other performance issues. If we can at least identify (or possibly even fix) the slowdowns in the design, it would be very helpful, both for our understanding and for Skein’s hardware profile. Even if we find that the designs are properly optimized, that would also be good to know.
A group at George Mason University led by Kris Gaj implemented all the second-round candidates in FPGA (presentation, paper, and much longer paper). Skein had the worst performance of any of the implementations. We’re looking for someone who can help us understand the design, and determine if it can be improved.
Another group, led by Stefan Tillich at University of Bristol, implemented all the candidates in 180 nm custom ASIC (presentation and paper). Here, Skein is one of the worst performers. We’re looking for someone who can help us understand what this group did.
Three other groups—one led by Patrick Schaumont of Virginia Tech (presentation and paper), another led by Shin’ichiro Matsuo at National Institute of Information and Communications Technology in Japan (presentation and paper), and a third led by Luca Henzen at ETH Zurich (paper with appendix, and conference version)—implemented the SHA-3 candidates. Again, we need help understanding how their Skein performance numbers are so different from ours.
We’re looking for people with FPGA and ASIC skills to work with the Skein team. We don’t have money to pay anyone; co-authorship on a paper (and a Skein polo shirt) is our primary reward. Please send me e-mail if you’re interested.
More Skein News
Skein is my new hash function. Well, “my” is an overstatement; I’m one of the eight designers. It was submitted to NIST for their SHA-3 competition, and one of the 14 algorithms selected to advance to the second round. Here’s the Skein paper; source code is here. The Skein website is here.
Last week was the Second SHA-3 Candidate Conference. Lots of people presented papers on the candidates: cryptanalysis papers, implementation papers, performance comparisons, etc. There were two cryptanalysis papers on Skein. The first was by Kerry McKay and Poorvi L. Vora (presentation and paper). They tried to extend linear cryptanalysis to groups of bits to attack Threefish (the block cipher inside Skein). It was a nice analysis, but it didn’t get very far at all.
The second was a fantastic piece of cryptanalysis by Dmitry Khovratovich, Ivica Nikolié, and Christian Rechberger. They used a rotational rebound attack (presentation and paper) to mount a “known-key distinguisher attack” on 57 out of 72 Threefish rounds faster than brute force. It’s a new type of attack—some go so far as to call it an “observation”—and the community is still trying to figure out what it means. It only works if the attacker can manipulate both the plaintexts and the keys in a structured way. Against 57-round Threefish, it requires 2503 work—barely better than brute force. And it only distinguishes reduced-round Threefish from a random permutation; it doesn’t actually recover any key bits.
Even with the attack, Threefish has a good security margin. Also, the attack doesn’t affect Skein. But changing one constant in the algorithm’s key schedule makes the attack impossible. NIST has said they’re allowing second-round tweaks, so we’re going to make the change. It won’t affect any performance numbers or obviate any other cryptanalytic results—but the best attack would be 33 out of 72 rounds.
Our update on Skein, which we presented at the conference, is here. All the other papers and presentations are here. (My 2008 essay on SHA-3 is here, and my 2009 update is here.) The second-round algorithms are: BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein. You can find details on all of them, as well as the current state of their cryptanalysis, here. NIST will select approximately five algorithms to go on to the third round by the end of the year.
In other news, we’re once again making Skein polo shirts available to the public. Those of you who attended either of the two SHA-3 conferences might have noticed the stylish black Skein polo shirts worn by the Skein team. Anyone who wants one is welcome to buy it, at cost. Details (with photos) are here. All orders must be received before October 1, and we’ll have all the shirts made in one batch.
New Book: Cryptography Engineering
I have a new book, sort of. Cryptography Engineering is really the second edition of Practical Cryptography. Niels Ferguson and I wrote Practical Cryptography in 2003. Tadayoshi Kohno did most of the update work—and added exercises to make it more suitable as a textbook—and is the third author on Cryptography Engineering. (I didn’t like it that Wiley changed the title; I think it’s too close to Ross Anderson’s excellent Security Engineering.)
Cryptography Engineering is a techie book; it’s for practitioners who are implementing cryptography or for people who want to learn more about the nitty-gritty of how cryptography works and what the implementation pitfalls are. If you’ve already bought Practical Cryptography, there’s no need to upgrade unless you’re actually using it.
EDITED TO ADD (3/23): Signed copies are available. See the bottom of this page for details.
EDITED TO ADD (3/29): In comments, someone asked what’s new in this book.
We revised the introductory materials in Chapter 1 to help readers better understand the broader context for computer security, with some explicit exercises to help readers develop a security mindset. We updated the discussion of AES in Chapter 3; rather than speculating on algebraic attacks, we now talk about the recent successful (theoretical, not practical) attacks against AES. Chapter 4 used to recommended using nonce-based encryption schemes. We now find these schemes problematic, and instead recommend randomized encryption schemes, like CBC mode. We updated the discussion of hash functions in Chapter 5; we discuss new results against MD5 and SHA1, and allude to the new SHA3 candidates (but say it’s too early to start using the SHA3 candidates). In Chapter 6, we no longer talk about UMAC, and instead talk about CMAC and GMAC. We revised Chapters 8 and 15 to talk about some recent implementation issue to be aware of. For example, we now talk about the cold boot attacks and challenges for generating randomness in VMs. In Chapter 19, we discuss online certificate verification.
Skein News
Skein is one of the 14 SHA-3 candidates chosen by NIST to advance to the second round. As part of the process, NIST allowed the algorithm designers to implement small “tweaks” to their algorithms. We’ve tweaked the rotation constants of Skein. This change does not affect Skein’s performance in any way.
The revised Skein paper contains the new rotation constants, as well as information about how we chose them and why we changed them, the results of some new cryptanalysis, plus new IVs and test vectors. Revised source code is here.
The latest information on Skein is always here.
Tweaks were due today, September 15. Now the SHA-3 process moves into the second round. According to NIST’s timeline, they’ll choose a set of final round candidate algorithms in 2010, and then a single hash algorithm in 2012. Between now and then, it’s up to all of us to evaluate the algorithms and let NIST know what we want. Cryptanalysis is important, of course, but so is performance.
Here’s my 2008 essay on SHA-3. The second-round algorithms are: BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein. You can find details on all of them, as well as the current state of their cryptanalysis, here.
In other news, we’re making Skein shirts available to the public. Those of you who attended the First Hash Function Candidate Conference in Leuven, Belgium, earlier this year might have noticed the stylish black Skein polo shirts worn by the Skein team. Anyone who wants one is welcome to buy it, at cost. Details (with photos) are here. All orders must be received before 1 October, and then we’ll have all the shirts made in one batch.
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.
Sidebar photo of Bruce Schneier by Joe MacInnis.