[Hypothetical] Keybase.io has received an NSL

[ghost]

Note: this is a fabricated, fake AP article. When reading it, you might want to pretend it's real. The nature of an NSL is that we can never know whether or when Keybase has received one.

By THE ASSOCIATED PRESS Feb 13, 2016, 6:07 P.M. E.D.T.

NYC - Anonymous sources close to Keybase, the U.S. based company that democratized private communication for the masses, allege that the company received a National Security Letter (NSL) sometime last week. When asked to comment we received no response from Keybase. Not that they could respond without breaking the law; the NSL includes a lifetime gag order preventing them from disclosing details about the letter or any cooperation with the NSA to expose customers' private communication.

"Assuming it's true, Chris and Max have one tough decision ahead of them," says Ladar Levison. "They can comply with the letter, betray their users, and become complicit with the unconstitutional surveillance of our citizens. Or they stand up for their customers and shutter the Keybase service." Mr. Levison is no stranger to this dilemma; in May 2014 he abruptly shut down his secure email service after, it is speculated, he received his own NSL.

Mathew Greene, cryptographic researcher at Johns Hopkins, warns that the damage for some users could go beyond the confines of Keybase. "The lynchpin of private communication is your so-called secret key. Given the nature of Keybase customers, and the benefits of doing so, I speculate most customers host their keys on Keybase servers."

The impact is broader than it initially seems. "Some customers will have used the same key with similar services," continues Prof. Greene, "such as Google's end-to-end Gmail privacy extension or Facebook Messenger." By coercing Keybase to divulge customers' keys, the NSA can listen in on messages originating from Keybase or any of the services sharing the same key.

"If this news is true, the sensible thing is to switch out your keys and discontinue using Keybase. Unfortunately your past messages may still be exposed." Experts speculate that the NSA retains copies of encrypted messages, awaiting a time when breaking into the messages is technologically feasible or they get ahold of the keys to unlock them.

The NSA must clear one last hurdle: guessing the password on your key. But recent studies show anywhere from 40% to 83% of passwords can be guessed in under a day with commodity hardware and widely available software. "The NSA's capabilities will be no worse than that, almost certainly better," says Greene.

Does it matter if the allegations are true? According to cryptographer Bruce Schneier, "it's logical to assume Keybase was commandeered months ago, if not as early as 2014. If they haven't been commandeered yet, they will be." Schneier points out the most expedient protection is to never upload your secret key to Keybase. But he adds, "regardless of your precautions, the safest course is to believe everyone else entrusts Keybase with their secret key and by extension has entrusted it with the NSA."

Which defeats the purpose, or so it would seem.

[zQueal]

Even if this is true, Max and Chris would be legally unable to answer--however, this is the exact situation for which we requested a small graphic in which to notify users of such an event.

Although the article brings up some amazingly relevant points:

[...] regardless of your precautions, the safest course is to believe everyone else entrusts Keybase with their secret key and by extension has entrusted it with the NSA.

For now, I'll have to fall back to my motto; If you want it to stay a secret, keep it away from the Internet.

[ghost]

If you want it to stay a secret, keep it away from the Internet.

That seems like an unproductive, defeatist stance. There are many reasons to pursue widespread adoption of encrypted communication. One of those is that it makes passive surveillance harder. We know from the Snowden leaks that targeted intrusions are uncommon relative to passive surveillance. There's a lot to be gained even if the maxim holds that if the NSA (or similar actor) wants in to your stuff, they're in.

There's an attitude in the security world, which is that no crypto is better than bad crypto. This makes sense, of course! But convenient crypto...which still works? I'd rather people used that than nothing, and I think we can make this usable for something like half the population. - @malgorithms #166

I laud the goal of improving crypto usability. I worry that bearing that flag, keybase is justifying design choices that lead to poor security for their target market. I find it akin to offering a highly usable and appealing climbing harness that has weaknesses known only to expert climbers; non-experts using the harness will take unwarranted risks because they've been mislead into believing the harness is effective. In this case, having no harness is better.

I've seen similar criticisms swept away with a dismissive, "ahh, you security nuts..." kind of tone.

It does seem to me that there's a contingent here who given their druthers would have keybase morph into the PGP status quo. I side with Chris and Max in their mission to do it a bit different, challenging assumptions, introducing innovative ideas. The world has changed since PGP, key servers, and the WoT first emerged. In the context of wider adoption, identity proofs stand a much better chance of succeeding than the current WoT model, for example.

