22 ms·

Fake Linus Torvalds' Key Found in the Wild, No More Short-IDs

701 points by demiol 10y ago

eriknstr 10y ago
The e-mail includes a couple of links. The linked site at http://gwolf.org/node/4070 http://gwolf.org/node/4070 returns "page not found?" for me currently. Here is an archived version of that page which works: http://archive.is/sSXvX http://archive.is/sSXvX
ckastner 10y ago
This has also been discovered with the Debian project, as I submitted a while ago [1]. 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... Edit: even the 64-bit fingerprint is probably insufficient, see [3]. [1] https://lists.debian.org/debian-devel/2016/08/msg00143.html https://lists.debian.org/debian-devel/2016/08/msg00143.html [2] https://lists.debian.org/debian-devel/2016/08/msg00144.html https://lists.debian.org/debian-devel/2016/08/msg00144.html [3] https://lists.debian.org/debian-devel/2016/08/msg00215.html https://lists.debian.org/debian-devel/2016/08/msg00215.html
- tomrod 10y ago
  Why is this scary?
  - ckastner 10y ago
    Because it removes many obvious tells of a deliberate key collision targeting a specific key, and thus is harder to detect. 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.
    - schoen 10y ago
      The whole point of this research was to underscore that PGP key acquisition is commonly broken. You could choose to blame PGP software, users, documentation, or the web-of-trust model itself, but in any case what a significantly number of people commonly do is unsafe.
CiPHPerCoder 10y ago
I've attended security conferences in the past two years wherein representatives of companies that claim to see 80+ percent of all Internet traffic in their threat intel offerings who were presenting about Android malware reverse engineering used short IDs in their slide deck and business cards. When I mentioned Evil32 to them, they looked at a loss. https://evil32.com https://evil32.com 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.
- deleted 10y ago
  [deleted]
- voltagex_ 10y ago
  I'm just some guy, but I've got a stack of cards with my short ID on them - what do I do now? Toss them?
  - ashitlerferad 10y ago
    Destroy them carefully and use the opportunity to create new ones with QR codes on them with your full public key (or just the full fingerprint).
    - pflanze 10y ago
      I've written software to help me create QR codes for my business card, including PGP, address, web site etc. There are many gotchas, some apps ignore some VCard fields, hence it puts copies into generic comment fields, too. Seems to work OK now. Maybe I should turn this into a web service. https://github.com/pflanze/vcard-scm https://github.com/pflanze/vcard-scm
forgotpwtomain 10y ago
32 bit seems so obviously bad I'm not sure why we still have it..
- wtbob 10y ago
  The 90s were a different time, that's the only explanation I can come up with. Short key IDs are yet another 90s-crypto wart.
  - xorblurb 10y ago
    Even in the 90s it seems odd to design a system trivially vulnerable to birthday attacks (with maybe a simplification, but that's how primitives are evaluated: if it fails in a slightly simplified version or environment, it's unfit for service). Now birthday attacks are not exactly applicable to the "how to forge a key with the same short id as that exact person", but with an high number of keys available there may be other ways to ease your attempts to generate collisions, even if that means relaxing your target requirements somehow. Even if there are not, you must be extremely paranoid when designing anything security related: here barely doubling the size of the short id would have mitigated today's problem, but we see that now 64 bits is not even enough. So there has been a fuck-up (with, I agree, a (lack of) security climate in the 90s that might have contributed a lot to that fuck-up), it has enormous consequences right now (given some distro still default their gpg packages to an obsolete version, it seems). We must take what happened and happens right now into account, and learn our lesson: trivial conveniences decreasing security against abstract hole shall be considered an absolute no-go, and something to fix ASAP with absolute priority. 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.
ajdlinux 10y ago
All the fake keys that I've seen mentioned are from the data set at https://evil32.com https://evil32.com. 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!
- d33 10y ago
  At this point this is INSANE that GnuPG still defaults to short IDs...
  - pavanky 10y ago
    I remember reading that they updated it to be full key a few versions ago. I can't seem to find the actual link for that..
    - satbyy 10y ago
      This bug report makes GPG to default to full fingerprint https://bugs.gnupg.org/gnupg/issue2379 https://bugs.gnupg.org/gnupg/issue2379
  - snassar 10y ago
    It doesn't anymore. With GnuPG 2.1 listing of keys shows the fingerprint.
    - okket 10y ago
      But for server installations (auto-signing, checking, etc.) you are often directed to GnuPG 1 because "less dependencies". Also "apt install gnupg" / "dnf install gnupg" both give you version 1 on the most recent Ubuntu/Fedora. 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.
