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 http://archiv.infsec.ethz.ch/education/fs08/secsem/bleichenbacher98.pdf).

https://github.com/tkuriyama/cryptopals/tree/master/set6

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.

https://github.com/tkuriyama/cryptopals/tree/master/set6