Hacker News Reader

"Protocols and constructions should be designed to minimize dependence on randomness, the way DJB's EdDSA does:"

I think a lot of the reason that ECDSA/DSA are so inelegant was that they were designed to get around the patent on the (quite elegant) Schnorr signature algorithm, which EdDSA is based on. Thankfully, the patent expired in 2008, so moving to better signature algorithms that don't rely on per-message randomness is a matter of institutional inertia at this point.

Hmmm… and ElGamal's signing scheme didn't qualify? I don't think that's a reason, or even an excuse: Schnorr actually did claim his patent read on DSA. (That obviously never went anywhere, and the US Government, in a show of force via the NSA, filed their own patent on DSA.)

The NSA also really doesn't seem to have had much of a problem negotiating the licensing of patents with industry participants in the past! It is, after all, in an extraordinarily strong bargaining position: an awful lot of public money to throw around (openly, via on-the-book government contracts, and otherwise); the backing of a 'superpower' government and its negotiators; a remarkably good idea of what the position of those its bargaining with is (it is a signals intelligence agency…!); and is even able to classify patents and other nonsense like that.

DSA was sceptically received at the time, and there was widespread suspicion about its complexity and critical dependency on random k. (Even just two or three predictable leading bits of k can cause disaster!) Sizes above 1024 bit were not specified for way too long, and I would consider a 1024-bit DSA key most definitely crackable by the computing resources available to the NSA (or perhaps anyone else with a budget and a chip fab on contract after-hours!) today. (Those with DSA PGP signing keys may wish to take note and replace them, I suggest, with 4096-bit RSA keys.)

