5
$\begingroup$

I'm looking for a cryptographic algorithm that allows encrypting only 8 bits of data in a block. Is there any such algorithm that is considered secure?

The reason I'm asking is because I have to encrypt and decrypt the data contained in SPI Flash memory (the BIOS flash), and I need it to be really fast to get the cyphertext and give the plaintext to the CPU. The CPU can fetch 8 bits at a time, and can jump to a different address each time.

$\endgroup$
  • 5
    $\begingroup$ It is totally insecure by any means. $\endgroup$ – sashank Aug 24 '15 at 11:00
  • 1
    $\begingroup$ Does it have to be a block cipher? $\endgroup$ – Thomas Aug 24 '15 at 11:06
  • $\begingroup$ Yes, because I have to encrypt and decrypt the data contained in a SPI Flash ( the bios flash ), and I've to be really fast to get the cyphertext and give the plaintext to the CPU. The CPU can fetch 8 bit each time and can jump to different address each time. $\endgroup$ – haster8558 Aug 24 '15 at 11:08
  • $\begingroup$ It isn't difficult to implement a secure block cipher with an 8 bit block size. But I cannot come up with any meaningful mode which would be secure when used with such a cipher. It sounds like you intend to use ECB mode, which is just about the worst you can do. With such a small block size ECB mode is totally insecure even if the block cipher is perfectly secure. $\endgroup$ – kasperd Aug 24 '15 at 21:23
  • $\begingroup$ I do not know of any. Smallest I know of take 32 bit blocks. This is processed as 2 16-bit words, so it would work fine in many 16 bit machines, but 8 bits is tough. $\endgroup$ – WDS Aug 25 '15 at 3:39
7
$\begingroup$

First of all, there's no such thing as a secure 8-bit block cipher, at least not as such things are conventionally used.

That's because there are only 256 possible values for an 8-bit byte, and a block cipher will map each of these values to a different fixed value. Thus, an attacker who can even occasionally guess the unencrypted value of some bytes (or, worse yet, can control the bytes to be encrypted) can easily learn which unencrypted byte corresponds to many, if not all, the encrypted bytes. In fact, even if the attacker only had access to the encrypted data, they could most likely still decrypt much of it simply by comparing the frequencies of different encrypted bytes, and the patterns in which the bytes occur, with known examples of typical BIOS contents.


If you had a fast, key-agile block cipher, you could in theory make this attack a lot harder by using a separate key (typically, generated "on the fly" from a master key and the byte address) to encrypt each byte. If the data never changed, and assuming that the keys were effectively independent (or at least independent enough to avoid related-key attacks), this could be secure; indeed, even if the data did sometimes change, all that observing multiple versions of the encrypted data would leak is whether the value of a particular byte matched an earlier value of the same byte.

Alas, I'm not aware of any fast, key-agile 8-bit block ciphers with a good track record of resisting cryptanalysis. (That doesn't prove that there aren't any, of course.)


However, you could instead go further, and encrypt each bit separately. Of course, there's only one possible 1-bit block cipher*, and it has only two possible keys: 0, which leaves the bit unchanged, and 1, which flips it. Thus, "1-bit block cipher" is really just a fancy name for XOR.

You still need to generate an independent key bit to XOR each of your data bits with, of course. For that, you need a stream cipher. In particular, since you say you need random access to the data, I'd suggest using a (conventional, wide-block) block cipher in CTR mode as your stream cipher.

As long as your data never changes, XORing it with a keystream generated by a conventional block cipher (e.g. AES) in CTR mode actually is semantically secure.

With CTR mode, you can generate any (e.g.) 128-bit block of the keystream any time you like, without having to generate all the preceding bits of the keystream first. As a simple performance optimization, consider caching the most recently computed keystream block in a register, just in case the next byte to be requested falls inside the same block. You could even optimistically start pre-calculating the next block before you actually need it, if you expect a lot of sequential reads in practice.


However, note that CTR mode (and stream ciphers in general) may be insecure if the data can change. In particular, as soon as an attacker learns both the encrypted and the unencrypted value of a given byte (or even a given bit), they'll learn the corresponding bits of the keystream. Further, even just observing two different encrypted values read from the same address will reveal the bitwise difference of the corresponding plaintext values.

Avoiding such attacks is the domain of disk encryption theory, and can get rather tricky in general, especially if you demand that no extra storage space be used.

However, if you can set aside a bunch of (say, 16 or 32) bits in each Flash memory block to store a write counter, and are fine with the value of this counter being leaked if someone inspects the encrypted data, there may be a simple solution: just use this write counter together with the byte address (truncated to cipher block boundaries, of course) as the counter value. That way, every time a Flash block is rewritten, the keystream for that block changes completely.

Of course, this means that you can't store data in the bits used for the counter, which, in particular, could complicate addressing, since the "logical block size" seen by the CPU will be slightly smaller than the physical block size of the Flash memory. There are various tricks you might be able to use to get around that, but they depend on the specs of the system you're working with.

Also note that CTR mode encryption (like stream ciphers in general) is particularly malleable, and therefore potentially culnerable if an attacker may modify the encrypted data in the Flash memory. To prevent such attacks, you may also want to store a (possibly per-block) MAC of the encrypted data, and verify it before allowing any data to be read. (Note that the MAC input should include the block number and the write counter / IV, to protect against attacks involving swapping blocks or resetting the counter. If you're using per-block MACs, you may also wish to compute a global "MAC of MACs" to prevent an attacker from mixing blocks from different versions of the data.)


*) Technically, there are two 1-bit block ciphers, but they differ only by a trivial rearrangement of the key space.

$\endgroup$
  • $\begingroup$ Many flash memory devices have a physical blocks that are multiples of 528 bytes, rather than 512, which may ease addressing issues. $\endgroup$ – supercat Aug 24 '15 at 19:52
  • $\begingroup$ +1, for the second paragraph, basically porting ECB mode's weakness from per-message to over time. And also note: The worst point about CTR isn't learning the key-stream. But if the attacker knows or strongly suspects that there's a given value encrypted, he may do significant damage to the system by flipping (some of) the bits (and therefore flipping the corresponding plaintext bits). $\endgroup$ – SEJPM Aug 24 '15 at 20:05
  • $\begingroup$ @SEJPM: That's a very good point. I originally meant to suggest using a MAC for integrity protection, but forgot that while writing the answer. I've corrected that omission now. $\endgroup$ – Ilmari Karonen Aug 24 '15 at 21:05
4
$\begingroup$

An 8-bit block cipher would be practically unusable.

A $b$-bit PRP can be used fewer than $2^{b/2}$ times before it's distinguishable from PRF and this limit carries over approximately as is to block ciphers. So you could use it (less than) 16 times per key, i.e. for 128 bits of data. If you had a 128-bit key you might as well use it as a one-time pad.

If you just need to be able to encrypt/decrypt data in 8-bit increments, some kind of stream cipher could work.

$\endgroup$
  • 1
    $\begingroup$ In particular, if random access is needed, using a (conventional, e.g. 128-bit) block cipher in CTR mode as your stream cipher could be a good choice. But do note that CTR mode, like stream ciphers in general, may be insecure if the data can change. $\endgroup$ – Ilmari Karonen Aug 24 '15 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.