Re: [RFC PATCH 0/3] mtd: nand: add randomizer support
On Thu, May 01, 2014 at 10:56:06PM +0200, Boris BREZILLON wrote: > > However, with a synchronous scrambler the security concern boils down > > to how robust and unpredictable is the PRBS. > > I'm not sure security is the main concern here. > AFAICT, NAND scramblers (note that I stopped using the name "randomizer" > :-)) is mainly used to avoid large island of identical data, because > some NAND chips are sensible to such patterns (see [1] page 14). Right, if you send to the flash 'the wrong data' then some combination of: 1) Retention time till ECC failure is reduced 2) The flash block is permanently damaged early 3) A 'nearby', unrelated flash block has ECC failure due to interference So, if someone deliberately and maliciously defeats the scrambler and deliberately sends in wrong data what happens? 1/3) Delibrate, predictable file system corruption 2) Create device damage and significantly early replacement of the device. All could lead to a DOS attack of some sort, at a minimum. FWIW, there was a similar attack against a certain communication system. The line scrambler was statistically predictable, and if an attacker sent enough packets that were the predictable anti-scramble then enough would align with the scamble pattern and the communication channel would fail and retrain creating a DOS vector. For this reason these days com systems tend to use a 58 bit self-synchronous LFSR for scrambling purposes. > And this is exactly what's done in the sunxi HW scrambler > implementation, or at least you can do it based on what you're > specifying in your DT (see the "nand-randomizer-seeds" in the 3rd > patch): you can define a seed table and the seed is selected based on > the page number you're reading or writing. Well, re-using fixed (and public) seeds: state = rnd->seeds[page % rnd->nseeds]; Just changes the probabilities. For instance, some filesystems can be asked to create extents with a large alignment (like 2M) to speed IOs, and a small seeds table means the seeds within such a file will be fully predictable. If you are already stuck with this, then fine, it can be a driver specific binding - but if this is a new green-field design, intended to be broadly used as a core MTD feature: I'd suggest just seeding with the block number xor some value, and using a LFSR with a state space larger than the number of blocks in the device, and don't specify a seeds array in DT. Regards, Jason -- To unsubscribe from this list: send the line "unsubscribe devicetree" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC PATCH 0/3] mtd: nand: add randomizer support
On 01/05/2014 19:59, Jason Gunthorpe wrote: > On Thu, May 01, 2014 at 07:31:13PM +0200, Boris BREZILLON wrote: > >> I totally agree with you, this is not a randomizer but rather a scrambler. >> The reason I chose the "randomizer" word is that all the documents I >> read are talking about randomizers. >> But, other than I don't have any concern about changing all references >> to "randomizer" into "scrambler" ;-). > If nobody else says anything, Scrambler is at least consistent with > Wikipedia.. > > and 'descrambler' sounds better than 'unrandomizer' :) > >>> BTW, there are security concerns here. The scrambler PRBS must not be >>> predictable by the user, otherwise they can write data that undoes the >>> scramble and defeat it, ie deliberately writing the last 2k of a 4k >>> write block as all 0's after scrambling could cause the first 2k to be >>> lost. That feels like something that could be scary .. >> AFAICT, the scramblers/randomizers used in NAND applications are all >> predictable, which means the scrambler state does not depend on the last >> data being scrambled. > Right, I'm not surprised storage would use a synchronous scrambler, > self-synchronizing scramblers make the most sense for communication.. > > However, with a synchronous scrambler the security concern boils down > to how robust and unpredictable is the PRBS. I'm not sure security is the main concern here. AFAICT, NAND scramblers (note that I stopped using the name "randomizer" :-)) is mainly used to avoid large island of identical data, because some NAND chips are sensible to such patterns (see [1] page 14). > > For instance, re-using the same PRBS seed and staring point for every > block is probably a bad idea. The proposed solution leave the scrambling process to the scrambler implementation, thus it is possible to provide a different seed for each block. And this is exactly what's done in the sunxi HW scrambler implementation, or at least you can do it based on what you're specifying in your DT (see the "nand-randomizer-seeds" in the 3rd patch): you can define a seed table and the seed is selected based on the page number you're reading or writing. > > At the very least I would think the block number should be included in > the per-block seed of the PRBS. > > And also a per-parition/device global seed.. Actually the seed table is configurable per-partition and this is why I depend on the "per-partition ECC config" series. Best Regards, Boris [1] http://www.bswd.com/FMS09/FMS09-T2A-Grunzke.pdf -- Boris Brezillon, Free Electrons Embedded Linux and Kernel engineering http://free-electrons.com -- To unsubscribe from this list: send the line "unsubscribe devicetree" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC PATCH 0/3] mtd: nand: add randomizer support
Hi Boris, On Thu, May 01, 2014 at 03:09:49AM +0200, Boris BREZILLON wrote: > Hello, > > This series is a proposal to add support for randomizers (either software > or hardware) to NAND flash controller drivers. Thanks for providing this! I'll need these features soon and I'm happy to see them coming into the nand controller framework. Antoine > The last patch is the sunxi HW randomizer implementation and is just given > as an example (it won't apply on the MTD tree, because it depends on other > stuff not yet posted on the MTD ML, but if you want a full overview of the > NAND Flash controller driver you can take a look at this series [2]). > > I can also provide a software implementation based on LFSR (Left Feedback > Shift Register) algorithm, thought I haven't tested it yet, hence why it's > not part of this series. Let me know if you're interested in this > implementation. > > This series depends on the "per-partition ECC" series [1], because I need > the randomizer seed to be different depending on the partition (for the > same reason I needed ECC config to be different for each partition: the > bootrom config might not fit the NAND chip requirements). > > I'd like to have feedback from both MTD maintainers and driver > developers who might need to implement (or use) a randomizer in their > system, so feel free to comment on this series. > > Best Regards, > > Boris > > [1] https://lkml.org/lkml/2014/2/12/627 > [2] > https://groups.google.com/forum/#!msg/linux-sunxi/s3lBb01I0Js/z2NoCFJ83g4J > > > Boris BREZILLON (3): > mtd: nand: introduce a randomizer layer in the NAND framework > of: mtd: add NAND randomizer mode retrieval > mtd: nand: add sunxi randomizer support > > drivers/mtd/nand/nand_base.c | 278 ++- > drivers/mtd/nand/sunxi_nand.c | 507 > +- > drivers/of/of_mtd.c | 35 +++ > include/linux/mtd/nand.h | 98 > include/linux/of_mtd.h| 6 + > 5 files changed, 858 insertions(+), 66 deletions(-) > > -- > 1.8.3.2 > > > ___ > linux-arm-kernel mailing list > linux-arm-ker...@lists.infradead.org > http://lists.infradead.org/mailman/listinfo/linux-arm-kernel -- Antoine Ténart, Free Electrons Embedded Linux, Kernel and Android engineering http://free-electrons.com -- To unsubscribe from this list: send the line "unsubscribe devicetree" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC PATCH 0/3] mtd: nand: add randomizer support
On Thu, May 01, 2014 at 07:31:13PM +0200, Boris BREZILLON wrote: > I totally agree with you, this is not a randomizer but rather a scrambler. > The reason I chose the "randomizer" word is that all the documents I > read are talking about randomizers. > But, other than I don't have any concern about changing all references > to "randomizer" into "scrambler" ;-). If nobody else says anything, Scrambler is at least consistent with Wikipedia.. and 'descrambler' sounds better than 'unrandomizer' :) > > BTW, there are security concerns here. The scrambler PRBS must not be > > predictable by the user, otherwise they can write data that undoes the > > scramble and defeat it, ie deliberately writing the last 2k of a 4k > > write block as all 0's after scrambling could cause the first 2k to be > > lost. That feels like something that could be scary .. > > AFAICT, the scramblers/randomizers used in NAND applications are all > predictable, which means the scrambler state does not depend on the last > data being scrambled. Right, I'm not surprised storage would use a synchronous scrambler, self-synchronizing scramblers make the most sense for communication.. However, with a synchronous scrambler the security concern boils down to how robust and unpredictable is the PRBS. For instance, re-using the same PRBS seed and staring point for every block is probably a bad idea. At the very least I would think the block number should be included in the per-block seed of the PRBS. And also a per-parition/device global seed.. I suspect even a properly seeded LFSR is sufficent, but by no means have I studied this :) > For example, the sunxi HW scrambler is using a Fibonacci LFSR [1]. > Do you have any example of non predictable scrambler that are used to > scramble NAND data ? The benifit here is that the scrambled data is completely private to the driver and flash chip. So any attack on the scrambler would have to use the driver as some kind of oracle to search for synchornization. Eg running through the full keyspace of an N-Bit LFSR by writing an anti-scrambled block, reading it back and checking if it is corrupted. This is why per-block randomization of the PRBS is very important - if the attacker has only filesytems access then they don't know the block number and now have to attack the filesystem block allocator as well as the LFSR block-independent seed to generate an anti-scrambler data pattern. But that is just an off the cuff feeling. It would be smart to study it further :) Regards, Jason -- To unsubscribe from this list: send the line "unsubscribe devicetree" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC PATCH 0/3] mtd: nand: add randomizer support
On 01/05/2014 18:34, Jason Gunthorpe wrote: > On Thu, May 01, 2014 at 03:09:49AM +0200, Boris BREZILLON wrote: >> Hello, >> >> This series is a proposal to add support for randomizers (either software >> or hardware) to NAND flash controller drivers. > FWIW, I think the term for reversibly combining a PRBS with data is > 'scrambling', it is often used in communication systems for similar > reasons - probabilisticly increasing transition density. > > randomizing is something else entirely :) I totally agree with you, this is not a randomizer but rather a scrambler. The reason I chose the "randomizer" word is that all the documents I read are talking about randomizers. But, other than I don't have any concern about changing all references to "randomizer" into "scrambler" ;-). > > BTW, there are security concerns here. The scrambler PRBS must not be > predictable by the user, otherwise they can write data that undoes the > scramble and defeat it, ie deliberately writing the last 2k of a 4k > write block as all 0's after scrambling could cause the first 2k to be > lost. That feels like something that could be scary .. AFAICT, the scramblers/randomizers used in NAND applications are all predictable, which means the scrambler state does not depend on the last data being scrambled. For example, the sunxi HW scrambler is using a Fibonacci LFSR [1]. Do you have any example of non predictable scrambler that are used to scramble NAND data ? Best Regards, Boris -- Boris Brezillon, Free Electrons Embedded Linux and Kernel engineering http://free-electrons.com -- To unsubscribe from this list: send the line "unsubscribe devicetree" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC PATCH 0/3] mtd: nand: add randomizer support
On Thu, May 01, 2014 at 03:09:49AM +0200, Boris BREZILLON wrote: > Hello, > > This series is a proposal to add support for randomizers (either software > or hardware) to NAND flash controller drivers. FWIW, I think the term for reversibly combining a PRBS with data is 'scrambling', it is often used in communication systems for similar reasons - probabilisticly increasing transition density. randomizing is something else entirely :) BTW, there are security concerns here. The scrambler PRBS must not be predictable by the user, otherwise they can write data that undoes the scramble and defeat it, ie deliberately writing the last 2k of a 4k write block as all 0's after scrambling could cause the first 2k to be lost. That feels like something that could be scary .. Jason -- To unsubscribe from this list: send the line "unsubscribe devicetree" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html