How I implemented my own crypto

http://www.urbandictionary.com/define.php?term=table%20stake...

So this old movie cliché where the protagonist has lost almost all his chips and needs a huge win, so he casually throws in his car keys and the title to his house in the middle of play is not allowed. Neither is grabbing your wallet and throwing cash in.

The idea is that (a) rich people cannot bully others around at will with their huge wealth "in the background" and also (b) players are protected from losing possessions extraneous to the game.

(business) minimum entry requirement for a market or business arrangement OR (poker) limit on the amount a player can win or lose in the play of a single hand [1]

[1] https://en.wikipedia.org/wiki/Table_stakes

There are programs that teach this, but they take years. Nobody who's passed through that is interested in creating an easy scaffolding whose levels are unclear.

The crypto community has repeatedly been burned by overeager beginners with false senses of competence making rather nasty mistakes. Consequences can be dire, from destroying companies to getting people killed. On the lighter end, you have things like Decrytocat.

In some arenas, it's appropriate and a good practice to assume that everyone reading is a beginner who needs 101-level info on everything. Webdev is a good example - CSS, or cascading style sheets, are good for handling the display logic of semantic markup. The stakes are low and the costs for screwing up trivial. With cryptography, it needs to be driven home to the idle reader that this is serious stuff.

Bignum is what you need when you have one number that you're splitting between multiple variables (because it's a 256-bit number, and you want your library to work on 32-bit PCs, for example).

Carry propagation is if part of your result is too large for one part of your number and needs to overflow into the next part.

Actual carry propagation bug and bugfix available here: https://news.ycombinator.com/item?id=8857363

Sean, Marcin, and I spent the better part of a year individually replying to tens of thousands of emails from people doing the Cryptopals challenges that we wrote and published for free. Do you know how much work that was? Here's a hint: it was a lot of work.

There are a lot of charges you can level at me to try to win a dumb message board argument, but the one where I want cryptography to be a secret priesthood known only to the anointed select is not one of them --- nor is the argument that I haven't taken the time to help make these kinds of cryptographic attacks easier for people to learn about.

Please immediately find one of those other arguments to substitute for this one, and, if you have it in you, take a moment to retract.

Thanks in advance.

And yes, I believe I'm talking about a more complicated class of bugs than you are. For instance: OpenSSL's algorithm implementations pass test vectors (OpenSSL is FIPS certified, too). But OpenSSL has had recent carry propagation bugs.

I am not concerned about your use of C, or about the presence of memory corruption bugs in your library. If I was going to harp on about that, I'd also have to go after everyone who's written a Markdown library. My concern is that the kinds of things you say you've done to ensure the security of your cryptography don't address real cryptographic vulnerabilities.

You may have done other things and I just haven't read about them! I don't really care about your library one way or the other; the only thing I care about is the idea that if you pass test vectors and Valgrind is OK with your binary, you're probably OK. No!

"Almost certainly you will get the urge to invent new cryptographic algorithms, and will believe that they are unbreakable. Don't resist the urge; this is one of the fun parts. But resist the belief; almost certainly your creations will be breakable, and almost certainly no one will spend the time breaking them for you. You can break them yourself as you get better."[1]

The problem that Schneier is referring to is that doing a careful analysis (that is required if you want to use your crypto in production) is tedious, time consuming, and requires expertise in the area to know most blank spots of the algorithms (heck a single one is hard enough). That's why he recommends you to be have enough experience breaking many algorithms before you make any serious claim about your the safety of your crypto.

So all in all it's great that you got the interest in the area, there is a lot of work needed in OSS. But be very careful about claiming that your lib is ready for production. What you got is a bunch of volunteers to glance at your code. Few cryptographers (if any) will seriously try to break it.

[1] https://www.schneier.com/crypto-gram/archives/1999/1015.html...

On the contrary, this is -exactly- why you don't want to roll your own crypto. Because they can and will break it. Good crypto takes serious thought and effort from people who put a lot of thought and effort into it.

