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.

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

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.

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

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

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

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:

https://www.iacr.org/archive/eurocrypt2002/23320530/cbc02_e02d.pdf

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

https://github.com/tkuriyama/cryptopals/blob/master/set3/p17.fsx



Friday, September 22, 2017

Cryptopals Set 2 -- F#

After a hiatus, Set 2 completed in F#: https://github.com/tkuriyama/cryptopals

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

Notes

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

Sunday, August 20, 2017

Units of Measure in F#

An interesting (and seemingly very useful feature) of F#: units-of-measure types, which help the compiler reason about correctness. 

https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/units-of-measure

> [<Measure>] type cm;;
 [<Measure>]
 type cm

> [<Measure>] type mile;;
 [<Measure>]
 type mile

> [<Measure>] type hour;;
 [<Measure>]
 type hour

> let distance = 20.0<mile>;;
 val distance : float<mile> = 20.0

> let duration = 12.0<hour>;;
 val duration : float<hour> = 12.0

> let speed = distance / duration;;
 val speed : float<mile/hour> = 1.666666667

> speed + 2<cm>;;
 Stopped due to error
 System.Exception: Operation could not be completed due to earlier error
 The type 'int<cm>' does not match the type 'float<mile/hour>' at 3,8
 The type 'int<cm>' does not match the type 'float<mile/hour>' at 3,6


> speed + 1.0<mile/hour>;;
 val it : float<mile/hour> = 2.666666667

Sunday, May 28, 2017

Cryptopals Set 1 -- F#


Completed with word/line count comparisons stats between Python and F# here: https://github.com/tkuriyama/cryptopals

F# is about 1000 lines total vs 1180 lines in Python. Although F# is overall more concise, there is considerably more boilerplate in calling .NET libraries such as cryptography functions.

Since the problem space is relatively pure computation, I've found writing functionally in F# to be more pleasurable. On the other hand, the MSDN documentation seems rather unfriendly compared to what I've gotten used to in Python... (fortunately, the C# examples are pretty readable and I found someone else's example of using the AES decryption API).

Thursday, April 27, 2017

Cryptopals Set 2


http://cryptopals.com/sets/2
https://github.com/tkuriyama/cryptopals/tree/master/set2

Notes
  • Challenge 9 and 15 PKCS#7 padding -- the challenges do not make clear that that if the final data block fits the data block perfectly (e.g. there are 16 bytes of data remaining in the final 16-byte block), an additional block should be appended as padding.
  • Challenge 14 Byte-at-a-time ECB decryption -- this is indeed a harder variant of challenge 12, since a random number of bytes being prefixed to the attacker-controlled text means that the oracle is not always reliable. From previous challenges, however, we know that repeating blocks are encrypted identically in ECB mode. We can therefore prepend the attacker-controlled text with two repeating blocks, i.e. have the oracle encrypt (random prefix || repeating blocks || attacker-controlled text || target-bytes). If we observe repeating blocks, we know where our attacker-controlled text begins (as a wrapper around the oracle function, call this "smart oracle"). Assuming that the random number of bytes prefixed is uniformly distributed over integers with some upper boundary N, it will take roughly N times more calls to the oracle to achieve a desirable result... which is reasonable as it scales linearly. I'm still missing something as the smart oracle sometimes fails, but decryption generally works after a few tries.

Saturday, April 22, 2017

Cryptopals Set 1

I have started working through the Cryptopals Challenges after hearing about it on a Podcast.__init__ episode. It seems like a good and practical refresher to Dan Boneh's Crytopgraphy I class on Coursera (incidentally, I've been waiting for Crytography II for many years but the course seems to be constantly pushed back). It should also be a good exercise to work through in F# -- as a means to learn more of the language -- after completing a first pass in Python.

Set 1 is fairly straightforward, though it took me a while to workout how to operate consistently on bytearrays (per the Cryptopals rules) and convert between different encodings (hex, base64, bytes represented as ints vs chars...). It seems that Python 3 makes the experience of working with bytes a little easier.

Notes

  • Challenge 3 Single-Byte XOR Cipher: most frequency distribution of characters in the English language that I found did not include non-alphabet characters, such as space. My solution did not work until space was included in the scoring of plaintext (using chi-squared). 

https://cryptopals.com/sets/1
https://github.com/tkuriyama/cryptopals/tree/master/set1