Encrypting odd sized buffers
in [Cryptography]
|
From: Tran Ngoc Duong on 24 Jun 2010 05:06 On Jun 24, 2:11 pm, Ross MacGregor <ross__macgre...(a)hotmail.com> wrote: > Tran Ngoc Duong wrote: > > Here is a 108-bit block cipher that I've just crafted specifically for > > your need. It is a 54-round Feistel structure and > > it uses the function f(x) = (x*(2*x+1)) <<< 18 (over 54-bit numbers). > > Thanks for all the work on this, I really appreciate it! > I will probably go with an established hash function for > this as performance should not be an issue. > > Why did you suggest 54 rounds? I think that for a Feistel cipher with 2N-bit block, N rounds is a good starting point for security consideration. I'm influenced by GOST -- a 64-bit block cipher which is a 32-round Feistel structure with a bijective f-function and 11-bit rotation, i.e. rotation by 1/3 half- block length. As for my algorithm, 54 rounds gives reasonable confidence for the security level of about 180 bits, I think.
From: Francois Grieu on 24 Jun 2010 05:33 Le 24/06/2010 01:28, Maaartin wrote: > On Jun 24, 12:32 am, Francois Grieu <fgrieu(a)gmail.com> wrote: >> My understanding is that Luby & Rackoff have proven that for >> r>=4, breaking the PRP requires work exponential in n, even >> under choosen-plaintext and choosen-ciphertext attack. This is >> an asymptotic result, NOT applicable to the small n that we >> consider. > > So you say, we have nothing for small n, right? *I* have nothing practical in my hand luggage if someone asks for a Feistel cipher with a good security argument for small n. Even after glancing at the nice pointers set up by Paul Rubin <news:7xeifxxo8v.fsf(a)ruckus.brouhaha.com> > We could use more rounds and this would help against your > argument (I mean your counting of achievable permutations etc.), Yes. > but still we have no security proof whatsoever, right? Right. As it stands, my counting claims exactness only for 3 rounds. I plan to revive old code that scrutinize r = n = 4. It explores the combinations of the first 3 PRF, then (according to my ancient comments) finds the single fourth PRF such that the resuting permutation P verifies: 0<=u<v<2^n and (P(u)^P(v))<2^(n/2) => P(u)==0 which, together with a hash-code table, allows fast and exact statistics on a manageable number of permutations P. I think this could be extended for r up to 6 using a meet-in-the-middle technique, for a randomized (rather than provably representative) subset of the permutations. > So there's only HPC left, but I've got the feeling, nobody took > it seriously, so do we have nothing at all? I have not found time to study HPC. The name did not help. If key agility and a small memory footprint does not matter, we can explicitly build the table for a PRP; it require n*(2**n) memory bits, O(2**n) steps at setup [with the n* term often negligible in practice except for cache effects]. Encryption (or decryption, or both with twice as much memory) is then very fast. It is easy to make odds of each permutation equal to any arbitrary tolerance. That's easy and provable. Francois Grieu
From: Ross MacGregor on 24 Jun 2010 16:14 On Jun 24, 1:13 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Just a question out of curiosity: What's the problem of using the > simplest PRNG f(x)=a*x+b mod 2^108 (a odd) in your application? Sorry, I haven't been very clear with what I am looking for. We have an existing application that uses a similar scrambling function, but there are concerns that you can predict the sequence if you know the function. This is why I am interested in the encryption approach and using a key to encode the output. A secure solution would be best. Thanks, for the information on permutation polynomials it's good stuff for me to know.
From: Paul Rubin on 24 Jun 2010 17:12 Ross MacGregor <gordonrossmacgregor(a)gmail.com> writes: > Sorry, I haven't been very clear with what I am looking for. We have > an existing application that uses a similar scrambling function, but > there are concerns that you can predict the sequence if you know the > function. This is why I am interested in the encryption approach and > using a key to encode the output. A secure solution would be best. Can you rely on being able to keep the key secret? Earlier you mentioned a possible security audit, so I'd expect protecting the key (or eliminating reliance on it) to be an element of that audit. For example, you say you don't want attackers to predict the sequence, where "predict" presumably means gaining advance knowledge of future elements of the sequence. Is it also a problem if they gain knowledge of -past- elements of the sequence? I'd be concerned about relying on a home-cooked algorithm and the secrecy of the key if the input to the permutation is predictable, but as long as the input is unpredictable enough, it doesn't really matter what permutation you use. The idea to keep in mind is that the attacker is going to infer some probability distribution on the output. The distribution may not be uniform, but there will in any case be some output value e with maximal probability, i.e. Pr[e] >= Pr[x] for all x. What you are trying to do is maximize the so-called min-entropy, which means make Pr[e] as small as you can (Pr[e] is a measure of how "guessable" the value is). You can minimize Pr[e] either by making the input unguessable, or by disguising a guessable input by running it through an unguessable permutation. This stuff about block ciphers concentrates all your effort into the second of these possibilities. Maybe you want some combination of both.
From: Ross MacGregor on 24 Jun 2010 18:43
On Jun 24, 2:12 pm, Paul Rubin <no.em...(a)nospam.invalid> wrote: > Can you rely on being able to keep the key secret? Earlier you > mentioned a possible security audit, so I'd expect protecting the key > (or eliminating reliance on it) to be an element of that audit. Yes, the key will be secured from users/attackers. The input for a generated set of numbers will start with a random 108 bit number that will be incremented (+1 likely) for each number generated. This input value will also be secured from users/attackers. The ability of our users to collect past elements is very restricted and total elements generated will be in the order of 30 million. |