Is encrypting twice much more secure?
in [Cryptography]
|
Prev: A published list of rare tetragraphs?
Next: A discrepancy in literatures on permutation polynomials
From: Tom St Denis on 17 Jan 2010 10:05 On Jan 16, 11:31 am, Phoenix <ribeiroa...(a)gmail.com> wrote: > Well, is encrypting twice much more secure? > > Yes or no? > > Alvo Generally no. I've posted the logic to this answer already. Basically the argument works like this Question: Is double-AES more secure than single AES? Answer: No. Suppose, O(2^256) work is feasible [e.g. meaning that double-AES *is* more secure] than a MITM attack can break the double- AES with 2^256 space and 2^256 time. Suppose that 2^256 work/space is not possible, then double-AES is not more secure since you can't break single AES anyways. Tom
From: Ilmari Karonen on 17 Jan 2010 10:46 On 2010-01-17, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote: > > Hmm, maybe someone breaks key sharing in the next 50 years - quantum > computers could do that, mostly it's public key type stuff. > > Though iirc there are some known-work techniques which QC won't break - > but it's not my field. There are several well known information-theoretically secure secret sharing schemes. A trivial one, for sharing a key among N persons, is to encrypt it with N-1 independent one time pads, give the result to the first person and one of the pads to each of the remaining N-1. Shamir's secret sharing scheme, based on polynomials over a finite field, is a slightly more elaborate solution which can allow the key to be recoverably by any K out of the N persons, for some 1 < K <= N, and is also information-theoretically secure. -- Ilmari Karonen To reply by e-mail, please replace ".invalid" with ".net" in address.
From: Peter Fairbrother on 17 Jan 2010 11:39 Ilmari Karonen wrote: > On 2010-01-17, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote: >> Hmm, maybe someone breaks key sharing in the next 50 years - quantum >> computers could do that, mostly it's public key type stuff. >> >> Though iirc there are some known-work techniques which QC won't break - >> but it's not my field. > > There are several well known information-theoretically secure secret > sharing schemes. A trivial one, for sharing a key among N persons, is > to encrypt it with N-1 independent one time pads, give the result to > the first person and one of the pads to each of the remaining N-1. With today's storage technologies, it might be just as well to do that with the plaintext (assuming it's not petabytes in size) rather than the key. Then you don't have to worry about the security of the encryption. > Shamir's secret sharing scheme, based on polynomials over a finite > field, is a slightly more elaborate solution which can allow the key > to be recoverably by any K out of the N persons, for some 1 < K <= N, > and is also information-theoretically secure. I vaguely remember that, but can't remember the details - does it scale well to say 20 megabytes? -- Peter Fairbrother
From: unruh on 17 Jan 2010 13:32 On 2010-01-17, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote: > unruh wrote: >> On 2010-01-16, Peter Fairbrother <zenadsl6186(a)zen.co.uk> 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. It inputs >>> the corresponding ciphertext from the first cipher and outputs the key >>> for the first cipher - not the plaintext. >> >> The function is the mapping from key to encrypted text. The inverse is >> the function from encrypted text to key. > > Okay. I thought you had implied the first function was encryption, which > is a mapping from plaintext to ciphertext. > >> >>>> But this is exactly exhaustive search with known plaintext. >>> Yes, with the proviso above. But the encryptor does the work for you! >> >> Sorry, but if we are allowed to hypothesise such an encryptor, why not >> just hypothesis a key finder, for which you hand it the encryptoed text >> and it produces the key. > > Yes - it's also known as exhaustive search. > >> Under that hypothesis, all crypto systems are >> insecure. Ie, you have to first make it plausible that such an encryptor >> as you hypothesis exists, and estimate the work that it has to do to >> encrypt. If the work is does is greater than exhaustive search, then it >> is no advance at all. >> >>> There is no requirement that the second cipher be easy or efficient ... >>> just a cipher, which technically it is. >> >> Sure there is such a requirement. > > *Not in the definitions of cascaded ciphers there isn't.* > > The second cipher may be equivalent to a brute force attack, and take as > much work to perform - but it's still a cipher. > >> If the work needed to run it is far larger tan the work >> required to break the original cypher by exhaustive search, then it is >> not a break in anyone's definition. It does not weaken the original >> cypher. > > All I'm doing is showing is that in this theoretical and impractical but > *follows-the-definitions-of-cascaded-ciphers* case the cascaded ciphers > are weaker than the first cipher alone - which M+M said, incorrectly, > was impossible. But the cascaded cypher is NOT weaker than the orginal alone, since the cascaded cypher is exactly exhaustive search ( which always sets an upper bound on the strength of a cypher). > > > > If you don't like the extreme example (although it is theoretically > sound), suppose instead that the second cipher merely does some of the > work of breaking the first cipher - I think I've shown that that is at > least possible. > > The combo is then weaker than the first cipher alone. How are you defining "weaker"? > > -- Peter Fairbrother > > >> >> >>> >>> -- 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: unruh on 17 Jan 2010 13:36
On 2010-01-17, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote: > unruh wrote: >> On 2010-01-16, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote: >>> Phoenix wrote: >>>> Well, is encrypting twice much more secure? >>>> >>>> Yes or no? >> >> ... >>> >>> >>> 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. >>> >> >> The OP wants to put out there the source code for his program he is >> selling, and encrypting it. He is giving some lawyer the keys so that if >> he dies, the lawyer can give his customers the keys and they can get the >> source code. He wants the encrypted source code to be public. He is >> worried that before he dies someone will break AES and his source code >> will be released and he stops raking in the money from selling the >> binary code. Thus, he wants to triple encrypt to make sure that his >> source code is safe while he is alive. > > Are you (he) talking about triple AES? Has anyone analysed that? No. He mentioned three different cyphers. > > If eg AES is a group then that's no more secure than single AES (I very > much doubt AES is actually a group, it's just an example of what can go > wrong with triple encryption using the same cipher). > > >> So it falls under the belts and braces category. > > If he's using different ciphers. There is some logic to that. > > What I'd do is use two 256-bit block, 256-bit keyed ciphers chosen to be > as dissimilar as possible. With independently chosen keys. > > Rijndael-256/256 (not AES-256) might be one, and Twofish 256/256 another. > > > The reason for using two ciphers is to protect against a possible break > in only one of them. That was his reasoning. > > The reason for using 256-bit keys is defense against quantum computers. > > The reasons for using 256-bit blocks are - too complex to explain in a > short post. > > The reason for not just using one cipher is - history. If you want a > good chance of being a long way out in advance of history then you need > to take extreme measures. > > But it's only a good chance, we simply don't know what advances will > happen over the next 50 years. > > Practical crypto is an art, not a science - there's always someone > wanting to break your system, and they will think of potential attacks > you haven't thought of. Lots of them, and maybe one will work. > > And there ain't many ciphers in use 50 years ago which ain't broke now. > > > Of course his trowsers >> are made of tissue paper, so a couple of million to the lawyer will open >> up his source code like toilet paper in a rain, but he is worried about >> someone spending a million to break AES instead to get at his source >> code. > > ITYM a billion to break AES :) But then some people do have the money > and desire to try, NSA springs to mind. For his source code? > > But you're right. > > Key sharing? > > Hmm, maybe someone breaks key sharing in the next 50 years - quantum > computers could do that, mostly it's public key type stuff. > > Though iirc there are some known-work techniques which QC won't break - > but it's not my field. > > > -- Peter Fairbrother |