wtbob 10y ago
I don't know why more folks don't display keys and fingerprints as Base64; it seems to me that "q68RxlopcLEwq+PEeb4+QwBBGIY=" (Linus's real key) and "D2oUZTLYaa7kOPdLYhGqOwBBGIY=" (Linus's fake key) are pretty easilt-distinguishable, and not terribly verbose.
- eli 10y ago
  If everyone did that, couldn't attackers just target collisions that "look like" the target key in Base64? i.e. the same first 5 or 6 chars and the punctuation in the right places.
- YPCrumble 10y ago
  Is there a reason a hacker couldn't just create a key like "q68RxlopoLEwq+PEeb4+QwBBGIY=" to create a similar problem?
  - akerro 10y ago
    The string is longer so collision is harder to find. btw that's a way .onion addresses are generated, it takes first 80 bytes from the key and outputs base32 from the input.
    - CiPHPerCoder 10y ago
      Rather, it takes the first 80 bits of a SHA1 hash of a 1024-bit RSA public key, then converts it to base32. Obviously, collisions aren't obscenely expensive.
- _wmd 10y ago
  You can do what PGPfone did and encode the fingerprint as a series of dictionary words: 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 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/cheatcodes-turning-bittorrent-links-into-spoken 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
JulianMorrison 10y ago
Take a leaf out of urbit's book, and convert hex strings into readable nonsense syllables that are a lot easier for humans to compare.
- lucaspiller 10y ago
  UTF-8 v9.0 contains 1085 emoji, that should be even easier to compare than random symbols.
  - sleepychu 10y ago
    I'm not sure if you're sincere but I don't think emoji would be easier to compare. +Might be less friendly to screen reader users?
    - avisser 10y ago
      I hate to say it, but comparing two, long hash values via a screen reader doesn't seem viable for humans, regardless of emoji. Maybe an auralizer to turn the hash into a short piece of music?
      - JulianMorrison 10y ago
        See my above example from urbit. They are something a screen reader would clearly read differently for different values, if not comprehensibly.
    - masklinn 10y ago
      > I'm not sure if you're sincere but I don't think emoji would be easier to compare. 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.
raesene6 10y ago
Personally I like the keybase approach for this of tying GPG keys to a set of accounts. 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...
hannob 10y ago
Seems some people are playing havoc with key ids. 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=index 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.
- geofft 10y ago
  From evil32.com: > 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.
  - emmelaich 10y ago
    Seems it is not merely the strong set. 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.
- eridius 10y ago
  Yes, they've been revoked. See this comment https://news.ycombinator.com/item?id=12298230 https://news.ycombinator.com/item?id=12298230
ckastner 10y ago
Linus' fake key [1], as well as all the others from the random sample I took, have been revoked as of today. [1] http://pgp.mit.edu/pks/lookup?op=vindex&search=0xEA185A5E76E21CBB http://pgp.mit.edu/pks/lookup?op=vindex&search=0xEA185A5E76E....
- brians 10y ago
  So the evil32 people kept the private keys. That's exciting.
  - mpasternacki 10y ago
    Not necessarily, they might have just generated revokation certs which are separate (so that they can be used in case your private key is lost). Keeping a revokation cert would be a responsible thing to do, just in case something like this happens.
    - eridius 10y ago
      They had an old backup that contained the private keys. See this comment https://news.ycombinator.com/item?id=12298230 https://news.ycombinator.com/item?id=12298230