But not every critic here is a dissident. I consider myself an ally, but I'm concerned that voicing an objection to private key hosting, for instance, gets my bozo bit flipped. Also, the current party-line, "we know experts like you won't upload your private key," really miss the point. I'm not just worried about my security, I'm worried about the security of keybase's target market. Also, as eluded to in the fictional article, so long as keybase allows customers to make choices that are bad for security, I have to assume everyone else but me has done so, which substantially weakens the trust I can put into communication facilitated by keybase.

---

I think 1Password can be a source of inspiration, including a novel approach to browser crypto without performing crypto in the browser (or browser extension):

• uses AES
• AgileBits is reticent to offer their own keychain hosting service so that they cannot be compelled to betray their customers
• recently moved all crypto out of the browser extensions by creating a native app (1Password mini) which performs crypto and keychain activities
• minimal, UI-less browser extension responsible for analyzing web forms which delegates to 1Password mini native app for UI, crypto, and keychain functionality
• separation of concerns

Imagining a similar "Keybase Mini" in the menubar/taskbar/notification-applet, it would:

• provide a UI for functionality that currently is only available to users with the keybase CLI
• pair with a Keybase browser extension to power features on keybase.io that currently require that the user's private key be hosted on the server and that encryption be performed in the browser
• be a P2P client/server for securely transferring the private key to trusted devices

It's more complicated than performing everything on keybase.io, but I believe 1Password, Dropbox, et al have shown simple, well designed native helpers are within most users capabilities to understand and use. This illustrates how holding onto all constraints: democratized, usable, strong, and secure crypto, may lead to a design that satisfies all of them, instead of settling for only some.

[malgorithms]

Hi @toolbear, thanks for all this post. A few clarifying questions on your proposal at the bottom ("Keybase Mini"):

• how are you saying the private key will be relayed from machine to machine? A 1PW model (store in a separate syncing service?) or some kind of integrated P2P filesharing service?
• what are your thoughts on mobile devices and key portability? We are just getting into mobile development these days. But people need their private keys on their phones too.

I promise Max and I are open to suggestions.

Btw, there are two basic kinds of attacks we see when talking about tyrannic compulsion and the portability/syncing of private keys:

1. someone evil holds a gun to keybase's head and makes it hand over encrypted private keys, then works on brute forcing them.
2. someone evil compels keybase to modify its software, either across the board or targeted to an individual.

I'm bringing these up because we should be sensitive to mitigating these attacks while maintaining key portability. People need a way to move their private keys from computer to computer to phone to tablet. This we won't give up on, and it needs to be a usable solution.

Perhaps one could argue Dropbox is more prepared to defend itself against the forced mass seizure of encrypted data. On the other hand, perhaps they care more about their business than the security of its Keybase users.

Oh, last thing! Can I edit the subject of this issue to say [hypohethical] or similar? We have not in fact received an NSL.

[ghost]

@malgorithms, thanks for taking the time to respond. Also apologies: I'm a thorough thinker and writer, but cannot claim brevity as one of my talents.

Can I edit the subject of this issue to say [hypohethical] or similar?

I changed it. I admit it was a little link-baity 😝, but I also had the following point to make: barring a radical shift in U.S. laws, there are two outcomes:

1. Keybase fails and nobody uses it
2. Keybase succeeds and receives an NSL

Your statement "we have not in fact received an NSL" cannot be trusted. You're forbidden from revealing receipt of an NSL. Were you to make routine "no NSL yet" assertions or employ a similar canary (#761), it's probable you would be compelled to keep making those assertions. For instance, Ladar Levison was threatened with prosecution for shuttering Lavabit.

I want Keybase to succeed because I want accessible crypto to succeed. That includes trying to (encourage you to) design a system that works even when Keybase is commandeered. Which, unless someone else has some innovative ideas, needs to be a zero-knowledge system when it comes to private keys.

How are you saying the private key will be relayed from machine to machine? A 1PW model (store in a separate syncing service?) or some kind of integrated P2P filesharing service?

I was meaning P2P. I'm not entirely against independent sync services, but I have more misgivings, elaborated later. Meanwhile, tackling a usable, secure, P2P private key exchange seems like an admirable goal.

I was thinking you could utilize the same identity proofs:

Import private key for "toolbear" from aken.localdomain?
[private key fingerprint]
✔ "toolbear74" on twitter: https://twitter.com/toolbear74/status/490822209569837056
✔ "toolbear" on github: https://gist.github.com/da5c5954036e8ab08ad2

I include mobile devices and USB sticks under the "P2P" umbrella. Probably more accurate to call it decentralized, but that word probably evokes keyserver in the reader's mind.

