### Thread: Hashing Algorithms

Page 3 of 3 First 123
1. #### MD6 announced

New, replacement for md5 developed by Ron Rivest and annouced at Crypto 2008

Originally Posted by 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. 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.

Apologies again to the enormous number of authors if I have any serious
errors above. And thanks to Ron Rivest for publicizing this hash design
several months before the due date (October 31), potentially giving an
advantage to his competitotrs. He emphasized that his goal is to produce
the best possible outcome for the whole process.

Hal Finney
2. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2004
Posts
82
Rep Power
12
Another thing, when consider using hash algoritms and increasing password storage security, is to not make it "too secure".

Its pointless to store the passwords offsite, if access to the server where the user logon, means you can do everything a logged on user can do.

For example, if you have a file server, everyone uses a account on the file server and a private folder. The folders are not using any encryption. The password is encoded using modified BASE64 to prevent SQL injection attacks. (By using _ and - as the 2 additional characthers, eg A-Z a-z 0-9 and _ and -)

In this case, its unneccesary to hash the passwords. Nobody is going to manage to read off the database. So your passwords are secure this way.

If someone hacks the server completely and roots it, your security is lost, regardless of using hashed password or not. The hacker has access to all private and stored files, can store files and retrieve files, everything a logged on user can do plus a little more. The hacker is not prompted for password, he is root. So why would he want your user's passwords?

A hacker searching for local passwords on the rooted server would be equvalient of trying to find a key to the safe the burgular has already broken open. Its pointless for the hacker to gain access to the user passwords when he has root.
-----

If the files would be encrypted with the user's password as a key, then it would make sense to hash the passwords for verification.

The users are more to like your site if the user can retrieve the original password, rather to set a new, if he forgot it.

Then there is some other cases, where you fear that theres a risk that the user finds the passwords by downloading the user database or something by hacking the database engine (eg SQL injection), you can hash the password, or you can encrypt them with a key stored on the disk inaccessible from the database engine.

What I mean, is that you do not need to store the passwords more secure than then service the passwords unlock. Its pointless, the hacker will go the easiest way, if the passwords are too securely stored, the hacker will instead act on bypassing the authentication completely instead, then the hacker dosent need the passwords.
3. Originally Posted by sebastiannielse
Another thing, when consider using hash algoritms and increasing password storage security, is to not make it "too secure".

Its pointless to store the passwords offsite, if access to the server where the user logon, means you can do everything a logged on user can do.

For example, if you have a file server, everyone uses a account on the file server and a private folder. The folders are not using any encryption. The password is encoded using modified BASE64 to prevent SQL injection attacks. (By using _ and - as the 2 additional characthers, eg A-Z a-z 0-9 and _ and -)
Your writing is a bit unclear. You are correct in that the bad guy will attack the weakest link, so if you have bad security in one place, having great security in another doesn't help much.

But your "example" of using MIME encoding as a hash makes no sense. Its not a hash, its a one-to-one translation. So in this context, I have no idea what you are trying to say with the example.
4. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2004
Posts
82
Rep Power
12
What I did mean with the modified BASE64 encoding, was a way to completely avoid injection attacks, thus ruling out the possibility that the SQL is injected to download the user database.

Then the passwords dosen't need to be hashed.

If you continue reading, you will find out:
"In this case, its unneccesary to hash the passwords. Nobody is going to manage to read off the database. So your passwords are secure this way."
5. Originally Posted by sebastiannielse
What I did mean with the modified BASE64 encoding, was a way to completely avoid injection attacks, thus ruling out the possibility that the SQL is injected to download the user database.

Then the passwords dosen't need to be hashed.
I don't believe that a simple MIME encoding of passwords will completely eliminate SQL injection or any other set of attacks.

And in general, passwords should be hashed with a real one-way hash.

So if you have some other point to make, I'm not sure why you are making it in this thread.
6. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2004
Posts
82
Rep Power
12
The point I want to make, is that its not ALWAYS neccessary to hash the passwords, or come up with secure salts.

The criteria, if the passwords does need to be hashed or not, depends, if someone were to gain access to the stored passwords, also means this person always will gain access to what the passwords protect or not.

If no, then its a good idea to hash the passwords securely. If yes, then its more convient for the users to be able to gain their old passwords back.
Last edited by sebastiannielse; October 18th, 2009 at 07:37 PM.
7. Originally Posted by sebastiannielse
The point I want to make, is that its not ALWAYS neccessary to hash the passwords, or come up with secure salts.
Fine, but that concept does not belong in this thread

Start a new one if you want
Page 3 of 3 First 123