10 ms·

A number of people are suggesting that this Haskell implementation must be worse than OpenSSL. It probably is. Writing good crypto code is hard. There are proba

A number of people are suggesting that this Haskell implementation must be worse than OpenSSL. It probably is. Writing good crypto code is hard. There are probably bugs. Many are saying that one problem with Haskell is that you can't eliminate side-channel attacks due to features of the language. I disagree. There is no common language better than Haskell at encoding invariants in the type system. One could, for example, implement a "biggishnum" library in Haskell using large but fixed size integers and constant-time operations. Free monads are a powerful idea in Haskell[1]. They allow one to easily generalize "interpreters" over sequences of commands. In Haskell, more-so than any other language I've ever used, one can decouple execution from algorithm specification. Free applicative functors generalize further[2]. They define a computational structure that must be fixed a priori. That is, by definition a free applicative functor cannot know the state of the data during its execution. There are some problems with this. Applicative functors have an operation which can lift regular functions into it. That operation would have to be hidden, so that only a kernel was exposed that offered the ability to initialize data, and then perform computations upon it. But it's possible to do this. It is actually not a radical idea to imagine this being done in Haskell. Making a library and a set of primitive operations that can be used by an end user safely, in provably constant time is possible. [1] http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html http://www.haskellforall.com/2012/06/you-could-have-invented... [2] http://paolocapriotti.com/assets/applicative.pdf http://paolocapriotti.com/assets/applicative.pdf

cynicalkane 13y ago
I'm wondering about a situation where forgetting a strictness annotation is the analogous Haskell situation of forgetting to bounds-check some input. There are lots of ways in Haskell for something not to be evaluated. (No, the simple fixes like 'use strict fields' do not cover all cases.) To put all of them behind a free monad seems like it would be giving up a lot. In C you could have made some 'safe buffer' struct together with some safe set of functions. But people didn't do that.
- AnthonyMouse 13y ago
  > In C you could have made some 'safe buffer' struct together with some safe set of functions. But people didn't do that. Exactly. struct buffer { void* data; size_t len; }; void smemcpy(buffer* dst, buffer* src, size_t n) { if(dst->len < n || src->len < n) abort(); memcpy(dst->data, src->data, n); } I mean how hard is that, honestly? Buffer bugs in C don't come from the language, they come from the tendency of C programmers to value performance highly. "I just checked that the buffer is big enough, I don't need memcpy to waste cycles checking it again. I don't need that length variable sucking up memory when I know how big the buffer is." Except when you do.
  - sseveran 13y ago
    They come from the C language allowing it.
    - AnthonyMouse 13y ago
      All Turing complete languages allow you to do anything all Turing complete languages allow you to do. You can allocate a huge block of memory in Java or C# and then write your own malloc to allocate buffers from subsets of it. In some cases that may have better performance. It also allows you to have buffer overruns. You can run right off the end of one buffer and into the next and the language won't stop you because it only knows that you haven't reached the end of the array it allocated.
      - lomnakkus 13y ago
        Do Turing machines have a concept of "undefined behavior" in the same way that C does? AFAICT all behavior of a Turing machine is defined -- sure you might not calculate what you want, but that doesn't admit arbitrary behvaior outside of the semantics of the machine as in the C language.
        unstabilo 13y ago
        "Undefined behavior" means "undefined by the language specification", but it is well defined by the compiler implementation. In other words, you never use the C language, always an implementation.
freyrs3 13y ago
> There is no common language better than Haskell at encoding invariants in the type system. There are a few uncommon dependently typed ones with code extraction to other languages though. Though doing so is fairly time intensive still.
orblivion 13y ago
> A number of people are suggesting that this Haskell implementation must be worse than OpenSSL. It probably is. Writing good crypto code is hard. There are probably bugs. Ok, but if it were vetted as much as openssl, it would probably be much better, yes?
- dtech 13y ago
  Define "better". Probably it wouldn't be more secure because both would be scrutinized and production-tested about the same. It would protect us against some common C errors but might make us vulnerable to "common" Haskell vulnerabilities. You really can't say. It probably would be slower though, which is kind of a big deal for webservers and the like.
  - mercurial 13y ago
    > It probably would be slower though, which is kind of a big deal for webservers and the like. More critically, it would only be useful to Haskell code. Haskell, unless C, cannot be embedded. Having a version in Rust - which does not rely on the runtime - ought to be safe from this kind of issue (baring any problem in Rust itself) while being still embeddable from external code. It would still be somewhat slower than C, and of course Rust is far from mature.
    - tormeh 13y ago
      Doesn't Haskell compile first to C and then to native?
      - h3st 13y ago
        Not since GHC 7.0: http://www.haskell.org/ghc/docs/7.4.2/html/users_guide/code-generators.html http://www.haskell.org/ghc/docs/7.4.2/html/users_guide/code-...
    - stefantalpalaru 13y ago
      http://www.haskell.org/haskellwiki/Calling_Haskell_from_C http://www.haskell.org/haskellwiki/Calling_Haskell_from_C