I acknowledge P2P is unlikely to be as usable or convenient as storing the private key in the cloud, but it's an interesting and useful challenge to see if we can approach that convenience while maintaining better security.

What are your thoughts on mobile devices and key portability? ...people need their private keys on their phones too.

I have my 1Password keychain on my iPhone. I even enabled a pin to unlock it, which is less secure, but more convenient. Important distinction: the app defaults to the more secure mode of operation. The evolution of the 1Password keychain format is a great case study; I reluctantly omit it here for the sake of brevity.

It might seem contradictory that I store my 1Password keychain on Dropbox, yet rail against hosting my private PGP key on keybase.io. Multiple factors are at play, which I can elaborate on, but I think it boils down to playing the odds and the risks of a compromise are lower. Oh, and probably a dose of self-deception out of expedience.

---

The next two topics assume compulsion. I'll point out that the "bad guys" might attack and subvert Keybase without your knowledge. Beyond complicity, they are essentially the same.

Makes [keybase] hand over encrypted private keys, then works on brute forcing them.

Yes. Agilebit's Jeffrey Goldberg has repeatedly shared his belief that strong crypto plus a strong passphrase are the best defense here.

This leads to my concern with TripleSec, a bespoke crypto system written by amateur cryptographers. I admire TripleSec, but it's prudent to question your credentials. Additionally, from what I've read, cascade ciphers are largely discouraged; their added complexity gives minimal improvement while simultaneously increasing the chance for implementation error and making cryptanalysis more difficult.

I assume a motivator in creating TripleSec was client-side, browser crypto. The proposed "Keybase Mini" would move all keybase crypto (aside from secure comm between extension and native helper) out of the browser.

Compels keybase to modify its software, either across the board or targeted to an individual.

This is the biggest threat in my view. Having commandeered keybase, a bad actor can harvest users' private key passphrases when those users decrypt or sign via their browsers. Given the nature of browser security, this seems a likely attack vector. I know you're cognizant of these threats, demonstrated by removing 3rd party JS includes, e.g. #107.

Whether through compulsion or subversion, I believe strongly that performing keybase crypto in browser will be exploited.

Perhaps one could argue Dropbox is more prepared to defend itself against the forced mass seizure of encrypted data.

I assume no, irrespective of what one reads into Condoleezza Rice's appointment. Large corporations, if so inclined, may be more successful at narrowing the scope. But in that case, the NSA sidesteps compulsion and just taps into their infrastructure.

Hence my advocacy for a zero-knowledge design. At the very least it moves the target from "compromise this centralized service" to "compromise and distribute client software containing backdoors". For the latter we have some decent defenses such as open source client code.

[maxtaco]

BTW, as for TripleSec, there was a discussion about it among crypto experts a few months back. The construction seems pretty safe. It's not a "cascade" at all. Rather, it's just the XOR of 3 (computationally) independent cipher streams. Even if one outputs all 0s, the strength of the other 2 are unaffected. (This property doesn't hold for traditional cascades).

[ghost]

If I switch sides and attempt to defend TripleSec against Schneier's Law, are these accurate statements? Would you add anything?

• we're implementing established cryptography, not designing a new crypto system
• we've implemented 3 mainstream ciphers
• to the extent that you might claim we're designing a new crypto system, it amounts to the decision to combine the 3 ciphers with XOR, a construction that is simple to implement and correspondingly easy for cryptanalysts to review

As I'm sure is obvious, when it comes to crypto I'm a layman who depends on trying to square his limited understanding with the advice he reads from crypto experts he occasionally reads (though not too much, lest he gets too paranoid and depressed).

[timbray]

@malgorithms writes:

1. someone evil holds a gun to keybase's head and makes it hand over encrypted private keys, then works on brute forcing them.
2. someone evil compels keybase to modify its software, either across the board or targeted to an individual.

I just can’t bring myself to worry about brute-force attacks at scale. The one that keeps me awake at night is #2. I am increasingly convinced that the browser community needs to figure out a way to deliver a trustworthy JS app, as in one where you can audit a particular version and then be sure that you’re using that building. No, I don’t actually know whether that’s technically possible.

[malgorithms]

The one that keeps me awake at night is #2.

We share (2) as our bigger concern of the pair. And, unfortunately, moving the key store off of Keybase into something else (say Dropbox) does not solve that. Let's say I use 1Password. If Apple serves me a bad 1Password app from the app store (either because they are forced to, directly, or because AgileBits submits one), then whether I store my encrypted AgileBits data in Dropbox or on AgileBits servers is irrelevant. The same is true for downloading the binary from AgileBits' website. They might release signatures, but again, how is the average consumer verifying those?

JS crypto correctly gets attention as a place where individuals can get targeted custom software that they don't review. But this is not unique to JS. Almost all the other methods of general consumer software installations suffer from the same problems: almost no consumer will (or can) check software signatures.

So (2) is a serious problem in all consumer crypto software.

For another example, Max and I have been playing with Whisper System's Signal App. (It's really cool, btw.) And while I think it's extremely well done, I have no clue whether the Signal app I installed matches the open source software. There could be an entirely bad one in the store, or Apple may have to serve bad binaries on request/coercion.

