Is encrypting twice much more secure?
in [Cryptography]
|
Prev: A published list of rare tetragraphs?
Next: A discrepancy in literatures on permutation polynomials
From: unruh on 16 Jan 2010 14:45 On 2010-01-16, Phoenix <ribeiroalvo(a)gmail.com> wrote: > Well, is encrypting twice much more secure? > > Yes or no? Maybe, perhaps even probably.
From: Peter Fairbrother on 16 Jan 2010 15:34 Phoenix wrote: > Well, is encrypting twice much more secure? > > Yes or no? Sometimes it's more secure. Sometimes it's about the same. Sometimes it's less secure. Here are four of the usual reasons for encrypting twice (or more often). They all have pitfalls and disadvantages, and should only be used in specific, and usually rare, situations. First, to increase effective keysize and the work needed for a brute-force attack. Usually the same cipher is used in all encryptions. This is unreliable unless you get all the details right, and triple encryption is usually needed to double the effective keysize. It doesn't work for all ciphers. Cobbling these together is dangerous. The combination should have been analysed, as well as the single cipher - it can make things worse, not better, if you eg adapt 3-DES to use a different cipher. Avoid completely - you don't need to do it, there's a better cipher out there. Second, to protect against some "known unknown" attacks. This might be potential algebraic attacks on AES, or a potential general attack on all feistel ciphers, and you might use a combo of AES and Twofish. I'll call this belt-and-braces. We generally assume, on statistical grounds but with no actual proof, that this is at least as secure as either one of the ciphers (when the keys are independently chosen at random) - it may be less, but that's unlikely if the ciphers are carefully chosen. It isn't done to increase effective keysize, the work needed for a brute-force attack, or security against anything but some "known unknown" attacks. The benefit is arguable, and some cryptologists don't like the idea - others do. Personally I come down slightly on the side of using it when resources are always guaranteed to be plentiful and cheap. Third, to be able to add or strip off layers of encryption. Usually the same cipher is used in all encryptions. This is not done to increase cipher security or effective keysize, and we usually consider that it does neither. It may, but we discount that possibility. We generally assume, on statistical grounds but with no actual proof, the security is as good as a single encryption (when the keys are independently chosen at random) - it may be less, but that's unlikely. There are keysharing techniques which can divide a key into shares with provable security, and these are often more efficient for the required purposes. In general, use keysharing instead - but there are a few circumstances where layering is justified. Mixmaster anonymous email is one, and onion routing. There are a couple more, but they aren't common. Fourth, universal re-encryption, usually used to disguise ciphertext. This is where people can re-encrypt without knowing the original key used (roughly speaking), but someone who knows the decryption key can still decrypt the re-encrypted ciphertext. Either partial layering, where the keys are universally re-encrypted and the ciphertext is layered, or special ciphers must be used. Multiple encryptions using the special ciphers can be provably as secure as a single encryption (when the keys are independently chosen at random), but multiple encryptions are not more secure than a single encryption. Uses for this are rare. There are also some vaguely similar public key techniques potentially usable in digital money, which might be called double encryption if viewed from some angles. If you aren't doing one of the layering things, or belt-and-braces, or universal re-encryption, then don't double/multiple encrypt - it's usually not the best way to go. -- Peter Fairbrother
From: Peter Fairbrother on 16 Jan 2010 15:47 unruh wrote: > On 2010-01-16, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote: >> 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. > > No. since the second cypher can only be the inverse for a single > plaintext. The second cipher is not an inverse for the known plaintext. It inputs the corresponding ciphertext from the first cipher and outputs the key for the first cipher - not the plaintext. > But this is exactly exhaustive search with known plaintext. Yes, with the proviso above. But the encryptor does the work for you! There is no requirement that the second cipher be easy or efficient ... just a cipher, which technically it is. -- Peter Fairbrother > > Note that if such a second cypher exists, then this is exactlychosen > attack method on the cypher that tests the strength of the cypher. Ie, > this cypher is very weak. That second cypher therefor does not decrease > the strength of the first, because the first is already very weak, and > this is precisely the weakness.
From: Paul Rubin on 16 Jan 2010 15:53 Simon Johnson <simon.johnson(a)gmail.com> writes: > Has anyone proved that AES belongs to NP? Has anyone proved this for > *any* block cipher? What's to say they aren't really in P like BBS > could be? I think you mean "is there a proof that AES is NP-hard". There is no proof (and for that matter it could even be that P=NP) but there is a body of theory about circuit complexity giving some hope of the notion. With public key, it's different, because trapdoor functions require extra properties. You might like Russell Impagliazzo's famous "five worlds" article if you're not familiar with it: http://www.cs.ucsd.edu/users/russell/average.ps
From: Peter Fairbrother on 16 Jan 2010 16:23
Peter Fairbrother wrote: > unruh wrote: >> On 2010-01-16, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote: >>> 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. >> >> No. since the second cypher can only be the inverse for a single >> plaintext. > > The second cipher is not an inverse for the known plaintext. sorry, should read "the single chosen plaintext". > It inputs > the corresponding ciphertext from the first cipher and outputs the key > for the first cipher - not the plaintext. > >> But this is exactly exhaustive search with known plaintext. > > Yes, with the proviso above. But the encryptor does the work for you! > > There is no requirement that the second cipher be easy or efficient ... > just a cipher, which technically it is. > > > -- Peter Fairbrother > > >> >> Note that if such a second cypher exists, then this is exactlychosen >> attack method on the cypher that tests the strength of the cypher. Ie, >> this cypher is very weak. That second cypher therefor does not decrease >> the strength of the first, because the first is already very weak, and >> this is precisely the weakness. |