satbyy 10y ago
As mentioned in debian-devel lists, add this to your ~/.gpg.conf: keyid-format long as a stop gap measure, it will show long IDs (64-bit). Obviously comparing full key (`--with-fingerprint`) is the best.
- raphlinus 10y ago
  Someone claims (https://groups.google.com/forum/#!topic/sci.crypt/JSSM6NbfweQ https://groups.google.com/forum/#!topic/sci.crypt/JSSM6Nbfwe...) that it's just as easy to spoof 64 bit as 32 bit keys. I have no idea whether to believe him, but even if he's full of it, it's prudent to assume that if the 32 bit attack was practical 20 years ago, 64 bits is within reach today.
  - geofft 10y ago
    That's a post from 1996. I'm not sure how "easy" was calculated. Possibly both were hard but tractable, but 64 bits should have been much harder. 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 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 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.)
    - Senji 10y ago
      This means state actors like three letter agencies already have this capability.
- bysat 10y ago
  Thanks!
aftbit 10y ago
Hi, Eric here, co-creator of evil32. I posted a brief note on our site about this, but here's a little more detail. 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 https://keybase.io/aftbit
- TorKlingberg 10y ago
  Sorry, whose private keys did you find a backup of?
  - deckar01 10y ago
    It sounds like they have issued revocation certs for the keys associated with the fake accounts to stop people from sending any more messages to the fake accounts. They are also promising not to decrypt any of the messages that were meant for the attack victims, but encrypted for the fake accounts' public keys and sent to the attacker during the attack.
amenghra 10y ago
http://pgp.mit.edu/pks/lookup?search=B9E39278 http://pgp.mit.edu/pks/lookup?search=B9E39278
- ktta 10y ago
  wait, this looks interesting. Can someone comment on this? Are you supposed to know the fingerprint after you input name and stuff or before? Or is this just modification of data like how you can add email IDs?
  - lmm 10y ago
    You're supposed to confirm the fingerprint with the person. At the time the recommendation was a phone call (if you knew their voice) using the PGP word list - it was felt to be computationally implausible to fake that up in realtime. Or people publish fingerprints on their site etc. 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.
    - ktta 10y ago
      Thanks for taking the time, but seems like you didn't click on the link. When you look at the name of the keyholder of the fingerprint (B9E39278), the User Name of the keyholder is same as the fingerprint of the key. I was asking if the User Name is set after the key is generated or before. Or if one can change user name after key generation. And I think you can, so there's nothing interesting here :)
  - amenghra 10y ago
    method 1: Keep generating keys until you have a collision. 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/ https://openpgpjs.org/)
    - 10y ago
fulldecent 10y ago
Just make the keys 256 characters and add an ASCII art penis in the front, just to make it very clear that humans should not be seeing these things.
zbuf 10y ago
These keys have always seemed remarkably short. Roughly how many CPU-hours does it take to find a collision?
- garaetjjte 10y ago
  "It takes 4 seconds to generate a colliding 32bit key id on a GPU" source: https://evil32.com/ https://evil32.com/
- meta_AU 10y ago
  I'm using ABCDABCD, and from memory it took a couple of hours. The hardest part was picking a 'vanity' short id that wasn't already taken.