> Take a look at so-called 'professional' cryptographers and their libraries, and you'll find that practically all of their code had severe bugs. Professionals make errors like everyone else, 'professional' just means you're being paid for it. You will have a hard time finding a professional and widely used crypto library that wasn't essentially compromised in one of its functions at one time or another. Not only that, professionals from the closed-source department have a long history of coming up with compromised or bogus, sometimes even ridiculous cryptographic algorithms and implementations. Two typical examples: CMEA cell phone encryption, and the Crypto AG backdoor debacle.

This doesn't diminish the claim that the modal individual should not attempt to "roll their own crypto." You're pointing out that professionals make mistakes, but of course they do - that indicates nothing about the propensity for amateurs to make mistakes.

> It requires about the same level of skill as e.g. implementing a production-ready low-level network protocol or a file system.

I have never implemented a low level network protocol or a file system (although at least the former sounds like a fun project) - so I cannot claim you're wrong here. However, I will point out that a network protocol is not designed to be error-proof in an intentionally antagonistic environment, which is a difficulty unique to cryptographic software. There are incentives involved in breaking crypto code that do not present themselves in other areas of software development, even if the programming difficulty itself is not entirely dissimilar.

> Last but not least, many popular and widely used crypto libraries started as a side hobby. For example, libtomcrypt started that way. In fact, many widely respected cryptographers started as hobbyists. For example, Bruce Schneier. Of course, the ones who are widely accepted as peers are also those who are in the 'hire me as a consultant, not the other guy' business, and they will naturally advise everyone to not roll their own crypto but to rely on their expertise...

They can start as side hobbies, but they are not going to remain that way for any meaningful amount of time if they are to be widely deployed and safe. You can only choose two out of those three.

More importantly, there is no cabal of cryptographers spreading FUD to line their own pockets with consulting fees. The cryptography consulting industry is very small compared to the actual security consulting industry. In the application security consulting industry I do believe there are firms that try to secure business this way, but that industry is much larger (and has firms which try to misrepresent cryptographic competency). I have had significant interactions with engineers at Riscure and NCC Crypto, which is a sizable portion of all the "real" cryptanalytic consulting work that occurs (at least in the United States) - they never struck me as being the sort to suggest what you're saying. That leaves Rambus/CR and a select few other firms doing real crypto consulting, which leads me to believe the industry is, on the whole, very legitimate.

Sidenote: how we started these things historically is not relevant anymore. We have learned a lot since then. Failing to "stand on the shoulders of giants" and learn from history is one the biggest factors that makes home-rolled crypto so easy to break - they are doomed to repeat the mistakes of history. Mistakes that are nowadays well documented and well known.

Rolling a usable crypto library is not a single person endeavor. Your own crypto won't be peer reviewed, thus you should not trust it.

You're right that the code written by professionals has lots of bugs. Bug is a term that describes a problem in code that has been found. With crypto software, the danger isn't the problems that get found (and then addressed), it's the problems that aren't found. "Roll your own" solutions have problems that never get found. That's the danger and it has nothing to do with the skill of the programmer.

This cowboy-programming attitude being extended to security is no small part of why we are so vulnerable as a society to attacks on our computer systems that can compromise our core infrastructure[1], our secrets[2], and our economic security[3].

[1] Think weeks-long country-wide power outages

[2] Think juicy blackmail material on anyone with their hands on levers of power. Look at the damage that North Korea's attacks did to Sony Pictures, for example.

[3] Think small-scale attacks on services that even a single major company, or many small companies, rely on.

No, you really can't, unless you stretch the definition of "side-hobby" to the point of breaking at the seams. I'd be shocked if a single person who professionally works in security or cryptography is going to agree with you in this thread. You need far more than a "little care" to assure that a new cryptographic library is safe. It's an endeavor suited to a collaborative academic or corporate environment, with robust human capital and strong oversight.

