Sunday, February 16, 2020

Mini Regex

Hacker News linked to Brian Kenighan's post about a small regex matcher, which seemed like a good bite-sized problem to try implementing -- both in general and for practicing Haskell, particularly with this being a pattern matching problem.

Following Kernighan's specifications, the regex language is limited to:

    c    matches any literal character c
    .    matches any single character
    ^    matches the beginning of the input string
    $    matches the end of the input string
    *    matches zero or more occurrences of the previous character

To make the exercise a bit more stateful, I chose to implement find (return the left-most occurrence of a pattern that matches the regex, if it exists), instead of just indicating the presence of a match. There is minimum lookahead required -- just one character to detect boundaries for the Kleene star.

I first tried to implement find with a lazy map over the tails of the input (returning the head as the left-most match), but ran into the problem of inputs with no matches. Since I couldn't find an out-of-box function, mapUntil implements a map that stops when a non-default value is found, and otherwise returns the default value. This also has the benefit of using an empty string to indicate no match, which is more direct here than, say, using Maybe. Always wrapping and unwrapping the input with the start and end sentinels seemed like a reasonable price to avoid introducing special cases later on.

find :: Regex -> String -> Match
find r s = unwrap $ mapUntil "" (findWord r) (tails $ wrap s)
  where wrap xs = ('^':xs) ++ "$"
        unwrap xs = [c | c <- xs, c `notElem` ['^', '$']]

mapUntil :: Match -> (String -> Match -> Match) -> [String] -> Match
mapUntil d _ [] = d
mapUntil d f (x:xs) = if m /= d then m else mapUntil d f xs
  where m = f x ""

The core matching function covers four patterns: non-star regex, star regex, the regex is consumed (success), or otherwise failure.

findWord :: Regex -> String -> Match -> Match
findWord (x:'*':xs) s@(y:ys) ms = findWord xs ys' (reverse ms'++ ms)
  where (ms', ys') = if not (match x y) then ("", s) else splitWhile (matchStar x xs) s
findWord (x:xs) (y:ys) ms = if match x y then findWord xs ys (y:ms) else ""
findWord "" _ ms = reverse ms
findWord _ _ ms = ""

Match is very simple. MatchStar needs a bit of extra state, since '.*' matching should stop if the next part of the regex matches input.

match :: Char -> Char -> Bool
match x y = x == '.' || x == y

matchStar :: Char -> String -> Char -> Bool
matchStar x [] y = match x y
matchStar x (x':xs) y = (x == '.' && x' /= y) || x == y

SplitWhile seems like it should exist... it calls both takeWhile and dropWhile, so could be rewritten more efficiently to require only single pass over the input.

splitWhile :: (a -> Bool) -> [a] -> ([a], [a])
splitWhile f xs = (takeWhile f xs, dropWhile f xs)

There are a few reverses and concatenations, which weren't immediately obvious to me to refactor into more efficient patterns. Code with some hand-written test cases:

Monday, October 7, 2019

Learn You a Haskell, Again

After a few failed attempts in past years, I feel like I've finally collected enough momentum and functional thinking to overcome the initial hurdle in learning Haskell.

Brent Yorgey's 2013 UPenn class was recommended by a few sources, so I worked through that over the past two or three months. The class pulls together material from Learn You a Haskell (LYAH), Real World Haskell (RWH) and lectures notes into 12 weeks of materials. There are 11 weekly assignments that culminate in Functors, Applicatives, and Monads. At this point, I think I need significantly more practice in the last topics... Overall, the reinforcement provided by two independent texts in addition to the course materials was quite helpful in triangulating new topics, both conceptually and through worked examples.

Some good next steps seem to be continue working through some later chapters in LYAH and RWH (with a particular interest in monadic parsing), as well as the next course suggested by

Sunday, August 26, 2018

Cryptopals Set 6 -- Bleichenbacher

After another hiatus, I finally managed to wrap up Set 6 with Bleichenbacher's PKCS 1.5 padding oracle attack (original paper from '98

All of the padding-based attacks are quite interesting. From first principles, I guess it is difficult to design padding that is cryptographically sound, since by definition padding needs to be deterministic and reasonably easy to parse.

