Patent Description:
Flash memories and, in particular, embedded flash memories may store confidential data and, hence, should be protected from eavesdropping ("hacking").

<CIT> describes multiple embodiments for enhancing security and preventing hacking of a flash memory device. The embodiments prevent malicious actors from hacking a flash memory chip to obtain data that is stored within the chip. The embodiments include the use of fault detection circuits, address scrambling, dummy arrays, password protection, improved manufacturing techniques, and other mechanisms. <CIT>relates to an apparatus and a method for transferring data between a processing circuit and a memory. <CIT> relates to a system for securing a secret word during a read of the secret word from a read-only memory (ROM). <NPL>, relates to technical fields of parallel algorithms and architectures and discloses asymptotically tight bounds for performing BMMC permutations on parallel disk systems.

The following disclosure serves a better understanding of the present invention. An embodiment of the present invention that is described herein provides a memory device including a non-volatile memory (NVM) and a secure-programming circuit (SPC). The SPC is configured to receive a program-NVM instruction to program a given data word in a given location of the NVM, and, responsively to receiving the program-NVM instruction, to program bits of the given data word in the NVM in a random order.

In some embodiments, the given data word consists of two to the power of N bits, and the SPC is configured to generate a random permutation of two to the power of N values, and to program the bits of the given data word in an order that follows the random permutation. In an embodiment the SPC is configured to generate the random permutation by multiplying an invertible binary matrix by a vector including respective bits of a count so as to produce a product, and adding a vector of random bits to the product. In an exemplary embodiment, the invertible matrix is a triangular binary matrix including a main diagonal, a first triangle and a second triangle, the main diagonal includes "<NUM>" values, the first triangle includes "<NUM>" values and the second triangle includes random bits.

An embodiment of the invention provides a method for secure programming of a non-volatile memory (NVM). The method includes receiving a program-NVM instruction to program a given data word in a given location of the NVM; responsively to receiving the program-NVM instruction, and bits of the given data word are programmed in the NVM in a random order.

Hackers sometimes attempt to obtain the contents of an NVM (or parts thereof) by a side channel attack, for example by monitoring the power consumption, or the radiated electromagnetic energy.

In particular, integrated circuits that comprise both a flash memory and read/write circuitry to read and write the flash memory (e.g., a processor with an embedded flash) are usually hard to hack by direct methods, as the data exchange between the read/write circuit and the NVM storage is not directly visible on the external pins of the integrated circuit.

Some flash devices employ a bit-serial programming technique wherein bits of a data word to be programmed are serially written into the NVM storage array. After erasure, the flash cells are typically at a given logic value (e.g., logic <NUM>), and, hence, programming of logic <NUM> value does not consume power, whereas programming of a logic <NUM> consumes a significant amount of energy. By monitoring the power supply currently, a hacker may be able to detect when a logic <NUM> or a logic <NUM> are programmed. If the bits are written in a given order (e.g., from LSB to MSB, or vice a versa), the hacker could easily reconstruct the programmed word.

Embodiments of the present invention that are disclosed herein provide circuits and methods to secure NVM from side channel attacks. In an embodiment, the IC comprises a secure-programming circuit (SPC), that is configured to program words in the flash array at a random bit order; hence, a side-attack will reconstruct a useless random shuffle of the programming word bits.

In some embodiments, the SPC includes a programming word register, configured to store the word to be programmed; a counter, configured to count the bits being programmed, a scrambler, configured to generate random permutations of the count; a multiplexer, configured to select a bit of the programming word register according to the random permutations of the count; and a serial programming circuit, configured to program bits in the flash array with the value selected by the multiplexer.

In some embodiments the scrambler generates random permutations of the count by multiplying an invertible (e.g., triangular) matrix of random bits by a binary representation of the count, and adding a vector of random bits to the product.

<FIG> is a block diagram that schematically illustrates a secure embedded-flash integrated-circuit (IC) <NUM> that is subject to a side-channel attack <NUM> in accordance with an embodiment of the present invention.

The IC <NUM> includes a processor <NUM> and a flash memory array <NUM> (in some embodiments, other types of non-volatile memory may be used). In an embodiment, the flash memory array <NUM> includes a plurality of banks; each bank includes a plurality of words, and each word includes a plurality of individual non-volatile cells. In some embodiments each cell stores one bit.

When processor <NUM> erases a bank, all cells in the bank are set to a known logic value. Traditionally the erase value is arbitrarily denoted as logic <NUM>; thus, no action is needed to program a logic <NUM> in a flash cell of an erased bank.