I think perhaps the only reason DSA got any popularity was because of the RSA patent, which it wasn't subject to, and the US cryptographic export restrictions which were the style at the time (remember the PGP source code "type-in listing" book publication?), which DSA avoided ostensibly because you couldn't encrypt with it but mainly because the US Government wanted you to use it. (ElGamal's encryption scheme was commonly used in tandem with it in practice, for example by some PGP versions.)

ECDSA has been accepted in a more sanguine fashion overall, although I'm not sure why that has been. Just like DSA, it definitely works correctly if it's done properly - but one tiny slip and you're toast.

Why was ECDSA better-received than DSA? Time may have helped; so is what they were seen to have done in the meantime. "Suite B-eatification" (as Kevin put it!) I think might've made people a little less sceptical of the NSA's intentions overall; also SHA (which as far as we know is not backdoored and has never been), and (via NIST) their arms-length involvement in reviewing candidates for the AES process. That introduced its "Information Assurance" mission (the one to protect classified US Government data - anyone else's data, or unclassified US Government data, is Not Their Problem). With Suite B, they wanted to be able to use more off-the-peg commercial providers for that purpose (rather than their bespoke, if a bit haute couture weird and distinctly old-looking, in-house stuff, which they referred to by contrast as "Suite A"). And people - perhaps foolishly - trusted that, despite the "equity" tension between their two missions, they would never risk compromising the same encryption systems they'd use for top secret US Government data. (It appears that trust may have been sadly misplaced… and, thanks to Snowden's bold willingness to go on-the-record about their unethical actions, they have permanently destroyed that trust now.)

We can, indeed, do better now, happily. I wonder if we will?

This talk was a fun "thinking-like-the-enemy" thought experiment, interlaced with the kinds of things djb's been generally warning about for years - I think it's up on YouTube somewhere, and like many slides makes more sense with the talk, although I sadly can't find it now (and I recall the audio quality wasn't great).

Along similar lines, someone down below has helpfully pointed out the fantastic "Operation ORCHESTRA" briefing PHK gave at FOSDEM 2014, which is equally funny and pointed. That video is on YouTube: https://youtu.be/fwcl17Q0bpk - http://phk.freebsd.dk/_downloads/FOSDEM_2014.pdf

I'm only 10 minutes into the first youtube vid... holy shit this is the most terrifying thing I've ever seen.

No wonder our patent reform is so broken... literally the government is using it to it's advantage. Screw the cloak and daggers shit when we can just hire some lawyers to bury people and everyone acts like it's common place... wow. WOW WOW WOW.

Ty for this.

In case you weren't in on the memo, it isn't a real NSA briefing. :)

But it could be. Any smart attacker with a budget could work like that…

I found this particular talk to be different that the usual DJB. It felt more like a self-reflection on why, despite being technically correct, his cryptographic solutions always fail to gain mainstream traction.

I have a lot of respect for DJB and for the way he always challenges the status-quo. This talk is an excellent summary of the current issues in the crypto industry. But he ignores the fact that we use AES, SHA and RC4 because _it's easy to use them_. And his solutions are never easy to use.

Make Nacl dead simple to use. Write clients and servers that use it. Integrate it into Firefox, Chrome, Dovecot, Nginx, Postfix, cUrl, etc... and people will slowly move away from TLS and its broken crypto.

Have you seen libsodium [1]? It's a "portable, cross-compilable, installable, packageable fork of NaCl, with a compatible API, and an extended API to improve usability even further." I've been using it in a toy project of mine and so far I'm very impressed!

1. https://github.com/jedisct1/libsodium

In practice, people are afraid to use libsodium because it was significantly worked on by people other than DJB, and they weren't sure whether it was vetted by DJB. I've personally seen this as an actual reason for avoiding it. And the concern doesn't seem entirely misplaced.

But why? Would you be afraid to use libreSSL, because the AES implementation wasn't done by Rijmen and Daemon (inventors of AES)? Generally one feature of the Bernstein designs are that they are reasonable simple to implement securely for a competent programmer. By comparison, RSA and the likes are frigging hard to get right because of side channel attacks [1].

[1] http://www.tau.ac.il/~tromer/acoustic/

No, you're missing something. Nacl isn't secure merely because it implements trustworthy algorithms that its authors themselves design. It's secure because it was designed from the ground up to be secure at an implementation level, and (critically) to be misuse-resistant. Equally importantly, the implementation was done by people with a pedigree in building secure misuse-resistant crypto.

Sodium (which I like and recommend) can't make the same claim. It gets what trustworthiness it has from the fact that it's a slavish fork of Nacl that merely aims to make it compatible with more runtimes.

> It's secure because it was designed from the ground up to be secure at an implementation level, and (critically) to be misuse-resistant.

Ok, interesting. Do you happen to have an example at hand? I don't see where there is room left for much sophistication in the implementation (regarding misuse-resistance), between the well defined algorithms and the strict API that Sodium shares with NaCl. For example lets look at crypto_box (public-key authenticated encryption):

On the crypto side it uses Curve25519 (alias X25519). Its paper has a pretty clear definition how to use the public key bytes as an x-coordinate. Because of the Montgomery multiplication an implementation does not have to calculate the y-coordinate, this eliminates one potential error source. Because of (1) its twist security and because (2) any input in a small subgroup results in a zero element output (neutral element or the (0,0) point), an implementation does not have to check the public key for its validity (another error source eliminated). All these are benefits any implementation will have.

On the interface side crypto_box is as locked down as a nonce based design can be. You enter: (•) Any 32 byte public key value (X25519 makes sure no harm can be done with malicious values), (•) your 32 bytes private key (not malleable by the attacker), (•) the nonce (during decryption any input is ok, because a wrong input will just generate an authentication error; during encryption there is the danger of nonce reuse, which is also present in NaCl) and (•) the plaintext / crypttext (again, because of the mandatory authentication any malicious ciphertext input will be rejected by the library).

So I don't see how a faithful implementation of the interface and algorithm specifications can get much wrong regarding misuse-resistance. Regarding it being secure because it was designed from the ground up to be secure at an implementation level, that is something I expect from any cryptography library. After all, is there any more basic requirement than that? (Well, you could argue being interoperable with other implementations is the most fundamental requirement, but I won't accept such low expectations when I'm asking for a competent developer.)

> It gets what trustworthiness it has from the fact that it's a slavish fork of Nacl that merely aims to make it compatible with more runtimes.

I fully agree that its inheritance from NaCl is Sodiums strongest selling point and its the argument I should have been using instead. I only had it dimly in the back of my heat at that time, though, and wasn't sure enough about it to claim it as a fact. Being less lazy to look it up would have saved me this follow up post ;) (Though I am genuinely interested in my question above.)

I feel bad that I don't have a good response to this comment right when the thread got usefully technical (but maybe 'pbsd will jump in and correct me on something). The fact is that I like libsodium and do not actually believe that the port itself introduced problems --- although I'd be a little concerned about any additional crypto functionality they ever introduced.