klrr 13y ago
How would you restrict the possability of lifting a function into an Applicative? Can't you simply use pure and <*> for that?
exDM69 13y ago
> Many are saying that one problem with Haskell is that you can't eliminate side-channel attacks due to features of the language. I disagree. There is no common language better than Haskell at encoding invariants in the type system. One could, for example, implement a "biggishnum" library in Haskell using large but fixed size integers and constant-time operations. Why do you disagree? Timing attacks are probably the easiest kind of side channel attacks to prevent but CPU cache line eviction and branch prediction are a lot more difficult to deal with. Especially when using a programming language with managed memory where you can't be quite sure what kind of memory accesses a program will perform. And in the days of virtual machines on cloud servers, they are very relevant. I do not think that it is totally impossible to write Haskell crypto code without any side channels, it is certainly more difficult than writing crypto code in C or Assembler. But the big problem is that now you'd need the programmers dealing with crypto not only to be proficient cryptographers but also experts on the internals of the Haskell runtime system. That's a pretty tall order. I would like to hear from the original authors of this library, what was their motivation in starting this project? I am sure they were not unaware of the potential of side channel attacks. I don't think this project was started with the intention of replacing OpenSSL in production use, but perhaps for fun or educational purposes. Or perhaps to write offline tools for creating and validating certificates, etc.
- AaronFriel 13y ago
  I'm sorry if I wasn't clear. With the appropriate types in Haskell, you can write a data type that would be called a free applicative functor. It can be used to describe the shape of a computation. By reducing the surface area of said functor, by not exposing the "pure" operation, one can describe computation that are fixed in terms of their input. This is amazing, because I mean truly fixed. The course of execution cannot be altered by the values of the input. Cache line eviction? All memory access is statically known in advance. Branch prediction? There are no branches. The code would look a lot like what the Haxl[1] project at Facebook has produced. They used applicative functors to create a domain-specific language that described the shape of a computation without specifying the details. That allows them to write a compiler for their DSL in Haskell. In their case, they used Haxl to hide concurrency from their users, Facebook developers. Those developers can use Haxl to write concurrent, cached, optimized and type-checked queries against Facebook's datastores, without having to know how to write safe concurrent, fast queries. To the Facebook developers, there is no concurrency, the code they write just looks like a monad or an applicative in Haskell. It should be no surprise then that one of the lead developers of Haxl originally worked on the Glasgow Haskell Compiler. [1] Haxl slides [PDF warning]: https://github.com/meiersi/HaskellerZ/raw/master/meetups/20130829-FPAfternoon_The_Haxl_Project_at_Facebook/The%20Haxl%20Project%20at%20Facebook.pdf https://github.com/meiersi/HaskellerZ/raw/master/meetups/201...

cynicalkane 13y ago

I'm wondering about a situation where forgetting a strictness annotation is the analogous Haskell situation of forgetting to bounds-check some input. There are lots of ways in Haskell for something not to be evaluated. (No, the simple fixes like 'use strict fields' do not cover all cases.) To put all of them behind a free monad seems like it would be giving up a lot. In C you could have made some 'safe buffer' struct together with some safe set of functions. But people didn't do that.

AnthonyMouse 13y ago
> In C you could have made some 'safe buffer' struct together with some safe set of functions. But people didn't do that. Exactly. struct buffer { void* data; size_t len; }; void smemcpy(buffer* dst, buffer* src, size_t n) { if(dst->len < n || src->len < n) abort(); memcpy(dst->data, src->data, n); } I mean how hard is that, honestly? Buffer bugs in C don't come from the language, they come from the tendency of C programmers to value performance highly. "I just checked that the buffer is big enough, I don't need memcpy to waste cycles checking it again. I don't need that length variable sucking up memory when I know how big the buffer is." Except when you do.
- sseveran 13y ago
  They come from the C language allowing it.
  - AnthonyMouse 13y ago
    All Turing complete languages allow you to do anything all Turing complete languages allow you to do. You can allocate a huge block of memory in Java or C# and then write your own malloc to allocate buffers from subsets of it. In some cases that may have better performance. It also allows you to have buffer overruns. You can run right off the end of one buffer and into the next and the language won't stop you because it only knows that you haven't reached the end of the array it allocated.
    - lomnakkus 13y ago
      Do Turing machines have a concept of "undefined behavior" in the same way that C does? AFAICT all behavior of a Turing machine is defined -- sure you might not calculate what you want, but that doesn't admit arbitrary behvaior outside of the semantics of the machine as in the C language.
      - unstabilo 13y ago
        "Undefined behavior" means "undefined by the language specification", but it is well defined by the compiler implementation. In other words, you never use the C language, always an implementation.

