Custom hash function as Bash script

Question

I'm looking for a (possibly cryptographic strong) hash function in Bash with the following properties:

• The input is only a string with 4 lower-case characters: aaaa to zzzz
• The output should be a decimal number (with leading zeros) in range: 0000 to 9999
• Low number of collisions and hash values distributed as evenly as possible
• Surjective (each output should appear)
• Chaos (should have a good diffusion of hash values)
• Optional: Confusing (it should not be possible to draw any conclusions about the input value from the hash value)

I have not yet found a (simple) algorithm that would fulfil these requirements.

This is my approach. How would you rate it?

#!/bin/bash
# ord() - converts ASCII character to its decimal value
ord() {
 printf '%d' "'1ドル"
}
my_hash_4 () {
 s=1ドル
 while (( ${#s} < 4 ));
 do
 s="${s}a"
 done
 hash=0
 multiplier=1
 for i in $(seq 0 3);
 do
 j=$(ord "${s:$i:1}")
 hash=$((hash+(multiplier*(j-97)*961)))
 multiplier=$((multiplier*26))
 done
 # (int) (10_000 / Math.pow(26, 4) * hash) % 10_000
 hash=$((((10000000*hash)/456976000)%10000))
 printf '%04d\n' "$hash"
}
my_hash_4 "1ドル"

Example output:

bash my_hash.sh aaaa
0000
bash my_hash.sh baaa
0021
bash my_hash.sh abaa
0546
bash my_hash.sh bbaa
0567
bash my_hash.sh zzzz
9978
bash my_hash.sh hallo
2292

• Dair: I'm not certain how you can make a cryptographic hash with such a small range of values. There are a total of of 26*26*26*26 = 456976 inputs and 10 * 10 * 10 * 10 = 10000 outputs. Each of these can easily be brute forced.
• Fe2O3: In case you missed that lecture/chapter: Modulo is the primary magic ingredient that makes reversal of a well designed encryption impractical. In practical terms, What you have here is called a "one way function", with no possibility of extracting exactly what the original information was. (1+4=5 but 2+3=5, too... Given just 5, there's no way to reverse thing to determine the two input values again.)
• Fe2O3: Question: My 'scripting' is on shaky ground, but... Code wants to accommodate short strings (less than length 4) by padding on the end. Code then deals with ONLY the leftmost 4 characters. Q: Why be meticulous about looping to append 1 character at a time to reach length 4? Easier to ALWAYS append 3 characters ("aaa") to input (sometimes making length 7), then slice off leftmost 4 characters for processing. Step back to see the whole forest. That first while() evaporates away.
• pacmaninbw: The question is valid, and you learned something. I won't vote to keep it open because that would override any community votes and force it to stay open, but I think that it should stay open.
• pacmaninbw: Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered.

Answer 1

I see no evidence that this is a cryptographically-strong hash function. You should include a comment that links to a reputable reference for the algorithm you are implementing, so that reviewers can compare your code against the specification and confirm that it matches. Otherwise, we have to assume that no cryptanalysis has been performed at all.

I would recommend using an existing implementation if possible, and reduce its output to your desired range (0-9999). Then only the last part needs to be verified as the operation of your script and all the specialist crypto work is done by those with the expertise.

That said, with such a small input space (264 values), "cryptographically strong" is probably meaningless - even on quite ordinary consumer hardware, it's not hard to generate all possible hashes for lookup or comparison.

---

There seems to be a baked-in assumption that input is ASCII. Yet that is not a given on all platforms where Bash can run.

---

Loops like this are wasteful:

 s=1ドル
 while (( ${#s} < 4 ));
 do
 s="${s}a"
 done

Simpler just to append 4 chars (削除) then crop (削除ここまで):

s=${1}aaaa

Although we could then crop s down to 4 characters (s=${s:0:4}), there's no need because the rest of the script only indexes the first 4.

---

Invoking seq to generate 0 1 2 3 seems wasteful. Bash brace-expansion {0..3} is more efficient.

• Dair: I don't believe even using an existing hash function and concatenating it will make the hash function any more secure. There are simply too few values for this to ever be secure.
• Toby Speight: @Dair, you're absolutely right. One can make a tiny rainbow-table for this.

Answer 2

How would you rate it?

Obscure.

This does not impress me as a supportable codebase.

 hash=$((hash+(multiplier*(j-97)*961)))
 ...
 hash=$((((10_000_000*hash) / 456_976_000) % 10_000))

There's a lot of magic constants in the OP code. I imagine there might be some paper in the open literature that this code is based on. Cite your reference. What .PDF or other work does this source code rely upon?

That 312 (961) left shift does not seem well motivated. Including unit tests which demonstrate how bash arithmetic behaves during deliberate overflow would be useful. One day bash might change such behavior, and you'll want to know how to diagnose it.

The constant 45.6976 seems to have come from nowhere.

(And no, I didn't downvote. I did say the code seemed harder to maintain than necessary, and explained why.)

---

hash = ... % 10_000))

The modulo makes it clear that we shall obey the 4-digit contract. It would be easier to reason about the loop if a modulo happened within it. From the Review Context my understanding is that we expect a "long" input string to deliberately overflow, producing mod 264 results on each iteration. Coding an explicit modulo call would make Author's Intent more transparent, and reduce coupling between this high level source and low level details like bash version or native processor word width.

• Tobias Grothe: "I imagine there might be some paper in the open literature that this code is based on. Cite your reference." I thought about the constants myself. Thanks for downvoting my question.
• pacmaninbw: @TobiasGrothe Even I as a moderator can't see who down votes questions or answers. You can't assume an answer that provides valid observations that are critical of the code means that the user that provided the answer down voted the question. Most of the experienced users that answer a question upvote the question, at least I do. I down vote questions that are not worthy of answers.
• Tobias Grothe: @J_H Perhaps you mean the FNV-1a hash function. And 26^4 (number of possible input values) is 456976, that's in the comment one line up.
• J_H: Sorry, I didn't read the comment one line up. It looked like "commented out code" rather than advice to a human. Typically we seek to delete such lines prior to PR review or merging to main. Its format differs enough from the code that actually does run that I didn't immediately view them as identical. Assigning \26ドル^4\$ to a symbol would be a good first step in assisting some poor maintenance engineer a year down the road who wants to understand what's happening and its motivation. It's unclear how FNV-1a is relevant to OP, absent XOR or a FNV prime. Do I understand the code? No, not well.

Answer 3

Validate input

The script expects the input is a string with 4 lower-case characters: aaaa to zzzz.

It would be good to enforce this in the script:

if ! [[ 1ドル =~ ^[a-z]{4}$ ]]; then
 echo >&2 "Input must be a 4-digit string in the range aaaa..zzzz; got: 1ドル"
 exit 1
fi

Simplify using ((...))

Instead of x=$((x+...)) you can write simpler as ((x += ...)).

Use more spaces in arithmetic expressions for readability

In arithmetic expressions it's possible to use spaces similar to as in C.

Instead of:

hash=$((hash+(multiplier*(j-97)*961)))
multiplier=$((multiplier*26))
hash=$((((10000000*hash)/456976000)%10000))

Combined with the previous point about ((...)) and using more spaces, this is easier to read:

((hash += multiplier * (j - 97) * 961))
((multiplier *= 26))
((hash = ((10000000 * hash) / 456976000) % 10000))

Answer 4

Bash is a shell. A shell is a tool to manipulate (create/destroy) files and processes and sequence calls to other tools. It is not a tool to manipulate text, including performing math operations. The people who invented shell also invented awk for shells to call when they need to manipulate text. Here's your shell script with the text manipulation part rewritten in awk, using GNU awk for its ordchr library:

$ cat my_hash2.sh
#!/usr/bin/env bash
my_hash_4() {
 awk -l 'ordchr' -v val="1ドル" '
 BEGIN {
 s = sprintf("%4s", val)
 gsub(/ /, "a", s)
 hash = 0
 multiplier = 1
 for ( i=1; i<=4; i++ ) {
 j = ord( substr(s,i,1) )
 hash += ( multiplier * (j-97) * 961 )
 multiplier *= 26
 }
 # (int) (10_000 / Math.pow(26, 4) * hash) % 10_000
 hash = ( (10000000 * hash) / 456976000 ) % 10000
 printf "%04d\n", hash
 }
 '
}
my_hash_4 "1ドル"

$ for i in aaaa baaa abaaa bbaaa; do ./my_hash2.sh "$i"; done
0000
0021
0546
0567

You can write it a bit more briefly and clearly than a shell script (e.g. by including white space between values/variables) and if you only need to calculate 1 hash at a time the above would run about twice as fast as your original shell script but if you wanted to calculate multiple values in one execution then it'd run orders of magnitude faster, after being tweaked to handle multiple input strings, e.g.:

$ cat ./my_hash2.sh
#!/usr/bin/env bash
my_hash_4() {
 awk -l 'ordchr' -v val="1ドル" '
 {
 s = sprintf("%4s", 1ドル)
 gsub(/ /, "a", s)
 hash = 0
 multiplier = 1
 for ( i=1; i<=4; i++ ) {
 j = ord( substr(s,i,1) )
 hash += ( multiplier * (j-97) * 961 )
 multiplier *= 26
 }
 # (int) (10_000 / Math.pow(26, 4) * hash) % 10_000
 hash = ( (10000000 * hash) / 456976000 ) % 10000
 printf "%s\t%04d\n", 1,ドル hash
 }
 ' < <(printf '%s\n' "$@")
}
my_hash_4 "$@"

$ ./my_hash2.sh aaaa baaa abaaa bbaaa
aaaa 0000
baaa 0021
abaaa 0546
bbaaa 0567

You should discard your shell script and use the above as a starting point for whatever it is you need to do.

If you don't have GNU awk then remove -l 'ordchr' and add this function to the bottom of the awk script, before the last ', and then it'll work in any awk:

 function ord(char, num) {
 if ( !(char in _ord) ) {
 for ( num=0; num<=255; num++ ) {
 _ord[sprintf("%c", num)] = num
 }
 }
 return _ord[char]
 }

Of course you could tweak that loop to go from -97 to 158 and then you wouldn't need to do j-97 in the loop on the input chars.

• Fe2O3: Tiny: s = sprintf("%saaaa", 1ドル) maybe? As noted in my comment, and another answer, following code only interested in leftmost 4 characters, regardless of length of s. Length doesn't strictly need to equal 4.
• Ed Morton: @Fe2O3 I was deliberately showing the realistic awk equivalent of the OPs original shell syntax so it was most obvious how to do the same in awk as they were doing in shell. There are other possible enhancements too.

Answer 5

Based on the previous reviews of J_H and Toby Speight (thanks for that), I now have this version I want to share with you:

#!/bin/bash
my_hash () {
 s=${1}aaaa # ensure that there are at least 4 chars
 a=$(printf '%d' "'a") # ordinal of 'a'
 hash=0
 multiplier=1
 for i in {0..3};
 do
 j=$(printf '%d' "'${s:$i:1}") # ordinal of ith char
 hash=$((hash+(multiplier*(j-a)*961)))
 multiplier=$((multiplier*26))
 done
 hash=$((((10000*hash)/456976)%10000))
 printf '%04d\n' "$hash"
}
my_hash "1ドル"

I think it is more readable and performs better and has less magic constants.

The thing I'm still not happy with is the constant 961 (31*31).

In my view, this means that "similar" or "neighboring" input values are not distributed well enough, so that there is not enough chaos or diffusion. But this would have to be analyzed mathematically.

• Ed Morton: Letting printf populate a itself with printf -v a '%d' "'a" would be more efficient than spawning a subshell with a=$(printf '%d' "'a") and ditto for j=.... But you shouldn't use shell for this anyway.