Re: [cryptography] The Unbreakable Cipher
On 09/25/2013 03:51 PM, Jonathan Katz wrote: On Wed, Sep 25, 2013 at 1:30 PM, Greg Rose g...@seer-grog.net mailto:g...@seer-grog.net wrote: On Sep 25, 2013, at 9:40 , Jonathan Katz jk...@cs.umd.edu mailto:jk...@cs.umd.edu wrote: Every cipher is breakable, given enough traffic: in principle, yes, as long as the traffic (formally, the entropy of the traffic) is larger than the key length. You misstated this. It's breakable if the *redundancy* of the traffic is larger than the key length. Not so; this is most easily seen by taking the uniform distribution over n-bit messages, in which case the entropy is n and the redundancy is 0. regards, Greg. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography If the message is chosen from a uniform distribution over n bits (and assuming that the message is not used for something else after it is deciphered), the adversary will not be able to distinguish a correctly deciphered message from an incorrectly deciphered message, no matter how short the key is in comparison to the data. Now, you could easily argue that there is absolutely no reason to send a message with those properties, but that isn't really the point. -- KmNJcjeUDRXMu6riH0KAK9Og8WAaAT8oXcbnFIij5djCP4v+6GTFxnHoHzvW NTL+4ZPiGUqerypkfsDfEOcO+i6ZlY59G79tEMwR0fsKO9w9MLbv6Odz5RxY JZgUsZJ8lZWx/zBsL4oqU60k+EFbV14fSUVoaRpazy1ozgQFdi2SdfHTB41y 7SsMX/JlevnnBj/GhUyFlXPr2kwechOSy5W74iVbUaOpeYMqNIx3jCmZfjez Gi+sS8ghQB8y5b9NgYTlR7HBh+leObqQX/R5bAkyPyh2oDOlFbD2HQiCsiB9 Uj/qLtG3CaZQVtkCSC1s3NschLBgWHfQ9xkb3Peqzg== ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Unbreakable Cipher
On Wed, 2013-09-25 at 10:11 -0400, John Young wrote: [Answer to the question:] Does there exist an unbreakable cipher would be this, Every cipher is breakable, given enough traffic, and every cipher is unbreakable, if the traffic volume is restricted enough. [End quote] Is this conclusion still valid? If so, what could be done to restrict traffic volume to assure unbreakablility? And how to sufficiently test that. Presuming that NSA and cohorts have investigated this effect. Sure it is. XTS-AES must be rekeyed after each terabyte; WEP was limited by a 24-bit initialization vector; etc. There are always limits, but sometimes they are literally astronomical. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Unbreakable Cipher (2)
- Forwarded message from coderman coder...@gmail.com - Date: Wed, 25 Sep 2013 23:38:58 -0700 From: coderman coder...@gmail.com To: brian carroll electromagnet...@gmail.com Cc: cpunks cypherpu...@cpunks.org Subject: Re: The Unbreakable Cipher (2) On Wed, Sep 25, 2013 at 9:29 PM, brian carroll electromagnet...@gmail.com wrote: ... no- not for a multilinear/nonlinear bit set approach. voluminous data exchange... you're wrong. the key is to re-key so frequently there is never a significant volume transferred under the same symmetric key. in the manually keyed IPsec experiment i mentioned in another thread, we used synchronized key daemons to maintain a rolling pair of SA/AH+ESP associations that rotated on a per second interval. as long as you didn't transfer more than some obtuse number of terabits in a given second the assurance provided by a random key is intact. (and we used VIA C5P dual RNG processors to provide the manual keying material that was kept in sync between a pair of communicating stations over unencrypted 802.11b - there was no IKE or other public key exchange, just synchronized symmetric ciphers and digests) - End forwarded message - -- Eugen* Leitl a href=http://leitl.org;leitl/a http://leitl.org __ ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org AC894EC5: 38A5 5F46 A4FF 59B8 336B 47EE F46E 3489 AC89 4EC5 signature.asc Description: Digital signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] The Unbreakable Cipher
NSA Technical Journal published The Unbreakable Cipher in Spring 1961. http://www.nsa.gov/public_info/_files/tech_journals/The_Unbreakable_Cipher.pdf Excerpts: [Quote] David Kahn, Lyen Otuu Wllwgh WI Etjown pp. 71, 83, 84, 86, 88 and 90 of the New York Times Magazine November 13, 1960 says that an unbreakable cipher system can be made from one time key that is absolutely random and never repeats. ... For each cipher system there is an upper bound to the amount of traffic it can protect against cryptanalytic attack. What is cryptanalytic attack? It is a process applied to cipher text in order to extract information, especially information contained in the messages and intended to be kept secret. If some of the information is gotten by other means and this results in more being extracted from the cipher, this is (at least partially) a successful attack. If certain phrases can be recognized when they are present, this is successful cryptanalysis. If a priori probabilities on possible contents are altered by examination of the cipher, this is cryptanalytic progress. If in making trial decipherments it is possible to pick out the correct one then cryptanalysis is successful. ... Another example is that of Mr. Kahn, one-time key. Here the limit is quite clear; it is the amount of key on hand. The key arrives in finite messages, so there is only a finite amount on hand at anyone time, and this limits the amount of traffic which can be sent securely. Of course another shipment of key raises this bound, but technically another cipher system is now in effect, for by my definition a cipher system is a message. A sequence of messages is a sequence of cipher systems, related perhaps, but not the same. ... [Answer to the question:] Does there exist an unbreakable cipher would be this, Every cipher is breakable, given enough traffic, and every cipher is unbreakable, if the traffic volume is restricted enough. [End quote] Is this conclusion still valid? If so, what could be done to restrict traffic volume to assure unbreakablility? And how to sufficiently test that. Presuming that NSA and cohorts have investigated this effect. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Unbreakable Cipher
For your question: Session keys and key rotation? Den 25 sep 2013 16:11 skrev John Young j...@pipeline.com: NSA Technical Journal published The Unbreakable Cipher in Spring 1961. http://www.nsa.gov/public_info/_files/tech_journals/The_Unbreakable_Cipher.pdf Excerpts: [Quote] David Kahn, Lyen Otuu Wllwgh WI Etjown pp. 71, 83, 84, 86, 88 and 90 of the *New York Times Magazine *November 13, 1960 says that an unbreakable cipher system can be made from one time key that is absolutely random and never repeats. ... For each cipher system there is an upper bound to the amount of traffic it can protect against cryptanalytic attack. What is cryptanalytic attack? It is a process applied to cipher text in order to extract information, especially information contained in the messages and intended to be kept secret. If some of the information is gotten by other means and this results in more being extracted from the cipher, this is (at least partially) a successful attack. If certain phrases can be recognized when they are present, this is successful cryptanalysis. If a priori probabilities on possible contents are altered by examination of the cipher, this is cryptanalytic progress. If in making trial decipherments it is possible to pick out the correct one then cryptanalysis is successful. ... Another example is that of Mr. Kahn, one-time key. Here the limit is quite clear; it is the amount of key on hand. The key arrives in finite messages, so there is only a finite amount on hand at anyone time, and this limits the amount of traffic which can be sent securely. Of course another shipment of key raises this bound, but technically another cipher system is now in effect, for by my definition a cipher system is a message. A sequence of messages is a sequence of cipher systems, related perhaps, but not the same. ... [Answer to the question:] Does there exist an unbreakable cipher would be this, Every cipher is breakable, given enough traffic, and every cipher is unbreakable, if the traffic volume is restricted enough. [End quote] Is this conclusion still valid? If so, what could be done to restrict traffic volume to assure unbreakablility? And how to sufficiently test that. Presuming that NSA and cohorts have investigated this effect. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Unbreakable Cipher
On Wed, Sep 25, 2013 at 10:11:33AM -0400, John Young wrote: Is this conclusion still valid? If so, what could be done to restrict traffic volume to assure unbreakablility? And how to sufficiently test that. You need to be able to estimate the rate of information leakage. This seems to be related to measuring RNG entropy, and is considered a hard (perhaps hopeless?) problem. Presuming that NSA and cohorts have investigated this effect. It seems to be possible to construct a family of cyphers based on PRNGs with Very Large Internal State (the shared key is the state) that asymptotically approach (in a special/edge case are exactly equivalent to) one-time pads. You'd tap them for XOR with cleartext through a relatively small (=plenty of hidden state) window (not necessarily contiguous) and use enough iteration rounds to make sure the information has has a chance to propagate through the computational volume. Edge cases are low-dimensional CAs with a suitable rule, which should be easiest to attack. Higher-dimensional CA analoga have a lot of neighborhood cells, and their map to address space looks like a small world network, so state mixes quite rapidly, requiring fewer rounds. Whether making neighborhood itself random versus orthogonal is helping or hindering things is not obvious. Whether to make the neighborhood itself subject to change at each or N rounds is helping or hindering things is not obvious. The actual problem is to build them provably hard to reverse, and rekey (though a secure channel, natch) before they leak enough information about their inner state to be attackable. signature.asc Description: Digital signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Unbreakable Cipher
On Wed, Sep 25, 2013 at 10:11 AM, John Young j...@pipeline.com wrote: NSA Technical Journal published The Unbreakable Cipher in Spring 1961. http://www.nsa.gov/public_info/_files/tech_journals/The_Unbreakable_Cipher.pdf Excerpts: [Quote] David Kahn, Lyen Otuu Wllwgh WI Etjown pp. 71, 83, 84, 86, 88 and 90 of the *New York Times Magazine *November 13, 1960 says that an unbreakable cipher system can be made from one time key that is absolutely random and never repeats. ... I'm not sure why this was news in 1961; Shannon had this observation a decade earlier and the one-time pad predates that. [Answer to the question:] Does there exist an unbreakable cipher would be this, Every cipher is breakable, given enough traffic, and every cipher is unbreakable, if the traffic volume is restricted enough. [End quote] Is this conclusion still valid? Every cipher is breakable, given enough traffic: in principle, yes, as long as the traffic (formally, the entropy of the traffic) is larger than the keylength. Every cipher is unbreakable, if the traffic volume is restricted enough: not true; the cipher that ignores the key and outputs the message in the clear is not secure for any non-zero traffic. On the other hand, the one-time pad is secure as long as the traffic is less than the keylength. If so, what could be done to restrict traffic volume to assure unbreakablility? And how to sufficiently test that. Presuming that NSA and cohorts have investigated this effect. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Unbreakable Cipher
On Sep 25, 2013, at 9:40 , Jonathan Katz jk...@cs.umd.edu wrote: Every cipher is breakable, given enough traffic: in principle, yes, as long as the traffic (formally, the entropy of the traffic) is larger than the key length. You misstated this. It's breakable if the *redundancy* of the traffic is larger than the key length. regards, Greg. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] The Unbreakable Cipher
On Wed, Sep 25, 2013 at 1:30 PM, Greg Rose g...@seer-grog.net wrote: On Sep 25, 2013, at 9:40 , Jonathan Katz jk...@cs.umd.edu wrote: Every cipher is breakable, given enough traffic: in principle, yes, as long as the traffic (formally, the entropy of the traffic) is larger than the key length. You misstated this. It's breakable if the *redundancy* of the traffic is larger than the key length. Not so; this is most easily seen by taking the uniform distribution over n-bit messages, in which case the entropy is n and the redundancy is 0. regards, Greg. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