freyrs3 13y ago

> There is no common language better than Haskell at encoding invariants in the type system. There are a few uncommon dependently typed ones with code extraction to other languages though. Though doing so is fairly time intensive still.

orblivion 13y ago

> A number of people are suggesting that this Haskell implementation must be worse than OpenSSL. It probably is. Writing good crypto code is hard. There are probably bugs. Ok, but if it were vetted as much as openssl, it would probably be much better, yes?

dtech 13y ago
Define "better". Probably it wouldn't be more secure because both would be scrutinized and production-tested about the same. It would protect us against some common C errors but might make us vulnerable to "common" Haskell vulnerabilities. You really can't say. It probably would be slower though, which is kind of a big deal for webservers and the like.
- mercurial 13y ago
  > It probably would be slower though, which is kind of a big deal for webservers and the like. More critically, it would only be useful to Haskell code. Haskell, unless C, cannot be embedded. Having a version in Rust - which does not rely on the runtime - ought to be safe from this kind of issue (baring any problem in Rust itself) while being still embeddable from external code. It would still be somewhat slower than C, and of course Rust is far from mature.
  - tormeh 13y ago
    Doesn't Haskell compile first to C and then to native?
    - h3st 13y ago
      Not since GHC 7.0: http://www.haskell.org/ghc/docs/7.4.2/html/users_guide/code-generators.html http://www.haskell.org/ghc/docs/7.4.2/html/users_guide/code-...
  - stefantalpalaru 13y ago
    http://www.haskell.org/haskellwiki/Calling_Haskell_from_C http://www.haskell.org/haskellwiki/Calling_Haskell_from_C

klrr 13y ago

How would you restrict the possability of lifting a function into an Applicative? Can't you simply use pure and <*> for that?

exDM69 13y ago

> Many are saying that one problem with Haskell is that you can't eliminate side-channel attacks due to features of the language. I disagree. There is no common language better than Haskell at encoding invariants in the type system. One could, for example, implement a "biggishnum" library in Haskell using large but fixed size integers and constant-time operations. Why do you disagree? Timing attacks are probably the easiest kind of side channel attacks to prevent but CPU cache line eviction and branch prediction are a lot more difficult to deal with. Especially when using a programming language with managed memory where you can't be quite sure what kind of memory accesses a program will perform. And in the days of virtual machines on cloud servers, they are very relevant. I do not think that it is totally impossible to write Haskell crypto code without any side channels, it is certainly more difficult than writing crypto code in C or Assembler. But the big problem is that now you'd need the programmers dealing with crypto not only to be proficient cryptographers but also experts on the internals of the Haskell runtime system. That's a pretty tall order. I would like to hear from the original authors of this library, what was their motivation in starting this project? I am sure they were not unaware of the potential of side channel attacks. I don't think this project was started with the intention of replacing OpenSSL in production use, but perhaps for fun or educational purposes. Or perhaps to write offline tools for creating and validating certificates, etc.

AaronFriel 13y ago
I'm sorry if I wasn't clear. With the appropriate types in Haskell, you can write a data type that would be called a free applicative functor. It can be used to describe the shape of a computation. By reducing the surface area of said functor, by not exposing the "pure" operation, one can describe computation that are fixed in terms of their input. This is amazing, because I mean truly fixed. The course of execution cannot be altered by the values of the input. Cache line eviction? All memory access is statically known in advance. Branch prediction? There are no branches. The code would look a lot like what the Haxl[1] project at Facebook has produced. They used applicative functors to create a domain-specific language that described the shape of a computation without specifying the details. That allows them to write a compiler for their DSL in Haskell. In their case, they used Haxl to hide concurrency from their users, Facebook developers. Those developers can use Haxl to write concurrent, cached, optimized and type-checked queries against Facebook's datastores, without having to know how to write safe concurrent, fast queries. To the Facebook developers, there is no concurrency, the code they write just looks like a monad or an applicative in Haskell. It should be no surprise then that one of the lead developers of Haxl originally worked on the Glasgow Haskell Compiler. [1] Haxl slides [PDF warning]: https://github.com/meiersi/HaskellerZ/raw/master/meetups/20130829-FPAfternoon_The_Haxl_Project_at_Facebook/The%20Haxl%20Project%20at%20Facebook.pdf https://github.com/meiersi/HaskellerZ/raw/master/meetups/201...