Take the 2-minute tour ×

I'm building file-encryption based on AES that have to be able to work in random-access mode (accesing any part of the file). AES in Counter for example can be used, but it is well known that we need an unique sequence never used twice. Is it ok to use a simplified Fortuna PRNG in this case (encrypting a counter with a randomly chosen unique key specific to the particular file)? Are there weak points in this approach?

So encryption/decryption can look like this

Encryption of a block at Offset:

rndsubseq = AESEnc(Offset, FileUniqueKey)
xoredplaintext = plaintext xor rndsubseq
ciphertext = AESEnc(xoredplaintext, PasswordBasedKey)

Decryption of a block at Offset:

rndsubseq = AESEnc(Offset, FileUniqueKey)
xoredplaintext = AESDec(ciphertext, PasswordBasedKey)
plaintext = xoredplaintext xor rndsubseq

One observation. I came to the idea used in Fortuna by myself and surely discovered later that it is already invented. But as I read everywhere the key point about it is security, but there's another good point: it is a great random-access pseudo random numbers generator so to speak (in simplified form). So the PRNG that not only produces very good sequence (I tested it with Ent and Die Hard) but also allow to access any sub-sequence if you know the step number. So is it generally ok to use Fortuna as a "Random-access" PRNG in security applications?


In other words, what I suggest is to use Fortuna PRNG as a tweak to form a tweakable AES Cipher with random-access ability. I read the work of Liskov, Rivest and Wagner, but could not understand what was the main difference between a cipher in a mode of operation and a tweakable cipher. They said they suggested to bring this approach from high level inside the cipher itself, but for example in my case xoring the plain text with the tweak, is this a tweak or not?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

I think you may want to look up how "tweakable block ciphers" work and have a look at how the problem of disc encryption is solved: Disk encryption theory. Encrypting the whole disk is similar to your problem: encryption of each sector must be done independently (you want independent encryption of data at different offsets) and yet the whole thing must be secure. There is a lot of work done on that. Wikipedia seems to give a good overview.

EDITED to add: Re your edit: Yes, you are trying to make a tweakable block cipher out of AES by XORing the tweak with the plaintext. More concretely, you have Enc(T,K,M) = AES (K, f(T) xor M) where AES(K,...) means AES encryption with the key K and f(T) is some function of the tweak (in your case I guess it's Fortuna). I had a brief look at the paper you mentioned and as far as I can see it's possible to show that this method does not produce a secure tweakable block cipher. The idea (based on definitions from section 2 of the Liskov, Rivest, Wagner paper) is as follows. We have access to either the encryption oracle or a random permutation and we want to tell which one we are interacting with. We can set the tweak T and the plaintext M and we get back the corresponding ciphertext but we don't know the key which is used. Here is how to figure out if we use the construction AES(K, f(T) xor M). Pick any two different values T, T', compute f(T), f(T'). Pick any message M and then compute the second message as M' = M xor f(T) xor f(T'). Now ask the encrypting oracle to encrypt M using tweak T and M' using tweak T'. If we deal with the considered construction, the outputs will be identical. If we deal with random permutations, the outputs will be almost certainly (with probability 1-2^-128) different. That is because both inputs to the AES encryptions will be the same, so the ciphertexts will be also identical. This would not be the case when we use random permutations, because the probability that the two outputs are identical is 2^-128. The bottom line is that xoring tweak to the input is probably not a secure method.

The paper gives some examples of what they can prove to be a secure construction. The simplest one seems to be Enc(T,K,M) = AES(K, T xor AES(K, M)). You need two encryptions per block, but they prove the security of this construction. They also mention faster variants, but they require additional primitive (almost-xor-universal function families).

share|improve this answer
Although I already read the article (Disk encryption theory), it's good to mention it here (+1). I just read the document about tweakable block ciphers and will edit the post –  Maksee Sep 24 '09 at 14:07

Even though I think your approach is secure enough, I don't see any benefits over CTR. You have the exact same problem, which is you don't inject true randomness to the ciphertext. The offset is a known systematic input. Even though it's encrypted with a key, it's still not random.

Another issue is how do you keep the FileUniqueKey secure? Encrypted with password? A whole bunch issues are introduced when you use multiple keys.

Counter mode is accepted practice to encrypt random access files. Even though it has all kinds of vulnerabilities, it's all well studied so the risk is measurable.

share|improve this answer
I tried to avoid using simple counter in CTR to address the appearance of identical cipher blocks at the same offets for different files encrypted with the same password. So I just simply need some an unique sequence for AES CTR. Sure it can be for example unique Guid per file and +16 for every next block, but PRNG on the same guid just changes data more significally from block to block. It seems that even keeping the FileKey secret is not necessary. Maybe I'm wrong, but I interested in what kind of leak of information is possible if I guarantee the uniqueness of the sequence per file. –  Maksee Sep 23 '09 at 7:49

I don't see any need in counters or RNG. Just encrypt file in blocks (several kiulobytes blocks for example, choose granularity depending on your needs. Even AES block size can be selected ;) ). In this case you will have random access possibility easily.

share|improve this answer
No, you have to add some file-based randomness to the data. Otherwise two blocks filled with zeros will be the same in two files encrypted with the same password. It's a leak of information. –  Maksee Sep 22 '09 at 14:32
Do you know what CBC is? –  FractalizeR Sep 23 '09 at 6:40
CBC doesn't allow random-access. –  Maksee Sep 23 '09 at 8:23
But you can use CBC on blocks more than cypher block length, not on the complete file. So, to get random access you will need to decrypt just one block in CBC mode. –  FractalizeR Sep 23 '09 at 10:47

Your Answer


