Live data from Hacker News

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

astroengineer.wordpress.com

31–40 of 125 posts

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

#31
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…

It's only (128 choose k) I think. Why are you multiplying with 2^k?

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

#32

Earlier quoted context omitted.

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.

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

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.

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

#33
post #31
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…

It's only (128 choose k) I think. Why are you multiplying with 2^k?

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!

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

#34
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…

Veritasium has a video explaining cases of bit flip that maybe you find interesting:

https://youtu.be/AaZ_RSt0KP8

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

#35
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…

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.

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

#36
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…

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

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

#37
post #20

Earlier quoted context omitted.

Can you explain what you mean by that?

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.

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.

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

#38

Earlier quoted context omitted.

Happens even on end user browsers resulting in bit-flipped domains being looked up: https://securitee.org/files/bitsquatting_www2013.pdf

Bitsquatting is a great name. I’m not 100% that this isn’t just typosquatting though.

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.

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

#39
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

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

#40
post #6

Besides hardware mitigations (radiation hardening, ECC memory) what would be software mitigation techniques for this?

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.

So in this context, send the message with three different encryption keys?
Post reply on HN