[HN Gopher] Calling NSA to find your encryption key after a few ...
___________________________________________________________________
Calling NSA to find your encryption key after a few bits were
flipped (2010)
Author : marcodiego
Score : 132 points
Date : 2022-04-23 19:06 UTC (1 days ago)
(HTM) web link (astroengineer.wordpress.com)
(TXT) w3m dump (astroengineer.wordpress.com)
| Terry_Roll wrote:
| Considering 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?
| moyix wrote:
| I'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 wrote:
| It's only (128 choose k) I think. Why are you multiplying with
| 2^k?
| moyix wrote:
| Oh, 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 wrote:
| Article 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
| codeflo wrote:
| Bit 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.
| jdsampayo wrote:
| Veritasium has a video explaining cases of bit flip that maybe
| you find interesting:
|
| https://youtu.be/AaZ_RSt0KP8
| baruchel wrote:
| Bit flips are quite useful for sorting huge arrays of data:
| https://news.ycombinator.com/item?id=28766154
| charcircuit wrote:
| That's not a proper sort. A sort is not just a function that
| takes in a list and returns a list that is sorted. The result
| must also include all of the elements that you had when
| starting. That property isn't checked by the code you linked.
| layer8 wrote:
| Someone should calculate how many copies of the array you
| need (as a function of input data size) to make that
| sorting strategy work with reasonable assurance that the
| original data is maintained.
| [deleted]
| smegma2 wrote:
| That code has a race condition :^)
| captn3m0 wrote:
| Happens even on end user browsers resulting in bit-flipped
| domains being looked up:
| https://securitee.org/files/bitsquatting_www2013.pdf
| lostlogin wrote:
| Bitsquatting is a great name. I'm not 100% that this isn't
| just typosquatting though.
| LanternLight83 wrote:
| It 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.
| daniel-cussen wrote:
| I have super bivalent opinions about Intel. This is the
| opposite of ambivalent, it means heavily charged in both
| directions, but cancellation is not allowed.
|
| So that's why they should have let all their chips do ECC
| instead of making it a premium feature, it would have been
| better for their brand as "Chipzilla" and had no real cost. And
| it's dangerous! In fact a soft-error at sea level killed an
| operating system update on me, lost about tens of thousands of
| data and money. I have standing to sue Intel, until this
| sentence clause in which I hereby forfeit the suit, together
| with requesting them to reconsider ECC (error correction codes)
| in all their chips as a safeguard needed due to Moore's Law,
| which was their business plan. Just give it a thought, Intel.
| nix23 wrote:
| It's your error, having a system with important data no
| actual/realtime backup no second system and no plan to
| recover from a failed update and no ecc is YOUR error alone.
|
| However, intel should have made ecc the standard and not just
| for 1000$+ Xeons.
| gjvc wrote:
| >However, intel should have made ecc the standard and not
| just for 1000$+ Xeons.
|
| Agree 100%. IMHO, the choice between "domestic" and
| "industrial-strength" should not mean choosing between
| different degrees of risks of failure.
| mrlonglong wrote:
| I gather DDR5 will have ECC as standard du to the extreme
| density of memory that will bitflip a lot more than
| usual. Yay fo r consumers.
| kmeisthax wrote:
| DDR5 supports on-chip ECC but the extra parity bits we
| typically associate as "ECC" are still as optional as
| ever, motherboard manufacturers will still not bother to
| route those signals anyway, and Intel will still demand
| you give up overclocking and pay more for Xeon in order
| to use ECC sticks.
| kklisura wrote:
| Besides hardware mitigations (radiation hardening, ECC memory)
| what would be software mitigation techniques for this?
| NovemberWhiskey wrote:
| Forward-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 wrote:
| To 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 wrote:
| So in this context, send the message with three different
| encryption keys?
| sodality2 wrote:
| This 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 wrote:
| If 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.
| sroussey wrote:
| They do this in planes, but with different coders for the
| three inputs in case of human coding error as well.
|
| Unfortunately, humans tend to make similar errors at similar
| areas of code when given the same specs.
| themodelplumber wrote:
| That'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?
| mlyle wrote:
| There'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
| dfranke wrote:
| It 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.
| bombcar wrote:
| They probably had to find the key to get it to accept a command
| to restart and reread the key from ROM.
| cube00 wrote:
| This 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 wrote:
| This is taken care of at the filesystem level.
| javert wrote:
| Can you explain what you mean by that?
| willis936 wrote:
| Filesystems 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.
| NovemberWhiskey wrote:
| Block-level encryption in SAN is pretty common.
| jaytaylor wrote:
| Which filesystems support this degree of integrity
| checking? Presumably ZFS, but what about EXT4/3,
| ReiserFS, BTRFS, ZFS, NTFS, and FAT32?
|
| It would be wonderful if they all have the feature, but I
| thought only ZFS was really that paranoid.
| willis936 wrote:
| ZFS and BTRFS have nice online scrubbing features, but
| nearly every filesystem these days is journaling,
| including NTFS and XFS (and its contemporaries).
| Journaling means every block has a checksum. Sure, FAT32
| doesn't have that, but no one should ever have the
| expectation of data integrity on FAT32. You can run
| checkdisk on journaling filesystems to scrub for errors.
| colejohnson66 wrote:
| > 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 wrote:
| SSDs 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.
| meibo wrote:
| Correctly configured RAID setups also make it possible to
| detect and recover errors across drives & data without
| downtime, this is commonly how it's done in datacenters.
| pinewurst wrote:
| https://www.space-travel.com/reports/NASA_Fixes_Bug_On_Voyag...
| kccqzy wrote:
| For Voyager 2 in particular, the problem was then fixed in May
| 2010.
|
| https://www.space-travel.com/reports/NASA_Fixes_Bug_On_Voyag...
| aborsy wrote:
| I expected NSA will hand over to them the stolen key before bit
| flip.
| brundolf wrote:
| From 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 wrote:
| Me too!
| godelski wrote:
| Same, 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).
| phendrenad2 wrote:
| Always 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.
| benob wrote:
| Is there a way to embed redundancy in a crypto key so that
| another key a few bits away can still decrypt the data?
| clysm wrote:
| DES (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.
| kevin_thibedeau wrote:
| Encode it for storage with FEC.
| drexlspivey wrote:
| What 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 wrote:
| Yeah 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.
| drdaeman wrote:
| I 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 wrote:
| This 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 wrote:
| Isn't the use case the ability to change the encryption key in
| case it's compromised?
| karmanyaahm wrote:
| Why 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]
| Strilanc wrote:
| > 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.
| mlindner wrote:
| Voyager 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 wrote:
| Was it? The story is about a spy satellite.
___________________________________________________________________
(page generated 2022-04-24 23:00 UTC)