Since I am planning a project which relies on storing encrypted information on a potentially hostile host, I tried to design a cryptographic mode, called mode FMC. This mode should, when combined with AES, provide a higher security margin than AES alone would. Basically mode FMC is a try to defend your private data (like credit card numbers or password lists stored in the application I am going to write) against yet to be discovered weaknesses in AES. As with any cryptographic project, it would be great to get review.
I’ve written a paper and published the code under LGPL. The code is implemented in C++ and includes a python binding.
21.11.2009 More secure than AES – mode FMC
November 21st, 2009 | General
9 comments ↓
Cryptography is hard. Googling for your name doesn’t turn up any evidence that you’re an experienced cryptosystem designer, so I’m going to guess (without reading it) that your proposal is actually easier to break than plain AES.
http://www.schneier.com/blog/archives/2009/09/the_cult_of_sch.html
@Dan: I admit that I am not an experienced cryptographer, but I still believe the proposal is good. I can not do anything about the fact that so far you didn’t read the proposal, but I can try to illustrate why it certainly is not easier to break than plain AES.
Suppose you have a pair of algorithms: encode and decode, and you encrypt/decrypt using AES-CBC like this:
C = E_S (encode (P))
P = decode (D_S (C))
Then if encode and decode do not depend on the secret key S, and AES is secure, the resulting algorithm should also be secure.
Examples of encode and decode are:
1. encode (P) = bzip2 compress P
2. encode (P) = P || SHA-256 (P)
3. encode (P) = store first letter and then only diffs to last letter
4. all “inner” steps used in FMC mode
Hi, have you compared other proposed AES modes? See http://csrc.nist.gov/groups/ST/toolkit/BCM/modes_development.html
@xurfa: well, I’ve just looked at some of the papers listed there, and I think one major difference is that they all assume that AES-encryption is perfectly secure. So in EAX, CCM, CWC, CS and GCM mode (and probably also some of the others), one AES (often CTR-mode) encryption is used to assure privacy, and some mechanism for authentication is added.
Mode FMC is designed with the thought that some cryptographic technique for (partially) breaking AES may become known, maybe in 30 years or so. So FMC encryption uses two AES-encryptions and some extra encoding passes of the data, to strengthen the cipher against future discoveries.
Certainly this means that in comparision the the other modes, mode FMC is neither very fast nor for instance does it allow parallel processing (for encrypting your 10 gigabit network); but on the other hand, if AES is not as strong as we thought, then any of the other modes might be vulnerable, wheras mode FMC might remain secure.
I am no security researcher, but Dan seems to be right: If C = E_S (encode (P)) means “first encode data and then encrypt with AES”, and if compression methods like bzip2 are your encode step, then you actually weaking AES because the compression algorithm places well known tokens at well known positions. Therefore your approach would allow well known secret attacks.
This kind of attack is famous for breaking the quite secure Enigma machine in WWII: Quite some die hard Nazis ignored the explict command to not sign messages and finished each message with “Heil Hitler”. His majesty’s cryptographers where quite amused.
Well, but maybe I just misunderstand everything. I am no crypto researcher.
@Mathias: if AES is secure, then a few well-known bytes introduced by bzip should not be a problem. This kind of attack would be a known plaintext attack. There is a stronger class of attack – choosen plaintext – where the attacker does not only knows but gets to choose the plaintext that is being encrypted.
I think the best choosen plaintext attack is against a reduced round AES (with 8 instead of 14 rounds), requiring 2^204 time and about 2^128 choosen plaintexts. (Improved Cryptanalysis of Rijndael, N. Ferguson et al).
However, I used bzip only as example, in order to say that if AES is secure, then any encoding should be okay. But you are right, some encodings may be better than others. An bzip encoding has the advantage that the data is more evenly distributed than the input data, if the input data is ascii text. But it has the disadvantage of having well-known bytes.
The particular encoding defined in mode FMC is designed in a way that it should be absolutely impossible to know what is the input of the outer layer of encryption, even if one knows or chooses all the plaintext. So the FMC encoding should produce something equivalent to white noise as output, without having fixed output bytes like for instance bzip.
I read your paper with interest, but agrees with other posters that it is really a good idea to find some standard solution here instead of inventing something new. I’m not sure what a good pointer is, though, but there are AEAD ciphers out there with good security properties, although perhaps not exactly the properties you are looking for.
Anyway, two tips on your techniques that could be improved:
1) Key derivation from password could be strengthened by adding a salt and an iteration count. I would recommend to use the PKCS#5 PBKDF2 from RFC 2898 instead.
2) The length of the password appears to be possible to infer from your protocol (or I missed something). I think you want to pad the values so that all records are 1024 bytes or similar. This has a downside of creating a fixed upper limit on password/domain/username lengths, but if you use a high enough limit it may not be a problem in practice. Padding the data with either 0 or random data has some different properties, so be sure to use a good padding scheme.
/Simon
@Simon: As I said, I am not aware of any AEAD scheme that is as careful about guaranteeing privacy (by for instance specifying two AES-256 encryptions per 128-bit block), as mode FMC is. Most schemes optimize for speed and size, both of which are irrelevant for my application.
About your tips:
1) The FMC spec explicitely requires a master key with 256-bit. Then keys K and S are derived from that master key using
K = SHA-256 (master_key || “key encryption key”)
S = SHA-256 (master_key || “secret key”)
There is no mention of where the 256-bit master_key comes from, but for dpim, it will be generated from “/dev/random”, and stored on disk on the client. To guarantee for the security of the master_key file, a password-derived key will be used to encrypt the file.
What is important is that the actual secret data, which will be sent over the net, is encrypted with the master-key, which should be equally likely any 256-bit value. If you password-derive the master-key, and then send data encrypted by a password-derived master-key over the net, people can do dictionary attacks on it. And some users /will/ choose weak passwords like “password” or so…
To make it short: the FMC spec doesn’t include anything about password-derived keys, but instead specifies the master_key to be 256-bit, so your tip does not apply to the FMC spec.
2) Right – that makes sense. There is an information leak here, although in practice its not so bad, because if you have ten entries in the database, with ten different site/username/password combinations, there it gets very hard to know which entry belongs to which site, because the data is encrypted. Also, the data is padded to 16-byte boundaries, so suppose you knew which entry belongs to which site, you would only get to know that the password is between 6 and 22 characters long or some other 16-char range.
I don’t like padding to 1024 bytes very much, because it slows down the transfer a lot. I think one might add an extra field containing a random amount of random data (say between 0 and 64 bytes long); but I haven’t quite decided what would be the best solution.
@stw: Thanks for explanation.
Leave a Comment