.

hashing for dollars

Existing string munging on RX

Autokey

• Used for CRIDs
• Traditional key-based encryption
• Jumbles text, retains symbol form and length
• Very fast
• Decryptable
• Not particularly secure

Autokey

• Input: all our words from loose using have lost their edge.
• Key: secret
• Output: kbu cjd hprjy qmud ilujd xpxkq xxsw hvng zgksj nqwa.

Autokey

• Input: CRID EXAMPLE
• Key: secret
• Output: kbu cjd hprjy qmud ilujd xpxkq xxsw hvng zgksj nqwa.

MD5

• Readily available
• Non-decryptable
• Very secure
• Slow

MD5

• Input: EXAMPLE HERE
• Output: a68bf07db30dffa768179ecd86ab7adc

PubID/SiteID

• Get a bunch of them
• All different formats, lengths
• Coming from different places
• May include ones that a partner has seen already

First try: Autokey

Business value

• Uniform format
• Easily understood
• Judge content as coming from RX

Second try: MD5

Third try: Siphash

Siphash Performance

Google's HighwayHash

• Faster (0.913 ms)
• Cryptographic

Cryptographically Secure Hashes

• MD5
• SHA

Necessary for RX

• Indexes our list
• Are mostly unique
• Fast
• Short

Google's FarmHash

• Based on CityHash
• Based on MurmurHash
• Not cryptographically secure
• VERY fast

Farmhash Performance

Farmhash 32 bit Performance

Farmhash 32 bit output

Collisions

Collisions

Collisions

Figuring out bitsize

• Run on 204,663 inputs

Statistical analysis

• Treat hashes like random pickers
• What's the chance you're going to pick the same one?

Statistical analysis

• Treat hashes like random pickers
• What's the chance you're going to pick the same one?
• Start with the number of ways you can pick all of them:

\[{m \choose 2}\]

Choosing

\[{2 \choose 2} = 1\] \[{3 \choose 2} = 3\] \[{4 \choose 2} = 6\] \[{5 \choose 2} = 10\] \[{100 \choose 2} = 4950\]

Chance of the hash algorithm picking one way

\[\frac{1}{2^{b}}\]

Chance of the hash algorithm picking one way

\[\frac{1}{2^{b}}\]

\[\frac{1}{2^{32}} = 2.3 \times 10^{-10}\]

\[\frac{1}{2^{64}} = 5.4 \times 10^{-20}\]

Combining it all

\[{m \choose 2} \cdot \frac{1}{2^{b}}\]

Combining it all

\[{204663 \choose 2} \cdot \frac{1}{2^{b}}\]

Master Equation

\[{m \choose 2} \cdot \frac{1}{2^{b}} = 1\]

Useful form 1

You know how many inputs (m). You how know many bits (b). How many collisions (c) should I get?

\[c = {m \choose 2} \cdot \frac{1}{2^{b}}\]

Useful form 2

You know how many inputs (m). You want the smallest number of bits (b) such that collisions should be rare.

\[b = \log_2(m^2 -m) - 1\]

Useful form 3

You know how many bits (b). You want to know the number of inputs (m) before you are likely to get collisions.

\[m = \frac{\big(\sqrt{2^{b+3} + 1} + 1\big)}{2}\]