The MD6 hash function (rough notes)

["Hal Finney"]

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. How

Re: "Cube" cryptanalysis?

[Greg Rose]

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] 
> 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] 




--
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]

Re: "Cube" cryptanalysis?

[Greg Rose]

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]

Inscrypt 2008 CFP

[Perry E. Metzger]

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  

Re: "Cube" cryptanalysis?

[David Wagner]

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]