Simple (to code) secure hash function

Question

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.

Answer 1

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. :)

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.