One thing that escapes me is the use of ceiling division for a number of equations in Bleichenbacher's paper -- it doesn't seem to be specified, yet all the implementations I referenced seemed to apply it consistently.

I will probably take a break from the Cryptopals for now (i.e. defer Sets 7 and 8) and tackle some other projects. I feel reasonably comfortable with F# now, but still want to learn Haskell, and meanwhile Python is fully transitioning to Python 3 and Guido has retired as BDFL...

The MOOC landscape seems to have advanced in the past year or two as well, so it will be interesting to take up a few more courses again.

Tuesday, March 20, 2018

Cryptopals Set 6 -- F#

I've worked through Set 6 up to the last two problems involving Bleichenbacher's PKCS 1.5 Padding Oracle attack. With a new job just started, it will likely take a while longer to complete those, so this will be a partial post in the meantime.

Completing the first six problems of the set required me to revisit two shortcuts that I took thus far: a reasonably fast (probabilistic) prime gen algorithm, and a cube root (or n-root) algorithm for BigIntegers. In both cases the implementations are borrowed, but it was a good exercise to think through them.

As a slight non sequitur: working with BigIntegers in F# has given me a deep appreciation for just how convenient it is to work with integers in a language like Python. Thanks to PEP 237, integers are treated for the most part uniformly, so the user never needs to think about size. But of course, big integers that exceed the CPU word size do require implementation. Which is obvious from first principles, but not something that occurred to me in a meaningful way until I had to write a re-implement a number of functions to work for BigIntegers. Convenience and learning are uneasy friends.

Overall in the first six problems, the exercise of forging a 1024-bit RSA signature (when e=3) was both the most interesting and the most challenging.

Thursday, November 23, 2017

Cryptopals Set 5 - F#

Set 5 was advertised as difficult, but I found the implementations to be quicker that previous sets as they involve more number theory and less programming.

I took a few implementation shortcuts (each of them a good exercise to do properly, but I'd rather forge ahead and get through the cryptographic concepts at this point):
  • Client-server interactions are simulated (still haven't sorted out F# package manager yet)
  • Prime numbers are drawn from known list rather than generated 
  • Cube root solving is ignored (p40 just tests the result against the cube of the original message, rather than testing the cube root of the result against the original message)
I spent some time trying to implement Newton's method of approximating roots, which worked fine for square roots but in my implementation almost always did not converge for cube roots (once a guess became negative, it stayed negative... how to constrain to positive numbers while improving the guess in each iteration?). Something else to investigate in the future.

Sunday, October 29, 2017

Cryptopals Set 4

As advertised, Set 4 was easier to work through than Set 3.

For better or for worse, I couldn't actually find implementations of SHA-1 and MD4 in F#, so I ended up implementing them using a combination of the standard descriptions and C# / Python implementations. (The MD4 implementation is still incorrect somewhere, so I'll probably need to fix it before attempting Wang's attack later on in the challenges.) As with the Mersenne Twister, there is something very reassuring about being forced to implement each digest iteration in a pure fashion without mutations.

For the SHA1-HMAC timing leak attacks, I fell back to Python (trying Python 3!) since I haven't yet been able to get Paket / Nuget to work on my OS X machine. The F# tooling via Visual Studio for Mac seems like it is coming along, but I'm still trying to work in emacs... I'd like to play around with Suave and some of F#'s HTTP message handling libraries at some point. Meanwhile, setting up a virtualenv for Python 3 and running a tiny server via Flask was incredibly easy.

Sunday, October 15, 2017

Cryptopals Set 3 -- F#

I've finished the remainder of Set 3 of the Cryptopals challenges... in the interest of time -- and of focusing on F# -- I've abandoned the parallel Python implementations for now.

The Mersenne Twister (MT) series were fairly interesting. Though the underlying math remains somewhat elusive, reading the pseudocode and implementing in F# gave me a good understanding of what happens in each iteration. One item that I didn't consider initially was the integer type. The 32-bit MT calls for an unsigned 32-bit integer... which should be fairly obvious, except that one rarely needs to think about different integer types in Python. A danger of starting with such a convenient language, perhaps...

I didn't properly break the fixed-nonce CTR (challenge 20), as my previous frequency analysis failed to fully decrypt to codes. But it looks like this will require revisiting in the next set of problems (challenge 25).