I'm just saying: I wouldn't trust libressl if Vincent Rijmen wrote it. :)

I only arrived late here; the thread is already too large to do any proper pedantry.

I like libsodium. It demonstrates that usable packaging is important, something that DJB seems to either ignore or not understand. But I only endorse libsodium as long as you stick to the NaCl API and not the stuff it's been slowly piling on, which may or may not be OK. What it certainly does is make choosing which function to use a lot harder: do I use crypto_secretbox or crypto_aead? crypto_hash, crypto_generichash, or crypto_shorthash? crypto_auth or crypto_generichash?

One response: timing attacks. DJB is one of the most knowledgeable researchers on side-channel attacks, and he leverages this knowledge when both designing _and_ implementing his algorithms.

True, but that is a common (though difficult) requirement of well written crypto libraries and not directly related to misuse-resistance.

Too bad. But thanks for your reply anyway :)

As well as being the author of the algorithms in NaCl, djb is also a specialist in secure software development, as tptacek mentioned.

You can be reasonably sure that his code is bug free, but they went the extra step of proving the absence of certain types of bugs using static analysis tools. One of the project's deliverables mentioned they used Frama-C to prove the absence of integer overflows, for example. (I will update this comment when I find the specific report.)

Other projects take the traditional approach of trusting that the code looks right until someone proves otherwise.

Edit: The report was probably one of these, which I can't access anymore:

http://www.cace-project.eu/downloads/deliverables-y1/CACE_D5... http://www.cace-project.eu/downloads/deliverables-y1/CACE_M5... http://www.cace-project.eu/downloads/deliverables-y3/31_CACE...

All the deliverables are accessible here [1], and from the most relevant one (D5.4) the short story seems to be:

- The core library's memory safety was verified using VCC; - A Frama-C plugin was used to verify (a limited form of) side-channel resistance.

Correctness verification seems to have been done by reimplementing NaCl in CAO, a language made during CACE for this purpose. It is not a 1:1 match to C, from what I can tell, so this does not imply correctness of the C code.

However, none of this is verifiable at all. The NaCl code has no VCC or Frama-C annotations, or associated CAO; there is absolutely no mention of this in the NaCl page. So we are forced to take the authors of that report at their word, if we want to believe them at all.

[1] https://www.cspforum.eu/documents-reports/description/cace

I must say, as a non-participant, I am slightly disappointed in how the deliverables of the CACE project were handled.

Nevertheless, one thing that is “left” from the verification effort is hidden options -experimental-mem-deps and -experimental-path-deps for Frama-C. These are on the automatic side of Frama-C analyses: they require a value analysis to pass on the target code, but they do not require it to be precise. And it is fun to see input length and error conditions pop up as things the execution time depend on (and in the case of a typical AES implementation, the input buffer itself):

http://blog.frama-c.com/index.php?post/2011/12/31/Do-not-use...

Sounds like DJB's job could get much easier if he adopts Rusts once it's stable.

This is like a comment from a Markov generator.

How about an inversion of the Turing Test, where human contestants try to convince judges they are a Markov generator? Since it's difficult for people to generate randomness, this should be challenging enough to be interesting. (Not claiming it's intellectually interesting to participate in, however.)