To program a word (e. , <NUM> bits) in an erased bank of flash memory array <NUM>, the processor <NUM> sends a programming instruction to a secure-programming circuit (SPC) <NUM>. The programming instruction may include an address field that the SPC stores in a programming address register <NUM>, and a data field that the SPC stores in a programming data register <NUM>. A multiplexer <NUM> sequentially selects bits of the programming data register and forwards the selected bits to a bit programmer circuit <NUM>, which is configured to program one bit at a time at a flash memory array word that is pointed to by programming address register <NUM>. As explained above, programming is done only to programming data register bits that are at logic <NUM>.

A hacker <NUM> attempts to read that data that the programmer circuit <NUM> programs in the flash memory array <NUM>. The hacker uses a side channel attack and observe the power supply current Idd that IC <NUM> consumes, using a current probe <NUM> that is input to an oscilloscope <NUM>. As mentioned, the current consumption of IC <NUM> is significantly higher when the programming circuit programs a logic <NUM> than it is when a logic <NUM> is programmed. Thus, by observing a waveform <NUM> displayed on the oscilloscope screen, the hacker can tell when a logic <NUM> is programmed.

However, according to the example embodiment illustrated in <FIG>, the order of the programmed bits is random, and the hacker will not be able to reconstruct the written data word. For example, if IC <NUM> programs a security key in the flash memory array <NUM>, the key that the hacker will read will be bit-scrambled.

To randomize the order in which the bits of programming data register <NUM> are programmed, the SPC <NUM> further includes: a counter <NUM>, which is configured to count the programmed bits; and a scrambler <NUM>, which randomly scrambles the output of the counter, using a one-to-one random mapping. The multiplexer <NUM> is coupled to the output of the scrambler <NUM> and will thus randomly select bits of programming data register <NUM> to be programmed. For example, assuming an <NUM>-bit programming data register, scrambler <NUM> may output the sequence <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, which will be the order in which the programming circuit programs the word in the flash memory. The output of the scrambler <NUM> is also the bit-address input of programming circuit <NUM>.

In the context of the present invention and in the claims, the term "random" (as used, for example, in "random order", "random bits", "random sequence", "random permutation", etc.), in various grammatical forms, refers to both truly random and pseudorandom values or events.

The configuration of channel-attack scenario <NUM>, and the configuration of SPC <NUM>, including SPC <NUM>, illustrated in <FIG> and described herein above are examples that are cited for the sake of conceptual clarity. Configurations may be used in alternative embodiments. For example, in an embodiment, the side channel that the hacker uses may be the return current to the Vdd pin (not shown); in another embodiment the hacker may measure a voltage drop across a resistive or an inductive path in the printed circuit. In some embodiments, the hacker measures electromagnetic radiation emitted from IC <NUM>, and in yet other embodiments the hacker may use other means such as a microphone, an infra-red detector, and others.

In an embodiment, the counter <NUM>, the scrambler <NUM>, the programming data register <NUM> and the multiplexer <NUM> are not needed. Instead, the processor <NUM> sends bits, in a scrambled order, to the programming circuit <NUM>.

In some embodiments, the flash memory array stores two or more bits per cell. For example, in an embodiment of a flash memory cell may be not-programmed, weakly programmed, mediumly programmed and strongly programmed. The four states typically represent two stored bits, having the value of <NUM>, <NUM>, <NUM> and <NUM>, respectively. (weak, medium or strong relate to a measure of the charge trapped in a floating gate of the flash cell. ) A hacker can tell if a <NUM>, <NUM>, <NUM> or <NUM> is programmed to a flash memory cell by observing the current from the Vdd supply; however, in an embodiment, the order of the bit-pairs are scrambled, and the hacker will get a scrambled collection of bit-pairs.

<FIG> is a flowchart <NUM> that schematically illustrates a method for a secure flash programming in accordance with an embodiment of the present invention. The flowchart is executed by a SPC <NUM> (see <FIG>).

The flowchart starts at a receive-programming-word operation <NUM>, wherein the SPC receives a programming instruction (e.g., from processor <NUM> in <FIG>) including an address word and a data word to be programmed in flash memory array <NUM> (see <FIG>). The data word may be a secret, e. , a cypher key.

Next, in a random-permute operation <NUM>, the IC generates a permutation map of all bits of the programming word. Such a permutation map maps each bit position of the programming word to a unique position using a random one-to-one mapping.

The SPC then, at a serial-programming operation <NUM>, serially programs the bits of the programming data word in the flash memory array, at the address indicated by the programming instruction according to the permutated order. For example, if bits <NUM>, <NUM>, <NUM>, <NUM> of the programming data word are mapped to <NUM>, <NUM>, <NUM>, <NUM>, the SPC will first program bit <NUM> of the programming data word, then bit <NUM>, followed by bit <NUM> and bit <NUM>. After operation <NUM> is performed, the flowchart ends.

Thus, according to the example flowchart illustrated in <FIG>, the SPC programs the bits of a programming data word in a flash memory array at the address indicated by the program instruction and at a random bit order, rendering side-channel attacks difficult.

