Naive Ractor solution to RubyConf 2020 Raffle

README.md

Raffle Ractor

RubyConf 2020 held a puzzle-raffle in which the puzzle required using brute force to figure out the cleartext which produced a given hash.

Problem Description

If you process payments with Braintree you’ve likely seen a unique id that looks something like a1b2c3d4. This id goes by different names at different places but is often a way for a company to create a massive numbering system. Assuming an alphabet of only lower case letters and digits, the system above could be used for (26 + 10) ^ 8 = 2,821,109,907,456 combinations. That is an enormous number! Some places, including Braintree, also choose to encode some information in these ids. Without going too much into the Mathematics of hashing and encoding algorithms we can say that it’s possible to take some information, let’s say an email or url, add some other information, say a 5 character raffle number 😉, and encode that information into a fixed length String. If you know the unique id and you have the fixed length encoded String, you can reverse engineer, by brute force, the raffle number that was concatenated to the id. That’s what we’ll be doing today! If you’re interested, DM me a link to your rubyconf crowd cast profile* or some unique identifier (email, pgp key, you name it), this will act as your id. I’ll respond with a String/digest hashed from your profile and your raffle number. Your job is to reverse engineer the digest to determine your raffle number. If you correctly calculate your raffle number, you will be entered into a raffle to win 3 new Raspberry Pi 400 units: I have provided a sample.rb file to get you started. N.B. The sample file uses SHA256 but that’s not necessarily the digest algorithm we have used.

Approach

Not going to lie, I read the hints and made an assumption about the hashing algorithm. From there, I used nested loops to generate every possible raffle entry.

I then tried iterating over them, but that was slow (never finished), so I thought it would be a good opportunity to try to learn about Ractors and parallelize it.

This is the probably horrible but functional solution I produced. I believe it is actually doing the hashing in parallel (not just concurrently), but I may be wrong. It's literally my first time using Ractors 😅

Note that it keeps checking even after finding a solution, because I haven't yet figured out how to pass around a stop message and check for it without blocking if the message queue is empty.

hints.md

Hint 1

The problem boils down to generating the entire set of 5 character permutations from our alphabet and testing those using the generate hash method.

Hint 2

We are using one of the follow hashing algorithms

Digest.constants
# => [:SHA2, :MD5, :SHA256, :SHA384, :SHA512]

I'm not very good at encryption so I accidentally ended up using the weakest hashing algorithm.

Digest::SHA2.base64digest("abc")
# => "ungWv48Bz+pBQUDeXa4iI7ADYaOWF3qctBD/YfIAFa0="
Digest::MD5.base64digest("abc")
# => "kAFQmDzST7DWlj99KOF/cg=="
Digest::SHA256.base64digest("abc")
# => "ungWv48Bz+pBQUDeXa4iI7ADYaOWF3qctBD/YfIAFa0="
Digest::SHA384.base64digest("abc")
# => "ywB1P0WjXou1oD1pmsZQBycsMqsO3tFjGotgWkP/W+2AhgcroefMI1i67KE0yCWn"
Digest::SHA512.base64digest("abc")
# => "3a81oZNherrMQXNJriBBMRLm+k6JqX6iCp7u5ktV05ohkpkqJ0/BqDa6PCOj/uu9RU1EI2Q86A4qmslPpUyknw=="

raffle_ractor.rb

# frozen_string_literal: true

require 'digest'
Digest::MD5.base64digest('abc123') # I ran into issues if the first use was in the ractor pool. not sure why

ALPHABET = %w(
  a b c d e f g h i j k l m n o p q r s t u v w x y z
  0 1 2 3 4 5 6 7 8 9
).freeze

generactor = Ractor.new(ALPHABET, name: 'generactor') do |alphabet|
  close_incoming

  ALPHABET.each do |one|
    ALPHABET.each do |two|
      ALPHABET.each do |three|
        ALPHABET.each do |four|
          ALPHABET.each do |five|
            Ractor.yield([one, two, three, four, five].join('').freeze)
          end
        end
      end
    end
  end

  close_outgoing
end

id = 'YOUR UNIQUE ID HERE' # (I used my email address)
digest = 'YOUR DIGEST PROVIDED BY @Kush'

puts 'running'

ractors = 1000.times.map do |n|
  Ractor.new(generactor, id, digest, name: "hasher-#{n}") do |generactor, id, digest|
    loop do
      begin
        raffle_candidate = generactor.take
      rescue Ractor::ClosedError
        break
      end
      hash = Digest::MD5.base64digest(id + raffle_candidate)

      puts "Found it! Your raffle number is #{raffle_candidate}" if hash == digest
    end
  end
end

ractors.delete(Ractor.select(*ractors).first) until ractors.empty?

puts 'done'

sample.rb

require 'digest'
​
# Some notes,
# - The algorithm we have used comes from the core Ruby digest module.
# - It is not necessarily the one used in this example.
# - All we are doing is concatenating your id with your raffle number.
​
# Run this script with:
# ruby sample.rb me@example.com BjQwH7VH9Ef1tAiQ7d/H1Va1nyWIsZxZRb3oSMGE87w=
# This should print your raffle number for this unique id and digest combination
​
def generate_hash(id, raffle_number)
  Digest::SHA256.base64digest(id+ raffle_number)
end
​
def mine_raffle_number(id, digest)
  alphabet = %w(a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9)
​
  [["1", "2", "3", "4", "5"], ["a", "b", "c", "d", "e"]].each do |raffle_candidate|
    raffle_candidate = raffle_candidate.join("")
    if generate_hash(id, raffle_candidate) == digest
      puts "Found it! Your raffle number is #{raffle_candidate}"
      break
    end
  end
end
​
id, digest = ARGV[0], ARGV[1]
mine_raffle_number(id, digest)