Ugg!

[zQueal]

Well, one of the only things I would worry about with brute forcing would be the work factor that's being set to scrypt the hashes. As many of you may or may not know, bcrypt, and scrypt have built in work factors which, if set appropriately pretty much render any form of brute force attack useless as the work factor is necessary to reverse the hash and comes with it a cost of time in seconds. I couldn't find the table for scrypt, but here's for bcrypt:

Work	Time (Seconds)
4	0.0013326406478882
5	0.0024385929107666
6	0.0046159029006958
7	0.0089994072914124
8	0.018425142765045
9	0.035568559169769
10	0.070761203765869
11	0.14275025129318
12	0.28672399520874
13	0.56773639917374
14	1.1397068500519
15	2.2705371022224
16	4.5342264413834
17	9.0786491513252
18	18.10820235014
19	36.225910997391
20	72.565172195435

This pretty much means that with a high enough work factor things such as brute force or hash collision attacks are meaningless--if keybase is using a work factor of 15, for example, it would take within the ballpark of 2.2705371022224 seconds to execute each brute force attempt multiplied by the number of attempts necessary to be successful and multiplied again by the number of users being "cracked."

At the end of the day, I feel pretty safe. I would be interested to know the AWF that's being used by scrypt, but it actually increases entropy if that information isn't publicly available.

[ghost]

Now it's worth distinguishing between U.S. government compulsion (which I call commandeering) versus clandestine subversion (which I call attack).

Unfortunately, moving the key store off of Keybase into something else...does not solve that.

Diversification has merit, doesn't it? An attacker must subvert two systems. Accepting as a given that Dropbox is commandeered, diversifying there is a wash. Diversifying to a zero-knowledge cloud sync service has benefits, though I admit maybe less than I think.

That said, average consumers are going to demand Dropbox/GDrive/SkyDrive/iCloud, which I agree offers little-to-no extra defense from commandeering over keybase.io hosting.

They might release signatures, but again, how is the average consumer verifying those?

Signatures enable security watchdogs who might sound an alarm which might reach the average consumer. A non-zero chance of detection is an improvement. Commandeering Keybase, they could compel you to publish signatures of tampered clients. Verifying Open Source app store releases, which you bring up, is relevant here.

JS crypto correctly gets attention as a place where individuals can get targeted custom software that they don't review. But this is not unique to JS.

Agreed.

But it's both easier and faster to subvert the browser. Making matters worse, one of the traditional advantages of the web – zero deployment – works to our disadvantage. Even with auto-updates enabled, native app deployment isn't globally instantaneous. A window, albeit small, for early detection exists.

I have no clue whether the Signal app I installed matches the open source software.

Do you know off hand if code signing an iOS or OS X app modifies the blob? If so, is it possible to extract the original blob that was signed? The idea being that, given the exact build steps, you could build Signal from source, sans code signing, and compare fingerprints.

The idea again is enabling watchdogs. Given the iOS/OSX app store review delay, advance notice of a release would allow them to reproduce builds well in advance of Apple completing their review, waiting until eventual release to check the fingerprint. Being consistent in this practice would make releases that lacked this "heads up" look suspicious. Naturally, this pre-supposes open source Keybase clients.

[ghost]

I just can’t bring myself to worry about brute-force attacks at scale. — @timbray

if set appropriately pretty much render any form of brute force attack useless — @Xanza

I agree with @timbray that commandeering (my words) is the greater threat, but I'm reluctant to dismiss brute-force attacks at scale. While work factor may make brute-force at scale uneconomical, I don't know if the same can be said about dictionary attacks at scale. The NSA has the advantage of constantly increasing capabilities; time; individual metadata; password history; and the poor password habits of the average, uninformed or unwary consumer.

[zQueal]