I can name a couple credible contestants from this site (obviously, if there was an Asshole Test, there'd be no question who'd win it from HN).

Would that me positively or negatively correlated with karma? ;)

Isn't misuse-resistance a property of the interface alone and doesn't it consequently transfer to libsodium? No argument on the other counts.

A community should raise money to have libsodium audited by professional crypto auditors. I'm not sure appealing to the ease of implementing DJB's theories is a good idea given how screwed up a lot of the crypto in the field actually is.

All I'm saying is, in general, crypto is hard, and an easy theory doesn't change how hard it is to get an implementation exactly right.

I don't think this is a great use of crypto auditor time, for what it's worth. Microsoft SecureChannel, Truecrypt, libOTR, GnuPG, PHP mcrypt --- all much more important audit targets.

Ah, good point.

GnuPG hasn't been audited? Huh.

Is that because of those projects being more widespread or less innately trustworthy or both?

Little of both, depending on the project.

No, I'm afraid to use LibreSSL because the AES implementation wasn't done by Dan Bernstein. The issue is not so much with using algorithm implementations implemented by the algorithm designer as with using algorithm implementations implemented by somebody who knows how to program.

In this particular case, there is the issue that the AES implementation in OpenSSL has been shown in the past to be vulnerable to timing side-channel attacks over the network (again, by Dan Bernstein) and as far as I know has not been through the complete overhaul necessary to fix that problem.

I wouldn't be at all surprised if someone found exploitable side-channel attacks in third-party implementations of Salsa20 or ChaCha in the next few years.

TweetNacl was written by DJB, and implements the same primitives. It's a nearly drop in replacement.