The flowchart illustrated in <FIG> and described above is cited by way of example. Other suitable flowcharts may be used in alternative embodiments. For example, in some embodiments, the SPC <NUM> prepares the permutation map before receiving the program instruction. In an embodiment, the SPC, while programming a bit of the programming data word, determines a next random bit to be programmed from the bits that were not yet programmed.

In embodiments, a plurality of methods to generate the permutation map may be used.

<FIG> is a flowchart <NUM> that schematically illustrates a method for generating a permutation map in accordance with an embodiment of the present invention. The flowchart is executed by the scrambler <NUM> (see <FIG>).

The flowchart starts at a generate random vector operation <NUM>, wherein the scrambler generates a vector V of N random bits, designated rnd<NUM> to rndN-<NUM> (shown below for N=<NUM>):
<MAT>.

Next, at a generate matrix m operation <NUM>, the SPC generates an invertible NxN matrix, in the present example a NxN triangular matrix M, having "<NUM>" values in the main diagonal, random bits (Ri) in one of the two triangles (the triangle above the main diagonal or the triangle below the main diagonal) and having "<NUM>" values in the other triangle. For example, an upper-right-diagonal matrix, having random numbers rndi in the upper-right triangle and "<NUM>" in the lower-left triangle can be used, as shown below (for N=<NUM>):
<MAT>.

The SPC now enters a clear-count operation <NUM>, and clears a count register, indicating that a first bit (starting from <NUM>) is now to be programmed.

Next, the SPC enters a generate Vc operation <NUM>, and generates a vector Vc, including the bits of count (shown below for N=<NUM>):
<MAT>.

Then, at a generate permutation vector operation <NUM>, the SPC generates the permutation vector Vp according to:
<MAT>
where addition is binary exclusive or, and multiplication is a binary AND function. Operation <NUM> is shown below for N=<NUM>:
<MAT>.

The SPC then, at a check-count-done operation <NUM> checks if the permutation of the last bit position (corresponding to count=<NUM>N-l) has been permuted, and, if so, ends the flowchart. If, in operation <NUM>, the count is not done, the SPC enters an increment count operation <NUM>, increments count, and then reenters operation <NUM> to permute the next value of count.

The configuration of flowchart <NUM> is illustrated in <FIG> and described herein above is cited by way of example. Other configurations can be used in alternative embodiments. For example, in alternative embodiments other suitable types of invertible matrices, not necessarily triangular, can be used. As another example, in some embodiments, Sattolo algorithm is used (see, for example, "<NPL>). (However, the Sattolo algorithm is not sequential, and, if used, a suitable circuit should be added to output the permutation bits one by one.

The configurations of IC <NUM>, including SPC <NUM> and the methods of flowcharts <NUM> and <NUM>, illustrated in <FIG> and described herein above, are examples configurations and flowcharts that are shown purely for the sake of conceptual clarity. Any other suitable configurations and flowcharts can be used in alternative embodiments.

The different sub-units of IC <NUM>, including SPC <NUM> may be implemented using suitable hardware, such as in one or more Application-Specific Integrated Circuits (ASICs) or Field-Programmable Gate Arrays (FPGAs), using software, using hardware, or using a combination of hardware and software elements.

The processor <NUM> and/or the SPC <NUM> (see <FIG>) may include one or more general-purpose processors, which are programmed in software to carry out the functions described herein. The software may be downloaded to the processor in electronic form, over a network or from a host, for example, or it may, alternatively or additionally be provided and/or stored on non-transitory tangible media, such as magnetic, optical, or electronic memory.

Claim 1:
A memory device, comprising:
a non-volatile memory (NVM); and
a secure-programming circuit (SPC) (<NUM>) configured to:
receive a program-NVM instruction to program a given data word in a given location of the NVM; and
responsively to receiving the program-NVM instruction, program bits of the given data word in the NVM in a random order,
wherein the memory device is characterized in that the given data word consists of two to the power of N bits,
the SPC (<NUM>) comprises a scrambler (<NUM>) and a counter (<NUM>) and is configured to generate a random permutation of two to the power of N values, and to program the bits of the given data word in an order that follows the random permutation, and is configured
to generate the random permutation by:
generating (<NUM>) a vector (Vn) of random bits through the scrambler (<NUM>);
generating (<NUM>) an invertible binary matrix;
clearing (<NUM>) a count register of the counter (<NUM>), thereby setting a count to zero;
a) generating (<NUM>) a vector (Vc) comprising respective bits of the count;
b) multiplying (<NUM>) the invertible binary matrix by the vector (Vc) comprising the respective bits of the count to produce a product;
c) adding (<NUM>) the vector (Vn) of the random bits to the product;
d) checking (<NUM>) if the count equals to <NUM>N -<NUM>;
e) if the count is not equal to <NUM>N -<NUM>, incrementing the counter (<NUM>) and repeating steps a)-e).