I don't know if the same can be said about dictionary attacks at scale. The NSA has the advantage of constantly increasing capabilities; time; individual metadata; password history; and the poor password habits of the average, uninformed or unwary consumer.

That is, unfortunately, a very sobering fact to me. Kind of scares the shit out of me, really.

[xero]

this is a very interesting topic...

I have no clue whether the Signal app I installed matches the open source software.

Do you know off hand if code signing an iOS or OS X app modifies the blob? If so, is it possible to extract the original blob that was signed? The idea being that, given the exact build steps, you could build Signal from source, sans code signing, and compare fingerprints.

ios bakes your identity info into every app for drm purposes. so the same app on two different identical mobile devices will have different fingerprints.

when you join itunes they generate you a key pair. when you download an app apple injects a header encrypted with your public key. only your private key can decrypt the header embedded in the app.

e.g. if i copied an ipa generated for you, and put it on my device (this is assuming you can get It there, itunes would refuse to sync it anyway), and then tried to run it, it would simply crash because my private key wouldn't be able to decrypt the headers generated with your keys.

just another example of drm getting in the way.

[ghost]

just another example of drm getting in the way.

Indeed. With your pointer, I did some more research. Near as I can tell, independent fingerprint checking of an IPA installed from the App Store would require a jailbroken device :frowning:

[far-blue]

I strongly agree that keybase should encourage a zero-knowledge environment and I think the suggestion of a 1Password-like mini-app is a very good one. The keybase API should make this pretty easy and moving the 'heavy lifting' off to a mini-app also makes maintaining plugins for different growers easier.

Regarding sync'ing of gpg keychains I've struggled with this for years but am currently confident enough in SpiderOak's zero-knowledge setup to use them. I certainly don't recommend Dropbox as they have proven to the world multiple times that their staff have access to keys and can read your data.

The mobile environment is a tricky one but I hope iOS8 will make things easier. AgileBits have shown the power of the new features in the upcoming iOS with a 1Password 'helper' for Mobile Safari as well as a library to allow App developers to integrate 1Password. 1Password on iOS 8 will also allow unlock via the fingerprint sensor. In theory, the same functionality could allow for a keybase app/library/helper combination in the same way (as well as shared, possibly read-only, access to a sync'd gpg keychain).

[gene1wood]

@malgorithms You may want to edit the description of this issue since the presence of the [Hypothetical] string in the title was not enough for me to realize that this issue wasn't on showing how keybase had gotten an NSL.

It was only after reading through the wall of text, a handful of responses, and your detailed response that I noticed the last line of your comment where you say We have not in fact received an NSL.

Any other reader that doesn't read the whole thread will take away from this the content of that AP news story that keybase has indeed gotten an NSL and that's why you haven't responded in a clear way saying "no we haven't" because you can't.

[ghost]

It is mostly irrelevant if a reader mistakes the hypothetical AP story for reality.

@malgorithms writes We have not in fact received an NSL. Imagine he repeats that statement tomorrow and a month from tomorrow. What's your basis for believing any of the statements are true? I'm not calling into question Chris' character, but how do we know Keybase can't be compelled to make these statements post-receipt? Absence of a signal is a signal, and the NSL prohibits revealing receipt.

We have to assume that we cannot detect when Keybase has received an NSL. It follows that we must assume they already have.

Illustrating this was the purpose of my OP. You read it and suspend your disbelief (or mistake it for reality) and view Keybase through a different lens; a lens where they have received an NSL and you know it.

[onlykey]

One solution to this hypothetical problem is to store private keys offline in hardware. Any time a private key is stored on computer it is susceptible to any number of attacks that if successful allow the attacker to decrypt not only current message but all past and future messages (Unless PFS is somehow integrated into PGP).

I propose integration with a product we are working on called OnlyKey - https://github.com/keybase/keybase-issues/issues/2940

The way this would work is that the Keybase app would send encrypted messages to the OnlyKey, the OnlyKey would send back decrypted messages. The only way to get the decrypted messages is for a physical person to press button on the OnlyKey. Unlike other tokens it would also work without any special drivers on any platform including Android. This way even if there is a backdoor in the app software it would only result in compromise of the decrypted messages that the user decrypts with that software not the user's key.

UPDATE 6/19/18 - OnlyKey now integrates with Keybase for web based PGP encryption. Private key remains offline and is never accessible to the browser - https://docs.crp.to/webcrypt.html

[ghost]

FWIW I spoke with someone at keybase recently via email and they informed me the government could not read messages on keybase. If you'd like a copy of the email I can provide one on the sneakernet.