RE: The MD6 hash function (rough notes)
See his presentation slides here http://people.csail.mit.edu/rivest/Rivest-TheMD6HashFunction.ppt. M -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Hal Finney Sent: 21. august 2008 19:26 To: cryptography@metzdowd.com Subject: 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
Re: The MD6 hash function (rough notes)
On Thu, 2008-08-21 at 10:26 -0700, Hal Finney wrote: Ron Rivest presented his (along with a dozen other people's) new hash, MD6, yesterday at Crypto. ---8---(snip)---8--- 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. However Adi Shamir stood up and expressed concern that his new Cube attack might apply. Rivest seemed confident that the degree of MD6 would be several thousand, which should be safe from Shamir's attack, but time will tell. I came across this paper today while searching for more information: http://groups.csail.mit.edu/cis/theses/crutchfield-masters-thesis.pdf It's titled 'Security Proofs for the MD6 Hash Function Mode of Operation' by Christopher Yale Crutchfield (certified by Ronald L. Rivest). I thought it might be of interest to the followers of this thread. -- Dustin D. Trammell Security Researcher BreakingPoint Systems, Inc. signature.asc Description: This is a digitally signed message part
Re: The MD6 hash function (rough notes)
On Thu, 2008-08-21 at 10:26 -0700, Hal Finney wrote: Ron Rivest presented his (along with a dozen other people's) new hash, MD6, yesterday at Crypto. The slides for this presentation are available from Ronald's website: http://people.csail.mit.edu/rivest/Rivest-TheMD6HashFunction.ppt -- Dustin D. Trammell Security Researcher BreakingPoint Systems, Inc. signature.asc Description: This is a digitally signed message part
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.
