Hacker News Reader

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

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/201...

> 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

This might be what it looks like before GHC had its way with it. After GHC inlining, optimization passes, rewrite rules, the code may well contain branches, conditional memory accesses, etc.

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.

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

They come from the C language allowing it.

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.

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.

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

You're thinking of implementation-defined behaviour. Undefined behaviour is not well-defined; the compiler does not have to implement it consistently or sanely, and certainly gcc won't.

> Do Turing machines have a concept of "undefined behavior" in the same way that C does?

Sure they do. For example, nothing in the Turing machine specification tells you how fast they are. Whether a given program will run on a Turing machine in a given amount of wall clock time is undefined.

Here's a real example with real machines. Suppose you have a program with two threads. The first thread computes data and puts it on a queue for the second thread, the second thread writes it to the filesystem. When the compute thread has computed all of the data, it sleeps for 10 seconds and then terminates the program without checking whether the write thread has actually completed writing all the data to the filesystem.

That results in undefined behavior in every real language I've ever heard of. Whether the data is all written depends on how fast the CPU is, how fast the filesystem is, what other programs are scheduled on the machine that compete for CPU and filesystem access at what priority, etc. Languages don't define any of those things so you have undefined behavior.

That's a different abstraction than "Turing Machine". Turing machines do not have '"undefined behavior" in the same way that C does' - it would look like a "in state 3, if you read a 0, move to an arbitrary state, write arbitrary symbols to arbitrary locations on the tape, move head to an arbitrary position on the tape, and possibly restructure the state machine in arbitrary ways."

Turing machines have undefined behavior in exactly the same way that C does. What do you suppose happens if a Turing machine reads from a location on the tape that has never been written? The value the machine observes in that circumstance is not required to be well-defined in order for the machine to be able to do all computations required of a Turing machine. Moreover, the more you add features of actual machines like parallelism and timers, the more opportunities for undefined behavior you introduce. What do you suppose a multiprocessor Turing machine does if you write concurrently to the tape without locking?

"What do you suppose happens if a Turing machine reads from a location on the tape that has never been written?"

It reads the default symbol (see e.g. the description of a TM on Wikipedia). It's semantics are well-defined.

The semantics of TMs are well-defined. The semantics of C's "undefined behavior" is not well-defined.

I should have said "blank symbol" not "default symbol".

Clarification: all Turing complete languages allow you to do any _computation_ all Turing complete languages allow you to do.

"All Turing complete languages allow you to do anything all Turing complete languages allow you to do."

This is false. All Turing Complete languages allow you to compute anything other Turing Complete languages allow you to compute, but that says nothing about encoding, or about interaction with the world. For an obvious encoding example, imagine you have a turning machine that can write only the symbols 0 and 2 to its tape. This is obviously Turing complete - it's isomorphic to a TM that writes 0 and 1, the TM doesn't care how the symbols are labelled. Now, if we ask it to encode 7 it has no trouble doing that in some encoding, but that can't ever be "111" on the tape.

The Python language allows constructs such as socket.write(my_private_key). Do you think that just because Python makes it possible to write your private key to a socket that it must necessarily happen?

It's hard to define semantics. Here, you have potentially copied less than dst->len bytes into dst->data. Is the remaining data (up to dst->len) still valid, is it garbage, should you have adjusted dst->len, etc?

When does it even make sense to partially mix byte-level representations of some data?

The buffer abstraction is necessary, but far from sufficient to build security-critical code. To do so, you also need to code in semantics somewhere, and buffers know zilch about the meaning of the data.

Check again. Hint: "abort()" is not "return" -- that code doesn't prevent you from having to know how large the buffer is, it just shoots your program in the head if you don't. Which is basically the same semantics Java et al have by throwing an out of bounds exception when you don't catch it.

Incidentally, this is another reason that the language can't save you from yourself. Program termination is sometimes totally unreasonable, e.g. in real-time settings. And it's unreasonable regardless of the language. When an airplane falls out of the sky, you don't get to declare victory just because the reason it did was an uncaught out of bounds exception rather than a buffer overrun. In that context the programmer must explicitly handle the condition that the buffer is too small, regardless of the language, because "abnormal program termination" is not an acceptable outcome.

Your code checks whether dst->len < n, but not whether dst->len > n; i.e., after copying 5 bytes to dst, there may be another 10 bytes of garbage in dst. This 'garbage' might as well be a password from a string that was just free'd. A fix would be to set dst->len to n after this operation.

OK, I see what you're getting at. There is a difference between the end of the buffer and the end of the data. But copying some bytes into a buffer doesn't imply that you intend to discard the rest of the buffer. It's quite common to want to replace a header or some other subsection of a buffer and have the rest of the buffer remain unmodified.