neoCrimeLabs 10y ago
apt package manager uses short-ids with a repository key is not recognised, as well as when you use apt-key to add the key to your keychain. 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.
raphlinus 10y ago
Just to point out, this attack goes back at least 22 years. According to [this thread](https://groups.google.com/forum/#!topic/sci.crypt/JSSM6NbfweQ https://groups.google.com/forum/#!topic/sci.crypt/JSSM6Nbfwe...), credit is due to Paul Leyland.
Fry-kun 10y ago
I've mentioned an idea in Phoronix forums[1] yesterday: Since most users won't bother comparing the entire signature (also applies to comparing md5/sha*/etc. hashes), it might be a good idea to map & display blocks of the sig as English words to the user. 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 With a word salad approach: 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 Even with an even-spaced font, it's hard to confuse the two (random words from [3]) [1] https://www.phoronix.com/forums/forum/phoronix/latest-phoronix-articles/891066-the-brewing-problem-of-pgp-short-id-collision-attacks https://www.phoronix.com/forums/forum/phoronix/latest-phoron... [2] https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0039.mediawi... [3] https://www.randomlists.com/random-words https://www.randomlists.com/random-words
- lmm 10y ago
  The pgp word list was created for exactly this purpose. https://en.wikipedia.org/wiki/PGP_word_list https://en.wikipedia.org/wiki/PGP_word_list
kseifried 10y ago
So my solution to this was to sign a ton of publicly archived email with my full fingerprint. Then I stopped signing email and not a single person noticed/cared, so yeah. Meh. CVE assignments, no big deal I guess.

701 points by demiol 10y ago

The e-mail includes a couple of links. The linked site at http://gwolf.org/node/4070 http://gwolf.org/node/4070 returns "page not found?" for me currently. Here is an archived version of that page which works: http://archive.is/sSXvX http://archive.is/sSXvX

ckastner 10y ago

This has also been discovered with the Debian project, as I submitted a while ago [1]. 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... Edit: even the 64-bit fingerprint is probably insufficient, see [3]. [1] https://lists.debian.org/debian-devel/2016/08/msg00143.html https://lists.debian.org/debian-devel/2016/08/msg00143.html [2] https://lists.debian.org/debian-devel/2016/08/msg00144.html https://lists.debian.org/debian-devel/2016/08/msg00144.html [3] https://lists.debian.org/debian-devel/2016/08/msg00215.html https://lists.debian.org/debian-devel/2016/08/msg00215.html

tomrod 10y ago
Why is this scary?
- ckastner 10y ago
  Because it removes many obvious tells of a deliberate key collision targeting a specific key, and thus is harder to detect. 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.
  - schoen 10y ago
    The whole point of this research was to underscore that PGP key acquisition is commonly broken. You could choose to blame PGP software, users, documentation, or the web-of-trust model itself, but in any case what a significantly number of people commonly do is unsafe.

CiPHPerCoder 10y ago

I've attended security conferences in the past two years wherein representatives of companies that claim to see 80+ percent of all Internet traffic in their threat intel offerings who were presenting about Android malware reverse engineering used short IDs in their slide deck and business cards. When I mentioned Evil32 to them, they looked at a loss. https://evil32.com https://evil32.com 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.

deleted 10y ago
[deleted]
voltagex_ 10y ago
I'm just some guy, but I've got a stack of cards with my short ID on them - what do I do now? Toss them?
- ashitlerferad 10y ago
  Destroy them carefully and use the opportunity to create new ones with QR codes on them with your full public key (or just the full fingerprint).
  - pflanze 10y ago
    I've written software to help me create QR codes for my business card, including PGP, address, web site etc. There are many gotchas, some apps ignore some VCard fields, hence it puts copies into generic comment fields, too. Seems to work OK now. Maybe I should turn this into a web service. https://github.com/pflanze/vcard-scm https://github.com/pflanze/vcard-scm

forgotpwtomain 10y ago

32 bit seems so obviously bad I'm not sure why we still have it..

wtbob 10y ago
The 90s were a different time, that's the only explanation I can come up with. Short key IDs are yet another 90s-crypto wart.
- xorblurb 10y ago
  Even in the 90s it seems odd to design a system trivially vulnerable to birthday attacks (with maybe a simplification, but that's how primitives are evaluated: if it fails in a slightly simplified version or environment, it's unfit for service). Now birthday attacks are not exactly applicable to the "how to forge a key with the same short id as that exact person", but with an high number of keys available there may be other ways to ease your attempts to generate collisions, even if that means relaxing your target requirements somehow. Even if there are not, you must be extremely paranoid when designing anything security related: here barely doubling the size of the short id would have mitigated today's problem, but we see that now 64 bits is not even enough. So there has been a fuck-up (with, I agree, a (lack of) security climate in the 90s that might have contributed a lot to that fuck-up), it has enormous consequences right now (given some distro still default their gpg packages to an obsolete version, it seems). We must take what happened and happens right now into account, and learn our lesson: trivial conveniences decreasing security against abstract hole shall be considered an absolute no-go, and something to fix ASAP with absolute priority. 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.

ajdlinux 10y ago

All the fake keys that I've seen mentioned are from the data set at https://evil32.com https://evil32.com. 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!

d33 10y ago
At this point this is INSANE that GnuPG still defaults to short IDs...
- pavanky 10y ago
  I remember reading that they updated it to be full key a few versions ago. I can't seem to find the actual link for that..
  - satbyy 10y ago
    This bug report makes GPG to default to full fingerprint https://bugs.gnupg.org/gnupg/issue2379 https://bugs.gnupg.org/gnupg/issue2379
- snassar 10y ago
  It doesn't anymore. With GnuPG 2.1 listing of keys shows the fingerprint.
  - okket 10y ago
    But for server installations (auto-signing, checking, etc.) you are often directed to GnuPG 1 because "less dependencies". Also "apt install gnupg" / "dnf install gnupg" both give you version 1 on the most recent Ubuntu/Fedora. 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.

wtbob 10y ago

I don't know why more folks don't display keys and fingerprints as Base64; it seems to me that "q68RxlopcLEwq+PEeb4+QwBBGIY=" (Linus's real key) and "D2oUZTLYaa7kOPdLYhGqOwBBGIY=" (Linus's fake key) are pretty easilt-distinguishable, and not terribly verbose.

eli 10y ago
If everyone did that, couldn't attackers just target collisions that "look like" the target key in Base64? i.e. the same first 5 or 6 chars and the punctuation in the right places.
YPCrumble 10y ago
Is there a reason a hacker couldn't just create a key like "q68RxlopoLEwq+PEeb4+QwBBGIY=" to create a similar problem?
- akerro 10y ago
  The string is longer so collision is harder to find. btw that's a way .onion addresses are generated, it takes first 80 bytes from the key and outputs base32 from the input.
  - CiPHPerCoder 10y ago
    Rather, it takes the first 80 bits of a SHA1 hash of a 1024-bit RSA public key, then converts it to base32. Obviously, collisions aren't obscenely expensive.
_wmd 10y ago
You can do what PGPfone did and encode the fingerprint as a series of dictionary words: 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 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/cheatcodes-turning-bittorrent-links-into-spoken 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

JulianMorrison 10y ago

Take a leaf out of urbit's book, and convert hex strings into readable nonsense syllables that are a lot easier for humans to compare.

lucaspiller 10y ago
UTF-8 v9.0 contains 1085 emoji, that should be even easier to compare than random symbols.
- sleepychu 10y ago
  I'm not sure if you're sincere but I don't think emoji would be easier to compare. +Might be less friendly to screen reader users?
  - avisser 10y ago
    I hate to say it, but comparing two, long hash values via a screen reader doesn't seem viable for humans, regardless of emoji. Maybe an auralizer to turn the hash into a short piece of music?
    - JulianMorrison 10y ago
      See my above example from urbit. They are something a screen reader would clearly read differently for different values, if not comprehensibly.
  - masklinn 10y ago
    > I'm not sure if you're sincere but I don't think emoji would be easier to compare. 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.

raesene6 10y ago

Personally I like the keybase approach for this of tying GPG keys to a set of accounts. 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...

hannob 10y ago

Seems some people are playing havoc with key ids. 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=index 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.

geofft 10y ago
From evil32.com: > 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.
- emmelaich 10y ago
  Seems it is not merely the strong set. 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.
eridius 10y ago
Yes, they've been revoked. See this comment https://news.ycombinator.com/item?id=12298230 https://news.ycombinator.com/item?id=12298230

ckastner 10y ago

Linus' fake key [1], as well as all the others from the random sample I took, have been revoked as of today. [1] http://pgp.mit.edu/pks/lookup?op=vindex&search=0xEA185A5E76E21CBB http://pgp.mit.edu/pks/lookup?op=vindex&search=0xEA185A5E76E....

brians 10y ago
So the evil32 people kept the private keys. That's exciting.
- mpasternacki 10y ago
  Not necessarily, they might have just generated revokation certs which are separate (so that they can be used in case your private key is lost). Keeping a revokation cert would be a responsible thing to do, just in case something like this happens.
  - eridius 10y ago
    They had an old backup that contained the private keys. See this comment https://news.ycombinator.com/item?id=12298230 https://news.ycombinator.com/item?id=12298230

satbyy 10y ago

As mentioned in debian-devel lists, add this to your ~/.gpg.conf: keyid-format long as a stop gap measure, it will show long IDs (64-bit). Obviously comparing full key (`--with-fingerprint`) is the best.

raphlinus 10y ago
Someone claims (https://groups.google.com/forum/#!topic/sci.crypt/JSSM6NbfweQ https://groups.google.com/forum/#!topic/sci.crypt/JSSM6Nbfwe...) that it's just as easy to spoof 64 bit as 32 bit keys. I have no idea whether to believe him, but even if he's full of it, it's prudent to assume that if the 32 bit attack was practical 20 years ago, 64 bits is within reach today.
- geofft 10y ago
  That's a post from 1996. I'm not sure how "easy" was calculated. Possibly both were hard but tractable, but 64 bits should have been much harder. 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 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 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.)
  - Senji 10y ago
    This means state actors like three letter agencies already have this capability.
bysat 10y ago
Thanks!

aftbit 10y ago

Hi, Eric here, co-creator of evil32. I posted a brief note on our site about this, but here's a little more detail. 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 https://keybase.io/aftbit

TorKlingberg 10y ago
Sorry, whose private keys did you find a backup of?
- deckar01 10y ago
  It sounds like they have issued revocation certs for the keys associated with the fake accounts to stop people from sending any more messages to the fake accounts. They are also promising not to decrypt any of the messages that were meant for the attack victims, but encrypted for the fake accounts' public keys and sent to the attacker during the attack.

amenghra 10y ago

http://pgp.mit.edu/pks/lookup?search=B9E39278 http://pgp.mit.edu/pks/lookup?search=B9E39278

ktta 10y ago
wait, this looks interesting. Can someone comment on this? Are you supposed to know the fingerprint after you input name and stuff or before? Or is this just modification of data like how you can add email IDs?
- lmm 10y ago
  You're supposed to confirm the fingerprint with the person. At the time the recommendation was a phone call (if you knew their voice) using the PGP word list - it was felt to be computationally implausible to fake that up in realtime. Or people publish fingerprints on their site etc. 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.
  - ktta 10y ago
    Thanks for taking the time, but seems like you didn't click on the link. When you look at the name of the keyholder of the fingerprint (B9E39278), the User Name of the keyholder is same as the fingerprint of the key. I was asking if the User Name is set after the key is generated or before. Or if one can change user name after key generation. And I think you can, so there's nothing interesting here :)
