13

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.

Improve this question
5
  • 3
    Are you just doing this as a learning exercise because frankly I wouldn't trust anything besides the commonly known algorithms. Commented Aug 2, 2009 at 22:59
  • 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". Commented Aug 3, 2009 at 11:24
  • 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? Commented Aug 3, 2009 at 12:55
  • 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. Commented Aug 3, 2009 at 14:47
  • Does scheme really not have an implementation of sha1? Commented Aug 3, 2009 at 20:50

5 Answers 5

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This seems to be what I've been searching for. I've given the paper a skim and accepted your answer. Thank you.
4

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.

Improve this answer

Comments

2

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.

Improve this answer

1 Comment

Thank you. This looks like an interesting possibility.
2

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)))
Improve this answer

6 Comments

I actually considered suggesting that one, but decided against it. Another disadvantage is that the output is fairly large: 128 bytes if you use a 1024-bit modulus. Also: remember that you must split the input into blocks and chain the results (or just fail if the input is larger than the modulus).
Also: what you have implemented is neither RSA nor Diffie-Hellman. Actually, this is rather trivially breakable. Finding a given (a^p mod q), p and q is easy. The discrete logarithm problem is finding a given (p^a mod q), p and q.
Thank you Rasmus. You have been helpful in this thread. In the same section of "Applied Cryptography" explaining the use of RSA, this method is mentioned. I don't have the book with me at the moment, but I am fairly certain of that. I will double check when I get home. I see how this is not exactly the discrete logarithm problem. But in RSA we still have message^e mod n, where n is (p-1)(q-1) for some primes p q, and e is relatively prime to n. This being trivially breakable would make it seem that RSA is as well. Can you point me in the direction of the algorithm that breaks this?
In RSA the modulus is not a prime, which means that we can't apply Fermats Little Theorem: a^(q-1)=a (mod q). To find a from a^p mod q, first use the Chinese Remainder Theorem to find x and y so that xp+y(q-1)=1. Then (a^p)^x = a^px = a^(1-y(q-1)) = a*(a^(q-1)^-y) = a (mod q).
You are welcome. Btw. Fermats Little Theorem says that a^(q-1)=1 (mod q), not what I wrote above.
|
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. :)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.