# wmoxam/ey-contest

Calculates hamming distance, etc for EY
C Ruby
Fetching latest commitâ€¦
Cannot retrieve the latest commit at this time.

```1000 word dictionary
12 word phrase
up to 5 characters appended to phrase digits and letters

How many word sets?

1000!
-----
12!(1000-12)!

==

total = (1..12).to_a.inject(1.0) do |t, i|
t * (1000-(12.0-i.to_f)/i.to_f)
end.ceil

== 974997404313888311468767317225111552 sets

times the number of 5 character combinations

10 digits + 26 letters in either case = 62

62*62*62*62*62 == 916132832

== 893227133206731515717579881878483827649675264 phrases

Letter combos of a word
Since case can be changed, this greatly increases 12 word set size

given N
Number of combos == ("1" * N).to_i(2) + 1

1 = 2
2 = 4
3 = 8
4 = 16
5 = 32
6 = 64
etc

so now, rather than 1000 word dictionary we have a 32000 word dictionary (if all words are 5 chars long)
so we have:

total = (1..12).to_a.inject(1.0) do |t, i|
t * (32000-(12.0-i.to_f)/i.to_f)
end.ceil

== 1152012457656667041440530647805828935429644585850109952 sets
and

1055396435332282460355974701957148648722705431188328357837144064 phrases

It takes my naive ruby implementation 6 seconds to compute 1000 phrases
== It would take 33466401424793330173642018707418462985879801851481746 years to compute all of the phrase

3.25 million per seconds
== It would take 10297354284551793899582159602282603995655323646 years to compute all of the phrases

sha1 had a 4503599627370496 attack with no collisions found (http://en.wikipedia.org/wiki/SHA_hash_functions)
In theory brute-force search would require 2**80 (1208925819614629174706176) operations.
The c implementation would take 4305291380393 years to mount that sort of attack (on one cpu)

This implementation:
200000000 iterations per process
4 processes on a EC2 medium instance
average time to complete: 269 seconds
== 2,973,977 comparisons per second, per EC2 medium instance
== 743,494 comparisons per second, per CPU

so 20 cents per 10,706,319,702 comparisons

GPU script:
./gpusha1 -device 0 6cac827bae250971a8b1fb6e2a96676f7a077b60 Cloud Ruby DHH one eight six active record controller data rspec mongrel MySQL postgresSQL tokyo MRI jruby rubinius memcached exception metaprogramming reflection

Prediction: Likely this will end in a tie (if more than one is serious about throwing resources into it). Hamming distance likely in the low 30's - high 20's
```