Moreover, the purpose of the above is to achieve the level of bounds checking that you get with the likes of Java. If you want to go beyond that then you need something more complicated -- maybe add separate variables to the buffer struct for buffer_len and data_len and then have different memcpy functions based on whether you want existing data in the buffer to be truncated. But there comes a point at which further complexity produces more confusion than safety.

Ideally, you would have a parsing and validation routine which fills in a struct. Afterwards, you manipulate only the struct instead of raw byte representation.

> But there comes a point at which further complexity produces more confusion than safety.

Buffer is simply not the right abstraction for complex protocols, regardless of how "complex" operations you define.

> Ideally, you would have a parsing and validation routine which fills in a struct.

The parsing and validation routine is where you need the buffer abstraction. If you make a mistake there then a copy function that won't let you read or write past the end of the buffer will mitigate the damage.

    if(obj != null) {
        obj.stuff = ...
    }

I mean how hard is that exactly? yet Java applications have null pointer exceptions all time

Nothing wrong with null pointer exceptions - they are specific checks to see if the pointer is valid and are a good thing. If you see one, it means the programmer made a mistake and the runtime caught it for him.

There are also tools to help with it in the form of @NotNull, @Nullable, etc.

It's a completely different issue compared to actually accessing memory in an undefined way as you can in C. The bounds check you are replying to is manually creating something like that exception through the use of abort() while in java it is done always at the cost of some performance in exchange for safety.

Consider the following: some languages don't have null. When you need nullable what you really want is an Option/Maybe type. No null pointer exceptions, ever! It just won't compile until you fix the bug.

