[Haskell-cafe] cryptography in haskell

Marcel Fourné haskell at marcelfourne.de
Tue Feb 17 09:43:12 UTC 2015

Am Sat, 7 Feb 2015 11:53:42 -0500 schrieb Patrick Mylund Nielsen:
>In other words, Haskell eliminates several classes of errors, but
>doesn't prevent logic errors, and can do nothing about poor standards.
>Aside from this, I think the main issues would be:
>  - Timing resistance: This is not as simple as sprinkling some bitwise
>operations on your crypto code. It took a long time to figure out even
>the basics in OpenSSL, and for better and worse it's more difficult to
>intuit what your Haskell code will be compiled to than it is with C
>(though C compilers have been known to optimize away constant-time

I feel prompted to add something in here, since I'm working on this as
the author of hecc[0].
My published basic implementation of elliptic curve cryptography
contains the basic math for the so-called NIST-curves[1] in a
best-effort timing-attack resistant way, which I will try to explain
here. I will try to make my own experiences into simple guidelines this
way, so it might be a bit long-ish.

There are numerous ways to see different execution times depending on
the bits of the secret key, each of which has to be fixed.
First of all, if there is a branch in your code, a construct like
if secretkeybit == True then do_something else do_nothing
is way too easy to attack. 
(1) All your branches need to have exactly the same execution times.

If you implement RSA or ECC, there will at some point be a
square-and-multiply or double-and-add equivalent. A good fix for this
is the Montgomery's Ladder, which has the property of juggling both
branches in its parameters. In theory, this will leave no timing
channel since both branch-parameters will be executed (I learned:
{-# LANGUAGE BangPatterns #-} is very helpful here).
(2) All branches need to be really executed.

Sadly, this is not sufficient in a lazy evaluation environment like
Haskell - or any other language which permits the compiler to optimize
computations away (I agree: There be dragons if you really want to be
compiler-safe in C! ;-)).
I found out that special patterns in a secret key can lead a
lazy Montgomery Ladder to faster execution times in Haskell, which I
will try to explain in a proper paper in detail, time permitting.

There are malicious little things in modern CPUs called "caches", which
make some executed code quite a bit faster. In company with the branch
prediction unit, branches based on bits of the secret key become very
volatile, so the best defense is
(3) No branches based on the content of bits of the secret key.

This point is very hard to do when implementing the NIST-curves for
TLS, my own code is not yet made in this fashion.

Also currently, most people use Integer-gmp, which is of course based
on gmp, which got timing-attack resistant (slower) implementations
of methods in its version 6 release, so every one before that may be
insecure when regarding timing attacks. This is not a deal-breaker,
since other libraries in other languages also depend on gmp, like
nocrypto[2] for Mirage OS and GNUTLS.

I am currently fixing my new Ed25519/EdDSA implementation in pure
Haskell (please don't confuse it with the fully functioning and fast
C-wrapper one [3]), which is branch-free per point (3) and should be an
example of code under such a rule. 
Right now I am not sure when the code will be ready for public
scrutiny, but it should at least be implementation-secure and correct,
being fast can follow later.
This release will also feature a rework of hecc and a name-change,
since the possible confusion with Hyper-Elliptic Curve Cryptography.

Please note: I am currently searching a (paid) position as (preferably)
phd student. I like working on functional programming, provabilty and
cryptography. If you or anyone you know has interest in having me
working for them, please contact me!

Best of wishes,
Marcel Fourné

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 801 bytes
Desc: OpenPGP digital signature
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150217/7db7ccaa/attachment-0001.sig>

More information about the Haskell-Cafe mailing list