Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have a file containing 16-bit samples and I want to encrypt it, but the problem is that I need to be able to read any random 16-bit value from the file, and be to able to decrypt it, without reading larger (or surrounding) blocks. Because else it would require huge modifications to the device and driver.

It doesnt need to be very strong encryption, so I thought about just XOR-ing each 16-bit value with a another (fixed) value. But thats not really secure once the plain-text is known. And there are many samples with the value '0' at the start of the stream, so it would be easy to deduce the secret XOR value just by looking to the startblock.

Is there a similar method, that is almost as efficient and low-memory, but offers a little more security than my example above? The encryption may only take a few CPU cycles because its for an embedded MCU, however the decryption will be done using very fast CPU's.

share|improve this question

migrated from stackoverflow.com Oct 8 '13 at 20:44

This question came from our site for professional and enthusiast programmers.

1  
I just want to emphasize that modes that are secure for random reads often aren't secure for random writes. For example CTR mode becomes extremely weak when you do random writes(two-time-pad). –  CodesInChaos Sep 19 '13 at 10:08
    
@CodesInChaos: Good point about not reusing the keystream. See the edit I just made to my answer for some ways to address it. –  Ilmari Karonen Sep 19 '13 at 13:21
1  
Note that XOR encryption with a repeating key is not at all secure. The key can be recovered very, very easily from any ciphertext. –  ntoskrnl Sep 20 '13 at 13:01

4 Answers 4

up vote 5 down vote accepted

Any block cipher in CTR mode can be used to encrypt and decrypt data in arbitrary order.

Basically, to encrypt something in CTR mode, you use the block cipher to encrypt a simple sequence of values, like (1, 2, 3, 4, 5, etc.), and concatenate the results to produce a pseudorandom bitstream, and then XOR this "keystream" with the data you want to encrypt. Since you can produce any block in the keystream at any time just by feeding the appropriate counter value into the block cipher, you can easily decrypt the data in any order.

(Yes, you can even decrypt pieces of data smaller than a single cipher block with CTR mode, even down to a single bit. You do need to compute the keystream block by block, but you don't need an entire block of ciphertext to be able to decrypt it. If reading the ciphertext is much slower than block cipher encryption, this may be a useful optimization, and you can always cache the keystream block in case you need it again.)

The work needed for CTR mode encryption is basically the same as for decryption, and depends on the block cipher you're using. If you can find a usable AES implementation for your MCU, I'd recommend using it; it's a standard, widely used and well analyzed cipher. As they say, nobody ever got fired for using AES. If AES is too much for your MCU, you may want to look at specialized lightweight block ciphers like PRESENT instead.

Also note that CTR mode does not, by itself, protect message integrity — for that you need authenticated encryption. However, many modern authenticated encryption modes, such as EAX, GCM and SIV, do essentially consist of CTR mode augmented by a message authentication scheme, and thus support all the features of CTR mode (including random-access decryption) once the data has been authenticated. The authentication itself, however, normally requires reading and processing all the data, unless you choose to divide it into smaller segments and authenticate each segment separately.


Addendum: As CodesInChaos notes in the comments above, if the "file" you're encrypting might change, such that an attacker could observe several different ciphertexts corresponding to the same position in the file (encrypted with the same key and counter sequence), then CTR mode becomes quite vulnerable to attacks.

The reason is that, like with any other encryption scheme based on XORing the data with a fixed keystream, an attacker who can observe two distinct values encrypted with the same part of the keystream can recover the XOR of the plaintexts simply by XORing the ciphertexts. If they can guess one of the plaintexts (say, because they know it's all zeros), this immediately reveals the other one. For more information, see e.g. this earlier question.

That said, if the encryption is only done to transfer the file from the device to the host (i.e. the data is only encrypted "on demand" when it's requested by the host), it may be possible to solve this issue by constantly varying the key and/or the initial counter value, e.g. based on a running message counter or a high-resolution timestamp.

For example, assuming that you file is no longer than 64 GB, you could use the lowest 32 bits of the block cipher input for the counter (i.e. the position of the block in the keystream), the next 64 bits for a timestamp or a message counter (make sure it can never decrease, even if an attacker manipulates messages), and still (assuming a 128-bit block size like for AES) have 32 bits left over e.g. for a per-file unique nonce. This would ensure that no part of the file is ever encrypted twice with the same keystream.

Also note that it's perfectly OK to apply this scheme as a second layer of encryption to transfer data that's already stored in encrypted form (possibly also using CTR mode, with a different key and/or initial counter value) on the device. This could afford an extra measure of security against attacks involving physical disassembly of the device and direct reading of the stored data on it.

share|improve this answer
    
CBC and CFB modes work as well (and ECB, but that's obvious). You can extract the chain part from the previous or next block for arbitrary access. I think just OFB does not work for arbitrary access, since you would require both the ciphertext and the plaintext of the previous block for the chaining. –  tylo Sep 19 '13 at 9:45
    
Example for CBC: You know the key and the ciphertext blocks $c_{k}$ and $c_{k-1}$ and want the plaintext $p_k$. What you do: decrypt $c_{k}$, and you get $p_{k} \oplus c_{k-1}$. If you XOR $c_{k-1}$ on that, you get $p_k$. –  tylo Sep 19 '13 at 10:30
    
@tylo: True, CFB and CBC also support random-access decryption, although encryption with those modes is inherently sequential. Unlike CTR mode, they also require you to retrieve the entire previous block of the ciphertext (and for CBC, the entire current block too) in order to decrypt any part of a block. –  Ilmari Karonen Sep 19 '13 at 12:54

A stream cipher where you can calculate the stream at any offset without deriving the prior stream bytes is probably the simplest option.

AES-CTR is a mode that uses AES like a stream cipher. To decrypt at a random spot, you need only know the offset from the beginning and you can perform a single AES encryption call.

AES-CTR overview: Generate a unique 64-bit number (aka, the nonce) for each message, and concatenate it with a counter. The counter is the 64-bit representation of the block offset within the plaintext. Then generate the keystream K as:

K = AES(nonce || 0) || AES(none || 1) || ...

Then XOR K against the plaintext to produce the ciphertext.

To perform a random read, just determine the offset of the desired block and calculate AES(nonce || offset) and XOR it by the ciphertext to yield the plaintext.

share|improve this answer

Joshua probably doesn't care between CTR or CBC mode, but it may matter to others that follow.

CBC mode encryption also allows decrypting arbitrary blocks of ciphertext. To decrypt starting in block provide the ciphertext of block as the initialization vector and decrypt as usual.

As Nickolay observes, you will need to start at the first block boundary at or before the sample you want, discarding the extras.

share|improve this answer

CTR cipher mode allows block-oriented random reads, but it will not be 16-bit aligned but 16-byte aligned (for AES). You can do some combination of XOR and CTR - use 16-bit initial XOR value, XORed/ended/otherwise modified with position in file. For better non-linearity you can take any 16-bit group Fp and XOR initial vector with Nth element in this group.

share|improve this answer
    
While CTR mode produces the key-stream in 16 byte blocks, that only affects performance. You only need to read and decrypt those ciphertext bits you're interested in. On a modern CPU you won't even notice the overhead of generating a few bytes too much. –  CodesInChaos Sep 19 '13 at 13:12
    
Logically this is right, I just sticked to phrase 'without reading larger (or surrounding) blocks'. –  Nickolay Olshevsky Sep 19 '13 at 17:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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