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).

Monday, October 9, 2017

Cryptopals Set 3 -- CBC Padding Oracle

Problem 17 is an interesting exercise in implementing the CBC padding oracle attack, described elegantly in Serge Vaudenay's 2012 paper:

The crux of the attack, of course, is that it only requires 1 bit of information (!) -- a yes or no from a padding oracle, indicating whether a given ciphertext's CBC padding is valid or not. It would be interesting to study at some point how the padding oracle is manifested in the real world (in older versions of TLS, etc).

The implementation took longer than expected. I'm fairly certain that I'm missing some functional programing constructs, as my solution is not very elegant... the problem (or point) being that non-mutative data structures are used, so there's quite a bit of generating new arrays (which can be verbose when one is just trying to change a single byte in the middle).