3 ms·

My EE knowledge is a few years out of date, but I was surprised to learn that excessive correlation between pages causes problems. The XOR key used for decorrel

by aaron_l 12y ago

My EE knowledge is a few years out of date, but I was surprised to learn that excessive correlation between pages causes problems. The XOR key used for decorrelation is apparently not too hard to reverse engineer, so I wonder if this could be turned into an attack against solid state storage devices. Would storing a particular data stream which becomes very correlated once the XOR is applied lead to data corruption? Wear leveling and filesystems might make this difficult to pull off, but it still scares me a bit.

jwise0 12y ago
I also wondered this! I suspect it should be possible to do that; it would certainly be an interesting attack vector to try on cloud storage systems...
bahahah 12y ago
Due to close physical proximity, there will always be some degree of capacitive coupling between the cells. This coupling will cause a cell's potential to increase slightly when its neighbors are programmed. Having all of your neighbors programmed to the highest potential state is the worst case, as your delta V from coupling is greatest. If it is shifted enough, there would be a bit error at that cell. Data randomization seeks to mitigate this issue by normalizing the distribution of states across the page. Having a single XOR key wouldn't do a very good job for the reasons you noted. When I worked on flash, we used elements of the address to seed a PRNG for data randomizing. So the XOR key varies across the entire device. There are other systems in place in flash to further mitigate these issues. All programming is adaptive, using feedback between programming pulses to hit the target. The pages within a block are intelligently ordered so that a programmed cell cannot possibly have all of its neighbors programmed from lowest to highest potential. But yes, in general, if you had the right data stream, you would be able to slightly degrade the BER, possibly past what the ECC can repair. There are a lot of systems in place though, as NAND is inherently lossy to begin with. These issues are compounded by MLC designs which have tighter margins per cell. SSDs have yet another layer of system mitigation. I know of at least one manufacturer that disables NAND level randomizing in favor of encrypting every bit of data that is programmed. Some drives have enough redundancy that they can lose an entire flash die without losing data -- as if losing a disk in a raid setup. You probably shouldn't be storing anything important long term on a device that programs NAND raw. i.e. flash drives and sd cards. They aren't designed nor spec'd for high reliability.
- StillBored 12y ago
  This whole XOR scheme seems destined to fail! Why not just use a 64b/66b (or similar) encoding scheme?
  - bahahah 12y ago
    The XOR scheme is perfectly good enough. If it were a real issue affecting customers it would be replaced (but it isn't). The XOR scheme is extremely cheap (compact) and does not need to operate serially on the data stream (good for performance). The only applications that use the NAND provided randomizer are the cheapest of controllers. In fact, even the SD controller in the linked article used their own XOR scheme. A system designer can always turn off the builtin randomizer, and replace it with whatever method they choose -- they all do for various reasons. At the controller level it can be implemented in, typically, higher performance and more compact logic processes. It does not need to be duplicated for multichannel devices, as it would if it were in the NAND.
    - userbinator 12y ago
      The XOR scheme is perfectly good enough ...until someone finds a way to exploit it, as has happened with CD's "weak sector" copy protection schemes. It's only a matter of when it will happen, not if.
      - bahahah 12y ago
        Corrupting the storage of a test pattern isn't particularly useful. MAYBE, you could cause premature tagging of bad blocks wearing out a flash drive/card faster. If the system you are using is allowing these kinds of writes to your storage device you have more pressing issues. Only the most primitive SD/flash drive controllers actually use this scheme anyway -- encryption is much better at randomizing.
- deleted 12y ago
  [deleted]
userbinator 12y ago
This reminds me of the CD copy-protection schemes that rely on "weak sectors" - data that, once passed through the whitening scheme used for CDs, created long runs of 0s/1s that made them very difficult to read and even more difficult to duplicate in CD-R burners. I agree that it also scares me when certain patterns of data are essentially harder to store than others - and the "solution" is to just make it statistically unlikely, as opposed to using a more robust encoding like RLL that guarantees worst-case behaviour (although requires more overhead). This problem of some sequences of bits being problematic has actually been around for a long time - see http://en.wikipedia.org/wiki/Lace_card http://en.wikipedia.org/wiki/Lace_card for example - and is one of the reasons for the odd character layout of EBCDIC.

by aaron_l 12y ago

jwise0 12y ago

I also wondered this! I suspect it should be possible to do that; it would certainly be an interesting attack vector to try on cloud storage systems...

bahahah 12y ago

Due to close physical proximity, there will always be some degree of capacitive coupling between the cells. This coupling will cause a cell's potential to increase slightly when its neighbors are programmed. Having all of your neighbors programmed to the highest potential state is the worst case, as your delta V from coupling is greatest. If it is shifted enough, there would be a bit error at that cell. Data randomization seeks to mitigate this issue by normalizing the distribution of states across the page. Having a single XOR key wouldn't do a very good job for the reasons you noted. When I worked on flash, we used elements of the address to seed a PRNG for data randomizing. So the XOR key varies across the entire device. There are other systems in place in flash to further mitigate these issues. All programming is adaptive, using feedback between programming pulses to hit the target. The pages within a block are intelligently ordered so that a programmed cell cannot possibly have all of its neighbors programmed from lowest to highest potential. But yes, in general, if you had the right data stream, you would be able to slightly degrade the BER, possibly past what the ECC can repair. There are a lot of systems in place though, as NAND is inherently lossy to begin with. These issues are compounded by MLC designs which have tighter margins per cell. SSDs have yet another layer of system mitigation. I know of at least one manufacturer that disables NAND level randomizing in favor of encrypting every bit of data that is programmed. Some drives have enough redundancy that they can lose an entire flash die without losing data -- as if losing a disk in a raid setup. You probably shouldn't be storing anything important long term on a device that programs NAND raw. i.e. flash drives and sd cards. They aren't designed nor spec'd for high reliability.

StillBored 12y ago
This whole XOR scheme seems destined to fail! Why not just use a 64b/66b (or similar) encoding scheme?
- bahahah 12y ago
  The XOR scheme is perfectly good enough. If it were a real issue affecting customers it would be replaced (but it isn't). The XOR scheme is extremely cheap (compact) and does not need to operate serially on the data stream (good for performance). The only applications that use the NAND provided randomizer are the cheapest of controllers. In fact, even the SD controller in the linked article used their own XOR scheme. A system designer can always turn off the builtin randomizer, and replace it with whatever method they choose -- they all do for various reasons. At the controller level it can be implemented in, typically, higher performance and more compact logic processes. It does not need to be duplicated for multichannel devices, as it would if it were in the NAND.
  - userbinator 12y ago
    The XOR scheme is perfectly good enough ...until someone finds a way to exploit it, as has happened with CD's "weak sector" copy protection schemes. It's only a matter of when it will happen, not if.
    - bahahah 12y ago
      Corrupting the storage of a test pattern isn't particularly useful. MAYBE, you could cause premature tagging of bad blocks wearing out a flash drive/card faster. If the system you are using is allowing these kinds of writes to your storage device you have more pressing issues. Only the most primitive SD/flash drive controllers actually use this scheme anyway -- encryption is much better at randomizing.
deleted 12y ago
[deleted]

userbinator 12y ago

This reminds me of the CD copy-protection schemes that rely on "weak sectors" - data that, once passed through the whitening scheme used for CDs, created long runs of 0s/1s that made them very difficult to read and even more difficult to duplicate in CD-R burners. I agree that it also scares me when certain patterns of data are essentially harder to store than others - and the "solution" is to just make it statistically unlikely, as opposed to using a more robust encoding like RLL that guarantees worst-case behaviour (although requires more overhead). This problem of some sequences of bits being problematic has actually been around for a long time - see http://en.wikipedia.org/wiki/Lace_card http://en.wikipedia.org/wiki/Lace_card for example - and is one of the reasons for the odd character layout of EBCDIC.