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

Friday, September 22, 2017

Cryptopals Set 2 -- F#

After a hiatus, Set 2 completed in F#:

After struggling with type mismatches using sequences vs lists vs arrays for a while, I settled on using byte arrays as inputs and outputs wherever possible. While it seems more functional to recurse over lists, many of the problems are much simpler when it is possible to index directly into arrays. Also, the .NET AES function assumes an array.

The F# solutions have fewer lines than the Python ones, but verbosity is comparable. In part this is due to the fact that using immutable objects is just more verbose for some operations (e.g. creating a new array with one byte difference in the middle). It will be interesting to see how the comparison develops with some of the more complex problems. (Of course, the real significance does not lie in word or line count, but correctness and conciseness of solutions...)


  • Challenge 14 Byte-at-a-time ECB decryption -- I realized that my previous Python implementation did not interpret the problem correctly (it assumed that the target bytes could be fed into the oracle one block at a time, whereas the oracle already ships with all target bytes, so to speak). I also interpreted the oracle function slightly different this time, insofar as having an unknown, random prefix that does not change once the oracle function is initialized (as opposed to returning a different prefix each time the oracle function is called).