I'm willing to accept that someone can safely implement a primitive or a construction in a new library with significant time, effort and feedback from others. But that level of effort doesn't really qualify as a side-hobby, and until the implementation was formally checked by professional cryptographers I'd consider it suspect.

This is to say nothing of designing novel primitives or constructions, which I would consider as far removed from a "side-hobby" as a local 5K is to the Olympics.

However, I absolutely think people should attempt to implement their own cryptography if they're curious about it and want to learn. Just don't use it in production and assume it's unsafe. People who work in the industry don't make these claims because we think it's fun, we do it because we've all seen the consequences.

GCHQ loves people who think this.

Have a look at some of the game console cryptography. These are companies with strong financial incentive to get it right. They're large well funded multinational organisations. They still get it wrong.

Something that is, in some sense, truly portable is one that has a single specification that runs on all platforms the base implementation supports. Virtual machines and certain styles of language standard are often able to accomplish portability for a vast number of applications.

C is meant to map easily to a wide range of hardware without overhead, conceptually it's almost the opposite of portability since it precludes creating standard abstractions that would hold true across architectures as those could not map to native functionality across the board.

It's easy to compile C programs on a different architecture however, which is probably where this argument stems from. Remember when we switched from 32 to 64bits? How many codebases managed to make the jump painlessly?

The sort of direct control one might look for is, as far as I know, only practically found in your processor's assembly language, and your operating system's collection of syscalls.

I think Rust, Common Lisp, OCaml, D, Haskell, and other languages give you a lot of benefits that are simply not worth giving up in a new crypto library, like safety.

The ANSI C and C++ standards define the concept of abstract machine for the language semantics, just like in most languages.

Additionally you have the concepts of sequence points, the new memory model semantics for multi-threaded code and the beloved UB.

UB which doesn't exist in most languages, because their rather leave it implementation defined or lose the opportunity to target some strange CPU not able to support the language semantics.

Also Assembly doesn't has UB, making it ironic that it is safer to write straight Assembly at the expense of portability than C or C derived languages.

Edit: Sorry, wrote this too hastily and want to put it in perspective. While Ada is well-suited for cryptography and has some good implementations, it is probably not as secure as C crypto libraries in practice. The reason is that the implementations I know don't do OS-specific things like locking memory or preventing core dumps, and doing this in Ada is a bit harder than in C.

If you're curious, check this out: https://doc.rust-lang.org/1.5.0/book/ffi.html

> I would totally recommend to rewrite the whole thing in Rust for Rust projects, though.

Any time you rewrite anything, you run the risk of introducing new and unexpected bugs, and you're just doing unnecessary, complex work fraught with pitfalls (doubly so here) -- generally a Rust project would create a wrapper around the C code, invoke the methods and expose idiomatic APIs on top to avoid just that.

This is my go-to article on re-writing things and why not to: https://www.joelonsoftware.com/2000/04/06/things-you-should-...

To be clear I'm not saying you made a mis-step, just that your arguments for it don't seem at first glance to support your decision.

Yeah, you don't even need a new, hip language to avoid C's pitfalls.

> Portability does not equal 'without blemishes'. It simply means that when compiled across platforms it will perform as expected.

By that measure, C is not portable, since it will behave differently across multiple platforms – or multiple compilers, multiple compiler versions, even multiple optimization settings.

But from a rather philosophical point of view, C is basically Portability 1.0, it was one of the first truly portable "fast" languages. I'd like to think that we could do better than C with 40 years or CS research and industry experience.

Of course, there's the whole second-system syndrome so it's a wicked problem :)

Daniel Bernstein, Daniel Bleichenbacher, Dan Boneh and Thomas Pornin are professional cryptographers and world-renowned experts. Even I would feel comfortable writing crypto if Bleichenbacher was watching behind my back.

Frank "wrote" libsodium, but libsodium is effectively a port of NaCl. Frank had Daniel Bernstein watching behind his back.

Eric Young wrote OpenSSL. Look how that turned out! Has there been a class of cryptographic vulnerability that OpenSSL hasn't had?

