Fake Linus Torvalds' Key Found in the Wild, No More Short-IDs
lkml.org
lkml.org
I found an old (local) backup of the private keys and used it to generate revocation certificates for each key. Fortunately, there is no way for anyone else to access or regenerate the private keys for this particular clone of the strong set, and I have been very careful with my copy - it is only available on my personal machine, and I have only used it to generate the revocation certificates. I will not use these keys to generate any fake signatures nor to decrypt any messages intended for the original recipients.
We wanted to bring awareness to the dangers of using short key IDs in the 21st century, since that ID is very easy to fake, and most of the contents of the key body are not covered by the signature, so they can be changed at will. However, we feel that the keys uploaded to the public keyserver are, on balance, more of harmful to the usability of the GPG ecosystem than they are helpful in highlighting security flaws.
It's important to realize that anyone could repeat our work pretty easily. While we did not release the scripts that automated cloning the web of trust, the whole process took me less than a week. Cloning a single key is even easier - it could be done with only a few minutes of effort by someone familiar with GPG. The GPG ecosystem needs to develop better defenses to this attack.
Our original talk (and previous work) seems to have convinced people to stop using 32-bit IDs in documentation or on their business cards. However, there is another common and harmful pattern: users who want to email someone discover their key by searching the keyserver for that email, then taking the newest key. This is akin to trust-on-first-use, and opts out completely from the web of trust or any kind of external verification.
Proof of identity: https://keybase.io/aftbit
Well, yes? What is the alternative, if I want to email someone who exists only in the form of a pseudonymous online identity?
Anyone can upload any key to a keyserver with any name.
If the key is just for their pseudonym, I usually offer to sign the key if they can send me the key through one service of my choice (where their username is public knowledge) and the fingerprint through another (meaning an attacker would have to compromise both accounts I chose). The offer to sign their key often makes people much more willing to jump through hoops, and I get to improve the web of trust.
But for some people I just don't care enough and just add the first best key.
But if this isn't true—if, for example, you are someone who wants to get in contact with a terrorist group (maybe for an interview, maybe because you want to join them, etc.) then there's not much to do but to trust-on-first-use some channel that seems to be them, no? No public channel can possibly be vouched for as being "the real them", or that channel would have been chased up by the CIA. Which means that any/every channel might just be a honeypot from the CIA or whoever else, trying to either frustrate your efforts, or convert you into a double-agent.
As you say any one of those channels could be a CIA operation, that's why asking for verification from two independent channels (i.e. asking for the keyfile on one channel, for the fingerprint on another) is preferable. A terrorist group that actually uses pgp might even entertain you if you ask on more than two channels for the fingerprint. The more channels you chose, the less likely it is that a single attacker controls all of them.
Another factor is that any public channel that is a front is likely to be called out sooner or later as a non-official channel. Most people and organizations are wary of the dangers of impersonation.
Of course there will always be situations where it's impossible to establish trust, like a leak by a group who tries to stay anonymous to the point of not associating with any previously used pseudonyms. Here you can't do anything but trust the first communication. But I think those cases are extremely infrequent: most groups and individuals try to establish a reputation, which nearly always gives you more points to anchor trust.
Also, I have several invites for Keybase is anyone wants one.
Doesn't that undermine the whole decentralized web of trust concept? All those services are operated by US companies - or what if someone simply compromised Keybase itself?
Ideally: Nothing. Keybase refers to other sources. I.e. a page on GitHub woth username and key fingerprint. So if keybase is compromises those links miss and it's no prove.
Keybase is just the place that connects all the proofs. The actual client verifies that they are correct. As such, if keybase was every compromised they would only be able to change the link to the gist, which wouldn't do them much good without access to my github account.
If you want to communicate with someone specific then presumably there's something that distinguishes that person from other people. Find a way to connect that something with a key fingerprint. E.g. if the point is that that someone is a journalist for the New York Times (as when Snowden was first looking to leak), they should publish their fingerprint in the NYT, or at least something NYT-official (like their website).
There are use cases where trust-on-first-use is adequate, sure. But there are use cases where it isn't.
It appears a couple of researchers decided, back in 2014, to demonstrate this issue by cloning the entire strong set of the PGP web of trust (not just Linus' key, but basically everyone who uses PGP/GPG for Free Software development - myself included).
It would appear that sometime quite recently, someone decided it would be fun to upload all of those keys (there's ~24,000 in their tarball) to the keyservers...
One would hope that the researchers behind evil32.com are ethical enough and sensible enough to have permanently destroyed the secret keys - but obviously, anyone could mount this attack quite trivially with modern hardware.
So, check your fingerprints!
With GnuPG 2.1 listing of keys shows the fingerprint.
For desktop usage many prefer GnuPG 2.0, because they fear compatibility issues that the new 2.1 key storage format could have with 3rd party software, and you can't go back (at least this is the reason why the Homebrew maintainers still default to 2.0, but at least not to version 1 anymore since a few days).
So you have a mess of 3 stable versions, all used by many at the same time.
Here's this week's LWN article about it:
https://lwn.net/SubscriberLink/696561/6392ebc623b794d8/
Note that it's a subscriber-generated link (articles <1wk old are paywalled). Please consider funding LWN's excellent work by becoming a subscriber: https://lwn.net/subscribe/
What 3rd party software is using the keystorage mechanisms directly? Do you mean how information is output from GnuPG?
It sounds like the situation you are describing is the keystore, which has changed formats. GnuPG 2.1, as far as I can remember, will oll use the older versions keystore, but you are correct, once you have a 2.1 keystore it can't be used by GnuPG 2.0 and 1.x.
It's a tough call for the GnuPG developers and something distributions should help with. On one hand there is immense pressure to improve GnuPG, on the other hand, you have many actors who kick GnuPG around when it makes any deviation.
I would say defaulting to GnuPG 1.x is a bug and new releases of Linux, Homebrew, etc., should use GnuPG 2.0 at the very least, but better yet, use GnuPG 2.1 which has many of the things that people complain about fixed or in process of being fixed.
Not on the same machine, but server/automatic -> GnuPG 1, desktop 2.0 or 2.1. Also different people may run different versions, even GnuPG 1 on desktop because they are used to. This compatibility mess that seems to persist for while was what I meant why people prefer to use the lowest common denominator in their sigs/cards/slides -> evil32.
> What 3rd party software is using the keystorage mechanisms directly?
Aren't there any? Good, then I misunderstood that argument in the Homebrew debates I read, sorry. That leaves only the fear of automatic upgrading and the inability to downgrade again as a blocker.
As for the downgrading issue:
It used to be you could just copy your .gnupg directory from computer to computer to computer and that's what constituted migrating your PGP keys.
This was also true for moving frmo GnuPG 1.4 to GnuPG 2.x. If you are starting with a new GnuPG keystore from 2.1 you can't just copy .gnupg and use it in a GnuPG 1.4 system, you have to export your public keys, your private keys, and your trustdb (although I am iffy on what this does) and import them on the systems where you are running GnuPG 1.4 or 2.0
I am unaware of any 3rd party software directly accessing the GnuPG keystore, but that doesn't say much.
Any idea what this will mean for Yubikey users? I've been wanting to set up my Yubikey 4 for GPG for a while, and have been... daunted.
When I mentioned Evil32 to them, they looked at a loss.
If this is news to you, don't feel bad. Many infosec conference speakers don't do this right either, and those are the sorts of people you'd expect to get this right.
The really scary part is the follow-up [2]:
> € gpg --search-key samuel.thibault@gnu.org
> ...
> (1) Samuel Thibault <samuel.thibault@gnu.org>
> 4096 bit RSA key 7D069EE6, created: 2014-06-16
And it has 55 signatures from 55 colliding keys...
[1] https://lists.debian.org/debian-devel/2016/08/msg00143.html
[2] https://lists.debian.org/debian-devel/2016/08/msg00144.html
[3] https://lists.debian.org/debian-devel/2016/08/msg00215.html
For example, pgp.mit.edu and Enigmail would currently output information for both keys that would be almost identical per 2014-08-05, the day evil32 apparently generated the keys. I say "almost" only because they didn't set the correct timestamps, and apparently did not duplicate all UIDs -- but they easily could have.
The diligent PGP user will of course not fall into such a trap, but an inexperienced user easily might, and there are many of them.
I got a mail earlier today I couldn't decrypt for unclear reasons. Now I understand why: It seems it was encrypted with a copy of my public key that is on the keyserver colliding with the keyid of my real key.
Right now there is a revoked copy of my key there: https://pgp.mit.edu/pks/lookup?search=hanno%40hboeck&op=inde...
What's exactly going on here? Other commentors indicate that someone uploaded keys from the evil32 page to the keyservers. Have the authors of evil32 now used their private keys to revoke them?
Anyway, the conclusion seems obvious: Keyids are dead, use full fingerprints. Latest gpg 2.1 versions already show full fingerprints by default.
I still had a short keyid on my webpage, will change that now.
> I saw that your clone of the strong set is revoked?
> Someone downloaded our copy of the strong set and uploaded all of the keys to the SKS keyserver network. :( While we took on this project to help prompt GPG to build a more secure ecosystem, this mass clone made the keyservers harder for everyone to use. Of course anyone could use our tools to regenerate their own strong set clone and do this again, but we'd rather our keys not be used that way.
I take that to mean that yes, they continued to be in possession of the private keys.
Mine is not in the strong set and it had a collision uploaded. It has the same upload (creation?) date -- 2014-06-16 as many others.
Obviously, collisions aren't obscenely expensive.
Real gregkh: 647F28654894E3BD457199BE38DBBDC8 = style tactful newcomers file gallows adored insist flags athletics
Fake gregkh: 497C48CE16B926E93F49630127365DEA = jukebox governor fashionable mahogany prepares gobble surprised martha apostles
There's even an Internet standard for this: http://tools.ietf.org/html/rfc1751 , although its dictionary isn't very large or interesting. Here's another implementation intended for BitTorrent magnet hashes: http://pythonsweetness.tumblr.com/post/56715292510/cheatcode...
SSH keygen has a mode where the digest is printed as ASCII art, I imagine by using the key as input into something like a fractal function. I can't find the option for it, but I'm sure you've seen it on the console at some point
http://superuser.com/questions/22535/what-is-randomart-produ...
What you need is a picture that makes the visually salient information tot up to about 160 bits.
That's tough, but since the human visual system is so powerful, it's not hopeless. But we would need real psychologists to help design the art generators, backing the results with experiments.
The word lists ignore and even foil, our gramatical machinery. And I at least have never been able to remember what my own randomart SSH key fingerprint looked like. Adding colour might be a good start.
The upside to showing a larger hash is that humans are very good at roughly comparing two things. The difference in casing is probably enough to trigger a conscious check. A visual hash is still better.
i.e. Ctrl + C, Ctrl + F, Ctrl + V
"oh look it didn't find it ... they don't match", versus, "yup all 64/128/2048/n digits match, the hashes are the same".
Odds are 1 in 64 to get the first character as lowercase q, 10 in 64 to get digits in the second spot, once more for the third spot, one in 16 to get a + sign close to where the plus sign is right now (so 1/64 for an exact match, 1/32 for one position off to either side, 1/16 for one position off to the left or right), another 1/16 for the second plus, and finally let's match the last three characters so another 1/(64^3). The padding should always be the same I think.
After, on average, 27.5 billion attempts you'd have a matching base64 output. It's not as great as a 32-bit integer (2 billion attempts on average) but it's in the same ballpark.
This is different from the 32 bit key id because the key id would be an exact match and the "visually similar" base64 string is only similar on first glance, but if you check the base64 carefully you might as well check the fingerprint carefully.
This is why it's recommended to check a few random positions when matching cryptographic hashes by the way.
http://hipku.gabrielmartin.net/#0F6A:1465:32D8:69AE:E438:F74...
> Hipku.encode('0F6A:1465:32D8:69AE:E438:F74B:6211:AA3B');
> Bold grouse and brass ghosts
> clamp strict lean sane tart dry whales.
> Fresh geese blur rust dice. The clever dark lamb
prowls in the ancient jungle.
Tiger lillies dance.https://www.usenix.org/conference/usenixsecurity16/technical...
https://news.ycombinator.com/item?id=12272425
From the abstract:
"The highest attack detection rate and best usability perception is achieved with a sentence-based encoding. If language-based representations are not acceptable, a simple numeric approach still outperforms the hexadecimal representation."
[1] http://pgp.mit.edu/pks/lookup?op=vindex&search=0xEA185A5E76E....
Generally when I'm talking to someone online I know someone via other sites (e.g. twitter, github), so being able to say "the person who controls the account xxx on github, uses this key" lets me establish a level of initial trust.
Obviously for high trust applications that's not enough, but better than nothing...
Maybe an auralizer to turn the hash into a short piece of music?
The point is to leverage human pattern matching so you want short-ish figures with large differences.
Each hex digits is 4 bits, but each emoji is 10 bits, a 128 bits key is 13 emoji which is significantly more eyeballable than 32 hex digits, and chances are you'll notice EGGPLANT being replaced by CAMERA in 13 pictures easier than you'd notice B being replaced by 8 in 32 characters.
Compare like with like - what are the two most similar emoji from that set of 2^10 ?
[0] https://en.wikipedia.org/wiki/Box_Drawing
[1] https://en.wikipedia.org/wiki/Mahjong_Tiles_(Unicode_block)
[2] https://en.wikipedia.org/wiki/Domino_Tiles
[3] https://en.wikipedia.org/wiki/Playing_cards_in_Unicode#Playi...
An example of urbit's rendering of a 128-bit number into textual form is "racmus-mollen-fallyt-linpex--watres-sibbur-modlux-rinmex". While it might be gibberish, it's gibberish that even a screen-reader program could take a swing at, and humans can easily read.
https://www.npmjs.com/package/proquint
Proquint (5 letters per 16 bits) is tighter than Urbit's `@p` (6 letters per 16 bits). The Urbit form was designed for synthetic names and restricts itself to phonemes that sound comfortable and natural to English speakers. (Not to say that English should be the universal language, it's actually a terrible language to make everyone learn, just that it is.)
Word lists work reasonably well, but they're quite bulky and they don't take advantage of the human hardware accelerator for learning new words. When you have a GPU, use it. These kinds of synthetic strings also make great passwords, BTW.
(Disclaimer: Urbit guy here.)
* Strict CV syllable scheme.
* Atonal
* Consonants distinguished only by voiced/voiceless (Chinese, e.g., doesn't do a voicing distinction, but switching to an aspiration distinction would suffice for them)
* 5 vowels: a, e, i, o, u (actual vowel quality may vary; every language that has at least 5 vowels has these 5 vowels) (some languages, particularly indigenous languages in North America, have 3 or 4 vowels, but the intersection yields too few vowels).
* Consonants are harder to inventory. /p/, /t/, /k/, /m/, /n/ are nearly universal, and /b/, /g/, /d/, /s/, /z/ are also quite common. The IPA /j/ (that's the 'y' in 'ya' for English speakers), /w/ (pronounced as you'd think in English) are pretty common semi-vowels. Maybe /l/, /ʃ/, /ʒ/ as well, should you need more consonants.
That gives you 25-75 plausible syllables, depending on how many consonants you go with.
[1] If you go by least common denominator, you end up with maybe 1 vowel and no consonants (there's no consonant phoneme present in every language IIRC).
Edit: not suggesting that Lojban's solution is somehow preferable to your advice, just trying to remember what they did about this issue.
From what I can tell, CV(C) (with the second consonant usually having some restrictions) is fairly widespread. However, in my personal (purely anecdotal) experience, pronouncing foreign consonant clusters or unfamiliar final consonants is much harder than pronouncing unfamiliar initial consonants or vowels, so I'd be slightly wary of letting the final consonant go too unrestricted.
Do Debian or any of the *BSDs yet default to including a font that supports emoji?
Sadly I do not expect the security approach to change before at least one more people generation, and then to be honest I'm not even sure it will ever change at all if we consider the mean global situation: the approach of far too many people is still "we don't give a fuck, we don't know anything about that, actually we don't even know that we should know something about that, this will just not happen to us, this is only a cost we can skip". Unless they are personally fucked, I don't expect half of that kind of people changing their mind. And then there are now so much software everywhere that I expect that the vast majority are so full of holes this is not even funny, and I expect that the ratio of insecure software will actually increase unless some kind of regulation are put in place -- but then I don't expect regulation to actually be sane and mandate for real security, given that politics want back doors at least every 4 years.
To optimistic people, please consider the following: even in a mainstream IT field, on one of the most used kind of device today, handling personal data all the day, the market leader designed an ecosystem where the OS that most people are actually using is most of the time not patched during most of the lifetime of said devices. If Google can get away with having such insane and shameful approach, why would you expect a random car vendor to have any real security in its embedded software? Obviously it is even worse for gadgets that VC currently think should/will be installed everywhere.
We are heading to security nightmare unless each of you who think security is important wake up and push the hardest they can to improve the situation. Relentlessly.
keyid-format long
Today it is significantly easier to collide a 32-bit key than a 64-bit one, but both are pretty easy. A 32-bit key can be collided in 4 seconds on a GPU, according to https://evil32.com. It can certainly be done on normal desktop hardware in hours. For a 64-bit key, 'JoshTriplett calculated (last week) that a collision would take 15 days if someone built hashing hardware of comparable quality to a commercial Bitcoin miner:
https://lists.debian.org/debian-devel/2016/08/msg00215.html
(Incidentally, I am very pleased with Bitcoin having created a liquid market between cryptographic computational speed and money, so we can answer these sorts of questions precisely.)
Care must be taken to avoid similar-looking and similar-sounding (homophonic) words, but since there are >150k words in Oxford English Dictionary, so it should be possible to get 65k usable ones.
In fact, someone pointed out something like this already exists to a degree: [2]
A contrived visual example (suppose someone matches first two and last two segments!):
Fake Linus Torvalds: ABAF 11C6 32D8 69AE E438 F74B 6211 AA3B 0041 1886
Real Linus Torvalds: ABAF 11C6 5A29 70B1 30AB E3C4 79BE 3E43 0041 1886
Fake Linus Torvalds: lopsided crate threatening hydrant peep bumpy art work earth spurious
Real Linus Torvalds: lopsided crate symptomatic equal kaput chunky kettle include earth spurious
(random words from [3])
[1] https://www.phoronix.com/forums/forum/phoronix/latest-phoron...
[2] https://github.com/bitcoin/bips/blob/master/bip-0039.mediawi...
Obv. the fingerprint only matters if you want to be sure you are talking to someone specific, in which case you usually have a way to know who they are or why you care. For some use cases trust-on-first-use is adequate.
method 2: What you said, modify the details.
A fun way to play/explore all things GPG is to use a javascript library and Chrome's javascript debugger (e.g. https://openpgpjs.org/)
When using 3rd party repositories, you will often see something like the following, which also uses short-ids:
> apt-key adv --keyserver keyserver.ubuntu.com --recv 7F0CEB10
So it makes me wonder if any commonly used repositories (or PPA's) have fake duplicate keys with the same key-id.
Roughly how many CPU-hours does it take to find a collision?
source: https://evil32.com/