12 ms·
Calling NSA to find your encryption key after a few bits were flipped (2010)
- drdaeman 5y agoI wonder what was the design consideration there? If I'd to make a guess, the point of having key in a re-programmable memory (susceptible to such errors) could be that it could be re-programmed later - otherwise it could've been just hardcoded in ROM. Athough if the error was that it was a RAM copy of the key that's got corrupt, this might explain things - no one to reboot the machine around, huh. If re-programmability was a design consideration, it is interesting is that there was no key reset procedure (with another, "master" key) which is something one would want to use if the normal communications key is compromised or corrupted.
- tylergetsay 5y agoThis was my thought as well, maybe the key was considered sensitive and getting it on the ROM would have exposed it to more people than "necessary"?
- axg11 5y agoIsn’t the use case the ability to change the encryption key in case it’s compromised?
- kklisura 5y agoBesides hardware mitigations (radiation hardening, ECC memory) what would be software mitigation techniques for this?
- NovemberWhiskey 5y agoForward-error correction. At the simplest, write the key ten different places in memory and compare the read values to determine the most probably correct.
- yeetsfromhellL2 5y agoTo protect against bit flips in car fly-by-wire systems, each signal is sent three times with the 2/3 majority making the decision. This happened after the runaway Prius fiasco that may have been caused by a gamma ray. Prior to that incident the fly-by-wire system only sent one signal.
- babelfish 5y agoSo in this context, send the message with three different encryption keys?
- sodality2 5y agoThis is really inefficient, two bitflips in the same location will result in a bitflip. For 3x the space surely there's a more resilient scheme that can handle more.
- tetha 5y agoIf I recall right this depends on the original message length and 1 bit is a bit of an edge case. If you transfer just 1 bit, you're very space constrained and it's hard to do much. 1 bit to 1 bit has nothing, 1 bit to 2 bits has single-bit error detection, and 1 bit to three bits has single bit error correction (--and 2 bit error detection-- (this isn't right, thinking about it for a second)). After this, the minimum required checksum length growth logarithmically, plus 1 or 2 for detection / correction - and that constant factor makes 1 bit so weird.
- thehappypm 5y agoAll error correction and detection are designed with an acceptable probability of error in mind, which depends on the medium. For example, if you know cosmic rays might flip 1 in a million bits, and you want your system to have 1 error per trillion bits, then you need to send every bit twice to be able to detect a one-in-a-million error.
- necovek 5y agoIt's not only about memory size, but the speed of processing too. Higher level protocols would signal an error, and require a retransmission until no error is detected. However, "majority rule" does indeed sound like an error checking mechanism designed by a non-engineer (or non-mathematician) commitee.
- pinewurst 5y agohttps://www.space-travel.com/reports/NASA_Fixes_Bug_On_Voyager_2_999.html https://www.space-travel.com/reports/NASA_Fixes_Bug_On_Voyag...
- brundolf 5y agoFrom the headline I imagined this was something like "We lost our encryption key for some important data, but the NSA had already cracked or stolen it, so they were able to return it to us"
- account-5 5y agoMe too!
- godelski 5y agoSame, but in reality it was a far more interesting topic. And surprising to see how long it took them to crack it considering they had a priori information for the key (knowing the new key could only be a few bits from the old key).
- lukas099 5y agoIf, hypothetically, the NSA could have found the key faster using classified technology, would they be forced to do it the slower way? Otherwise an uncleared person could surmise that the existence of the classified technology.
- godelski 5y agoI mean there's two possibilities with that, right? If they got lucky they could push immediately and freak everyone out and they could also just sit on the answer for a week. Either way, we get bounds on their capabilities.
- karmanyaahm 5y agoWhy is traffic from Voyager even encrypted? The results back are public scientific data anyway, right? And it's not like other nations (the only ones with power to transmit that far, back then) would send rogue commands without getting caught.
- deleted 5y ago[deleted]
- mlindner 5y agoVoyager launched in 1977 so I find your surprise rather odd. Also it wasn't always so far from Earth that amateurs couldn't reach it.
- bombcar 5y agoWas it? The story is about a spy satellite.
- Strilanc 5y ago> it's not like other nations (the only ones with power to transmit that far, back then) would send rogue commands without getting caught. How would you catch them? Also, these spacecraft didn't start off outside the solar system. They weren't always so far away that a lone prankster would have trouble sending them messages.
- karmanyaahm 5y ago> How would you catch them? Wouldn't they be monitoring whatever frequency it's using? I don't know much about how spacecraft worked in the 70s so maybe it's not practical. > They weren't always so far away that a lone prankster would have trouble sending them messages. That and what mlindner said is a good point. The start of the mission could've been easy to mess with.
- wl 5y agoThe antennas used to send signals to probes are very directional. Monitoring the uplink frequency wouldn't detect someone else sending commands to the probe unless the monitoring receiver was very close to the transmitting antenna or within the transmitting antenna's beam.
- codeflo 5y agoBit flips are scary even on Earth. At a previous job, we had a customer who suddenly couldn’t send us email anymore. When their IT sent us the server logs to “prove” it’s our fault, we saw that the one letter in the cached MX record was wrong. This was puzzling, until I looked at the ASCII table to verify that the difference was exactly one bit. We never found out where in the name resolution process the bit got flipped. The problem healed itself a few days later when the DNS cache expired, so it wasn’t worth further investigation. That really gave me pause how often random bits are wrong in other data.
- captn3m0 5y agoHappens even on end user browsers resulting in bit-flipped domains being looked up: https://securitee.org/files/bitsquatting_www2013.pdf https://securitee.org/files/bitsquatting_www2013.pdf
- lostlogin 5y agoBitsquatting is a great name. I’m not 100% that this isn’t just typosquatting though.
- LanternLight83 5y agoIt might be subset of typosquatting, but it's distinct from what the term usual refers to because the typos that are statistically likely to result from user input (swapping neighboring keys, duplicating or omitting letters, etc) occur manually on the level of keys and characters, where as from those that result from bitflips ("adjacent" bit sequences) occur invisibly / without a manual mistake on the level of bit-/byte-streams, forming two mostly exclusive sets of domains that could be targeted. A determined attacker would likely target both.
- duskwuff 5y agoIt isn't simple typosquatting because it can involve errors that aren't plausible typos (like "mic2osoft.com" for "microsoft.com"), or domains that a user would never enter manually (like "fbcdn.com" or "ytimg.com", which are used for content delivery at Facebook and YouTube, respectively).
- cube00 5y agoThis is what worries me about the current push that all backups including the off site tape vault must be encrypted at rest. Any problem with the de-encryption and your data is toast.
- willis936 5y agoThis is taken care of at the filesystem level.
- javert 5y agoCan you explain what you mean by that?
- willis936 5y agoFilesystems keep checksums of every block of data. If single bits are flipped then they can be corrected. If you encrypt at a lower level than the filesystem then you're at the mercy of that lower level's error correction, but in practice it is rare to encrypt at a lower level. Typically it's done at the filesystem level or higher, including when using self-encrypting drives.
- colejohnson66 5y ago> If you encrypt at a lower level than the filesystem then you're at the mercy of that lower level's error correction, but in practice it is rare to encrypt at a lower level. My understanding is that many SSDs do encryption transparently. The ATA protocol even has a “SECURE ERASE” command that instructs the drive to wipe just the encryption key. This allowed even “bad blocks” to be erased securely.
- willis936 5y agoSSDs have a lot more aggressive error correction than most filesystems because they anticipate a high error rate and are constantly changing the map of logical blocks to physical blocks. Tapes at rest don't have to worry about that though.
- benob 5y agoIs there a way to embed redundancy in a crypto key so that another key a few bits away can still decrypt the data?
- clysm 5y agoDES (and TDES) has 1 parity bit for every 7 bits of key. Nobody really uses it as far as I've seen (e.g. they just generate random keys with invalid parity), but it's built in to the key itself.
- ip26 5y agoParity only tells you the key is corrupt, it can't correct the block :/
- kevin_thibedeau 5y agoEncode it for storage with FEC.
- moyix 5y agoI'm kind of surprised that this took "two weeks, a stable of computers, and billions of combinations tested"? If we make the (generous) assumption that this was using a 128-bit key (more than was common in 1993—the age of DES and 56-bit keys, unless you were using public key crypto – which would be a very strange choice for a military satellite), we have: 256 (2 * 128) keys with 1 bit different 32,512 (2^2 * 128 choose 2) keys with 2 bits different 2,731,008 (2^3 * 128 choose 3) keys with 3 bits different 170,688,000 (2^4 * 128 choose 4) keys with 4 bits different 8,466,124,800 (2^5 * 128 choose 5) keys with 5 bits different So to reach billions of combinations you need 5 bitflips, which seems quite high! But I guess space is a pretty rough environment :)
- zaik 5y agoIt's only (128 choose k) I think. Why are you multiplying with 2^k?
- moyix 5y agoOh, you might be right – I originally had that but second-guessed myself (thinking that once you have the k bit positions, you need to exhaustively search the 2^k possible settings for those bits). I guess for each possible set of positions you only need to check the case where they're all flipped. Without the extra factor you need 6 flipped bits to reach a billion combinations (128 choose 6 is 5,423,611,200). Thanks!
- muhehe 5y agoArticle says "which was only a handful of bits away from the original". As non-native speaker i don't know the exact nuance of handful when considering bits, but it seems a lot
- danachow 5y agoNo a handful in this abstract context (strengthened by the word “only”) means not so many (which given even the power of the computers at the disposal of the NSA at the time was enough to ruin your 2 weeks).
- phendrenad2 5y agoAlways sucks to put into place a triple-redundant system, and a cosmic ray finds the one weak link that wasn't redundant. Space isn't for the faint-hearted.
- drexlspivey 5y agoWhat happens if a bit is flipped in a private key embedded in a HSM? For example the root CA private key or the root cold wallet key for a cryptocurrency exchange? In this case you are not able to alter the public key to correct for the bit flip (like they did with Voyager). I guess if that happens you are toast?
- est31 5y agoYeah same happens if someone tries to open it and the HSM deletes the content, or someone physically burns it, etc. Generally that's why you ideally don't just have one key, but multiple. Ideally with voting, but even if you just replicate the key into a second HSM at a different physical location, it's going to improve your situation a lot.
- aborsy 5y agoI expected NSA will hand over to them the stolen key before bit flip.
- Terry_Roll 5y agoConsidering bit flips were the leading theory for the changed key, I'm surprised it took that long to brute force test for the changed bit(s). Sure I dont know how long the key length was, I dont know how long the encrypted string was, but surely it wouldnt have taken that long to cycle through a number of flipped bits, or would it?
- lovemenot 5y agoSame intuition here. Assuming no miscommunication or subterfuge, perhaps it can be explained by a large number of bits flipped by a single ray and/or a preponderance of rays, each flipping a small number of bits. If the satellite's shielding design was poor, there could have been a lot of exposure from a single event, such as a solar flare. Or perhaps just a single bit of code was flipped and it began writing to protected areas of memory.
- kccqzy 5y agoFor Voyager 2 in particular, the problem was then fixed in May 2010. https://www.space-travel.com/reports/NASA_Fixes_Bug_On_Voyager_2_999.html https://www.space-travel.com/reports/NASA_Fixes_Bug_On_Voyag...
- moyix 5y agoFor a more humorous tale of recovering a private key after a chunk of it was damaged (in this case, replaced by the string "FUCK A DUCK"), see this hilarious CRYPTO 2012 rump session talk: https://crypto.2012.rump.cr.yp.to/87d4905b6d2fbc6ad2389debb73f7035.pdf https://crypto.2012.rump.cr.yp.to/87d4905b6d2fbc6ad2389debb7... There is also a video and a few more details here (starting at 47:38) in their longer CCC talk: https://youtu.be/v_X0gUzGWsA?t=2858 https://youtu.be/v_X0gUzGWsA?t=2858 (Slides for that longer talk: https://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3.pdf https://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3...)
- 310260 5y agoThis is a someone common problem with solar flares and cellular base stations. Bit flips cause odd configurations to show up, sites to become sleepy, or even just straight up go off-air. A simple reset fixes them but it happens more often than you might expect.
- throwaway15908 5y agoWhy are they even encrypting the stuff? 1024 bit key? On such a long term mission, KISS is pretty crucial. EDIT: Probably some military doctrine. For science you monster.
- hoppla 5y agoCan a cosmic rays flip 0’s to 1’s and visa versa, or just in in one direction? Edit: I am thinking of memory chips
- ofiryanai 5y agoI think only 1 to 0, as the cosmic ray cause electrons to "discharge" hence lowering the voltage, assuming that 1 is a little bit higher voltage than 0. But far from an expert in electronics and physics :)
- rvnx 5y agoQuoting the NASA incident report: Updated May 17, 2010 at 5:00 PT. One flip of a bit in the memory of an onboard computer appears to have caused the change in the science data pattern returning from Voyager 2, engineers at NASA’s Jet Propulsion Laboratory said Monday, May 17. A value in a single memory location was changed from a 0 to a 1. On May 12, engineers received a full memory readout from the flight data system computer, which formats the data to send back to Earth. They isolated the one bit in the memory that had changed, and they recreated the effect on a computer at JPL. They found the effect agrees with data coming down from the spacecraft. They are planning to reset the bit to its normal state on Wednesday, May 19.
- themodelplumber 5y agoThat's pretty fascinating. I admit I find it kind of strange that only the encryption key was affected in this way, i.e. that finding the newly-correct key proved a fix to the issues, as opposed to fixing one issue out of many linked to such an event. It made me wonder--what are the odds of that? What is the relative exposure area of the encryption key compared to the rest of the onboard assets which could have been mangled?
- bombcar 5y agoThey probably had to find the key to get it to accept a command to restart and reread the key from ROM.
- mlyle 5y agoThere's basically two things that happen with radiation in orbit. * Ionizing dose weakens and disrupts crystalline structure. Wears things out / degrades their specs. * Single, very high energy particles-- e.g. protons-- come in at high speed and change a voltage somewhere. This can have massively bad effects (e.g. it can, for non-radiation hardened parts, cause parts of the chip not meant to be a transistor to become one shorting power and ground-- this is a "single event latchup"). Or, it can affect the operation of one or a few adjacent bits of memory ("single event upset"). https://en.wikipedia.org/wiki/Single-event_upset https://en.wikipedia.org/wiki/Single-event_upset
- dfranke 5y agoIt probably wasn't the only thing affected. It's just flipping bits in encryption keys has much more dramatic and obvious effect than flipping other random bits in memory. Flip a bit in a raster image and you get one funny-looking pixel. Flip a bit in an AES key and you completely corrupt all the data handled by that key.