Is encrypting twice much more secure?
in [Cryptography]
|
Prev: A published list of rare tetragraphs?
Next: A discrepancy in literatures on permutation polynomials
From: Simon Johnson on 15 Jan 2010 12:59 > This is absolutely overkill, and at the best knowledge of the cryptanalytic > industry will take more compute capability than the entire universe can ever > create. > Pretty much every cipher out there is designed to be efficient as well as secure. Once you've decided that speed isn't an important property (beside security of course) then you need to do a root and branch review of what you want out of a cipher because suddenly a huge design constraint has been lifted. In this new world where performance doesn't really matter, the most secure practical cipher today is the Blum Blum Shub (BBS) generator. We know that it reduces to factoring. That is an astonishing proof, when you consider we haven't be able to prove this result for RSA. Moreover, providing you're rekeying every couple of years like a good little user, BBS actually gets more secure. Here's why. Suppose you're happy with a throughput of 500k per second. Let's say that you're using a 2048-bit modulus today and you're getting that throughput comfortably. In two years time, you decide to retire this modulus and move to a new key. Due to increases in computing power, you can now use a 3000-bit key and achieve the same throughput. You've doubled the work per byte of keystream generated but the attackers' work load has increased by a factor of millions. So when I see people talking about triple encrypting stuff, I feel they've missed the point entirely. If you don't need speed, why use AES at all? AES is provably secure against a limited set of attacks. A new attack could break it tomorrow. With BBS there is only one attack: factoring. It's true that somebody could devise a much faster factoring algorithm but there is strong circumstantial evidence that suggests that this will probably not be possible. At any rate, the case is much, much stronger than the comparable case for AES. I don't think BBS gets enough love in the crypto community.It's very simple and very secure; it's a truly beautiful algorithm. Cheers, Simon
From: Tom St Denis on 15 Jan 2010 13:06 On Jan 15, 12:59 pm, Simon Johnson <simon.john...(a)gmail.com> wrote: > > This is absolutely overkill, and at the best knowledge of the cryptanalytic > > industry will take more compute capability than the entire universe can ever > > create. > > Pretty much every cipher out there is designed to be efficient as well > as secure. > > Once you've decided that speed isn't an important property (beside > security of course) then you need to do a root and branch review of > what you want out of a cipher because suddenly a huge design > constraint has been lifted. > > In this new world where performance doesn't really matter, the most > secure practical cipher today is the Blum Blum Shub (BBS) generator. > We know that it reduces to factoring. That is an astonishing proof, > when you consider we haven't be able to prove this result for RSA. Actually, there is a variant of RSA where N = p^2q and it's provably reducible to factoring. It's weird in that encryption uses N as the exponent. It's in LTC under the "katja" directory [iirc]. I named the directory after the author of the eprint paper I based the implementation on. it's less desirable than RSA because the public operations are much slower. Also, speed/efficiency DOES matter. Crypto is used in places where 4000MIPS processors are not common :-) Tom
From: Tom St Denis on 15 Jan 2010 13:09 On Jan 15, 1:06 pm, Tom St Denis <t...(a)iahu.ca> wrote: > On Jan 15, 12:59 pm, Simon Johnson <simon.john...(a)gmail.com> wrote: > > > > > > This is absolutely overkill, and at the best knowledge of the cryptanalytic > > > industry will take more compute capability than the entire universe can ever > > > create. > > > Pretty much every cipher out there is designed to be efficient as well > > as secure. > > > Once you've decided that speed isn't an important property (beside > > security of course) then you need to do a root and branch review of > > what you want out of a cipher because suddenly a huge design > > constraint has been lifted. > > > In this new world where performance doesn't really matter, the most > > secure practical cipher today is the Blum Blum Shub (BBS) generator. > > We know that it reduces to factoring. That is an astonishing proof, > > when you consider we haven't be able to prove this result for RSA. > > Actually, there is a variant of RSA where N = p^2q and it's provably > reducible to factoring. It's weird in that encryption uses N as the > exponent. It's in LTC under the "katja" directory [iirc]. I named > the directory after the author of the eprint paper I based the > implementation on. it's less desirable than RSA because the public > operations are much slower. For the curious; Abstract: Public key cryptography has been invented to overcome some key management problems in open networks. Although nearly all aspects of public key cryptography rely on the existence of trapdoor one-way functions, only a very few candidates of this primitive have been observed yet. In this paper, we introduce a new trapdoor one-way permutation based on the hardness of factoring integers of $p^2q$- type. We also propose a variant of this function with a different domain that provides some advantages for practical applications. To confirm this statement, we develop a simple hybrid encryption scheme based on our proposed trapdoor permutation that is CCA-secure in the random oracle model. http://eprint.iacr.org/2005/278 Tom
From: Paul Rubin on 15 Jan 2010 13:21 Simon Johnson <simon.johnson(a)gmail.com> writes: > In this new world where performance doesn't really matter, the most > secure practical cipher today is the Blum Blum Shub (BBS) generator. > We know that it reduces to factoring. That is an astonishing proof, > when you consider we haven't be able to prove this result for RSA. 1. Why should we expect factoring to be harder than breaking block ciphers like AES? Factoring is generally believed to not be NP-hard and someone might discover a P-time factoring algorithm tomorrow. Factoring is in NP/\co-NP, a more constricted complexity class than typical block ciphers, which don't hvae to be in co-NP. 2. WHy is it astonishing that we know BBS reduces to factoring but we don't know the same for RSA? BBS doesn't try to be a trapdoor function like RSA. RSA performs a much harder trick and I'd think it unsurprising that its complexity is harder to analyze.
From: Peter Fairbrother on 16 Jan 2010 03:49
Peter Fairbrother wrote: > Mok-Kong Shen wrote: >> Peter Fairbrother wrote: >> >>> I don't know about screwing up the implementation, which could do >>> horrible things - but yes, there is established theory that multiple >>> encryption with statistically independent keys is at least as secure as >>> the first encryption, see: >>> >>> M. Maurer and J. L. Massey, Cascade ciphers: The importance of being >>> first, Journal of Cryptology, vol. 6, no. 1, pp. 55�61, 1993. >>> >>> www.isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI434.pdf >>> >>> so if one pass is secure enough you're okay. >>> >>> (I have a tiny doubt about their result, which I've been working on for >>> some years now - but in practice it won't mean much even if it pans out) >> >> Wouldn't an 'definition' of 'statistically independent keys' (not very >> simple to verify absolutely in practice, I surmise) by itself >> ('logically') imply that the 2nd cipher couldn't weaken the work of the >> 1st cipher? (For in the other case one could say then that the keys >> aren't 'independent' after all.) No, and here's a concrete, if unlikely, example to prove otherwise. Iirc, it directly disproves Maurer and Massey's theory, although I haven't read it for awhile. Imagine the first cipher is a secure block cipher with block size equal to key size. Take a chosen plaintext, and construct an ordered list of keys against ciphertexts for the first cipher. Now imagine the second cipher has only one possible key (or two, if you don't like the idea of a cipher with only one key, but they are both very similar permutations) which is a permutation the reverse of the list above. You mow have a very simple chosen plaintext attack - get the encryptor to input the chosen plaintext, and out comes - the key, with very high probability! It doesn't matter if the first cipher is perfectly secure, IND-CPA, IND-CCA2, the whole schmear. The second cipher has done the brute-force work of a chosen plaintext attack for you. I have further doubts about the theory as well. -- Peter Fairbrother >> >> When your work bears fruit, please let us know as soon as possible, for >> that would be very interesting and valuable. > > I don't think that's going to be for some time if ever, and it probably > won't be very valuable (although it might be interesting), but here's a > rough outline of my thoughts ... my doubts are more intuitive than > clearly expressible, and originally based only on a nebulous doubt of > the proof-by-example in the paper mentioned ... > > ... if anyone wants to finish it feel free, but credit me in the paper > please! ... > > ... and this is probably going to get long, and I'll be including some > beginner's stuff. And I'm only looking at block ciphers here, not stream > ciphers. > > > Consider a block cipher as a set of permutations of plaintext into > ciphertext. > > [ In simple terms, we could write the possible plaintexts out in > numerical order, then write out the corresponding ciphertexts in order - > that ordered list is a permutation, and there is a different permutation > for each key. ] > > If there are B different possible plaintexts in a block, there are B! (B > factorial) possible permutations. If there are K possible keys then > there are K actual permutations. > > The cipher, in effect, chooses one the possible permutations, and > assigns one to each key. For a "secure" cipher, one usual requirement is > that these choices and assignations "look" random for all purposes. > > So far, so normal. > > [ There is another requirement for a cipher - in order to be able to > uniquely decrypt, the cipher cannot assign the same permutation to two > different keys. > > []-> Therefore it is impossible to have a truly random choice over the > entire set of possible permutations. > > This also implies that B! must be greater than K - not usually a > problem, for the average block cipher B! is very very much larger than K. > > Later we'll consider a case where B! is about equal to K. This doesn't > happen with today's real block ciphers, which is why it isn't likely to > be a valuable result in practice (although it isn't a result at all, as > yet). ] > > > First, let's go back a bit - for a secure cipher the choices of > permutations should look random for all purposes. > > But for any real cipher the choices are fixed by the cipher itself, in > the sense that they don't change - and there are patterns in them even > if they are truly chosen at random. > > In any finite fixed set of random numbers there are patterns of some > kind, if you look for them. > > []-> It is therefore impossible to create a real cipher where the > permutations look random for all purposes - in some sense patterns can > be detected in them. > > Incidentally, this is why rainbow tables can be used to break most > (all?) ciphers, although in practice they may often need more resources > than brute force. > > > > On to cascaded ciphers. The second cipher also has patterns in it, and > these can interact with the patterns of the first cipher. > > Usually, for real ciphers, this isn't a problem, in the sense that it > takes more resources than brute force to break them, and it's usually > possible to prove that an attack based on this kind of interaction is > statistically overwhelmingly likely to take more resources than brute > force on the first cipher, when the keys are independently chosen. > > But for cases where B! is about equal to K in both ciphers, I *think* > birthday problems negate that statistical proof. I haven't worked out > the details though, and I may very well be wrong. > > > > -- Peter Fairbrother |