TweetNaCl (http://tweetnacl.cr.yp.to/software.html) is dead easy use - just drop the .c & .h files into your code.

Well, it might be dead easy to drop into your code, but that doesn't make it dead easy to use. In fact, it has no documentation (at least not on the page you linked to), so the only way to actually use it is to reverse-engineer it.

I'm a big fan of DJB, but the sad fact of the matter is that his stuff is, at the moment, only usable by people who already know what they are doing.

The documentation is on the NaCl site which is linked: they are compatible.

True, but to get to the docs you have to go through three levels of indirection (Introduction -> NaCl -> one of the nine documentation links on the left) and the docs are not exactly beginner friendly. TweetNaCL is a huge advance in usability over full NaCl (which is a freakin' nightmare) but I still say it needs some better documentation if it's going to be usable by anyone who isn't already an expert.

In most cases you only need a handful of functions - crypto_box_keypair/crypto_box/crypto_box_open for public key crypto and crypto_secretbox/crypto_secretbox_open for private key crypto. It is way simpler than any other crypt library I have used.

Awesome! But that information needs to be on the TNaCL web page, not in an HN comment.

It's a terrible piece of self reflection in that case. His thesis is his stuff never got adopted because of the NSA? DJB is very smart, but he doesn't necessarily play well with others (as tptacek alluded to) and sometimes does some odd things.

As a random example: Nacl, which is pretty good, isn't portable. The portable version that someone made, Sodium ripped out a bunch of the platform specific stuff to make it portable, but because no one knows which parts were security critical and which weren't,there more than some doubts. These kind of things matter.

Put another way, as a piece of self reflection at least he could figure out how to make it harder for the NSA to marginalize his ideas if that's really the reason they haven't been adopted.

It isn't self-reflection. It's a talk he gave to an audience that puts his research into a current events context and provides a backhanded roadmap to the kinds of crypto research topics that are important to the project of securing the Internet against the NSA. As that, it's pretty effective.

It's pretty hard to make a credible argument that Bernstein and Schwabe and Lange did a poor job with Nacl, since the next best alternative is Keyczar, which might not even be maintained anymore. What's the other credible high-level crypto library?

Gutmann's cryptlib (if you stick to the high-level API, which is documented as such).

It's "anciently conservative" (not based on fancy new ciphers, you can like it or not), by a competent cryptographer, and battle-tested.

There aren't. Nacl certainly is credible. But it isn't (at least last time I looked) portable. As I understand this is because of a bunch of x86 assembly meant to generate very fast and constant time crypto code.

This is Bernstein's entire stick. Which is fine, but if you can't use it on ARM and therefor on mobile, you've killed a large area where adoption of new crypto could actually happen. Arguably, a slower constant time cross platform library would have been a better idea if he actually wanted to see it used widely. This is what Sodium claims to be ....but well who knows if that's secure.

And I don't think I agree with you that this is Bernstein merely saying here's why you need what I've done. It's an explanation of why it didn't happen that basically argues that people' are being so stupid about crypto that they might as well be NSA shills. As a narrative it ignores a lot of reasons this stuff didn't happen and a lot of lessons that should be applied in getting it right this time.

Virtually none of the ideas that Bernstein talks about in here have anything to do with people adopting his implementations. Bernstein's packaging isn't why TLS uses PKCS1v15. It's not why elliptic curve signatures almost always require random ephemeral keys. It's not why userland programs scatter broken RNGs throughout their codebases instead of just tapping urandom. It's certainly not why the most popular modern cipher is one that requires either modern Intel hardware or side channel leaks to be performant.

It's also worth remembering that Bernstein has this reputation you're alluding to among Unix nerds. In cryptography, he has no such stigma; he's a world-class cryptographer and I can't find any indication of interpersonal DJB drama in that field at all. I'm almost inclined to attribute the problem to the Unix nerds.

NaCl includes portable C implementations of all its operations, but it's possible that they might not be constant-time on a given compiler. SUPERCOP now has ARM assembly implementations of the NaCl operations (contributed by Peter Schwabe), but they haven't been integrated into a NaCl release yet.

Schwabe has even written AVR versions of many of the NaCl operations, so maybe you can do your crypto not only on mobile but on an 8-bit microcontroller.

I think DJB works hard enough and it's a bit much to expect him to not only work on his passions but also figure out how to get his work and ideas adopted. We're all good at some things and not others.

What I'd like to see is a way for others to support his efforts.

How can I, for example, currently working as a software developer working at a reasonably 'high' level (currently I'm mainly a consumer of libraries and frameworks) push for better quality in the crypto that I depend on, knowing that DJB has at least partial answers to some of the problems?

Hey tptacek, I'm CTO at a young zero knowledge email startup, and while I'm a proficient crypto user, I'd like to learn more about security and cryptography in general. Do you have any tips for me? Thanks!

I do! http://cryptopals.com.

I noticed that solutions to Set 1 Challenge 1 in languages other than C++ all 404. Does that mean that no one has contributed solutions? If so, how can I contribute?

They received a ton of solutions in a bunch of different languages when they were running this as a closed competition. They said it would take some time for them to add the solutions to the page, but its been months and I think they have given up on it.

We didn't give up on it! I did, however, leave Matasano to start a new company, and that's slowed us down. We will certainly still be posting solutions.

Another problem is that every time we've talked about posting solutions, people have asked us to hold off.

Finally, a quick jab: thousands and thousands of people completed several sets of these challenges --- more than a thousand got through the CBC padding oracle, which (in our challenge) is cryptographically more complicated than the TLS POODLE attack. None of them had solutions. You don't need them either. :)

I thought 1.6 (repeating-key xor) was the hardest one prior to set 6 and I'm guessing many thousands made it through that one!

Set #7 is much harder than #6. And there're rumors about set #8 which has attacks on EC-algos.

Set #6 is also much harder than set #5! Or at least, I thought so, but I haven't finished it or, sadly, worked on it for quite a few months.

We know what the 8 challenges are, but we have to do the work of getting good reproducible challenges worked out for them.

Thank you!

Try this "Crypto I" course

    https://www.coursera.org/course/crypto

Also Udacity has "Applied Cryptography"[1].

While coursera focuses on theory, it is a bit more practical. I'd say they complement each other nicely.

[1] https://www.udacity.com/course/cs387

Thanks, will do!

One of the points he makes is that "if it's standardized then it's broken. So if we were to take his words to the letter, we should be worried at the current work of standardizing Chacha20-Poly1305 into TLS 1.3 (https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-0...) and assume it's somehow broken ?

No.

Your comment could be read as saying that these slides are self-promotional — that is, that they are intended to puff up the importance of the topics that Bernstein has happened to publish work on. A more charitable and accurate reading is that these slides explain why he believed and still believes that those topics were important to spend time on, and why people should do things differently now. (That explains the lack of emphasis on RC4: everybody already knows RC4 is broken.)

I believe the latter, for what it's worth, not the former.

> Application-layer randomness is a bad idea, and, like Nacl does, everyone should just use a single, carefully audit kernel RNG

In Linux we already have this with /dev/random, right?

Yes, modulo "carefully audited", but the problem isn't that it's not possible; the problem is that so few applications rely on it, and that there's folklore encouraging people not to use it.

http://sockpuppet.org/blog/2014/02/25/safely-generate-random...

Are you saying that that article is wrong? I was under the impression that /dev/random and /dev/urandom on Linux were exactly the same thing, but with urandom not being limited by the (very questionable) entropy counter.

I'm pretty sure they are exactly the same on many of the BSDs.

The thing is, /dev/urandom is not even limited by the entropy counter when there is no entropy in the system at all. That was the reason for the RSA factor collisions: The software just used /dev/urandom during boot time when the embedded systems did not have enough entropy available. As a remedy the libreSSL team asked for a Linux syscall with the feature to block if and only if the random pool has not been seeded with at least 128bit of randomness: https://news.ycombinator.com/item?id=8049180

That's a Linux bug with a universally-deployed userland workaround. There's no question that urandom should work on Linux the way it does on FreeBSD, but that's not a reason to avoid urandom in userland software. The death toll from avoidance of urandom is enormous; the death toll from this bug... isn't.

I would say it was both a Linux and a application bug, you could just open an fd on both random and fallback onto urandom or even better supplement random with a prng such as haveged.

"Supplementing" random(4) with a userspace PRNG is exactly the anti-pattern that Bernstein is talking about.

I'm pretty sure they are exactly the same on many of the BSDs.

* OpenBSD: /dev/random + /dev/urandom are the same and use ChaCha20.

* FreeBSD: They are the same (via symlink) and use RC4. Soon will use ChaCha20.

* NetBSD: Unsure. Last I checked, /dev/random was broken/non-functional like on Linux, and /dev/urandom was slow, like on Linux.

* Dragonfly BSD: Somewhat unsure, but ChaCha output can be xor'd with another stream to produce the returned random numbers.

* Bitrig: when it is released, it will use ChaCha20 like OpenBSD.

Related: libbsd currently uses RC4 in its arc4random functions but has publicly stated a future switch to ChaCha20.

I wrote that article, so, no.

if /dev/random decides that it has not not enough entropy sources then reading from it blocks - sometimes it blocks for a minute if the machine has few entropy sources (for example no mouse and no keyboard attached)

That's why most libraries use /dev/random to seed their own RNG, he says that's wrong and that /dev/urandom (which does not block) is scary.

Usually libraries (openssl,JCE) RNG seeds from /dev/random - this is the internal state of the RNGb; internal state is transformed into next iteration by applying SHA-1 and at each turn some initial bits of internal state are returned as random numbers.

of course the library RNG comes from the requirement for a lot of randomness in most protocols, (and for predictable performance, also servers also may need to do a lot of random numbers) of course the article has many points.

Seeding a userspace RNG with /dev/random is exactly the anti-pattern Bernstein is talking about. It's what broke the Android RNG. Don't do that. Just use urandom.

There's a comment about /dev/random and /dev/urandom later at the article.

TLDR - they are broken. He does not even care to explain why it's broken, because everybody knows it.