Stripe CTF Level 0 Full solutions

level0-bloomfilter.hs

module Main where

import qualified Data.BloomFilter as B
import Data.BloomFilter.Hash (hashes, cheapHashes)
import System.Environment (getArgs)
import Data.Char (toLower)
import Control.Monad.ST (ST, runST)
import Data.STRef (newSTRef, modifySTRef, readSTRef)
import Control.Monad (forM_)

-----------

main = do
  args <- getArgs
  let dictfile = case args of [] -> "/usr/share/dict/words"
                              [d] -> d
  dict <- readFile dictfile
  input <- getContents

  let output = doMemberTest dict input
  putStr output

-----------

doMemberTest :: String -> String -> String
doMemberTest dict = unlines . map unwords . map (map formatOutput) . map (map $ testEl $ isMember $ fromWords $ lines dict) . parseInput

parseInput :: String -> [[String]]
parseInput = map words . lines

testEl :: (String -> Bool) -> String -> (Bool, String)
testEl tst s = (tst s, s)

formatOutput :: (Bool, String) -> String
formatOutput (b,w) = (if b then "" else "<") ++ w ++ (if b then "" else ">")

------

newtype Dictionary = D (B.Bloom String)

falsePositiveRate = 0.01
bits = 4194304
hashFns = cheapHashes 10

fromWords :: [String] -> Dictionary
--fromWords = D . B.fromListB hashFns bits . lines

fromWords ws = D $ B.createB hashFns bits $ \mbf -> do
  forM_ ws $ \w -> do
    B.insertMB mbf w

isMember :: Dictionary -> String -> Bool
isMember (D b) = flip B.elemB b . map toLower

-------

level0-set.hs

module Main where

import qualified Data.Set as S
import System.Environment (getArgs)
import Data.Char (toLower)

import Control.Monad.ST
import Data.STRef
import Control.Monad (forM_)

-----------

main = do
  args <- getArgs
  let dictfile = case args of [] -> "/usr/share/dict/words"
                              [d] -> d

  dict <- readFile dictfile
  input <- getContents

  d <- return $ fromDict (lines dict)

  let output = doMemberTest d input
  putStr output

-----------

doMemberTest :: Dictionary -> String -> String
doMemberTest d = printOutput . map (map $ testEl $ isMember d) . parseInput

printOutput :: [[String]] -> String
printOutput = unlines . map unwords

parseInput :: String -> [[String]]
parseInput = map words . lines

testEl :: (String -> Bool) -> String -> String
testEl tst s = let b = tst s in formatOutput b s

formatOutput :: Bool -> String -> String
formatOutput b w = (if b then "" else "<") ++ w ++ (if b then "" else ">")

------

newtype Dictionary = D (S.Set String)

fromDict :: [String] -> Dictionary
--fromDict = D . S.fromList

fromDict ws = D $ runST $ do
  s' <- newSTRef (S.empty)
  forM_ ws $ \w -> do
    modifySTRef s' (S.insert w)
  readSTRef s'

isMember :: Dictionary -> String -> Bool
isMember (D s) = flip S.member s . map toLower

-------

level0.c++

#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include "bloom_filter.hpp"

using namespace std;

bloom_filter *filter;

bool included(string word) {
  if (word[word.length()] == '.') return false;

  transform(word.begin(), word.end(), word.begin(), ::tolower);
  return filter->contains(word);
}

void run() {
  string line;
  while (getline(cin, line)) {
    istringstream iss(line);
    bool first = true;

    do {
      string word;
      iss >> word;
      if (word == "") {
        break;
      }

      if (!first) {
        cout << " ";
      } else {
        first = false;
      }

      if (included(word)) {
        cout << word;
      } else {
        cout << "<" << word << ">";
      }
    } while (iss);
    cout << endl;
  }
}

void build_dict(string dictfn) {
  bloom_parameters parameters;

  // How many elements roughly do we expect to insert?
  parameters.projected_element_count = 250000;

  // Maximum tolerable false positive probability? (0,1)
  parameters.false_positive_probability = 0.0001; // 1 in 10000

  // Simple randomizer (optional)
  parameters.random_seed = 0xA5A5A5A5;

  parameters.compute_optimal_parameters();

  //Instantiate Bloom Filter
  filter = new bloom_filter(parameters);

  ifstream dictfile(dictfn.c_str());
  if (dictfile.is_open()) {
    string word;
    while (getline(dictfile, word)) {
      filter->insert(word);
    }
  }
  dictfile.close();
}

int main(int argc, char *argv[]) {
  string dictfn = "/usr/share/dict/words";
  if (argc > 1) dictfn = argv[1];

  build_dict(dictfn);
  run();
}

level0.rb

#!/usr/bin/env ruby

# Our test cases will always use the same dictionary file (with SHA1
# 6b898d7c48630be05b72b3ae07c5be6617f90d8e). Running `test/harness`
# will automatically download this dictionary for you if you don't
# have it already.

require 'set'

path = ARGV.length > 0 ? ARGV[0] : '/usr/share/dict/words'
entries = File.read(path).split("\n").to_set
rgx = /[^ \n]+/

contents = $stdin.read
output = contents.gsub(rgx) do |word|
  if entries.include?(word.downcase)
    word
  else
    "<#{word}>"
  end
end
print output