Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Calling NSA to find your encryption key after a few bits were flipped (2010)

astroengineer.wordpress.com

Post reply on HN
Print view View original

91–100 of 125 posts

Re: Calling NSA to find your encryption key after a few bits were flipped (2010)

#91

Post by wyldfire »

daniel-cussen wrote: post #22
codeflo wrote: post #12

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 flip…

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 upda…

> had no real cost.

Can you expand on that? Typical coding schemes use redundancy to be able to detect failures. I'm no info theory expert but I presume there's always a cost. And if you can design a smart enough algorithm you can balance the cost with the actual likelihood of failure to find some kind of equilibrium. Of course the algorithm development has its own cost (NRE, time-to-market).

It's not clear whether you're talking about modern computers or dawn-of-PCs when you say "should have." It might be smaller cost now but back in the day it would have been mega expensive.

Re: Calling NSA to find your encryption key after a few bits were flipped (2010)

#92

Post by hvdijk »

charcircuit wrote: post #44
baruchel wrote: post #36

Earlier quoted context omitted.

Bit flips are quite useful for sorting huge arrays of data: https://news.ycombinator.com/item?id=28766154

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.

Do you know of any sort routine that guarantees the result includes all of the input elements even in the event of random bit flips? If not, do you consider the sorting routines in your everyday libraries improper as well or is that a special restriction reserved for this particular implementation?

Re: Calling NSA to find your encryption key after a few bits were flipped (2010)

#93

Post by wyldfire »

jagger27 wrote: post #79
bcrosby95 wrote: post #74

Earlier quoted context omitted.

You're unlikely to notice a single bit flip in a picture you take.

I just tested this on a JPEG. Flipping any bit in the first few bytes of a JPEG renders it unopenable on my Fedora system. I get that it's just a header and could probably be fixed, but there are consequences for bitflips, even on images.

Consider the likelihood of the bitflip occuring in the critical area you targeted versus any old place in the file. The file is dominated by encoded raster info.

Most errors like the bitflips we discuss are not correlated with file locations. They're typically medium errors and the design of typical filesystems will result in something closer to uniform distribution of errors. Bus errors could perhaps be correlated with the start of activity but I think that seems uncommon.

Re: Calling NSA to find your encryption key after a few bits were flipped (2010)

#94

Post by lukas099 »

godelski wrote: post #55
brundolf wrote: post #9

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"

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).

If, 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.

Re: Calling NSA to find your encryption key after a few bits were flipped (2010)

#95

Post by godelski »

lukas099 wrote: post #94
godelski wrote: post #55

Earlier quoted context omitted.

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).

If, 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.

I 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.

Re: Calling NSA to find your encryption key after a few bits were flipped (2010)

#96

Post by tshaddox »

hvdijk wrote: post #92
charcircuit wrote: post #44

Earlier quoted context omitted.

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.

Do you know of any sort routine that guarantees the result includes all of the input elements even in the event of random bit flips? If not, do you consider the sorting routines in your everyday libraries improper as well or is that a special restriction reserved for this particular implementation?

No, when we normally talk about code we have some vague notion of a formal system that works according to its specification, and thus that !isSorted loop example is pretty clearly invalid. And even if you do allow for random bit flips, surely that’s more likely to happen to the boolean returned by isSorted than for enough bits to flip to make the array sorted.

Re: Calling NSA to find your encryption key after a few bits were flipped (2010)

#97

Post by jakear »

moyix wrote: post #26

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 choo…

That's assuming NSA told the world (/ people who go around posting stories about their day-job to the internet) immediately after succeeding with the crack. Much better opsec to wait a for a period at least as big as the time it took to crack, leaks less information about the magnitude of compute you can harness.

Re: Calling NSA to find your encryption key after a few bits were flipped (2010)

#98

Post by danachow »

muhehe wrote: post #39
moyix wrote: post #26

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 choo…

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

No 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).

Re: Calling NSA to find your encryption key after a few bits were flipped (2010)

#99

Post by hvdijk »

tshaddox wrote: post #96
hvdijk wrote: post #92

Earlier quoted context omitted.

Do you know of any sort routine that guarantees the result includes all of the input elements even in the event of random bit flips? If not, do you consider the sorting routines in your everyday libraries improper as well or is that a special restriction reserved for this particular implementation?

No, when we normally talk about code we have some vague notion of a formal system that works according to its specification, and thus that !isSorted loop example is pretty clearly invalid. And even if you do allow for random bit flips, surely that’s more likely to happen to the boolean returned by isSorted than for enough bits to flip to make the array sorted.

The objection that the GP raised, the lack of a check that the result includes all of the elements of the input, is not needed under your notion of a system that works according to its specification, as according to that specification it is a loop invariant. It is also not useful, as it is an infinite loop. Your view of why cosmic ray sort is not a proper sort therefore contradicts GP's explanation, even if you share the GP's conclusion. My question was aimed at further exploring the GP's view; I think an opposing view does not help here.

Re: Calling NSA to find your encryption key after a few bits were flipped (2010)

#100

Post by danachow »

willis936 wrote: post #46
jaytaylor wrote: post #37

Earlier quoted context omitted.

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.

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.

> Journaling means every block has a checksum.

No it doesn’t.

Many journal filesystems use a checksum for log entries, but that is certainly not covering every block of the filesystem with a checksum. And that checksum only comes into play during log recoveries. Once a block is committed to disk there is no checksum in play (unless the fs has special support for it).

Some newer journaling filesystems support metadata checksumming, but that is not some requirement to be journaling. XFS has not always supported metadata checksumming, and it’s a relatively recent addition to ext4 (like last decade). NTFS doesn’t do checksums on even metadata. This is one reason why ReFS is a thing.

Post reply on HN