Re: Cube cryptanalysis?
Steve Bellovin writes: Greg, assorted folks noted, way back when, that Skipjack looked a lot like a stream cipher. Might it be vulnerable? I'm still absorbing Adi's new ideas, and I haven't looked at this in any detail, so anything I say should be taken with an enormous grain of salt. But, off-hand, I'd guess not. I don't see anything that immediately makes me worried about Skipjack, or AES for that matter. In its most basic form, Adi Shamir's cube attack applies when some bit of the output of the stream cipher (or block cipher, etc.) can be written as a polynomial of the key and input such that the degree of the polynomial is not too large. One major innovation is that the attack applies even if the number of terms in the polynomial is enormous -- say, way too many to explicitly write down the polynomial. When the degree is not too large, Adi showed some powerful techniques for recovering the key. Adi pointed out that this might be especially relevant to many LFSR-based stream ciphers. The reason is that many LFSR-based stream cipher use a non-linear filter function of low degree. Often, the key loading process also has relatively low degree. The LFSR itself is linear and hence does not increase the degree. The attack only seems directly relevant to a subset of stream cipher architectures -- for instance, Adi mentioned that he does not know how to apply it to some clock-controlled LFSR-based stream ciphers, such as A5/1 -- but the class of stream ciphers it applies to is an important and common class of stream ciphers. In contrast, I don't expect this to threaten most modern block ciphers. Most block ciphers contain enough rounds, and enough non-algebraic structure in each round, to ensure that the degree of the resulting polynomial will be large, so in those cases the attack does not seem applicable. But of course I could well be missing something, and it's always possible there could be further advances. It's a brilliant piece of research. If you weren't at CRYPTO, you missed an outstanding talk (and this wasn't the only one!). - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Inscrypt 2008 CFP
Forwarded: From: Peng Liu [EMAIL PROTECTED] To: [EMAIL PROTECTED] Cc: Peng Liu [EMAIL PROTECTED], D LIN [EMAIL PROTECTED] Reply-To: Peng Liu [EMAIL PROTECTED] We are sorry if you receive multiple copies! CALL FOR PAPERS 4th International Conference on Information Security and Cryptology Inscrypt 2008 December 14 - 17, 2008, Beijing, China http://www.inscrypt.cn/ The 4th International Conferences on Information Security and Cryptology will be held in Beijing from December 14 to 17, 2008. The conference is co-organized by Chinese Association for Cryptologic Research and The State Key Laboratory of Information Security (SKLOIS) of China. It is an annual conference targeting the top research results in the related area. The formal conference proceedings will be published by Springer Verlag in LNCS series after conference. PAPERS == Authors are invited to submit full papers presenting new research results related to cryptology, information security and their applications. All submissions must describe original research that is not published or currently under review by another conference or journal. Areas of interest include, but are not limited to: Access Control Provable Security Authentication and AuthorizationSecure Multiparty Computation Biometric Security Foundations of Cryptography Distributed System Security Secret Key and Public Key Cryptosystems Database Security Implementation of Cryptosystems Electronic Commerce SecurityHash Functions and MACs Intrusion Detection Block Cipher Modes of Operation Information Hiding and Watermarking Intellectual Property Protection Key Management and Key Recovery Mobile System Security Network SecurityOperating System Security Security Protocols and Their Analysis Risk Evaluation and Security Certification Security Modeling and Architectures Prevention and Detection of Malicious Codes INSTRUCTION FOR AUTHORS === Conference language is English. All submissions must be anonymous, with no author names, affiliations, acknowledgments, or obvious references. It should begin with a title, a short abstract, and a list of key words, and its introduction should summarize the contributions of the paper at a level appropriate for a non-specialist reader. The paper should be intelligible and self-contained within 20 pages including references and appendices and must be submitted electronically. Submissions not meeting these guidelines risk rejection without consideration of their merits. It is highly advised to prepare the submissions in the Springer LNCS format (see http://www.springeronline.com/sgw/cda/frontpage/0,11855,5-164-2-72376-0, 00.html). A detailed description of the electronic submission procedure can be found from a link at http://www.inscrypt.cn/. IMPORTANT DATES === Deadline for Submission: August 27, 2008 Notification of Acceptance:October 25, 2008 Pre-proceedings version deadline: November 10, 2008 Proceedings version deadline: January 15, 2009 CONFERENCE GENERAL CHAIR Dengguo Feng SKLOIS, Institute of Software, CAS, China TECHNICAL PROGRAME COMMITTEE Moti Yung Columbia University, USA (co-Chair) Peng Liu Pennsylvania State University, USA (co-Chair) Dongdai LinInstitute of Software, CAS, China (co-chair) Vladimir S. AnashinMoscow University, Russia Vijay Atluri Rutgers University, USA Marina Blanton University of Notre Dame, USA Zhenfu Cao Shanghai Jiaotong University, China Claude Carlet INRIA,Universite Paris 8, France Jean-Sebastien Coron University of Luxembourg Marc DacierSymantec Research Labs Europe Cunsheng Ding Hong Kong University of Science and Technology, China Jintai DingUniversity of Cincinnati, USA Stefan Dziembowski University of Rome La Sapienza, Italy Jean-Charles Faugere INRIA, France Guang Gong University of Waterloo, Canada Qijun Gu Texas State University, USA Martin HellUniversity of Lund, Sweden Xuxian Jiang NC State University, USA Jiwu Jing Graduate University of CAS, China Brian King Indiana University-Purdue University, Indianapolis, USA Miroslaw KutylowskiWroclaw University of Technology, Poland Chi-Sung Lai National Cheng Kung University, Taiwan DongHoon Lee Korea
Re: Cube cryptanalysis?
David Wagner wrote: It's a brilliant piece of research. If you weren't at CRYPTO, you missed an outstanding talk (and this wasn't the only one!). Yes, the program chair and committee did a great job. Whatsisname? Oh, yeah, David Wagner. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Yes, of course Adi is correct, but I blame you for reading what I wrote and not what I meant... :-) Adi mentioned that the slides and paper will go online around the deadline for Eurocrypt submission; it will all become much clearer than my wounded explanations then. thanks and regards, Greg. (cc:ed back to the crypto list) Matt Ball wrote: Hi Greg, I don't think we've met, but I'm also at the crypto conference, and happened to be sitting next to Adi and showed him this e-mail thread. He mentioned that the following text was a little misleading: On Wed, Aug 20, 2008 at 2:40 PM, Greg Rose [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: Basically the method focuses on terms of the polynomial in which only one secret bit of the key appears, and many of the non-secret bits. Using chosen (or lucky) plaintexts, vary all but one of the non-secret bits, and sum the output bits (mod 2, that is, XOR). Fix the other non-secret bit to 1. The attack does not vary only one of the non-secret bits, but rather some subset of the non-secret bits. The other non-secret bits need to stay constant. This could happen in counter mode, for example, when the nonce is fixed and only the counter field varies. I'll let Adi double-check this statement for correctness... :) Cheers, -Matt Previous message: James Muir wrote: Greg Rose wrote: Basically, any calculation with inputs and outputs can be represented as an (insanely complicated and probably intractable) set of binary multivariate polynomials. So long as the degree of the polynomials is not too large, the method allows most of the nonlinear terms to be cancelled out, even though the attacker can't possibly handle them. Then you solve a tractable system of linear equations to recover key (or state) bits. I would like to know how Dinur and Shamir's work differs from Courtois' previous work on Algebraic cryptanalysis of block ciphers. It is a refinement of Courtois' technique? Greg, do you, or someone else have some insight on this? I spent about an hour trying to come up with a short but legible explanation of the technique, and failed. Sorry about that. I can visualize it, and could probably reproduce Adi's drawings on a whiteboard, but not with typing. The following is as close as I could come. Basically the method focuses on terms of the polynomial in which only one secret bit of the key appears, and many of the non-secret bits. Using chosen (or lucky) plaintexts, vary all but one of the non-secret bits, and sum the output bits (mod 2, that is, XOR). Fix the other non-secret bit to 1. Now all the terms that involve less than the full complement of non-secret bits will appear an even number of times in the sum, and because it is mod 2, they will all cancel out! The only terms that will be left are the ones with one secret bit, and all ones for the non-secret bits... but that is linear in the secret bit! So what you are left with is a simple, linear, polynomial relating unknown (key) bits. Gather enough such equations, just a few more than the number of key bits will do, and solve the linear system in trivial time. Note that you had to have 2^(d-2) chosen plaintexts to sum over for each of the equations... that's where the complexity comes from. The attack is called Cube because in the case where d=4, each time you sum over all of the varying known bits, it can be visualized as the face of a cube, the corners of which are the possibilities for the 3 known inputs. Hope that helps. Note that the formula I typed from memory for the complexity was wrong... it's O(n * 2^(d-2)), if the above is correct. For anything more than this, you'll have to wait for the paper. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] -- Thanks! Matt Ball, IEEE P1619.x SISWG Chair M.V. Ball Technical Consulting, Inc. Phone: 303-469-2469, Cell: 303-717-2717 http://www.mvballtech.com http://www.linkedin.com/in/matthewvball - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
The MD6 hash function (rough notes)
Ron Rivest presented his (along with a dozen other people's) new hash, MD6, yesterday at Crypto. I am not a hash guru although I've implemented SHA and its ilk many times, so I can't guarantee all my notes are correct. I will compare it somewhat with SHA as that is what I know. SHA-1 is a Merkle Damgard hash, meaning that it runs a compression function that takes as input the chaining value from the previous compression function block, along with the next block of input, and compresses that, creating the next chaining value for the next block. MD6 is a tree hash, so the leaf nodes run the compression function which takes successive blocks of input and compress it down to a chaining value. These chaining values are then fed up to a parent node, which uses the same compression function to produce its own chaining value, and so on up to the root node. I think the tree branching factor was 4 - each node has 4 children. There is also an alternative serial mode for use by memory limited devices, but I don't recall any details on that. A unique feature of MD6 is that the input to the compression function is very large - 512 bytes. SHA-1 takes 64 bytes. MD6 is oriented around 64 bit words, so this input is considered to be 64 words. The MD6 chaining variable is 1024 bits or 16 words - compare to the hash width for the SHA family ciphers: 160 for SHA-1, 256 or 512 for SHA-256 and SHA-512. Per NIST's spec, the largest hash output for SHA-3 is 512 bits, so MD6 intentionally uses a double width chaining variable internally, and truncates it for output. The compression function of MD6 is particularly unusual, combining simple steps with a large number of rounds. In SHA-1 the first thing you do is to take the 16 32-bit input words and expand them into an 80-word key array, each word in the expanded input being a function of certain previous words. Then you run an unbalanced Feistel using the expanded inputs. MD6 starts off with something similar, using a somewhat more complex expansion algorithm, and going on far longer. To my surprise, this is the whole compression function! The last 16 words of this process are the output chaining value. There is no Feistel network or any other mechanism. In more detail, the 64 (64-bit) input words are prefixed by two sets of about a dozen words - sorry, I don't remember exactly how big these were. One set is a constant value, and the other set includes a variety of environmental information about the circumstances of this instance of the compression function. This includes global information like how wide the hash is that will finally be derived by truncating the final chaining value; the location of this compression function block in the hash tree, including in particular whether we are the last (root) node; and other such data. One notable value here is an optional per-hash key, for creating a keyed hash, of up to 8 words (512 bits). These prepended blocks bring the full input size up to about 87 or 89 words - again I apologize, I am working strictly from memory here. Now this input begins to be extended. Each additional word is a function of about 5 of the previous 89 words. They did a search to choose the best 5 offsets in order to maximize diffusion. The combining function is quite simple though, composed solely of xors, ands, one right shift and one left shift. Rivest mentioned that this made it reversible - a desirable feature as it guarantees that no entropy is lost. At first I was unclear how doing x = x ^ (x 5) for example is reversible, for example, but then I got it. The shift amounts change each step, again optimized by a computer search for good mixing. But the really important point here is that there are a huge number of such steps. The function is expressed in rounds of 16 steps each. MD6-256 uses 104 rounds; MD6-512 uses 168. Multiply times 16 and you are performing this extend step on the order of 2000 times. Again, the last 16 words are the output of the compression function. Rivest gave a lot of performance information. Because of the tree structure, the function is highly parallellizable, and scales almost linearly with the number of CPU cores available. With 1 core, it is not super fast: MD6-256 on a 64-bit CPU is 77 MB/sec; MD6-512 is 49 MB/sec. For comparison, SHA-512 is 202 MB/sec on the same setup. They need about 3 cores to match the speed of SHA-512. He also presented a number of cryptanalytic results. There is provable security against differential cryptanalysis, by virtue of the large number of rounds; also security against side channels. A SAT solver and another technique could only do something with about 11 rounds, versus the 100+ rounds in the function. The tree structure is also shown to preserve strong properties of the compression function. Overall it seemed very impressive. The distinctive features are the tree structure, very wide input blocks, and the enormous number of rounds. The cryptanalysis results were favorable.
