Is encrypting twice much more secure?
in [Cryptography]
|
Prev: A published list of rare tetragraphs?
Next: A discrepancy in literatures on permutation polynomials
From: Gordon Burditt on 16 Jan 2010 11:29 >When generating the keys the most important thing MAKE ABSOLUTELY SURE YOU >GENERATE THE KEYS RANDOMLY, roll a pair of dice to generate 5 bits at a time >(you'll need ~3600 bits, it'll take a while), destroy the dice, burning is >best. There are hexadecimal (0-F) dice so you could get 8 bits from rolling a pair of them. If those are too exotic, or your key generation requirements start making the dice budget problematical, there are 8-sided dice (Although I haven't seen any numbered in octal 0-7, but you can read an 8 as a 0) at pretty much any gaming store. Other interesting dice options: You can get 30-sided dice with the alphabet on them (and 4 spaces you could interpret as "reroll", or perhaps "random punctuation"). Roll two 10-sided dice (one the "tens digit" and one the "ones digit") to get a number from 0-99, then add 28. This is the ASCII code of a character in a passphrase. This assumes you are excluded from putting in ASCII characters 00-31 and perhaps some of the printable characters (95 of them, including space, excluding DEL). If you get an unacceptable character for the particular use (this varies a bit with the application), re-roll. If you want a random latin-1 character (or other 8-bit character set character), roll a 30-sided die (10's and 100's digits) and a 10-sided die (1's digit). If you get an unacceptable character, re-roll.
From: Phoenix on 16 Jan 2010 11:31 Well, is encrypting twice much more secure? Yes or no? Alvo
From: unruh on 16 Jan 2010 14:39 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. But this is exactly exhaustive search with known plaintext. 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. To > > 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
From: Joseph Ashwood on 16 Jan 2010 13:01 "Phoenix" <ribeiroalvo(a)gmail.com> wrote in message news:3f2e6699-236c-4b0b-a00f-438095e7e5fd(a)34g2000yqp.googlegroups.com... > Well, is encrypting twice much more secure? > > Yes or no? The answer is more complex than yes or no. 3DES is more secure than DES, but double-ROT13 is used as a joke. Assuming the two ciphers are keyed independently, assuming certain things about the ciphers (long discussion), then double encryption is no less secure than single encryption. Any variation from this, and the combination can be less secure. So "yes or no" is actually the correct answer. Joe
From: Joseph Ashwood on 16 Jan 2010 13:25
"Simon Johnson" <simon.johnson(a)gmail.com> wrote in message news:c5a0e0ec-f863-40a0-b11e-fa3f64c41bd9(a)r24g2000yqd.googlegroups.com... .... > 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? Actually it can be trivially proven that AES is O(1) to break for a given key length. Key length is fixed, by definition doing a fixed amount of work is O(1) work. The concern is the actual compute/storage requirements, the actual requirements for larger factoring problems is not as firmly understood and heavily debated. > Really, that was the point of my original post. If you don't care > about speed you can spend CPU cycles reducing the number of security > assumptions. AES could be felled by attacks that haven't even been > invented yet. However, due to BBS's reduction to factoring we know the > only way BBS can be broken is by a radical advance in factoring. An advance that history has proven to be quite likely. Improved factoring attacks seem to come in about 5 year cycles, and while the graph has been fairly predictable, the deviation from predictability is growing. With symmetric attacks ( diff, linear, etc) the rate is about one every 10 years, but far less predictability. We just recently saw the attack for the decade on AES, the related key attacks, but its just about time for the factoring attack. The expectable factoring attack should advance the 768 that we just saw to about 820, any deviation from this could change things substantially in the predictions of security. > I think that conclusively shows that BBS has a better proof of > security than AES, does it not? It does not. BBS's proof of security is proof that it is nearly broken for usable key sizes, and the necessary key sizes for the equivalent security of 128-bit AES is currently arguable at up to about 30,000 kilobits, largely unusable. > Besides, you *can* use BBS as a trapdoor. You can publish N to the > world and anyone can encrypt using that modulus. They can send you the > cipher text and if you have the knowledge of the factors you can > recover the plain-text. We must be looking at very different BBS algorithms. If the initial X is published along with N, then anyone can decrypt. If only N is published then decryption requires guessing X, even if the factorization is known. So it cannot be subsituted for a public key algorithm. There is also the matter of the missing MAC. So to edit the list you provided to replace all the portions possible with BBS: > * Discrete logs are hard. > * There is no short-cut to the Diffie-Helman problem. * Factoring is hard. > * SHA-256 is secure. The only change is "AES is secure" versus "Factoring is hard." Since factoring is less hard than AES for reasonable sizes of IFP, the BBS variation is generally less secure. Joe |