- amenghra 10y ago
  method 1: Keep generating keys until you have a collision. 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/ https://openpgpjs.org/)
  - 10y ago

fulldecent 10y ago

Just make the keys 256 characters and add an ASCII art penis in the front, just to make it very clear that humans should not be seeing these things.

zbuf 10y ago

These keys have always seemed remarkably short. Roughly how many CPU-hours does it take to find a collision?

garaetjjte 10y ago
"It takes 4 seconds to generate a colliding 32bit key id on a GPU" source: https://evil32.com/ https://evil32.com/
meta_AU 10y ago
I'm using ABCDABCD, and from memory it took a couple of hours. The hardest part was picking a 'vanity' short id that wasn't already taken.

neoCrimeLabs 10y ago

apt package manager uses short-ids with a repository key is not recognised, as well as when you use apt-key to add the key to your keychain. 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.

raphlinus 10y ago

Just to point out, this attack goes back at least 22 years. According to [this thread](https://groups.google.com/forum/#!topic/sci.crypt/JSSM6NbfweQ https://groups.google.com/forum/#!topic/sci.crypt/JSSM6Nbfwe...), credit is due to Paul Leyland.

Fry-kun 10y ago

I've mentioned an idea in Phoronix forums[1] yesterday: Since most users won't bother comparing the entire signature (also applies to comparing md5/sha*/etc. hashes), it might be a good idea to map & display blocks of the sig as English words to the user. 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 With a word salad approach: 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 Even with an even-spaced font, it's hard to confuse the two (random words from [3]) [1] https://www.phoronix.com/forums/forum/phoronix/latest-phoronix-articles/891066-the-brewing-problem-of-pgp-short-id-collision-attacks https://www.phoronix.com/forums/forum/phoronix/latest-phoron... [2] https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0039.mediawi... [3] https://www.randomlists.com/random-words https://www.randomlists.com/random-words

lmm 10y ago
The pgp word list was created for exactly this purpose. https://en.wikipedia.org/wiki/PGP_word_list https://en.wikipedia.org/wiki/PGP_word_list

kseifried 10y ago

So my solution to this was to sign a ton of publicly archived email with my full fingerprint. Then I stopped signing email and not a single person noticed/cared, so yeah. Meh. CVE assignments, no big deal I guess.