Or, more generally, I think languages should have union and intersection types - "(IFoo && IBar) || (IBaz)", etc. (I also think languages should have arbitrary Boolean expressions as types, where the compiler emits a warning and a runtime check if the compiler cannot prove either if the condition will be always met or it won't be always met, but that is another matter.)

Null is just a built-in final/sealed type(enum?) with a single value and no operations defined, like boolean is a type(enum?) with two values.

That, combined with proper type inference, would alleviate a large chunk of the boilerplate associated with statically typed languages in general, and Java in particular. (For how much Java is pushed as moving errors to compile time, there are an awful lot of things that fail only at run time that could be checked at compile time...)

Same thing with checked exceptions. A checked exception is really just an option - return foo or failure.

Even when Java fails at runtime, because it forces garbage collection for memory management, buffer overflows and dangling pointers can't really happen - yes, if you're not careful, the process can still have unexpected behavior, or it might crash. Actually, the Heartbleed bug wouldn't have been such an issue if OpenSSL wouldn't use its own wrapper around malloc/free (at the very least, the malloc/free underneath would be a variable in that equation), e.g. http://article.gmane.org/gmane.os.openbsd.misc/211963

So while I love strong and static type systems, the issue at play here is memory safety - the very reason for why people still use C/C++ is the same reason for why Heartbleed happened.

You're assuming that the JVM is secure. But yes, good point.

Although I'd argue that a truly strong type system should also catch problems with pointers. The compiler should try to prove that any pointer access/arithmetic can or cannot cause undefined behavior - if it could cause undefined behavior, emit a compiler error, if it cannot prove that it won't cause undefined behavior, emit a warning and insert a runtime check.

(Still have the underlying "unsafe" functions. But group them into part of the standard library as an "unsafe" package.)

That's what Rust does. Its type system prevents all memory and concurrency errors. But to be able to have a self-hosting compiler (and to be able to write an OS in it) there's also `unsafe` blocks.

If you use @NotNull etc in Java, then it also won't compile until you fix the bug.

> Buffer bugs in C don't come from the language, they come from the tendency of C programmers to value performance highly.

You have to use other people's code / language constructs which are underspecified and/or you don't have time to fully understand. Throw in versioning to the equation and now the problem is exponentially worse. This is why C code will always be full of memory vulns. Heartbleed is a very oversimplified example of the problems in C.

>In C you could have made some 'safe buffer'

No you couldn't've. C is fundamentally unsafe language and people like you should stop pretending it isn't.

People (all people) are fundamentally unsafe, not languages. It may be harder to write safe code in some languages than others, but that arguably doesn't make the language unsafe. Most certainly though, it does not make it "fundamentally" unsafe.

You can imagine a language that's memory safe. In fact, these languages exist today.

Browse through the National Vulnerability Database, and write down the language of each bug.

Discounting bad PHP, a huge majority of bugs are in C/C++ code. And "past popularity" isn't a good explanation, because a lot of the software is fairly recent.

So, the following isn't an opinion. It's simply a matter of observable fact. If you write in C/C++, you are far more likely to introduce security vulnerabilities than in other languages; therefore, unless there's a pressing reason to use these languages, don't.

> It's simply a matter of observable fact. If you write in C/C++, you are far more likely to introduce security vulnerabilities than in other languages; therefore, unless there's a pressing reason to use these languages, don't.

And in the case of crypto code, one could argue that there is a very good reason to use C/C++: to prevent timing attacks.

How hard would it be to develop a fast memory safe language that eliminates timing attacks?

That's a very good question. I think it's possible that the recent revelations will at least spur some interest in researching this. It seems like we need it badly.

That seems like a great idea.

Timing attacks work when code tries to be fast, taking shortcuts where possible. There's a reason we talk big-O instead of big-Theta: we gladly accept when an algorithm finishes early. This is, in this case, highly undesirable. Shortcuts are great, everywhere but crypto; not unlike recursion being great, unless it's embedded.

A language where every expression takes constant-time to compute seems like a solution. No short-circuiting, no variable runtimes. Don't use sorting algorithms like insertion/quicksort where best-case & worst-case are very different; use selection/merge where best-case = worst-case = average-case. Use constant-time hash functions. Caching is a very prevalent (and somewhat invisible) shortcut that needs to be solved (how can a language disable caching?).

Obviously this isn't fast but you can't have both.

Obviously this isn't fast but you can't have both.

Merge sort is still pretty fast. It isn't the fastest. But safe > fast when it comes to reliability and security.

You are making the claim that there would not be an increase in representation of other languages if they were more represented in the wild. I don't know how you could prove that.

That is, I don't think this exercise really shows what you think it does. Consider, if 90% of the software out there is in c/c++, and you had equal representation of language to vulnerability, then you would expect 90% of the vulnerabilities to be in c/c++. This would not mean that you are more likely to write bugs in those languages. In fact, unless I misunderstand, it would simply mean you are just as likely to have bugs there as otherwise.

Right?

You missed the point, and your characterization of my claim is way off.

1. A huge number of vulnerabilities affect C/C++ programs, almost all of which are memory based.

2. Memory-managed languages take care of this for you.

3. Therefore, C/C++ shouldn't be a default choice in domains where a managed language does just as well (a separate question).

Everything else is tangential.

But here are some reasons why your second paragraph is dangerously wrong (and why my claim was not as you characterize):

1. It only applies if we assume a uniform distribution of security effort across languages.

2. It only applies if we assume that c/c++ is being used for the same class of applications programs written in other languages, or that the applications have similar attack surfaces.

3. It only applies if we assume a uniform distribution of security effort over all code regardless of age.

and so on...

And also, 90% of code -- especially relatively recent code -- is not written in c/c++.

Look, I don't even really disagree with your hypothesis. I just question whether counting all of the CVEs and "discounting bad PHP, a huge majority of bugs are in C/C++ code" proves much. Other than the majority of attacked applications are c/c++. (well, likely they are php, but we are tossing that for some reason.)

Especially if you follow that with the claim of "If you write in C/C++, you are far more likely to introduce security vulnerabilities than in other languages." In order for that claim to stick, you have to show not just that there are more CVEs against c/c++ than other languages, but that there is the same effort spent in attacking non c/c++ programs. Right? (Or, am I misreading a claim on that?)

Sure, if you reduce that to "memory vulnerabilities", it is a true statement. However, you did not make that reduction. As you point out in your counter #2, there are plenty of other vulnerabilities out there. What makes you think people are more likely to avoid those than they are memory vulnerabilities in c/c++?

As for the 90% of code not being c/c++, what is the point? Unless you can show that they receive the same level of attack as the c/c++, you can not really use that to claim that they are inherently more secure. Worse, your throwing of php under the bus just shows that recent languages don't do enough to prevent security mistakes.

Heaven help you if you throw in XSS and friends. Suddenly one of the darlings of the tech industry at the moment, javascript, is rocketing to the top of the list for security blunders.

The point is that in Haskell you could reasonably define a 'biggish-num' type where only strict and constant-time operations would be possible - you couldn't forget to make an annotation, you'd have to explicitly ask for the value to become a 'normal number' before being able to make any such operation.

In C having such a 'safe buffer' struct would require discipline from you, in Haskell that'd be the natural order of things.

From your comment, I can't understand why defining a special struct in C is different from defining a special type in Haskell.

I understand that many C programmers don't do it, mind you, but how is that different from a Haskell programmer not using the proper type for a certain operation?

In Haskell, there are types that you have probably heard of but not used. Functors, applicative functors, and monads. In Haskell, I could define a value and its type:

> value :: ConstantTime Int

But how do I obtain an "Int" from that, since I know it somehow relates to an integer type? The answer is: you must ask the implementation of ConstantTime for the value, and if it doesn't want to give it to you, it doesn't have to. Constructors can be one way.

The library author could define a number of additional operations. These operations are privileged, being written as part of the library, they can actually inspect the inner data at any time. This is the "small core" that needs to be verified.

> addInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int > subInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int > mulInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int > divInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int

Then to compute something like Euler's formula one could write a function in terms of those functions.

> newtonsMethod :: ConstantTime Int -> ConstantTime Int > newtonsMethod = ...

And one can be certain that the laws that apply to `addInt` apply to `newtonsMethod`.

This composition has wonderful benefits because if there is no branching operation defined by the library, users cannot use branches inside ConstantTime. To serially apply addition, multiplication, etc, one can write in a sort of reverse polish notation:

> square :: ConstantTime Int -> ConstantTime Int > square input = mulInt input input

Using the multiplication operator, (*), would be illegal there. And that function, square, cannot inspect the value of input. Because it can't inspect the value, it can't make choices based on that value.

OP's point is that the onus is on the library developer to not just use Int. You're treating it like the library developer is a user of another library.

I guess the point is that Haskell is more expressive and declarative, which makes this almost (not totally) the default behaviour of Haskell library developers. And I guess the resulting code would be easier to parse (by a human) because of its declarative nature. It would also be easier to test due to its functional pureness.

Whether that merits dumping the incredible amount of man hours that have gone into OpenSSL is debateable. I'd probably say it's worth fixing OpenSSL and trying to refactor it into a more provably sound system.

Ok, but saying that Free Applicatives are the "default" behavior of library developers is disingenuous.

Fair point

Thanks for your detailed reply.

I still fail to see how this is fundamentally different from a similar approach in C (but maybe that's because I don't understand Haskell at all). In C you would define your ConstantTimeInt as a struct, and define a bunch of functions that operate on this struct. Using a + or * operator is also not defined for this struct. You'd have to use

   csiAdd(const struct ConstantTimeInt *addend1, const struct ConstantTimeInt *addend2, struct ConstantTimeInt *res)

In all cases it requires the developer of the library to be conscious of timing attacks, and not just use a regular int with variable-time addition.

In your example, any attempt to extend the core library is fraught with error. There is no way to safely do so and transitively trust the authorship. For example:

    void square(const struct ConstantTimeInt *value, 
                struct ConstantTimeInt *result)
    {
      sleep(rand());
      return multiply(value,value);
    }

This is legal C! The ConstantTimeInt structure does not allow the composition of operations to produce safe operations from their composition!

This is illegal Haskell:

    square :: ConstantTime Int
           -> ConstantTime Int
    square = do
      randomRIO (0,100) >>= threadDelay
      return $ multiply value value

In Haskell, tight, small libraries can be written using impure constructs (as these ConstantTime things likely would be) and verified logically. Then, using the type system, that kernel can be used to create an amazing variety of strongly typed systems safely from a compact representation.

In your envisioning of a C ConstantTime library, you would never finish writing the library. If someone wanted to perform date arithmetic, you would have to implement that in your library and check it by hand and monitor it and maintain it. You could never let your guard down on any commit that would touch an ever-expanding body of code that would have to be rigorously checked to handle increasingly complex scenarios.

For example, to implement a constant time big (but fixed size) integer multiplication operation, you would not be able to trust that some other author's composition of your functions is safe purely by its type.

In Haskell I can validate and be sure that I'm using "the proper type" in 100% operations - in C it's hard to verify that there is no code (intentional or accidental) that touches the inside of that struct in some way.

For example, C is full of operations (pointer arithmetic, read from an unbounded array) that may read the inside of that struct without that code mentioning that struct in any way.

In C, sequencing isn't typechecked. In Haskell, it is. Actions must be compatible to be chained together in (what in C would be) a block.

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

> 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?

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.

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

Doesn't Haskell compile first to C and then to native?

Not since GHC 7.0: http://www.haskell.org/ghc/docs/7.4.2/html/users_guide/code-...

http://www.haskell.org/haskellwiki/Calling_Haskell_from_C

I was unaware of that. Looking a bit deeper into it, it looks pretty involved as soon as you want to do something non-trivial with it.

Not in only could be embedded, but also compiled into dynamically linked library.

(Shameless plug) I've collected examples of this here: https://github.com/drdaeman/haskell-library-ffi-example

The nice thing about this example is that you only need GHC to create the shared library, and then GCC can do the rest with just the .so file produced.

Haskell is actually a very fast compiled language. Especially for webservers, where its concurrency shines.

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