Simple (to code) secure hash function

11
votes

I need a secure (cryptographic) hash function with the following properties:

  1. Can be coded in as few lines as possible (in R5RS Scheme). Hopefully under 50.
  2. Memory and CPU performance within reason for password-length data. (e.g. it does not have to be super efficient or create hashes for millions of bytes of data)

Most secure hash functions I can find are designed with speed/memory efficiency in mind and are complex to code as a result.

The current candidate is Mash-1 (or Mash-2): Handbook of applied cryptography. Google Books

Thanks.

Edit: Thank you all for your answers so far. Please forgive me if the following comes off as rude, I just want to be clear. Please trust me that I have done my homework and considered the "standard" options. I know the easiest thing to do is use one of those, but that's not what I'm looking for.

The single question I am trying to answer is: What cryptographically secure hash algorithm can be implemented in the smallest amount of "readable" code?

I have already posted the best candidate I could find. Any suggestions about something simpler, or commentary about Mash-1/2 would be most helpful.

5
hashcryptographyscheme
Are you just doing this as a learning exercise because frankly I wouldn't trust anything besides the commonly known algorithms. - Spencer Ruport
The problem you're having is that no-one is willing to put their hand on their heart and say "X is secure" when X is a little-studied crypto primitive. This is because "secure" generally means "hasn't been broken yet, despite significant attention". - caf
You really need to clarify your security requirements: if you do not choose one of the most common hash algorithms you are performing a security trade-off, since it is much more likely that is has an unknown weakness. "Secure" is not a binary value. You are not willing to use SHA-512 because it is too complex to implement. So help us discover how much security you are willing to trade off for easier implementation. Are you simply looking for the most secure hash that can be implemented in 50 lines of Scheme? Even if that algorithm is likely to be broken within, say, 10 years? - Rasmus Faber
I'm putting together a web stack that is to be used as a pedogogical tool. I don't want to omit anything necessary (password hashing) but I want to ensure everything is as simple as possible so that anyone studying it has a hope of fully understanding every component. Some cryptographic algorithms (RSA, Feistel cyphers) have a certain simple elegance to them, and I was hoping for something similar in a secure hash. I have to work with what is available and the intention of this thread is to discover what my options are. - Mark Bolusmjak
Does scheme really not have an implementation of sha1? - Nick Johnson

5 Answers

4
votes

If you want a secure hash function for the purpose of actually securing something (say, as part of an encryption algorithm), you would be best served using a library implmentation of SHA-512 (or perhaps RIPEMD-160 or a few others).

If you want it for hashing passwords, I would say a hash function like MASH would fit the bill of being resistant to brute force (when used with a salt) and rainbow tables. I still wouldn't use it unless I had stringent requirements forbidding or precluding me from using a library implmentation - but it sounds like you may have just those.

If you want it for something less secure, say file integrity checking, almost anything would do unless you're explicitly concerned about malicious users generating collisions. In that case, depending on the value of what you're protecting, I would range from something simple like MASH to something more resistant like SHA-512 or RIPEMD-320.

3
votes

If you prefer simplicity and pedagogical value over efficiency then the VSH hash function might be an option. It comes with strong arguments that VSH is a collision resistant hash function, though this function lacks some other properties (e.g. pseudorandomness) that other hash functions have.

2
votes

For your requirements, I would check out the SHA-3 finalists.

If you have the AES primitive implemented for encryption, you can reuse that to implement several of the functions relatively simply.

Otherwise, I think I would go with Daniel Bernstein's Cubehash. That one looks to have some of that "simple elegance" that you were looking for.

2
votes

According to section 18.12 of Bruce Schneier's "Applied Cryptography": "It is possible to use a public-key encryption algorithm in a block chaining mode as a one-way hash function."

RSA (with the private key being discarded) is listed as an example. Security is as strong as RSA.

RSA encryption step is fairly simple to implement. Especially in a language which has arbitrary sized integers.

The 2 caveats being: 1. far slower than most (all) other secure hash functions. Which is fine for me. 2. If you hard coded your public keys into the code, the world would have to trust that you discarded your private key data. Or create their own public private keys.

I will post code as soon as I have a working example.

EDIT: Here it is. 30 lines. Simple. Secure. EDIT 2: What I actually included is a variant, and may not work. See comments below this post and watch for updates.

; compute a^d mod n
(define powmod
  (lambda (a d n)
    (cond 
      ((= 0 d) 1)
      ((= 1 d) (modulo a n))
      ((= 0 (modulo d 2)) (modulo (expt (powmod a (/ d 2) n) 2) n))
      (else
        (modulo (* (powmod a 1 n) (powmod a (- d 1) n)) n)))))

(define foldr
  (lambda (func end lst)
    (if (null? lst)
      end
      (func (car lst) (foldr func end (cdr lst))))))

; something to turn a string into a number
(define any-string->number
  (lambda (s)
    (foldr
      (lambda (a b) (+ a (* 256 b)))
      0
      (map char->integer (string->list s)))))

; some big primes
(define p 325981479175658910158495167696993467513669112200235950741366213684181287869366665231)
(define q 930416184994449450269535709442344346507738432154879695027334802205487824589832585453)

; hash turns a string into a number
; see discrete logarithms. the inverse of this is *hard* to compute
; http://en.wikipedia.org/wiki/Discrete_logarithm
(define hash
  (lambda (s)
    (powmod (any-string->number s) p q)))
1
votes

Check out the TrueCrypt source. They implement several strong hash functions. Just the standard warning, it is unwise to modify an existing implementation or worse yet, use your own. It will almost certainly inject weakness. I realize you're not doing that here, but just a disclaimer. :)