And yet consider: for all the effort that people like Bernstein and Boneh put into writing strong, safe crypto, the entire world has blundered into vulnerability after vulnerability because the amateurish crypto in OpenSSL is the one every else ended up using.

It's as if you set out to prove my point.

Finally: you obviously know that "writing your own crypto" isn't the only way to become good at it. In fact, it's a terrible way to get good at it. The right way to get good at crypto is to learn how to break it. But that takes effort, and you can have a blog post crowing about your new crypto library just a few weeks after deciding to write one.

NaCl does not use autoconf nor even make.

It is not necessary but if someone really feels compelled to use it, why stop them?

I have never seen any author or end user comment that they dislike using autoconf, or write alternatives to it. Autoconf is loved by all, isn't it?

I think what you could say is that using NaCl in your own software is the only way to get good at using it. Maybe the existence of libsodium means that more developers will have a go at using NaCl? Is it easier to use than an SSL library? The only way to find out is to try both and compare.

There is no need to use autoconf to build libnacl.a. The original build system for NaCl is beautifully simple. But if someone misses autoconf and make, then libsodium has added in those dependencies.

More projects using NaCl:

http://ianix.com

As far as I can tell, the authors listed on the above site are not "rolling their own crypto" for their projects, they are using cryptography written by the author of NaCl.

Personal bias disclosure: I find NaCl easier to use than all the SSL libraries I have tried. If I am not mistaken, I believe this was a design goal by the author.

[1]: https://github.com/LoupVaillant/Monocypher/blob/master/src/m...

To see the difference, you need to first modify the makefile to use UBSan instead of just GCC (just comment the active CC line, and uncomment the right one). You may want to tone down the optimisations for faster compilation as well. Then you can run `make clean` and `./test.sh`. You should have a warning on commits prior to this patch.

  #include <stddef.h>
  #include <inttypes.h>
  
  int main(int argc, char **argv)
  {
  	uint8_t msg[] = { 255 };
  	size_t i = 0;
  	size_t c_index = 255;
  	return msg[i] << ((c_index % 4) * 8);
  }

  runtime error: left shift of 255 by 24 places cannot be represented in type 'int'

Your example is different, this is because you're doing an addition. I can see how this could be a problem if you want to do a rotation (a << 4) + (a >> 60) and hence why you should use a ^ instead of a + here (example: https://github.com/gvanas/KeccakCodePackage/blob/master/SnP/... )

  #include <stdio.h>
  #include <stdint.h>

  int main(){

    uint8_t start = -1;
    printf("%x\n", start); // prints 0xff
    uint64_t result = start << 24;
    printf("%llx\n", result); // should print 00000000ff000000, but will print ffffffffff000000
    result = (uint64_t)start << 24;
    printf("%llx\n", result); // prints 00000000ff000000
    return 0;
  }

u64 = u8 << 24

Here the integer promotion might transform u8 into a 16-bit or 32-bit int (depending on the arch). Which will then be converted to a u64 AFTER the shift. Which might have you lose half or more of the bits.

His code is not that though, it's

u32 = u8 << 24

which should work only if ints are 32-bit on the system you compile on.

Verifying some (but not all) properties of crypto is relatively (but not absolutely) easy, because it's essentially just math with pure functions. Operating systems and physical controllers with real-time constraints have different requirements and more interacting state, which means that the desired properties are not easily expressed as a mathematical expression.

The thing about the "don't roll your own" advice is it's aimed at people who don't competently know what they're doing rather than those who do.

https://en.wikipedia.org/wiki/Franz_Reichelt

EDIT: Some interesting discussion here: http://www.dropzone.com/cgi-bin/forum/gforum.cgi?post=482241...

On a first read I though "yeah, sure, looks quite dangerous indeed", then I read:

Sylvester H. Roper, inventor of the eponymous steam-powered bicycle, died of a heart attack or subsequent crash during a public speed trial in 1896. It is unknown whether the crash caused the heart attack or vice versa.